Simple path finding

Let's set things straight from the very beginning: advanced path finding is way beyond the scope of this tutorial. If you are interested in learning advanced A* path finding, for example, there are lots of examples on the web. Here's an article that explains the theory, provides a sample and has links to other useful resources.

The code is too complex for beginners, though, and I don't want to scare anyone. So, let's discuss the code for a simple obstacle avoidance algorithm.As you can see in the image, the enemy wants to get to the player. A wall gets in the way, though, so the enemy will bounce of it, changing its direction after each try, and finally managing to avoid the big wall. The algorithm is not perfect, but it's more than enough for what we need in our simple escape games.

Here's an easy, effective implementation of this obstacle avoidance method. We use an action called PlayerTracker, which must be attached to the enemy - the entity that tries to get to the player.

action PlayerTracker()

{

while (!player) {wait (1);}

First of all, we wait until the player pointer is valid; it would make no sense to try and track the player if its model isn't loaded yet.

VECTOR temp, temp_angle;

var npc_speed = 5;

var covered_dist, i;

Then, we define two vectors named "temp" and "temp_angle", as well as three variables.

It's time to examine a loop that runs at all times, making the entity follow the player.

while (1)

{

my.skill10 += 6 * time_step;

Our entity is animated; "6" gives the "walk" animation speed

vec_set (temp.x, my.x);

temp.z -= 10000;

temp.z = -c_trace (my.x, temp.x, IGNORE_ME | IGNORE_PASSABLE | USE_BOX) + 20;

The three lines of code above make the entity trace 10,000 units below its feet. We do this because we want to make sure that the entity's feet are placed firmly on the ground at all times; otherwise, the entity would start to float in the air after climbing a hill, for example.

temp.x = npc_speed * time_step;

temp.y = 0;

ent_animate(my, "walk", my.skill10, ANM_CYCLE);

The lines above animate the entity, making it play its "walk" animation in a cycle. The code below takes care of the obstacle avoidance part.

covered_dist = c_move (my, temp.x, nullvector, IGNORE_PASSABLE | GLIDE);

if (covered_dist < 0.1)

{

my.pan += 90 - random(180);

i = 0;

while (i < 10)

{

c_move (my, temp.x, nullvector, IGNORE_PASSABLE | GLIDE);

ent_animate(my, "walk", my.skill10, ANM_CYCLE);

i++;

wait (1);

}                                

}

The variable named "covered_dist" stores the distance that was covered by the entity during the last movement frame. If the value is lower than 0.1 units, its means that our entity is stuck somewhere in the level, so the obstacle avoidance code kicks in.

Actually, the mechanism is quite simple; we add a random angle that can range from -90 to 90 degrees to the entity's current pan angle. Then, a new loop ensures that the entity travels in the new direction for 10 frames, thus ensuring that it has moved away from the obstacle.

The code below will be executed if covered_dist is greater than 0.1 (the entity can move).

else

{

vec_set(temp_angle, player.x);

vec_sub(temp_angle, my.x);

vec_to_angle(my.pan, temp_angle);

my.tilt = 0;

}

If the entity can move, it will rotate towards the player, because this is its goal in the first place, right?

if (vec_dist(player.x, my.x) < 50)

break;

wait (1);

}

Finally, if the entity has found the player, it will use a "break" line of code to take a break ;)

ent_animate(my, "stand", 0, 0);

The last line of code switches the entity's animation from "walk" to "stand". It's a well-deserved rest for an entity that has done everything in its power to find the player.

}