Sunday, January 1, 2012

Loose Navigation Grids




Due to my startup, I have not had much time to do navigation research last year. I think I have been thinking on my few odd spare cycles is the idea of loosely connected grids, which kind of mixes waypoints and grids for the ultimate dynamic navigation. I had a little time during holidays and I thought I'd give it a spin.

A Grid

The whole process starts with voxelizing the level geometry much like in Recast and finding walkable surfaces. After that the area is converted to a 2D heighfield. This is done by doing a breath-first search starting from the center of the walkable surface. The voxelization is created around a point on walkable space, so this location is guaranteed to be walkable. This initial step finds contiguous walkable area that can be stored in 2D grid.




The property I tried to improve in the voxelization phase compared to Recast is the bounds. In Recast each tile requires to voxelize a column which cuts through the whole world vertically. This makes the runtime for the voxelization really unpredictable. In this version the grid voxelization bounds are always the same, which makes the whole process more predictable in terms of max memory and processing.

Automatic Exploration

As you can see from the image, the voxelization bounds are a bit larger than the actual grid. The larger area is used for two purposes. Firstly, it allows to counter for the obstacle expansion like in Recast, and secondly, it allows to calculate which neighbor cells in the 2D grid will lead to unexplored space. The dark outlines in the grid shows cells whose neighbor cells lead to unexplored space, I call these border cells.




These border cells are used to find few good locations for new grids. The process for find new grid locations starts by sorting all the border cells so that the nearest cell to the center is first. Each of these seed cells are visited in turn and if the location is not occupied yet, a new grid location is stored, and a perimeter around the grid location is marked as occupied. I use breath-first flood fill for this. A perimeter up gridSize/2 distance is marked as occupied. The yellow ticks in the above image mark these locations.

In addition to the flood fill, overlap of neighbor grids is used to filter new grid location generation.

The whole exploration process starts from one grid and it's potential new grid locations expanding until the whole connected walkable surface is covered. That is, because the neighbor overlap is taken into account, the process will some point just terminate, since there are no more new potential grid locations.

Finally connections between the grids are found. For each grid overlapping grids are found (the check is done at cell level), and closest 6 grids are stored as neighbors.


Path Planning

I have not yet implemented this phase, but this is how I think it should be done.

In order to move an agent in the world, first an A* search is done along the high-level graph which connects the grids. This path can be continuously replanned to take into account changes in the graph.

Movement within one grid is calculated using simple grid path planner. In order to move the agent from the current grid to the next grid, the goal is set to the nearest point which in the next grid. This should create similar behavior as described in Way Portals. It is quick to calculate the overlap between two grids, so it can be calculated on the fly. Once the agent is on the next grid, the next grid is set as current grid, and overlap is calculated and movement towards the next grid begins.


Future Improvements

There's a lot of work to be done to improve grid placement during the exploration phase. Currently there is too much of overlap, and this could be improved by voxelizing a bit larger area and using that extra area beyond the grid size to find the new grid locations. This extra padding could be also used to sample jump-links as per my Paris 2011 persentation.


Conclusion

Building efficient navigation structure for dynamic worlds is tricky. I think this technique has a lot of potential. For a long time I thought that grids are too memory heavy, but the real break through for me was when I realized that the grids can be kept compressed in the memory. This reduces the memory consumption down to the same level as navmeshes.

The technique combines small grids with waypoint graph. I think it has a lot of "roadmap" flavor to it. Here's some important properties of this navigation method:

  • Local: Pretty much every aspect of the technique is local: generation of each grid is local, traversing of each grid is local, updates to the grid are local too. This is important to keep the memory and processing in budget.
  • Hierarchical: In order to make path replanning fast, the navigation representation needs to be hierarchical. Replanning should do only small amount of work, and the rest of the system should iteratively find more precise solution.
  • Dynamic: When something changes in the game world, it needs to be reflected in the navigation graph too. Firstly, this technique allows quick updates to the navigation representation. Building individual pieces as well as connecting them together needs to be flexible and fast.

I think this is the way to implement path planning in 2012!


Download prototype and code (OS X):



7 comments:

  1. Interesting approach (as always), i don't have a Mac right now but I'll check your code !

    I have a ew questions though:

    - The 6 grid neighbors you're talking about are left/right/front/back/top/bottom ? Why do you need the top and bottom neighbors for navigation purpose ?

    - Why do you keep the overlapping part of your grids once the gris graph is computed ?

    Happy new year btw !

    ReplyDelete
  2. @Clodéric, the grids themselves are not placed on a grid like Recast tiles. They can have any relation to each other (much like waypoints). So 6 is just some number, it generally describes good selection of neigbours (circle packing).

    The overlapping parts are kept so that it is possible to add, remove and update grids on the fly. Compression takes care of the wasted space. This type of simple grid data compresses with LZ to similar amount of data as comparable navmesh would take.

    ReplyDelete
  3. Hello Mikko,

    I am sorry to send here but I see you are active here so...

    Could you please point me to some startup documentation or tutorials on Recast and Detour? I want to use it for my RTS game for bachelor thesis.

    Thanks

    ReplyDelete
  4. Thank you for your code. I have used it and a Theta* search algorithm to implement grid rasterization and local grid pathfinding for a large map with a combination of wide spaces and compact buildings. My next task is global path finding and I would like your thoughts on a potential problem: How not to wobble like a drunken sailor.

    Lets say I need to find a path from A to B that crosses about 10 grids at a 60d angle. If we do a normal A* search on the global grid, we'll get a list of grids that's pretty close to the bresenham line between A & B. Now, starting from grid 0, what point do we aim at?

    If we aim at the center of the next grid, we'll get a drunken sailor walk that weaves back and forth across the 'ideal' line. If we aim at the center of the next->next grid, the line will be a bit straighter but still weaving. The best choice in this case is to aim at the point on grid 0 that is closest to the end point B.

    So now, lets ask the pathfinder to do A to C where the ideal path would be A-B-C with a right angle turn at B. If we use the straight path code from the A-B example, we'll have the drunken sailor problem again as the path is adjusted every time we enter a new local grid. It gets worse with the case of A to D where D is south of A and we have to go north to B and east to C first in order to get there. Using the straight-line code we might never get there!

    So, how do you anticipate performing a local grid search that will approximate a straight line, yet still be able to move around global obstacles?

    ReplyDelete
  5. Here's a couple of my older posts, which should give some more detailed answers:

    Firstly, global path finding. I think one should use the "portals" between two tiles to calculate the global path. If we "approximate" the movement inside each tile as straight line then we can use funnel algorithm to find more straight global path, like described in the post:
    http://digestingduck.blogspot.com/2010/03/sketch-for-hierarchical-pathfinding.html

    The same approximation idea can be applied to make the local path finding simple and fast.
    http://digestingduck.blogspot.com/2010/03/local-navigation-grids.html

    On top of these, I would definitely try to optimize the path as the agent follows it. Something similar as I've done with navmesh based methods:
    http://digestingduck.blogspot.com/2010/11/path-corridor-optimizations.html

    Assuming that the movement within a tile may seem too approximate. Assuming about 5x5m tile, human sized characters, and 2D grid that is actually a good approximation.

    ReplyDelete