- I have a question that relates to writing games, that I can’t seem to find an answer for: I am attempting to write an action/FPS game and I need a method of finding the fastest way between any two points in a complex maze (that is, a maze that may have more than one path between any two points).
- Two factors are needed: the next proper direction to take, and the distance information of that path (or distance between points), so that the shortest path to the next point can be found.
- The underlying principle of the game depends partly on the computer being able to guide the “enemies” I this fashion, and the maze is prety complex; I would suppose that all-out searching is too expensive in processor time. Is there any way of naming the paths or connecting points, so that info on how to reach a target point from any destination can be deduced by comparing the two coordinates? I found a method that works perfect for simple tree structures (those with only one possible path between any two points on the tree) but it fails for complex trees. The length of a path doesn’t have to be stored in the path name (or, alternatively, the length between points if the points are named); just the proper direction to take. The length data can exist in another array.
I’ve been lurking at the local book superstores, reading the game programming books for free, and none treat the subject of how to tell a computer to navigate a maze. Any ideas, besides simple searching? - MC
- To elaborate: a simple maze (one with only one possible path between any two points) presents a tree structure. In this case finding a way from any point to any other point is just using simple set theory, but this doesn’t work if the higher branches of the tree reconnect with other branches (as the need to for the game’s sake). Anyone not unconfused don’t unraise your hand. - MC
If the maze is constant, the best thing to do is just crunch out what the best direction is for each point either at precompile time (using a lookup table) or at run time before the action of the game initiates. Either way you won’t slow down game time.
Depending on how you store the maze, the lookup table could even be inherent to the data structure; although, you might just have to do an exhaustive search, at least you can start at dead ends and work your way back out. It shouldn’t matter if you have crossover points ultimately because only one direction is ever the best solution just like in a more simple tree.
figuring it once seems best, unless the maze itself is constantly changing. Even if it’s extensible, you could do a chunk at a time.
BTW, if you haven’t already, you might want to try asking (newsgroup) comp.ai.games – they deal with a lot of pathfinding and maze stuff in there.
this .sig left intentionally blank
If you haven’t already, maybe you should investigate some of the “bot” programs available for Quake I and Quake II. (I’ve seen EraserBot’s operation described in decidedly non-geek terms, for example.) Some of them used a compile-time map-analysis step to create a graph of paths that the bots could use to get from one area to another. Some (like EraserBot) were able to build the graph as the game was played, meaning they got better at navigating as the game went on. You may be able to get source code for some of the bot projects, as they were free labor-of-love type projects. It’s my understanding that one of the bot project leaders was recruited by id software to help make the bots that are included in Quake III.
I’m no expert, but I’d guess that if you want a truly general solution to traversing such a graph, you’re going to have to resort to at least some searching. This sounds like it’s related to the old “travelling salesman” comp-sci problem. I think of it as one of those problems for which there are no ideal solutions, and dealing with it amounts to picking the solution that sucks the least. Fortunately, modern computers, particularly those with enough horsepower to run FPS games, shouldn’t have too much trouble with a little searching.
The typical way to find the shortest path through a graph is Dijkstra’s algorithm. (Mazes are easily converted into mathematical graphs.) You’ll find it in any CS algorithms book, and it’s probably online somewhere too.
It’s nice to know my education occasionly has a practical application.
Here’s a very cool Java applet demonstrating Dijkstra’s Algorithm.