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 energy. - 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. Any ideas? Please help!

Quote: Original post by thSoft
Navigation Mesh: The graph's nodes are the triangles ...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.

There are two ways I can think of for dealing with this:
(1) Use the projection of each triangle into the floor plane to determine whether it can be a pathfinding node or not. If the triangle projects to an area smaller than the agent (or to zero area) then ignore that triangle when building the nav-mesh and test the connectivity of its neighbours (i.e., can the triangle be stepped over, which is typically a function of the gradient of the normal of the triangle and the projection of the triangle into the wall plane... i.e, is it too high).

(2) The second way is to use the gradient of the triangles normal directly. If the gradient is zero, then the triangle is a vertical one and not a suitable destination node.

In either of the cases up, if a targeted triangle fails the 'suitable destination' check, then test it neighbours for the nearest triangle that is suitable and highlight that one. If there is no suitable triangle within a given radius, then return a failure on finding a suitable target (and indicate this to the player so they know to move the mouse).

Make sense?

Cheers,

Timkin

Hi,

For the nav mesh solution, would it be possible for you to use another set of meshes, instead of the ones that are rendered? For examples, the collision meshes will be way simpler, and in the case of the stairs, will be a very simple slope...

Anyway, for both situations, if you succeed to have only a few nodes, what you could do is transform their position in camera space, and then find the best suitable node and pathfind to it. The "best suitable node" is the tricky part... but you can trick it with simple assumptions... the ground should always remain down, so the node you'll pick is most likely going to be lower in the screen than the mouse click.

At least, we succeeded with a similar system in Syberia 1 and 2, hope you'll be able to get something working :)

Cheers

Eric

I think you might be a bit confused on points of visibility. This has to be a quick post, so I will clarify more later.

In PoV, you have your bounding polygon edges, and you have your visibility points which are offset to the convex points on the polygon. Your points of visibility are placed such that wherever your destination point may be, there is a point of visibility that you can connect to your destination point with a straight line.

Consider the following 2d example, where the start and destination points are marked in cyan, we have a polygon obstacle in white, and that polygon requires visibility points shown in magenta. The path that will probably be generated from A* is also shown in cyan.





So your start point is your current location, and your end point is where the user clicked on your terrain. You use the A* search, and your search nodes are all of the points of visibility and your start and end node.

If you can move in a straight line from your current location to the destination without intersecting/colliding with a bounding polygon edge, then you move in a straight line to your destination.

If you cannot navigate to your target in a straight shot, then there must be some obstacle blocking your path. Test all of the polygon's visibility points, and whichever points you can reach by moving in a straight line from your current location, you consider as a successor node.

So a point of visibility's successor nodes are the nodes of which are completely visible from that node (e.g., you can draw a straight line from this PoV to that PoV without intersecting some other polygon's edge).

This is the great thing about PoV, your A* search deals with fewer nodes than a tile or grid based search, and the path traveled is usually very efficient.

Hope this helps.

thSoft: Why would you use every triangle as a navmesh? Every implementation I've heard of considers every triangle, and then generates a greatly simplified graph that accounts for every factor(game physics, unit scale, etc) available during the preprocessing.

The methods commonly used is to embed your path finding information, i.e., triangles nodes, into some other fast searching structures. Let's take an example.

For each clickable triangle, you put it into the BSP or octree or quadtree or portal. Then, when your clicks on screen, you project a ray from screen to the world. Then, you search for which node is hit and any triangle is hit.

You have your node for the start of the search then.

pcwlai, this solution only takes account of clicks ON the nav mesh. If the user clicks on a building, he'd probably want his unit to go as close as possible to the click position, even if its unreachable.