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.

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.

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?

As you may already know if you follow me on Twitter (why not?), I often work with pathfinding. This thing started as a small side quest during my Ph.D. and then grew up to become the main topic of my future Ph.D. thesis. I’m still quite sure that this is not what I chose back in the day but, well, now that I’m on the dancefloor I have to keep dancing.

Returning to the subject, my work is totally focused on pathfinding with cognitive capabilities. This means that I try to embed pathfinding into a more high-level reasoning pattern or, if you prefer, to push high level elements - such as reasoning with keys and equipment - down into the pathfinding level. As a consequence I use hierarchical abstraction of the map space a lot and for “a lot” I mean that in the last year and half I’ve implemented Hierarchical Pathfinding (HPA*) at least 4-5 times in different context and languages.

Hi everyone! Sorry for the long absence but my days are really full of commitments and terrible news. It is still not over, but but I really need write about something before is too late. :) During the last 3th-7th October, the tenth conference on Artificial Intelligence for Interactive Digital Entertainment (AIIDE) was held in Raleigh (North Carolina, USA). It was a very interesting conference on AI and games stuff and I am really happy to have joined such amazing things. I mean, this is something that I could proudly say to the 10 years old me and make him happy and unbelieving. I could look the younger me in the eyes and say “In the future you’ll participate in a conference about artificial intelligence and videogames with some of the most beautiful mind in that field!”. Wow. However, unfortunately I received too many commitments and bad news from Italy to be able to freely enjoy this conference and to be fully concentrated. I’m really sorry of this.