3
\$\begingroup\$

Anyone aware of any sample source code that contain Navigational Meshes?

I'm aware of recast navigation (which is a little bit too complicated). - Written in C++.

Preferably C# but C++ is ok.

\$\endgroup\$
3
  • \$\begingroup\$ What in particular are you looking for? Would you like sample source code on how navigational meshes are used, or how they are generated (like recast, but your question simply asks for code that "contains" Navigational Meshes) \$\endgroup\$
    – Ray Dey
    Dec 25, 2010 at 23:41
  • \$\begingroup\$ I'm looking at how to generate the nodes and traverse it. Not generating the mesh itself, We'll do that manually. \$\endgroup\$ Dec 25, 2010 at 23:58
  • \$\begingroup\$ I'm assuming that the algorithm will just take a vertices and all the polygons they belong to then we send start and end points to it. \$\endgroup\$ Dec 25, 2010 at 23:59

1 Answer 1

2
\$\begingroup\$

I haven't really used Navigation Meshes extensively yet, but from your reply, since you're only looking at how to generate the nodes and traverse it, I would do it the following way.

Firstly, to generate the nodes in the navigation graph, I'd iterate through all the quads in the mesh and add them to a graph appropriately.

E.g.

foreach quad in mesh
{
   add quad to graph
   if quad has neighbouring quads
      add neighbouring quads to the neighbour list of the added quad 
}

That's a fairly simple brute-force method, but there's probably better methods out there.

To traverse the created graph simply make use of A* (A* Algorithm). This will give you a higher level path (a path from quad-to-quad).

Then to pathfind within each quad you can use a simple steering behaviours towards the next quad or even A* again to find the shortest-path (if you've got obstacles in the way).

Not sure if that's been explained very well, but it's a very high level look at it.

Hope it helps.

Ray

\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged .