# Pathfinding with multiple random paths in a Tower Defense game

I thought about random pathfinding for my Tower Defense game. A* would not work for my puposes, because I specifically need random pathfinding.

Imagine a map with routes, a starting point and a destination. I have multiple routes, which all lead from the starting point to the destination, one way or another. It could look like this:

Color description: red - starting point; black - destination; grey - route; white - free space
(The numbers are used in the text as a reference to some tiles)

I first thought about just calculating the next waypoint randomly, when an entity passes a tile. But that would not work. When an entity passes tile 1 it either can go up or down. When it comes to 2 it can either go down/up (relative to it´s position) or right.
If it goes down/up it would go to tile 1, which means that it goes backwards. Bad...

I would really like to make it dynamic, but I can´t figure out what I can do now. Anyone with ideas or experience in this?

• Most tower defense games I am aware of make the things crawl the Shortest path to the exit and block any moves that would invalidate from exiting... The hard part here would be making sure to recalculate the paths when the player changes the tower layouts – James Apr 15 '11 at 20:58
• @James: Do you mean getting the shortest path, which is A*, or do you mean crawling through the waypoints to get valid directions for every tile. I also don't need to recalculate the path since my ways are fixed and the player can't place towers there. But in general you are right. – Marco Apr 15 '11 at 22:12

Instead of having all adjacent squares as possible next waypoints, only include squares that do not lead back to the beginning and randomly pick from those. If you did this, it would be impossible to go backwards because going back is not an option.

This is a directed graph problem with each waypoint as a vertex, and each path an edge. You just need to limit the number of cycles, perhaps removing them entirely.

• That was my second thought. I have to think about the implementation of "the way leads back now" thing. Limiting the number of tiles to pass would not be dynamic and flexible. – Marco Apr 15 '11 at 22:18
• You can solve this by building a directed graph and keeping track of the visited/unvisited tiles. Then just make sure you search unvisited tiles only. That should build you a graph that represent your paths. Now if you hit a tile where a note has several outgoing edges (in the graph that was previously built), just pick one randomly. – bummzack Apr 15 '11 at 22:37
• I meant to write "node" not "note" in my previous comment. Sorry. – bummzack Apr 16 '11 at 7:53
• @bummzack: No, that wouldn't work. Imagine a map with 3 paths. If I search for unvisited nodes, I could also simply go to the beginning. I think about implementing a algorithm which crawls through the map and randomly chooses between the directions. When it realizes that it goes back to the beginning this part is unusable. I could do this with a counter. When the distance to the start gets smaller it goes back. This would be parsed once on map creation in development process, so there are no performance issues. – Marco Apr 16 '11 at 10:05
• @Marco Why wouldn't that work? If you implement a breadth first search from your start-node, you won't visit previous nodes again. You'll never return to beginning, because it's much like a flood-fill. – bummzack Apr 16 '11 at 10:35

You say random, but how much randomness do you want? Is it ok if the enemies pick a path that is 10 times as long as the shortest one? Is it ok if the enemies enter a dead end and have to backtrack? That is, random over what set of paths, and with which probability distribution?

Assuming you want the enemies to prefer short paths, you could use A*, but randomly vary the edge weights fed to it. Then, enemies will always choose a random path that visits each node at most once, with a bias towards shorter paths. In particular, if without randomization there would be several paths of same length, each of these paths would be chosen with equal probability.

Alternatively, in A*, you could iterate over neighbours in random order. In your eaxmple, when path finding reaches node 1, it would at random enqueue the top of bottom neighbour first, causing the top or bottom path to considered first. This solution would cause enemies to pick among all shortest paths at random. In your simple example, both shortest paths would be equally probable, but in a situation like:

start -+--------+
|        |
+--------+
|        |
+--------+- end


the top path would be chosen at probability 1/2, while the bottom ones would be chosen at probability 1/4 each.

• I'm not sure what exactly the OP means by "random pathfinding" but your solution for picking randomly among all shortest paths is what I would assume he meant, and your "alternatively etc" is a great solution for that problem. – jhocking Apr 27 '11 at 14:29

Just a proof of concept:

1. Choose a random direction.
2. If this would cause us to go somewhere we've already been, pick another direction.
3. If we have run out of directions go back to the last square with a unexplored direction.