2

Is there a design pattern or well known algorithm to build a simple map with roads and city blocks?

To have an idea of what's my target i describe some of the constraints and the context:

  • a matrix which represents a (rectangular) map
  • few possible city blocks represented as rectangles (eg, 4x3, 5x2, 1x6)
  • few possible road sizes (eg, 1, 2)
  • block are never connected, meaning that there is always a road between them

the result would be an array like this:

111101111100110
111101111100110
111100000000110
000001110000110
000001110000000
...

where as for example, "1" are the blocks and "0" are the roads.

What I intend to do is to place a block where it is possible, then circumscribe with roads, and go on. This would be ok, but could lead to some place where blocks don't fit.

I would like to know if there is something in the state of the art of such algorithms.

  • Did you search for the knapsack problem? To me it sounds like a 2D variant of it. – valenterry May 10 '14 at 20:54
  • This makes me think! I feel there is a linear solution out there even if the one I implemented is not ok maybe just because doesn't make a tree search of fitting blocks and let some islands here and there. ty!! – donnadulcinea May 11 '14 at 9:29
2

Most algorithms will come up with a randomly generated map purely based on a seed. It would never evaluate the map, and therefore not guarantee a nice user experience.

Since you have mentioned that you would like to build a "state of the art" map generator, the first thing that comes to my mind is genetic algorithms. Such an algorithm would create many different maps, based on an underlying gene combination. With each iteration, every map would be evaluated and improved. (the gene pool can be the exact same representation as your matrix above - what's even nice about this is that you will not have such a block city effect - unless that's what you want, then you can code it that way too).

In order to implement this, all you would need is an evaluation algorithm (for any given map). If you can come up with such an evaluation algorithm and you let this map-generation process run through a couple of iterations/evolutions (e.g. 100), you would end up with some really cool maps.

An evaluation algorithm (fitness) would consist of something like:

penalty = how many roads are too close to one another +
how many cities are too close to one another

I have simplified the formula above, it should be a bit more like: the sum of how close each city is to each other city + the sum of how close ... etc

then fitness = 1/penalty

I did a quick search on: "genetic algorithm & map generator" and came up with some results that claim:

"In this paper we introduce a procedural map generator for a real-time strategy (RTS) game. The main component of this generator is a genetic algorithm devoted to create and evolve balanced maps, i.e. maps where no player has any map related advantage with respect to other players."

http://www.lcc.uma.es/~raul/pubs/procedural_map_generation_for_a_rts_game.pdf

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.