3d Point & Click Pathfinding
Posted 21 January 2006 - 05:01 PM
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!
Posted 21 January 2006 - 08:28 PM
Posted 21 January 2006 - 09:06 PM
Posted 12 February 2006 - 09:38 PM
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.
Posted 21 July 2006 - 08:48 AM
1 user(s) are reading this topic
0 members, 1 guests, 0 anonymous users