AI path-finding, part 1.

Over the years, I have accumulated a fair amount of knowledge about video-game programming and especially interactive graphics. But when it comes to Artificial Intelligence (AI for short) programming, I am still a noob!

Programming the behaviour of the skeletons in the game was a difficult task, and the code I wrote is difficult to maintain / to modify. If I want the game to have more enemies, with different behaviours, I will have to rewrite this code.

AI is a vast and complex subject, and today, I'm only going to discuss a small subset it, but  one that is needed by Castle Defender. Ladies and gentleman, let me introduce to you the almighty path-finding!

Part 1: A rubbish path-finding

Path-finding can be implemented in various ways, and the most common one is probably the A* algorithm. (I'm not going to talk about it, just do a Google search). But the simplest path-finding algorithm (and the one I've been using so far!) is most probably this one:

Algorithm 1: simplest path-finding

    move toward destination

    if hitting a wall then

       move sideways a bit

    end

Not really an algorithm per say! But it works surprisingly well for simple scenes. And it is used in more video games than you might think! Have the look at the behaviour of the zombie mobs in Minecraft for instance.

In Castle Defender, using this algorithm, enemies would walk straight towards the castle, and if they hit a tree, they would move sideways to get around it before carrying on moving towards the castle.

So this algorithm works best for simple terrains, but what if the castle is protected by battlements? The enemy would walk towards the castle until reaching a wall, at which point they will choose a random direction (let's say right) and move along the wall in that direction until reaching the end of the wall before resuming their wall towards the castle. This might result in very unoptimised path, as illustrated in Figure 1.

Figure1: The simple AI is choosing the longest path.

The situation above is still very simple, and the AI do reach the castle in the end, even if it might take a while. But what if the game has more complex elements like rivers that the AI can only cross using bridges? Or poisonous areas that the AI should avoid? Or a series of walls outside the castle?
It quickly becomes impossible to make sure this "stupid AI" reaches its destination.

Next week, we will see how smart path-finding can be easily achieved by using a technique known as flow-field pathfinding.