Perfect AI

This month I have created the first article in a series that will deal with advanced AI. If you think that "Perfect AI" sounds too good to be true, here's what I plan to do: an enemy that knows the position of the player all the time and knows how to get to the player using the shortest route available.

It is obvious that every game has its particular AI needs so I want to keep the discussion at a beginner - intermediate level; this way everybody should be able to modify the existing code, adding new features to it. Don't forget the "Acknex User Magazine" topic at the forum; post your ideas there and some of them will come to life. Btw, all the articles in this magazine were requested by you at the forum.

Ok, so let's see what we can learn this month. I wrote a few articles about AI in my previous magazines, mostly using the "trial and error" method. The enemy tries to get to the player by moving towards it; when it hits an obstacle, it rotates to the left or to the right, moving a certain distance in the new direction, and then it tries to get to the player again.

If you think that this is primitive AI, well.. you are right! However, if does its job pretty well for small sized obstacles and it is extremely easy to code. Advanced AI needs to use nodes or waypoints (but I'm not going to use this term because you might confuse them with the points on the paths that can be created in Wed). A node is a point of interest placed in the level; take a look at all the colored squares in the first picture: these are the nodes created by me for this maze level.

Every node should have at least a node to talk to so feel free to add as many nodes as you need in your levels; on the other hand, don't use unnecessary nodes because you will slow down the game. Here's an example for a bad node placement:

You can see that "1" is isolated; it can't "see" any other node. The same thing goes for "3" and "8": they can "see" each other but none of them can see the rest of the nodes. Now here's the corrected version:

I have added the nodes numbered "9" and "10" and now the nodes can communicate with each other. Let's imagine the following situation:

The enemy wants to find the player, so it will do the following things:
- Asks this question: "which one of you, nodes, is the closest to the player and can see the player?"
- "It is me, pick me!" says node 2.
- "Oh, I see.." replies the enemy, "but how do I get there?"
- "Well", says node 2, "I don't know how to get you here, but I tell you that I can see node 10".
- "Good enough", replies the enemy. "Hey, node 10, what do you see?"
- "I can see node 5" replies node 10.
- "And you, node 5?" asks the enemy again.
- "I can see node 4 and node 7".
- "I can see node 7 too! Now I know how to get to the player!" says the enemy rubbing its dirty hands. "All I need to do is to move to node 7, then to 5, 10, 2 and I will find (and kill!) the player.

That's how advanced path finding works. There are a number of path finding algorithms that are well known: A*, Dijkstra, Breadth - first search, etc. I think I'll use a combination of the first two algorithms.

Now that you've got some info about AI let's see what have we got in the code used for this month's AI article:
- a network of nodes;
- only the nodes that are close to the player use precious computer resources;
- the nodes that are close to the player and can see the player are detected;
- the closest node to the player that can see the player is known, as well as its distance to the player.

I would say that this is a good start, so let's see the code that has made all these things possible. I will start by presenting you the arrays that are used in the demo:

var node_distance[50];
var see_player[50];
var nodex[50];
var nodey[50];

Node_distance[50] will hold the distance from a specific node to the player; its elements are node_distance[0]... node_distance[49] but we aren't going to use the first element (we want to keep the things as simple as possible) so this array can be used by 49 nodes. My demo level uses 30 nodes but if you need more nodes you can increase the size of the arrays above.

See_player[50] is set to one if the node can see the player and to zero if the node can't see the player. Take another look at the picture above: node 2 can see the player so see_player[2] = 1 and node 10 can't see the player so see_player[10] = 0.

Nodex[50] and nodey[50] hold the coordinates of the nodes on x and y; we need these arrays because if we want our enemy to go to node 5 (for example) we will find the coordinates for node 5 in these arrays.

Time to see a text and a panel:

text ai_txt // displays the texts on the screen
{
font = ai_font;
pos_x = 0;
pos_y = 0;
string = "Target node:\nD.to target:";
flags = visible;
}

panel ai_pan // displays the numerical values on the screen
{
pos_x = 0;
pos_y = 0;
layer = 10;
digits = 240, 0, 3, ai_font, 1, target_node;
digits = 240, 22, 3, ai_font, 1, closest_distance;
flags = overlay, refresh, visible;
}

I have ai_txt to display the two rows of text on the screen and ai_pan to display the two figures. The target node is the closest node to the player that can see the player and "D. to target" is the distance from the player to the target node. Let's take a look at function main:

function main()
{
fps_max = 60;
clip_size = 0;
level_load(level1_wmb);
wait (3);
camera.z = 2400;
camera.tilt = -90;

We limit the frame rate to 60 fps, we make sure that we show all the triangles for all the models and then we load the level. We wait for the level to be loaded and then we make sure that we get a good view of the whole level by choosing a convenient camera height and angle.

while (1)
{
index %= 49; // limit the "index" value
index += 1; // from 1 to 49

The while loop will determine the closest node that can see the player. We use a var named index as a counter; its value ranges from 1 to 49 because we can use up to 49 nodes if those arrays have 50 elements.

if ((node_distance[index] < closest_distance) && (see_player[index] == 1))

If the distance from a new node to the player is smaller than the old distance to the player and we are testing a node that can see the player (see_player[index] = 1) then we have a new winner! We have set a new target node for our enemy!

{
closest_distance = node_distance[index];
target_node = index;
}

If this isn't true, we will use the previous winner; the older node is still the closest to the player.

else // haven't found a new winner?
{
closest_distance = node_distance[target_node];
}
wait (1);
}
}

We will use a model that can "walk" and "stand" for the player; let's see the code for it:

action player1
{
player = me; // I'm the player
while (1)
{
my.pan += 4 * (key_cul - key_cur) * time; // rotates with the left / right arrow keys
player_speed.x = 10 * (key_cuu - key_cud) * time; // moves forward / backward with the up / down arrow keys
if (key_cuu + key_cud > 0) // if the player is walking
{
ent_cycle("walk", my.skill46); // play "walk" frames animation
my.skill46 += 7 * time; // "walk" animation speed
my.skill46 %= 100; // loop animation
}
else // the player is standing
{
ent_cycle("idle", my.skill46); // play "stand" frames animation
my.skill46 += 2 * time; // "stand" animation speed
my.skill46 %= 100; // loop animation
}
move_mode = ignore_passable + glide;
ent_move(player_speed, nullvector);
wait (1);
}
}

The player rotates when you press the left or right arrow keys and moves forward / backward when you press the up / down arrow keys. Change "4" and "10" to change the rotation and movement speed. If the player is walking it plays its "walk" animation and if it is standing it plays its "idle" ("stand") animation. The player moves and glides along the walls if it hits them.

The last part of the code is the one associated to the nodes:

action node // using 30 nodes in this demo
{
my.skill47 = 1234;
my.passable = on;
my.skin = 1; // red
while (player == null) {wait (1);}
node_number += 1; // get a unique number
my.skill48 = node_number; // and store it in skill48
nodex[my.skill48] = my.x; // store x and y
nodey[my.skill48] = my.y; // for this node

We set a weird value for skill47 to give the nodes a unique id, we make the node passable because they shouldn't block the player or its enemies and then we choose the first skin for the node (red). The node model has three skins: red, green and blue. Red is the default value, green is used by the nodes that are close to the player and blue is used by the nodes that can "see" the player.

We wait until the player is created and then we assign every node a unique number, which will be stored in skill48. Maybe you are wondering how this system works, so here's a detailed explanation: all the entity placed in our level load one by one. The first node entity that appears in the level will add one to node_number and then will store the value (one) in skill48. The second node will add one to the existing value (one) and then will store the result (two) in its skill48. The process repeats until all the node entities are loaded; when this happens, every node has stored its number inside its skill48.

The last two lines of code store the position of the node (x and y) in the level.

while (1)
{
node_distance[my.skill48] = vec_dist(player.x, my.x);

I have told you that node_distance stores the distance from the node to the player, isn't it? The line of code above does that. If the player is closer than 500 quants to the node:

if (node_distance[my.skill48] < 500)
{
trace_mode = ignore_me + ignore_models + ignore_passents;
if (trace (my.pos, player.pos) == 0) // if this node can "see" the player
{
my.skin = 3; // the node changes its color to blue
see_player[my.skill48] = 1; // the node can see the player
}
else
{
see_player[my.skill48] = 0; // this node can't see the player
my.skin = 2; // can't see the player? keep the green color
}
}

We "trace" from the node to the player; if the result is zero, the node can see the player so we change the skin of the node to blue and we set see_player to 1 for this node. If the node can't see the player we use the green color for the node: the player is close but can't be seen by the node.

else // far from the player? keep the red color
{
my.skin = 1;
}
sleep (0.1); // trace 10 times a second
}
}

If the player is far away from the node, we keep the (default) red color for the node. All these operations happen 10 times a second because the last instruction inside the while loop is sleep(0.1).

Let's run the project: open level1.wmp, built it and run it using ai1.wdl:

You will see the following image:

The green squares are the nodes that are closer than 500 quants to the player. You can move the player around and see how the green nodes change. Now exit the engine and run the level again using -d traceplayer, like in the picture below:

You will see the following image:

Some of the green nodes have turned to blue; these are the nodes that are closer than 500 quants to the player and can "see" the player. It wouldn't be wise to have "trace" instructions for the nodes that are far away from the player, isn't it?

I encourage you to create one or more test levels and to learn how to place your network of nodes inside it / them. Here's a bad example for a correct network of nodes:

The enemy wants to get to the player, so it must use this path: 1, 5, 3, 2, player. If I would have added the missing node, the path from the enemy to the player would have been much shorter, isn't it? Don't forget that perfect AI starts with perfect path planning.

Next time we will learn to compute the shortest path between any two nodes in the level: the starting point (the enemy) and the target point (the player).

Take-off

Sometimes we need to interrupt the player from whatever he is doing because we need to show a nice cut scene effect. If you have decided to write the code for your game from scratch, you shouldn't have too many problems but what about the rest of the users, the ones that are faithful to the template code?

The code used inside this article creates a chopper that sits on the ground, waiting for the player to come close to it; when this happens, the chopper takes off by itself.

I had to get rid of the default camera without modifying the templates so I have defined a new view:

view cutscene_view
{
layer = 15;
pos_x = 0;
pos_y = 0;
}

The action attached to the chopper has its code listed below:

action chopper
{
my.passable = on;
while (vec_dist (my.x, player.x) > 150) // wait until the player has come closer than 150 quants
{
ent_cycle("fly", my.skill20); // play "fly" animation
my.skill20 += animation_speed * time;
my.skill20 %= 100; // loop the animation
if (!snd_playing(chopper_handle))
{
chopper_handle = ent_playsound (my, chopper_wav, 200);
}
wait (1);
}

The chopper is passable; if the player is farther than 150 quants, it plays its "fly" animation in a loop and plays the chopper_wav sound in a loop.

cutscene_view.size_x = screen_size.x; // has the same width
cutscene_view.size_y = screen_size.y; // and height with "camera"
cutscene_view.x = -1685;
cutscene_view.y = -1240;
cutscene_view.z = 210;
cutscene_view.pan = 20;
cutscene_view.tilt = -15;
cutscene_view.roll = 0;
player.invisible = on; // hide the player
player.shadow = off; // and its shadow (if any)
camera.visible = off; // hide "camera"
cutscene_view.visible = on; // show the new view

If the player has come closer than 150 quants to the chopper, we use the same screen size width and height for cutscene_view, we set a convenient position and angles for the new camera, we hide the player and its shadow, we hide the old view (camera) and then we show the new view (cutscene_view). I chose those values for cutscene_view by flying inside the level; press zero twice to be able to fly, press "D" or "F11" to see the debugging panel and look at its xyz and ang columns to get the x, y, z, pan, tilt, roll values needed for your game.

while (my.z < 1000) // wait until the chopper has reached a height of 1,000 quants
{
if (animation_speed < 10)
{
animation_speed += 0.05 * time;
}
else // start flying when animation_speed is bigger than 10
{
my.z += 10 * time;
my.x += 30 * time;
}
ent_cycle("fly", my.skill20); // play "fly" animation
my.skill20 += animation_speed * time;
my.skill20 %= 100; // loop the animation
if (!snd_playing(chopper_handle))
{
chopper_handle = ent_playsound (my, chopper_wav, 500); // the sound is louder this time
snd_tune (chopper_handle, 0, 25 * animation_speed, 0);
}

As long as the chopper hasn't reached the height of 1,000 quants, its animation speed grows from 4 to 10; when animation_speed is bigger than 10, the chopper starts to take off (increases its z) and moves forward (increases its x). We play the same "fly" animation at a bigger speed and chopper_wav is tuned accordingly.

vec_set(temp, my.x);
vec_sub(temp, cutscene_view.x);
vec_to_angle (cutscene_view.pan,temp); // rotate cutscene_view towards the chopper

These three lines of code will rotate cutscene_view towards the player all the time.

wait (1);
}
exit; // shut down the engine
}

The chopper has reached a height of over 1,000 quants so the engine will shut down. You could load a new level here, maybe trigger some explosions in the same level, etc. The only thing that matters is that the player is in good hands now (as long as I'm not flying the chopper).