Friday, August 20, 2010

Visibility Optimized Graph Experiment


I blogged earlier about A* node placement. I had the change to try out the visibility optimized node placement today. First impression, not impressed.

It generates quite aggressively goal directed paths, much like if you over estimate your heuristic (or was it vice verse). The final segment to the goal is always perfect, though.

In case someone wants to give it a try, here's the code I used:
static int isectSegSeg(const float* ap, const float* aq,
const float* bp, const float* bq,
float& s, float& t)
{
float u[3], v[3], w[3];
dtVsub(u,aq,ap);
dtVsub(v,bq,bp);
dtVsub(w,ap,bp);
float d = dtVperp2D(u,v);
if (fabsf(d) < 1e-6f) return 0;
d = 1.0f/d;
s = dtVperp2D(v,w) * d;
// if (s < 0 || s > 1) return 0;
t = dtVperp2D(u,w) * d;
if (t < 0 || t > 1) return 0;
return 1;
}

...

if (neighbourNode->flags == 0)
{
float sa[3], sb[3];
getPortalPoints(bestRef, bestPoly, bestTile,
neighbourRef, neighbourPoly, neighbourTile,
sa, sb);
float s,t = 0.5f;
if (!isectSegSeg(bestNode->pos,endPos, sa,sb, s, t))
dtDistancePtSegSqr2D(endPos, sa,sb, t);
t = dtClamp(t, 0.1f, 0.9f);
dtVlerp(neighbourNode->pos, sa,sb, t);
}

1 comment:

  1. I personnaly tested an intermediate way by blending the MidEdgePoint & ClosestPoint to StartEnd segment. So the crossing edge position is clamped between 25%-75% of the Edge.
    For me it works fine and it fixed 95% of all my "Big Edge vs small Edge" distance estimation bugs.
    The ultimate technic would be to do the string-pulling algorithm during A*, but i failed trying to merge them :(

    ReplyDelete