## Choosing between Behavior Tree and GOAP (Planning)

I would like to expand the answer I gave on /r/gamedesign some days ago. The main point of the question was: how can I decide if it “better” to implement the decision-making layer of our game AI with Behavior Trees (BTs) or with more advanced plan-based techniques such as the Goal Oriented Action Planning (GOAP) or SHOP.

## GameDesign Math: RPG Level-based Progression

Level-based progression is an extremely popular way of providing the player with the feeling of “getting stronger”. The system is born with Role-Playing Games (RPG), but it is nowadays embedded in practically every game; some more, some less. Even if it is perfectly possible to provide progression feeling without levels and experience points, level-based progression is easy, direct, linear and fits well in many (too many?) game genres.

But designing a good experience-level progression is important. Many games do that without much thinking. They just slap experience points and level and that’s it. The general idea is that the more your level is big, the more experience you need to advance. This is true, but it is just a small part of the design. Because in game design, you must keep in mind the effect of your gameplay element on the player and must be useful to convey the emotion you want to convey. Not the other way around.

I cannot give a full analysis of level-based progression system, but I can use simple math to explore the effects, limits and the design space of it.

## Why using a level-based progression system?

Judging from the amount of games that have a level-based progression system in place, the real question is “why not?”.  However, whenever we see something extremely successful we should ask ourselves why it is so popular.

The reason is: to give the player a sense of progression. Players want to see that they are getting stronger. And there is no better way than see “numbers getting bigger”: levels, damage, HPs. The player has spent hours playing to become powerful and these big numbers are here to prove it!

In many games, our skill is cannot be directly measured. Sure, we can feel this warm sense of progression in Super Mario Bros when we go back to the first level and we can go blazing fast. But this is nothing respect to the feeling of going back to the starting place and dealing ONE MILLION DAMAGE to that level 1 monster that gave us so many troubles.

But there is also another reason designers like to introduce levels in their game. They are a handy way for the designers to control the flow of the game. And they offer to the player a clear indicator of this too. Nothing stops a player from rushing through the game like slamming a monster several levels higher than the player on the player’s way. This kind of artificial difficulty can be done extremely badly and when it does games can be screwed by this. But if well-tuned, it is really effective.

Another question is: if we like big number, why use levels in the first place? Why we do not just use experience points and offer a “smooth” progression? Because it’s not satisfying! We want to see number get bigger, but we want to perceive the change. That’s the reward after the “work”.

It is just like eating a pizza. We can eat a pizza on the week-end after a week of strict diet, or we can have just a couple bites of pizza every day. At the end, we will probably eat the same amount of pizza, but I think one solution is definitely more satisfying than the other.

## Understanding the progression mechanics

Now that we know why we use level-based progression, it is time to play with some number. Note that this is not necessary, but understanding the math behind gameplay elements is a pet peeve of mine, and I think is helpful to understand better what and how to change something to achieve a particular goal. Also, because if you don’t do the math, your player will do it for you.

At the basis of level-based progression there are experience points. Mathematically speaking, level progression is a function mapping a certain amount of experience to a certain level.

$L = f(E)$

When designing the level progression, we are designing this function. How much experience (ad so time) players have to invest into the game to gain a level?

In practice, however, when designing a level-based progression, it is easier to find the inverse function: that is a function that, given a leve, tell use how much experience we need for this. This is usually called experience curve.

We can already have some intuition. If our experience curve is linear, then every level need the same extra amount of experience: 10 for Level 2, 20 for Level 3, 30 for Level 4 and so on. If our experience curve is exponential, we need always more experience, and therefore we level-up slower at the end game. If our experience curve is logarithmic instead we need always less experience and, therefore, we level-up faster the more we play. They are all valid experience curves, everything depends on what kind of game you want.

Here, we will explore the most famous experience curve, the exponential one. The exponential curve is constructed starting from a single concept. Suppose you have a first amount of experience at level 1: $a$. In order to reach level 2 you want the player to double, triple, etc., your initial experience. So

$E(2) = a + ba$

