All Questions

Community

Daniel Queiroz Porto

Alternative flood fill for when the number of cells walked is important

In the tabletop game I'm doing with my friend when we say a piece has a "movement_range of 3" we mean that It can only walk 3 cells. With the flood fill algorithm as is I'll be able to walk to any cell that is at a max distance of 3 and not really just 3 cells.

For example, this should not be allowed

So to I did some small changes to the flood fill that worked for me, like this:

func _flood_fill(cell: Vector2, max_distance: int) -> Array:
var array: = []
var stack: = [{cell = cell, distance = 0}]

while not stack.empty():
var current: Dictionary = stack.pop_front()

if not game_board_data.is_within_bounds(current.cell):
continue
if current.cell in array:
continue

if current.distance > max_distance:
continue

array.append(current.cell)
for direction in DIRECTIONS:
var coordinates: Vector2 = current.cell + direction
if is_occupied(coordinates):
continue
if coordinates in array:
continue

stack.append({cell = coordinates, distance = current.distance + 1})

return array

I don't think the change from "pop_back" to "pop_front" is really necessary, I just did it so that I could get them in order of "closer cells". The main change was dealing with distance by assigning a value to each cell rather than calculating it.

So the starting cell is at distance 0, all of it's neighbors are at distance 1, and then their neighbors are at distance 2 and so on and so forth, like counting steps.

So that cell that is behind another piece in the example actually has a distance of 4 instead of 2, that is what I get if I just calculate it's distance from the starting cell instead of counting how many steps it took to get there.

Now it works!

  • Nathan Lovato replied

    Great job! Thanks for sharing, always appreciated 🙂