Recast and Detour 1.21

Small maintenance update to Recast. There is no new functionality, but I refactored the GUI and demos.

I noticed that I will need to add yet another, yet slightly different, way to build the data for my current endevour of making a tile based navmesh fro Detour. The current demo is getting too complicated. So I went and refactored the GUI and the generation code that it is easier to create new ways to create and use the data. The Recast API will stay the same, but the way the data is passed to the new Detour stuff will be different and I want to create functional tests for the new code too.

If you are new user to Recast, take a look at BuilderStatMeshSimple.cpp it should get you started how to integrate Recast into your own code. BuilderStatMesh.cpp should give you an idea how to use Detour static navigation meshes. If you want to generate navmesh for larger areas, check out the tiling examples.

Now that the GUI refactoring is done, I can continue adding tiled navigation mesh support for Detour. The idea is that the whole navmesh is composed of several pieces. Just like the tiled preprocessing generates them. These pieces can then be added and removed at runtime creating the basic structure of streaming the navmesh or generating new tiles at runtime.

I have pretty solid plan how to go forward with it. I plan to support the same API as the dtStatNavMesh has, plus some extra functions to add and remove the mesh tiles. I will (slowly) work towards that goal this summer.

Recast and Detour version 1.21

Recast 1.2

One of my larger projects currently are Recast and Detour. They are both open source projects aiming to solve some path finding related problems. Recast is automatic navigation mesh generation toolkit and Detour is a runtime component which can be used to do some spatial queries and pathfinding on navmeshes. Basically you can throw any triangles mesh Recast and it will generate a mesh from that data which allows the AI to navigate in that environment using Detour.

By releasing Recast and Detour open source, I hope that people who usually do not have access to such technology can fullfill their crazy ideas as well as I hope the code can live up to high standards of other game developers and they could adopt it to be used in their games.

I just recently released Recast 1.2. In this version the new feature is to be able to build navigation meshes in tiles. That is, large worlds which would not otherwise fit into memory can be processed in smaller chunks.

The tiles allow other kinds of interesting things too. First the Recast algorithm performs way better when it is run on smaller set of data. The bottleneck of the algorithm is large open areas. They will create inaccuracies and take a lot of performance. Secondly if the tile size is reasonable, the resulting mesh will follow the contours of the underlying geometry much better.

The really interesting stuff will follow in the next version, Recast and Detour 1.3. I plan to use the tiled data structure at runtime too. Currently the tiles are stiched together after all the processing is done.

The tiled structure allows us to do streaming. That is, the user is able to remove and add tiles he wishes. It does not matter where the tiles come from, it can be from disk or you can create the tiles on the fly too! Recast is fast enough to build a 20 by 20 meter tiles in about 25-50ms (assuming indoor shooter level). I have not idea how well this will work in practice, but I'm really eager to find out!

There are other things the tiled structure allows too, for example it would be used for hierarchical pathfinding (HPA*) and certain queries, like finding nearest polygons, can be made faster too.

NanoSVG

I like prototyping. Over the years I have gathered small pieces of code I seem to rewrite every time I land to a work environment. This is my first attempt at storing these interesting bits for other people to use too (and to save myself the trouble of finding the previous version from some half broken hard drive).

NanoSVG is simple and stupid SVG parser that does not need ay external libraries. Just blob the header and a source file into your project and your ready to enjoy vector paths! It is just enough that you can do all your level editing in Inkscape or Illustrator, hit save and play your new level.

I usually use colors to encode different things. For example red squares could be enemy spawn locations and green square the starting point of the player. If you need modifiers, just add outlines, so that red box with blue outline means a grunt with a SMG.

As you might have guessed my prototypes often look like geometry wars. I tend to use OpenGL to draw antialiased lines, points and some text. The point is to build something just enough to get validation or better insight to your ideas.

This version of the SVG parser is based on the Antigrain Geometry SVG example, and I wrote similar parser with Kimmo when I was working with Mountain Sheep.

Wobbling towards 'awesomeness'

The digesting duck captures my point of view to game AI so well that it is hard to decide where to start describing it.

I think there are a lot of parallels on how the automatons were build once upon the time and how game AI is being build in 21st century. It is a shame to think how much of the original ideas of those illusionists we have lost. I think we could learn a lot from the observations of the people from that time.

Too much of the game building is though to be magic. Most of the designers (especially ones that have no programming background) I know have a lot of trouble understanding how game mechanics work.

And the most common reason seems to be that they want to believe. They want to believe that there is something magical happening in the code that makes things tick. Just like the people who saw mechanical pooping duck few hundreds years ago.

I think better analogy is that we are building mechanical toys. Instead of popping the hood, we open the game editor or turn on debug views. These visualisations of the inner workings of the game magic should give the designer better understanding how things work. I sometimes feel like the game studios should hire UX people to make the game data more understandable for all the people whore are working on it.

My intention is to make this blog about building the most awesome 'mechanical toys' and share snippets of interesting code.

The title of this post is a 'homage' to my friend's Chris' blog. He does not post often, but when ever he does it is pure awesomeness.