Forum index VCMI Project - Heroes 3: WoG recreated
Forum of the project aiming to recreate best turn-based strategy ever!

FAQFAQ  SearchSearch  MemberlistMemberlist  UsergroupsUsergroups  StatisticsStatistics
RegisterRegister  Log inLog in  AlbumAlbum  DownloadDownload

Previous topic :: Next topic
Opened by: Warmonger
2014-12-27, 14:29
Random map generator
Author Message
beegee 
VCMI programmer

Joined: 12 Dec 2009
Posts: 247
Location: Stuttgart, Germany
Posted: 2012-10-22, 19:51   Random map generator

In the context of my student research project I want to develop a random map generator for VCMI. The project has been approved by the university. It has to be submitted at the latest 1st july 2013. Any help regarding map generation algorithms or the h3m map format is appreciated. Yeah, I didn't want to develop VCMI any further, but things have changed:) The possibility to do a student project about vcmi/rmg gave me the motivation.

The RMG should be handled as a sub-project like libvcmi, battleAI,... I'll commit to trunk if I got something usable. (which is almost safe and won't be changed to frequently)

@Ivan/Tow: Is there any good material how the .H3M format is composed of?(I've searched a little bit, and you may know already some good material^^, I can always look into the source code, i know^^)

The next step is to compare already developed algorithms(which can be found via the internet) and compare them with the original H3 template-based RMG. That seems to be very nice: http://www-cs-students.st...ap-generation/. Perhaps it can be adapted to the tile-based terrain of H3.

In the far future I may write a simple map viewer with Qt if there is enough time. This way I can watch generated maps directly in linux instead of copying them to VM/Windows. This should be relatively easy. Some map drawing code have to be moved from client to lib. (then it can used by external apps) This map viewer can be used as a base for a map editor later. (I know far future, so don't think too much about it...)
 
     
Warmonger 
VCMI programmer


Age: 27
Joined: 07 Jun 2008
Posts: 1530
Location: Warsaw, Poland
Posted: 2012-10-22, 20:07   

You probably will want to follow this, at least in main points:
https://www.dropbox.com/s...%20smedstad.ppt

Original RMG explained. Some implementation details are missing, but I find it a very worthy read. Even considered coding RMG on my own in the future, glad there's someone to take the job ;)

I can't see much reason behind "simple map viewer", consider using this:
http://www.mapeditor.org/

And good luck!
_________________
Think twice if you really need to send me private message. Use public forum for general questions.
DJ Warmonger blog
beegee wrote:
Warmonger, you are the best!
Last edited by Warmonger on 2012-10-22, 20:37; edited 1 time in total  
 
 
     
beegee 
VCMI programmer

Joined: 12 Dec 2009
Posts: 247
Location: Stuttgart, Germany
Posted: 2012-10-22, 20:17   

Thanks Warmonger! Hmhm I can't download the ppt file from dropbox. I receive a dropbox error 500 when clicking on the link. Any country restrictions?(don't know)

What do you mean with the map editor project? Can this editor be programmed to load and render h3 maps?
 
     
Tow dragon 
VCMI Programmer


Joined: 01 Feb 2008
Posts: 1004
Location: Kraków
Posted: 2012-10-22, 20:33   

beegee wrote:
@Ivan/Tow: Is there any good material how the .H3M format is composed of?(I've searched a little bit, and you may know already some good material^^, I can always look into the source code, i know^^)


I think RMG shouldn't be concerned with map storage format... just fill fields our H3M reader fills.

BTW, I doubt simple map viewer would be simple to do -- there is a quite big step of randomization performed after a map is loaded but before it is displayed. You would have to make terrainRect render non-randomized maps. It uses callbacks for FoW etc. -- a common piece code for client and map viewer would be a nontrivial task. Moreover, putting terrainRect into lib would make it dependent on SDL. I'm not sure if it would be a good decision. After all server doesn't need it. Lib is designed to handle game data/mechanics common to lib and server, not rendering of graphics. What about a new dynamically linked library instead?
_________________
:)
 
     
Warmonger 
VCMI programmer


Age: 27
Joined: 07 Jun 2008
Posts: 1530
Location: Warsaw, Poland
Posted: 2012-10-22, 20:38   

Link fixed.

Quote:
What do you mean with the map editor project? Can this editor be programmed to load and render h3 maps?

Looks like it. Among other things, it contains ready GUI and Json parser. Also, has "Qt" in its name :P
_________________
Think twice if you really need to send me private message. Use public forum for general questions.
DJ Warmonger blog
beegee wrote:
Warmonger, you are the best!
 
 
     
Ivan 
VCMI programmer

Age: 25
Joined: 08 May 2009
Posts: 1438
Location: Ukraine
Posted: 2012-10-22, 23:41   

Quote:
@Ivan/Tow: Is there any good material how the .H3M format is composed of?(I've searched a little bit, and you may know already some good material^^, I can always look into the source code, i know^^)

If this is going to be submodule like libraries maybe you should use not h3m but our internal format directly? This will also remove some limitations that come from it. Rectangular maps were requested already after all :)
And instead of storing generated maps you can store presets + random seed.

I remember some RMG-related info on Russian forums. Will try to find it.

Quote:
I can't see much reason behind "simple map viewer", consider using this:
http://www.mapeditor.org/

Not sure if this can work as full H3 editor - objects in H3 are quite complex and from what I see this map editor is oriented towards simple set of tiles.
 
     
beegee 
VCMI programmer

Joined: 12 Dec 2009
Posts: 247
Location: Stuttgart, Germany
Posted: 2012-10-25, 11:56   

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
...
 
     
Ivan 
VCMI programmer

Age: 25
Joined: 08 May 2009
Posts: 1438
Location: Ukraine
Posted: 2012-11-03, 12:02   

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)
http://forum.df2.ru/index...49&#entry559149

