Blobs in Games: Polygon Map Generation, by Amit Patel

Hi Nodename! Thanks for the link, and kind words. You’ve noticed that I made minor changes to your library. Here’s the background:

The interface for the Voronoi class is essentially: first, give it points, and let it do its work; then, for each point get back the Voronoi region, or the Delaunay neighbors. There are other methods I didn’t use because I wanted to use the abstract Voronoi data without graphics-specific stuff (colors, bitmapdata, drawing routines, etc.).

In as3delaunay there’s a color per region. I needed much more. For the map project I want to associate a lot more data with each region, edge, and polygon corner:

* each region has an elevation and moisture
* each region also has a ‘biome type’ (desert, forest, lake, etc.)
* some edges are rivers, and have added attributes like water volume
* some edges are roads, and have added attributes
* some edges are coast/beach, and divide ocean and land regions
* polygon corners have elevations for the 3d view and water flow algorithms

For that data I need to have the same polygon corner object for all the regions that use it, instead of having a new one per region. That way I can have only one elevation etc. per corner and never have discrepancies.

I also want the relationships between these:

* for each region, which N edges touch this region?
* for each region, which N corners form this region?
* for each polygon corner, which three edges are connected to it?
* for each polygon corner, which three regions are touching it?
* for each edge, which two regions does it divide?
* for each edge, which two corners does it connect?

My solution for both of these is that I take the output of the Voronoi class and form my own structure from it. I assign an int index to each region, edge, and corner. I can then create an array with additional data and use that int to index into it. I also calculate all 6 relationships (region→edge, region→corner, edge→corner, edge→region, corner→region, corner→edge). The as3delaunay library has a lot of this internally but doesn’t expose it. To recover this data I had to make your Edge class public. (The code is the buildGraph method.)

I think this interface is much more general than returning the points and line segments alone, and it separates out drawing from representation. With the int index whoever’s using the library can associate arbitrary data with any part of the geometry, and even better, multiple add-on libraries can keep their own associated data without stomping on each other. The relationship data includes the Voronoi regions (region→edge) and the Delaunay triangles (corner→edge), plus many other useful mappings. However the added indirection of the indices is less convenient for many uses of a Voronoi library.

I wasn’t planning to make this structure; it just sort of emerged as I worked on the project. Unfortunately I never generalized it to put it back into the as3delaunay library. There are still bits and pieces that are specific to the map project; you can see them in the graph/ directory.

Thanks again for as3delaunay! It was the best of the Voronoi/Delaunay libraries I had found for Actionscript. I hope the above explains why I made the change, and why I built a wrapper around your interface.