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 crates.io. 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. :)

Example

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) {
            continue;
        }

        visited.push(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 };
            heap.push(next);
        }
    }

    // Goal not reachable
    None
}

 

Improve Inventory-Aware Pathfinding with Map Preprocessing

This article has been originally published on Gamasutra

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”.

Continue Reading on Gamasutra!

How to manage a Videogames Bibliography in LaTeX

There is a common question in academia for people working on videogames: “Is there a consensus on how to cite videogames in academic papers?”. Obviously not, there is no consensus and probably never will. However, I will try to show you a solution to this problem that I enjoyed a lot in the last months. It is clear, it is customizable and it is the most formal way I’ve found to do that.

Use BibLaTeX

The first prerequisite is to use BibLaTeX. BibLaTeX is a replacement for BibTeX (the default bibliography manager for LaTeX). It is more flexible and powerful than BibTeX, therefore, even if it is a bit more complicated to set up, it is worth the switch in any case.

In order to switch to BibLaTeX you can follow the simple steps described here. It is not hard. There are just three things you have to do. First, load the BibLaTeX package with

\usepackage[style=<somebiblatexstyle>,<other options>]{biblatex}

Second, load your bibliography with

\addbibresource[<options for bib resources>]{<mybibfile>.bib}

And, at last, print your bibliography.

\printbibliography[<options for printing>]

Create your videogame bibliography

Cool. Now, what we want to do is to create our personal videogame bibliography. Ideally, we want a new LaTeX command \citegame{game_id} for managing videogame citation. First, however, we have to create our videogame.bib file. Inside this file, we will add entries for videogame in this way:

@software{bioshockinfinite,
  author = {{Irrational Games}},
  title = {BioShock: Infinite},
  url = {http://www.bioshockinfinite.com/main.php},
  version = {1.1.25},
  date = {2013-03-26},
}

Pro Tip. It is possible that you want to print your videogame bibliography in a separate section (different from your hard books and papers bibliography). You can do this in this way:

% Print the standard bibliography.
\printbibliography[title={Bibliography},nottype=software] 
% Print your Videogame/Software Bibliography
\printbibliography[title={Videogames},type=software]

Add a custom cite command

Now it is time to implement our custom cite command! In the preamble of your LaTeX file insert this code:

\DeclareCiteCommand{\citegame}
  {\boolfalse{citetracker}%
   \boolfalse{pagetracker}%
   \usebibmacro{prenote}}
  {\ifentrytype{software}{%
    \printfield{title}%
    \setunit{\addspace}%
    \printtext[parens]{%
    \printnames{author}%
    \setunit{\addcomma\space}%
    \printfield{year}}}{\GenericError{}{Not a game entry}{}{}}}
  {\multicitedelim}
  {\usebibmacro{postnote}}

This command creates a custom \citegame{game_id} that you can use to cite videogames. You can customize the format but in my documents I use the “Title (Developer Year)” format presented above. For instance, you can use the following code:

\caption{Elizabeth in \citegame{bioshockinfinite} is an AI companion which, 
among the other tasks, will randomly provide ammo, medikits and money for the player.}

To get a result like this:
Latex videogame Example

 

Latex Videogame Bibliography

Conclusion

I hope enjoy this very small tutorial! Feel free to update and improve it. There are still some rouge edges that I would like to remove. In any case, share it with your colleagues if you like!

On the procedural generation of a proto-language

As you probably know, last week I was at the DiGRA-FDG conference in Dundee, Scotland. The conference ended last week, but I have the urge to add something to a really interesting presentation I’ve attended during the first day at the workshop on Procedural Contents Generation.

Before FDG, I was reading a small book on how the Chinese language has evolved during the centuries. It is extremely interesting. Especially if we look at the clear and wonderful evolution from pictures on paleolithic wood artifacts to the modern Mandarin Language. This triggered in me the idea to explore the literature on teleological algorithms for the procedural generation of languages (if you don’t know, the teleological algorithms in PCG are the ones that try to generate a “thing” by simulating the physical and evolutionary processes through which the “thing” is generated in the Real World™).

I was thinking about that just two days before the conference. Therefore, you can maybe understand my surprise when the first presentation I attended was titled: “Diegetically Grounded Evolution of Gameworld Languages”.

This small paper describes very effectively the simulation of some aspects of how languages evolve in the real world. It is inspiring and worth read it! However, I feel that the thing I was interested into was not really covered. So, I’ll try to dump my brain in this article.

Continue reading “On the procedural generation of a proto-language”

Back from Nucl.ai 2016 – A small report

I’m back! During the last week, I had a beautiful experience as a volunteer at the Nucl.ai 2016 conference, one of the nicest Game AI related conferences in Europe.

I like this conference. It has a very informal atmosphere and both speakers and attendees are incredibly friendly and very willing in giving advice. You can go there like a complete no-one (for instance, like me) and you can speak and have a beer with Lead AI programmer in Triple-A games, in top notch industries like Google, Blizzard or Epic as if they are your friends.

This is possible because I can guarantee that the people involved in organizing this conference are very passionate about the topic and, most important, they do it while having fun!

But that’s enough with advertising! Let’s talk about what I got from attending this conference!

Continue reading “Back from Nucl.ai 2016 – A small report”

Inventory-Aware Pathfinding – Part 1

Everybody know what pathfinding is. I don’t think I have to explain to a game developers audience why pathfinding is so important in games. If something in your game is moving not in a straight line, then you are using some kind of pathfinding.

What is less evident is that pathfinding is the only place in which “searching” is generally accepted. Except for GOAP and other planning-based techniques, the big part of the NPC’s decision-making techniques are reactive-based.

This is not a bad thing. Reactive techniques are an amazing design tool. However, this raises a question. Why is this? Mainly because of computational limits – full-fledged planning still requires an impractical amount of time – but also because of design unpredictability. The output of planning decision-making techniques is hard to control and the final behavior of the agent could be counterintuitive for the designers and, at the end, for the players.

Why can pathfinding play a role in this? Because it is possible to embed in it a minimal, specialized, subset of planning, especially if these planning instances require spatial reasoning. A common example is solving a pathfinding problem in which areas of the map are blocked by doors that can be open by switches or keys sparse around on the map. How can we solve this kind of problems?

Continue reading “Inventory-Aware Pathfinding – Part 1”

Procedural Contents Generation in Modern Videogames

8th September 2016 Update: I uploaded these slides on SlideShare. You can see them here.

Hi guys! In the last month I’ve prepared a presentation on Procedural Contents Generation history and techniques in commercial videogames. I did this presentation for a Game Jam some time ago and for a series of meetings in our university.

I think it is a nice summary of the main elements of PCG in commercial games, so I think it is worth to share this presentation with you!

Download Slides

Enjoy! :)