Mapping/Random map assembly/Algorithm
From UFO:AI
Random map assembly algorithm
This algorithm was made by Gerd Heiße. Below is his description of how it works:
Update: I committed some changes to the random map assembly code recently. The new code does not check all possible tile placements systematically, because this takes much too long - something I had to learn ...
Such a systematically approach is only implemented for the mandatory tiles, the other tiles are chosen by randomly testing some possible tiles at random positions, calculating a rating value for each placement and selecting the best one. This is done until the map is filled. If the algorithm comes to a dead end, it falls back to the mandatory tiles and start with the next possible placement of these tiles. The rating of a placement is done in the following way:
- 0 points for an empty field
- 1 point for an filled (solid) field
- -N points for a field with connection information, where N is the number of adjacent tiles
The idea behind this is to prevent isles and holes in the map assembly process and to prefer larger tiles in the beginning. I made good experiences with this solution, but for some maps (i.e. village big) it takes up to a minute in bad cases. From my point of view this algorithm works better than the former one, but it is not a big problem to go back to the other code if it leads to problems (only one file involved).
The current changes in code have some other consequences:
- The assembled maps are built from more larger tiles than before. So we should do some fine tuning in the ump files if there are too much tiles of one kind.
- The algorithm now uses bit logic for quicker connection tests. Because of this the possible connection characters are reduced to 31. The numbers 6...9 are not available anymore. The only valid characters are now: '+', '0' ... '5', 'a' ... 'z', 'A' ... 'Z'.
A note about the release: I think we should simply deactivate or comment out the big village map and other maps which need more then a few seconds for assembly. One possibility to achieve better assembly times is to use larger tiles and more complete tile sets (i.e. the village tile set has only two street corners from four possible).
