MovingAI pathfinding benchmark parser in Rust

You know I worked a lot with pathfinding. In academia, the MovingAI benchmark created by the MovingAI Lab of the University of Denver is a must for benchmarking pathfinding algorithms. It includes synthetic maps and maps from commercial videogames.

Parsing the benchmark data, the maps, creating the map data structure and more, is one of the most boring thing I needed to do for testing my algorithms. For this reason, I think a common library for working with the maps specifications it is a must.

For this, and because I enjoy a lot coding in Rust, I did a MovingAI map parser for rust.

Repository is here. The library is also on It is still unstable because I want to be sure that the public AI is consistent with the requirements. I also not very solid on the needs of Rust APIs. So, I welcome some help here. :)


However, look how it is convenient for writing pathfinding algorithms! All the important stuff (neighbors, map, and so on) are just out of the box. This is an A* algorithm I wrote in literally 5 minutes.

// A* shortest path algorithm.

fn shortest_path(map: &MovingAiMap, start: Coords2D, goal: Coords2D) -> Option<f64> {

    let mut heap = BinaryHeap::new();
    let mut visited = Vec::<Coords2D>::new();

    heap.push(SearchNode { f: 0.0, g:0.0, h: distance(start, goal), current: start });

    while let Some(SearchNode { f: _f, g, h: _h, current }) = heap.pop() {

        if current == goal { return Some(g); }

        if visited.contains(&current) {


        for neigh in map.neighbors(current) {
            let new_h = distance(neigh, goal);
            let i = distance(neigh, current);
            let next = SearchNode { f: g+i+new_h, g: g+i, h: new_h, current: neigh };

    // Goal not reachable


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.

Flow is the core concept of game design. You need to keep your player in the flow balancing difficulty. Levels and experience point are a great way to do this (sometime, a lazy way).

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.

Linear, logarithmic, quadratic and exponential progressions.

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.


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.

Small rant about “blockchain” overuse

A lot of startups are using “blockchain” as a replacement hyped word for “distributed database”. Well, a blockchain is the most inefficient and slow “distributed database” ever created. Blockchain strength is not in being a database! Stop doing that!

The blockchain power is in avoiding divergent transactions, and guarantee a not falsifiable and immutable history. That is, no node in the system can alter the past of the chain. That’s it. They are huge and specific problems.

Nevertheless, there are industry people saying that “blockchain immutability” is the biggest problem of a blockchain.

And so we have tons of blockchain/alter-coins, but “centralized” or “owned” by someone. But if I need to trust “someone”, why using a blockchain system in the first place! Just use a damn distributed database!

(Originally on Twitter)

How to add a logo in Rust documentation

One of the feature I like the most on Rust is automatic documentation. Documentation is a pillar in language ergonomic, and I love that Rust spend so much time into making documentation and documenting code a much pleasant experience.

Rust autogenerated documentation (with cargo doc) looks good, every crate on get its documentation published on, and, most important, every code example in the code is compiled and run as a “unit test” making sure that all the examples are up-to date!

I love that. But what if we want to customize a bit the documentation? For instance, by uploading a crate logo or a custom favicon? Googling this does not provide a lot of information. That’s why I am writing this small how to.

Continue reading “How to add a logo in Rust documentation”

Questions about Deep Learning and the nature of knowledge

Rush of Knowledge

If there is something that can be assumed as a fact in the AI and Machine Learning domain is that the last years had been dominated by Deep Learning and other Neural Network based techniques. When I say dominated, I mean that it looks like the only way to achieve something in Machine Learning and it is absorbing the great part of AI enthusiasts’ energy and attention.

This is indubitably a good thing. Having a strong AI technique that can solve so many hard challenges is a huge step forward for humanity. However, how everything in life, Deep Learning, despite being highly successful in some application, carries with it several limitations to that, in other applications, makes the use of Deep Learning unfeasible or even dangerous.

Continue reading “Questions about Deep Learning and the nature of knowledge”

The Most Promising Programming Languages for 2018

This is the time of the year in which I propose 5 emerging/new languages that you should keep an eye on the next year. I’ve done it last year, and the year before, and the year before that.

This year, however, I am not in the mood of doing it. There are several reasons why. The first one is that this year there have not been a lot of movement on the new programming languages. I am sure there are a lot, but no one got enough attention to make into a list. Therefore, I am concerned that I will just starting to repeat myself talking about the same stuff.

Continue reading “The Most Promising Programming Languages for 2018”

Preserving a Cryptography book from 1897

Some time ago I found on my grandma’s house an old Italian book on cryptography from 1897. Why a 120 years old book on cryptography was on my grandma house, is a mystery. I’d like to think that some grand-grand-parent was a late 19th century hacker. Anyway.

The book title is “Crittografia ossia l’arte di cifrare e decifrare le corrispondenze segrete” of Count Luigi Gioppi of Turkheim.

Well, I don’t know if this book is hard to find. In any way, I decided to take a photo of every page to share and preserve this book. The book is very old and some page is ruined, sorry if the quality of the photo is not optimal. I’ve done my best for not destroying the book in the process. :)

I will release the photo one chapter at the time. Keep this page in the bookmark.

Continue reading “Preserving a Cryptography book from 1897”