Search Space Representation

[_Nemesis_]

Hi guys,

Brief Background:
I'm currently working on a project in which I wish to create an autonomous game agent capable of traversing 3D environments. To do this I would like to implement a custom path finding algorithm that works with a navigation mesh.

The Problem:
I'm currently looking at various ways of creating a navigation mesh and I've found several great articles about the theory but unfortunately I haven't found any articles that discuss the techniques and methods used to actually create a nav mesh.
Preferably I would like to auto-generate the mesh based on the geometry of some terrain that I create using a heightmap but if this involves a large time-consuming amount of work then perhaps someone could suggest a quicker solution (I am working to a tight schedule and can't afford to spend too much time on this).

I would appreciate any help, code snippets etc. in particular, that could at least get me started with the creation of a navigation mesh.

All advice/feedback/support is welcome :)

[mike_2000_17]

Well, I guess I should answer this, considering that path-planning is the subject of my Ph.D. thesis (the scenario is quite a bit more complex, of course).

Storage:

What you refer to as a "navigation mesh" is essentially a graph (a network of nodes and edges that link them together). Associated with each node, you would normally have information like its position in the environment (2D, 3D, or more, in my research its 15 dimensions) and other information that is usually useful to determine the desirability of that position (like proximity to obstacles, proximity to some goal position, exposure to enemies to dangers, etc.). Associated with each edge, you would normally hold information like the traveled distance/time or other cost-of-travel values.

Now, once you understand that your navigation mesh is in fact a graph. You have to look into graph theory, which is a huge deal in computer science due to its many applications, namely, the internet! (which is also a graph or network). There are many kinds of graphs with different properties and different storage methods.

Generally, a path-planning problems over a fixed graph (or mesh) will involve a grid-like graph, which, in formal terms, is a planar and undirected graph.

In concrete terms, this also means that when looking for an actual implementation or method of storing your navigation mesh, you need to be looking for a "graph library". The most prominent and one of the best graph library is the Boost Graph Library which provides classes to create graphs of many kinds (including a grid_graph). In addition, most graph libraries, like BGL, will provide a number of algorithms that can be used to find the shortest-path through the graph from a starting point to an end point (predominant algorithms for this is A* and Dijkstra).

Construction:

You have many options here, ranging from a fixed mesh that spans the entire world, to a dynamic mesh that only sparsely spans the world (usually very local).

If you decide to create one big mesh that spans the whole world, then you should normally save it along with your map of the world, there's no point in re-generating it upon the loading of the map. But if you have to re-generate it, it's not that much work. To generate the mesh, you have to just create a grid over the entire world (like, say, 512 nodes by 512 nodes over the map, or pick the same resolution as your heightmap). Then, you traverse all the nodes and edges to set their properties to their appropriate values (by referring to the environment to see if the given node is in collision with an obstacle and so on). And that's pretty much it.

Draw-backs of using a fixed mesh over the entire world are two-fold: you have a very large search space, and you can't deal with dynamic environments very well. The former means that you might spend a lot of time computing your best paths (there are "anytime" alternatives that can cope with that). The latter means that you might have trouble with bookkeeping (adjusting the values in the mesh in reaction to changes in the environment) and with readjusting your planned paths. For simple AI agents in computer games, a fixed grid is usually enough and it works well, for the simple reason that the environments are usually fairly small, predictable and structured, and solution paths are usually not required to be very sophisticated. In robotics, it's a whole different ballgame.

Also, fixed graph approaches are usually combined with hierarchical meshes. This is simply done by having multiple meshes of increasing finesse. You plan a coarse path across a coarse mesh, and then you pick the waypoints from that solution and use them as start/end pairs on the finer mesh, until you've reached the finest resolution. And usually, you only do the finer-resolution planning in the immediate surrounding of the character, and you move along like that.

