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).

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!