Jump to content

Procedurally Generated Maps - Or How I Learned To Stop Worrying And Love Random Battlefields


9 replies to this topic

#1 Erebus Alpha

    Member

  • PipPipPip
  • Survivor
  • 81 posts

Posted 03 December 2014 - 12:14 AM

The devs have stated somewhere (too lazy to look it up and quote it ATM) that they are not going to use randomized computer-generated maps, since these random maps would be imbalanced and no fun to fight in.
  
TLDR: Devs are wrong, it can be done. They can use computers and automation to do most of the tedious work of mapping, and if it's designed at all well, it will make balanced and interesting battlefields - likely surpassing the current ones we fight on. They can focus on CW and other cool things, and only have to make new stuff to go in the maps once in a while. Instead of map development being measured in terms of weeks per map, we will instead get maps per week.
  
Based on my knowledge of programming, I strongly disagree with the devs' viewpoint. Any task that can be reduced to procedures and equations can be automated, and there are ways to use the human labor at PGI far more wisely than just generating a map once in a while. Automating this process will free up human labor for work on community warfare, new mechs, and other very cool things. There is a lot that the developers and players could gain from this.
  
To start, we need to understand what a map consists of. The most obvious feature is terrain - that stuff our mechs walk around and stand on for the majority of the match. It starts off as a perfectly flat and tesselated plane, and it uses a greyscale heightmap to 'shape' this plane into a curvy and more visually appealing landscape-ish thing.
  
Why use a greyscale heightmap? The value (darkness/lightness) of a single pixel in the heightmap image can be used to derive the height of a single vertex on that plane. The heightmap allows developers to store an ENORMOUS amount of data about the game environment in a deceptively small file.
  
Once the heightmap and terrain shape are derived, there are textures (batches of images) which are overlaid onto the heightmap. This has the benefit of making the terrain not invisible, and also look pretty. A single texture on the terrain would be very boring, so there are multiple textures applied in layers; more of those greyscale images control the transparency of these textures, so that you get some nice-looking variance. The next time you are in a map, take a look at one of the smooth boundaries of a steep hill - you'll see the two textures bleed into one another.
  
Still, even with just terrain, the maps would look very bland and uninteresting. This is where models come into play - additional 3D geometry placed into the game world. Almost all of the 'interesting' stuff in MWO's maps consists of these models. All the buildings are models. All the destroyed bridges, all the rocks, and all the chunks of debris are models. Just like terrain, these have their own corresponding textures - but are not defined by a heightmap as the terrain is. All of these models have an X, Y, and Z coordinate position, as well as an XYZ scale (to determine how large and/or stretched the model is), and an XYZ rotation (to determine which way the model is facing).
  
Sometimes maps have water; this is a highly tesselated plane, just like terrain, except that it is non-colliding (stuff can pass through it), and the vertices move up and down all on their own, just like ripples and waves in water. This is usually accompanied by an imaginary volume, telling the game to draw water splashes instead of dust clouds when our mechs walk through it - and in the case of lava, to heat up or damage mechs. These imaginary volumes are useful in all sorts of ways - in fact, they're what tells the game that you're standing in a capture point.
  
Now it's time to begin identifying what parts of this can be automated, and develop an outline of a procedure to automate the map-making process. It's doubtful that we will ever have fully autonomous map generation, and have a thousand fresh maps released every tuesday - but we can probably use automation to step up map production to 5+ maps per week.
  
First, a randomizer needs to determine attributes about the general environment. This means determining if the map will be a forest, or a desert, or a tundra, or a city. A 'biome' if you will. This step is important, that way the game knows not to use swampy textures and desert cactuses on an airless moon. This step could be made non-autonomous, and manually set by a mapper quite easily.
  
Next, we need a heightmap for the terrain. There are already plenty of heightmap generators out there, which generate heightmaps according to criteria such as the desired sharpness and height variations of terrain features. It is fairly easy to produce random cliffs, or random mountains, or random rolling plains.
  
