FaraWay: Dynamic Way Point Trails

Hi there,

it has been awhile! I won’t bore you with the details, but INK has been doing far better than expected! Thank you to everyone who has shared, supported, and purchased INK. It has been an absolute blessing!

During my INK development cycle, Sandy Gordon and Fellipe Martins have been working hard on the first project to be produced by our new studio, Spaceboy Games.

We will reveal more about the project soon, but for now, you can find information about it using the hashtag, #FaraWay.

Top-Down AI

Artificial Intelligence has never been my strong suit, but I have broken a lot of technical ground over the course of INK and recent demos. One thing that we wanted to do with #FaraWay was feature AI that understands the different layers of depth that are often seen in games like The Legend of Zelda. We felt that a lot of games of the genre feature dumb/repetitive AI (TLOZ) and/or flat terrain with limited obstacles (everyone else).

Multi-Layer Collision

The first step was actually getting collision along multiple terrain layers working properly. It isn’t exactly elegant, but I just decided to go with having two sets of collision objects. When the player (and other entities) collides with a set of stairs/ramp, I prepare to change the object’s collision layer. If the object leaves the stairs via bottom of the bounding box, the layer is set to one (or decreased). If the object leaves the stairs via the top of the bounding box, the opposite happens.

From there, it’s easy. Just call collision scripts against one group of objects when you layer is one, and call them against a second group of objects when your layer is two.

Path Finding

Ok, so we have enemies that collide with the different layers correctly. Great, but there’s no way in hell that they could navigate that terrain intelligently with traditional approaches (i.e. wander aimlessly and then move towards the player).

Now I can’t actually claim that this technique is my own. I’m sure someone has done this before, but I came up with it myself and thought that it was a solid approach that wouldn’t require a complex rendition of A* or Navigation Meshes.

The basic idea is that once the enemy has the player within line of sight (LOS), it’s easy. You just move the enemy towards the player. It becomes difficult when the player leaves LOS and hides behind complex terrain shapes (i.e. a U-shaped turn-around). I combat this by having the target object, often the player, generate way points.

A way point stores three pieces of information: an x-position, a y-position, and a layer. Way points are generated on two occasions: when the object loses LOS with the target or the target loses LOS with the last way point. This way, the object always has a visual connection with either the target or a way point (which has a visual connection with the next way point or the target).

From there, I iterate through the way points in two different ways. One, I iterate through them as the target. If the target turns around and run past an old way point, we don’t need it anymore. Two, when an enemy is close enough to a way point that it can see the next one, I get rid of the first one.

Other than that, the only thing that I’ve added is a maximum number of live way points for each enemy. Knowing this, you could probably outsmart the AI faster than most. For example, making four turns that block out each previous way point will get these pigs off of your trail.

Line of Sight

Determining appropriate LOS was actually the most difficult part for me, due to how I set up the multiple collision layers. I ended up extending Game Maker’s collision_line() script.


/// collision_line_ext(x1, y1, x2, y2, layer1, layer2);

// SAME LAYER //
if (argument4 == argument5) {
    if (argument4 == 1)
        return collision_line(argument0, argument1, argument2, argument3, oParSolid, false, false);
    else 
        return collision_line(argument0, argument1, argument2, argument3, oParSolid2, false, false);   

//DIFFERENT LAYER //
} else {
    var stairs = collision_line(argument0, argument1, argument2, argument3, oStairs, true, false);
    
    if (stairs != noone) {
        if (argument4 == 2) {
            return (argument3 <= stairs.bbox_bottom) || collision_line(argument0, argument1, argument2, argument3, oParSolid2, false, false);
        } else {
            return (argument1 <= stairs.bbox_bottom) || collision_line(argument0, argument1, argument2, argument3, oParSolid2, false, false);
        }
    } else {
        return true;
    }
} 

The code shown above may or may not make sense, but basically, the issue is only relevant when the object and the target are on different layers. If they're on the same layer, I just check if there are objects of the same layer between the two objects.

I ended up deciding that an object could see up and down stairs only. If there is a collision with stairs between the two objects, but no collision with solid objects, THEN the objects can see each other.

The complexity is probably not evident at first, but I can go into more detail if anyone is interested (it had to do with the bridges since they are not solid objects for either layer). An object standing on layer one, underneath a bridge, could see objects on layer two if there were no layer two collision objects between them.

Below I'll put the code used to generate way points. It is currently in the BEGIN_EVENT of the enemy objects that have path finding capabilities.


/// Pathfinding

if (pathfinding) {
    if (!waypoints) {
        if (instance_exists(oPlayer)) {
            // Player in sight
            if (!collision_line_ext(x, y, oPlayer.x, oPlayer.y, layer, oPlayer.layer)) {
                // Reset waypoints
                waypoints    = 0;
                
                // Target player
                target = oPlayer;
                
                // Save player coordinates
                txprev = oPlayer.x;
                typrev = oPlayer.y;
                tlayer = oPlayer.layer;
            } else {   
                // Create first waypoint
                var wpdir = point_direction(oPlayer.x, oPlayer.y, txprev, typrev);
                
                wx[0] = txprev + lengthdir_x(8, wpdir);
                wy[0] = typrev + lengthdir_y(8, wpdir);
                wt[0] = tlayer;
                
                target    = -1;                
                waypoints = 1; 
            }
        } else {
            // No player exists
            target      = -1;
            waypoints   = 0;
            pathfinding = false;
        }
    } else {
        if (instance_exists(oPlayer)) {
            var temp = waypoints;
            
            for (var i = (waypoints - 1); i >= 0; i -= 1) {
                if (!collision_line_ext(wx[i], wy[i], oPlayer.x, oPlayer.y, wt[i], oPlayer.layer)) {
                    temp = i;
                }
            }
            
            // Cut path
            if (temp  waypointsMax) {
                    target      = -1;
                    waypoints   = 0;
                    pathfinding = false;
                }
            }
        } else {
            // No player exists
            target      = -1;
            waypoints   = 0;
            pathfinding = false;
        }
    }
} else {
    if (instance_exists(oPlayer)) {
        // Player in sight
        if (!collision_line_ext(x, y, oPlayer.x, oPlayer.y, layer, oPlayer.layer)) {
            // Reset waypoints
            waypoints = 0;
            
            // Target player
            target = oPlayer;
            
            // Save player coordinates
            txprev = oPlayer.x;
            typrev = oPlayer.y;
            tlayer = oPlayer.layer;
            
            // Begin pathfinding
            pathfinding = true;
        } else {
            // Can't see player
            target      = -1;
            waypoints   = 0;
            pathfinding = false;
        }
    } else {
        // No player exists
        target      = -1;
        waypoints   = 0;
        pathfinding = false;
    }
}

The system is VERY simple when applied to single layer, top-down games. It is likely that I will package this up nicely for the Game Maker Marketplace. In the mean time, if you'd like to use/modify the portions above, please feel free!

#FaraWay development is streamed every Saturday at 11AM PST.
The host(s) will rotate each week (Fellipe, Sandy, Alejandro/Myself, repeat).

Thank you again for all of the continuous support and encouragement,
-Z

Advertisements
FaraWay: Dynamic Way Point Trails

One thought on “FaraWay: Dynamic Way Point Trails

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s