Voronoi in Games

In Attack of the Gelatinous Blob I recently came across the problem where I needed the human AI to build checkpoints, guard stations, and other defensive positions in appropriate places; but where should they go and how can I calculate that? Obviously I want them in densely populated areas and not in the wilderness, I also want them in as many places as possible so the player can’t flank the locations with blobs.

I remembered back to senior year in university studying computational geometry, in particular a routine to calculate distance relationships between points. If I used houses and building as points of interest, then I can find out what ones are closest, and from that I can determine the dense areas. In that class we covered Voronoi diagrams (and their inverse: Delaunay Triangulations) that do just that. Here’s a picture to demonstrate:

Delaunay_Voronoi

(Black lines are the Voronoi)

The red lines between the points are the center lines, and the Delaunay Triangulation shows the lines between points perpendicular to the Voronoi lines, like so:

Delaunay_Triangulation

With this information I can find out the smallest triangles and these areas will be the most densely populated areas that the humans should place defensive structures.

Back in my first job, in fact the 2nd project in my first job, I had to create a Voronoi diagram generator to calculate the center-line of lakes and river polygons for some GIS technologies. That was years ago, and although the code was open source, the company that we contracted too took it and ripped out our names and hid the source. Bummer. I didn’t want to write it again. So I searched for another Java solution to it, and voila, found one: The Delaunay Applet by Paul Chew. This app does everything I need and more. Along with Voronoi Polygons and Delaunay Triangulations, it also can generate circles from the circumcenter of the triangulation. These circumcenter points are the exact place where I need to place defensive structures and the circle radius tells me how dense that location is. Sweet!

Here’s a quick look at the code.

Triangle initialTriangle = new Triangle(new Point(-2000, -1000), new Point(2000, -1000), new Point(0, 3000));

Triangulation dt = new Triangulation(initialTriangle);

for (Vector3f buildingLocation : all.keySet()) {

// for each human house or building

dt.delaunayPlace(new Point(buildingLocation.x, buildingLocation.z)); // place point

}

// all done adding points, now lets find the smallest circles

for (Triangle triangle : dt) {

Point c = triangle.getCircumcenter();

float radius = (float) c.subtract(triangle.get(0)).magnitude();

// test to see if it is a small radius

// place a defensive structure there

}

Pretty darn easy!

Here is the code in action in AotGB:

voronoi-circles

The red circles are the dense areas.

The code is open source and free to use; no particular license to it. I highly recommend trying it out. And if you aren’t using java, port it over. It will be much easier than writing your own Fortune’s sweep-line algorithm, trust me 😉

Leave a Reply

Your email address will not be published. Required fields are marked *


7 − one =