CODEWITHSUNDEEP
algorithmgraphgame-enginea-starflood-fill
Maglos
Maglos

Reputation: 88

Floodfill an area and construct A star path

Consider a turn based game on a 2d grid, where a piece can move to an unoccupied cell provided it only takes a certain amount of steps to get there. When the piece is selected, I want to highlight all possible destination cells and display them - this is where I'm using a floodfill to recursively build a map of available cells and then overlay that on the board. Once a valid square is selected, I then use A* to find a path to the square that the piece will follow.

Intuitively it seems like there's wasted work in this approach - I've gone to the trouble of generating a set of walkable squares, only to have do extra work to search through it and actually walk it.

This seems like a common feature in many games, is there a streamlined approach already out there? Or perhaps, given the resultant grid from the floodfill is irregular but guaranteed to be walkable, is the apparent overwork negligible?

Upvotes: 2

Views: 770

Answers (1)

Nico Schertler
Nico Schertler

Reputation: 32597

Of course, just remember the path that you took during flood-filling (conceptually, it is actually more of a breadth-first search).

This is usually done by remembering the predecessor cell during exploration. Once you have the final cell (i.e., the user clicks on it), traverse the path back by following the predecessor links until you find the start node. Just as you would do at the end of A*. The only difference is that the forward pass is now calculated by your BFS approach.

Upvotes: 2

Related Questions