Then, there is the world of dynamic graphs, or probabilistic graphs. These are more common in robotics path-planning where fixed-graph approaches are just "intractable" (meaning, there is no way to compute a plan in time for the plan to still be useful). With dynamic graphs, the idea is to generate the mesh randomly as you go along, and generating it in such a way that you generate nodes that are likely to be useful in your current planned path (either to refine it, or to go forward, or escape a trap or obstacle, etc.). A basic, unbiased and static method of that kind is the Rapidly-exploring Random Tree (RRT). Many other methods exist, but they are unlikely to help you in a AI agent problem.

So, overall, I would suggest you construct the fixed mesh by going through it, pruning it, and setting up the values (position, obstacle, desirability, travel distance, etc.) from inspecting the environment (heightmap and obstacles). You can easily do this with BGL's grid_graph class or its adjacency_list class too. For a hierarchical mesh, well, you don't actually store it as a hierarchical graph, you just traverse it differently depending on the level of detail of the path-planning.

Algorithms:

This answer is pretty simple: use the A* algorithm. This algorithm is, like many others, implemented in the Boost Graph Library. If you need to deal with dynamic changes in the environment, a variant of A* exists to deal with that, it's called AD* (Anytime Dynamic A*), and I have a BGL-compatible implementation of it available here (refer to this example code for seeing an example of constructing a fixed graph that spans a world represented by an image (white for free, grey-scales for obstacles), setting up the node/edge values, and then running AD* on that to solve the path-planning problem over time, this is just a unit-test program so its not really a super well done).

I hope this basic overview helps you.

[_Nemesis_]

Firstly I would like to say a big thank you because the information you have given has been a huge help!:)

I have a few questions though:

If I store a node per cell at the same (or similar) resolution as my heightmap then isn't this just a grid representation using waypoints?
I was hoping to achieve something more like the large triangular polygons that I have seen for the majority of navigation mesh examples.

Secondly, even if I use a hierarchical approach (which I was actually considering before posting here) then won't I still have large memory useage if I were to use a grid of nodes/waypoints?
I imagine this is the reason the larger triangular polygons are often used in navigation meshes?

Finally, I neglected to mention (sorry) that I will be able to drop objects in to the environment at run-time. Do you think that a fixed mesh would still be a suitable solution?

Thanks again!

[Yasinepd]

thanks mike :)

[mike_2000_17]

>> If I store a node per cell at the same (or similar) resolution as my heightmap then isn't this just a grid representation using waypoints?

Yes. Why would that be so terrible? You probably would use a down-sampled resolution visa vi your heightmap (like half the resolution, so some resolution that makes the distance between waypoints reasonable compared to the size of your characters).

>> I was hoping to achieve something more like the large triangular polygons that I have seen for the majority of navigation mesh examples.

That's very reasonable. This won't be any harder or easier to construct versus a "square" grid. And, it will probably yield somewhat nicer results (less squarish paths). Here is a quick piece of code that would do exactly that:

#include <boost/graph/adjacency_list.hpp>

#include <cmath>

//Create a struct for node-properties:
struct WaypointProperties {
  double x, y, z;  //store the position.
  double value;    //store the desirability value.
};

//Create a struct for edge-properties:
struct PathSegmentProperties {
  double travel_distance; //store the distance traveled along the edge.
};

// Define the type of the graph:
typedef boost::adjacency_list< boost::vecS,  //Edge-list storage type.
                               boost::vecS,  //Vertex-list storage type.
                               boost::undirectedS,    //Connection type
                               WaypointProperties,    //Waypoint properties
                               PathSegmentProperties, //Path-segments properties
                               boost::vecS            //In-edge-list storage type.
                             > NavigationMeshType;

const double half_tan_30 = 0.5 * std::tan(M_PI / 6.0);

double get_distance(const WaypointProperties& p1, const WaypointProperties& p2) {
  return std::sqrt( (p1.x - p2.x) * (p1.x - p2.x)
                  + (p1.y - p2.y) * (p1.y - p2.y) 
                  + (p1.z - p2.z) * (p1.z - p2.z) );
};

