Avoiding Steering Behaviour and Pathfinding Using A Star

Main Features

• Obstacle Avoidance using Steering Behaviors
• Path navigation using A Star

Download demo and source

Introduction

This is a short demo utilizing both steering behaviors to avoid obstacles that are enclosed in bounding sphere and path navigation through a graph to avoid obstacles that are enclosed in bounding squares in a tower defense like game. The spiders will try to seek to the target (blue fiery portal) while avoiding obstacles using steering behavior while the marine will do the same but instead uses A* for its pathfinding.

I added tanks which acts as the towers and would rotate to face the furthest enemy as an added feature.

The avoidance steering behavior was implemented with the help from the book Programming Game AI by Mat Buckland.

The A* algorithm here was ported with permission from the book Programming an RTS Game with Direct3D by Carl Granberg. You can also find an in-depth explanation of the A* algorithm on this site: http://www.policyalmanac.org/games/aStarTutorial.htm written by Patrick Lester. I also carefully numbered the code(1 – 5 ) according to the A* steps as described in that site.

Particle effects using the example from the XNA creators club are utilized as portals to show starting points where the entities spawn and destination points where all the entities are headed. The demo also allows you to place towers in real time, and shows how the tower would rotate to face the furthest entity within its range.

I will only outline the important code, namely how the entities avoid obstacles with a bounding sphere and how the entities finds a path using A*.

So without further ado, let’s get going.

Obstacle avoidance using steering behavior

Each entity has a pointer to all the obstacles that are currently in the world. While the entity is on its way to a destination, it checks all obstacles that are within some defined distance and tags them as collidable.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void TagObstacles(float boxlength)
{
    for (int i = 0; i < obstacles.Count; i++)
    {
        obstacles[i].tag = false;

        // Line / Circle intersection test
        Vector3 to = entity.Position - obstacles[i].sphere.Center;
        float range = boxlength + obstacles[i].sphere.Radius;
        if (to.LengthSquared() < range * range)
        {
            obstacles[i].tag = true;
        }
    }
}

The boxLength defines a detection range that extends from the entities position. Once the potential collidables have been tagged, we go ahead and finding which one is the closest to the entity:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
for (int i = 0; i < obstacles.Count; i++)
{
    if (obstacles[i].tag)
    {
        // Calculate this obstacle's position in local space
        Matrix invert = Matrix.Invert(entity.WorldMatrix) * entity.UniformScale;
        Vector3 LocalPos = Vector3.Transform(obstacles[i].sphere.Center, invert);

        // Remember to scale local position to entities unifrom scale
        LocalPos *= entity.UniformScale;

        if (LocalPos.Z >= 0f)
        {
            //if the distance from the x axis to the object's position is less
            //than its radius + half the width of the detection box then there16
            //is a potential intersection.
            float ExpandedRadius = obstacles[i].sphere.Radius + entity.BoundingSphere.Radius;

            if (Math.Abs(LocalPos.X) < ExpandedRadius)
            {
                //now to do a line/circle intersection test. The center of the
                //circle is represented by (cX, cY). The intersection points are
                //given by the formula x = cX +/-sqrt(r^2-cY^2) for y=0.
                //We only need to look at the smallest positive value of x because
                //that will be the closest point of intersection.
                float cX = LocalPos.X;
                float cZ = LocalPos.Z;

                //we only need to calculate the sqrt part of the above equation once
                float SqrtPart = (float)Math.Sqrt((double)ExpandedRadius * (double)ExpandedRadius - (double)cX * (double)cX);

                if (Single.IsNaN(SqrtPart))
                {
                    continue;
                }

                float ip = cZ - SqrtPart;
                if (ip <= 0.0)
                {
                    ip = cZ + SqrtPart;
                }

                //test to see if this is the closest so far. If it is keep a
                //record of the obstacle and its local coordinates
                if (ip < distToClosest)
                {
                    distToClosest = ip;

                    obstacle = obstacles[i];
                    LocalPosOfClosestObstacle = LocalPos;
                }
            }
        }
    }
}

