HoMM V Unofficial Random Map Generator
by Tapani Utriainen, 2006-10-31
Installation and usage
The installation is simple, just download the zip-archive and copy the files inside anywhere on your computer. It does not matter where they are, and no separate installer is needed.
Download link: Tapani's HOMM V Unofficial Random Map Generator v1.05
The RMG will create a map file and place it in Heroes data directory so the game can find it. By default, the map files are called in lines of "Random_Map_XYZW.pak", but it is possible to change the name and location by using the Browse button. The odd-looking code at the end of the filename (i.e. XYZW) is a timestamp to keep different random maps apart. The code is chosen in a way that the newest map generated will appear on top when selecting a map in the game.
Those having some other version of the game than the European one, the map generator will attempt to place the maps in the default installation location ("C:\Program Files\Ubisoft\Heroes of Might and Magic V"). If that fails, you are supposed to get a save file dialog so you can specify where to place the map. (However, this has not been tested :-)
To summarize the installation and usage:
- Copy the files anywhere
- Create a map
- Launch the game, and select the random map on top
Note: The game will only look for new maps on startup, so you need to restart the game after you have generated a map.
Options
When launched, the generator will show a dialog like this:
The easiest hands-on way of getting a grip of the various options is to generate a few maps, and to look at them in the map editor. In order to load a generated map into the map editor, you can place the map in the Maps folder and save the map as a h5m file (both the folder and file type can be changed using the Browse button). Alternatively, you can generate the map, and then point the map editor to the data directory and load the pak file (pak, h5m and zip files are the same, just named differently).
Map size
Obviously this controls the size of the map. Even if the generator is able to generate larger maps than default, it should be noted that anything larger than 216x216 is likely to take quite some time to generate, even hours. The number of areas generated increase with map size.
Monster strength
It is hard to explain what the monster settings indicate. The best way to get an idea is to generate a map and see if you like the results (using the map editor for instance). Roughly one can say that an expert player should not play anything less than very strong, and playing hairy or higher is not recommended for anyone not considering themselves an expert. The omfg setting is not recommended for anyone :-)
On hairy and higher you need to get past throngs or swarms (or even zounds) of upgraded level 7s. As an example, our last game had monsters set somewhere between hairy and extra hairy, and we had to go through 600 black dragons as the fattest border guard. (We play on heroic only, and the monster stacks grow 11% every week - so any stack will get huge with time).
Richness
Controls the amount of treasures, resources, artifacts on the map. Settings higher than normal has not been tuned, and might give bizarre results.
Regardless of richness setting, all players are guaranteed a sawmill, ore pit, windmill and a dolmen in the starting area, as well as a few basic resources (a pile of gold, ore and wood). On some of the higher richness settings some additional mines might appear in the starting area.
Fairness
- Basic fairness: Means that both players receive similar objects in the starting areas, isomorphic map halves with the same amount of towns and mines and some similarity of objects in the areas. For instance if you find an area with a few marletto towers, an arena and a crystal - chances are that your opponent has got at least some stat improving buildings as well in an equivalent area. Not the same ones though, and probably not even equally many.
- Advanced fairness: Both players receive same guards in front of the key objects in the starting area (wood and ore mines, windmill, ...), and equivalent border guards.
- Expert fairness: Tries to achieve millimeter justice. Both players receive the same objects and guards in all areas. Artifacts are an exception, only the same "rarity" (i.e. major, relic, etc.) is guaranteed.
Terrains
Used mainly for looks (anyone seen an inferno castle on grass knows why :-). Recommended choices are:
- Inferno: lava
- Necropolis: lava (or dirt)
- Dungeon: dirt
- Sylvan and Haven: grass
- Academy: grass (or sand)
Mostly, we have been playing 216x216 maps, hairy to extra hairy monsters, very poor or poor richness using heroic difficulty. Therefore those settings are the ones that have received most tweaking. Also note that playing with necropolis can result in raising of truly bizarre amounts of skeletons on these maps.
How it works (Algorithm description)
The algorithm that creates the maps is essentially the same as the one Gus Smedstad described for Heroes 3. It works using the concepts areas (i.e. zones) and connections (i.e. borders). The generated maps will consist of smallish areas and neutral monsters guarding the passages between these areas.
1. Random graph
In this phase a random graph is created for describing the areas and the connections between them. Only half of the graph is randomized, the other half is a copy of the other - thus guaranteeing that the map is divided into two graph isomorphic (i.e. similar) halves. The randomization is done in a way that makes it likely for the shortest path between the starting areas to be quite long.
This abstract graph representation is roughly the information stored in for instance HoMM 3 random map templates. For instance, the map after this stage is like:
- Area 0 is connected to Area 1
- Area 1 is connected to Area 0 and Area 2
- Area 2 is connected to Area 1
...and so on.
2. Planar embedding
In this phase the graph representation is planarized. The nodes in the graph represent area centers, and they are to be placed onto the map in a way that connected areas end up beside each other. No teleporters should be necessary. This is the phase that takes almost all of the time when generating maps.
For all the computer scientists out there: this problem is equivalent to a planar embedding of a graph with distance constraints. The distance constraints are that any two connected nodes should be placed reasonably close to each other (for instance the distance should be between d and 2d, for some constant d). Any ideas on how to do this in a fast way would be appreciated.
The result after this planarization phase looks roughly like the figure on the right. The circles represent areas, lines connections between them, the colours indicate who's map half the area belongs to and the double circles indicate a starting area.
3. Voronoi partitioning
Once the area centers are placed on the map, the tiles on the map are assigned to belong to the area that has its center closest. This type of partitioning is called a Voronoi partitioning (or Delaney tesselation).
To be picky, in order to do a quicker (dirty) partitioning and to create a bit more irregular areas, another norm than the normal Euclidean metric is used. (The norm used is a p-norm with p=1/log2(1.5), each tile can be assigned in O(1)).
All areas and their tiles are assigned a terrain, and the area boundaries are raised a bit. Water is placed where the closest area center is sufficiently far away.
4. Object placement
In the last phase objects and guards are placed. First the borders are filled with mountains and stones, then the areas are filled with objects. Each triggable object is placed as far away from the closest triggable object in the area. (Implemented by an incremental multi-source Dijkstra. By using the same peculiar norm as in the Voronoi partitioning, this has at least a logarithmic factor faster worst case than an ordinary Dijkstra). The reachability of placed objects is preserved by making sure that no new object placed can block access to already placed objects. (This is done by traversing the Moore-contour of the new object, for a valid placement, the contour can touch an obstacle at most once).
As a final step, monsters are placed to guard every triggable object. The strength of guards and border guards depend on the number of borders they are away from the nearest home town and the distance between the home castles. For instance, if the distance between home towns is four borders, then each border is worth 0.25. This way the biggest neutral encountered will be roughly the same for each monster setting regardless of the size of the map.
In case of any failures (like objects that could not be placed), the process is restarted until the map generation succeeds. If the planarization fails, which it often does for the larger maps, the generator will randomize new graphs and attempt to planarize them several times until it succeeds.
Future
Since the Hammers of Fate expansion has been announced to contain an official RMG, any further development of this RMG will have to wait until the expansion is released. In the case the official RMG cannot produce good maps or is messed up in some other way, some interesting features to add would be:
- Multi-type guards - that is having garrisons between areas containing several different troop types.
- More than two players - like 2v2 or even using HoMM 3 RMG-templates
- A better (i.e. faster) planarization algorithm
- Progress bar, Abort button, ....
It is also possible that there are bugs in the maps, and fixing those are always a necessity.
You can discuss this RMG with the Heroes Community.
Thanks to Tapani for creating the tool and this page!