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.

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.

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

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.

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