Then we generate a steering force that is perpendicular to the collision point, this way, the entity would steer towards the shorter route.

1
2
3
4
5
6
if (obstacle.sphere.Center != Vector3.Zero)
{
  Vector3 offset = entity.Position - obstacle.sphere.Center;
  SteeringForce = PerpendicularComponent(offset, entity.Forward);
  SteeringForce.Normalize();
}

And there you have it. The entities would steer away from the obstacles.

Pathfinding with A Star.

To start with A star, a graph needs to be created first for the A * algorithm to traverse. Our graph node is represented by a MapTile class, which has information that stores if the current node is walkable or not, which neighboring tiles it is connected to and its x, y coordinates. The following code shows how the map tiles are initially initialized.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
public void InitMapTiles()
{
    // Copy height values and initialize map tiles types
    for (int y = 0; y < size.Y; y++)
    {
        for (int x = 0; x < size.X; x++)
        {
            MapTile tile = GetMapTile(x, y);
            tile.mappos = new Point(x, y);
            tile.walkable = true;
        }
    }

    // Connect the map tiles using the neightbors[] pointers
    for (int y = 0; y < size.Y; y++)
    {
        for (int x = 0; x < size.X; x++)
        {
            MapTile tile = GetMapTile(x, y);
            if (tile != null && tile.walkable)
            {
                // Clear old connections
                for (int i = 0; i < 8; i++)
                    tile.neighbors[i] = null;

                // Possible neighbors
                Point[] p = {new Point(x-1, y-1), new Point(x, y-1), new Point(x+1, y-1),
            new Point(x-1, y),                    new Point(x+1, y),
            new Point(x-1, y+1), new Point(x, y+1), new Point(x+1, y+1)};

                // For each neighbor
                for (int i = 0; i < 8; i++)
                {
                    if (Within(p[i]))
                    {
                        MapTile neighbor = GetMapTile(p[i].X, p[i].Y);

                        // Only connect tiles if the neighbor is walkable
                        if (neighbor != null && neighbor.walkable)
                            tile.neighbors[i] = neighbor;
                    }
                }
            }
        }
    }
}

Now that we have a graph initialized with all its node walkable for now, every time an entity needs to travel from one location to another, a call to Graph::GetPath(…) will return all possible node positions and this would become the entities waypoints. GetPath is the actual A* implementation and the reason A* is faster than other graph searching algorithm is because it tries to search for the next available open node by gearing towards the final destination using a distance function.

Check out the accompanying demo for the A* implementation.

Suggested Improvement

• I’m a fan of tower defense games, that’s why I thought of coming up with this short demo. The tank’s cannon fires projectiles using the xml particle example from the XNA Creators website, but it does not consider the projectile hitting the target. You would want to add collision check for the projectile. It’s simple to do in XNA, just store a position from the tip of the projectile and do a bound check with an entity nearest to the projectile using the code here: http://www.xnawiki.com/index.php?title=Intersection_Checking.
• You would notice that when placing obstacles, it does not consider the moving entities, this makes an entity using the A star algorithm freeze in its path when an obstacle is added on its current position. Probably the quickest way to do this is to check all entities position and see if they are standing on the tile/node where the obstacle is about to be place.

Summary

I guess that’s about it. If you have any questions do let me know about it. All the graphic assets that come with this code come from the XNA community sites. The beast uses the steering behavior to get to its destination while the marine uses the A* algorithm.

You can see the drawback between the two – whereas the marine can only travel from node to node, whereas the beast would have problems reaching its destination when the obstacles are close to each other or there is not enough space in between the obstacles for the beast to squeeze itself into.

The demo that comes with this article also has other simple steering behaviors implemented – evade, pursuit, seek, arrive etc.

Thanks for reading if you have any questions don’t hesitate to post your comments here.