Open NathanLovato opened 1 year ago
I solved this problem using a distance-limited flood fill. https://www.redblobgames.com/grids/hexagons/#range-obstacles
It should be pretty easy to modify the current scripts. Here is what I did:
func distance_limited_flood_fill(start_cell: Vector2i, movement_range: int):
var visited := Array()
visited.append(start_cell)
var fringes := Array()
fringes.append([start_cell])
for k in range(0, movement_range):
fringes.append(Array())
for center_cell in fringes[k]:
for neighbor_cell in arena_tile_map.get_surrounding_cells(center_cell):
if neighbor_cell in visited:
continue
if cell_is_blocked(neighbor_cell):
continue
visited.append(neighbor_cell)
fringes[k + 1].append(neighbor_cell)
return visited
This was written for Godot 4 and takes advantage of the fact that tilemaps now have a built-in get_surrounding_cells()
function. In fact the project I am working on uses hexes, but the function works for any type of tilemap.
My cell_is_blocked()
function is where you could put the existing code that checks if the cell is out of bounds, occupied by a unit, or has an obstacle.
The flood fill algorithm will, in some cases, reach cells too far beyond an obstacle. we need to keep track of the walk distance of each cell in the function.