That is, the experience at level 2 should be the starting experience plus $b$ times that. For level 3, we do the same, we wont to have $b$ times the increment at level 2.

$E(3) = (a+ba) + b(ba) = a + ba + b^2a$

In general, at level $L$:

$E(n) = a + ba + b^2a + \ldots + b^L$

That is a geometric succession, that can be luckily be expressed in closed form.

$E(L) = a \frac{1-b^L}{1-b}$

See? A nice exponential experience curve. But this time you know why it is like this. You know the meaning of the parameters and how to tweak them in order to obtain what you want.

Given an experience curve, one of the importan properties we can infer is the level progression over time. How fast a player will travel along the level progression from the bottom to the top? How much time the player need to put into the game for leveling up from 10 to 11? And from 79 to 80? How can I tune the experience of a certain area?

These are all interesting question. We can find an answer by looking at the experience curve. First step is to invert the function to obtain the level progression function, that is, how level advances given the experience.

$L(E) =\frac{1}{log(b)} \log(\frac{a + (b - 1) E}{a})$

Who. That’s ugly. But there is just some parameter noise. For the sake of the discussion, we assume $b = e$ (that’s not unreasonable) and $a=1$.

$L(E) = \log(1+ (e - 1) E)$

Much better. Now, we need to consider the experience a function of time. Obviously, we cannot know a real function for that, but we can general idea of “how much experience we expect the player to collect at each time”. Do we expect the player to get always the same experience over time? Do we expect to get always more experience? This is very common and implemented  with high level monsters or quests giving more experience points.

Then, we can derive some kind of leveling speed function.

$\frac{\partial L}{\partial t} = \frac{(e-1)}{(1 + (e-1) E)} \frac{\partial E}{\partial t}$

And here I stop for now. I like this stuff but, more than this is probably unnecessary. The important thing is that you try to model your progression in function of time by inverting the experience curve and plugging in some “experience function”. This will help you in having a rough estimate of the time and effort needed for leveling up in your game.

## Real Case Examples

How are experience curves for real cases? Pretty much similar. I’ll give you the example of RuneScape.

$E(L) = floor \left( \frac{\sum_{n=1}^{L-1} floor \left( n + 300 \cdot 2^{\frac{n}{7}} \right)}{4} \right)$

That’s definitely a more complex formula. Why is done like this? No idea. However, we can identify that it is an exponential function, in the same spirit of the one discussed above.

World of Warcrat legacy formula instead is not analytic. Instead, we have a formula for the experience required to level up at a certain level.

$\Delta E(L) = ((8 \times L) + Diff(L)) \times MXP(L) \times RF(L)$

Where $Diff$ if a difficulty factor, $MXP$ is the basic experience given by a monster of level $L$ and $RF$ is a generic scaling factor. This formula start as a quadratic experience curve and then explode into exponential (thanks to the Diff formula). Giving us this strange shape (note that this is the derivate of the experience curve).

In Diablo 3, instead the formula is a nightmare (there is a typo in the formula, but I do not want to rewrite this in LaTeX on WordPress…).

Where $y$ is the $\Delta E(L)$ and $x$ is $L$. Why are this constants chosen in this way. I don’t know. Probably a fine tuning.

## Conclusion

In the end, I hope you have fun with experience curves. There are thousands of different way to do them. Just remember that it is not just and always an exponential curve. Time and experience are linked together and modeling the experience curve can give you a lot of insight on how to avoid “grindy” parts in you game and keep the player in the flow.

## Seasons Generation from Orbital Parameters

Welcome back to part 3 of the Procedural Calendar Generation series. In the first part we looked on how to compute celestial body position in a simple two-body system. The second part, instead is crash course on ellipse geometry.

In this part, instead, we will tackle a fascinating consequence of the cosmic dance of our planet around its sun: seasons. Seasons are a strange beast because their behavior depends on a huge amount of factors. We are used to our four seasons with mild springs and autumns, hot summers and cold winters. But these four season are just the consequence of our planet ecosystem, atmosphere, the peculiar axial tilt, if the orbit is particularly eccentric, distance from the sun in different period of the year can be a strong modifier too! In multi-star system, we can have more than 4 seasons, in planets with strange mechanics we can not have seasons at all (or better, the “season” depends on where are you on the planet).

