## Sunday, July 25, 2010

### PathFinding Mark 1

Pathfinding now works. The above shows a collection of convex polygons with their joined edges connected. Click once inside the polys to start the path and again to end it and a line will be drawn respecting the polygon bounds. The funnel algorithm could still be implemented on top of this to make the path more optimal (but it would probably hug the edges more and look a little unnatural for an advenutre game.

You could do thing like tags polys or edges in the Astar graph for special animations like stair or ladder climbing. Though I don't know how much of a headache it would be to get the animation to sync to the structure of the stairs or ladder.

I'll clean this code up a little and update the repository soon.

Here's how the nodes and connections are made into a graph for the A* algorithm.

```private Tuple CreateNodeNetwork(ConvexPolyForm polyStart, ConvexPolyForm polyEnd, Point from, Point to)
{
_nodeGraph.Clear();
// Store a map poly -> node to make it simple to work out the connection nodes.
Dictionary polyToNodeMap = new Dictionary();

PathNode startNode = null;
PathNode endNode = null;

// Create a node for the centroid of each polygon
// Replace the postion of the start and end polygon.
foreach (ConvexPolyForm poly in _polygons)
{
Point position;
PathNode node;
if (polyStart == poly)
{
position = from;
node = new PathNode(position);
startNode = node;
}
else if (polyEnd == poly)
{
position = to;
node = new PathNode(position);
endNode = node;
}
else
{
position = poly.GetCentroid();
node = new PathNode(position);
}

}

// !* This is where you'd add several nodes per edge, if you wanted.
foreach (Connection connection in _connections)
{
LineSegment line = connection.GetShortestEdge();
Point midPoint = line.GetMiddle();

PathNode connectionNode = new PathNode(midPoint);