Contextual Steering Behaviors (Improvements?)

Hello all,

I wanted to start a thread on developing efficient contextual steering behaviors in GM. The idea for this solution for steering behavior is based on this article from Andrew Fray: https://andrewfray.wordpress.com/2013/03/26/context-behaviours-know-how-to-share/. The intended final use is in conjunction with A* pathfinding, so, of course, this solution doesn't need to do any complex pathfinding - just object avoidance and weighting directional choices.

The gist of the solution is as follows:

Step 1 - Interest Map
An interest map is generated using radial sensors, valuing the directions based on interest in going in that direction. To keep things simple, I am only using a single interest source for now - the direction of the goal. E.g.:


Step 2 - Danger Map
A danger map is generated using similar radial sensors, valuing "dangers" or bad directions and weighting primarily based on proximity (in more complex applications, different weights can be applied based on object type or other factors).


Step 3 - Computation of Inputs
An algorithm looks at the input from both the interest sensors and the danger sensors and calculates a desired resulting direction.


Purpose of Post
The purpose of this post is two fold:
  1. Solution Feedback. My solution is posted below - I would greatly appreciate any suggested improvements for a more efficient solution. It is already quite performant, but I would like to be able to have a large number of agents using this steering behavior at any point. So...efficiency is important here and any extra efficiency would be greatly helpful.
  2. Alternative Solution Algorithm. My solution below resolves the inputs as follows: (a) Ignore all sensor directions with a danger sensor over a fixed amount (b) average the remaining interest directions with an added weight based on current direction to favor directions close to the current direction. As a note, I weight the danger sensor collisions based on object type with walls giving full weight and other units given half weight. The results are pretty good, but I am all ears for better solutions.
As a note, I did try the solution proffered by the article: "Find the slot with the lowest danger, or as will probably be the case the set of slots with the equal lowest danger. Look in the corresponding slots in the interest map and pick the slot with the highest interest. For a tiebreak, pick the slot that is closest to our current heading." This resulted in rather choppy movement though because the lowest danger sensors changed too frequently.

My Solution

Simple Project File: https://www.dropbox.com/s/zva7kh38jdfaxa6/Contextual Steering Behaviors.yyz?dl=0

Creation Code:
GML:
spd = 2 //move speed for demonstration purposes

oa_sensor_count = 24 //set initial sensor count
oa_interest_sensor = array_create(oa_sensor_count) //initialize array for interest sensors
oa_danger_sensor = array_create(oa_sensor_count) //initialize array for danger sensors
oa_sensor_length = 256 //sensor length
oa_result = 0 //initialize resulting direction variable

//initialize target location variables
target_x = obj_goal.x
target_y = obj_goal.y
Step Code:
GML:
//----- Update Target Location Variables -----\\
target_x = obj_goal.x
target_y = obj_goal.y

//----- Increase or Decrease Sensor Count -----\\
if mouse_wheel_up() oa_sensor_count += 1
if mouse_wheel_down() oa_sensor_count -= 1
if oa_sensor_count < 4 oa_sensor_count = 4

//----- Set Interest Sensors -----\\
var i,angle,goal_direction,difference;
goal_direction = point_direction(x,y,target_x,target_y) //find target direction
for (i=0;i<oa_sensor_count;i++) //loop through all interest sensors
    {
    angle = (360 / oa_sensor_count) * i //direction of current sensor
    difference = abs(angle_difference(angle,goal_direction)) //find angle difference of sensor from goal direction
    oa_interest_sensor[i] = (180 - difference) / 180 //set sensor to normalized difference
    }

//----- Set Danger Sensors -----\\
var j,n,col,distance,list,weight;
for (i=0;i<oa_sensor_count;i++)
    {
    oa_danger_sensor[i] = 0 //reset danger sensor to 0
    angle = (360 / oa_sensor_count) * i //direction of current sensor
    list = ds_list_create() //create list for collision line detection
    //fill list with collidable targets (par_detectable)
    n = collision_line_list(x,y,x+lengthdir_x(oa_sensor_length,angle),y+lengthdir_y(oa_sensor_length,angle),par_detectable,1,1,list,0)
    //loop through list of collidable instances to affect danger sensors
    for (j=0;j<n;j++)
        {
        col = ds_list_find_value(list,j) //get collidable instance
        distance = point_distance(x,y,col.x,col.y) //get distance to collidable instance origin
        switch col.object_index //set danger weight based on object type
            {
            case obj_wall: weight = 1.0; break; //full weight if wall
            case obj_unit: weight = 0.5; break; //half weight if unit
            }
        //set danger sensor based on distance from collidable instance and weight
        oa_danger_sensor[i] = max(oa_danger_sensor[i],(oa_sensor_length - distance) / oa_sensor_length * weight);
        }
    ds_list_destroy(list) //free up collision list
    }

//----- Calculate Resulting Direction -----\\
var i,result_x,result_y,potential_list,dir;

//populate potential direction list with danger directions below a fixed amount
potential_list = ds_list_create()
for (i=0;i<oa_sensor_count;i++)
    {
    //if danger result is < .4 add to "OK" directions list
    if oa_danger_sensor[i] < .4
        {
        ds_list_add(potential_list,i)
        }
    }

//average interest directions from potential list weighted based on interest direction value
var potential_direction,interest,diff;
result_x = 0
result_y = 0
for (i=0;i<ds_list_size(potential_list);i++)
    {
    potential_direction = ds_list_find_value(potential_list,i)
    interest = oa_interest_sensor[potential_direction]
    dir = (360 / oa_sensor_count) * potential_direction
    //further weight based on how close direction is to current direction to favor current direction
    diff = abs(angle_difference(dir,oa_result))
    result_x += lengthdir_x(interest,dir) * sqr((180 - diff) / 180)
    result_y += lengthdir_y(interest,dir) * sqr((180 - diff) / 180)
    }
    
ds_list_destroy(potential_list)
oa_result = point_direction(0,0,result_x,result_y)

//----- Movement and image_angle Update -----\\
x += lengthdir_x(spd,oa_result)
y += lengthdir_y(spd,oa_result)
image_angle -= angle_difference(image_angle,oa_result)/8
Draw Code:
GML:
draw_self()

draw_set_alpha(.5)

//----- Draw Danger Sensors -----\\
var i,current,len,dir;
draw_set_color(c_red)
for (i=0;i<oa_sensor_count;i++)
    {
    current = oa_danger_sensor[i]
    len = current * oa_sensor_length
    dir = (360 / oa_sensor_count) * i
    draw_line_width(x,y,x+lengthdir_x(len,dir),y+lengthdir_y(len,dir),3)
    }

//----- Draw Interest Sensors -----\\
draw_set_color(c_lime)
for (i=0;i<oa_sensor_count;i++)
    {
    current = oa_interest_sensor[i]
    len = current * oa_sensor_length
    dir = (360 / oa_sensor_count) * i
    draw_line(x,y,x+lengthdir_x(len,dir),y+lengthdir_y(len,dir))
    }

//----- Draw Resulting Direction -----\\
draw_set_color(c_aqua)
len = 256
dir = oa_result
draw_line(x,y,x+lengthdir_x(len,dir),y+lengthdir_y(len,dir))

draw_set_alpha(1)
 
Top