During the last few weeks, I’ve seen over and over people saying that Cuphead is hard. That it is brutal. That is the “dark souls of the side shooter”. For this reason, before this trend goes too far, it is time to make things clear: Cuphead is not hard.

## Crash course on basic ellipse geometry

Because I started a small series about astronomical algorithms and the magic of math in space, I think we need to cover an important prerequisite. In the series, I will talk a lot about ellipses (duh), I will move from the semi-axis majors, to the periapsis, to eccentricity, to ellipse’s center and ellipse’s foci. I am concerned that things can get more complicated than expected if the readers does not know many of the geometric properties of the ellipse. For this reason, I put here this vade mecum on the ellipse geometry. A summary with all the basic points and lengths. A place that I can link everywhere I need to refresh a definition.

## Playerunknown’s Battlegrounds did everything wrong. And doing so, it won.

This small article is born from a discussion I had with a friend of mine this week. He was writing a review on Playersunknown’s Battlegrounds (from now on, PUBG) and he ended up talking about the evolution of the genre and its triumph over every other competitor. The article was good but it did not enter in detail about, what I think, it is a greatly important and interesting question: Why PUBG? Why not any of the other dozens of battle royal games we were plagued in the last years?

PUBG is clearly a winner in this competition. It sold more than 8 million copies on Steam only, and I can see the trend going with the future release on consoles. The problem, in my opinion, is that, on paper, there is nothing in PUBG implementation that seems “right”. Nevertheless, it won.

Machiavelli once said that success is 50% luck. That’s definitely true for PUBG. But the other 50% must be researched in the PUBG qualities. Analyzing them, despite the massive “errors”, it is very important for any game designer.

## Against Addiction and Gambling-like Mechanic in Free to Play Games

I want to take the cue from a last week massive Reddit thread on micro-transaction in Free2Play (F2P) games to give my opinion of the topic. I think it is important. We need to increase awareness that predatory practices in F2P games are incredibly close to gambling and share with it the same self-destructive and harmful addictive behavior. This is wrong in so many way: it is dangerous for the victims, it is dangerous for the game itself, and it is dangerous for the entire F2P model.

The Reddit thread presents this as a new discovery, but it is not. The trend is clear for a long time and there are a lot of discussions on the topic. Before we try to find a solution, let’s look at the different faces of the problem.

## The Micro-Gambling Addiction: The User Perspective

When we talk about predatory marketing behaviors in F2P games, we talk about all that practices implemented to encourage/force people into spending more and more money in F2P games using excessive addiction/gambling inspired techniques. Every developer tries to make people spending money on their game. However, sometime F2P games push this too hard using addictive design mechanism with the goal of “trapping” people willing to put in the game unhealthy amount of money. And they do nothing to prevent this.

A common misconception when talking about this is that people usually assumes that the target of Predatory F2P games are the children. After all, we usually look to children as vulnerable creatures that can be easily tricked with games. This is wrong. Predatory F2P games targets are the so-called “whales”: people who can spend thousands of euros per month on a game. Children have no money, they cannot be whales.

In order to survive, F2P games need to catch some whales, and to do that they aim to vulnerable people using gambling-like techniques. We are talking about depressed people, people who had a big loss, people who have problem at works or in social context, people not satisfied with their life. F2P games give to this people a community, a goal, a deep sense of accomplishment. But in Predatory F2P all this comes with a price: a price these people need to pay to continue playing, to not let down their community/clans, to be competitive and continue to feel accomplished.

