Detour Crowd Path Replanning

Path replanning for Detour Crowd has been a long time pet peeve of mine. I've blogged about the problems surrounding it earlier, but very little code has been submitted. I've been testing some ideas along the way, but never managed to have the few hours of solid coding to get all the pieces together.

Here's what happens in the above video:

• At start all the agents find a short parts towards the goal. In the video they intentionally get stuck at local minima at start. Generally this improves responsiveness, but sometimes the agents move to wrong direction for a moment.

• During movement the agents will replan their paths if they notice that the navmesh has changed in front of them. When the agents turn to purple, it means that they are replanning their paths. Similar small search is performend when the replanning occurs, but polygons along the existing path are favored. This makes changes close the agent responsive and changes further away does not make any visual change at all.

• When the agent approaches the end of the path and the last polygon on the path is not the goal polygon, the agent will periodically replan the path. When a pathway to the goal opens, the agent will use that path.

On top of that there is the path topology optimization going on too. I think the recent changes made that pretty much irrelevant–I think it might be better to just fire a replan every now and then just for the kicks.

I think that summarizes my thinking about path following in general. Once the world is constantly changing, the system ends up replanning the whole time. You cannot replan as much as you would like to since it is hard to determine how long A* will take, so the system becomes this weird scheduler-caching-magic-fudge-latency-hiding-box. There are these dynamic planning algos, like D*, but they all require too much memory.

I hope to get to have the change to put another pass on Detour Crowd replanner to make it much simpler and more robust. Now there is too much state management spaghetti in there.

The changes are available in SVN, please not that I removed the adjust move target function as it was complicating the logic too much. If you are using it, please let me know and I'll try to figure out similar functionality. I also added velocity control for agents (for player characters and such).

Crafting 3D User Interfaces for the Web

I had a talk a little while ago at local frontend dev event called Webshaped. My talk was about how to craft easy to use, tangible 3D UIs. This is one of the dearest topics to me, and I think I overdid the presentation a bit. It kinda became a mash-up between a game design talk and UI talk for kinda designers and sorta programmers (or developers as web folks like to call them).

I think I will redo the presentation at some point in the future if such an opportunity presents itself. Maybe more focused on some of the sub topics, or more maybe with interactive things to try out etc.

I have not talked much about Tinkercad on my blog so far. A lot of the interesting stuff about Tinkercad does not quite fit the voice of this blog, but I think I'll write a thing or two about it.

For those who don't know, Tinkercad is super easy to use 3D modeling tool for makers, artist and tinkerers alike. It works directly in your browser. Under the hood Tinkercad is a solid modeler, which means that all the stuff you make with Tinkercad can be 3D printed.

Here's something we did just recently, an embeddable viewer for your projects. The project shown below is a plan of our deck with summer furniture and some gardening stuff.

Loose Navigation Grid Prototyping

I had a little time this weekend to work on AI again. I've blogged earlier about loose navigation grids, and now I finally got it to the point that it starts to look interesting. Above is a video showing the current prototype in action.

Path Planning in Dynamic Worlds

In addition to this example, I've been working on path replanning in DetourCrowd. It has become painfully obvious, that the most limiting factor for pathfinding is that we assume that it is perfect. Dynamic worlds make this pain a migraine.

If the world is constantly changing, the notion of "path to the goal" becomes really hard to define. Even the goal itself becomes uncertain. For example if we picked a cover point and the level around the AI and the cover changed, is the cover a good choice any more? The more I've thought about it, the broader the problem has spread.

I have earlier discussed that I think in changing worlds, the contract between the behavior and the pathfinder should be the initial path. If the initial path changes too much, then the behavior plan fails and the behavior should replan too. This does not seem to be well accepted idea, so I've started to rethink the problem.

The feedback I'm getting from the people who are using Recast is that they would just like everything to work. Out of the box, don't-tell-me-how-it-works.

Loosing Up the Constraints

So the idea I'm toying with the loose navigation grids is that you just drop your character in the world, tell it to go to some location and it happens or not. The important idea I'm testing here is that can we make the navigation system uncertain? There is no guarantee that the agent will find its' way to the goal, but it will try, with limited horizon of information.

This allows a couple of things. Firstly, since we know that we have limited view of the world, we can use greedy search algorithm and replan to our hearts content. We're side stepping A* worst case performance which means visiting all the nodes in the graph. Secondly, accepting the limited information again, interesting culinary opportunities open up as such as exploring the navigable space more locally, iteratively, patching things up as we go, throw away information that is too far.

The down side is that given the local nature of the search space, the system will get stuck in local minima. But then again, how big are local minimas in games? MMOs may have the nasties pathfinding problems of the all, but I think they should use hierarchies to hide the complexity. 

I think this has been interesting though process so far. I've been able to let loose a lot of preconceptions and limitations I had before.

