Choosing random location on navmesh

I added two methods to generate random points on navmesh to Detour. The first method generates random points anywhere in the mesh based on query filter, and the second method generates random points around a specified location. The first one is good for choosing just some random location, and the second one is good for finding a location which is guaranteed to be connected to the start location.

dtStatus findRandomPoint(const dtQueryFilter* filter, float (*frand)(), dtPolyRef* randomRef, float* randomPt) const;

dtStatus findRandomPointAroundCircle(dtPolyRef startRef, const float* centerPos, const float maxRadius, const dtQueryFilter* filter, float (*frand)(), dtPolyRef* randomRef, float* randomPt) const;

There were two tricky parts on choosing a good random location. The first was how to make sure that the random samples are more or less uniform, that is, the area of a polygon needs to be considered. Secondly, the filters and off-mesh connections make picking random polygon quite hard.

In general the filtering can be used to prevent generating random points in disabled areas, but you can also mark certain areas (i.e. spawn locations) and restrict the point generation only to those locations using filter flags.

I wanted to avoid allocations, so I started to look for a "streaming" random selection algorithm. The solution turned out to be Reservoir Sampling. I modified it a bit to make it consider the area of a polygon.

Area weighted reservoir sampling looks something like this:

poly = nil
areaSum = 0.0
foreach p in polygons {
    area = p.area()
    areaSum += area
    if (frand()*areaSum <= area) {
        poly = p
    }
}

Where frand() returns a random number in range [0..1). The basic idea is that each polygon is chosen at decreasing probability relative to the polygon area.

The good thing is that this algorithm works great in practice, the bad thing is that it is a bit slow. It needs to visit all polygons and calculate their area. This could be sped up by caching the calculations, but different filter types make this quite cumbersome in practice.

The code was committed in R331.

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):

• navtest.zip

Path Replanning

I've been picking on path replanning again. It is interestingly annoying problem. I have currently settled on following idea to make it somewhat manageable.

Prerequisite
In ever dynamic game world, the path finding and path following becomes statistic. The changes are that most of the time your request does not pan out the way they were requested. It is really important to have good failure recovery, both on movement system level as well as on behavior level. Plan for the worst, hope for the best.

Movement Request
At the core of the problem is movement request. Movement request tells the crowd/movement system that a higher level logic would like an agent to move to a specific location. This call happens asynchronously.

Path to Target
When the request is processed, the movement system will find the best path to the goal location. If something is blocking the path, partial path will be used and the caller is signaled about the result. From this point on, the system will do it's best to move the agent along this route to the best location that was just found.

Path Following
If a disturbance is found during the following, the movement system will do a small local search (same as the topology optimization) in order to fix the disturbance. If the disturbance cannot be solved, the system will signal that path is blocked and continue to move the agent up until to the valid location on the current path unless it is interrupted.

API
This could lead to following interface between the high level logic and the movement request.

struct MovementRequestCallback
{
 // Called after path query is processed.
 // (Path result accessible via ag->corridor)
 // Return true if path result is accepted.
 virtual bool result(Agent* ag) = 0;

 // Called when path is blocked and
 // cannot be fixed.
 // Return true if movement should be continued.
 virtual bool blocked(Agent* ag) = 0;

 // Called when the agent has reached
 // the end of the path trigger area.
 // Return true if movement should be continued.
 virtual bool done(Agent* ag) = 0; 
};

bool dtCrowd::requestMovement(int agent,
 const float* pos, const dtPolyRef ref,
 MovementRequestCallback* cb);

The 'result' callback allows the high level behavior to cancel movement in case unfavorable path rest is found (i.e. partial path), or it allows the behavior to set some internal state based on the path result.

The 'blocked' function allows the higher level logic to handle more costly replans. For example the higher level logic can try to move to a location 3 times until it gives up and tries something else, and it can even react to replays if necessary.

The 'done' function allows to inject extra logic on what to do when path is finished. For example a 'follow enemy' behavior may want to keep on following the goal even if it is reached, whilst 'move to cover' might do a state transition to some other behavior when the movement is done.

The general idea is to move as much of the state handling behavior out from the general code, and try to make the replan to be as cheap as possible. The downside is that the replan cannot react to big changes in the game world, but I argue that that is not necessary and should be handled with higher level logic anyway (i.e. the path can be come much longer).

What do you think?

Hierarchical Pathfinding in Detour

Uwe Koch has written a great thesis about hierarchical pathfinding with navmeshes. He presents a generalized version of HPA* implemented in Detour. The short summary: 4-5 times faster than Detour's A*, and uses 10-20 times less memory (graph nodes).

Applying graph partitioning to hierarchical pathfinding in computer games

• Thesis
• Source code

Path Replanning in DetourCrowd

I just added first version of path replanning for DetourCrowd. If a polygon becomes invalid along the path, the path is replanned. Invalid polygon means that the polygon just disapperas (i.e. a tile is removed), or its' flags don't match with the filter anymore. In the above video, the red polygons have disabled flags and the agents react to the changes over time.

The way it works on practice is that before the current path is followed, we peek ahead to make sure the next N polygons are valid (I used 10 in the above example). If a any polygon during that sub path is invalid, a replan is issued from the furthest valid position along the path. if the current polygon becomes invalid, or of the target location becomes invalid, the agent will stop.

