Custom Detour Query Filters

I just committed the change for custom query filters and slight optimisation for the A* (SVN R200).

Custom Query Filters

I kept the earlier default behavior of the filter, so the API and functionality change is really small. Instead of calling dtNavMeshQuery.setAreaCost() you now call dtQueryFilter.setAreaCost().

There was quite some discussion if the passFilter() and getCost() should be virtual function calls or not. For people working on PowerPC processors it can be quite a big deal as both the functions are called per node during A*. On PC, the perfomance loss of using virtual function is not super bad (about 5-10%) compared to the flexibility it gives.

There is a define in the dtNavMeshQuery.h called DT_VIRTUAL_QUERYFILTER. If the define is set, the above mentioned functions are declared virtual and you can override them. In other case, the default implementations are inlined which should lead maximum performance. This was the best compromise I could think of.

Your custom query filter should be as fast as possible, as it can easily dominate the A* performance. If you want to query an agent flag, cache it locally inside the custom filter before you call pathFind(). If you need to do physics queries, try to cache them too before hand too. Use as little extra data as possible.

A* Optimization

While I was testing the impact of the virtual calls I noticed that the edge midpoint calculations were taking quite substantial time, so I tried caching the results. I earlier thought that having smaller node size and recalculating the edges on the fly would be more efficient than storing the node positions. It doubles the node struct size and all.

It turns out I was wrong (may vary per platform). Anyways, the node position is now stored for each node. This also opens up possibilities to try different node calculation methods. Caching the node positions resulted about 15% speed improvement.

This is the piece of code that calculates the node position:

            // If the node is visited the first time, calculate node position.
           if (neighbourNode->flags == 0)
           {
               getEdgeMidPoint(bestRef, bestPoly, bestTile,
                               neighbourRef, neighbourPoly, neighbourTile,
                               neighbourNode->pos);
           }

Be aware not to create neighbour nodes on top of each other (that is, zero length connections). For example if you want to place that new node so that it is the nearest point on the edge from parent node, then you should clamp the edge 't' to lie between for example 0.001 and 0.99, or something similar. You can use getPortalPoints() to query the segment which connects best and neighbour.

I also added a debug view mode which displays the nodes and link to their parents. This should help to see how well the node placement might work.