4 – Artificial Intelligence

I’m currently working on my most anticipated feature of our game.  I am making a game mode called “Co-op Death” that allows 1 – 4 players to join forces and take on endless waves of enemies.  It may seem pretty basic, but there are actually a lot of complicated problems to solve.  The most technical (and the most fun to create) aspect is definitely artificial intelligence.  I’m currently finishing up the third iteration of the AI.  In case you are not aware of what AI entails, allow me to break it down for you.  Keep in mind that this is a solution that is very specific to this particular game.

1 – Picking a target

Before the enemy ship moves, shoots, or even runs away, it needs to know what it’s focusing on.  If there is only one player, this couldn’t simpler.

if (opponents.count == 1) target = opponents[0];

But if there are 2 or more players, this requires a robust solution.  We don’t want the AI to focus on player 1, while ignoring the shots he’s taking from player 2, behind him.  The algorithm we settled on takes into account these questions:

How far away are all the players?
Which players can I see?
How much HP do they have?
How much HP do I have?

These questions are very important and very answerable.  They all have quantifiable answers.  The numbers are put through a formula and a “Priority Index” is created for each player.  The player with the highest priority index becomes the target.

2 – Attack or Retreat?

Once the target is chosen an action must be performed.  In our case, we broke the potential actions in to engaging the target and fleeing from the target.  This may be the simplest part of the whole operation, but we are discussing making it more complex.  For now, the AI compares its percentage of remaining HP and compares it with the targets percentage of remaining HP.  If the AI has less than half the percentage of HP as it’s target, the AI flees.

float healthRatio = health.percentage() / target.health.percentage();
if (healthRatio < 0.5) defend();
else engage();

3 – Retreating

This comes down to a bunch of raycasting.  Basically by doing a bunch of math with vectors, we are able to produce a point, behind a wall, that the AI can go to.  This places a barrier between the AI and its target.  Currently, when the AI arrives at this point, it just stops moving.  It looks a bit awkward, but function is more important than beauty at this stage.

4 – Engage

What does it mean to engage the target?  Shooting them should be part of that.  Also, moving around in a realistic way.  When I say realistic, I mean what a human would do.  In a fast paced game where everyone is shooting each other, humans don’t stand still.  Moving makes you harder to hit, so that’s what people do.  The AI has a preferred distance it likes to be from its target.  This is based of the type of weapon that is equipped.  We also randomize that distance to give the AI some natural looking movement.  This makes the AI move towards and away from the target.  To make them move side to side, we just randomize that, too.  We are using perlin noise to generate random numbers that change smoothly over time.  Since the AI is always facing the target, strafing left and right actually causes it to circle its target just like humans do.

 5 – Pathfinding

If the AI wants to attack its target, but there is a wall in the way, it needs to navigate around that wall.  Pathfinding is present in many games so it’s only natural for there to be many different algorithms to handle different cases.  Care should be taken when choosing an algorithm because implementing the wrong one for the job can cause huge amounts of processor overhead.  If you have 30 characters on screen and they all have to navigate a maze-like environment, be prepared to spend lots of time optimizing your solution for that specific problem.  I originally used A* pathfinding.  You can read a wonderful article about A* here.  It’s a fairly robust algorithm that is design for grid-based movement.  I spent 1 day implementing it and 3 days optimizing it.  In its original state, the game slowed down to 10 frames-per-second with just 1 enemy  on screen.  After optimizations, I achieved 60 fps with 15 enemies on screen.  In some cases, optimizations aren’t just good practice, they are absolutely necessary.

You might be wondering how I used a grid-based pathfinding algorithm in a game like this.  I simply used a graph instead of a grid.  You see, in a grid, every cell has 8 neighbouring cells.  If cells are adjacent, they are connected (they are traversable).  We start at one cell and we just need to know the next cell to go to.  The only requirement is that the new cell is connected to the old one.  In computer science, rather than calling them cells and connections, we call them vertices and edges.  Consider the image:

rect2998The dark rectangles are walls and the red circles we will call “nodes”.  If we make the assumption that every node can see at least one other node, then the entire play field is reachable.  One way to think about it is with lights.  If the nodes were light sources, then the whole level should be illuminated.  Okay, so if the AI can travel from node to node, then it can go wherever it pleases.  At this point it isn’t really pathfinding.  This is what I like to call spacial awareness.  It knows about its immediate surroundings, but nothing beyond than.  This AI could easily walk itself into a corner, thinking that it was going the right way.  To guarantee that the AI will find the player, it needs a list of node to travel to in order.  In other words, it needs to find a path.  This is where all those different algorithms come in.  I have recently ditched A* in favor of my own greedy, cached algorithm.  It’s called a greedy algorithm because it always wants the optimal path to be the right one.  While some methods do a broad search and narrow in on the solution, the greedy method finds the best case solution and modifies it until it works.  Here is the logic:

1 – Find the closest node to the AI that is within line of sight. (node A)
2 – Find the closest node to the target that is within line of sight of the target. (node Z)
3 – Starting at node A, move to its neighbour that is directionally closest to the destination.

That’s it!  Just repeat those steps a few times and the target will be found.  The reason that this is a great solution is because it is so fast that it basically takes no time to compute.  The only potential downside is that you can’t guarantee the path to be the shortest possible path.  It also assumes a simple level design.  With proper node placement, it’s possible to go through all the longest routes in you head.  This is important as it is very easy to place the nodes in such a way that some paths are impossible.  This brings me to the last awesome benefit of this algorithm.

Assuming that the level doesn’t change over time, the paths will not change either.  This allows us to pre-compute all the paths from each node to every other node before the game starts.  Each node contains a list of paths to all other nodes.  This all happens in a matter of milliseconds even when using 20 nodes.  So when an AI needs to travel to node X,  it simply finds the closest node and looks up the path to node X.  No pathfinding is required and no CPU time is wasted.  It comes with a few restrictions, but they aren’t restrictions that will make us change anything.  It’s a solution that is tailored for our purposes, as most great programming solutions are.

I hope you found that interesting.  Until next time.

Leave a Reply

Your email address will not be published. Required fields are marked *