Getting to Know My Data

In order to forward with the tiled navigation, I decided to take a bit more detailed look at what kind of data Recast creates per tiles. I knew roughly how much time it takes per tile and I could say that there were not that many polygons per tile. I like this part of the job. It always gives me such insights.

I ran my tests with 32x32 tiles (which means 40x40 rasterization when the padding is added, that results 50% over rasterization), max 6 vertices per polygon. The above scenarion was generated in 13.5 ms and it touched 11750 triangles during rasterization. I'm sure there are a lot of unnecessary triangles which are processed.

My current input data is huge mesh (the above one contains few million triangles) and I divide it into chunks of less than 512 polygons using AABB tree like algorithm. This is sort of balancing between memory and speed. In real world example the data usually would be a database of objects, which creates much nice partitioning in practice.

After running the tests I noticed that almost half of the tiles in my test data usually contain just one polygon! The most complex tiles I got were around 32 polygons. This means that if I chose to use HPA* for pathfinding, I could just sore a small lookup table inside each tile to find paths inside that tile.

Most of the time the technique is able to create a tile in about 15 ms, the most complex cases do not exceed 50 ms. The technique is currently rasterization bound, which takes over 50% of the build time. This is actually good news, since I think there is a lot of room for improvement there.

The results from different levels show similar trends in build speed and polygon counts.


Thanks to John Ratcliff for the test data!