Custom AI Pathfinding

T

TheNozza

Guest
This is a specific question related to code I have created in my studio's game.

On the old forums I asked for assistance in solving a pathfinding problem I have for AI. http://gmc.yoyogames.com/index.php?showtopic=680691#entry4898982

I am using GameMaker's pathfinding system to calculate a path to the target point (as designated by current behaviour of the object), but then using my own code to control speed as required. The AI is designed to control top-down walker robots, which travel essentially in straight lines. When they need to turn a corner, they must decelerate, stop, rotate, then are able to accelerate again. When going around straight sides of a building, everything works absolutely fine, but currently when the robots have to travel in a diagonal, they fail to get up to speed.

My code currently calculates the next corner, ie next point on the path at which to stop, based upon a sudden change in the path direction. During a diagonal path, the path changes direction nearly every grid cell, as that is the way A* works.

What else can I try to calculate the next 'path corner?' Deceleration at the final target is easy since I already have its coordinates, and speed control works for this already.
 

Nocturne

Friendly Tyrant
Forum Staff
Admin
One thing that comes to mind is to actually use the path_speed functionality. You could interpolate the path points to add one extra point half way between each of the actual points, then set the path speed of all the actual points to somethng like 10%. So now the robot will accelerate and slow down between each point on the path.
 
T

TheNozza

Guest
One thing that comes to mind is to actually use the path_speed functionality. You could interpolate the path points to add one extra point half way between each of the actual points, then set the path speed of all the actual points to somethng like 10%. So now the robot will accelerate and slow down between each point on the path.
Thanks for the speedy reply.

Path speed is something I specifically need to avoid, as I've run into many problems with it, and there are times when I need to control the robots' movement and speed outside of the boundaries of a path. My goal is to use A* to compute a path for me. I then grab the path points/coordinates that I need. This way, the object is not specifically 'locked' to the path, and I have a great freedom of movement with the object.

Interpolating points in between might help, if the diagonal path were at 45 degrees and I only used the interpolated points. In all other cases of a path section off a 90-degree angle, interpolation becomes useless, since it only gives me a half-way point when the path changes direction. When there is a slight angle, the path points calculated give mostly straight lines, with a small zig-zag in the middle. At least, I think that's how it works, right?

EDIT:
Sorry. I got confused with interpolation and the way A* works in GM. The grid would produce squares in such a way that any path direction will only be 90 degrees or 45 degrees, so interpolation would work for a diagonal path section. How would I go about interpolating all those new path points? This is new territory for me and a point in the right direction would be a big help.

Hopefully this is my eventual solution. Fingers crossed!
 
Last edited by a moderator:

Nocturne

Friendly Tyrant
Forum Staff
Admin
Okay, so you'd first create the path, then you'd loop through it and get all the path points into an array or something, before finally looping through them again and adding in another path point... so, roughly:

Code:
var path_points = path_get_number(path);
var p_array;

for (var i = 0; i < path_points; i++;)
{
p_array[i, 0] = path_get_point_x(path, i);
p_array[i, 1] = path_get_point_y(path, i);
}

for (var i = 0; i < path_points - 1; i++;)
{
path_change_point(path, 1, p_array[i, 0], p_array[i, 1], 10);
var pd = point_direction(p_array[i, 0], p_array[i, 1], p_array[i + 1, 0], p_array[i + 1, 1]);
var pr = point_distance(p_array[i, 0], p_array[i, 1], p_array[i + 1, 0], p_array[i + 1, 1]);
var px = p_array[i, 0] + lengthdir_x(pd / 2, pr);
var py = p_array[i, 1] + lengthdir_y(pd / 2, pr);
path_add_point(path, px, py, 100);
}
Something like that should work... :)
 
T

TheNozza

Guest
Thanks for the help.
I'm a little bit lost.

You used path_change_point, then calculated the new point positions, then added a new point at the calculated positions. I've never used path_change_point before, but after a quick read, shouldn't path_change_point come after the calc?

Additionally, the game is intended to run on consoles, and we could have many robots in the level at once, potentially 300. I'm guessing that this might be very CPU-intensive. I can certainly be more frugal about when a new path calc is run, but would all this cause significant lag if I were to be calcing a new path every step unchecked?
 

BLang

