You need to decide your decisions

Every day, you only have a limited amount of “good” decisions. So, it is better to learn how to avoid wasting them.

If there is something that I learned from my daily struggle with procrastination, is that every day you just have a limited amount of decisions. Every day, you can only do 5, 8, maybe 10 meaningfully decisions. After that you will start doing mistakes, get tired and, in general, doing wrong.

What can be surprising of this, is that doesn’t matter how important the decision is. Look at a traditional day: you wake up and you need to decide what to eat for breakfast, what clothes to wear, if it is better to go to work using the car or public transportation. You have literally just waked up and you have already depleted the big part of you decision pool for the day. And none of that decision is meaningful for your work, your career, your family, your affections.

Continue reading “You need to decide your decisions”

Inventory-Aware Pathfinding – Part 1

Sometimes, solving planning and pathfinding at the same time can save you a lot of time. It is the case of Inventory-Aware Pathfinding in which we want to solve pathfinding in a map constrained by the items brought by the agent (e.g., keys to open locked doors).

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”

The Primes Ancestor Tree

A beautiful mathematical object I played with in some boring afternoons. Just for the love of math.

This will be just a small theoretical article on the Primes Ancestor Tree. We will explore the possibility to label a generic tree in such way that it will be possible to verify if a node is an ancestor of another node (or to find the common ancestor of two nodes) just by applying integer arithmetic.

In fact, sometimes ago I was trying to implement some fancy algorithm that, given two nodes from the open list of a search algorithm, finds their common ancestor. While I was doing this I asked myself if it was possible to use prime numbers in order to provide a labeling system that encodes the “descendant” relation of the nodes.

I think that I have found a theoretical system. Even if it can not be used in real-world applications, I had fun playing with it looking for the properties of the resulting labeled tree. So, I thought it could be interesting to share.

Continue reading “The Primes Ancestor Tree”

How to use Rust in Python (Part 3)

Third (and last?) part of our Rust in Python series. It is now time to see how to pass objects from Rust to Python and vice versa!

You can follow the links to read the first part and the second part of this series.

In the previous part we have seen how to pass not trivial data to Rust functions such as a Python list. It is still not enough, though. In many cases we need to pass complex data structure back and forth from a Rust library. We may need to pass quaternions, 3D points, trees, a list of “books”… In short: anything.

Learning how to pass custom aggregated data types to Rust libraries (and back to Python) will be the focus of this part!

Continue reading “How to use Rust in Python (Part 3)”

How to use Rust in Python (Part 2)

In the previous part we have seen how to run simple Rust functions with integer arguments. This is not enough, of course. We need to go further by passing Python lists to Rust functions.

You can find the first part of this article HERE.

In the previous part we have seen how to run simple Rust functions with integer arguments. This is not enough, of course. We need to go further by passing Python lists to Rust functions.

The problem is that it is not possible to pass directly a Python list to a C interface. Python lists (we can call them Plists) are complicated beasts, you can easily see that they are objects full of methods, and attributes and… Stuff.

We need first to convert this in something edible from a Rust library. But first things first.

Continue reading “How to use Rust in Python (Part 2)”

How to use Rust in Python (Part 1)

Rust is an amazing language. It is one of the best potential alternatives to C and has been elected two times in a row as the most promising language of the year (by me, :P). However, because its strict compile-time memory correctness enforcement and because it is a low-level language, it is not the fastest way to build a prototype. But don’t worry! Rust is the perfect language for embedding fast-binary libraries in Python! In this way we can get the best of both worlds!

Writing Rust code that can be executed in Python is stupidly easy. Obviously, you have to well design the interface between the two languages, but this will improve your Python code in two ways: 1) You can execute CPU-intensive algorithms at binary speed and 2) use real threads instead of the Python “simulated” ones (and because Rust is designed to be memory safe, writing thread safe routines is much easier). Let’s see!

Continue reading “How to use Rust in Python (Part 1)”

Convert images to MovingAI maps

The MovingAI Benchmark Database is one of the most famous collections of maps for benchmark on pathfinding algorithms. I use it a lot during my work, it is useful to test an algorithm over a lot of real-world game maps. The consequence is that I developed a lot of tools to work with the map format of the MovingAI database.

The last of these tools is a straightforward Python script to convert images into maps in the MovingAI format. It is useful when you want to quickly develop some test maps.

Continue reading “Convert images to MovingAI maps”

Research Code vs. Commercial Code

Since the beginning of my working life, I was torn between my researcher and software developer self. As a software development enthusiast, during my experience as a Ph.D. student, I suffered a lot looking at software implemented by researchers (many times my code is in the set too). Working with research code is usually an horrible experience. Researchers do so many trivial software development mistakes that I’d like to cry. The result is: a lot of duplicated work reimplementing already existent modules and a lot of time spent in integration, debugging and understanding each other code.

On the other hand, it is almost impossible that a researcher will learn the basics of software development in some book because 1) nobody cares (and they really should!) and 2) books on this topic are mostly focused on commercial software development. This is a problem because, even if best practices overlap for the 80%, research code and commercial code are driven by completely different priorities.

So, because I am just a lonely man in the middle of this valley, nor a good research code writer nor a good commercial code writer, I can share my neutral opinion. Maybe, I will convince you, fellow researcher, that may be worth to spend some time improving your coding practices.

Continue reading “Research Code vs. Commercial Code”

Postmortem: Writer’s Block – 1GAM January

The first month of the year is gone and I’ve made a game! The January 2016 entry of 1GAM, namely “Writer’s Block”, is now completed (kind of)!

January 2016 has been a great start for this year! During the last months of last year I started a personal journey to fight my inner demons. I don’t want to bore you with some self-improvement/productivity bullshit -it is not the place for that- so I will not. You just have to know that after 6 months of trying and failing this January is the month in which all the good habits really start to stick.

The “One Game A Month” challenge was the perfect way to test myself and doing one of the activities I love most. As usual, we will start from the beginning.

Continue reading “Postmortem: Writer’s Block – 1GAM January”

Fast (Approximated) Moving Average Computation

Computing the Moving Average of a sequence is a common task in games (and other applications). The motivation is simple: if something happened too far in the past, probably it does not matter anymore.

One of the main problem with the standard average is that it “slows” over time. This can be a serious problem. Suppose that you are designing a game in which your player have to quickly press a button to keep a value (e.g., player speed) above a certain average. If you use the global average, after a certain amount of time, your player can stop pressing the button and still keep the average above the threshold.

The demonstration of this is quite intuitive. If you have an average a(t) at frame t and the player will not press anything in the current frame, the average at frame t+1 will be

a(t+1) = a(t) \frac{t}{t+1}

This factor depends on the elapsed time and becomes “almost 1” very quickly. You don’t want that. You want to keep your player on the narrow land between “boredom” and “frustration”. You cannot give to your player the possibility to win without doing nothing for 30 seconds.

The solution to this problem is simple. Use a Moving Average. The player will have to push the button faster than the threshold, but the average is computed only using the data from the last 5 second (or any other time window you want).

Continue reading “Fast (Approximated) Moving Average Computation”