template <typename DesirabilityComputer>
void GenerateNavigationMesh(NavigationMeshType& waypoints,
                            double x_min, double x_max,
                            double y_min, double y_max,
                            double edge_length,
                            const HeightMapType& map,
                            DesirabilityComputer get_desirability) {
  typedef boost::graph_traits< NavigationMeshType >::vertex_descriptor Vertex;
  typedef boost::graph_traits< NavigationMeshType >::out_edge_descriptor Edge;
  
  //create fresh mesh:
  waypoints = NavigationMeshType();

  std::size_t w_count(std::floor((x_max - x_min) / edge_length));
  double h_step = edge_length * half_tan_30;
  std::size_t h_count(std::floor((y_max - y_min) / h_step));
  
  double y = y_min;
  for(std::size_t j = 0; j < h_count; ++j, y += h_step) {

    // First, generate an even row:
    double x = x_min;
    for(std::size_t i = 0; i < w_count; ++i, x += edge_length) {
      Vertex v = add_vertex(waypoints);
      double z = map(x,y); //get height from heightmap.
      waypoints[v].x = x;        //set position x.
      waypoints[v].y = y;        //set position y.
      waypoints[v].z = z;        //set position z.

      // Then, compute the desirability using the given function object:
      waypoints[v].value = get_desirability(x, y, z);

      // Start creating edges:
      Edge e; Vertex u;
      if( j > 0 ) {  //if you are at least at the second row:
        if( i > 0 ) {  //if at least at the second column
          u = vertex( (j-1) * w_count + i - 1, waypoints);
          e = add_edge(u, v, waypoints);
          waypoints[e].travel_distance = get_distance(waypoints[u], waypoints[v]);
        };
        u = vertex( (j-1) * w_count + i, waypoints);
        e = add_edge(u, v, waypoints);
        waypoints[e].travel_distance = get_distance(waypoints[u], waypoints[v]);
      };
      if( i > 0 ) {  //if at least at the second column
        u = vertex( j * w_count + i - 1, waypoints);
        e = add_edge(u, v, waypoints);
        waypoints[e].travel_distance = get_distance(waypoints[u], waypoints[v]);
      };
    };

    //Then, generate an odd row:
    ++j;
    if(j == h_count)
      break;
    y += h_step;

    x = x_min + 0.5 * edge_length;
    for(std::size_t i = 0; i < w_count; ++i, x += edge_length) {
      Vertex v = add_vertex(waypoints);
      double z = map(x,y); //get height from heightmap.
      waypoints[v].x = x;        //set position x.
      waypoints[v].y = y;        //set position y.
      waypoints[v].z = z;        //set position z.

      // Then, compute the desirability using the given function object:
      waypoints[v].value = get_desirability(x, y, z);

      // Start creating edges:
      Edge e; Vertex u;
      
      u = vertex( (j-1) * w_count + i, waypoints);
      e = add_edge(u, v, waypoints);
      waypoints[e].travel_distance = get_distance(waypoints[u], waypoints[v]);
      
      if( i + 1 < w_count ) { //if we are not at the last column:
        u = vertex( (j-1) * w_count + i + 1, waypoints);
        e = add_edge(u, v, waypoints);
        waypoints[e].travel_distance = get_distance(waypoints[u], waypoints[v]);
      };

      if( i > 0 ) {  //if at least at the second column
        u = vertex( j * w_count + i - 1, waypoints);
        e = add_edge(u, v, waypoints);
        waypoints[e].travel_distance = get_distance(waypoints[u], waypoints[v]);
      };
    };
  };
  
  // Then, we can also prune the nodes that have negative desirability (say that it means definite collision, with a static obstacle):
  for(std::size_t j = 0; j < num_vertices(waypoints); ++j) {
    Vertex v = vertex(j, waypoints);
    if( waypoints[v].value < 0.0 ) {
      // delete the vertex:
      clear_vertex(v, waypoints);
      remove_vertex(v, waypoints);
      --j; // <-- this is important.
    };
  };
};

