Random map generator


#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).


#77

It is already present in original templates. There are three types of objects possible to spawn in each zone. Also, each zone has minimum and maximum object value.

You forget that the whole point to write new RMG is also to add new objects in the future. Listing all possible objects to spawn in a zone is a no-go, we must provide more general and easy to handle mechanics. Like spplitting all objects to several classes (pickable, creature banks, stat boosts for example). This way new objects could be easily assigned to specific class and work fine in old templates.

Particular objects could be banned by mods, setting them as unavailable or changing their value.


#78

I have a question, will be supported by old teamplate? for example 2SM4d(3), 8MM6.
Or manually created for example Jebus Cross? If you put rmg in a folder DATA.


#79

Right now most difficult part of RMG is implementing algorithms (like voronoi diagram or automatic obstacle placement tool from editor). How they will be used is quite minor detail at this point.

Besides - as already mentioned by Warmonger this should be made in more generic way. And to do that we first need quite a lot of refactoring in map object handling - currently this is combination of hardcoded H3 properties that was written when project started + set of hacks to make objects from mods work (like dwellings).

If you really want to push this further - maybe you should move this to more easy to edit wiki? And then decide what should be part of zone configuration, template configuration, what should be user-selectable and what should become property of objects or object classes

UPD: actually - looking on current RMG format I think we should move rmg template format to wiki. Current format already have some (quite minor at the moment) points that I don’t like
Current version is in file config/rmg.json or here: github.com/vcmi/vcmi/blob/maste … g/rmg.json

Povelitel
Up to beegee or to whoever will implement rest of RMG. In worst case you’ll have to rewrite template to VCMI format. Considering that most difficult part in templates is balancing porting to vcmi should be easy - just rewrite those 10-20 lines from rmg.txt to our format.


#80

Of course you cannot hard-code every object inside map template. But doing like original RMG, will create highly unbalanced maps. (1-3 utopias on your zone while enemy has 0). (Grail on your zone… etc).

So specific rules should be implemented for these balance breaking objects and probably add a few more from the upcoming mods.

  • New map rule, allow only 1 level 7 to be flagged. This allows presence of 2-3 dwellings on your terrain but you will choose which one to “take”.

  • “Dirty bit” for conservatory gained creatures. Meaning you cannot upgrade and/or combine them.