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);
}