Monday, January 25, 2010
Off-Mesh Connection Progress pt. 3
Almost there! I just got the Off-Mesh connections to work with tiles. It was a bit more work than I expected.
I like tight data structures and that was one of the things why things got quite complicated with Off-Mesh connections. Previously all the links were stored in one big array, and each polygon would have base index plus number of links which specified the links per polygon. It was reasonable painless to extend that to allow add few links in between using double buffering and bit of precalculation.
The way I chose to implement the Off-Mesh connections required some of the data to be resolved at runtime. That made managing nice array of links eventually too complicated. So after long struggle I switched to linked list which is build initially so that it creates contiguous strips for internal edges and after that all dynamic edges are allocated from simple free list.
I have not done any performance testing yet, I don't expect it to be that much slower and I hope it will help me to improve some more dynamic features later.
The link structure currently is a bit too heavy to my taste, it's 12 bytes. Typically links take somewhere between 30-60% of the memory consumption per tile. If I can get rid of bmin and bmax of the link without causing too much burden at the runtime, I should be able to pack edge and side to the extra bits of the next index, which would leave 8 bytes per link (and roughly 15-20% less memory usage in total).
A bit more testing and cleaning up and I can let off-mesh connections to be as is for a little while until I will visit them again to add the segment-to-segment links. There are some rough edges which need to be fixed for the demo too. I've yet to come up with good visualization of the Off-Mesh links which would allow me to draw them while editing and when they are "baked" into the navmesh.
There has been some contribution work done to allow Recast and Detour to work on different coordinate systems, definitely a feature which will help many users. There are couple of things related to that which I have not quite settled in yet, but that feature should see the daylight soon too.