Voronoi terrain generator breakthrough!

Just had a nice breakthrough with a terrain generator I’m working on. It’s based on voronoi polys. The approach is outlined in this article: http://www-cs-students.stanford.edu/~amitp/game-programming/polygon-map-generation/

The breakthrough is that I finally managed to get a java implementation of Fortune’s algorithm working. This algorithm is a super fast way of generating the polygons. Anyways, here’s a visual; both the delaunay and voronoi polys are outlined (just using regular pseudo-random numbers here tho).


When it comes to implementation, I think I’m gonna tesselate the map similar to how he does it in the article, and use noise for the heights. It’ll probably be best to create heightmaps out of the graphs & noises, rather then creating meshes out of the triangles. That way the terrain can be divided up into regular TerrainQuads, while the graphs are stored and used for all the other stuff (generating roads, rivers etc.).

There will probably be some terrain images posted later.



You should have mentioned this earlier, I could have pointed you to an open source java voronoi tool I made years ago. It is a fun algorithm though, good learning experience, and has really useful results. You can use this for path generation for AI as well.


Nice work :slight_smile:

Thanks. I’ll upload something sometime I suppose, when it’s working better.

And yes I definitely should have asked first. This code is made from a web applet. Had to clean it up a lot (used arrays of doubles as vectors, among other things).

Can’t remember what it was named tho, I think i googled “voronoi generation script” or something like that. It was high up on the list.

1 Like

COSC 6114 Computational Geometry - Zhenyu Pan

That’s all i find. Gonna find the link.

1 Like

ug the app is gone! wtf, all that work and it’s gone off of their site.

It was a plugin for JUMP, a GIS app. Did some nice voronoi stuff and was open source.

I think OpenJUMP (a fork of the Jump project) has some voronoi capabilities however. But yours is built already and works with JME, so it is 100x better now :slight_smile: