GameMaker [solved] mp_grid_path AI move towards target with limited movement

T

trentallain

Guest
Is there a way I can get a path towards a target (such as an ally character) that is limited by how many move points (MP) the AI character has?

This is a grid turn based game, and I am trying to code some AI for it. Grid squares are 20px, and the grid size is 40x20.

Getting the paths for player controlled characters is pretty straightforward, because the player can choose a position to move to, however AI needs to plan to move towards a character even if it is outside its MP range.

One way I was thinking of doing it is getting a path to the target, not taking into account MP, and then make it follow the path to where the path point equals the MP. Would this work and be better than any other options?

Also how would I do this but also take into account the range that the AI character can attack from (a circle of grid squares around it, range is the radius in grid squares of this circle)? (no point in being a ranged character if it just walks right up next to the player)
 

Phil Strahl

Member
I am not an AI expert here, but how I would approach things would be like such:
  1. Regardless of move points, an enemy calculates the path to the target.
  2. Then it examines if its MP were sufficient. If yes and it's next to the target, check if the attack points (should you have those) are sufficient as well. If so, good, that's the preferred way to go then.
  3. If the MP aren't sufficient, it gets the tile it would end up on and checks if its target is within reach from that position. If yes, it could attack in certain circumstances (enough health/damage).
  4. If not, then the enemy could walk back on the path to a position where it is out of range of the target or even start looking for cover along the way.
I guess my point is braking the enemy behavior down and acting accordingly. You could also introduce a rating system where each option has a rating. The better the rating, the higher the chances the enemy will choose that path or strategy.
 
T

trentallain

Guest
I am not an AI expert here, but how I would approach things would be like such:
  1. Regardless of move points, an enemy calculates the path to the target.
  2. Then it examines if its MP were sufficient. If yes and it's next to the target, check if the attack points (should you have those) are sufficient as well. If so, good, that's the preferred way to go then.
  3. If the MP aren't sufficient, it gets the tile it would end up on and checks if its target is within reach from that position. If yes, it could attack in certain circumstances (enough health/damage).
  4. If not, then the enemy could walk back on the path to a position where it is out of range of the target or even start looking for cover along the way.
I guess my point is braking the enemy behavior down and acting accordingly. You could also introduce a rating system where each option has a rating. The better the rating, the higher the chances the enemy will choose that path or strategy.
I can't figure out why my AI units won't follow the path...
Here's what I have so far:
ai_get_closest:
Code:
/// @function ai_get_closest(x, y);
/// @function Return the closest target
/// @param x
/// @param y

// Get the closest target
var _x = argument[0];
var _y = argument[1];
var _ai_closest_priority = ds_priority_create();

// Loop through all characters
with (obj_character) {
    // If its team is not an enemy
    if team != "enemy" {
        // Add the target to the queue based on distance from unit
        var _target_distance = point_distance(_x, _y, x, y);
        ds_priority_add(_ai_closest_priority, id, _target_distance);
    }
}
// Get the closest target
var _closest_target = ds_priority_find_min(_ai_closest_priority);
ds_priority_destroy(_ai_closest_priority);

return _closest_target;
obj_ai_control create:
Code:
// Create a priority queue of all AI to be controlled, sorted by distance from the closest player unit
ai_unit_priority = ds_priority_create();
// Get camera active area
var _cx1 = camera_get_view_x(global.camera) - 50;
var _cy1 = camera_get_view_y(global.camera) - 50;
var _cx2 = camera_get_view_x(global.camera) + global.camera_w + 50;
var _cy2 = camera_get_view_y(global.camera) + global.camera_h + 50;
// Loop through all units
with (obj_character) {
    // If the team is enemy
    if team == "enemy" {
        // if the AI unit is within the camera active area
        if point_in_rectangle(x, y, _cx1, _cy1, _cx2, _cy2) {
            // Add to queue of AI units to control
            var _closest_player = ai_get_closest(x, y);
            var _player_distance = distance_to_object(_closest_player);
            ds_priority_add(other.ai_unit_priority, id, _player_distance);
        }
    }
}

