Prototyping - Programming AI

The 'intelligence' part of our AI is simply just finding a path between 2 points. We'll use the A* algorithm on our collision map to produce arbitrary paths through the world. We'll use the paths to take enemy fighting ships to the player and then back to the mission path.

The design of this segment was covered in part 23.

GML Code

We add no new objects in this segment. We'll only be altering the obj_ship_ai object and adding a few scripts that support the A* algorithm

obj_ship_ai: Begin Step 3

Now that we're adding the active AI, we need to start by determining which AI mode the NPC should be be in. This is based mostly on the type of ship (combat or not) and the distance of the closest opponent ship.

///AI Mode select
if mode != AIMODE.inactive
{
    if ai_timer > 0
        ai_timer--
        
    if agent > 0 && !agent.is_player
    {
        if ai_timer < 1 then
        {
            switch agent.ship_type
            {
                case SHIPTYPE.hornet:
                case SHIPTYPE.stiletto:
                case SHIPTYPE.stingray:
                case SHIPTYPE.vi:
                case SHIPTYPE.vii:
                case SHIPTYPE.viii:
                {
                    /* Hunt or Move */
                    if mode == AIMODE.hunt && !instance_exists(target)
                    {
                        ds_stack_clear(astar_path_stack)
                        mode = AIMODE.path_seek
                    }
                    
                    if mode == AIMODE.move || mode == AIMODE.path_seek
                    {
                        var potential_target = find_closest_opponent()
                        if instance_exists(potential_target)
                        {
                            if point_distance(agent.x,agent.y,potential_target.x,potential_target.y) < 30*32
                            {
                                ds_stack_clear(astar_path_stack)
                                target = potential_target
                                mode = AIMODE.hunt
                            }
                        }
                    }
                
                }
            }
            ai_timer+=irandom_range(45,75)
        }
    }
}

///AI Mode select

if mode != AIMODE.inactive

