Path Finding Via 'Ant Races' (a floodfill algorithm) Assume you have a large board with varied terrain, perhaps some impassable terrain. Moves are strictly defined as moving one square on the board; moving that one square may take a longer or shorter time. How can you find the best way to get from one place to another? Introduction: Visualize trying to find your way across the board. You release a flood of ants at the start, and the first ant that reaches your destination has found the best path. How do you find the actual path? Each time an ant steps on a new square it labels that square with the time it took to get to that square. (Ants are not allowed to go where other ants have stepped.) When one ant reaches the destination, you can find your way back to the start by always moving into the square with the least time label. To find the path from the start to the end, simply have your mass of ants begin at the end and try to get to the start. Implementation for simple terrain (strictly passable/blocked): Consider a list of ants. Each turn, each ant moves to its destination square and marks it with the current time, spawns a number of new ants for each free square (that are unmarked and passable) and removes itself from the list. Implementation for variable terrain: Consider a list of ants. Every time tick, you go through the list and decrement the time remaining for each ant to reach its destination square. Ants that finally reach a new square (time left=0) shall mark that square with the current time and produce a number of new ants. One ant is produced for each unmarked and passable square that the old ant can get to from its current position. Each new ant is added to the list along with the time to its destination (the cost of the path to the square), and the old ant is removed. In this manner, each square is always marked with the least time taken to be reached. Once the 'start' is finally reached by some ant, one can quickly follow the path back to the 'end' by always moving to the adjacent square with the least time. Problems: Suppose two ants are heading for the same square? Ants can check if their destination square is already taken, and quietly die (sans offspring) if it is. On the other hand, given the assumption that the cost to get into this square is the same from any direction, then as soon as an ant arrives at a square, it can mark all the adjacent free squares, since no other ant could possibly do any better. That way, no two ants will never be heading for the same square. This saves a few cycles, too. Optimizations: Should we be keeping a big list of ants and checking them all every turn to 'move' them all (get them one tick closer to their destinations) and to see if any have arrived? That seems rather wasteful, especially if some ants are going to take a long time, hundreds of ticks maybe, getting from one square to the adjacent one. We can do quite a bit better with a modified data structure, actually. Consider not one list of ants, but a queue of lists of ants. Each list in the queue has the nice characteristic that every ant in that list will arrive at its destination at the same time, i.e. in list #1 in the queue, each ant will arrive in one time tick, in list #2 are all the ants that will arrive wherever they are going in two ticks, and so on. So list #0 is always the ants that have just arrived, that need to spawn children, mark squares, etc. To let one time tick pass, just move from the current list in the queue position to the next list in the queue. In this case, an index into an array of lists can keep track of the queue position. After dealing with the current list, bump up the index and deal with the next list. The index will wrap around from the end back to the beginning. How can we make sure that each list contains the ants arriving at the appropriate time? When producing a new ant that is heading for a square which will take 't' ticks to get to, put that ant in the list at position current array-index plus t [mod size of the queue]. So you need never check or update times; the position in the queue keeps track of times for you. The only timekeeping that must be done is knowing the current tick number to label just- reached squares with. Furthermore, you can make your list manipulation very simple, since you need never add or remove an ant except at the beginning of the list. Another minor optimization: Give your board an 'impassable' border, so that you need never check about going outside array bounds. How good is this algorithm? I don't think you can do better without changing the form of the problem. For each square, one ant is put onto a list, taken off a list, and the neighbors of that square are checked. It is O(n) on size of the board; approximately number of squares times number of neighbors for each square. Perhaps some other algorithm could do better for graphs in which each vertex had a large number of edges, since each edge is being checked twice. On a 486/80 with a purely C++ implementation, the time to find the best path for a 100x100 board, going from NW corner to SE corner, was ~60 milliseconds. The time was spent doing about 60,000 operations -- looking at each square four times, and creating and removing 10,000 ants. I suspect an implementation in assembler could do it in about 1/4 the clock time, making it practical for a realtime wargame. Note that we're finding the best path from _every square_ to the destination square, if we run the ant race until there are no new ants being formed. So, multiple units in a wargame with the same destination would incur no additional overhead. Possibilities for doing better by changing the problem may be compressing the board somehow, so that a large group of squares is considered as one square. I'd like to see somebody do a quad-tree implementation. Even so, running the ant races on the quad-tree graph would be a good way to find the actual paths. -- Richard Wesson