// AI controller states
ai_state = menu.inputting;
obj_ai_control step:
Code:
// If there are AI units to be controlled
if ds_priority_size(ai_unit_priority) > 0 {
    // Get the AI unit that is the closest to the player
    var _ai_unit = ds_priority_find_min(ai_unit_priority);
    // If AI can input
    switch (ai_state) {
        case menu.inputting:
            // Find closest player unit
            var _ai_target = ai_get_closest(x, y);
            // Convert global.grid to an mp grid
            var _grid_w = ds_grid_width(global.grid);
            var _grid_h = ds_grid_height(global.grid);
            var _ai_mp_grid = mp_grid_create(0,0,_grid_w,_grid_h,grid.size,grid.size);
            for (var u = 0; u < _grid_w; u++) {
                for (var v = 0; v < _grid_h; v++) {
                    // If the grid position isn't free
                    if global.grid[# _ai_unit.grid_x, _ai_unit.grid_y] != -1 {
                        // Set that position as taken in the mp grid
                        mp_grid_add_cell(_ai_mp_grid, u, v);
                    }
                }
            }
            // Clear starting position and target position
            mp_grid_clear_cell(_ai_mp_grid,_ai_unit.grid_x,_ai_unit.grid_y);
            mp_grid_clear_cell(_ai_mp_grid,_ai_target.grid_x,_ai_target.grid_y);
            // Create path
            var _ai_path = path_add();
            // If there is a path
            with (_ai_unit) {
                // If there is a path
                if mp_grid_path(_ai_mp_grid, _ai_path, grid_x * grid.size, grid_y * grid.size, _ai_target.grid_x * grid.size, _ai_target.grid_y * grid.size, false) {
                    // Delete end point of the path (because this is where the target is)
                    var _ai_path_length = path_get_length(_ai_path) / grid.size;
                    path_delete_point(_ai_path, _ai_path_length - 1);
                    // Follow the path
                    path_start(_ai_path, 4, path_action_stop, false);   
                }
            }
            // Clean up
            mp_grid_destroy(_ai_mp_grid);
            path_delete(_ai_path);
            ds_priority_delete_min(ai_unit_priority);
            break;
    }   
}
else {
    // Change turns and clean up
    global.turn = "ally";
    global.menu_state = menu.inputting;
    global.created_ai_controller = false;
    ds_priority_destroy(ai_unit_priority);
    instance_destroy();
}
obj_control step:
Code:
// Change turns
if keyboard_check_pressed(vk_enter) {
    if global.turn == "enemy" {
        global.turn = "ally";
        // Unselect unit
        global.grid_selected = -1;
    }
    else {
        global.turn = "enemy";
        // Unselect unit
        global.grid_selected = -1;
    }
}
if global.turn == "enemy" {
    // Create only 1 AI controller
    if global.created_ai_controller == false {
        instance_create_layer(0,0,"layer_above",obj_ai_control);
        global.created_ai_controller = true;
    }
    global.menu_state = menu.paused;
}
On the player's turn, I can move around my own units and attack fine, however when I press enter to change turns to the AI, nothing happens and it just switches back to my turn. Also grid_x and grid_y are each unit's cell position on global.grid.
 

Relic

Member
While I don’t have the motivation to pour over this quite large amount of code, consider setting a break point in your code just when the AI code starts, run the game in debug mode and step through line by line until something unexpected happens - like an IF check not behaving as intended or paths always being returned as impossible.
 
T

trentallain

