Hi. I'm about to write my first pathfinding code, I did research on the net and I found lot of infos EXECPT two things: 1) adding nodes with correct neighbourhood to a navmesh 2) pathsmoothing with LOS in a non-tile-based environment. I have my ideas on these two topics, I'm gonna share'em with you and I hope someone with more experience can help me understand better ways to solve these problems. Ok, first thing: I'm gonna use a navmesh made of triangles with a node in the center of every triangle (so each node has max 3 neighbours) and I also keep a list of the edges that are linked to just one triangle (this edges are clearly the ones defining the uncrossable borders of the navmesh. More on this later). The engine is a 3d one but my navmesh is just like a 2d-flattened walkable geometry, so I'll think of it as just a 2d mesh. I'm gonna use A* for pathfinding. Here comes the first problem: adding start_point and end_point to my node-graph with correct neighbours. My idea is to use nearest-neighbour algo on a kd-tree to find the nearest node, and add this nearest node and its neighbours as neighbours for the node I'm gonna add to the graph. Does this sounds reasonable to you? It's just the easiest way I can think of... After this step, I run my A* and I receive the path as a list of nodes. Great, but now I have to smooth it out a bit. Simplest way is to check if we can walk from node i to node i+2, so we can skip node i+1. The problem is that I didn't find any document about this kind of LOS check in non-tiled enviroment, so I made my own geometrical solution: I can say that the path between i and i+2 is walkable if the segments joining these two nodes DOES NOT intersects any of the border-egdes (the ones I mentioned before), basically I just need a fast way to check lots of segment-to-segment intersections. First thing, I rule out all the edges that are out of the "bounding rectangle" enclosing the a*-generated path. To check intersection with the remaining edges, the fastest solution I can think is this one: suppose we have to segments called A and B and the start and end points of these segments are called a1,a2,b1 and b2. Now if a1 and a2 are on the same side of the B segment OR b1 and b2 are on the same side of segment A, there is no intersection. Computing the position of a point relative to a line is quite cheap so I think my solution could work quite good. I hope someone can eventually correct my mistakes or suggest better ways :) Thanks for your time... PS: the game engine is aimed at adventure games, so I don't need extra-fast mass pathfinding, just the player character and some NPCs moving around. And for this starting test I'm not even taking into account the size of my moving characters.

Just a few quick comments:

1. You might at least consider placing the nodes at the edge midpoints rather than the triangle centroids. It may not matter in your case (depending on what pathfinding features you're planning on implementing), but keep in mind that it's possible to encounter triangle pair configurations where a straight line between the two respective nodes is not a valid path (if the nodes are located at the edge midpoints, all paths between two adjacent nodes will be valid).

2. You don't necessarily need to use a general raytracing function for your line-of-sight tests. By taking advantage of the connectivity information inherent in the navmesh, you can write a more efficient LOS test that walks from cell to cell until a constrained edge is encountered (this is covered in one of the first two GPG books, I believe).

3. LOS-based path smoothing can definitely improve the quality of computed paths, but won't return perfect results. One alternative is the funnel algorithm, which will return an exact geodesic path given a 'channel' of navmesh cells, a start point, and an end point.

Note that some of these details will depend on how you're handling agent size in your pathfinding code (e.g. geometry expansion, support for varying agent sizes, etc.).