I understand that the above operation takes time and memory. But, since you only have to do this once (either at load-time or saved along with the map of the environment). Also, the pruning that I included at the end might not be useful in practice because you lose the nice memory structure of the graph (h_count x w_count nodes) which is probably worse at the end (i.e. it might be better to keep the regular structure even if it means wasting memory and time with invalid waypoints).

>> Secondly, even if I use a hierarchical approach (which I was actually considering before posting here) then won't I still have large memory useage if I were to use a grid of nodes/waypoints?

The hierarchical approach doesn't save you memory usage (in fact, increases it). That's not the point. The important thing is the performance in the planning of the path and the ability to control, to some extent, the locality of the search.

If you consider a basic shortest-path algorithm like A* or Dijkstra, then these algorithms will, in one path-planning request, traverse all the nodes of the graph. This could be extremely wasteful. With a hierarchical graph, you can first plan on the high-level graph which has a very small amount of widely spaced waypoints. You will get a rough plan very quickly. Then, you can go down to the next level of detail in the graph and plan a path between the high-level waypoints, through sub-graphs that roughly include those waypoints. This is also quickly found. And you recurse like this down to the highest level of detail in the graph. Also, you can decide to recurse to maximum details in the close vicinity of the character, but not as much elsewhere. Basically, you can anticipate the motion of the character (since you control its path) and thus, you can preemptively detail the paths planned ahead.

At the end, you'll get a path that is (almost) as good as if you ran the A* on the entire high-detail graph to start with. But, it is most likely that you will only need to examine a fraction of the nodes (i.e. a trail of nodes surrounding the path). Of course, you pay a price in memory consumption, but that is generally a small price for the improved performance, also considering that you will probably do a lot of path-planning queries on the same navigation mesh. You also pay a price in terms of optimality (at least, theoretically speaking), because a hierarchical approach is no longer deterministic (meaning you have good probability of success, even optimality, but no strong guarantee of it), but let's not get into that.

This idea of incrementally detailing your path as you need it or as you have more processing time available is called an "anytime" algorithm, and the just-in-time (JIT) aspect of it is a good way to deal with dynamic environments.

>> I imagine this is the reason the larger triangular polygons are often used in navigation meshes?

The reason for triangular polygons is mostly about the fan-out pattern. In other words, a square 2D grid will lead to either 4 neighbors to each node (if you don't allow diagonal edges), or 8 neighbors to each node (if you allow diagonal edges). With a triangular grid, you get 6 neighbors for each node, and they are nicely distributed (roughly at equal angle intervals and equal distances). The square grid with no diagonals also has a nice even distribution of neighbors (equal angles, equal distances), but the branch factor is not much (4). If you allow diagonals, then you lose a very important property, the graph is no longer a planar graph (meaning that there is no way to draw the graph on a piece of paper without having two edges that cross each other), and there are some algorithms that demand graphs to be planar (not any of the shortest-path algorithms, IFAIK, but others).

Also, triangular meshes are just as easy to deal with as square grids (see the code above). They also generalize well to higher dimensions, and are very nice geometric figures (called a "simplex") ("nice" from the point of view of mathematics, not aesthetics).

>> Finally, I neglected to mention (sorry) that I will be able to drop objects in to the environment at run-time. Do you think that a fixed mesh would still be a suitable solution?

I think that a hierarchical mesh would do nicely. As I described, by only preemptively detailing the path just ahead of your character's motion, this will deal well with obstacles popping up. For instance, at each time-step, you make sure to validate the path that you planned in the close vicinity of the character (make sure he doesn't bump into obstacles that pop-up in front of him). And then, you do the planning as described, refining the plan ahead every time you move forward a substantial amount. It might be good to also revalidate your higher level plans regularly as well.

[_Nemesis_]

Thanks for clearly answering my questions :)
I think for now you have provided me with plenty of information to consider and read up on. If I need any more help then I know who to contact ;)

thanks again!