The placement of terrain tiles is now implemented fully:) From a technical side of view this requires updating terrain view and terrain type. With the newest SVN revision the final part updating terrain type is observed as well. If you place a single terrain tile grass on water for example, the editor adds three more grass tiles around it. This is one situation among others of updating additional terrain tiles. I think my algorithm performs better than the original from NWC as the original produces sometimes unpredictable results. My algorithm tries to find the minimum tiles which have to be updated, but it is slow currently.
So, now the really interesting part of the RMG begins, the generation of terrain. I have downloaded a few interesting papers on that part and I’ll read them the next days. The RMG is my student research project and therefore I have to compare a few approaches on terrain gen. The original algorithm of NWC seems nice, but we’ll see if there are any better solutions. I’ll post a plan soon, so you can participate on the way how terrain will be generated:) I have time till end of may, then I’ll write the dissertation. So we should move on quickly:)
First, I want to say some organizational things. I’ve divided this post into two posts. The first post lists possible map generation techniques and the second post says how we could generate a map in my opinion. The list is kept as a reference and may be incomplete. In the first post, I’m talking about generating content, you can replace it with generating maps if you want.
Some techniques to generate content randomly discussed here and the terms to classify those techniques are based on the following paper: julian.togelius.com/Togelius2011Searchbased.pdf I advise to read it, it’s very interesting.
Terminology Online vs. offline generation
Online generation means generating content during execution of the game, whereas offline generation means generating content during development of the game. Online generation needs to be fast and reliable, whereas offline gen can take more time producing sth. which may be incomplete and needs additional manual work.
Necessary vs. optional content
Necessary content is a content which is required to play the game, whereas optional content is unsurprisingly optional and doesn’t affect the completion/playability of the game.
Random seed vs. parameters
Random seed means that the generation of content depends only on a single random number, whereas parameters means that the generation depends on additional parameters. Parameters can serve as constraints to the generation process. Some sort of parameters are necessary if you want to have more control over the generation e.g. number of zones, distribution of resources,…
This image shows a rough overview of techniques which I want to discuss in more detail. There are three distinctive ways to generate content randomly: The constructive generation, the simple generate & test method and the search based generation. It should be said that a mix of many techniques can form the complete solution to generate content e.g. search based and constructive gen can be used hybrid.
Constructive generation:
Constructive generation means to generate content with a strict set of contraints and rules whereas the result is not validated or modified afterwards. This technique can be hard to control or to optimize. It is likely that more control means less interestingness or diversion of the generated content.
The following is a short list of constructive generation methods and their usage scenarios. I don’t want to explain any method further, it would take too much time.
Diamond-square, Midpoint displacement -> Generate roads, rivers, …
“Random grow” (I couldn’t find any term describing these technique) -> Generate isles,…
Software agents -> Generate maps,…
Voronoi diagrams -> Generate maps(terrain),…
Markov-chain -> Generate player names,…
Generate & test:
Generate and test means constructive generation plus a validation at the end of the generation. The validation either accepts the generated content or rejects it.
Search-based generation (in short: SBPCG, search-based procedural content generation):
Search-based generation is a specific form of generate & test and a relatively new research field(2007). It doesn’t simply accept or reject the content but tries to improve the content by using evolutionary algorithms for example. The SBPCG generates several individuals and tries to form new individuals by combining good properties. Survival of the fittest is used to retain only the best individuals.
I want to explain three fundamental things when using SBPCG:
Creation of a genotype. A genotyp represents a “compressed” form of the generated content and consists of real numbers for example. The genetic algorithm performs on the genotype.
Conversion genotype to phenotype. The phenotype is the “decompressed” form of the generated content and can be the representation of the content used in the game. The evaluation performs on the phenotype. The conversion genotype - phenotype can be direct, partially indirect or very indirect. Indirect means more work is required to “decompress” the genotype. Indirect: Genotype consists of number of zones, number mines, … only. Constructive gen is needed to convert genotype to phenotype which includes positions of zones, mines,… Keep in mind, the concept of locality. A small change in the genotype should result in a small change in the phenotype.
Evaluation of the content e.g. distance starting towns, distribution of resources, choke points,…). It is possible to rate the content with 1 function from 0(bad) to 1(good), but multiple ratings are possible as well. There are single-objective and multi-objective genetic algorithms.
Two more things are important, the search space and the evaluation function. The search space is the space where the genetic algorithm searches for better genotypes. Is it too small, probably not all possible solutions including interesting ones aren’t found. Is it too huge, the algorithm doesn’t find any valuable solution or the algorithm takes too much time.
The map generator is a online generator therefore it needs to be fast and should produce good quality maps. Maps produced are optional, so they don’t need to be perfect always. The generator uses some sort of parameters. The original H3 generator uses a mix of templates and parameters given by the user.
My idea is to use a hybrid approach of constructive generation and SBPCG to generate maps. SBPCG is used to generate the overall picture of the map. This includes the major parts of the map: Zone placement, terrain placement, town placement, mine placement, obstacles. That points are subject of the evaluation functions. This makes sense because a map is incomplete in terms of playability if the evaluation only looks for town placement for example. I don’t want to go into details for now, but every part needs some sort of constructive generation as well. In OH3 templates are used to define constraints for the map generation. Otherwise maps could be completely random resulting in unbalanced maps. With SBPCG we don’t need templates and can have even more control on the generation process while keeping it possible to generate asymmetrical, balanced and interesting maps. Nevertheless even with SBPCG we need some contraints(things which should never happen) to avoid noise for the genetic algorithm. In addition, SBPCG can solve the zone placement problem. But things don’t come without any cost. The search space and the evaluation functions need to be chosen carefully to have a moderate performance.
I know this is very very general, but I don’t want to invest time in things which don’t go into the right direction. If it’s fine, then I can write a concept how the genotype, phenotype and the evaluation functions could look like in Heroes 3/VCMI. I have approx. three weeks left and I think basic town & terrain(zone) placement can be done even with the use of SBPCG. If it doesn’t work out, we can choose to use the classic approach with templates. It would be nice to give it a try at least.
I think templates are not just another way to find map outline, hey are fundamental constrain essential for balance. Players use templates for online games to preserve balance, equality and predictability of generated maps. The name of template is the very first info players give when they describe the random map or game. I’d even say that compliance with templates is essential goal and should be kept even for cost of map quality. It’s better to have 100% coverage of zone boundaries, connections and guards that to have interesting boundary shape or road placement, for example.
Also, I think you put wrong page under second link, it’s same as 2.
As Warmonger said, templates are important for some players. Maybe you could just use SBPCG to generate (saveable, user-modifiable) templates used for further stages of map generation? You could of course invent your own template format.
Ok, thanks for your responses. Warmonger, I completely agree with the fact that online gamers want to have maps with symmetry, equality and balance. This is indeed a problem with SBPCG, most notable the problem of generating symmetrical maps.
Wow, that’s a really interesting idea. I think with semi-generated templates(templates generated by SBPCG and/or hand-edited) we could both generate symmetrical and balanced maps while also having asymmetrical and near-balanced maps. I’ll use a JSON format for the templates which is more user-friendly than the plain text files.
PS: To keep things simple, I’ll start with manually created templates to generate maps. I’ll post the basic templates format in the next days… Then, we will come to the next question: How much degree of control do we want to have?
Where is the problem in generating SBPCG maps that are based on templates? Genetic algorithms or swarm intelligence should suit graph planning nicely, as far as I know. If you find partitioning of zones difficult, it can be always generated with different algorithm. The main interest of SBPCG is to fill specific zones with treasures or just obstacles to begin with.
From what I have seen in OH3 maps generated with the same template are non-deterministic and not symmetrical, but pretty good balanced. So, even if the template is the same the map will be different to a certain amount, while keeping it predictability to a certain amount for online gamers. This is interesting, the template gives relatively little info about the generated map. The template holds info mainly about the rough structure, the map zones. The arrangement, the positions of the zones, how and where the objects & obstacles are placed in the zone is not specified. To conclude, on the one hand MP gamers want to have little info and some predictability about the map and on the other hand they want it to be random to a certain amount. I think we should really focus on the MP gamers when implementing the RMG, single player and hotseat gamers want interesting, story-telling maps which the RMG can’t really achieve. So, I think it is important to keep the templates approach, but we could implement generation of a “pandora-box” map later. (years later probably )
I don’t think that it’s worth the effort to generate templates with SBPCG. It can be added as a development tool later, when generation of “pandora-box” maps are possible. I think templates can be important constraints for the SBPCG to save generation time as well.
It is possible.
I would like to add a few more things: positions of starting towns and towns in general, positions of mines (wood, ore,…).
OK, I’ll write a JSON format where templates can be specified. These templates include only zone information. The template loader is object-oriented, so adding support for the legacy H3 format should be possible (a mapping would probably required, I don’t want to reverse engineer how values are calculated in the template exactly).
Currently I’m implementing the selection of a template which is adequate to the chosen random map generation options. First, I thought that it would be fine that the minimum and maximum human count / total player count is in the same range as the player count / computer only count of the generation options. But this will probably generate totally unbalanced maps for templates which allow a certain range of players. So, I generated a map in OH3 and was surprised that this is really true. Mostly all standard templates are unbalanced if not all human start zones are controlled by players(whether CPU or human). BTW, Small Ring is unbalanced any time. It didn’t required many attempts and I got a map where one player could easily conquer two neutral towns(human start zones) within 1 or 2 turns. Then, I remembered a site where professional RMG templates can be downloaded: toheroes.com/h3maps/Random.htm The first thing I noticed was that you can download templates for 2, 3 or 4 players only. So, they fit exactly to the amount of players, which have the potential of producing balanced and thus good maps. The next thing is that the ranges for the map size(of the template) are closer compared to the ones from OH3, so that the suit the selected map size(selected by the user) better. Now, I have a few questions regarding templates and if we could simplify the process a little bit.
Questions:
Should we allow templates which define ranges of possible players at all?
Should we allow random map generation with computer only players? Are such templates really used by heroes gamers? (It causes problems and adds complexity… We would have to define less templates as well.)
Just for interest: Why are there no x>4 player templates to download on the website I have posted? Are 8 player templates unusual for MP games as they are played online mostly and therefore many players are needed?
I don’t want to invest too much time into writing a good selection algorithm for suitable templates. The min/max human count and min/max total player count is a bit confusing. I don’t want it too customizable here regarding player count. 4 player templates which are played by only 3 players are mostly unfair. OK, it depends on good templates, but why should the template developer choose between those possibilites? BTW, perhaps I will add a /rmg subfolder where users can copy their own templates more easily just like /Maps.
The next problem is that it could involve too much effort to write templates for every amount of players. I think that this problem can be minimized with automatic template enlargement generation (both in size and players). I know this is not possible for all templates, but anyway. Further time could be saved if a specific type of zone could be defined once as a declaration and referenced from real zone definitions. For example human start zones have mostly the same properties. All these improvements can be done later. Keep in mind, I want to focus on terrain generation now(it has to be finished in a few weeks!), so I don’t want to invest too many time in changes regarding template or complex template selection algorithms. I can mostly move on, but I wanted to ask these questions to hear some opinions from experienced heroes MP gamers. (I will probably change the testing template from Small Ring to Balance, medium sized and deactivate two level gen, L and XL generation via the UI for now)
I don’t think that banning players from playing unabalanced map is the goal. You can assume for now that all maps will be generated with ‘right’ settings and removing some players is just an option.
Also, Jebus is an example of 4-player map played mostly in duels. It is not very sophisticated template, but works for that reason
Templates that support more than 4 players come in original game. However, they suck.
Altrough i’am not in theme, but VCMI seems to support any map sizes.
So is there possibility to take 4 player template, generate 144X288 (2XL) map for 8 player, based on this template?
What’s the progress on this? I want to make/enhance rmg. As I can see from the sources, it doesn’t actually generate anything, makes just a “stub” map.
If there is some code not in the svn/git, could you share it so I’ll have some starting point? Or, if not, tell me so I won’t worry about remaking what is already done.
jfhs and I had some initial discussion about the next steps concerning the development of the RMG. We think it’s better to continue the discussion in this thread.
A shortened version of my PM:
First, I want to tell you where we stay currently with the development of the RMG. The following parts are already implemented:
The structures which serve as parameters for how to generate a random map. All parameters are handled in the class CMapGenOptions.
The GUI components to start a random map and to select options regarding the map creation.
The client/server architecture which ensures that all clients and the server generate the same map.
Handling of random parameters.
Generation of a simple map with an empty island filled with towns only.
Correct handling of placing terrain tiles on the map (complex!)
Support for map operations and selection of terrain tiles and objects. See CMapEditManager
Creation of a few simple RMG templates with zone information
Parsing and selecting a RMG template based on the generation options
…
The next part which is missing and probably one of the most complex parts of the RMG is the placement of zones. The problem with the original H3 RMG is that it generates often maps with many teleporters which don’t have to be there necessarily. The problem can be solved with a genetic algorithm which uses crossover for example. The placement graph should be planar if possible. The sole information is the zone information, how many zones are there and how are they connected. The task is now to transform that zone information into a planar graph.
…
END
I didn’t post the part about SBPCG. I think we can simply omit it for now. It shouldn’t hurt too much as we can implement it later too. Let’s keep things simple and stupid or simple and small. The advantage of SBPCG is that you can optimize for several objectives if you can formulate fitness functions for them. There are many scenarios where fitness functions can’t be found(think of zone structure, town count/density, terrain type of a zone, etc…) and perhaps a few other scenarios where they can easily be found, e.g. optimize for average town distances, same mine distances(especially to wood and ore),… It’s possible to do the same thing with a strict ruleset or constraints, but it can be more difficult to maintain or to control. That’s all. If we don’t put too much effort on placing mines, towns or other objects perfectly for now and keep things simple, we can easily switch to some genetic algoritm/optimization algorithm at a later time if required.
Now jfhs, let’s get the discussion started Could you repost your last PM which you sent to me?
I’ve some “my” vision of how it should be implemented, based on that presentation of H3 RMG:
Split map to zones, according to template. This can be done simply by having several internal templates of placement, based on zones connections. I.e. if there are a zone that connects to more that 3 other directly, we should put it in center area and put others around. If there is no such zones, we can make zones roughly equal by width and height or make long, stretched by x or y, etc. I think there is very limited set of possible ways, and they can be somehow hardcoded, no need to use some complicated algorithm for them.
After deciding a rough template, place dots split using voronoi diagram the space. Or may be some else, but this will be ok for the start, I suppose.
Start filling each zone by placing boundary obstacles (to divide from surrounding zones) and essential objects, like castles, mines and ways to other zones. Way is just a road, if zones are directly connected, or portal if road won’t fit. About that problem with portals, may be I didn’t understood it right, but I don’t see anything wrong in placing portals instead of roads, cause cost to travel it is roughly same (maybe like 2/3 steps shorter, but that’s negligible). I even thought of starting without any roads, only portals cause it can simplify things a little.
Now place optional object in some prioritized order. I.e. place additional castles/towns, then mines, then dwellings, special objects (well, etc), resources, treasures/artifacts.
Make roads to connections.
Finalize by putting guards and obstacles everywhere needed.
Validate that all is guarded and is accessible properly.
Placement of the objects may be done by algorithm described in presentation, by putting them while some minimal distance is keeped between them, thus having desired distribution around the zone.
The most complex task for me seems the right placements of obstacles and guards, so they won’t block something that was not intended to be blocked. I think that should be done on both steps of placing objects and guarding them, so object won’t be placed on some tile that is not possible to guard properly. Other way may be to delete this “wrong placed” objects on the step of guarding/validation. But this should be done carefully and only with additional objects like treasures/resources, so it won’t hurt balance a lot.
I’ve already made some programming, and have some of this working:
Zones can be of any polygonal shape, for now map is split to rectangles, but it should work for any shape.
Town is putted to the center of the zone.
Mines and resources are distributed over the zone.
Some resources are guarded, but by very stupid method of simply surrounding them with obstacles and putting a guard on one of the tiles.
That’s what I have for now, and I want to improve it till I’ll get something like I described on top.
I already have plenty of feedback because of coding and testing (i.e. that guards should be incorporated with placement, in the beginning I thought this should be totally different steps). I think that’s a better way of doing the RMG, since many problems will surely arise during process, and extensive planning may fail at some point.
And additional question about random number generator:
If I use it like this: gen.getInteger(0, 10), it always gives the same number again and again. I’ve fixed this at some places where range is limited, by simply using static var for gen.getRangeI, but there are some cases where this is not possible. How can this be solved?
Place connected zone in close distance to previous one. Make this zone a new “current” one.
If current zone has no free connections, get back to first zone. Continue until all zones are placed.
Now, iterate a few times:
Calculate distance between each pair of zones. Sort them in ascending order. If a distance is smaller than sum of zone sizes, move the other zone away.
For each connection between zones, move the zones closer.
Finally, re-scale zones so that boundary middles in x-y lay within 1x1 square, if a map is square one. Multiplying that by map size you get your desired coordinates for zone middles.
Then comes voronoi partitioning, but that’s another topic.
I believe gen MUST be static / global so that every time you use it, random number is updated according to algorithm. Random number generators create series of random numbers, you know
My problem with teleporters is purely aesthetics: [forum.vcmi.eu/t/random-map-generator/542/11)
But having working RMG is much more important than that. Issues like this can be solved once core functionality is finished
If you’re constructing random generator every time then this will hapen:
)
