Random map generator

OK I’ve created a list which steps I want to do. The main goal is to develop rapidly a functional RMG with all parts of generation(terrain, heroes, towns, …). It doesn’t need every feature or produce good-looking maps in the first development phases. The implemention of the RMG will be similar to the original algorithm of H3.

I want to use the internal map format of VCMI. Storing generated maps to H3M is not required for now. I’ll integrate the RMG lib into vcmiclient, therefore a specific RMG generation screen/GUI(in PreGame) is needed (like in H3) => to start/test a generated map. That functionality is experimental and disabled by default. For testing purposes the generated map is fully visible when starting the game.

That’s my current todo list:

  • I want to separate map loading logic and the object representation of a map(map header,…). It simplifies/separates better the API and different map loading/saving algorithms can be supported. Mappa gets split into: CMap(the value object), CMapService(contains loading, saving, map accessing logic…)
  • Have a detailed look into the internal map format. Add javadoc comments like I did for the filesystem API. Add remarks which map attributes are required/optional.
  • Add RMG screen/GUI to vcmiclient/map selection. (buttons may be disabled, don’t have any functionality for now…)
  • Mock map generation(with terrain, obstacles, towns…). VCMI should start that map (to find out how the internal system works) This is coded in libRMG.

Future steps(i haven’t done much research, but algorithms which I found are similar -> fractal, voronoi polygons):

  • Simple templates in JSON
  • Terrain gen
  • Obstacles mask gen
  • Town/Monsters/Mines gen
  • Obstacles placement

Interesting posts on Russian forums (ask me if you need to translate them):

Parameters of objects in RMG (max number on whole map and for each zone, cost of the objects)
forum.df2.ru/index.php?showtopic … ntry559149

Generation of guards for objects (calculations of guards strength)
forum.df2.ru/index.php?showtopic … ntry558697

Problems with H3 RMG:

  • zones placement: huge amount of portals, including one-way portals. Sometimes - even completely sealed off sections. Algorithm should be able to place zones without large nuber of intersections (try to make zones graph planar). May be one of the most complex part of RMG.
  • creatures placement: sometimes H3 RMG may place them incorrectly. E.g. artifact guardians may block access to nearby town.
  • huge maps generation: if zones are not big enough to cover whole map large areas of maps will be filled with blocked terrain

Similiar info about templates is posted on HC.

I’d rather call it still unsolved problem and impossible to do anyway in many situations.

Thanks! That is really nice material. I’ll dive into it later:)

First part of preparation is done. Map loading is separated from the map object. If there are any new bugs when loading maps, please tell me. (I’ve tested several maps/campaigns…)

Second part is to add the RMG ingame screen and some mock map generation for testing. I won’t add a new library for the RMG, code will be placed into /lib/RMG.

I agree that it can’t be fixed completely - not every graph can be made planar.

But RMG places just too many teleporters too often. For example I just generated random map.
Template was 8MM0b, one level map. Connections in rmg.txt look like this:

1 -- 2 -- 3
| \  |  / |
|  \ | /  |
8 -- 9 -- 4
|  / | \  |
| /  |  \ |
7 -- 6 -- 5

This template can be generated without teleporters but nevertheless I have 4 pairs of them placed as well.

Even two-level maps with water ( = a lot of connection possibilities) suffer from this from time to time.

EDIT:
beegee, it looks that all your files use 4 spaces for indentation. Switch them to tabs for consistency with the rest of VCMI code.

I think it could be relatively easily and with good results approximated with some kind of genetic algorithm. You can consider placements as permutations.

Any progress on this? I am also interested in a new RMG.

Of course! But productivity is currently limited due to exams:( The RMG screen and the foundation to start RMG maps is done so far, if you didn’t know it already. Currently I’m busy with creating a mock map. I thought to get this step done earlier, but terrain placement seems to be trickier than expected. Mostly you just don’t recognize it, but the map editor of H3 does a lot of processing here. Selecting the correct view image of the terrain type and adding implicitely terrain tiles if needed. But I got now a theory to map this in a straightforward and easy way. (patterns which indicate which terrain view to use… relatively simple rules -> complex patterns -> rolled out in .json files)
This week are the last exams, so hopefully I get some time over christmas time!

Your progress so far, Is it public already?

The map generator is disabled by default ATM. There are many things left to do. When a basic map can be played(!) this may be changed. To show current progress in-game you have to set enableRMG to true in one of those files config/settings.json(for Win) or ~/.vcmi/config/settings.json(for Linux):

"general" : {
		"music" : 0,
		"sound" : 0,
		"enableRMG" : true
},

The RMG code is commited to lib/RMG. There will be some additions to lib/Map in the next days. At this timeline you’ll see progress and source code changes better: sourceforge.net/apps/trac/vcmi/timeline.

There are some updates to announce:) The RMG generates now(with rev3084) a test map with one island and 1 town for every player. Current town & terrain generation has the only purpose to create a valid map. This will be changed later of course. But the rest this means player/team generation, map header(description,…) is fully functional.
There a few known bugs to mention:

  • correct terrain view handling implemented, but not activated for now(1 part is missing + testing)
  • starting the map with only 1 player currently crashes(should be fixed in a few days)