Specifically, for the purposes of MWO's heightmaps, once a heightmap is generated, we need to apply either a reflective or a rotational translation of the heightmap, so that there are two identical sides to the map. At this point, every hill and every cliff will have an exact mathematical duplicate for the opposing team. Then, at the boundary, we need to smooth these features via mathematical averaging of the heightmap data along any unusually sharp cuts.
  
The program needs to pick two approximately flat areas (on the heightmap, an X by X pixel region in which the value does not vary greatly) to place bases for assault. The bases will be placed in mirrored pairs, keeping each side identical so far. Conquest maps are more forgiving in this regard, and don't require perfect mathematical duplicity; a mapper spending two minutes and plopping down five conquest points in the map is completely fine.
  
After this, it is time to place major models - things which tangibly affect game balance. As you have likely noticed in-game, not every cliff is a simple chunk of geometry - sometimes, it is a wholly separate model, partially sunken into the terrain. Examples of 'major' models would be Tourmaline Desert's massive crystal spires, and Viridian Bog's mesas and clifftops that often require jump jets to access. For the purposes of the programming, 'major models' is anything that would greatly affect game balance, and provide ample cover.
  
The placement of major models would also be reflectional or rotational, so that each team gets a mirror duplicate of the map's dominating features. Similarly, the placement of these models would be governed by criteria defined on a per-model basis, to avoid cliffsides and spires inadvertently spawning inside one another and causing a huge mess. These features would only spawn if no other major models spawned without being separated by at least 150 meters or so.
  
Now it's time to make the two sides different - but not to an overwhelming degree. On the second heightmap pass, we apply a randomize effect, slightly raising and lowering the terrain, but not enough to sharply affect the already terrain-defining features. This is so the two sides do not look perfectly identical, and instead feel unique and distinct when finished.
  
Now we begin applying textures randomly to the terrain, to fit the biome specified earlier. A second pass will apply textures based upon slope and absolute height, so that there are no irritatingly awful sand cliffs or similar nonsense. A tiny bit of geometric pattern recognition in this phase would go a long way.
  
Now we can start placing minor assets, based on the (new) heightmap data. Stuff like radio towers, small rock outcrops, and pieces of cliffs jutting from existing terrain-cliffs. This, again, would be heightmap-dependent. You'll never have a radio tower try and spawn in the middle of a crater, or have a building try and spawn on a cliffside. Similarly, you'll never have the oddball-cliffside that decides to spawn in the middle of a largely flat desert; those will spawn only at sharp differences in the heightmap's value.
  
Now the program can add 'clutter' assets - stuff like random shards of gravel, cars, and trees. This is stuff that only looks pretty, and doesn't really affect the map or balance at all. These will be texture-specific, based on the existing textures on the terrain. Thus, you will never have trees growing out of a mountain of solid obsidian, or sharp chunks of gravel reminescent of rockslide-debris appear on shoreline or sandy textures.
  
Water is fairly simple as well; define a minimum height underneath which the terrain defaults to flat, and a desired uniform texture (underwater silt/mud/whatever). The water 'plane' can be placed by hand, and defining a single water volume underneath the map (except the water-covered bits) is fairly easy.
  
All that remains thereafter is fog color & density, weather conditions, sky conditions, lighting, and player spawnpoints, all of which can be placed by hand and finished into a working map quite quickly. Additionally, things such as tunnels will require a bit of love from the mappers, as that requires special transparency and noncollision within the terrain, and some manual touch-up of the seam between terrain and model.
  
Keep in mind this is an ultra-basic description of what the map-generator would resemble. Entire base-zones, flank-zones, and center-zones could be created from wholly seperate heightmaps, merged together into one heightmap and model-populated, delivering huge, impressively complex, and balanced environments by the dozen or by the hundred.
  
"But ABFalcon, having 1000+ maps in the game is bad, because it would take up more disk space than I have, or make the download take a really long time!"
  
Maps do not work that way. A map is just a heightmap for the terrain, a list of the textures the terrain uses, a few transparency maps to control which textures appear where, and a large list of XYZ coordinates that tell where the models are. It is NOT maps which take up huge amounts of hard drive space - it is the highly detailed 3D models and 2D textures which take up gigabytes of space. Once those assets already exist in the game's file architecture, a map needs only to indicate what goes where.
  