Member
If there's a problem with too many nodes when the paths are diagonal, you could just loop through all the nodes on the path, take every two nodes that are 1 node apart from one another, then, if those two nodes are 'within sight line' from eachother (i.e. !collision_line vs wall objects), delete the middle node.

I feel like I'm pretty crap at explaining this, so I made a lil picture to explain it better:



Would something like this be useful at all?
 
T

TheNozza

Guest
If there's a problem with too many nodes when the paths are diagonal, you could just loop through all the nodes on the path, take every two nodes that are 1 node apart from one another, then, if those two nodes are 'within sight line' from each other (i.e. !collision_line vs wall objects), delete the middle node.
The picture helped a little. All I need is the coordinates of the next corner at which to turn. If I were to simply try to find the next corner, would I write the code as the following?

Code:
//run mp_grid_path
for (n = 1; n < path_get_number(path); n += 1){
    x1 = path_get_point_x(path,0);
    y1 = path_get_point_y(path,0);
    x2 = path_get_point_x(path,n);
    y2 = path_get_point_y(path,n);
    if !(collision_line(x1,y1,x2,y2,obj_wall,0,1)
    && !collision(x1,y1,x2,y2,obj_obstacle,0,1) //I just add other obstacle objects in here that are included in the map grid
    ){
        target_point_n = n;
        }
    else{
        return (target_point_n);
        }
    }
 
Last edited by a moderator:
T

TheNozza

Guest
I suppose, yes. But that's not exactly what I meant. You can optimize your path by just removing all the corners where your object doesn't have to turn, and only keeping the ones where it does. That way, you can just make it turn every time and keep your code clean and simple.

I whipped up a small demo for you, give it a looksee.
Thanks very much for that. I've integrated the script successfully into my existing code, but a new problem has cropped up.

The robots have an alarming tendency to want to cut corners. This is happening even in your version. I suppose that I might be able to convince the project manager to accept this minor error and perhaps we could turn it into a feature, but can you think of how I might fix this?
 

Nocturne

Friendly Tyrant
Forum Staff
Admin
Does it only happen at the very start and the very end of the path? It could be that the robots are not perfectly aligned with the initial path point or the final path point is not aligned to the path grid, and so it cuts a corner to get to it.
 
T

TheNozza

Guest
Does it only happen at the very start and the very end of the path? It could be that the robots are not perfectly aligned with the initial path point or the final path point is not aligned to the path grid, and so it cuts a corner to get to it.
No that's not it at all.
The path points are aligned. The collision line checks from the origin point of the object, which is in most cases is the centre. So if the path runs really close, then the path line will run right up against the corner of the building, resulting in the sprites of the robot and building overlapping, which is not a desirable effect.
 

BLang

Member
I think I have an idea on how to fix it... It's happening because we're using collision_line, which basically means that we're disregarding our sprite size...
Give me a couple hours and I'll put up a fixed version!
 

BLang

Member
Alright, sorry about the double post, but I wanna make sure this is seen since I've spent quite a bit of time on this.
I'm pretty sure I've fixed the bugs you were talking about. At least, I can't reproduce them anymore. One thing that I wanna mention is that this is a bit more limited, in the sense that it assumes that your sprites are of equal dimensions, and with a centered origin. They don't have to be, but the results are going to be a bit less accurate.

Anyway, I'm pretty sure the link is the same, but here you go anyway.

I ran a speed test - doing the pathfinding and the path optimizing once a step (which is quite a lot for pathfinding) to random coordinates, and my fps never drops below 1000.
 
T

TheNozza

Guest
Alright, sorry about the double post, but I wanna make sure this is seen since I've spent quite a bit of time on this.
I'm pretty sure I've fixed the bugs you were talking about. At least, I can't reproduce them anymore. One thing that I wanna mention is that this is a bit more limited, in the sense that it assumes that your sprites are of equal dimensions, and with a centered origin. They don't have to be, but the results are going to be a bit less accurate.

Anyway, I'm pretty sure the link is the same, but here you go anyway.

I ran a speed test - doing the pathfinding and the path optimizing once a step (which is quite a lot for pathfinding) to random coordinates, and my fps never drops below 1000.
Thanks very much! It's all working fully as intended. Now I just need to work steadily on fixing when I actually generate a path and controlling speed a bit better. It should all be smooth sailing from here. ;)
 
Top