5
\$\begingroup\$

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 : Link

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.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ I think your question could be better phrased as "How do I apply A* to a complex and dynamic 3D environment?" \$\endgroup\$ Commented Nov 17, 2010 at 4:47

2 Answers 2

Reset to default
9
\$\begingroup\$

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.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Right on. To build on that last paragraph a bit, dynamic obstacles really call for more than just waypoints and A*: ai-blog.net/archives/000152.html \$\endgroup\$ Commented Nov 17, 2010 at 15:14
3
\$\begingroup\$

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!)

\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.