Guest
While I don’t have the motivation to pour over this quite large amount of code, consider setting a break point in your code just when the AI code starts, run the game in debug mode and step through line by line until something unexpected happens - like an IF check not behaving as intended or paths always being returned as impossible.
I tried doing some show_messages and debug messages and this is what I have found:
The majority of the mp grid has the positions as occupied (due to the for loop where I check if a position is free, and if it isn't, set it as occupied). That's not expected considering most of the map is unoccupied. However, I have tried commenting that line out and all the positions are then unoccupied. AI units still don't move the slightest amount with that line commented. The if mp_grid_path line is working and the path has length to it, however the units just don't go anywhere. Just to double check, I have also tried drawing their x coordinate to make sure the sprite is following correctly, but this is stationary too. So basically I have no idea.

In the below code, the only thing I changed is ai_get_closest(x,y) to ai_get_closest(_ai_unit.x,_ai_unit.y) because I realised I was using the incorrect coordinates for it.
Code:
// If there are AI units to be controlled
if ds_priority_size(ai_unit_priority) > 0 {
    // Get the AI unit that is the closest to the player
    var _ai_unit = ds_priority_find_min(ai_unit_priority);
    // If AI can input
    switch (ai_state) {
        case menu.inputting:
            // Find closest player unit
            var _ai_target = ai_get_closest(_ai_unit.x,_ai_unit.y);
            // Convert global.grid to an mp grid
            var _grid_w = ds_grid_width(global.grid);
            var _grid_h = ds_grid_height(global.grid);
            var _ai_mp_grid = mp_grid_create(0,0,_grid_w,_grid_h,grid.size,grid.size);
            for (var u = 0; u < _grid_w; u++) {
                for (var v = 0; v < _grid_h; v++) {
                    // If the grid position isn't free
                    if global.grid[# _ai_unit.grid_x, _ai_unit.grid_y] != -1 {
                        // Set that position as taken in the mp grid
                        mp_grid_add_cell(_ai_mp_grid, u, v);
                    }
                }
            }
            // Clear starting position and target position
            mp_grid_clear_cell(_ai_mp_grid,_ai_unit.grid_x,_ai_unit.grid_y);
            mp_grid_clear_cell(_ai_mp_grid,_ai_target.grid_x,_ai_target.grid_y);
            // Create path
            var _ai_path = path_add();
            // If there is a path
            with (_ai_unit) {
                // If there is a path
                if mp_grid_path(_ai_mp_grid, _ai_path, grid_x * grid.size, grid_y * grid.size, _ai_target.grid_x * grid.size, _ai_target.grid_y * grid.size, false) {
                    // Delete end point of the path (because this is where the target is)
                    var _ai_path_length = path_get_length(_ai_path) / grid.size;
                    path_delete_point(_ai_path, _ai_path_length - 1);
                    // Follow the path
                    path_start(_ai_path, 4, path_action_stop, false);   
                }
            }
            // Clean up
            mp_grid_destroy(_ai_mp_grid);
            path_delete(_ai_path);
            ds_priority_delete_min(ai_unit_priority);
            break;
    }   
}
else {
    // Change turns and clean up
    global.turn = "ally";
    global.menu_state = menu.inputting;
    global.created_ai_controller = false;
    ds_priority_destroy(ai_unit_priority);
    instance_destroy();
}
 

Relic

Member
Is deleting the _ai_path as soon as the ai is sent along it removing the ability for the ai to follow this path?

I think you need to keep the path around for a bit longer- try commenting out the deletion line in that cleanup section. If fixed you will need to do path cleanups after the ai reaches its target.
 
T

trentallain

Guest
Is deleting the _ai_path as soon as the ai is sent along it removing the ability for the ai to follow this path?

I think you need to keep the path around for a bit longer- try commenting out the deletion line in that cleanup section. If fixed you will need to do path cleanups after the ai reaches its target.
I changed the path to be local to the instance, so it only needs cleaning up if the instance is destroyed. I also tried getting rid of the delete last point of path code to see what would happen, and the unit actually moves towards you (onto the cell you are on) but only if you are right next to them... Also that stops working after like 3 turn changes.

Here's the current AI control step code:
Code:
// If there are AI units to be controlled
if ds_priority_size(ai_unit_priority) > 0 {
    // Get the AI unit that is the closest to the player
    var _ai_unit = ds_priority_find_min(ai_unit_priority);
    // If AI can input
    switch (ai_state) {
        case menu.inputting:
            // Find closest player unit
            var _ai_target = ai_get_closest(_ai_unit.x,_ai_unit.y);
            // Convert global.grid to an mp grid
            var _grid_w = ds_grid_width(global.grid);
            var _grid_h = ds_grid_height(global.grid);
            var _ai_mp_grid = mp_grid_create(0,0,_grid_w,_grid_h,grid.size,grid.size);
            for (var u = 0; u < _grid_w; u++) {
                for (var v = 0; v < _grid_h; v++) {
                    // If the grid position isn't free
                    if global.grid[# _ai_unit.grid_x, _ai_unit.grid_y] != -1 {
                        // Set that position as taken in the mp grid
                        mp_grid_add_cell(_ai_mp_grid, u, v);
                    }
                }
            }
            // Clear starting position and add target position
            mp_grid_clear_cell(_ai_mp_grid,_ai_unit.grid_x,_ai_unit.grid_y);
            mp_grid_clear_cell(_ai_mp_grid,_ai_target.grid_x,_ai_target.grid_y);
            // If there is a path
            with (_ai_unit) {
                // Clear path points
                path_clear_points(ai_path);
                // If there is a path
                if mp_grid_path(_ai_mp_grid, ai_path, grid_x * grid.size, grid_y * grid.size, _ai_target.grid_x * grid.size, _ai_target.grid_y * grid.size, false) {
                    // Delete end point of the path (because this is where the target is)
                    var _ai_path_length = path_get_length(ai_path) / grid.size;
                    path_delete_point(ai_path, _ai_path_length - 1);
                    // Follow the path
                    path_start(ai_path, 4, path_action_stop, false);   
                }
            }
            // Clean up
            mp_grid_destroy(_ai_mp_grid);
            ds_priority_delete_min(ai_unit_priority);
            break;
    }   
}
else {
    // Change turns and clean up
    global.turn = "ally";
    global.menu_state = menu.inputting;
    global.created_ai_controller = false;
    ds_priority_destroy(ai_unit_priority);
    instance_destroy();
}
PS: grid.size is 20.
 

Relic

Member
Where you find _ai_parh_length, by diving the path length by the grid size...

This will return a number like 3.5 if the target is 70 pixels away. You then try and delete the last point, by referring to the _ai_parh_length - 1... which here would be 2.5. Not only is this not a point (needs to be an integer) but this also might not be the last point. You have assumed that each path will be made into points equal to grid size in length- but a path could be just a straight line of only two points but span multiple grid cells in length.

Have a look in the manual to compare path_get_length and path_get_number.
 
T

trentallain

Guest
Where you find _ai_parh_length, by diving the path length by the grid size...

This will return a number like 3.5 if the target is 70 pixels away. You then try and delete the last point, by referring to the _ai_parh_length - 1... which here would be 2.5. Not only is this not a point (needs to be an integer) but this also might not be the last point. You have assumed that each path will be made into points equal to grid size in length- but a path could be just a straight line of only two points but span multiple grid cells in length.

Have a look in the manual to compare path_get_length and path_get_number.
Thanks for that! Still doesn't work though. I've also tried making the path always to the top left cell, however they don't even follow that.

Updated code:
Code:
// If there are AI units to be controlled
if ds_priority_size(ai_unit_priority) > 0 {
    // Get the AI unit that is the closest to the player
    var _ai_unit = ds_priority_find_min(ai_unit_priority);
    // If AI can input
    switch (ai_state) {
        case menu.inputting:
            // Find closest player unit
            var _ai_target = ai_get_closest(_ai_unit.x,_ai_unit.y);
            // Convert global.grid to an mp grid
            var _grid_w = ds_grid_width(global.grid);
            var _grid_h = ds_grid_height(global.grid);
            var _ai_mp_grid = mp_grid_create(0,0,_grid_w,_grid_h,grid.size,grid.size);
            for (var u = 0; u < _grid_w; u++) {
                for (var v = 0; v < _grid_h; v++) {
                    // If the grid position isn't free
                    if global.grid[# _ai_unit.grid_x, _ai_unit.grid_y] != -1 {
                        // Set that position as taken in the mp grid
                        mp_grid_add_cell(_ai_mp_grid, u, v);
                    }
                }
            }
            // Clear starting position and add target position
            mp_grid_clear_cell(_ai_mp_grid,_ai_unit.grid_x,_ai_unit.grid_y);
            mp_grid_clear_cell(_ai_mp_grid,_ai_target.grid_x,_ai_target.grid_y);
            // If there is a path
            with (_ai_unit) {
                // Clear path points
                path_clear_points(ai_path);
                // If there is a path
                if mp_grid_path(_ai_mp_grid, ai_path, grid_x * grid.size, grid_y * grid.size, _ai_target.grid_x * grid.size, _ai_target.grid_y * grid.size, 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);
                    // Follow the path
                    path_start(ai_path, 4, path_action_stop, false);   
                }
            }
            // Clean up
            mp_grid_destroy(_ai_mp_grid);
            ds_priority_delete_min(ai_unit_priority);
            break;
    }   
}
else {
    // Change turns and clean up
    global.turn = "ally";
    global.menu_state = menu.inputting;
    global.created_ai_controller = false;
    ds_priority_destroy(ai_unit_priority);
    instance_destroy();
}
 

