   Pathfinding
  Hi!How can I apply a pathfinding algorithm on a 3d map?LE: Should to create a 2d map from 3d?[Edited by - Larry91 on June 3, 2010 11:07:18 AM]
  There's many techniques to do 3d path-finding.. but it depends on what kind of rule system your using(gravity, etc). The easiest is probably using a weighted graph built from path meshes (floors, ramps, climbable walls etc would all be in the path mesh). From there regular incremental path finding algorithms could be run over the graph (there's no algorithm that is perfect so it's kind of trial and error vs runtime performance), the third dimension doesn't really effect much in this case. Some systems also use vertex color values to show the A.I. things like safer areas and they also put a very low weight on edge nodes(or remove them all together) to prevent things like the A.I. getting stuck on a wall.More advanced systems will attempt to make shortcut paths in the mesh, so the A.I. has the ability to jump from a higher platform to a lower (computer vision algorithms can work in this case.. but it's difficult to do this reliably).Other options are to use Octrees( these usually work better for space type scenes where there will be objects in the way but there is nothing preventing the A.I. from moving in the 3rd dimension, like static gravity).   ;  A* simply solves through a graph.  It doesn't care whether or not the graph is 2D, 3D or even 75D.  So the challenge is generating that graph, not solving it.The typical solution in 3D games is to generate a navmesh during a data compile step and loading/solving that navmesh at runtime.  Generally you can do this through an iterative process:1) designers place "seed points" in the world.2) during the pre-compile you spawn capsules in the world at the seed points and push them around the level to determine whether a given place is pathable.  Essentially a flood fill of your map.3) from that data, generate a graph (naive implementation is just a node per pathable position, connections being based on your flood fill)Solving is then just straight forward A*.  No tricks-me   ;  Yah A* would work, so would Dijkstra's algorithm A2 or any of the other algorithms.   ;  As the other posters have mentioned, you can use a set of waypoints. For relatively small and few levels, manually placing waypoints may be sufficient. If you're dealing with a lot of content, you'll want to automate this (possibly still using manually placed nodes as hints or helpers).Alternately, you can look into navigation meshes. The Recast library might be a good place to start.   