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.

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]

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

Quote:

Original post by gorogoro 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.

If you already have an Oct tree coded, then morphing it into a k-d tree wouldnt be very hard. Here's how:

Presumably you have a tree node data structure with eight child (subtree) pointers. Change this to two pointers, but add in two other attributes: keyID and keyPartitionValue. At each level of the tree (each node) you're going to select one of the dimensions and assign this to the keyID attribute (so either x, y or z... 0,1 or 2). You'll then choose a value in that dimension and partition all of the data as either being left of, or right of that partition. If the data is left of, then it goes in the left subtree and if it's right of, it goes in the right subtree.

Now, to choose the keyID and keyPartition values.

keyID: a good metric to use is minimum variance. Compute the variance of the data in each dimension (so if each triangle has a centre coordinate given by (x,y,z) then compute the variance of each column of the matrix made up of all centres). Choose the dimension with the largest variance and set this as the keyID (the dimension on which to partition).

keyPartitionValue: as for this, a reasonable choice is the value of the median
(middle) datum in keyID dimension.

These choices will ensure that your data is evenly distributed in your tree, but that your leaf node bin sizes vary so as to give an approximately uniform density at the leaf depth.

If you have any trouble with this, give me a holler. I have some C++ classes for a k-d tree implementation that I'd be happy to share.

Cheers,

Timkin

Quote:

Original post by Timkin Quote: Original post by gorogoro 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. If you already have an Oct tree coded, then morphing it into a k-d tree wouldnt be very hard. Here's how: Presumably you have a tree node data structure with eight child (subtree) pointers. Change this to two pointers, but add in two other attributes: keyID and keyPartitionValue. At each level of the tree (each node) you're going to select one of the dimensions and assign this to the keyID attribute (so either x, y or z... 0,1 or 2). You'll then choose a value in that dimension and partition all of the data as either being left of, or right of that partition. If the data is left of, then it goes in the left subtree and if it's right of, it goes in the right subtree. Now, to choose the keyID and keyPartition values. keyID: a good metric to use is minimum variance. Compute the variance of the data in each dimension (so if each triangle has a centre coordinate given by (x,y,z) then compute the variance of each column of the matrix made up of all centres). Choose the dimension with the largest variance and set this as the keyID (the dimension on which to partition). keyPartitionValue: as for this, a reasonable choice is the value of the median (middle) datum in keyID dimension. These choices will ensure that your data is evenly distributed in your tree, but that your leaf node bin sizes vary so as to give an approximately uniform density at the leaf depth. If you have any trouble with this, give me a holler. I have some C++ classes for a k-d tree implementation that I'd be happy to share. Cheers, Timkin

Thanks a lot for the help guys!!!
I make it with an octree already.
Since it is done it was very easy. I have a struct called triangle wich have the indexes of the vertices of a given triangle and an index (the Navigation Graph indexes) struct Triangle{int A; int B; int C; int index:}
The Octree guards this triangle information (I think I've made it with 6 triangle per leaf or something like that). given a certain position the Octree gives me the leaves where it could be. Then I make an intersction using the bounding sphere of the agent to the leaves returned, and keep de smallest distance between the agent position and the leaves intersected by the bounding sphere. The smallest distance is the nearest cell, since I have the index of the cell in the triangle struct it's easy :)

Well when the things are done and working it seems easy. But in the beggining I wasn't really shure how I would do the thing.

We have to build a mini playable demo until july, so the kd tree is going to wait. Until then more problems are going to come :)