Random map generator

International board Development
#57

I’ve some “my” vision of how it should be implemented, based on that presentation of H3 RMG:

  1. 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.
  2. 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.
  3. 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.
  4. Make roads to connections.
  5. Finalize by putting guards and obstacles everywhere needed.
  6. 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:

  1. Zones can be of any polygonal shape, for now map is split to rectangles, but it should work for any shape.
  2. Town is putted to the center of the zone.
  3. Mines and resources are distributed over the zone.
  4. 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?

#58

My proposal of zones placement algorithm:

  1. Reorder zones vector randomly.
  2. Place first zone in the middle.
  3. Place connected zone in close distance to previous one. Make this zone a new “current” one.
  4. If current zone has no free connections, get back to first zone. Continue until all zones are placed.

Now, iterate a few times:

  1. 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.
  2. 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 :wink:

Show us :slight_smile:

#59

Demo or it didn’t happen :slight_smile:

#60

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:

CRandomGenerator() 
{
	gen.seed(std::time(nullptr));
}

There is also a small chance that I broke something during switch to c++11 random generators.

EDIT: try to wrap “gen” parameter in CRandomGenerator::getRange() methods with boost::ref():

TRandI getRangeI(int lower, int upper)
{
	return boost::bind(TIntDist(lower, upper), boost::ref(gen));
}
#61

Again just asking… there are/will be a ton of new content added to H3 via mods… Is it possible to have an option to bias towards some sets? (EG. more frequent HotA object placement over original H3).

#62

Didn’t understood this one. Sum of what zones sizes? All or pair?

I think that is what I needed, thanks, will try it later.

The algorithms for placing don’t really now what type of object it is placing, so I think there will be no problem with placing new objects from mods, but they should be somehow catgorized/parametrized. I think too early to think about this now.

About showing what I have. I am not feeling this should be “shown” as some real progress, cause I think even that small things that are there, will be changed/rewritten. But if you want:
github.com/jfhs/vcmi

You can get only two files from here:
github.com/jfhs/vcmi/tree/master/lib/rmg

Should compile everywhere, but I don’t guarantee it.

VCMI 0.95 released!
#63

Well, the distance between center of two zones should not be less than sum of their radiuses (size). Don’t remember at the moment if zone size is proportional to radius or area, however.

#64

Checked on my compiler zoo: gcc-4.6 fails because of this:

lib/rmg/CMapGenerator.cpp:1047:10: error: class std::set<int3> has no member named emplace;
lib/rmg/CMapGenerator.cpp:1048:9: error: class std::set<int3> has no member named emplace

This method is not implemented in 4.6. All other compilers work fine (not counting several unused variables warnings).

AFAIK H3 RMG has hardcoded probabilities to place some specific object. From my point of view this should be turned into property of object along with list of categories the object belongs to. When this functionality will be exposed to mods modders will be able to set any values they want (like increased chance to appear)

But yeah - it is too early to worry about that. After all we still don’t have neither RMG nor possibility to add new map objects (not counting town-related objects).

#65

I have an idea how to make right guarding, I need a pathfinding algorithm for that, but can’t find it. Could someone tell me where I should look?

#66

CPathifinder in CGameState.h.

Keep in mind that pathfinder was meant to calculate paths for heroes, will all the movement modifiieres and so on.

Also, it’s interesting to know what are beegee’s thoughts and plans on the code. I’d like to see something working in game, finally :sunglasses:

#67

Sorry, for the late response!

I think it’s best to get things done quickly. A deeper insight into the problem shows that a lot of effort is necessary to place zones on a planar graph perfectly. So I think it will be fine for the beginning if zones aren’t placed properly and if they are connected with teleporters if required.

I come up with a solution which is based upon Warmongers suggestion and extended with jfhs idea to place the zone with the most connections into the middle. So the only difference is that the zones vector isn’t sorted randomly as the first step, but ordered by the number of connections from high to low. If zones have the same number of connections, the order is random.

Currently we have three simple templates in SVN, the code below shows one template. It has 4 player start zones and 1 treasure zone. Placing the treasure zone into the middle should give good results for this easy template.

  P
  |
P-T-P
  |
  P

jfhs, you are doing a good job! The code is really nice, you use auto, for-each loops, boost format, logging,… :slight_smile: One question, can we already use for-each loops? I don’t know but I haven’t used it so far. I have only minor note, we are following these coding guidelines: wiki.vcmi.eu/index.php?title=Coding_guidelines. We use the hungarian notation for variables, classes, functions and so on.

I didn’t test your code, but do you place terrain tiles for the zones?

From my side you can freely work on the RMG and commit your code to SVN. Sadly, I can’t do much things for the time being. Before you can commit to SVN, I want to prepare some things. Hopefully I will be finished till Thursday or Friday.

  1. Add handler classes CRmgTemplateStorage and CTerrainViewPatternConfig to LibClasses.

  2. Split unit CMapGenerator.cpp into:

