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\$
  • 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 '14 at 22:38
  • \$\begingroup\$ Do you need the end result only? \$\endgroup\$ – AturSams Feb 5 '14 at 22:39
  • \$\begingroup\$ yes, I need the end result only \$\endgroup\$ – Rothens Feb 5 '14 at 22:40
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?

| improve this answer | |
\$\endgroup\$
  • \$\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 '14 at 23:02
  • \$\begingroup\$ Alright, I'll change my answer to allow the white country. ;) \$\endgroup\$ – AturSams Feb 6 '14 at 11:12
  • \$\begingroup\$ Oh, I love this! I'll try to implement it :) Thanks ;) \$\endgroup\$ – Rothens Feb 6 '14 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
| improve this answer | |
\$\endgroup\$
  • \$\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 '14 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 '14 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 '14 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 '14 at 12:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.