How to increase max system stack?

[EatYourBeetS]

Hi! In one of my games I need to check an area within dynamic borders and add it to a table, I'm using a recursive method:

Spoiler

#--------------------------------------------------------------------------# * GET INTERNAL_TABLE#-------------------------------------------------------------------------- def internal_table(x,y)@@internal_table.push([x,y]) if !@@internal_table.include?([x-1,y]) && terr_tile?(x-1,y)internal_table(x-1,y)endif !@@internal_table.include?([x+1,y]) && terr_tile?(x+1,y)internal_table(x+1,y)endif !@@internal_table.include?([x,y+1]) && terr_tile?(x,y+1)internal_table(x,y+1)endif !@@internal_table.include?([x,y-1]) && terr_tile?(x,y-1)internal_table(x,y-1)endend

It works well enough until the area to check exceeds a certain value, in that case a SystemStackError is raised, I'm sure that this method is not repeated infinitely, so I'd want to increase the maximum stack value, but I don't know which class contains it, and how is the stack's constant called, can you help me?

Also, if this can be solved in another and more efficient way, without touching the stack value, please tell me how to do it. Thank you for reading  . 

 

[Iavra]

I would strongly suggest to convert this method to an iterative one. Recursive method calls are almost always a bad thing.

 

[Andar]

Yes, I suggest looking for another way as well - if you got a tank leak that let's you loose a liter per kilometer, you shouldn't ask for a bigger tank - you should ask how the leak can be fixed...

Please describe what you want to do instead of how you want to do it, then we can point you to alternative solutions.

 

[EatYourBeetS]

I give this method a point in the map inside a certain area, then I want it to add every tile inside that area to a table, starting from that point,

- terr_tile?(x,y) returns true if the tile in that position is not a border(a special tile which can be either created by the player or be there by default)

- !@@internal_table.include?([x,y]) is a condition I added to avoid checking the same tile twice.

When this method ends the entire table is analyzed and the tiles inside it are changed accordingly to other variables, then @@internal_table is erased until internal_table(x,y) is called again, I'd really like to do it more efficiently, but I can't come up with anything else. 

e.g:

X = Border, O = free tile

OXXXOOOOXXXXOO

OXOXXXOXXOOXOO

XXOOOXXXOOOXXO

XOOOOOOOOOOXO

XXXOOXXXOOXXXO

OOXXXXOXXXXOOO

I want to get the area inside the border, can I do it using a while loop?

 

[Iavra]

Assuming, that you want to cover the whole map:

(0..$game_map.width - 1).each do |x|    (0..$game_map.height - 1).each do |y|        @@internal_table.push([x, y]) if terr_tile?(x, y)    endendI didn't actually test that, but this should iterate over every tile on the map and add it to @@internal_table if terr_tile? returns true.

 

[Andar]

I give this method a point in the map inside a certain area, then I want it to add every tile inside that area to a table, starting from that point,


<snip>


When this method ends the entire table is analyzed and the tiles inside it are changed accordingly to other variables, then


<snip>


I'd really like to do it more efficiently, but I can't come up with anything else.

That is a description on how you want to do something, but again you didn't tell us why you want to do that or what you want to achieve.
Why do you need the table? what will the player get as a result of that calculation? What will be done with the data of the table?


If you can answer those questions, then we might help you by providing some other methods, for example ways where you don't need to store the data in a table at all.

 

[Another Fen]

In many cases, the recursion depth of your algorithm is equal to the number of elements in your result.

You could use a queue for pending elements to resolve the recursion. You can also keep the size of the queue relatively small by evaluating latest additions last:

def internal_table(x,y)  included = Hash.new(false)  pending = [[x, y]]  # Iterate:  until pending.empty?    x, y = point = pending.shift    if !included[point] && terr_tile?(x, y)    included[point] = true    pending.push([x+1, y], [x-1, y], [x, y+1], [x, y-1]) end  end  # Return included Points:  return included.keysendEdit: Too slow, but didn't want to drop the post either...

