GameMaker Collision avoidance with lengthdir help

M

mtski

Guest
Hello everyone,

I have been making steady progress on a game I have been working on (mostly to learn) but it is an RTS style game. Most of the time I am able to debug enough to resolve my own issues, however, I am coming across a problem I cannot seem to think through on my own. Perhaps its because I lack the geometry skill to resolve it.

Basically, I am just trying to get one unit to avoid colliding with a tree while it is going to its targetx and targety destination by travelling/ rotating around the tree's collision mask. Any help would be appreciated. Here is my horribly working code at the moment.

Code:
var xx = lengthdir_x(spd,dir)
var yy = lengthdir_y(spd,dir)

if place_empty(x + xx,y,obj_parent_resources) and place_empty(x + xx,y, obj_stickPile) {
 x += xx
}

if place_empty(x,y + yy,obj_parent_resources) and place_empty(x + xx,y, obj_stickPile) {
 y += yy
}

<maybe do something here?>
I have updated my code, but still having issues getting stuck on corners and unable to change direction properly. Anyone?
 
Last edited by a moderator:
A

André

Guest
I have the same issue here :c

game crashes or player get stuck when moving diagonaly in corners
 

curato

Member
for a rts of any complexity you will almost have to use paths or some sort of pathfinding algorithm.
 

NightFrost

Member
There are several options you can use. One would be the builtin pathfinding via mp_grid family of commands. Easy to set up if limited usability, will serve for very basic pathfinding.

Another option would be to build a basic steering behavior system. Steering is based on vectors, so it is advantageous to know about those, but a vector is an arrow, if you will, with direction and length. Your unit would have a velocity vector that gets added to its position every step to move it around. To get to a specified position, you construct (every step) an acceleration vector. It points towards your goal and has the length equal to unit's acceleration (acceleration can be set to equal max speed for instant speed). Acceleration vector gets added to the unit's velocity vector so its direction changes. Obstacles, when close enough, create avoidance vectors that point away from the obstacle, these are also added in. When all modifying vectors have been added to velocity, it gets shortened to equal max velocity and added to current position. (GML roadmap had at one point mention of native support to vectors maths, but it seems to have disappeared.)

Another option is context steering, which is an attempt to address certain shortcomings of steering behaviors. It gathers avoidance and goal data from nearby entities and uses these to choose the direction of least resistance.
 
What I do when manually plotting a path, is to set "waypoints" on an object and step by step move and react.

1) Define a basic shape for your checking object and avoidance object: get sprite width / height and divide by 2, or use xoffset / yoffset if not centre origin. Use those dimensions to make rectangle or square.

2) Use those known coordinates to see which corner the checking object is closest to, and you can start doing a path - either: one for anticlockwise, or alternate, or both.

3) Tree is stationary so don't need to account for it's movement, and can say has reached each corner in a defined sequence. Next corner anticlockwise is such and such, set target.

4) Tied equally with three is the use of angle difference. Compares two angles: current corner to next corner in sequence, and angle from current corner to final destination point. This is known to be either one / minus one (or zero) depending on which way around we are going. If the result is a certain way it is true that the angle of path to next corner is beyond the angle of final point, and that the path can be finished to final point.

All relatively straightforward, albeit with some slightly lengthy repetition. Angle difference is the only costly element here, but it allows for a path to break off in relation to bypassing unneeded corners.
create event:
Code:
path = path_add();
final_x = undefined;
final_y = undefined;
Code:
// get id of collision object: here I assume you already have coll id, which is called coll_id. Final_x / y set to destination point.
if path_exists(path)
{path_clear_points(path);}
path_add_point(path, x, y, 100); // clears path if already exists, and puts current start point

var other_width = coll_id.sprite_width / 2;
var other_height = coll_id.sprite_height / 2;
var self_width = (sprite_width / 2) + 5;
var self_height = (sprite_height / 2) + 5;

var self_x = x;
var self_y = y;
var self_left = self_x - self_width;
var self_right = self_x + self_width;
var self_top = self_y - self_height;
var self_bot = self_y + self_height;

var other_x = coll_id.x;
var other_y = coll_id.y;
var cur_left = other_x - other_width;
var cur_right = other_x + other_width;
var cur_top = other_y - other_height;
var cur_bot = other_y + other_height;

var top_diff = abs (self_y - (cur_top - self_height));
var bot_diff = abs (self_y - (cur_bot + self_height));
var mid_diff = abs(self_y - other_y);
var min_vert_diff = min(mid_diff, top_diff, bot_diff);

var left_diff = abs(self_x - (cur_left - self_width));
var right_diff = abs(self_x - (cur_right + self_width));
var min_horiz_diff = min(left_diff, right_diff);

