Weekly report (Jan 27)

Jason here,

This week I determined how the NPCs' movement between static areas will occur:

• There are predefined, convex hulls that represent more complex areas that are called Free Move Zones (FMZs).
• These zones are connected by portals. Portals designate where it is safe to pass from one FMZ to another.
• The portals will use Next Hop Forwarding to determine the fastest routes to a destination. These routes will be pre-generated using the A* algorithm.

So far, I have the basic environment processor finished; it reads an Autodesk .fbx file and loads the FMZs and portals, and it also links the portals and FMZs together.

In addition, I have developed an algorithm to test if a point is within a convex hull. Tell me if I'm wrong! I made it up in a hurry, but the principles made sense at a glance--I'll probably get to test and tweak it before next week is finished. I hope it seems just as clever by then : )

// point is the Vector3 being tested

// centerPoints[] is the array that contains the center point for each face in world space

// dirs[] is the array of normals for each of the faces

// this assumes that faces point outward

for (int i = 0; i < currentFaceCount; i++)

{

// the outward direction (if it is within the convex hull, anyway)

Vector3 dir = centerPoints[i] - point;

dir.Normalize();

// recalling linear algebra, this measures the angle between two vectors

double angle = Math.Acos(Vector3.Dot(dir, dirs[i])/(dirs[i].Length() * dir.Length()));

if (angle < 0 || angle > Math.PI) // is the opposite direction

{

// point is not under the plane, so it is not within the convex hull

return false;

}

}

// point was "under" the plane for every face, so it is within the convex hull

return true;