3D Pathfinding

[Guest]

Archived from groups: comp.ai.games (More info?)

Hello,

First off, I'm new to this group so here goes my first message.

I'm currently looking into various ways of doing 3d pathfinding in a game
that is very similar to Dungeon Siege and Neverwinter Nights.

It consists of tiles that are arranged together. Each tile is 3D and can
have more than 1 level. For instance, you may be able to go up a flight of
stairs as well as walk under the stairs on a single tile. I want things like
bridges as well in the game.

I'm wondering what my options are for pathfinding. If anyone has any
suggestions as to what I should look into, that would really really help me
out. I'm not looknig for a "do this" type of answer, I want to actually
understand what's going on so algorithms are what I need.

I've looked into A* and I have done simple 2D navigation with it but I
haven't been able to figure out how to exploit it for 3D navigation. If
anyone has a link to some usefull info, that would be really appreciated.

Shawn

 

[Guest]

Archived from groups: comp.ai.games (More info?)

Shawn Carroll wrote:

> I'm currently looking into various ways of doing 3d pathfinding in a game
> that is very similar to Dungeon Siege and Neverwinter Nights.

2D tile based representations make it easy to determine adjacency,
but essentially, you are just implementing graph search indirectly.
For 3D, you have to know which levels are adjacent, and the tile
based representation seems to have confused the issue. Treat
the 3D navigation problem as a graph search problem, and the
problem will be much clearer.

As for path finding, A* is O(n^2) (n is the number of nodes in
the path) for 2D space. You know, all that "flooding". In 3D,
I expect it to be O(n^3), but that's without having done the
math for the 3D case. If so, it will be very slow for even
moderately short paths.

Mike