There are some things I don't like about this method. Firstly, it is quite wasteful in resources. Issues almost a full replan is pretty horrible. I tried some local repair operations, but they ended up being too very complicate and hard to time-slice.

Secondly, the replanning does not react if a new venue becomes available. The topology optimization pass will catch many of these cases, but if the goal was unaccessible when the replannig happened, the current implementation will not try to replan when it reaches the end of the path.

The end of the path could be flagged or some other tricks, but I think I might be missing a bit bigger picture here. What actually does a movement request mean?

Example of nasty case

Here's a simple example which emphasizes one of the problems with replanning. There is a house and it has a door which can be open or closed. The NPC does not have key (cannot open door), and wants to move inside the house. If the door is open, the NPC can walk in, that is path A in the picture. But what should be do if the door is closed?

From navmesh point of view, it looks like the graph is broken at the location of the door. The usual fall back in case no path is found is to return a path which leads to nearest position around the target. In our case that would be the path B in the picture.

It is really hard to tell the A* that there actually is a closed door and that the nearest accessibility to goal location is semantically the door. And this is when things start to slip from a technical issue to a simulation or story issue.

Imagine a case where the agent starts to move to the building, and before it gets there the door is closed. The story seen by the player could be something like this: The bad guard tried to capture the princess, but at the last moment the princess managed to close the door, and then the guard went to hide under the trees.

Game levels are full of cases like this. The AI has no notion of the trees, but when the AI walks under a tree and stands there, the player will give meaning to it.

There are more problems with that case too. For a moment imagine that we could replan the path every time the world changed. Now if we had a situation where the door would open and close every few seconds, the agent would get dead locked at the east side of the building since the solution would flicker between paths A and B.

These are just few examples which happen when you add replanning to your navigation system.

Solution

I think the proper solution to reacting to dynamic changes in the navigable surface is to treat the planned path the same way as any other plan in the AI system. That is, it is very likely to fail, and the plan will be considered as failed, if small adjustments to it cannot fix it. This makes assumptions about the request quite clear. It may not be the best solution, but I think it puts the decision at the right spot.

Request for comments! How do you handle partial paths and replanning?

Paris Game/AI Conference 2011 Slides and Demo

The Paris Game/AI Conference is over and it was a blast! There was just so much interesting stuff in there that my head was just about to burst. I really like the shooter symposium where handful of studios gave microtalks (about 15mins each) on similar subjects followed by a panel discussion and Q&A. It was really inspiring to see different ways to solve similar problems.

My talk this year was about some work I did for Killzone3. I made a handful of tools for them to improve their AI level design workflow. In my talk I concentrated on how to automatically build cover annotation for the player. Killzone has this mechanic where the player can latch to a cover and slide along it. AI cover locations are discrete points are explained and were deducted from the player cover.

The cover locations are found using voxelization and tracing the contours of voxelized areas. Then the contours are sampled to see if they are close to a wall, and further the wall height is calculated and cover planes are build from that.

I also explained how this idea can be further expanded to automatically find jump-links and other non-locomotion navigation annotation.

Here's the link to the slides and demo (with source, sorry only OSX binaries):

• AIGD11_MikkoMononen_AutoAnnotations.zip

I think the presentation did not go as well as last year. I tried to fix some problems I had last year, but ended up failing in some things I think nailed last year.

Firstly, last year I had two topics, and it seems I was only able to get the second topic through. So my idea for this year was to present one battle-proven practical idea and show how to vary it. Hopefully with enough details that people can implement it and maybe fond other uses for the technique too. I think the scope was good this year.

Secondly, even if I think my presentation last year was cool (and I got a lot of good feedback from it), I think it was a distraction. So this year I tried to simplify my slides to bare bones. The regular slides format does not work very well the way I like to explain things. I find it much easier to show different debug renderings in a demo and talk on top of that.

I horrible mistake I made this year was that I did not have enough time to practice the presentation out loud, in front of other people. I chopped some topics, since my practice runs were always over time. During the presentation I was super nervous because I did not have good confidence on time, and I ended up rushing through the slides super fast.

Lessons learned, I hope my next presentation will be much better :)

Temporary Obstacle Progress

I've been super busy recently. Our startup just opened a public beta. I have managed to get some progress done on the temporary obstacle handling, though.

This is now probably the 4th rewrite of the system, so things are slowly being massaged in place (it usually takes 5 rewrites :). Adding and removing obstacles works again, and I've done some good progress on making the tile cache class better. Though, the API is still a bit in flux.

I'm currently testing with cylindrical obstacles, my plan is to support only extruded convex poly obstacles at first and add support for custom obstacles types in the long run.

I get quite consistent average of 0.1ms per layer build time, and about 10% compression ratio of the layer data when using 48x48 layers. The compressed layer grid data needed to rebuild any navmesh tile with obstacles in the scene pictured above takes 75 kB. The navmesh itself for that scene takes 72 kB.

I have few things left to do to finish this feature: 1) a custom pass before the mesh is being passed to navmesh builder (to handle flags), 2) handle off-mesh connections. Once that is done, I will start making releases again. I wonder if I should call the next release Recast & Detour 1.5 or 1.9?