It is hard for people without these problems to understand how a person without a job can spend 3000$in one session on MapleStory in order to craft a single weapon. But it happens, more than you think. ### Is F2P Addiction as Gambling Addiction? If this remember you something, you are right: gambling addiction. Let’s look at the symptom of gambling addiction (from here) and see if we may relate them to F2P addiction. • obsessing over any type of gambling – replace gambling with games and, check. • gambling to feel better about life – As I said before, check. • failing to control your gambling – This is clearly obvious for people spending 10000$ on a F2P game.
• avoiding work or other commitments to gamble – Check.
• neglecting bills and expenses and using the money for gambling – Sadly, check.
• selling possessions to gamble – I am not aware of these cases, but I am sure that it is because I didn’t look well enough.
• stealing money to gamble – Check.
• feeling guilty after a gambling session – Check.
• taking bigger and bigger risks while gambling – This require defining “risk” in F2P game spending, but I can assume that for F2P whales, there is a tendency of spending more and more with the time passing.

In my opinion, gambling addiction symptoms map with my experiences with F2P addicted people. But, unlike gambling, there is no warning, there is not the same public attention and F2P addiction is definitely hard to be recognized as a real pathology.

## The Micro-Gambling Addiction: The Game Perspective

This concept is extremely well explained in the above video. I’ll try to summarize here the key points.

Because F2P games require whales to survive and because a handful of whales can represent 95% of the game revenues, the game slowly shifts their focus toward a whale-centric model. This is reflected in games becoming less and less fun for non-whales players. That’s how Pay-2-Win games are born.

But that’s not all. Games need non-whales customers, too. They need them, because they are the game population segment that feed the whales’ sense of accomplishment. Why I need to by that amazing sword if there is no one to crush with it?

This force the game to acquire new players faster than how the existing players quit. This, in turn, increases the advertising cost and exposure. Now, instead of a pay-2-win game, we have an annoying pay-2-win game with advertising popping up everywhere.

The self-feeding loop will continue indefinitely until the game is no more sustainable, leaving behind a battlefield of indifference or disgusted players.

Did the game improve over time? Did it leave a good memory to the old players? Did it offer a refreshing and fun experience? No. It trapped the whales into it as a parasite and pissed of everybody else. These are not the kind of products developers are proud to work in. These are not what games should be.

## The Micro-Gambling Addiction: The F2P Model Perspective

The last victim of this practice is the F2P model itself. The F2P model is a good model. There is nothing inherently bad about it. Actually, F2P has many benefits, it allows everybody to play it and allows people willing to spend money on it to spend the amount of money they think the game is worth, and more.

Though, predatory F2P is actively damaging the F2P model itself. If the trend did not stop we will face the following problems:

• Game studios that do not want to implement unethical marketing/design practices can go out of business because the finite amount of money of the F2P market is absorbed by those gambling/addiction-based games. Thus, making the F2P market less interesting for the majority of players.
• F2P games in general may start to have a bad reputation among the core of the gaming community. In turn, this drives people away from the model. We can already see how F2P has become a term with which gamer “insult” games.
• Governments may start acting in an indiscriminate way. Because we rarely see politicians understanding the technology they are going to regulate, I am sure that if something will happen will hit hard all the F2P model regardless of how much unethical their practices are.

We can already see some of these points in action and things are not going to improve in the foreseeable future.

## Defending people from micro-gambling

Here it comes the final question: how can we stop this? As individual, we probably can’t. We can avoid such horrible F2P games but we do not make a difference. Only the “whales” matters.

But this is not a reason to stop trying. Here a simple list of things you can do.

• Spread awareness of the problem. For now, this is not perceived as a social issue. But we have seen it definitely is. There clearly people out there that are putting themselves in financial problem territory with some game. This people need help. And nobody will help them if they think there is no problem.
• If you know people affected by this kind of addiction try to help them. If they are not in such deep problems, keep an eye on them. Addiction is easy to snowball in much bigger addictions. Don’t be ashamed. We have reached the point where it is not a shame to ask for help for somebody spending too much at Poker. It is the same for people spending too much in some F2P game.
• Every time it is possible, mark the connection between gambling and F2P predatory practices. Make clear that some games are using gambling related techniques. As the original Reddit thread suggest, if we stop using a generic micro-transaction for gambling-like mechanics in F2P games, it is easier to make people aware of the problem. Moreover, it will separate good F2P from bad F2P.

If you are a developer, instead, the obvious suggestion is to avoid to put heavy gambling inspired techniques in your game. I know that sometime they are accidental. But there are two easy tricks:

