Sign in to follow this  
sjaakiejj

Getting Adjacent Nodes for PathFinding

Recommended Posts

Hi,

I'm currently working on an AI Demo to gain some further insight on how bots can make decisions and how they find their targets. I've implemented a State Machine, Scripting, Messaging System, Character and AI Classes, Managers, some Steering Behaviours and a NavMesh generator.

After parsing the data into a NavMesh, I get a set of 1500 Positions (My Nodes) and 1500 Triangles (The center of which is the node) from a large map. Now the only problem is that I can't figure out how to determine if node B is adjacent, e.g. a neighbour of node A. I suppose I could check if the vertices that make up one edge on each triangle, match the vertices on a triangle next to it, but this would be a long process, and probably rather undesirable. So my question is, if you have a set of Triangles or a set of Nodes (or both for that matter), how do you figure out if they are adjacent to each other or not?

One way I thought of was taking the Manhattan distance between the two, but that wouldn't work if there is a wall between two nodes, as it would still believe that the other node is its neighbour. Likewise, I could use the nodes and triangles together, and compare the triangles these nodes belong to, which would make the problem less complicated but I'm not sure if there is a better way.

Thanks in advance.

Share this post


Link to post
Share on other sites
Quote:
Original post by sjaakiejj
After parsing the data into a NavMesh, I get a set of 1500 Positions (My Nodes) and 1500 Triangles (The center of which is the node) from a large map. Now the only problem is that I can't figure out how to determine if node B is adjacent, e.g. a neighbour of node A. I suppose I could check if the vertices that make up one edge on each triangle, match the vertices on a triangle next to it, but this would be a long process, and probably rather undesirable.
How so? You have three vertex indices on one triangle, and three on the other. See if a vertex index of the first triangle matches a vertex index on the second one, and if so, see if there's an adjacent edge. (You can also process all the adjacencies at once by iterating through all triangles, building and consuming a set of unmatched edges and their corresponding triangles.) Of course, you only do this once at load-time, saving the three adjacencies for each triangle.

Share this post


Link to post
Share on other sites
Using the unmatched edge set with an appropriate data structure, such as a hashtable, will cut it down to O(n). Get it working first, though.

Share this post


Link to post
Share on other sites
@The OP: As has been pointed out, the solution is to compute connectivity information for the triangle set. (I think your concerns regarding performance are probably unfounded; if you use appropriate data structures, it should be plenty fast. Also, since it's a preprocessing step, performance shouldn't be that much of a concern.)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this