"The devs already said they weren't doing this, why bother suggesting it?"
  
Sometimes the devs cannot see the forest for the trees, and unusual or atypical solutions do not get considered. Also, for better or worse, the devs have indeed changed their mind in the past, and went back on things they said.
  
"THESE MAPS WOULD BE BORING AND RUIN THE GAME BECAUSE REASONS, RAWR, HEAR MY RAGE!"
  
Randomness existing within clearly defined mathematical guidelines will make the maps plenty interesting. In fact, they will be much more interesting than the handful of well-memorized and beaten-to-death paths resulting from having far too few maps. Imagine having to improvise and explore on every map, because the same map rarely turns up more than a few times a month. Near-mathematical mirrored maps are also much more balanced.

Edited by ABFalcon, 03 December 2014 - 12:36 AM.


#2 Appogee

    Member

  • PipPipPipPipPipPipPipPipPipPipPip
  • Ace Of Spades
  • Ace Of Spades
  • 10,966 posts
  • LocationOn planet Tukayyid, celebrating victory

Posted 03 December 2014 - 12:57 AM

I could not agree with you more.

I suggested the same thing more than a year ago: http://mwomercs.com/...ng-and-prosper/

Some people are against PGRM because they believe such maps aren't balanced. And they are right. But war is like that. When you're invading a planet, you don't necessarily get to choose the field of battle, and every field of battle is skewed one way. Part of the skill of war is dealing with skewed battlefields.

If some planet ends up with a particularly difficult or overly-skewed PGRM, then just give it a new seed number, and bingo, the problem is fixed.

PGRMs would give us:
  • infinite variety of maps, and reduced boredom of playing the same small number of maps every time;
  • a genuine boost to role warfare. Scouts would actually be needed, for example!
  • better simulation of actual planetary conquest;
  • interesting changes to the overall invasion dynamics. That is, there will be some planets where the maps are known to clearly favour the attacking or defending side, and this will in turn influence the invasion path itself.
PGRM could make this game so much better, and give it a much longer life.

If I had more time I'd be tempted to buy a CryEngine development kit and write the map generation code myself.

Edited by Appogee, 03 December 2014 - 01:02 AM.


#3 Firewuff

    Member

  • PipPipPipPipPipPipPipPip
  • Overlord
  • Overlord
  • 1,204 posts
  • LocationMelbourne

Posted 04 December 2014 - 05:38 PM

you are an idiot. your description on how "easy" it is exactly like the computer vision summer project... yeah my students should be able to solve that no problem is a couple of months, that was 1960 and its still not solved. it shows a total lack of knowledge of game theory. proceedurally you can produce "something" but it will likely not be playable or even interesting. The idea that "its just bad luck" and "war is like that" doesnt fly when it comes to games. random is bad when it overwhelms skill for a player. Trying to remove randomness is exactly what the match maker does and people constantly complain about it. That is really only a problem with a small number of variables, maps have hundreds into what makes them playable.

Major issues are
- terrain gaps and fall thoughs, hard to avoid with random terain generation.
- Mechs getting hung up on objects (people ***** about that on well curated maps)
- "Blocking path" were there may not be physical paths for all mechs to be able to pass to engaged the enemy. not all mechs can traverse all slopes the same so any hard limit will be a problems for some mech or make it boring. (no canyon maps for example)
- Lack of usable LRM cover, the number of maps that have carefully curated LRM cover to make them playable is high
- Likely to have huge advantage as a sniper and mech with JJ. Brawl would be dead.


The idea you present of mirroring the battle field is idiotic, it completely REMOVES the need for scouts. I know what it is like here I know the other side of the map instantly.

Proceedural maps have been used in flight simulators and other games before, the key point in in most of those the limitation that they imposed were either minimal or the "terrain" never got interacted with so was literally just pretties. very few games ever got this right. Even Alpha Centuri/Civ/Colinisation it was a constant problem where one player was just in a better spot so while it worked for a single player game as soon as it was multiplayer far too often regardlesss of how good a play I was it didnt matter and quickly became frustrating. Those maps were far simpler in many respects

