Randomly generated maps

[MirceaKitsune]

Kind of an obvious feature to suggest, but surprisingly I'm not seeing other threads about it so might as well make one: Considering Megaglest maps use simple heightmap terrain and real unit positions are always 2D. Would it be difficult to allow automatically generated maps, computed by the engine before the game starts?

When setting up a match, the user would have two options: Select one of the existing maps like you do currently, or have the engine generate a map for you. When choosing the second option, you may optionally edit a few extra fields such as: The X and Y size of the map, how extreme the terrain should be (smooth plains vs. rough mountains), the frequency of trees and other resources, decoration density, etc.

I imagine this should be easy to achieve using perlin noise: Use a random seed for the terrain and for each resource, then scale its brightness to determine height / frequency and its contrast to determine concentration. Then place each player's starting point in the areas which are most open and closest to all resources, and there you have it! This would be fun for people who are bored of the existing maps, and just want something new each time they click the start button.

[Omega]

Procedural generation of maps is certainly possible. Mostly nobody has simply bothered to implement it, yet. But it's more complicated than you suggest. Generating a randomized heightmap is easy. The harder part is placing objects in a way that is playable, looks good, and doesn't follow simple patterns (because simple patterns are boring). Like, you could easily just make every map follow either an "X" or square shaped path between player bases or something. But that's predictable and boring. Some other games have it a lot easier because it's perfectly acceptable to not be 100% balanced. Eg, Civ V is well known for mostly using procedurally generated maps. But Civ V doesn't mind if one player is isolated on an island surrounded by water (since they have navies). Civ V doesn't care if you have a mountain range making it crazy hard for you to be attacked. Frankly, maps don't care too much about balance since the style of the game gives lots of ways to recover from that. And of course, if you want to see how much work can be involved in procedural generation, perhaps take a look at the various map scripts for Civ V.  It's not that easy to do well. I've seen some scripts that are like 5000 lines of Lua code (and that's with the infrastructure to place stuff already being in place!).

MegaGlest? Not so much. Map balance is much more important. That limits what procedural generation can do in an interesting way. The main "easy" ways to come up with procedurally generated maps in my mind would kinda be boring. It also doesn't help that the pathfinding can get confused if you do anything too weird (and hence why human made maps need to be tested when you try anything weird).

My personal recommendation is just to have lots of maps and tilesets installed. Using a random map with a random tileset and randomized starting points and you've got some serious degree of variance going on.

[kagu]

Omega + 1,

I experimented with this, I used python to generate perlin noise maps, then save it as mgm map.
I always imagined that as a starting point for a map , which could be continued by a human, or just as inspiration.

[MirceaKitsune]

There are indeed some points I haven't thought of; Generating roads between player's starting points would be tricky, especially when this random terrain may produce rivers (which units can't cross) and needs to cut through forests! One idea would be to randomize starting positions first, then build roads in between them, then generate the terrain (ensuring the road stays above water and below high mountain tops), and lastly produce the forests and other resources in safe areas.

[MoLAoS]

Generating roads would be pretty simple. Its basically just a one time pathfinding operation where you can take some shortcuts.

The real issue is making it look nice. Making a functional random map is trivial. Making a "wow that's awesome" random map is the sticky part.

[thiemo]

I very strongly second the idea of random maps. I just think fog of war is partially rendered useless on known maps. As I recently was told in a coop game, the are more resources in the centre of the map... do not be offended, it just natural to take into account what one knows. It is just hard to try to ignore it and I feel it is rather impossible to ignore all one knows as player about a known map that the faction cannot know at the beginning. I see it with myself. I played oneOnOne several times mostly to try out a new faction. After the second time I knew where the gold resource are and I could safe the effort for reconnaissance missions. I do not know, however, if this is an advantage over the AI.

[Omega]

I very strongly second the idea of random maps. I just think fog of war is partially rendered useless on known maps.

I don't feel like fog of war is really meant to make the map unknown. It's really more for strategic purposes I mean, plenty of games have fog of war and known maps. The most blatant example are MOBAs like League of Legends. The map there is totally known and fog of war is strictly to allow for strategic play. Ensures that unless you have a unit somewhere, you can never tell what your enemy is up to. Allows for surprise attacks and the like.

But you're right that the AI has a disadvantage because of map features like having gold in the middle. Perhaps for high AI difficulties, the AI should actually start with the map revealed? Not sure how much of a difference it makes, ultimately.

[jammyjamjamman]

I was experimenting a bit too with random map generation in python.

My idea for the main algorithm is something like this:

• Create the height map.
• Draw the surface map.
• Create resource positions (for players to get stone and gold from), not too close to each other.
• Place a stone and gold patch (or resource cluster) near to each resource position.
• Draw paths (on surface map) between positions, avoiding cliffs and and water.
• Position players in resource positions, making sure players are nearest to other team mates. (should teams be randomly allocated?)
• Add woods, avoiding water and paths and resource positions. Put big trees in middle of wood patches. (This part I'm the least sure of the best way how to do.)
• Add all the other decoration.

Actually, steps 3 and 4 can be interchanged with 5, but then the algorithm changes a bit. If 3 and 4 are done first, you need a pathfinder to connect locations (like what MoLAoS said), then you add some randomness to the paths (make them more windy). If 5 is done first, a random "walking man" or "turtle" style algorithm can be used. Resource positions are then stuck to the ends of roads.

[thiemo]

1. Create the height map.

My gut feeling is that the height map should rather be done last. The earlier you do the more likely it seems to me that you end up with inaccessibly portions where units are sort of islands. My idea would be (with the premise that every object has a specific anti-gravitational or gravitational force according to its nature and the nature of its counterpart, e.g. player positions repel each other strongly where as resources are lightly attracted, resources attract of the same type but the more are coagulated already the lower the attraction to prevent big lumps, ...)  :

• Generate player positions
• Connect them with paths (not necessarily shown as paths in the map)
• Generate resource positions
• Generate obstacles like boulders trees, gallows and gibbets
• Generate topology where the heights and lows, waters also are (anit) gravitational

http://www.anchormodeling.com/modeler/latest/ could give an idea of its workings.
Maybe the topology should still be generated first but needed an algorithm to make sure there are enough level and level enough places to place player positions, to have paths connecting all player positions with each other (multi use permitted) and all the rest.

[titi]

Its not really about random maps, but it helps a lot:
https://forum.megaglest.org/index.php?topic=8353.0

the heightmap importer/exporter: http://muwum.net/mgm/