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!

Procedural Content Generation on a MOBA genre videogame - Part 1

Its been a year since I started doing research on Prodecural Content Generation (PCG), and on October 28th I presented my thesis project, getting the highest grade, yaay!

As the title says, the project was a prototype of a videogame of the MOBA genre (Multiplayer Online Battle Arena, think of League of Legends, Heroes of Newerth, Dota, etc...), and it involved creating a MOBA game that relied heavily on PCG to create most of its content, thing that hasn't been done that I'm aware of.

On the common MOBA, developers provide most of the content of the game in the form of new and interesting characters to play. Each character is supossed to be new and refreshing in order to stand out among a huge pool of characters. The problem here is that the more characters the game has, the harder it is to create new ones, and thus comes the problem of the constant rebalancing that (I mostly play LoL or Dota 2 so I will be using those for examples) the developers have to go through. For example: whenever LoL spawns a new champion there is always a rebalancing update involved, because the new abilities brought by this new champion overshadow other(s) champions in some way, making them less viable, and since the idea of having a ton of different things to play with is to... well... play with them, the developers are forced to make changes here and there to make everything fit and make every champion kinda stand at the same height in the matter of viability (although in competitive gameplay we all know this is not and probably will never be the case).

Because of this issue regarding the creation of new characters to bring variety to the game, I thought about a solution for this problem and came up with an interesting solution, instead of having a lot of carefully crafted characters, every player would start a game with the same character, and then throughout the game, these characters would adapt to the play style of the player and change their appearance and attributes accordingly. I've called this the Character Adaptation System.

Before I get to explain the CAS I want to talk about the map. If you have played any MOBA you know that theres little variety on the maps you play. It's usually the same map over and over and over and over and over and over again and again. I'm not saying this is a problem, but who doesn't like to experience the refreshing feeling of traversing a place for the first time? This is seen on Minecraft or any game with a procedurally generated world, new content is always welcome by players and gives a nice touch to the overall experience.

Personally I think that this staticity presented on MOBA's maps comes from the fact that designing a map is hard, thus it's not worth it to create different variations of a map that is in the core the same. The best example for this is the Magma Chamber map for LoL that was never released because the designers concluded that it was just the same as Summoner's Rift but bigger (which also led to longer games). The developers didn't want to spend time developing the same thing they already had on Summoner's Rift, so they scrapped the map and created instead The Crystal Scar, which also brought with it the Dominion game mode. Both the map and the game mode are awesome and extremely fun to play, but with this you can have an idea of the consequences involved in redisigning a map just to have a different layout of roads and things like those, its hard, so hard that the developers rather not waste time on that, and I get it, it's actually what makes sense.

