Procedural Content Generation on a MOBA genre videogame - Part 2

This is the last part of my post about my thesis project, I recommend reading Part 1 if you haven't already! If you want to skip to the Character Adaptation System go to Part 3.

Procedural Map Generation

Before starting to implement the algorithm that would generate the map procedurally, I needed to do some research on the design of a common MOBA map. For this I used Dota 2's map because it's asymmetrical, why asymmetrical? well, had I used a mirrored map like League of Legend's then there wouldn't have been much of a challenge in generating the map since the balancing of both sides is guaranteed when it's mirrored.


Dota 2's map design notes:

When I talk about balancing the sides of the map I mean that no team has an advantage related to certain topology on their side of the map. Thus, the first rule of the map generator was that the difficulty of traversing the map should be as similar as possible for opposite sides of the map.

Having defined the first rule, I started to analyze how the Dota 2's map was designed. The map isn't symmetrical and yet it offers very similar possibilities for both teams, which is the target of this map generator.

River: The river represents the fastest way of traveling between lanes, but of course comes at the cost of high risk of being assaulted by the opposing team.

Lanes: These must be traversed entirely in order to access the enemy base, meaning that a team is forced to destroy the towers of at least one lane in order to have a chance to win

Towers: These are placed along the lanes to provide defensive measures for each team. In the case of the outer turrets (the ones outside of a base), these are positioned in a way that will ensure that a player traveling between turrets will have to go through a red zone, thus giving the other team a chance of attacking. Green and yellow areas represent where the player can be near an allied tower and be the safest.

Danger zones near outer towers.

Jungles: If we divide the jungles on the map by lanes and the river we end up with 4 sectors that contain the 4 jungles on the map. These jungles have very different paths but they all offer 3 specific roads that will be shown on the fitness functions section below.

After analyzing these aspects I realized something, the MOBA is, at the very core, just a game of attacking and defending turrets. We could get rid of the Ancient, bases and even the lanes, as long as there are turrets and ways of attacking and defending them effectively, the game would still be played as a MOBA. Through this reasoning I decided that I could take a lot of freedom modifying the composition of the map to my liking, but to not overscope the project, I decided to just focus on the generation of the jungles, which covers a big chunk of the map and modifying them haves great implications in the overall flow of the game.

Implementing the map generator

The objective then was to create procedurally a map that followed the design rules taken from Dota 2's. Everything would be procedurally generated, although only the jungle and river would change enough to have an actual impact on the game.

After doing some research on the best ways to create complex maps (contaning structures and a lot of constraints) I found 2 ways of doing this:

• Generating the map by chunks:

1. Add a first random chunk
2. Evaluate if all the chunks follow the rules defined. If they don't, go to step 4, else go to step 3. If the map is full this loop is terminated
3. Add a new chunk and go to step 2
4. Delete the last chunk added and  go to step 3

•  Generating the map randomly:

1. Generate a complete map randomly
2. Evaluate if it follows the rules defined. If not, go to step 3, else terminate the loop
3. Create a new randomly generated map and go to step 2

Both are viable methods and probably carry the same processing load, but I decided to generate the whole map randomly because this way I was able to use a genetic algorithm and I think these add a nice amount of randomness to the whole process that is always welcome when using PCG.

The common genetic algorithm uses a fitness function to determine which of a set of candidates is better. Usually these algorithms iterate over this set of candidates making new generations and mixing their traits to imitate the behavior of genetics in nature.

Using a fitness function F1 we can evaluate if a candidate has a path connecting the points A and B, and therefore determine which candidates have this characteristic. But when using complex candidates (like the maps to be used in the game) where theres a lot of information that needs to be processed in order to determine if its a viable candidate, the fitness function becomes a bit messy.

To address this problem, I used whats called a Multi-Objective Evolutive Algorithm, which basically consists of using more than 1 fitness function to evaluate all the candidates. So we can still have the fitness function F1 doing it's thing, and we can add a fitness function F2 that evaluates if there are obstacles between the point A and B. As you can see, we are interpreting different information from the same set of data, which is exactly what I needed.


Candidates creation:

With the next pseudo-code you can see the process behind the creation of a map candidate:

The jungles are created using a fractal algorithm provided by the AccidentalNoiseLibrary and the camps of each jungle are placed near unwalkable areas where the size of the camps fit.

Fitness functions: 

• Jungle roads: Each of the 4 jungles must guarantee that there exists:

• A road from the outer turret of the side lane to nearly 1/3 of the river
• A road from that point of the river to the center of the middle lane
• A road from the center of the middle lane to the starting point

 The red lines represent the boundaries of the jungle. The roads must exist within these boundaries.

• Camps difference: The difference between the amount of camps on the 2 jungles on each side of the map mustn't exceed a certain threshold 

Displaying the map:

After having selected the best candidate according to the fitness functions defined, the drawing process begins:

1. A Bezier curve is drawn between each control point outlining the river to make a nice and smooth river.
2. The intersection points between the 3 lanes is placed near the diagonal of the map. The position of each base is placed and then the lanes  and bases are drawn.
3. Using the intersection points of the lanes and the position of the bases, 4 triangles are drawn that represent the boundaries of each of the 4 jungles. Inside these triangles, the fractal algorithm draw the roads.
4. The camps are drawn according to their positions.
5. Trees are placed along the green or unwalkable areas.
6. Structures are placed and the game can begin.

Sample map generated procedurally. Yellow dots are the camps and green areas are unwalkable.

 
Well, that's a really brief explanation of the whole process I used to make the map of a MOBA game be generated procedurally. On Part 3 I'll be explaining the implementation of the Character Adaptation System.

Thanks for reading!