Relic

Member
Might be time to look outside this code - any other code that sets speed of the ai units to 0, stops paths, deletes paths, set x and y coordinates back to some starting point. Would probably be in a step event or perhaps some code when a turn change happens.
 
T

trentallain

Guest
Updated the code a little bit again (realised I wasn't centering the path positions into the middle of the cell). I also tried commenting out the line where I set the mp grid cells as forbidden. This worked and the AI could move towards the closest target. However, they can only do it once because after that they just ran off (what???).

I am 99% sure it doesn't have any conflicting code.

Here's a quick test .exe in a .zip so you can see what is going on if that's helpful:
https://drive.google.com/open?id=157iAN8cV87Qxw09Lv6-EYAGghVNigs-X

Use left mouse button to select a unit and click on a green cell to move there. Press enter to change turns to the AI. It should automatically change turns back after it has moved. Use alt+f4 to quit.

Here's the relevant part of the code:
Code:
// If there are AI units to be controlled
if ds_priority_size(ai_unit_priority) > 0 {
    // Get the AI unit that is the closest to the player
    var _ai_unit = ds_priority_find_min(ai_unit_priority);
    // If AI can input
    switch (ai_state) {
        case menu.inputting:
            // Find closest player unit
            var _ai_target = ai_get_closest(_ai_unit.x,_ai_unit.y);
            // Convert global.grid to an mp grid
            var _grid_w = ds_grid_width(global.grid);
            var _grid_h = ds_grid_height(global.grid);
            var _ai_mp_grid = mp_grid_create(0,0,_grid_w,_grid_h,grid.size,grid.size);
            for (var u = 0; u < _grid_w; u++) {
                for (var v = 0; v < _grid_h; v++) {
                    // If the grid position isn't free
                    if global.grid[# _ai_unit.grid_x, _ai_unit.grid_y] != -1 {
                        // Set that position as taken in the mp grid
                        //mp_grid_add_cell(_ai_mp_grid, u, v);
                    }
                }
            }
            // Clear starting position and add target position
            mp_grid_clear_cell(_ai_mp_grid,_ai_unit.grid_x,_ai_unit.grid_y);
            mp_grid_clear_cell(_ai_mp_grid,_ai_target.grid_x,_ai_target.grid_y);
            // If there is a path
            with (_ai_unit) {
                // Clear path points
                path_clear_points(ai_path);
                // If there is a path
                if 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) {
                    other.ai_state = menu.paused;
                    // Delete end point of the path (because this is where the target is)
                    path_delete_point(ai_path, path_get_number(ai_path) - 1);
                    // Follow the path
                    path_start(ai_path, 4, path_action_stop, false);   
                }
            }
            // Clean up
            mp_grid_destroy(_ai_mp_grid);
            ds_priority_delete_min(ai_unit_priority);
            break;
    }   
}
else {
    // Change turns and clean up
    global.turn = "ally";
    global.menu_state = menu.inputting;
    global.created_ai_controller = false;
    ds_priority_destroy(ai_unit_priority);
    instance_destroy();
}
 
T

trentallain

Guest
Solved - had to update the grid coordinates on global.grid and their local grid_x/grid_y positions.
Code:
// Delete end point of the path (because this is where the target is)
path_delete_point(ai_path, path_get_number(ai_path) - 1);
// Update grid coordinates
global.grid[# grid_x, grid_y] = -1;
// Get the end point of the path in grid coordinates
var _end_x = path_get_point_x(ai_path, path_get_number(ai_path) - 1) div grid.size;
var _end_y = path_get_point_y(ai_path, path_get_number(ai_path) - 1) div grid.size;
global.grid[# _end_x, _end_y] = character;
grid_x = _end_x;
grid_y = _end_y;
// Follow the path
path_start(ai_path, 4, path_action_stop, false);
 
Top