Depending on what you actually want, this still might be unnecessary of course.

 

[EatYourBeetS]

Assuming, that you want to cover the whole map:

(0..$game_map.width - 1).each do |x|    (0..$game_map.height - 1).each do |y|        @@internal_table.push([x, y]) if terr_tile?(x, y)    endendI didn't actually test that, but this should iterate over every tile on the map and add it to @@internal_table if terr_tile? returns true.

Yes but terr_tile? only checks if that tile is not a border, using this method I would get both the tiles inside and outside the border...

@Andar Sorry if I'm wrong but I think I already answered those questions, I need the table because I want to separate one piece of the map inside a border from the rest of it, I would then only change that piece of map in different ways, for example I could make it either a "danger zone" which damages any character who steps upon it, a "healing zone" or a zone with some other random effects.

@Another Fen  Wow this works perfectly, it is so clever! Thank you so much 

 

[Andar]

I need the table because I want to separate one piece of the map inside a border from the rest of it,

So basically you want a list of positions that are inside some form on a map.
How is that border created and defined?


Usually if something like this is done, the sections are marked in the editor with a region ID, and the test is to just check for every position if it has the requested region ID - that's why you have 63 different IDs for map definitions.


Unless you somehow randomly generate your maps, or if your maps are too large and you're running out on IDs, there is no need to calculate that in any iteration.

 

[EatYourBeetS]

The border is created in-game by the player, if he presses a button while walking he traces a line on the ground (I should have better specified this), so he could also create complex geometric shapes, and it's impossible to pre-define them in the editor.

 

[Andar]

yes, in that case you'll have to calculate the area. I hope one of the alternatives above gives a better performance, and I think some of them need to be adjusted to differ between the inside and outside of a closed border.

 

[Another Fen]

Though the algorithm above is by no means the fastest solution, there might be other problems if the player is allowed to draw borders like this:

░░░░░▓▓▓▓▓▓▓▓▓

░░░░░▓░░░░░░░▓

░▓▓▓▓▓▓▓▓▓▓▓▓▓

▓▓░░░▓░░░░░░░░

▓░░░░▓░░░░░░░░

▓▓▓▓▓▓░░░░░░░░

 

[EatYourBeetS]

This can only happen when the central point is drawn last, In that case one of the two areas is chosen based on the player's direction.

As soon as two extremities connect a method begins iterating trough the entire border calling "get_points(x,y,d)" for each tile until it eventually finds one external and one internal point:

Spoiler

#--------------------------------------------------------------------------# * CALLED BY BORDER CHECK#-------------------------------------------------------------------------- def get_points(x,y,d)return if @@x_internal != 0 y_p = ((d == 6 || d == 4) ? 1 : 0)x_p = ((d == 2 || d == 8) ? 1 : 0)if (terr_tile?(x+x_p , y+y_p) && terr_tile?(x-x_p , y-y_p)) @@x_internal=x+x_p@@x_external=x-x_p@@y_internal=y+y_p@@y_external=y-y_p end end

I then call your method for each of those two point and check which area is smaller.

 

[Another Fen]

I'm not sure I understood exactly how the algorithm works, but you also might face similar problems with these shapes then:

░░░    ░▓▓▓▓░    ▓▓▓▓▓

░░░    ▓▓▓▓▓▓    ▓░░░▓

░▓░    ▓▓░░▓▓    ▓▓▓▓▓

░▓░    ▓▓░░▓▓    ▓▓░░░

░░░    ▓▓▓▓▓▓    ▓▓▓▓▓

░░░    ░▓▓▓▓░    ▓░░░▓

░░░    ░░░░░░    ▓▓▓▓▓

In case you face performance issues, a more complex way might be to follow the border and store the left/right boundaries for each line of the shape. At least in theory this should be a much more efficient when you deal with large areas (for small areas the floodfilling should do fine I think).