{

if ai_timer > 0

ai_timer--

if agent > 0 && !agent.is_player

{

if ai_timer < 1 then

{

switch agent.ship_type

{

case SHIPTYPE.hornet:

case SHIPTYPE.stiletto:

case SHIPTYPE.stingray:

case SHIPTYPE.vi:

case SHIPTYPE.vii:

case SHIPTYPE.viii:

{

/* Hunt or Move */

if mode == AIMODE.hunt && !instance_exists(target)

{

ds_stack_clear(astar_path_stack)

mode = AIMODE.path_seek

}

if mode == AIMODE.move || mode == AIMODE.path_seek

{

var potential_target = find_closest_opponent()

if instance_exists(potential_target)

{

if point_distance(agent.x,agent.y,potential_target.x,potential_target.y) < 30*32

{

nbsp; ds_stack_clear(astar_path_stack)

target = potential_target

mode = AIMODE.hunt

}

ai_timer+=irandom_range(45,75)

}

obj_ship_ai: Begin Step 4

When the NPC is hunting a target, we need it to find a path to it with A* or follow the A* path if it already has one.

if mode == AIMODE.hunt && instance_exists(target) && agent > 0
{

    /* need new A* calc */
    if ds_stack_empty(astar_path_stack)
        ai_astar(agent.map_x, agent.map_y, target.map_x, target.map_y, 10)

    var diff_map_x = ai_next_x - agent.map_x;
    var diff_map_y = ai_next_y - agent.map_y;
    
    /* At the way, get the next waypoint */
    if diff_map_x == 0 && diff_map_y == 0
    {
        
        if ds_stack_empty(astar_path_stack)
            ai_astar(agent.map_x, agent.map_y, target.map_x+irandom_range(-12,12), target.map_y+irandom_range(-12,12),10)
        else
        {
            var next_waypoint = ds_stack_pop(astar_path_stack)
            ai_next_x = id_to_map_x(next_waypoint)
            ai_next_y = id_to_map_y(next_waypoint)
        }
        
    }
    
    if diff_map_x > 0 then ds_stack_push(agent.command_stack,"ai_right")
    if diff_map_x < 0 then ds_stack_push(agent.command_stack,"ai_left")
    if diff_map_y < 0 then ds_stack_push(agent.command_stack,"ai_up")
    if diff_map_y > 0 then ds_stack_push(agent.command_stack,"ai_down")
    
    /* Firing */
    if agent.fire_delay < 1 then
    {
        if abs(angle_difference(agent.direction, point_direction(agent.x,agent.y,target.x,target.y))) < 20
        {
            if point_distance(agent.x, agent.y, target.x, target.y) < 16*32
                ds_stack_push(agent.command_stack,"ai_fire")
        }
    }
    
    /* Reverse turn if target is directly behind */
    if abs(angle_difference(agent.direction, point_direction(agent.x,agent.y,target.x,target.y))) > 160
        ds_stack_push(agent.command_stack,choose("ai_right","ai_left","ai_up","ai_down"))
}

if mode == AIMODE.hunt && instance_exists(target) && agent > 0

{

/* need new A* calc */

if ds_stack_empty(astar_path_stack)

ai_astar(agent.map_x, agent.map_y, target.map_x, target.map_y, 10)

var diff_map_x = ai_next_x - agent.map_x;

var diff_map_y = ai_next_y - agent.map_y;

/* At the way, get the next waypoint */

if diff_map_x == 0 && diff_map_y == 0

{

if ds_stack_empty(astar_path_stack)

ai_astar(agent.map_x, agent.map_y, target.map_x+irandom_range(-12,12), target.map_y+irandom_range(-12,12),10)

else

{

var next_waypoint = ds_stack_pop(astar_path_stack)

ai_next_x = id_to_map_x(next_waypoint)

ai_next_y = id_to_map_y(next_waypoint)

}

if diff_map_x > 0 then ds_stack_push(agent.command_stack,"ai_right")

if diff_map_x < 0 then ds_stack_push(agent.command_stack,"ai_left")

if diff_map_y < 0 then ds_stack_push(agent.command_stack,"ai_up")

if diff_map_y > 0 then ds_stack_push(agent.command_stack,"ai_down")

/* Firing */

if agent.fire_delay < 1 then

{

if abs(angle_difference(agent.direction, point_direction(agent.x,agent.y,target.x,target.y))) < 20

{

if point_distance(agent.x, agent.y, target.x, target.y) < 16*32

ds_stack_push(agent.command_stack,"ai_fire")

}

/* Reverse turn if target is directly behind */

if abs(angle_difference(agent.direction, point_direction(agent.x,agent.y,target.x,target.y))) > 160

ds_stack_push(agent.command_stack,choose("ai_right","ai_left","ai_up","ai_down"))

}

obj_ship_ai: Begin Step 5

This handles the AI case where the ship is going back to the original mission path. If there is no planned path, it calls A* to find a valid path. If there it, is follows it until it's back on track.

if mode == AIMODE.path_seek
{

    /* need new A* calc */
    if ds_stack_empty(astar_path_stack)
        ai_astar(agent.map_x, agent.map_y, fixed_path_x[next_path_position], fixed_path_y[next_path_position], 24)
        
    var diff_map_x = ai_next_x - agent.map_x;
    var diff_map_y = ai_next_y - agent.map_y;
    
    /* At the way, get the next waypoint */
    if diff_map_x == 0 && diff_map_y == 0
    {
        
        if ds_stack_empty(astar_path_stack)
            ai_astar(agent.map_x, agent.map_y, fixed_path_x[next_path_position], fixed_path_y[next_path_position],10)
        else
        {
            var next_waypoint = ds_stack_pop(astar_path_stack)
            ai_next_x = id_to_map_x(next_waypoint)
            ai_next_y = id_to_map_y(next_waypoint)
        }
        
    }
    
    if diff_map_x > 0 then ds_stack_push(agent.command_stack,"ai_right")
    if diff_map_x < 0 then ds_stack_push(agent.command_stack,"ai_left")
    if diff_map_y < 0 then ds_stack_push(agent.command_stack,"ai_up")
    if diff_map_y > 0 then ds_stack_push(agent.command_stack,"ai_down")
    
    if abs(agent.map_x-fixed_path_x[next_path_position])+abs(agent.map_y-fixed_path_y[next_path_position]) < 3
        mode = AIMODE.move
}

if mode == AIMODE.path_seek

{

/* need new A* calc */

if ds_stack_empty(astar_path_stack)

ai_astar(agent.map_x, agent.map_y, fixed_path_x[next_path_position], fixed_path_y[next_path_position], 24)

var diff_map_x = ai_next_x - agent.map_x;

var diff_map_y = ai_next_y - agent.map_y;

/* At the way, get the next waypoint */

if diff_map_x == 0 && diff_map_y == 0

{

if ds_stack_empty(astar_path_stack)

ai_astar(agent.map_x, agent.map_y, fixed_path_x[next_path_position], fixed_path_y[next_path_position],10)

else

{

var next_waypoint = ds_stack_pop(astar_path_stack)

ai_next_x = id_to_map_x(next_waypoint)

ai_next_y = id_to_map_y(next_waypoint)

}

if diff_map_x > 0 then ds_stack_push(agent.command_stack,"ai_right")

if diff_map_x < 0 then ds_stack_push(agent.command_stack,"ai_left")

if diff_map_y < 0 then ds_stack_push(agent.command_stack,"ai_up")

if diff_map_y > 0 then ds_stack_push(agent.command_stack,"ai_down")

if abs(agent.map_x-fixed_path_x[next_path_position])+abs(agent.map_y-fixed_path_y[next_path_position]) < 3

mode = AIMODE.move

}

Script: find_closest_opponent

This script loops through all ships and finds the closest opponent.

/* This method can only be run by obj_ship_ai */
var ship;
var ship_id = -1;
var ship_dist = 10000;

for (var i=0; i<instance_number(obj_ship); i++)
{
    ship = instance_find(obj_ship,i)
    
    if ship.alignment != agent.alignment
    {
        if point_distance(agent.x, agent.y, ship.x, ship.y) < ship_dist
        {
            ship_id = ship
            ship_dist = point_distance(agent.x, agent.y, ship.x, ship.y)
        }
    }
}

return ship_id

/* This method can only be run by obj_ship_ai */

var ship;

var ship_id = -1;

var ship_dist = 10000;

for (var i=0; i<instance_number(obj_ship); i++)

{

ship = instance_find(obj_ship,i)

if ship.alignment != agent.alignment

{

if point_distance(agent.x, agent.y, ship.x, ship.y) < ship_dist

{

ship_id = ship

ship_dist = point_distance(agent.x, agent.y, ship.x, ship.y)

}

return ship_id

Script: id_to_map_x

Since I use unique IDs for each grid position, I need to convert that to the x grid coordinate

return argument0 mod 201

1	return argument0 mod 201

Script: id_to_map_y

Likewise for the y grid coordinate

return floor(argument0/201)

1	return floor(argument0/201)

Script: mh_dist

This is our heuristic for A*: The Manhattan Distance. Probably the best we can use in a 2D grid world.

/* Calculates Manhattan Distance */
//argument0 = x1
//argument1 = y1
//argument2 = x2
//argument3 = y2

return abs(argument0-argument2)+abs(argument1-argument3)

/* Calculates Manhattan Distance */

//argument0 = x1

//argument1 = y1

//argument2 = x2

//argument3 = y2

return abs(argument0-argument2)+abs(argument1-argument3)

Script: ai_star

Implementation of A* in GML.

/* Only call this from within obj_ship_ai
    Arg0 = start_map_x
    Arg1 = start_map_y
    Arg2 = end_map_x
    Arg3 = end_map_y
    Arg4 = Number of steps to solve for */
    
var start_x = argument0;
var start_y = argument1;
var goal_x = argument2;
var goal_y = argument3;
var max_steps = argument4;

var current_node, current_node_cost
var current_x, current_y;
var next_node, next_node_cost;
var next_x, next_y;

var goal_found = false;
var finished = false;

/* Clear previous A* information */
ds_priority_clear(astar_frontier_pq)
ds_list_clear(astar_closed_list)
ds_map_clear(astar_relation_map)
ds_map_clear(astar_cost_map)
ds_stack_clear(astar_path_stack)

/* Set Goal Node */
start_node = map_pos_to_id(start_x, start_y)
goal_node = map_pos_to_id(goal_x, goal_y)

/* Add the starting node to the frontier */
ds_priority_add(astar_frontier_pq, start_node, mh_dist(start_x, start_y, goal_x, goal_y))
ds_map_add(astar_relation_map, start_node, 0)
ds_map_add(astar_cost_map, start_node, 0)

/* Explore the frontier until the goal is found or the max distance is reached */
while !finished
{
    current_node_best = ds_priority_find_priority(astar_frontier_pq, ds_priority_find_min(astar_frontier_pq));
    current_node = ds_priority_delete_min(astar_frontier_pq);
    current_node_cost = ds_map_find_value(astar_cost_map, current_node);
    current_x = id_to_map_x(current_node)
    current_y = id_to_map_y(current_node)
    ds_list_add(astar_closed_list, current_node)
    
    if current_node == goal_node || current_node_cost == max_steps then
        goal_found = true
    else
    {
        /* Add all 4 neighbors to the frontier, if valid */
        for (var i=0; i<4; i++)
        {
            switch i
            {
                case 0: next_x = current_x-1; next_y = current_y; break;
                case 1: next_x = current_x+1; next_y = current_y; break;
                case 2: next_x = current_x; next_y = current_y-1; break;
                case 3: next_x = current_x; next_y = current_y+1; break;
                
            }
            
            /* If the neighbor isn't a barrier */
            if ds_grid_get(map.collision_map, next_x, next_y) == 0
            {
                var next_node = map_pos_to_id(next_x, next_y);
                var next_node_cost = current_node_cost + mh_dist(next_x, next_y, goal_x, goal_y)
                var in_closed = ds_list_find_index(astar_closed_list, next_node)
                var in_pq = ds_priority_find_priority(astar_frontier_pq, next_node)
                
                /* ...and hasn't already been explored */
                if in_closed < 0 && (is_undefined(in_pq) || in_pq <= 0)
                {
                    ds_priority_add(astar_frontier_pq, next_node, next_node_cost);
                    ds_map_add(astar_relation_map, next_node, current_node);
                    ds_map_add(astar_cost_map, next_node, current_node_cost+1);
                }
            }       
        }
    }
    
    if goal_found == true || ds_priority_empty(astar_frontier_pq)
        finished = true
}

/* Roll up the relation map (reverse traversal)*/
var rollup = false

while !rollup
{
    ds_stack_push(astar_path_stack, current_node)
    current_node = ds_map_find_value(astar_relation_map, current_node)
    if current_node == 0 then rollup = true
}

/* Kickoff our path at the first step */
if !ds_stack_empty(astar_path_stack)
{
    var first_step = ds_stack_pop(astar_path_stack)
    ai_next_x = id_to_map_x(first_step)
    ai_next_y = id_to_map_y(first_step)
}

100

101

102

103

/* Only call this from within obj_ship_ai

Arg0 = start_map_x

Arg1 = start_map_y

Arg2 = end_map_x

Arg3 = end_map_y

Arg4 = Number of steps to solve for */

var start_x = argument0;

var start_y = argument1;

var goal_x = argument2;

var goal_y = argument3;

var max_steps = argument4;

var current_node, current_node_cost

var current_x, current_y;

var next_node, next_node_cost;

var next_x, next_y;

var goal_found = false;

var finished = false;

/* Clear previous A* information */

ds_priority_clear(astar_frontier_pq)

ds_list_clear(astar_closed_list)

ds_map_clear(astar_relation_map)

ds_map_clear(astar_cost_map)

ds_stack_clear(astar_path_stack)

/* Set Goal Node */

start_node = map_pos_to_id(start_x, start_y)

goal_node = map_pos_to_id(goal_x, goal_y)

/* Add the starting node to the frontier */

ds_priority_add(astar_frontier_pq, start_node, mh_dist(start_x, start_y, goal_x, goal_y))

ds_map_add(astar_relation_map, start_node, 0)

ds_map_add(astar_cost_map, start_node, 0)

/* Explore the frontier until the goal is found or the max distance is reached */

while !finished

{

current_node_best = ds_priority_find_priority(astar_frontier_pq, ds_priority_find_min(astar_frontier_pq));

current_node = ds_priority_delete_min(astar_frontier_pq);

current_node_cost = ds_map_find_value(astar_cost_map, current_node);

current_x = id_to_map_x(current_node)

current_y = id_to_map_y(current_node)

ds_list_add(astar_closed_list, current_node)

if current_node == goal_node || current_node_cost == max_steps then

goal_found = true

else

{

/* Add all 4 neighbors to the frontier, if valid */

for (var i=0; i<4; i++)

{

switch i

{

case 0: next_x = current_x-1; next_y = current_y; break;

case 1: next_x = current_x+1; next_y = current_y; break;

case 2: next_x = current_x; next_y = current_y-1; break;

case 3: next_x = current_x; next_y = current_y+1; break;

}

/* If the neighbor isn't a barrier */

if ds_grid_get(map.collision_map, next_x, next_y) == 0

{

var next_node = map_pos_to_id(next_x, next_y);

var next_node_cost = current_node_cost + mh_dist(next_x, next_y, goal_x, goal_y)

var in_closed = ds_list_find_index(astar_closed_list, next_node)

var in_pq = ds_priority_find_priority(astar_frontier_pq, next_node)

/* ...and hasn't already been explored */

if in_closed < 0 && (is_undefined(in_pq) || in_pq <= 0)

{

ds_priority_add(astar_frontier_pq, next_node, next_node_cost);

ds_map_add(astar_relation_map, next_node, current_node);

ds_map_add(astar_cost_map, next_node, current_node_cost+1);

}

if goal_found == true || ds_priority_empty(astar_frontier_pq)

finished = true

}

/* Roll up the relation map (reverse traversal)*/

var rollup = false

while !rollup

{

ds_stack_push(astar_path_stack, current_node)

current_node = ds_map_find_value(astar_relation_map, current_node)

if current_node == 0 then rollup = true

}

/* Kickoff our path at the first step */

if !ds_stack_empty(astar_path_stack)

{

var first_step = ds_stack_pop(astar_path_stack)

ai_next_x = id_to_map_x(first_step)

ai_next_y = id_to_map_y(first_step)

}

Script: map_pos_to_id

Converts a map position given both coordinates to a unique value.

/* Converts a pair of map coordinates to a unique map ID */
return argument1*201 + argument0

1 2	/* Converts a pair of map coordinates to a unique map ID / return argument1201 + argument0

< Part 27 – HUD Programming	Part 29 – Default Mission >