If there are any further bugs, let me know.

Good to see some progress here :slight_smile: One isuse, though:

Indeed there’s no such file in my boost 1.46 folder. Is this part of new version of library?

VCMI_Lib is not compiling.

1>d:\home\krs\work\programming\vcmi\vcmi\lib\mapping\cmapeditmanager.cpp(256): warning C4018: '<' : signed/unsigned mismatch
1>d:\home\krs\work\programming\vcmi\vcmi\lib\mapping\cmapeditmanager.cpp(288): error C2440: '=' : cannot convert from 'void' to 'bool'
1>          Expressions of type void cannot be converted to other types
1>d:\home\krs\work\programming\vcmi\vcmi\lib\mapping\cmapeditmanager.cpp(294): error C2440: '=' : cannot convert from 'void' to 'bool'
1>          Expressions of type void cannot be converted to other types
1>d:\home\krs\work\programming\vcmi\vcmi\lib\mapping\cmapeditmanager.cpp(300): error C2440: '=' : cannot convert from 'void' to 'bool'
1>          Expressions of type void cannot be converted to other types
1>d:\home\krs\work\programming\vcmi\vcmi\lib\mapping\cmapeditmanager.cpp(267): error C3499: a lambda that has been specified to have a void return type cannot return a value
1>
1>Build FAILED.

Sorry for that circumstances.

The boost random library is header only and exists since boost 1.4.3 if i have looked correctly. The problem is that they’ve renamed the header files sometime between boost 1.4.6 and 1.5.0. Warmonger you have three options. Either you update to boost 1.5.0+ if you want to compile it quickly. The second option would be to fix it by yourself with a macro. The third and probably most convenient option would be to wait till 20.00h(utc+1), then I will have fixed it:)

Krs it seems to be that your compiler doesn’t support the new function declaration syntax for automatic return type deducation or sth. like that is it called:) You have only two options. Either fix it by yourself and adding -> bool after the line 261 right near (bool rslt). The second option is to wait as said above.

Compile bugs should be fixed. Does it work now?

I think the way how the RMG map is generated, that means the organization that every client generates a map, is problematic. In a multiplayer game there can be clients which use different implementations of the boost random API. This can result in different maps, which will lead to undefined behaviour. This solution was quick and easy, but it seems to be that it isn’t the most stable one. Boost random API changed a lot in v1.4.7 as you can see here: boost.org/users/history/version_1_47_0.html (most changes belong to random api) There are two solutions IMO. 1. Commit all required boost random header files to SVN. That way it’s sure that every build uses the same API. We have no additional dependency. But it’s not the nicest solution, I know:) 2. Generate map on the server/host and send generated map object to all clients. That will lead to much I/O traffic. Some code changes need to be done.

Shouldn’t this API produce same results everywhere? (assuming the seed is same). They may have renamed some classes but I don’t see any references to changes in algorithms that may affect us.

If not - then RMG won’t be the only problem - right now most of map initialization is done separately by both client and server using boost random.

From what I can see boost::random headers depends on common boost headers. May be messy.

AFAIK that c++11 standard “feature” - return type autodetection works only if lambda body consist from single return statement.
And this is how VS works. gcc\clang behavior is less strict here.

1>d:\home\krs\work\programming\vcmi\vcmi\lib\rmg\cmapgenerator.cpp(292): error C2653: 'CPlayerSettings' : is not a class or namespace name

I know people are sensitive when it comes to their coding style but looking through RMG I had some troubles reading some parts, so I can but wonder if you are not overdoing it?

mapGenOptions.setWaterContent(static_cast<EWaterContent::EWaterContent>(gen.getInteger(0, 2)));

Is the static_cast really needed?

In CMapGenOptions.h are these separate namespaces really necessary?

namespace EWaterContent
{
	enum EWaterContent
	{
		RANDOM = -1,
		NONE,
		NORMAL,
		ISLANDS
	};
}

