# 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 Commented Apr 15, 2011 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. Commented Apr 15, 2011 at 22:12
• If this would cause us to go somewhere we've already been, pick another direction. Commented Nov 8, 2022 at 9:17

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. Commented Apr 15, 2011 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. Commented Apr 15, 2011 at 22:37
• I meant to write "node" not "note" in my previous comment. Sorry. Commented Apr 16, 2011 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. Commented Apr 16, 2011 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. Commented Apr 16, 2011 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. Commented Apr 27, 2011 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.