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.


  1. Is there a way with these off mesh connections to customize their cost ? A teleporter link for example would probably have a low or zero cost of use. I don't see a way to set up costs for flags. Perhaps you can add an application callback to get customized costs by area/flags or something

  2. I'm currently working on adding cost per poly/connection. So yes, soon there will be a way :)

    Btw, there was recent discussion over at about teleports and the related issues. There were few things (which I forgot already :) which took me a bit by surprise.

  3. Hopefully it's okay to comment here... Has cost per off-mesh connection been implemented yet?

    Looking at dtNavMeshCreateParams, I can't immediately tell. I'm new to Recast (but all too familiar with great libraries with not-so-great documentation). What does offMeshConRad do?

  4. @null_ptr, you can specify the off-mesh connection area type via offMeshConAreas, and use dtQueryFilter in turn to set the cost per are type.

    p.s. We have discussion forum too at