#4 Darth Futuza

    Member

  • PipPipPipPipPipPipPipPip
  • 1,239 posts

Posted 04 December 2014 - 06:36 PM

Although creating procedural generated maps would indeed be cool, it isn't going to happen with MWO. There are a couple of reasons that Firewuff didn't mention, but are probably even more of a crux.

1) Generating a new map increases load time
2) If clients generate the map, it opens up the possibility that the map will get hacked and be used to cheat
3) If clients generate the map based on numbers obtained from the server, and the server performs map/position validation checks it drastically increases the size and number of packets needed to be sent between the client and server. This means even more network stress on PGI's servers and more lag for players.
4) If server generates the map, clients have to download it from the server (this means a 50-70mb sized download every match, say goodbye to your bandwidth, also people with slow internet will never be able to feasibly play).
5) FPS optimization is terrible and will result in even more dire frame rates then we already have (from what I've seen CryEngine is particularly bad at this and would likely get 2-3fps on these types of maps).
6) Even more work - probably couldn't expect it for at least 2 years, possibly 3 if PGI was interested in doing.
7) Randomly generated terrain introduces possibilities for a number of bad mapping bugs that significantly affect gameplay (for example, map holes that allow you to fall outside of the map, hills that are too steep/jagged, entities spawning on top of each other, etc...)

A far more simple solution is to simply make OBJECTIVES PROCEDUAL. Eg: randomized spawn points (or at least hundreds of possible spawnpoints per map), randomized capture points, randomized base/turret locations. Far less data to calculate, send over the network, but still has a significant change on each match.

#5 Burktross

    Member

  • PipPipPipPipPipPipPipPipPip
  • Bad Company
  • 3,663 posts
  • LocationStill in closed beta

Posted 04 December 2014 - 06:41 PM

View PostFirewuff, on 04 December 2014 - 05:38 PM, said:

you are an idiot. your description on how "easy" it is exactly like the computer vision summer project... yeah my students should be able to solve that no problem is a couple of months, that was 1960 and its still not solved. it shows a total lack of knowledge of game theory. proceedurally you can produce "something" but it will likely not be playable or even interesting. The idea that "its just bad luck" and "war is like that" doesnt fly when it comes to games. random is bad when it overwhelms skill for a player. Trying to remove randomness is exactly what the match maker does and people constantly complain about it. That is really only a problem with a small number of variables, maps have hundreds into what makes them playable.

Major issues are
- terrain gaps and fall thoughs, hard to avoid with random terain generation.

Quirks can be fixed, I'm sure.

View PostFirewuff, on 04 December 2014 - 05:38 PM, said:

- Mechs getting hung up on objects (people ***** about that on well curated maps)

Again, quirks that can be fixed in generation.

View PostFirewuff, on 04 December 2014 - 05:38 PM, said:

- "Blocking path" were there may not be physical paths for all mechs to be able to pass to engaged the enemy. not all mechs can traverse all slopes the same so any hard limit will be a problems for some mech or make it boring. (no canyon maps for example)

I'm not quite sure what you're saying...

View PostFirewuff, on 04 December 2014 - 05:38 PM, said:

- Lack of usable LRM cover, the number of maps that have carefully curated LRM cover to make them playable is high
- Likely to have huge advantage as a sniper and mech with JJ. Brawl would be dead.

No? How do you justify this thought?

View PostFirewuff, on 04 December 2014 - 05:38 PM, said:

The idea you present of mirroring the battle field is idiotic, it completely REMOVES the need for scouts. I know what it is like here I know the other side of the map instantly.

Perhaps not mirroring, but "balancing factors"
"Side x has 2-6 buildings, Side y will have 2-6 buildings in a different place"

View PostFirewuff, on 04 December 2014 - 05:38 PM, said:

Proceedural maps have been used in flight simulators and other games before, the key point in in most of those the limitation that they imposed were either minimal or the "terrain" never got interacted with so was literally just pretties. very few games ever got this right. Even Alpha Centuri/Civ/Colinisation it was a constant problem where one player was just in a better spot so while it worked for a single player game as soon as it was multiplayer far too often regardlesss of how good a play I was it didnt matter and quickly became frustrating. Those maps were far simpler in many respects

You surely haven't been in the roguelike department for some time. Procedural generation has been viable and is still viable, with hard work, today.

View PostDarth Futuza, on 04 December 2014 - 06:36 PM, said:

A far more simple solution is to simply make OBJECTIVES PROCEDUAL. Eg: randomized spawn points (or at least hundreds of possible spawnpoints per map), randomized capture points, randomized base/turret locations. Far less data to calculate, send over the network, but still has a significant change on each match.


At the very least, map features should be variable too. To my knowledge, cry engine doesn't use prebaked lightmaps, so that shouldn't be a problem to have buildings in different positions every now and then.

#6 Darth Futuza

    Member

  • PipPipPipPipPipPipPipPip
  • 1,239 posts

Posted 04 December 2014 - 07:08 PM

View PostBurktross, on 04 December 2014 - 06:41 PM, said:

At the very least, map features should be variable too. To my knowledge, cry engine doesn't use prebaked lightmaps, so that shouldn't be a problem to have buildings in different positions every now and then.

I'm not quite sure I understand what you mean about lightmaps, since having buildings in different positions is a physic/bounding box change problem, not a lighting/texture problem. CryEngine handles dynamic lightning just fine

#7 Praslek2

    Member

  • PipPipPipPipPip
  • 187 posts

Posted 04 December 2014 - 11:07 PM

This is a good idea that deserves serious consideration.

It sounds like a lot of work up front, with a huge payoff once it gets off the ground.

#8 Burktross

    Member

  • PipPipPipPipPipPipPipPipPip
  • Bad Company
  • 3,663 posts
  • LocationStill in closed beta

Posted 05 December 2014 - 09:41 AM

View PostDarth Futuza, on 04 December 2014 - 07:08 PM, said:

I'm not quite sure I understand what you mean about lightmaps, since having buildings in different positions is a physic/bounding box change problem, not a lighting/texture problem. CryEngine handles dynamic lightning just fine

Exactly. Source engine (HL2) is what I meant by prebaked lightmaps-- lighting is rendered once on compile.
And compilation can take hours....

#9 Darth Futuza

    Member

  • PipPipPipPipPipPipPipPip
  • 1,239 posts

Posted 06 December 2014 - 07:51 AM

View PostBurktross, on 05 December 2014 - 09:41 AM, said:

Exactly. Source engine (HL2) is what I meant by prebaked lightmaps-- lighting is rendered once on compile.
And compilation can take hours....

Ah okay, I see what you mean. Yeah rotating models around/etc would probably be feasible.

#10 Erebus Alpha

    Member

  • PipPipPip
  • Survivor
  • 81 posts

Posted 06 December 2014 - 12:38 PM

To clarify, what I mean by 'procedural generation' is the automation of most of the mapmaking process, not all of it. The maps would be generated at PGI and included with the game client with each update. It would not be truly autonomous procedural generation. The maps would not be made instantly before the match begins. The idea is instead to fill up the map-randomizer with so many maps (a few hundred or a few thousand), so that the odds of being on the EXACT same battlefield in any given day, or week, is quite low.

Truly real-time procedural generation of single-use maps immediately before matches would be almost insurmountably difficult. It might be possible to remove the human element from mapping completely, but the equations to do it would be ludicrously long and complex. The development time and expense for 100% autonomous, balanced, interesting, and awesome map generation likely exceeds what PGI/IGP is willing (or capable of) undertaking. Such would probably require a server rivaling something at NASA, CERN, or the USS Enterprise.

99% autonomous map generation would be much easier, and still yield enormous benefits in terms of balance and environment diversity.

Edited by ABFalcon, 06 December 2014 - 12:39 PM.






6 user(s) are reading this topic

0 members, 6 guests, 0 anonymous users