Generation of guards for objects (calculations of guards strength)
http://forum.df2.ru/index...97&#entry558697

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
 
     
Warmonger 
VCMI programmer


Age: 27
Joined: 07 Jun 2008
Posts: 1530
Location: Warsaw, Poland
Posted: 2012-11-03, 13:50   

Similiar info about templates is posted on HC.
Quote:
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.

I'd rather call it still unsolved problem and impossible to do anyway in many situations.
_________________
Think twice if you really need to send me private message. Use public forum for general questions.
DJ Warmonger blog
beegee wrote:
Warmonger, you are the best!
 
 
     
beegee 
VCMI programmer

Joined: 12 Dec 2009
Posts: 247
Location: Stuttgart, Germany
Posted: 2012-11-03, 14:53   

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.
 
     
Ivan 
VCMI programmer

Age: 25
Joined: 08 May 2009
Posts: 1438
Location: Ukraine
Posted: 2012-11-03, 15:06   

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

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:
Code:
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.
 
     
Tow dragon 
VCMI Programmer


Joined: 01 Feb 2008
Posts: 1004
Location: Kraków
Posted: 2012-11-04, 11:20   

Ivan wrote:
I agree that it can't be fixed completely - not every graph can be made planar.


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


Joined: 04 Sep 2012
Posts: 374
Posted: 2012-12-17, 21:51   

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

Joined: 12 Dec 2009
Posts: 247
Location: Stuttgart, Germany
Posted: 2012-12-18, 11:39   

Quote:
Any progress on this?


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!
 
     
krs


Joined: 04 Sep 2012
Posts: 374
Posted: 2012-12-19, 22:07   

Your progress so far, Is it public already?
 
     
Display posts from previous:   
Reply to topic
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum
Add this topic to your bookmarks
Printable version

Jump to:  

Powered by phpBB modified by Przemo © 2003 phpBB Group
Template Chronicles modified by Nasedo modified by Tow.
© VCMI Team
Page generated in 0.06 second. SQL queries: 14