• Try to make purchasable content not necessary for the game. A splendid example is Team Fortress 2 and Dota 2. In TF2 everything can be dropped, or can be bought to save time. In Dota 2, everything on sale is just cosmetic. This remove the urgency for people to buy stuff to be competitive and, at the same time, it allows people deeply involved in game to buy something to look cool.
• Try to put a limit on the amount of money needed to unlock contents. If there is no more than X amount of € of contents per year it is impossible for vulnerable people to spend 3000€ in a month. For instance, you can release your game as F2P and,  when a single user buys a certain amount of F2P contents (e.g., 100€ or more), he/she unlocks the full game. For instance, this is done in Pokémon Picross, where the user can grind everything in a F2P fashion, or can buy the equivalent of 15€ of stuff to have complete access to the game contents. There are many other examples of this.

I am open to hear more solutions for this problem. If you have any other trick to help F2P addicted people, send me a message and I will update this section!

My definition of gambling-inspired micro-transaction (randomization of the outcome, unlimited spending, payed content required to be competitive) is quite broad. Writing this article, I realized that this definition includes games such Magic the Gathering or Hearthstone because of one of their core components: booster packs. Are booster packs considered gambling? Well… technically yes. It is, in fact, possible that people get addicted to such mechanic (I personally I think I had some physical addiction to the smell of freshly unpacked booster packs). The feedback of excitement and punishment/reward of opening a booster pack is exactly the same of spinning a slot machine.

I think there is a subtle difference though. Booster pack always gives you something of value that can be used or exchanged to get the card you really want. Evan virtual TCG games implements such mechanism in attempts to attenuate the gambling aspects. For instance, Hearthstone allow you to disenchant duplicated card and use the resulting materials to “craft” a more valuable card. Sure, it is not a zero-sum process, but it is better than a slot machine.

For this reason, I think they can give the same problem in some cases, but in a more light and controllable form. They lay in a gray area.

Again, I do not want to ban gambling-like mechanic. I want to make people aware of the problem so that we can protect vulnerable people.

## Improve Inventory-Aware Pathfinding with Map Preprocessing

In the last article we introduced a basic approach for Inventory-Aware Pathfinding (IAP), a pathfinding algorithm capable of interacting with obstacles and not just avoiding them. If you have not read it, I encourage you to go back and read it to understand the basic challenges and the main ideas behind the proposed solution.

For instance, we can have a pathfinding algorithm that can solve small plans and “puzzles” involving reasoning like “before passing this door, I need to get that key”. This is definitely planning territory. However, if we focus on a small subset of the problem, we may squeeze the algorithm into the pathfinding search itself.

In order for the red NPC character to reach the King, he needs the KEY to open the door. But to get the KEY, he needs to give the MEAT to the DRAGON. But to do this he needs to kill the SKELETON with the MAGIC AXE. Or he can talk to the MONKEY and get a SPECIAL ARMOR that allows him to pass the LAVA RIVER.

We have already seen that, if we focus on this type of item-related problems, then we can tweak the problem in such a way it can be naively solved by a traditional pathfinding algorithm with just a minimal set of changes.

Unfortunately, the resulting problem grows exponentially with the number of collected items. If a pathfinding algorithm is not good at pruning the search space, it can barely solve problems with more than 2-3 items on the map.

To solve this problem, we can use smarter algorithms (like Jump-Point Search) and push the limit to 7-8 keys/items on the map (that are more than enough for many games). However, using this simple approach we cannot avoid the main drawback of IAP. If a path cannot be solved, the algorithm will lose time by searching  into a huge amount of “copies of the original map”.

## Randomness in PCG is about the result, not the parameters

I feel the urge of stating the obvious: randomness in Procedural Generation refers to the perceived randomness of the outcome; not the randomness of the input parameters.

In some sense this is “obvious” but, at the same time, is one of the most common mistake I see when developers tackle procedural content generation in their games. It is an understandable mistake, though. There are two assumptions we subconsciously make when we approach randomness: 1) we think that uniformly random  parameters produce uniformly random outputs (that’s blatantly false), and 2) we think that uniformly random outputs yield to uniformly random perception in the human (even more false).

