Hello people,

I have been trying to get a solid navmesh based A* thing going on. i have read allot of posts and pages about it, but i'm struggling with something.
for my A* function (think i got that working) i require to have a list of nodes. a node is made of a couple of properties for the most important is a reference to its neighbor nodes.

in pseudo code i create my list as follow:

for number of triangles in mesh do
vert1 = mesh.triangles
vert2 = mesh.triangles<br> vert3 = mesh.triangles<br> <br> construct 3 node objects from vertex postions<br> <br> check if node 1,2,3 is already added to list<br> if yes then switch with the &#111;ne already added.<br><br> for node1 add node2 and node3 as neighbor<br> for node2 add node1 and node3 as neighbor<br> for node3 add node1 and node2 as neighbor<br> <br> if node is not in list add to list of nodes<br>end<br><br>this works, i get a correct list of nodes and the neighbors are also good.<br><br>but i would like to use edge centers for my nodes, cause i think my path looks better<br>i use the same code as above but i create a node for :<br>node 1 = (vert1 + vert2) /2<br>node 2 = (vert2 + vert3) /2<br>node 3 = (vert3 + vert1) /2 <br><br>But i'm having some problems creating the neighbor nodes, the result is like this : http://www.pixelstudio.nl/navmesh.jpg<br>purple shows a node and the orange are its neighbors.<br>so somehow i have to adjust the neighbor creation, but i'm having problems with this… any1 got an idea?<br><br>Then a other question. i use an A* to find a path. but this would result in a weird situation if i would use large polygons, cause not all space in a polygon is used.. is it common to use polygon sized that are smaller that the objects that are walking &#111;n it? are the solutions for this ?<br><br>hope some1 understands a little of what i'm trying to say :) <br><br>thanks in advance for any help given!

Regarding the node neighbor problem, it just looks like you have a bug in your implementation. To find the neighbors for a node:

1. Find the two triangles that share that edge.

2. Add the nodes associated with those triangles' other edges as neighbor nodes.

Regarding polygon sizes, yes, naively plotting a path through polygon edges can result in jagged or irregular paths, or paths that are considerably longer than necessary.

A common solution is to post-process the path using the 'string pulling' or 'funnel' algorithm to produce a smoother and/or shorter path. However, this still won't necessarily be an exact geodesic path (although the results may be fine for practical applications).

There are some methods for generating an exact geodesic path that involve continuing the A# search even after a path has been found, but they're a little less straightforward to implement.