CTemplate
CZone
CMapGenOptions
CMapGenerator
CRmgTemplateStorage
Files should be grouped into a visual folder in Visual Studio project file for better structure.

  1. Create CZone and CTemplate objects in the heap and use pointers. They have to be accessible from several places. Ownership is clear, so it’s not a problem.

  2. Add stub classes:

CZoneGraphGenerator -> Generates a zone graph upscaled to map dimensions. Input is template, map dimensions, number generator…
CZonePlacer -> Takes the graph, transforms to voronoi diagram(?), executes fractal algorithms and places the terrain tiles.

So we can easily create an interface and provide an own implementation of CZoneGraphGenerator later for example, if we want to change that part of the RMG. It also shows the dependencies and makes testing easier.

Both generator classes don’t add any information to the original CZone object. For additional and generated data they “wrap” CZone objects and use composition.

#68

Done!

jfhs, from my side you can start working on the RMG. Ask Tow for a SVN access, so you can commit your changes. You can use the stub classes CZoneGraphGenerator and CZonePlacer which I commited as a starting point. You can write the code to place terrain tiles for a zone in CZonePlacer only and the rest somewhere else or all zone relevant placing stuff(placing obstacles,…) in that compilation unit. Just how you need it.

#69

How’s the work on generator going?
When to expect first working version?

I want to ask.
Do you plan to implement filling water with monsters/dwellings?

I earlier proposed to add optional value to creatures JSONs like “aggressive”: true,
if this is set, and in map editor other behavior is not set, then creature is generated never surrendering/joining/running.
And now I think of optional value “terrain”:. So if set, then RMG will place creatures to pointed terrain only. And this shall include “water”, so some water monsters, for example, from Abyss (they be generated on water).
What do you think on these ideas?
Can they be implemented in RMG?

#70

I don’t know if jfhs is working on the RMG. That ideas can be implemented in RMG, but it has to do someone. Perhaps I will have more time in a few weeks, but then I want to work on smaller tasks like fixing bugs, take care of mantis tickets,…

#71

Is latest RMG committed to SVN? (jhs changes?)

#72

Yeah, it would be nice to get all this code together just to have a little progress.

#73

In two weeks I will have more time where it would make sense to work on the RMG and to transfer jfhs’code along with a few additions into our codebase. I don’t know if we release VCMI 0.95 in January next year but I think this will be too closely. (it’s a bit unrealistic, perhaps February would be better) I could either work on the RMG or prepare a testing concept. (and do some tests)

#74

I am asking because I would be interested to take a look at it too. (Not as main developer, but who knows maybe I will have an idea or too). It will help a lot to have the latest code committed to know what was done and what not. this independent of what will actually be included in the release.

#75

Here some thoughts on RMG options necessary to cover… The advantages of many are self explanatory.
One key idea is that rather than banning things from the whole map, a per zone setting allows decent starting zones with more powerful objects being possible later in the game.

First, some game rules like no diplo, no fly etc should be covered in a separate special part “general map options”. I think I saw a H3 mod with a nice GUI that enabled disabled individual spells, artifacts, etc.

Here a list I have for now:
**
Zone Options:**

Type: "PlayerStart", "Treasure"
Size: '1','2' Proportional with map size
Owner: 'Player Number', 'none'
Terrain: 'Type' or 'matchesPlayerTown'
PlayerTowns, NeutralTowns: 'TownType', 'Quantity'(min/max), 'allowSameType', 'forceSameType'
BannedTowns: 'Castle', 'Rampart'
BannedAdvMapObjects: 'hillforrt', 'utopia', 'chartographer'
AllowGrail: (Per zone setting. Allows grail in treasure area)
Exclude Scrolls: ('level5', 'Berserk')

   **Ability to override zone density for individual objects**

Mines : 'wood', 'ore', 'crystal', 'sulfur', 'gem', 'mercury' (min / max)
'Leprecauns' / 'Windmils' / 'Watermills' (min / max)
'Crypts' (min / max) 
'Utopias' (min / max) 
'Creature Dwellings < 6' (min / max) 
'Creature dwellings 7' (min / max) 
Pandora Boxes: Reward type, Frequency, Guards. Different Pandoras in different zones.

Misc:

- zone visual separators like in H6 (but with no meaning)
- add a max to connection wideness

Global Options for all Zones:

  • Map size: use Square numbers 144x72 (allows rectangular maps)
  • Template description / recommended difficulty, etc

All the following :recommendations: can be overridden via the before mentioned general game options.

  • Recommended exclusion list for Adv map objects (hillfort, utopias)
  • recomended exclusion list for spells
  • recomended Disable Grail => no grail or obelisks

Misc:

  • Game option to allow for only 1 external creature dwelling. (Even if more could be available in area).
  • Game option allowFortsIfSameType
#76

Sounds nice, this settings belong to the template. General map options which can be chosen by the player should be kept to a minimum, but a few so called expert settings (utopia, grail, dimension door, fly, … ) should be OK.

I want do a few things on the RMG after working on campaigns (heroes moving to next scenario) and perhaps battle (gate animation).