Sign in to follow this  
Lesan

Flood pathfinding

Recommended Posts

I realize you get tons of these messages. However, nowhere I have been able to find a tutorial for this even though it's, I think, quite a common problem. I develop a tile-based turn-based strategy game. When the player selects a unit, the tiles where the unit is able to move to get highlighted like on the following picture. Each unit has its own movement points (for example 50) and every tile has its movement cost (grass 10, forest 20, ...) Also, when the unit walks diagonally, the cost is multiplied by 1.42 (When a unit crosses to forest, the step costs 20*1.42.) The code I am using, however, works for small distances only. When I select a unit with, let's say 120 movement points, it takes up to 2 seconds to display the possible tiles. That's too slow. Here's the code I am using:
private void FloodFill(Node node, Unit u, float energyremains, bool view, bool beginnode, bool diagonal)
        {
// node - The tile on which stands the unit
// energyremains - initially the energy of the unit, it gets lower and lower with recursion
// view - no longer used, assume always false
// begin node - currently examined node is the node on which stands the unit
            if ((!node.Occupied ) || beginnode)
            {
                float oldenergy = energyremains;
/* no longer needed
                if (view)
                {
                    float difficulty = node.Seedifficulty;
                    if (diagonal) { difficulty = (difficulty * 1.42f); }
                    node.Shrouded = false;
                    if (energyremains >= difficulty)
                    {
                        if (!beginnode)
                          energyremains -= difficulty; 
                    }
                    else
                    {
                        return;
                    }
                }*/
                else if (!beginnode)
                {
                    
                    float difficulty = node.GetWalkDifficulty(u);
                    if (diagonal) { difficulty = (difficulty * 1.42f); }

                    if (energyremains >= difficulty)
                    {
                        node.Reachable = true;
                        // If a node is reachable, it means it is highlighted and the unit can get there.
                        energyremains -= difficulty;
                    }
                    else
                    {
                        return;
                    }
                }

You don't have even to look at my code. I ask you only to give me a better solution to the problem, an effective solution to the problem, if exists. Thanks in advance.

Share this post


Link to post
Share on other sites
There's no need to go recursive here. It can lead to a lot of overhead and at some point you'll likely run out of stack, if the recursion goes too deep.

Just keep track of an open and closed node list, add your begin node to the closed list and the surrounding nodes to the open list, and then continually pick the cheapest node from the open list, mark it as closed, put it's neighbours in the open list (if they're not already closed or opened) and so on, until you run out of energy (for each node you'll have to keep track how much energy there's left).


You may want to search for 'flood fill' algorithms. They're not completely what you're looking for, but with some modifications (a sort of 'running out of paint' condition) they should be able to suit your needs.

Share this post


Link to post
Share on other sites
How big are your maps? If they're not that big, you might be able to pre-compute all the "reachable" points. For example, for each pair of tiles, you'll store a tuple like:

(tileA, tileB, distance)

This tuple would represent the number of moves (distance) required to go from tileA to tileB.

That way, calculating the highlighted area can be done in constant time at runtime.

Share this post


Link to post
Share on other sites
Just do a uniform-cost search instead of the depth-first search you're undoubtedly doing right now, and terminate recursion on an already-visited node.

Share this post


Link to post
Share on other sites
Quote:
Original post by Codeka
How big are your maps? If they're not that big, you might be able to pre-compute all the "reachable" points. For example, for each pair of tiles, you'll store a tuple like:

(tileA, tileB, distance)

This tuple would represent the number of moves (distance) required to go from tileA to tileB.

That way, calculating the highlighted area can be done in constant time at runtime.


That is true. The maps are about 50x50 tiles wide. The problem here is that some units, like Water Elemental, move fast in water while for other it's nearly an uncrossable terrain. Sorry, I did not mention that in the description. But thank you for the idea, I may try it.
Quote:
Just do a uniform-cost search instead of the depth-first search you're undoubtedly doing right now, and terminate recursion on an already-visited node.

I would love to do this, though it's not so easy.
Even if I already visited a tile, I still must revisit it because the new path may be shorter. Or the new path, leading across this already-visited tile may lead to a new, so far, unreachable tile.

Quote:

Just keep track of an open and closed node list, add your begin node to the closed list and the surrounding nodes to the open list, and then continually pick the cheapest node from the open list, mark it as closed, put it's neighbours in the open list (if they're not already closed or opened) and so on, until you run out of energy (for each node you'll have to keep track how much energy there's left).

So it would work like A* algorithm, only without heuristics and it would explore all open tiles (It wouldn't be stopped by reaching finish.)?
Sounds good, I hope I can implement it. I think I had something like this sooner in the development but it didn't work quite right...

Share this post


Link to post
Share on other sites
Quote:
Original post by Lesan
So it would work like A* algorithm, only without heuristics and it would explore all open tiles (It wouldn't be stopped by reaching finish.)?
Sounds good, I hope I can implement it. I think I had something like this sooner in the development but it didn't work quite right...

It's not like there's no heuristic, it's just different. Rather than trying to pick the tile that's closest to the finish, pick the one that's cheapest to move to next. After all, there's no finish: there's only running out of movement points. This approach also ensures that you always reach a tile in the fastest way possible, there's no need to revisit tiles.


You may want to cache the results, if you expect a player to frequently cycle between units before making actual moves.

Share this post


Link to post
Share on other sites
Quote:
Original post by Lesan
That is true. The maps are about 50x50 tiles wide. The problem here is that some units, like Water Elemental, move fast in water while for other it's nearly an uncrossable terrain. Sorry, I did not mention that in the description. But thank you for the idea, I may try it.
Ah, yes, that would throw somewhat of an onion in the ointment :)
Quote:
Original post by Lesan
Quote:
Just do a uniform-cost search instead of the depth-first search you're undoubtedly doing right now, and terminate recursion on an already-visited node.

I would love to do this, though it's not so easy.
Even if I already visited a tile, I still must revisit it because the new path may be shorter. Or the new path, leading across this already-visited tile may lead to a new, so far, unreachable tile.
I don't think you'd need to revisit tiles. If you reach a previously-visited tile, but this time with a lower cost, you just substitute the old cost with the new (lower) one - no need to keep going from that point, because presumably you've already found all possible routes away from that tile (or some of the routes are still in your "open" list at least). Unless, of course, the possible exits from a tile depends on the direction you came from (e.g. a bridge where you can go north-south over the bridge, or east-west under it, etc)

In fact, if you're doing an A*-style prioritized search (where you search lowest cost routes first) then you can't reach a previously visited tile with a lower cost anyway.

Share this post


Link to post
Share on other sites

Solved!





Thank you all for advice.
I implemented Captain P's method and it works well. I encounter problems now only on a 100x100 map without any obstacle (I made this map specifically for testing speed and memory problems) when I use my "God" unit (with unlimited energy). But even then, it takes only a few seconds to calculate it.

My problem is solved.
I will never have these "God" units in the game anyway.
But, I think there are games that need to calculate fast even that large field... or not?

Share this post


Link to post
Share on other sites
Quote:
Original post by Lesan
I would love to do this, though it's not so easy.
Even if I already visited a tile, I still must revisit it because the new path may be shorter. Or the new path, leading across this already-visited tile may lead to a new, so far, unreachable tile.

Incorrect. That's the whole point of uniform cost search instead of other searches: When you visit a node for the first and only time, you are guaranteed that you are visiting through the shortest path to the node. In fact, this is pretty much what Captain P suggested, leading me to wonder what you think UCS is.

Share this post


Link to post
Share on other sites
Quote:
Original post by Sneftel
Quote:
Original post by Lesan
I would love to do this, though it's not so easy.
Even if I already visited a tile, I still must revisit it because the new path may be shorter. Or the new path, leading across this already-visited tile may lead to a new, so far, unreachable tile.

Incorrect. That's the whole point of uniform cost search instead of other searches: When you visit a node for the first and only time, you are guaranteed that you are visiting through the shortest path to the node. In fact, this is pretty much what Captain P suggested, leading me to wonder what you think UCS is.

I understand now.

Uniform Cost Search, I thought, was a way of finding all the possible tiles in a constant time (or at least linear).
Now, it seems to me, a UCS is for example what I just implemented. (Using Captain P's advice).

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this