namespace EMonsterStrength
{
	enum EMonsterStrength
	{
		RANDOM = -1,
		WEAK,
		NORMAL,
		STRONG
	};
}

And a side-question… I find the code much, much harder to read with a map instead of a simple std::vector. What are the advantages of using a map in this particular case?

	/** Typedef of the players map, so that boost foreach can be used. */
	typedef std::map<TPlayerColor, CPlayerSettings> tPlayersMap;

Another not related side note:

Maybe I am getting “older” but I prefer any time a good old readable for {if} -> return to lambdas like this:

int CMapGenerator::countHumanPlayers() const
{
	return static_cast<int>(std::count_if(players.begin(), players.end(), ](const std::pair<TPlayerColor, CPlayerSettings> & pair)
	{
		return pair.second.getPlayerType() == CMapGenerator::CPlayerSettings::HUMAN;
	}));
}

They prevent pollution of global namespace. I’d prefer using strong enums but not all compilers support it.

What’s so hard about std::map? It’s a logical choice because not always all players are present.

for + if is an old, imperative style. Imperative style is all about optimization – we all should write programs declaratively, and, if that cannot be done efficiently, then in a functional way, and imperatively if we really have to. Unfortunately lack of so-called polymorphic lambdas and container.begin(), container.end() syntax makes this code look less appealing than it would look in a real functional language (Haskellish pseudocode:

 countHumanPlayers = length $ filter (\x -> x.second.getPlayerType() == CMapGenerator::CPlayerSettings::HUMAN) players 

; isn’t it beautiful? try to make off-by-one error here, or omit counter initialization; BTW – it’s fully statically typed if you didn’t know ;))

@Beegee
Great work! :slight_smile:
I’m very happy to see progress on RMG and looking forward to its further development.

Now for mine minor remarks (use them or ignore, as you like):

  • instead of writing
std::algorithm(container.begin(), container.end()...)

you can use

boost::algorithm(container, ...)

Boost.Range provides range overloads for STL algorithms, we have it in PCH.

  • BOOST_FOREACH works with auto&, map typedef is not really needed.
  • why not use tPlayersMap::value_type as lamda argument type (instead of pair<>)?
  • instead of writing
sth = unique_ptr<Type>(new Type(...))

you can have

sth = make_unique<Type>(...)

Type is not repeated then. [you may need to add 3-arg overload, I didn’t need it so far :P]

  • checking if map contains element (eg in CMapGenerator::getNextPlayerColor): instead of players.find(i) == players.end() you can have just !players.count(i). Or use vstd::contains that works on “all” containers.

It’s VC10 issue, Visual 2012 works with deduced returned type.

Can be written pretty much the same in C++ modulo polymorphic lambdas.

Though… for me the beatufiful thing in Haskell syntax is it lack of parenthesis in function call syntax. After reading Haskell, C-based languages start looking… Lispy. :stuck_out_tongue:

[center]**************************************************************************[/center]

It is always good to ask. Either you’ll find something that can be improved or you’ll get better understanding the style rationale. Either way — win. :slight_smile:

Yes, otherwise it would likely yield a compile error. Integers are not implicitly convertible to enums.

The solution might be to use templated getSth function like:

mapGenOptions.setWaterContent(getSth<EWaterContent::EWaterContent>(EWaterContent::NONE, EWaterContent::ISLANDS));

But it isn’t really shorter and makes an additional assumption that EWaterContent members are contiguous. (though it’s possible that I’d written this such way if it were simple to implement)

They are. Otherwise how would tell whether NORMAL is EWaterContent::NORMAL EMonsterStrength::NORMAL?
However you are likely the last one really needing that namespaces. :wink:
After we drop support for Visual 2010 we get strongly typed enums that create a name scope of their own. That namespaces will be gone then.

I assure that equivalent code based on vector would be worse. I know. Once we stored player settings in vector and it was source of endless problems and bugs. You either ened to have “empty, invalid” entries (and ifs for them everywhere) or separate “serial” and “color” IDs, either way it is horrible.

I believe it’s matter of getting accustomed to such style and its syntax. At the beginning }); felt so wrong to me. :wink: Support for functional-style programming elements in C++ is a new thing. It can be hard to read at the beginning. It gets better.

The difference is that algorithm+lambda allows you to clearly express intent and makes impossible to make a stupid mistake in counting algorithm.
When I look at the code I immediately recognize count_if part and I know what it is doing. In the traditional for-loop+if-approach it would take me longer — I would have to read through all the loop and make sure that it isn’t doing anything else and does not have side-effects.