Saturday, July 17, 2010

Pink is as a debug color is the one true way

I've been playing around with the poly-tool thing I made last weekend. This time I've given each triangle a node and then linked adjacent nodes. Which forms a very pretty graph. This type of graph can be used as the basis of a path finding system, which seems to be where this is heading.

My method of finding adjacent nodes is inefficient and possibly a little bit wtf but it works and it's a pre-process step (something that wouldn't be done while a game is running) so I'm happy to leave it as is for now.

The node positions are pretty easy to find, I've used used the centroid.

struct Triangle
{
    public Point A { get; set; }
    public Point B { get; set; }
    public Point C { get; set; }

    public Point CalculateCentroid()
    {
        float x = (A.X + B.X + C.X) / 3;
        float y = (A.Y + B.Y + C.Y) / 3;
        return new Point(x, y);
    }
}

It's just the averaging of the surrounding vertices to find the centre (centroid point, apparently triangles have a number of notions of centre) point.

The next step would be to whack an A-Star algorithm on this and see what happens. I'm pretty sure in certain cases the movement wouldn't be optimal and would look a little odd. To get around this there are things like the funnel algorithm but I don't know how far I want to take this little demo / experiment.
Post a Comment