Wednesday, July 8, 2009
Tiled Mesh Progress Pt. 2
First succesful path query on tiled mesh got done today!
I initially thought that I would use similar structure of simply connected polygons as I used for the static meshes and make the connections between the tiles a special case. It turned out that with my target tile size (32-64 voxels) actually the opposite was true. There are more tile-to-tile connections than inter-tile connections. So I went and changed my data structure a bit and I got rid of few levels of indirection, cleaner code and less conditionals with the expense of a bit more memory.
The tiled mesh is going to be a bit slower than the static mesh, but I expect it to be quite swift still. Once I get the initial full version done, I will experiment a little with different packed data maybe even limiting the vertices to range of 0-255 (the height will need few more bits), to get the data size as low as possible. A lot of the calculations can be done in integer coords anyways, so it should not be a problem.
One design decision that is biting me in the ass constantly is that I wanted the changes to tiles be as local as possible. For that reason I allow axis aligned T-junctions at the connections at the tile edges. That is adding a bit more work on the runtime as I need to clamp some coordinates when an edge at the tile border is processed. But it think in the end it is worth it. This also forced me to make support for more links per polygon than there are edges, so this work should be useful later when I will add support for non-polygonal links (jump/animation links).