Territory Map Generation

Question

Is there a trivial, or at least moderately straight-forward way to generate territory maps (e.g. Risk)?

I have looked in the past and the best I could find were vague references to Voronoi diagrams. An example of a Voronoi diagram is here.

These hold promise, but I guess i haven't seen any straight-forward ways of rendering these, yet alone holding them in some form of data structure to treat each territory as an object.

Another approach that holds promise is flood fill, but again I'm unsure on the best way to start with this approach.

Any advice would be much appreciated.

Answer 1

Why not use a map of primitives (triangles, squares), distribute the starting points for the countries (the "capitals"), and then randomly expanding the countries by adding a random adjacent primitive to the country.

Answer 2

The best reference I've seen on them is Computational Geometry: Algorithms and Applications, which covers Voronoi diagrams, Delaunay triangulations (similar to Voronoi diagrams and each can be converted into the other), and other similar data structures.

They talk about all the data structures you need but they don't give you the code necessary to implement it (which may be a good exercise). In terms of code, an Amazon search shows the book Computational Geometry in C, which presumably comes with the code (although since you're stuck in C, you'd mind as well get the other one and implement it in whatever language you want). I also don't have any experience with this book, only the first.

Sorry to have only books to recommend! The only decent online resource I've seen on them are the two Wikipedia articles, which doesn't really tell you implementation details. This link may be helpful though.

Answer 3

Great answers. I think I'll look into that book. I think the primitive idea is abstractly the same as a flood fill and sounds an interesting approach.

Answer 4

CGAL is a C++ library that has data structures and algorithms used in Computational Geometry.

Answer 5

I'm actually dealing with exactly this kind of stuff for my company's video game. The most useful info I've found are at these two links:

Paul Bourke's page at UWA, with his 1989 paper on Delaunay and a series of implementation links.

A great explanation of the psudocode and a visual of doing Delaunay at codeGuru.com.

In terms of rendering these - most of the implementations I've found will need massaging to get what you'd want, but since using this for a game map would lead to a number of points plus lines between them, it could be a very simple matter to do draw this out to screen.