GameMaker Getting as close as possible in a path

T

trentallain

Guest
What I was previously doing was generating a path between an AI unit and an opposing unit, however I now need to make the AI path smarter by making it so:

1. The number of path points isn't greater than the unit's MP (MP is the maximum amount of squares it can move).
2. The AI unit should try and get as close as possible to its closest target (even if the target is surrounded already) (-1 on global.grid signifies that it is a free position, anything other than that means the position is not free).
3. The AI unit shouldn't move any closer if its target is already within its range

If any of these issues occur in the path, I store that position so that I can delete all the path points after it occurs. It should find the first point where the path breaks.

This is my code of me trying to do it:
Code:
// Clear path points
path_clear_points(ai_path);
// Create the path regardless if you can fully traverse it
mp_grid_path(_ai_mp_grid, ai_path, grid_x * grid.size + 10, grid_y * grid.size + 10, _ai_target.grid_x * grid.size + 10, _ai_target.grid_y * grid.size + 10, false)
// Delete end point of the path (because this is where the target is)
path_delete_point(ai_path, path_get_number(ai_path) - 1);     
// Delete points that are either exceeding MP or are blocked
var _path_end = -1;
// Find where/if the path breaks
for (var i = 0; i < path_get_number(ai_path); ++i) {
    // Get path's grid coordinates at this position
    var _xpos = path_get_point_x(ai_path, i) div grid.size;
    var _ypos = path_get_point_y(ai_path, i) div grid.size;
    // Check if target is in range yet
    var _in_range = point_distance(_xpos, _ypos, ai_target.x, ai_target.y) < range;
    // If the path is larger than MP, or the position is taken on the grid, or the target is now within range
    if i > mp || global.grid[# _xpos, _ypos] != -1 || _in_range {
        // Set this point as the point to end the path at
        _path_end = i;
        break;
    }
}
// If the path has broken somewhere
if _path_end != -1 {
    for (var i = _path_end; i < path_get_number(ai_path); ++i) {
        // Delete all remaining points
        path_delete_point(ai_path, i);
    }
}
This code works as expected for generating a basic path, but only if I remove the parts where I find if the path breaks and where I delete the remaining points.

But when the full code is run, including those parts, my AI doesn't do anything at all.

And if I only use the i > mp part and not the other 2 situations, then my AI can move diagonally and doesn't appear to consider the amount of MP.

Could someone help me try and solve this please? So that it will cut the path where any of those 3 things occur and then deletes the remaining points.
 

Simon Gust

Member
I've never used mp grids but here is my understanding.

Skipping to the loop, you are checking every point of the path to the player, whether that point is:
1. further away than mp (whatever mp means)
or
2. not blocked
or
3. in range

So realistically, the first point found might already be valid.
using || instead of && messes with the logic a bit.

Example, the first point applies to (global.grid[# xpos, ypos] != -1),
then the point is already found and it doesn't search for better points.

blind shot to already confusing code ->
Code:
for (var i = 0; i < path_get_number(ai_path); ++i) 
{
    // Get path's grid coordinates at this position
    var _xpos = path_get_point_x(ai_path, i) div grid.size;
    var _ypos = path_get_point_y(ai_path, i) div grid.size;

    // check blocked cell ???
    /*
    if (global.grid[# _xpos, _ypos] == -1) {
        break;
    }
    */
    
    // i not greater than mp ???
    if (i <= mp1) {
        continue; // skip to next point
    }
    
    // accept path as valid path point
    _path_end = i;
    
    // add check to limit the max movement range on the enemy here
    /*
    if (i >= move_range_limit) {
        break;
    }
    */
    
    // check range to the player
    var _in_range = point_distance(_xpos, _ypos, ai_target.x, ai_target.y) < range; 
    if (_in_range) {
        break; // path already marked as valid, now just break to use this path, if not in range, the latest and furthest path is found.
    }
}
You may check the _in_range calculation, looks sketchy to me.

Another thing I don't understand is why you check inside the loop for blocked grid cells.
Why should they be blocked if the mp_grid paths around blocked cells?
 
T

trentallain

Guest
I've never used mp grids but here is my understanding.

Skipping to the loop, you are checking every point of the path to the player, whether that point is:
1. further away than mp (whatever mp means)
or
2. not blocked
or
3. in range

So realistically, the first point found might already be valid.
using || instead of && messes with the logic a bit.

Example, the first point applies to (global.grid[# xpos, ypos] != -1),
then the point is already found and it doesn't search for better points.

blind shot to already confusing code ->
Code:
for (var i = 0; i < path_get_number(ai_path); ++i)
{
    // Get path's grid coordinates at this position
    var _xpos = path_get_point_x(ai_path, i) div grid.size;
    var _ypos = path_get_point_y(ai_path, i) div grid.size;

    // check blocked cell ???
    /*
    if (global.grid[# _xpos, _ypos] == -1) {
        break;
    }
    */
   
    // i not greater than mp ???
    if (i <= mp1) {
        continue; // skip to next point
    }
   
    // accept path as valid path point
    _path_end = i;
   
    // add check to limit the max movement range on the enemy here
    /*
    if (i >= move_range_limit) {
        break;
    }
    */
   
    // check range to the player
    var _in_range = point_distance(_xpos, _ypos, ai_target.x, ai_target.y) < range;
    if (_in_range) {
        break; // path already marked as valid, now just break to use this path, if not in range, the latest and furthest path is found.
    }
}
You may check the _in_range calculation, looks sketchy to me.

Another thing I don't understand is why you check inside the loop for blocked grid cells.
Why should they be blocked if the mp_grid paths around blocked cells?
Thanks for your response!

I was checking inside the loop for blocked cells because I wasn't checking if mp_grid_path, I was just creating the path no matter what. I did this because I was trying to make the unit move as close as possible to its target, in which case mp_grid_path would fail if it couldn't reach it.

I think you're right with the _in_range calculation, I should be using ai_target.grid_x for its grid position (oops).
 

Simon Gust

Member
Thanks for your response!
I was checking inside the loop for blocked cells because I wasn't checking if mp_grid_path, I was just creating the path no matter what. I did this because I was trying to make the unit move as close as possible to its target, in which case mp_grid_path would fail if it couldn't reach it.
Still, there should be no way the path is blocked by an occupied cell, no matter where you decide to break the path.
 
T

trentallain

Guest
Still, there should be no way the path is blocked by an occupied cell, no matter where you decide to break the path.
That makes sense. Do you know how I would be able to move the AI unit as close as possible? Or a possible workaround?
 

Simon Gust

Member
That makes sense. Do you know how I would be able to move the AI unit as close as possible? Or a possible workaround?
It should already do that with this
Code:
var _in_range = point_distance(_xpos, _ypos, ai_target.grid_x, ai_target.grid_y) < range;
if (_in_range) {
    break; // path already marked as valid, now just break to use this path, if not in range, the latest and furthest path is found.
}
This will break the path on the very first cell the player get's in range to the enemy.
If the enemy is a melee dude, then you don't need that line as:
either the path is not long enough to the player (if you add the movement range check for the enemy)
or
the path ends in front of the player anyway
 

GMWolf

aka fel666
Look at Dijkstra s algorithm.
It's very simple, and very easy to adapt for what you need.
Once you understand it, adding an mp limite, range limit etc should be quite trivial.

For more complex ai, I like to use Dijkstra to generate a list of all tiles I can reach, and how much it will costs. For each of those tiles a calculate a score of how good it is to be in that position. Then I can easily choose the best tile to go to.
 
T

trentallain

Guest
It should already do that with this
Code:
var _in_range = point_distance(_xpos, _ypos, ai_target.grid_x, ai_target.grid_y) < range;
if (_in_range) {
    break; // path already marked as valid, now just break to use this path, if not in range, the latest and furthest path is found.
}
This will break the path on the very first cell the player get's in range to the enemy.
If the enemy is a melee dude, then you don't need that line as:
either the path is not long enough to the player (if you add the movement range check for the enemy)
or
the path ends in front of the player anyway
Code:
// Delete points that are either exceeding MP, blocked, or the path is already in range.
var _path_end = -1;
for (var i = 0; i < path_get_number(ai_path); ++i) {
    // Get path's grid coordinates at this position
    var _xpos = path_get_point_x(ai_path, i) div grid.size;
    var _ypos = path_get_point_y(ai_path, i) div grid.size;
        // Set path endpoint to this position
    _path_end = i;   
    // Make sure all of the following are correct, otherwise break out of loop and clear any remaining points
    // Make sure the position is free
    if (global.grid[# _xpos, _ypos] == -1) {
        break;
    }
    // Make sure the path doesn't exceed MP
    if (i > mp) {
        break;
    }
    // Check range to the player
    var _in_range = point_distance(_xpos, _ypos, ai_target.grid_x, ai_target.grid_y) < range; 
    if (_in_range) {
        break; // path already marked as valid, now just break to use this path, if not in range, the latest and furthest path is found.
    }
}
// If the path has broken somewhere
if _path_end != -1 {
    for (var i = _path_end; i < path_get_number(ai_path); ++i) {
        // Delete all remaining points
        path_delete_point(ai_path, i);
    }
}
I'm a bit confused as to why you said add checks here and commented out sections, however this is my interpretation.
It gives my AI the ability to move diagonally, sometimes moves them 1 square away, and doesn't limit it by MP.

I'm especially confused about the diagonal part because my original path has no diagonals...
 
Top