Thursday, August 19, 2010

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.

6 comments:

  1. Mikko,

    This idea sounds very flexible and I think its worth the small performance drop. With this interface you provide a lot of things out of the box.
    BTW. I´m wondering if this interface could be used as well to manage known/unknown area. E.g. if an agent only knows a way to room C through room B he will take that route although there might be a shorter way which he just did not yet discover. So an unknown tile would e.g. have infinite cost until it is discovered...

    Mirko

    ReplyDelete
  2. Mirko, yes. If you se really high cost, the path fill be found, but if you discard the unknown polys using the passFilter(), then no path is found (and it will be way faster too).

    ReplyDelete
  3. I did a bit more profiling because 10% decrease made me sad. I don't have very good profiling tools, so this is a bit of guesswork.

    I knew that the costly calculations in the path finder are: edge mid point query, cost calculation, node get (closed list management), node push, and node pop (open list management). Each of these take about 15% of the total time spent in the path finder. Some access random data and some are calculation heavy or costly algorithm.

    I noticed that if I cache the node position instead of calculating it every time, I can speed things up by 15%. The end result is that after the previous change which slowed things down 5-10%, the end result is faster than when I started changing :) The change doubles the dtNode size, but it is not huge addition in total memory consumption.

    As an edded bonus, caching the node pos allows me to test alternative node locations, like that visibility optimized version or a that "nearest point on target edge" tested earlier by other folks.

    ReplyDelete
  4. I guess you could avoid the virtual by making the query filter a template parameter for methods that need it. That could introduce other inefficiencies though and a lot of people don't like templates.

    With the virtual implementation you could provide a macro for turning it off so it uses a default non-virtual version for those who don't use it who don't want to pay the cost.

    ReplyDelete
  5. I think template is overkill here.

    There does not seem to be any measurable difference if those functions are virtual or not. If I make the functions inlined, I gain back about 5%.

    I'm testing now the code which has that node pos cache optimization in. That 5% also seems to be the amount my measures vary between the runs. If I take few averages, that inlining still wins few points.

    ReplyDelete
  6. Sounds like a very helpful feature!
    In my case, I have needed custom passFilter() function and no needed to calculate area cost.

    ReplyDelete