Proposal for Custom Cost and Polygon Filter for Detour

I have been recently discussing a potential solution to issues 47 and 103 with Neil Armstrong. That is, how to allow the user to pass custom cost values for A*. In some cases the different travel costs could be based on NPC type, or maybe even some local context like trying to avoid the polygon where the target is.

I think this kind of functionality is really important to achieve correct gameplay, and usually there is no one solution that fits all.

I'm proposing a change to the dtQueryFilter which would allow custom logic on polygon filtering as well as custom cost for searches. Here's the interface and the current implementation as an example:

struct dtQueryFilter
{
   dtQueryFilter() :
       includeFlags(0xffff),
       excludeFlags(0) {}
  
   virtual bool passFilter(const dtPolyRef ref,
                           const dtMeshTile* tile,
                           const dtPoly* poly) const
   {
       return (poly->flags & includeFlags) != 0 &&
              (poly->flags & excludeFlags) == 0;
   }
  
   virtual float getCost(const float* pa, const float* pb,
                         const dtPolyRef prevRef,
                         const dtMeshTile* prevTile,
                         const dtPoly* prevPoly,
                         const dtPolyRef curRef,
                         const dtMeshTile* curTile,
                         const dtPoly* curPoly) const
   {
       return dtVdist(pa, pb) * areaCost[curPoly->area];
   }
  
   float areaCost[DT_MAX_AREAS];

   unsigned short includeFlags;
   unsigned short excludeFlags;
};

The input to the cost function is a line segment from pa to pb which travels along curPoly and the previous and next polygons.

I'm not big fan of interfaces and I was worried how much overhead it would add. In my test case the path queries vary from 0.030 ms to 0.135 ms (there are some small fluctuations from run to run). When the passFilter() is virtual function instead of inlined function it adds 0.010 ms to 0.020 ms per path query. I think the interface is worth it.

So this post is request for comments. Unless anyone disagrees or proposes better solution, I will check in the changes.

[EDIT] I did few more tests and the above did not actually include the cost as virtual call, only the polygon filter as virtual function call. In total the virtual function call version is something around 5-10% slower.