Game Development Stack Exchange is a question and answer site for professional and independent game developers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I've looked a bit at Breadth-First and Depth-First search algorithms and I think I've got a pretty good idea of how they work.

Now I am here :

The problem is I don't see how a 2D grid can help with a 3D game. I suppose that wouldn't be a problem if the 3D game didn't have the AI explore multiple levels of a building, but since that is most often what occurs, I am not sure how I would "simplify" my static level geometry and my physics-dynamic changing scene into a structure that can be easily be traversed to determine a path to a goal node.

share|improve this question
I think your question could be better phrased as "How do I apply A* to a complex and dynamic 3D environment?" – AttackingHobo Nov 17 '10 at 4:47
up vote 9 down vote accepted

A*, BFS or DFS all search graphs. It doesn't have to be a graph with equidistant nodes as in a 2D Grid. It could also be a graph like in the following image (from Wikipedia):

map of Germany graph

Now imagine that the nodes of that graph lie in a 3D environment. They would have a position (X,Y,Z) and using that you can also calculate the distance to the neighbor nodes, which in turn can be used for the heuristic function in A* (for speed, simply use the squared length and skip the sqrt). Of course the graph can also be changed dynamically.

Maybe you'll even have to use several graphs. One that just models connections between rooms (fast calculation of: can I get from here to this other room?) and one fine-grained graph for the actual movement. There are also 3D "flood-fill" algorithms that can create such a graph for you, given some 3D data. These are rather CPU heavy though and you shouldn't run them during game.

For dynamic objects, I would probably use steering behaviors to avoid them (eg. a barrel or a chair in the way). There's usually no need to update the graph for objects like this.

share|improve this answer
Right on. To build on that last paragraph a bit, dynamic obstacles really call for more than just waypoints and A*: – Steve S Nov 17 '10 at 15:14

It might help if you think of the connections in tiles as literal connections.

They can be between squares like in a tilebased game, or between polygons or level chunks.

Astar only cares about a heuristic of movement from one node to the end, and the ability to ask for 'all my neighbors' so you can add them to the open list.

Try implementing 2d Astar with that in mind, I tend to create my array, and then do a second pass creating links to all the neighboring tiles. The advantage of doing this, is it is only a simple task to change to 8 way movement, and even adding teleporters that Astar respects (add a connection to far away tiles!)

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.