Holger Doessing
Denmark Odense

I am interested in creating a map that looks like a Voronoi diagram, although with a few caveats. I am not even sure if this is at all possible, but I would like to hear any mathematicians out there if you know of a software solution that will allow me to tweak the algorithm thus:
I want each cell to at least try and adopt certain size. Specifically, I want to avoid having cells of e.g. size (area) 1.41.6. Instead, I want the sizes of the cells to be closer to ~1 or ~2. If a cell is ~1.5, the algorithm should automagically shrink/enlarge the cell and its neighbors to make it closer to either 1 or 2. Very small cells might even be absorbed by neighboring cells.
I would like every side to have a minimum length. If a side does not have the proper length, it should be collapsed with another side. (This is less of a requirement; I can probably manually tweak the resulting chart to accomplish this.)
As you can see, I want to ensure that the resulting cells make up a playable board where the cells have reasonably sized borders and are either single or double (or triple etc.)sized. I understand that the resulting chart will probably no longer be a true Voronoi diagram. I also understand that I could do this manually e.g. in Illustrator, but I think especially #1 will be tedious to achieve by hand.
Any help is much appreciated!

Jeremy Lennert
United States California

You've talked about some ways you want it to be different from a Voronoi diagram. In exactly what ways do you care about it being similar to a Voronoi diagram? Why did you select that as a starting concept, and what properties of Voronoi diagrams do you care about preserving?
It may be worth noting that a regular square grid (e.g. a chessboard) fulfills all of your listed requirements so far. It actually is a Voronoi diagram (for one particular set of points), and all the cells and borders have consistent size.

Andrea Nand
Italy Modena
Best. Game. Ever.
I wrote nanDECK and BGG1tool

I've fastly assembled a test program (maybe it's something I can include in nanDECK). Before thinking about your points (1) and (2), a couple of questions:
 how the dots (and the colors) for each area are chosen? Random or input?
 the distances between the points can be calculated in two manners, which do you prefer?

Holger Doessing
Denmark Odense

Thanks for your replies!
Antistone wrote: You've talked about some ways you want it to be different from a Voronoi diagram. In exactly what ways do you care about it being similar to a Voronoi diagram? Why did you select that as a starting concept, and what properties of Voronoi diagrams do you care about preserving? I am currently exploring a city building mechanism, and I very much prefer the random feel of a Voronoi board to, say, a grid or a hex board. It gives the cities a much more organic look, and since the cells have different sizes and numbers of neighbors, the growth pattern itself is very dependent on e.g. where you nucleate from. The resulting cities look more like old European cities than modern NSWE gridbased cities, and I think it provides more and better decision points.
The downside is that the Voronoi diagrams I've seen so far typically have : (a) cells of nondiscrete sizes (I'd like the cells to be immediately recognizable as capable of haboring e.g. 1, 2, 3, or 4 buildings) and (b) cells with too many neighbors (for instance, the pink cell in Andrea's first chart above would probably be better usable as a game space, if its shortest side was scrapped in favor of clearly making it a trapezoid with 4 neighbors). I could certainly fix the latter issue in Illustrator, so my main problem is that I want the cells to be (close to) 1 of 4 different sizes. There are Illustrator plugins that will calculate the area of an object for me, but ideally I'd need a solution that would overlay this live info on all the cells and update it whenever I change anything on the artboard, and I've never heard of something like that. Hence, I'm asking if there's an automated solution for customizing the Voronoi diagram.
n_and wrote: I've fastly assembled a test program (maybe it's something I can include in nanDECK). Before thinking about your points (1) and (2), a couple of questions:
 how the dots (and the colors) for each area are chosen? Random or input?
 the distances between the points can be calculated in two manners, which do you prefer? I imagine that it would be better to have usergenerated input (although also more tedious to program and to use), because it would allow me to try and 'fix' small portions of the map that I wasn't happy with. I was thinking of supplying a coordinate text file or perhaps an image.
As for the distance calculations, I am definitely looking for something like your first diagram (ID 2887363). Pointy is good; it makes it much easier to quickly assess how many neighbors a cell has and it leaves room for game tokens on the cell borders themselves.

Jeremy Lennert
United States California

holgerd wrote: I very much prefer the random feel of a Voronoi board to, say, a grid or a hex board. It gives the cities a much more organic look, and since the cells have different sizes and numbers of neighbors, the growth pattern itself is very dependent on e.g. where you nucleate from. The resulting cities look more like old European cities than modern NSWE gridbased cities, and I think it provides more and better decision points. It sounds like there are NO rigorous mathematical properties you care about, and instead are interested in the general aesthetics of certain particular examples of Voronoi diagrams that you have seen.
You should seriously consider the option of just sitting down with a pencil and drawing a map based on your imagination. It is quite possible that will be faster than trying to use a computer program, and it will definitely require less in the way of technical skill.
If you want to make a computer program to generate the map, then you need to take your list of requirements (like "each cell is one of these wholenumbered sizes") and somehow turn it into an algorithm (a set of detailed, stepbystep instructions) for producing maps that meet those requirements.
If it were me, I might try something along these lines:
Core Idea: As in a Voronoi diagram, choose several points to be the "heart" of your regions. However, instead of simply measuring distance to each point, imagine that you positioned a tube of differentcolored toothpaste above each point, and then squirt them all out at the same time, so that each color spreads out from its point in a circle until it runs into another color, and then it flows faster in the remaining, open directions until you've emptied the entire tube.
Larger regions start with larger toothpaste tubes, which squirt out proportionately faster.
Details: Define an extremely fine grid (e.g. the individual pixels on your computer screen). This grid starts out blank.
Choose your "heart" points for each region by placing them somewhere on that grid. Also assign a size to each heart indicating how big you want the region to be (e.g. 1, 2, or 3).
Color each heart's starting point with that heart's color.
Then, begin a loop: consider each heart one at a time.
For that heart, consider all of the blank gridsquares that are touching a square of that heart's color. (Initially, this will be the squares adjacent to the heart's starting point.) Out of all of those squares, choose the one that is closest to the heart's starting point. Color that square with the heart's color.
If the heart has been assigned a size greater than 1, do that a number of times equal to the size. (e.g. for size 3, color the three closest options, instead of just the single closest option).
When you're done, you should have a very tiny dot of color located under each heart, while most of the grid will still be blank.
So, repeat: go over every single heart again, one at a time, and give it another grid square (or squares equal to its size).
If a heart has no contiguous options (i.e. there are no blank squares left that are touching that heart's color), then skip over that heart, but keep processing the remaining hearts. Keep going until none of the hearts have any space left (which should only happen when the entire grid is filled).
Have a human being take a look at the result. If it seems basically good, copy it down, and make manual tweaks until it's perfect. It it doesn't look good, start over from scratch with a new random seed.

Andrea Nand
Italy Modena
Best. Game. Ever.
I wrote nanDECK and BGG1tool

You can download this 1st version from here:
http://www.nand.it/files/voronand.zip
In the right box you can insert the coordinates of each point, I've used percent values, so they are indipendent from the resolution (for example, 50,50 is the center of the screen), the 3rd parameter is the color (if you omit it, a random color is chosen).
You can also insert a 4th parameter, a factor that is multiplied to the distance from that point, for example, a number less than one grows the area:
And a number greater than one shrinks the area:


