# Getting Adjacent Nodes for PathFinding

This topic is 2869 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

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

##### Share on other sites
Quote:
 Original post by sjaakiejjAfter 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 on other sites
Hmm, though it would get a performance of, out of the top of my head, O(n^2). Actually that's not as horrible as I imagined it to be. I'll give it a shot, thanks for your help :)

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

1. 1
Rutin
33
2. 2
3. 3
4. 4
5. 5

• 11
• 10
• 13
• 96
• 11
• ### Forum Statistics

• Total Topics
632974
• Total Posts
3009647
• ### Who's Online (See full list)

There are no registered users currently online

×