var horizontal = 0;
var ang_diff = -1;

var i = 3;
repeat(4)
{array_left[i] = undefined;
i -= 1;}

if (self_right < cur_left) // the various positions to test to get nearest corner
{if (self_bot < cur_top)
{horizontal_left = 1;}
if ((self_y > cur_top) && (self_y < cur_bot)) || ((self_bot >= cur_top) && (self_bot <= cur_bot)) || ((self_top >= cur_top) && (self_top <= cur_bot))
{horizontal_left = 2;}
if (self_top > cur_bot)
{horizontal_left = 3;}}

// overlap of objects
if ((self_right >= cur_left) && (self_right <= cur_right)) || ((self_left >= cur_left) && (self_left <= cur_right)) || ((self_x > cur_left) && (self_x < cur_right))
{switch (min_vert_diff)
{case mid_diff:
switch (min_horiz_diff)
{case left_diff: horizontal_left = 2; break;
case right_diff: horizontal_left = 5; break;}
break;
case top_diff: horizontal_left = 7; break;
case bot_diff: horizontal_left = 8; break;}}

if (self_left > cur_right) // no overlap of objects
{if (self_bot < cur_top)
{horizontal_left = 4;}
if ((self_y > cur_top) && (self_y < cur_bot)) || ((self_bot >= cur_top) && (self_bot <= cur_bot))
|| ((self_top >= cur_top) && (self_top <= cur_bot))
{horizontal_left = 5;}
if self_top > cur_bot
{horizontal_left = 6;}}
Have a starting position of where the checking object is in relation to other object.
Code:
if horizontal_left != 0
{switch (horizontal_left)
{case 1:
array_left[0] = 2; array_left[1] = 4; array_left[2] = 3; array_left[3] = 1; break;
case 2:
array_left[0] = 2; array_left[1] = 4; array_left[2] = 3; array_left[3] = 1; break;
case 3:
array_left[0] = 4; array_left[1] = 3; array_left[2] = 1; array_left[3] = 2; break;
case 4:
array_left[0] = 1; array_left[1] = 2; array_left[2] = 4; array_left[3] = 3; break;
case 5:
array_left[0] = 3; array_left[1] = 1; array_left[2] = 2; array_left[3] = 4; break;
case 6:
array_left[0] = 3; array_left[1] = 1; array_left[2] = 2; array_left[3] = 4; break;
case 7:
array_left[0] = 1; array_left[1] = 2; array_left[2] = 4; array_left[3] = 3; break;
case 8:
array_left[0] = 4; array_left[1] = 3; array_left[2] = 1; array_left[3] = 2; break;}
}
Builds an array based on a predefined "route" around the corners, until it comes back to the first corner. The only data in each entry is the number of a corner. Thinking about it I have it done like this because it is for moving objects (I've chopped out a bit of my project here as it's not relevant), but in this case you could already set corners as actual coordinates in a 2d array, because the trees are static.
Code:
if is_array(array_left)
{
var size_left = array_length_1d(array_left);
var full_width = other_width + self_width;
var full_height = other_height + self_height;
var dir, dir2, new_ang_diff; // will define values later
cur_left = other_x - full_width ; // "supersize" other dimensions here, to include own width / height (and a bit extra) so that aiming for corner includes space to place self, and go around without collision
cur_right = other_x + full_width;
cur_top = other_y - full_height;
cur_bot = other_y + full_height;

for (var i = 0; i < size_left; i++)
{
left_count = array_left[i];

switch (left_count)
{case 1: first_x = cur_left; first_y = cur_top; break;
case 2: first_x = cur_left; first_y = cur_bot; break;
case 3: first_x = cur_right; first_y = cur_top; break;
case 4: first_x = cur_right; first_y = cur_bot; break;}

dir = point_direction(self_x, self_y, first_x, first_y);
dir_2 = point_direction(self_x, self_y, final_x, final_y);


new_ang_diff = sign(angle_difference(dir, dir_2));
if new_ang_diff == ang_diff
{path_add_point(path, first_x, first_y, 100);
}
else
{
path_add_point(path, final_x, final_y, 100);
path_set_closed(path, false);
path_set_kind(path, 0);
break;
}
self_x = first_x;
self_y = first_y;
}
}
array_left = 0;
Compares the angles between final point and next corner. Adds whichever point to path, and continues on, or exits with path created.

It looks like a lot, and is only configured here for static objects, but I don't think it has much use on resources. When I check the time taken it is generally between 45 to 60 microseconds, though I have no idea how that compares to other techniques.

NOTE: This is only for going anticlockwise around an object. To do clockwise (i.e compute both ways around) 'ang_diff' would be 1.
 
Last edited:
Top