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

                 
        _nodeGraph.Add(node);
        polyToNodeMap.Add(poly, node);
    }

    // Create the edge nodes and add the links
    // !* 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);

        // Add bidirectional links to connected polys and edge polys.
        polyToNodeMap[connection.StartPoly].Neighbours.Add(connectionNode);
        connectionNode.Neighbours.Add(polyToNodeMap[connection.StartPoly]);

        polyToNodeMap[connection.EndPoly].Neighbours.Add(connectionNode);
        connectionNode.Neighbours.Add(polyToNodeMap[connection.EndPoly]);

        _nodeGraph.Add(connectionNode);
    }

    return new Tuple(startNode, endNode);
}

It's a little scruffy - do I really need to pass that many parameters in, have the dictionary, lazily return those two nodes in a tuple? :)
Post a Comment