These are two easy points to fail at design phase. How we will see later, even big companies find out the “obviousness” of these two points only years after their product release.

## Randomness in the output

First, we need to convince ourselves that it is false that uniformly random input parameters produce uniformly random results. For this, we can imagine a PCG algorithm as a function that takes some parameters $x_1,x_2,\ldots x_n$ as input and returns something $y$ as output. The wrong assumption is that if we replace $x_1,\ldots x_n$ with random variables $X_1,\ldots X_n$ with a uniform distribution, then the function will return a random variable $Y$ with uniform distribution.

A trivial counter example is the function $f(x) = 0$. I think it is clear that the function output is not only not-uniform, but it is not random at all. However, this example tell us nothing on the problem. A more interesting and famous example is a function returning a random point in a circle. For simplicity, we assume a radius 1 circle.  The generator function will be something like the following:.

$f(\rho,\theta) = \langle \rho cos(\theta), \rho sin(\theta) \rangle$

This is a standard polar coordinate system, where we can use $\rho$ in the interval $[0,1]$, and $\theta$ in the interval $[0, 2\pi]$. As it is known, for each pair $(\rho,\theta)$ we get a unique point in the circle.

In order to generate uniformly distributed point in the circle, our first idea is to chose $\rho$ and $\theta$ with a uniform distribution. However, the result is far from uniform.

As you can see, the points group around the center. Why? It easy to see that, according the way we are generating the points, half of the points will be in the $\rho < 0.5$ circle while the other half will be in the $\rho > 0.5$ ring. However, the area of the small circle is just 25% of the total area of the circle! We are, indeed, pushing half the point in a quarter of the area.

What we want is to generate uniform points on the area of the circle. In other words, we want that half of the points we generate will be placed in half the area (and the same for any other ratio). In the circle problem, this can be easily solved by taking the square root of $\rho$ before generating the points. You can do the math, or look at the example below.

The circle example is a classic and well-known example, but we can apply the same reasoning to any PCG algorithm. When you are uniformly picking the input parameters of your dungeon generator are you generating uniformly distributed dungeons? If this does not work for simple circles, I think it is unlikely that it works for dungeons. Unfortunately, the solution here is much more complex, but it is worth to take the problem in mind.

## Random in the perception

This is another common problem. I talked a bit about this in a previous article, but the problems returns many times even in different fields. It appears in games, when you want random abilities that seems fair to the player (that’s why a lot of MOBA use pseudo-random number generators) or music players such Apple iPods or Spotify shuffle their playlists. The problem is so common that we have the name for it: gambler’s fallacy. In short, we confuse randomness with “equally and evenly distributed events”.

The main problem here is that the final player does not always perceive true randomness as randomness. If your algorithm produces thousands of slightly different objects, even if they are technically random, if the player perceives them as “mostly the same thing” your algorithm has failed to achieve its purpose from a PCG point of view.

As a consequence, even if you have an algorithm that produce uniform randomness in the output (see above), if your output space is not uniform from a perception point of view, you still fail to achieve “true perceived randomness”. Unfortunately, understanding what means “perceived randomness” in many PCG domain is even harder that producing uniform output. For dungeon generators, this could depend on many faetures of the dungeon. For instance topology (long maze-like corridors vs. large rooms connected by short hallways), the tiles, the enemies or something else. In any case, it is not possible to guess this in advance. For this, it is important to analyze the players’ feedback in the specific game.

## Combining the two

We can then conclude that we can achieve “true randomness” in PCG with the combination of two properties:

1. The algorithm should produce random results uniformly distributed in the output space.
2. The output space should contain a uniform distribution of “perceived random” results.

Both these properties are just guidelines, because it is impossible to turn them into practical rules, or even verify them, in any PCG algorithm more complex than a random number generator. Nevertheless, these are two important aspects that a PCG developer should keep in mind.

If you are interested in this topic, in literature, the combination of these two aspects takes the name of Expressive Range (click on the  link for the paper on Expressive Range in PCG). But for us, this is a story for another time.