I write engine 3d The view ist similar to nwn(never winter night).How i can find shortest a path?In 2d is quite easy but in 3d I dont have tile!

All search algorithms can be implemented in N dimensions... however, their computational cost is exponentially proportional to N.

The algorithm you choose to implement will have a lot to do with whether you are precomputing possible paths offline, computing a single path online, computing multiple paths simultaneously online, whether the goal is moving, whether there are dynamic obstacles in the region, etc.

In terms of representation for 3D spaces, that also depends on whether you want to search in the state space (in which case consider an oct-tree decomposition of the volume that partitions regions of similar pathing cost) or search in the action space (in which case you can simply discretise movement actions in those 3 dimensions).

It's not enough to ask 'how do I find a shortest path'! You need to describe the problem in more detail. I highly recommend you search google for information on pathfinding. For a good starting point, check out Amit's pathfinding webpage.

http://www-cs-students.stanford.edu/~amitp/gameprog.html#paths

Cheers,

Timkin



[edited by - Timkin on February 25, 2004 9:16:14 PM]

I use octtree and I want use A*(astar).I know A* but I can''t write this algorithm in 3d

It has been a while since I played NWN, but from what I recall, there wasn''t a lot of up and down variation. Maybe you can reduce it to a series of 2D navigation maps. There are several games that use this approach to simplify the pathfinding and collision detection. I don''t know what method NWN uses, though.

Even if there are elevated areas in a room or area, as long as there is no possible path *under* the elevated area, a 2D nav map can still be used.

Peace

A* is the same in any number of dimensions. The algorithm was developed for general graphs, to find a path along the edges of the graph from one node to another. In games, the nodes are just positions, and two nodes have an edge between them if it is easy to find a path between the corresponding positions.

quote:

---

Original post by Jezak
I use octtree and I want use A*(astar).I know A* but I can''t write this algorithm in 3d

---

As the AP said, there''s absolutely NOTHING in the A* algorithm that dictates how many dimensions it is applicable in. The only implementation aspect that considers the number of dimensions is how you generate successor (child) nodes in your search tree.

Timkin