The Prototype

In the above video you'll sees that the loose navigation grid is build on the fly by starting at a seed point (i.e. character location). The exploration step looks at open edges in the local nav grids (hilighted at the end of the video) and creates a new grid at such location. Path planning is done hierarchically, first between the grids and then within one small local 2D grid.

The navigation structure should be "self healing". If an obstruction is added or removed, the intersecting grids can be deleted and exploration phase can be rerun on the neighbors of the deleted nodes to fill in the space.


Next time I'll have a little time I will try to make the whole path finding and movement to work to see how good it looks and then it is time to test some destruction.

Ludum Dare 23

Last weekend I took part in Ludum Dare game development compo. I've been jealous to Jetro for a long time because he always manages to make something great in these compos. So I took the time and bit the bullet myself.

The game I made for the compo is called Gingerbread Kingdom, it is kind of a mix between Carcassonne, Tower Defence and Rampart.

I set a couple of constraints to myself before I started: 1) Simple, 2) 2D Game, 3) written in Javascript. I often manage my daily work using disposable prioritized todo lists (Babauta style), and I often doodle pictures to set myself longer term goals. The castle and the giant in the above picture is the one that kept me going in the Ludum Dare concept (even if giants turned into birds later on). I had the idea of using the Carcassonne tiles from get go. When I saw the last theme voting, it was quite clear that it would fit in any of the ideas.

Equipped with these ideas I started to work on placing the tiles, finding complete castles and scrolling the area. Initially I had the idea that the world would be infinite (of course!), as I went on I kept on making it smaller and smaller, until at very end I removed vertical scrolling. On hindsight,  I think the game would be twice as fun if it did not have any scrolling at all.

One tile placement was working and I could detect the castles, it was time for some enemies. At this point the world was still infinite and I struggled to figure out a way to spawn enemies from any direction without making the game too frustrating. In the spirit of getting things done, I just made them always spawn from right, and afte I had implemented the first version, I did not see any reason to make it more elaborate.

Once I got the basic conflict set up, the hardest part of the project started: balancing. This was around the evening of the first day, and I was getting a bit worn out already. And boy was it hard! The game was not fun, it was unbalanced, unfair, buggy and I just had to keep on going to play it.

To get past that stage, I kept writing tiny lists of things that needs fixing, and fixed them and moved on. After some passes I started to see a game emerging, and it was time to start pruning things. The biggest change for me was to shrink the playfield. When I got the idea to use the Carcassonne tiles, I wanted to solve the Carcassonne problem that you run out of table. It took me more time than necessary to let go of that idea.

It has historically been really hard for me to design game endings. I can kinda make ok-ish failure conditions, but defining the point where you have won a game is just somehow out of my character. For example my earlier game Zen Bondage did not have game ending at all, you just had to decide that you're done. I kinda got away with it with the Buddhist theme there :)

So when I finished my "all nighter" around 2 am the first day, I had my basic game done.

The next day I concentrated on making game ending, and making the game more understandable. My design philosophy is: use less energy to decode more information. Usually this require rounds of user testing, and reworking things. This phase usually includes adding some kind of indication to all meaningful state transitions in the game.

My favorite tools for these indicators are particle systems and procedural animations. I think the 1.5 hours I spent on making that procedurally animated bird was well worth it. I wish I had had another 1.5 hours to spend on making a simple particle system, which I could have sprinkled all over the place.

I left the winning condition to very last stage of the project. I generally hate boss battles, so that was yet another mental struggle to get through. I'm glad my fiancee insisted on having a boss fight in the end :) Once I had it implemented, I had a stream of other ideas how to make the overal progress better, but no time.


The ideas that spawned the day after when I saw people actually play the game were:

• make tile rotation instructions in bigger, bolder, blinkier and fancier text 
• no scrolling, make the gamefield fit on screen
• add level of increasing difficulty
• could be procedurally generated
• ramp up difficulty based on enemies and terrain (water tiles)
• better indication which tiles are ready to fire
• lasers!

All in all I think it was a great project. the biggest lessons were that it is really hard to balance a game system when you're really tired. It turned out to be equally nasty to find bugs in dynamic language, especially refactoring was something was huuge pain. Next time I'll set up closure compiler from the start. I'm most proud that I was able to keep it simple and finish the game.

Demopaja Sources

Inspired by Farbrasuch's release of their demo tools, I decided to dig up my old Demopaja backup, clean up some directories from random crap, and put it up here for downloads:

• Demopaja_050508.zip

I don't have Windows dev machine these days anymore so I have no idea if it still compiles. I think it compiled back in 5th May in 2008 when I looked at it the last time.

I'm still quite proud of the tool, the documentation and all that. Even if I do despise the coding style – I was young then, you know.

[EDIT] You can treat the code public domain, some libs and snippets have their own licenses, treat them appropriately.

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