I'm working on a game which uses a tilemap. Squares on the map can either be walls or they can be empty. The algorithm I'm trying to develop should take a point on the map and return the number of cells that can be reached from that point (which is equal to the area of the sector containing the point).
Let the function which carries out the algorithm take an x-coordinate, a y-coordinate and a map in the form of a 2D array.
function sectorArea(x_coord,y_coord,map) { ... }
Say the map looks like this (where 1's represent walls):
map = [0,0,1,0,0,0],
[0,0,1,0,0,0],
[1,1,1,0,0,0],
[0,0,0,0,0,0]
Then sectorArea(0,0,map) == 4 and sectorArea(4,0,map) == 15.
My naive implementation is recursive. The target cell is passed to the go function, which then recurses on any adjacent cells which are empty - eventually spreading across all empty cells in the sector. It runs too slowly and reaches the call stack limit very quickly:
function sectorArea(x_coord,y_coord,map) {
# First convert the map into an array of objects of the form:
# { value: 0 or 1,
# visited: false }
objMap = convertMap(map);
# The recursive function:
function go(x,y) {
if ( outOfBounds(x) || outOfBounds(y) ||
objMap[y][x].value == 1 || objMap[y][x].visited )
return 0;
else
objMap[y][x].visited = true;
return 1 + go(x+1,y) + go(x-1,y) + go(x,y+1) + go(x,y-1);
}
return go(x_coord,y_coord);
}
Could anyone suggest a better algorithm? A non-deterministic solution would actually be fine if it is sufficiently accurate, as speed is the main issue (the algorithm could be called 3 or 4 times on different points during a single tick).
Maybe you can speed up the algorithm itself. Wikipedia suggests that a scanline approach is efficient.
As for the repeated calls: You can cache the results so that you don't have to run the area calculation again every time.
An approach might be to keep an region map of integers alongside your tiles. This denotes several regions, where a special value, -1 for example, means no region. (This region map also serves as your visited attribute.) In addition to that, keep a (short) array of regions with their areas.
In your example above:
When you calculate the area of (0, 0), you will assign 0 to the four tiles in the northwest corner. You will also append the area, 4, to the area array.
When you calculate the area of (0, 1), you notice that the region map for that coordinate has a value of zero, not -1. That means that the area was already calculated.
When you calculate the area of (4, 4), you find -1 in the region map. That means that the region hasn't been calculated yet. Do that, mark the region with 1 and append the new area, 15, to the area array.
I don't know how often the board changes. When you must recalculate the regions, blank out the region map and empty the array list.
The region map is only created once, it isn't recreated for every tick. (I can see this as a potential bottleneck in your code, when the objMap is frequently recreated instead of just being overwritten.)