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.