3d Point & Click Pathfinding

[thSoft]

Hi all!
I'm not totally sure whether to put this thread in this topic, but I'll give it a try. So.
I'm fully aware of the A* pathfinding algorithm. The problem is how can I apply it to a 3d point & click game...
The simpler question is what kind of graph representation to use for the 3d space. There are afaik 2 alternatives:
- Navigation Mesh: I would assign a value to every triangle of my world mesh, whether the player can step on it or not. The graph's nodes are the triangles, the graph's edges are their connectivity through their edges. There can be some complication with stairs (their "vertical" parts can be surpassed, but not stepped on), but I can represent this as a special value. This alternative is very redundant and can lead to enormous search space.
- Points of Visibility: The graph's nodes are predefined points in the game space, and the graph's edges are also determined by the level designer. The weight oo the edges are of course the Euclidean distance of its nodes. This results in a pretty small search space, though the waypoints must be placed very carefully.

Ok so far. Here comes the REAL problem:
How do I translate the user's click to a destination in the search graph?
I'll explain this. In a point & click game, the user clicks on the screen. Through my 3d engine api, I can determine which triangle did he/she click on. But which nodes should I give to the pathfinding algorithm as source and destination? Let's consider the two space representations mentioned above.
- Navigation Mesh: What if the user clicked on a triangle that the player can't step on, for example a wall piece? How could I know which is the real, traversable destination triangle, eg. the floor piece next to the wall??? I could assign a pointer to these non-traversable triangles, which would point to the respective traversable triangle, but this is a complete waste of the level designer's resources.
- Points of Visibility: The problem is even much more complex. I can't even determine which waypoint to start the search with (since the player can stand anywhere), not to mention the destination point. The player's position and the click will fall outside the search graph's nodes almost surely.

I hope I expressed myself clearly enough. Any ideas? Please help!

[Reedbeta]

Can't you just find the nearest traversable node to the one clicked on, or nearest to where the player is standing? BTW, if you go the route of using designer-placed waypoints, then you don't need to determine edges among them yourself, you can simply check pairwise accessibility when the level is loaded (i.e. by doing a geometry trace to make sure the player can actually get from one node to the other).

[monjardin]

Amit Patel has a wealth of great information about A* and pathfinding. You can find his comments on map representations here: http://theory.stanford.edu/~amitp/GameProgramming/MapRepresentations.html

[Scramasax]

Ok here is what I've done in the past:

1) I'd use a series of nodes to create a lattice, instead of a mesh. The reason for this, is that you can massage the data, as well as having a small data set, hence faster.

2) When you click you're AI, it needs an entrance an an exit node. You can run various distance checks to get the node. (Manhattan,Non Square Dist, or Squared Dist) Also you'll need to do a physical probe against the collision geometry and reject closest distance, if say, a node is behind a wall or some other obstacle. Doing this in a game can become expensive on the CPU side of things.

The best solution for this is to store the closets waypoint data in a bucket system. Either linear buckets, quad or octtree. The smaller the buckets, the better the closest data solutions will be. I'd generate this data off-line in a pre-compile step. That way you can use as complex heuristics as necessary.
----------
http://www.moxiefish.com/bluemarssmall.gif

[oxymoron]

Our world representation is a quadtree. When a user clicks in a room, the point is ray-projected in the standard 3D way to find which floor is intersected by the ray and the actual point of intersection (our UI ensures it is physically impossible to click points that are not in a room). Then we transform the point into room space, and figure out the leaf node in the quadtree the point is in. If it's valid, then the routing begins. We have a hierarchical A* that finds a path from room to room and then with in a room across quadtree cells. The path built is a 3D Bezier based on the quadtree centres, but we perform a relaxation pass on that curve to smooth it out and make it look more natural. The final section of the path is from the nearest leaf node centre to the point clicked.