Hi! I'm using a navigation mesh for my A* path Finding! Everything is set up and working.. My problem now is how do I do the mapping between my agents in the pathFinding structure and the game world?? I mean, I have the nodes conected to another nodes, building a graph system with pointers. Every node has an unique ID, it's position, and the triangle from the mesh, and other stuff.. My pathFinding algorithm accepts two id's the id where the agent is, and the id to where it wants to go. My question is in the game world, the entity only have a position, How can I now wich node of the graph it belongs??? Ideas please.......

Ideally, you should spawn your agents at a given node, and keep track of its closest node as the game run.

If, for some reason, you can't do that, then you need a way to find the closest node to an agent position. This can be done is several ways, depending on your game. Brute force is a possibility. A distance map will probably take too much memory. A KD-tree might work well.

Quote: Original post by Steadtler
Ideally, you should spawn your agents at a given node, and keep track of its closest node as the game run.

If, for some reason, you can't do that, then you need a way to find the closest node to an agent position. This can be done is several ways, depending on your game. Brute force is a possibility. A distance map will probably take too much memory. A KD-tree might work well.

I'm thinking of using an octree.. Now I don't how can I contruct such a tree :s..I have to map the nodes ids to it's positions and costruct the Octree accordingly. Argh..

Is this the correct procedure? How do ppl usually do this kind of stuff?
I can't find any usefull information on the books and papers.

As Staedtler pointed out, a tree based nearest neighbour search would be appropriate. At compile time you can construct a tree decomposition of your game world surface ('map'). Then, when you want to find the nearest mesh element to the agent (presumably the one it is standing on ;) ) you perform a nearest neighbour search using your tree. A k-d tree is an efficient data structure for performing this search. You could do it on an oct tree and this should give you roughly equivalent efficiency results in the limit that your map is perfectly flat.

Does that make sense?

Cheers,

Timkin

Quote: You could do it on an oct tree and this should give you roughly equivalent efficiency results in the limit that your map is perfectly flat.

I think you may be getting confused with a quad-tree. Even then, the map doesn't have to be flat, you just can't have a room on top of another room for instance.

An Octree would be my choice as well. Mostly because I use them often and know how to code them. :)

Quote: Original post by fig

Quote: You could do it on an oct tree and this should give you roughly equivalent efficiency results in the limit that your map is perfectly flat.

I think you may be getting confused with a quad-tree. Even then, the map doesn't have to be flat, you just can't have a room on top of another room for instance.

An Octree would be my choice as well. Mostly because I use them often and know how to code them. :)

Yeas Yeasterday I remembered that problem: "what if, I have a room on the top of the other room?? Ahh.. Fuck..". Guess quad-tree is better just for terrain.

But the same problem persist. How should I split the space? Since I just have some nodes connected performing a search graph.

Quote: Original post by fig
I think you may be getting confused with a quad-tree.

Hehe... not confused... just one of those days where you're thinking one thing and writing another. Call it a brain fart! Thanks for picking up the error. 8)

Quote: Original post by gorogoro
But the same problem persist. How should I split the space? Since I just have some nodes connected performing a search graph.

Okay, lets take a step back for a moment and consider the problem from an external perspective. You have a (presumably 2-d) surface (lets call it the map) embedded in a 3-d space and you want to overlay this surface with a navigation mesh for pathfinding. Having done this, you want any object/agent/etc situated at a known location on the map to be able to use the mesh to find a path to any other location.

Issues concerning mesh creation. If the surface is not 2-d but instead is a representation of say a building with multiple floors connected by stairs and elevators, then you have two ways of handling this. The first is perhaps the simplest, portals, while the second is more elegant (but not worth doing for many problems), 3-d map with transition constraints.

Portals are just as they sound. Points on a map where you can transition to another point on the map. You essentially split your 3-d surface into a set of minimally connected 2-d maps with portals acting as connections between them. So, you have two rooms connected by stairs? The stairs become a portal connecting 2 meshes, one for each room. Portals may be 1-way or 2-way.

Map constraints act similar to portals, but are not as binary. You can still represent your surface as a 3-d map, but you must constrain the connectivity nav-mesh nodes while pathfinding based on map surface constraints (like surface gradient, existance of barriers, etc). In most instances, such a constraint can be precomputed and handled using the portals method.

Issues concerning using the mesh
Once you have a mesh, then you decompose the mesh nodes based on a tree decomposition. For a given location on the map, use that location as a query to a nearest neighbour search using the tree. If you're using portals, then you'll need to treat portals as mesh nodes. If you're using map constraints, then you need to perform a constrained nearest neighbour search (the neighbour must satisfy local constraints for the agent to be able to move to it). You do the same thing for the goal location; find it's nearest neighbour in the tree.

You now have two nodes on your nav mesh as the focus of your pathfinding query.

As for finding nearest neighbours on a k-d tree... there's plenty of literature and code snippets available. Try [google] using 'k d tree nearest neighbour algorithm'.

Good luck,

Timkin

[Edited by - Timkin on May 23, 2006 8:50:13 PM]

A navmesh is often a seperate structure -- it can be a simplification of the rendered mesh (fewer triangles will speed up your A* significantly).

You can also add data like a list of adjacent triangles for each triangle -- to speed up position determination (you use a point-intersect-triangle calculation and a lazy optimization is to check the navmesh triangle the unit was previously on first, and then check against the short list of adjacent triangles before doing a wider search using quadtree, etc...

Just do a raycast from the center of your entity straight down for X meters to see what triangle it hits. Whatever triangle is nearest in the navigation mesh, is the triangle that your entity is on. If you hit no triangle, the entity is likely in freefall, or your nav mesh is not complete.

If you're using DirectX, there's a simple function to do raycast into a triangle mesh. It's kind-of slow for large meshes, though -- faster would be to put your triangles into a hash grid or a quadtree, to accelerate this ray query (easy when you know the query will always be done downwards).

Thanks for the Help Guys! :)

Guess I'm going to use an Octree for now, since I think I don't have the time to do a k-d Tree. I think the K-d Tree is the best choice for now, but I have already an Octree coded, so I'm going to adapt it to my needs.

My NavMesh s not rendered. It is a simplificatoin of the floor, and each triangle is a nav node (instead of each vertice :)).