But since I felt like I could address this problem (and also because I'm a PCG addict) I decided I would come up with a way to generate the map procedurally so that everytime you play a game the map is different, and I'm not talking about slightly different positioning of the towers, lanes, camps, etc... I'm talking about design concerned different, where the change is so big that it has real impact on how the map is played.

With this in mind, I created a system that is capable of procedurally generating the map from scratch, focusing on the river and the jungles (which covers a huge % of the map). The other stuff like lanes and bases generation don't have much impact on the design of the map.

This is a map generated procedurally by the system I created.

This is the video showing how the whole game works, it pretty much sums up all the features it has.

And this is last build I made. It still has some bugs here and there, but thats the final version of it.

IMPORTANT:

• To be able to connecto to a server hosting the game, the server must be connected directly to the modem (for some reason I'm not aware of, Unity network interface wouldn't let me get through routers).
• If you are hosting a game and it's running at non-playable fps, try leaving the "Spawn Minions" checkbox unchecked before hosting the server.

Content information:

• The Ancient, towers and terrain textures belong to Dota 2.
• Ashe and Blitzcrank (the melee and ranged characters you can play) as well as the minions, belong to League of Legends
• The rocks and trees where made by Anguel Roumenov for another project we are working on. You can check out his work at sohardtoremember.com

Well, thats it for this post, on Part 2 I'll be talking more specifically about how the map was generated and will explain implementation related stuff so you can have a better idea of how this was achieved. On Part 3 I will explain how are the characters modified throughout the game and how the Character Adaptation System works to achieve this.

Feel free to leave a comment if you have any questions related to the game or how did I get the content from Dota 2 or LoL

Caracas GameJam's 2013 Beatventures

Beatventures, that's a nice name isn't it? It's the name of the game my team made at the CGJ2013, but first of all I must talk about the theme.

Last years theme was an image of Ouroboros, and we had areally hard time figuring out what to make of it (if you want to read more about that, here's the post). This year... well... it wasn't even something visible, it was a sound, a heartbeat to be precise, and obviously the first thing in everyone's mind was this:

Well, a heart, you can do great deal of stuff with a heart as a premise, sure you can. So we started our painful process of figuring out what the hell to do with our game, should the player be a heart? should the player defend the heart? We thought of many things, we even thought of doing a beat-em-up where you are the heart and fight food that is bad for the heart, like fries, hamburgers, etc, I honestly loved that idea because it was hilarious, but it was a heart and our team wanted a more abstract aproach to the theme than just playing a heart, if possible we wanted no heart to be present in the game at all.

The hours passed, food eaten, drank unhealthy amounts of coke, and then drank more coke and coffee too! the usual thing. Talking about usual, our team was spending a really long time thinking about what the game should be, which is something we seem to love too much. We were throwing random ideas on the board, going back and forth between old and new ideas, we were getting kinda desperate, at least some of us.

We were stuck, we were making no progress, so I went out of the room to get some water, and do my usual walking & thinking (just so you know, my mind seems to work 300% better when I'm walking and talking to myself), and did that for around 10 minutes, trying to go back to square one and think of a new idea from there. I thought about a character in a maze looking for something, and the closer he got to that something the faster his heart would beat, so I went back into the room where my team was and talked to them about that. We spinned the idea around a bit but in the end it was no good, althought part of it seemed to mix with the other ideas we had.

In the end, just like always, after hours and hours and HOURS of discussing (and drinking coffee and coke, of course) what the game should be, we all finally got to the same place, and decided to make a rythm game. I'm sure the whole team loved the idea.

The game had this nice mechanic, were you could only move if you were in synch with the beat of the song playing. Fantastic, I'm in love with that idea, and even more with the idea of mixing that with a top-down game where you usually have free control over your movement.

Relieved that we finally could start working at around 3 or 4 am, we began to do our jobs. This time, we had split the tasks nicely, we had one person dedicated exclusively to the music (which was hella important, rythm game remember?), other dedicated to the art and the rest of the team (three) to programming. Yikes we are finally making this game happen!!!! 

Along the way we met a friend that had been present the last jam, and although he wasn't participating, he dedicated a lot of his time there helping with the art assets and teaching our artist, so by the end of the jam we actually had 2 artists.... YAY! FRIENDSHIP!!!

Ahem, anyways, near the end of the jam we were stressed, screaming "WHY WON'T YOU WORK?! WHYY?!", hitting the keyboard with our faces, it was a pretty rough moment... Well honestly it wasn't like that, but try to imagine that happening in everyone's head at the same time... Actually, that's a lot closer to reality now that I think about it.

THE JAME ENDED!!! WOHOOOO!!! WE MADE A GAME IN ONLY 48 HOURS!!! MWAHAHAHAHA!! I admit it always feel like that, which is awesome because, well... it is. 

Our team, Origames, made Beatventures.

All the other games were really cool and I really loved what people made just from a heartbeat. I must mention that this jam was huge for us, we had around 67 people in the end participating out of 70, we were almost full! and 18 games were made!! That is plain AWESOME, the people involved in making this happen are just AMAZING :)

This photo belongs to an entry from the CGJ organizer's blog (you should check it out), Ciro Duran.

Thanks for reading, go make games will ya?

Toasty-Arepa!

And this is the near-less-than-4-months-future!! Aren't we all glad? So as I promised, here's all the art that we used for the game Toasty-Arepa! I just love it, when I came up with this idea I couldn't believe that something so simple would look so nice :O.

Of course this isn't all the art, there are more funny things but I chose these so you can get an idea of how it looks, and I must say again, I LOVE this art, looks pretty nice for me.

Sadly we didn't have enough time to show the "comic" telling the story so.... JUSTICE MUST BE MADE!!!

Enjoy.

What up??

Phew! I've been really busy lately! Spent summer doing my internship at a game development studio and investigating for my seminar, really busy.

A month ago my ninth semester started and I've been attending to classes, the usual stuff, oh and also participated in another game dev contest :D. Well this was a bit different since it wasn't the usual "melt your brain in a weekend to finish a game", this was a contest made during an event that happens anually where I study, it's called CEIDEC.It is mostly a bunch of science expositions, you know, a lot of importat people exposing their ideas and projects. Sadly i couldn't attend to any of the presentations I was interested in since I was working *sadface*.

So the contest, well we were given a whole week to develop a game, they gave us a subject just like in the good 'ol Global Game Jam. The problem this time was that, we had a lot of time, but we also had a lot of homework so we weren't in the best shape, yet we amazingly pulled an almost complete game in almost just 24 freaking hours of develop (this doesn't include the art, but that didn't took too much time anyway), that's just insane in my experience, but we also owe it to Unity which is just like magic, you just drag and drop until your fingers bleed and BOOM it's a game!

Ok, the game, right, thats important isn't it? The subject they gave us was "Hybris" which is a term used to denote something that is exagerated or excessive in some way, well that may not be the accurate definition but that's how we interpreted it for our game, which by the way was called Toasty-Arepa (if you dont know what an arepa is you should google it, easier than explaining it (yezzz the lazinezzz).

So what's this Toasty-Arepa about? well the story we came up with was a girl that was really really REALLY disastrous, she did things so wrong that she would create portals to other dimensions, pretty much what we all know would happen if someone divided by zero. So what she did wrong in this case was that she tried to cook an arepa in a toaster (nonsense, by the way) and this created a portal that transported her to a weird dimension where nothing but the floor seems to make sense at all.

The game is a simple platformer where the world was generated randomly. The objective of the player is to reach the portal to escape before the time runs out (which is when the toaster finishes "toasting"). To annoy the player there are these weird flying thingies that would just watch the player and suddenly (if given enough time) would attack mindlessly, or at least that was the idea any way. The player also has this ability to becom invinsible and kill everything they touch, but this drains their HP so they can't spend too much time in this state.

Sadly we couldn't finish enough of the game, but what the hell, the game looks nice and it was done in a really short time so yay!!!... next entry will have the art and the link to the game so you can take a look.

Oh and we decided to finish this game :) so I should be writing about it in the near-less-than-4-months-future!