GMS 2 AI pathfinding to closest point to player

trentallain

Member
Hi, I've come back to making a fire emblem style game with grid based movement and pathfinding. By using mp_grid_path, I can make my enemy characters move to the closest player character. And by removing points off of the path until it's within their movement and attack range, it works quite well. However, if a player character is already surrounded by enemies, a path obviously won't be found. What should I do so that the enemy will move as close as it can to it's target?
 

trentallain

Member
Here is the code if it helps
GML:
switch(ai_state) {
    case menu.inputting:
        // 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:
                    // Create AI 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);
                    // Find closest player unit
                    var _ai_target = ai_get_closest(_ai_unit.x,_ai_unit.y); // returns -1 if there are none, otherwise returns the closest player
                    // If a player was found
                    if _ai_target != -1 {
                        // Convert global.grid to an mp grid
                        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[# u, v] != -1 {
                                    // Set that position as taken in the mp grid
                                    mp_grid_add_cell(_ai_mp_grid, u, v);
                                }
                            }
                        }
                        // Clear starting position and clear 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 ai_selected
                            ai_selected = noone;
                            // Tell the unit its target
                            target = _ai_target;//ai_target = _ai_target;
                            // Clear path points
                            path_clear_points(ai_path);
                            // If there is a possible 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) {
                                // Delete end point of the path (because this is where the target is)
                                path_delete_point(ai_path, path_get_number(ai_path) - 1);        ////
                                // If the path has length
                                if path_get_number(ai_path) > 1 {   
                                    // 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 from _path_end onwards
                                        // Make sure the path doesn't exceed MP                   
                                        if (i > mp - 1) {
                                            // End path if out of MP
                                            break;
                                        }                   
                                        // Check range to the player
                                        var _in_range = point_distance(_xpos, _ypos, target.grid_x, target.grid_y) <= range;
                                        if (_in_range) {
                                            // End path if already in range
                                            break;
                                        }
                                    }
                                    // If the path has broken somewhere
                                    if _path_end != -1 {
                                        for (var i = path_get_number(ai_path); i > _path_end; i -= 1) {
                                            // Delete all remaining points
                                            path_delete_point(ai_path, i);
                                        }
                                    }
                                    // If the path still has enough points after deleting any points
                                    if path_get_number(ai_path) > 1 {
                                        other.ai_state = menu.paused;
                                        // 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] = id;
                                        grid_x = _end_x;
                                        grid_y = _end_y;
                                        // Follow the path
                                        path_start(ai_path, 1, path_action_stop, false);    // change speed to 1                   
                                        other.ai_controller_path = ai_path;
                                        // Tell the unit that AI is controlling it
                                        ai_selected = id;
                                    }
                                }
                            }
                            // Make the unit attack if possible
                            if point_distance(grid_x, grid_y, target.grid_x, target.grid_y) <= range {
                                unit_state = unit.attack;
                                other.ai_state = menu.paused;
                            }
                        }
                    }
                    // Clean up
                    mp_grid_destroy(_ai_mp_grid);
                    // This unit has finished its turn so remove it from the priority queue
                    ds_priority_delete_min(ai_unit_priority);
            }   
        }
        else {
            global.turn = "ally";
            global.menu_state = menu.inputting;
            global.created_ai_controller = false;
            ds_priority_destroy(ai_unit_priority);
            instance_destroy();
        }
    break;
}
Although, I'm only really asking about the mp_grid_path part, and how I can find a way to move as close to the target location as possible in the event that a path doesn't exist.
 
If no path is found, use mp_potential_step() function as a fallback. Keep checking periodically if you can find a valid path, if you do you can use mp_grid_path/path_start() again.
 
Top