ChessMasterRiley
Member
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:
My Solution
Simple Project File: https://www.dropbox.com/s/zva7kh38jdfaxa6/Contextual Steering Behaviors.yyz?dl=0
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:
- 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.
- 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.
My Solution
Simple Project File: https://www.dropbox.com/s/zva7kh38jdfaxa6/Contextual Steering Behaviors.yyz?dl=0
Creation Code:
Step Code:
Draw 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
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
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)