2
\$\begingroup\$

My friend started to make a 'country-generator' type of thing. We have some starting points, and we want to 'grow' countries from them randomly until the whole area is filled. What's is an effect effective way to create something like this?

This is an image of a desired possible end result: What I want

\$\endgroup\$
3
  • 1
    \$\begingroup\$ You can have a 2d grid with cells that merge to represent growth. Merging can convert the type of neighbour cell to itself. Most effective way would depend on what you want to achieve after that. \$\endgroup\$
    – Kogesho
    Feb 5, 2014 at 22:38
  • \$\begingroup\$ Do you need the end result only? \$\endgroup\$
    – AturSams
    Feb 5, 2014 at 22:39
  • \$\begingroup\$ yes, I need the end result only \$\endgroup\$
    – Rothens
    Feb 5, 2014 at 22:40

2 Answers 2

5
\$\begingroup\$

Here is the general algorithm that could be used to achieve a similar result:

Let N be the number of countries you wish to have

  1. Randomly pick N^2 points on the 2D plain.
  2. Create the Voronoi diagram to split the plain into N^2 cells.
  3. Use Union Find between 2 random neighboring cells (that are on disjoint sets) N*(N-1) times
  4. Use the newly created trees of cells as the countries' polygons.
  5. Apply a wave / noise filter to get the fuzzy look you desire.

You can play with Voronoi here:

http://blog.ivank.net/voronoi-diagram-in-as3.html

Learn how to apply apply noise here (to make the cells less rigid):

How do I make a natural-looking map from some Voronoi regions?

\$\endgroup\$
3
  • \$\begingroup\$ yeah, Voronoi diagrams came into my mind too. I was just curious if is there any other methods. Oh, and if you look at the 'white' country, I think you can't achieve that with a Voronoi diagram. But maybe I am wrong \$\endgroup\$
    – Rothens
    Feb 5, 2014 at 23:02
  • \$\begingroup\$ Alright, I'll change my answer to allow the white country. ;) \$\endgroup\$
    – AturSams
    Feb 6, 2014 at 11:12
  • \$\begingroup\$ Oh, I love this! I'll try to implement it :) Thanks ;) \$\endgroup\$
    – Rothens
    Feb 6, 2014 at 12:25
4
\$\begingroup\$

For a 2D grid, like in the image you posted.

While probably not the most efficient in terms of speed and memory usage, I find that a brute force approach could still be useful, since it's easy to get it started. Especially if this is not to be used in places with time or memory constraints.

//Get some random cells for countries to start extending from.
for each Country in Countries
  Cell unoccupiedCell = Map.GetRandomUnoccupiedCell()
  Country.OccupiedCells.Add(unoccupiedCell)
  unoccupiedCell.occupier = Country
end for each

//Extend each country at random
while Map.UnoccupiedCells.Count > 0
  for each Country in Countries
    Cell unoccupiedCell = Map.RandomUnoccupiedCellInVicinityOf(Country)
    if (unoccupiedCell exists)
      Country.OccupiedCells.Add(unoccupiedCell)
      unoccupiedCell.Occupier = Country
    endif
  end for each
end while
\$\endgroup\$
4
  • \$\begingroup\$ This looks good, but can you expand on what Map.UnoccupiedCellInVicinityOf() does? I'd guess it picks a nearby cell near the Country that's passed in, but how does it determine what is "in the vicinity of"? \$\endgroup\$
    – fnord
    Feb 5, 2014 at 22:57
  • \$\begingroup\$ Changed to RandomUnoccupiedCellInVicinityOf. Basically, goes through the unoccupied cells that are near cells that were previously occupied by the current country, and selects one at random. This extends the current country's border by one cell, at a random position on its current border. \$\endgroup\$
    – user15805
    Feb 5, 2014 at 22:59
  • \$\begingroup\$ Referring to your edit: for each Cell in CellsOwnedByCountry(Country) Vicinity.Add(UnoccupiedNeighborsOf(Cell)) <-- that's the set of cells that are in the vicinity of Country, and are unoccupied (you select one at random from them). \$\endgroup\$
    – user15805
    Feb 5, 2014 at 23:02
  • 1
    \$\begingroup\$ That's not what I would call a brute-force approach. To me it resembles a "cellular automaton" approach, and that's the way I would have done it. Here's a tip: each country must keep stored somewhere the set of all the cells that are at its border, in order for RandomUnoccupiedCellInVicinityOf to be computed easily. The way to manage that set is to go through each border cell at each step, and if that border cell is surrounded by cells wihin the country, then it's not a border cell anymore! Also everytime you add a cell to the country, it becomes a border cell, including the very first cell. \$\endgroup\$
    – jrsala
    Feb 7, 2014 at 12:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .