hi,guys.
i am developing a TD game.

here is a simple description for the game:
the enemies walk along a shortest path from the entrance to the exit.when a tower is putted in their way.there will find a new shortest way.

the whole map has 26*15=390 cells.i use A* to find their shortest way.sometimes it will take up to 2941ms for a A* search on android.

i am now make every enemy has its own shortest way,so that when a tower is putted,every enemy can find their way home.i kown this is very inefficiency,but i can't find another solution.

my question is: is there any good solution for when to recalculate path for enemy so that reduce unnecessary calculations.

any advice will be grateful
PS:forgive my poor english

Payne

Instead doing A* for each enemy, calculate for each cell of your game field how many cells/tiles is to destination. It can be done very efficiently with BFS (Breadth-first search) starting from destination and filling field backwards. Then, when some monster wants to know where to go next from current cell, just look up in every neighbor cell which of them has value equal to number of current cell minus 1. That will guarantee shortest path. Also, when you place tower or remove one, then recalculate these numbers for all cells. This way it won't matter how many monsters are on your field.

What he said, but also I don't think it is necessary to recalculate the whole field every time a tower is placed. A unit will only possibly travel into a square if there is a neighboring square whose distance from the goal is exactly one bigger. So you can start at where the tower is placed (or removed) and work your way out from there updating cells only if necessary, and you only need to ever check neighbors of updated cells potentially not touching large sections of the board. If it's still going too slow (which I doubt but I don't know anything about mobile capabilities) you could spread your updates over several frames as well. It might take the guys a fourth second to turn around, but I doubt that would bother the player much.

Original post by Alrecenk
hi，Alrecenk，thanks for your advice.but i can't understand these sentance.

So you can start at where the tower is placed (or removed) and work your way out from there updating cells only if necessary, and you only need to ever check neighbors of updated cells potentially not touching large sections of the board.

can you describe it more in detail?and how to implement it in code or some code example?
thank you very much.

Here's how to do it, with an example done by hand:

We start with a grid where '+' represents an obstacle, '.' represents empty space and '0' marks the exit:

.................+++.....+...+.0.+...+.....+++..........

Then we use Dijkstra's algorithm: Whatever '.' is adjacent to a '0' is a '1', then whatever '.' is adjacent to a '1' is a '2', and so on (I used 'a'=10, 'b'=11, etc.):

a987654398765432a+++4321 b+765+10c+876+21ba9+++32a9876543

Now imagine we drop an extra obstacle in there, on the '4' in the third line (the one in boldface). You can consider its neighbors suspect, so you have to check if they are still touching something that is one step closer to the goal than themselves. For instance, the '5' above is fine, because it is still touching a '4'. But the '5' below is not touching a '4'. Therefore, we wipe it out to '.' and consider its neighbors suspect. We keep doing this recursively until we have this situation:

a987654398765432a----321 b-...-10c-...-21ba9---32a9876543

Finally we run Dijkstra's algorithm again to figure out the correct distances to the goal from things marked with '.':

a987654398765432a----321b-bcd-10c-abc-21ba9---32a9876543

Is that clear now?

Thanks alvaro. Your example is far superior to what I would have said.

thanks for alvaro and Alrecenk
every one is very kind.
very grateful.

a completely different approach would be a influence map, scent, however you wanna call it:

each N milliseconds, the tile of the exit gets set to 1.0, the entrance and tiles with towers on them get set to zero, and then you average each tile with the value of the neighbours. this way the "scent" of the exit moves across the map and gets blocked by towers. for an enemy to move towards the exit, it just moves towards the neighbouring tile that has the strongest scent.

I have no idea how that compares performance wise, but depending on how you tweak it you can certainly get all sorts of interesting results (if for example enemies subtract, say, 0.1 from the scent of tile they're on, those behind them will seek out less traveled routes etc). And you can do it in small steps, instead of calculating the whole path perfectly, it gradually adjusts itself. This also makes enemies seem *much* less robotic.