VHS AI Enemy Pathfinding

#macro PATHFINDING_GRID_CELL_DIVISOR 2
#macro PATHFINDING_GRID_CELL_DIAGONAL_COST (1.4)
#macro PATHFINDING_GRID_CELL_DIAGONAL_ENABLED false

enum E_ENEMY_PATHFINDING_TILE_TYPES {
    EMPTY,
    DOOR_OPEN,
    DOOR_CLOSED,
    WINDOW_OPEN,
    WINDOW_CLOSED,
    WALL
}

function enemy_pathfinding_node(_x, _y, _type) constructor  {
    x = _x;
    y = _y;
    type = _type;
    traversable = true;
    neighbors = [];

    cost_base = 1.0;
    cost_from_start = infinity;
    cost_to_goal = infinity;
    cost_total = infinity;
    parent = undefined;
    priority_queue_added = false;

    function add_neighbor(_neighbor)    {
        var _neighbor_is_diagonal = (abs(x - _neighbor.x) == 1 and abs(y - _neighbor.y) == 1);
        if ((not PATHFINDING_GRID_CELL_DIAGONAL_ENABLED) and _neighbor_is_diagonal) return;
        var _diagonal_cost = _neighbor_is_diagonal ? (PATHFINDING_GRID_CELL_DIAGONAL_COST) : (0.0);
        var _neighbor_cost = cost_base + _neighbor.cost_base + _diagonal_cost;
        var _neighbor_object = {
            node: _neighbor,
            cost: _neighbor_cost
        }
        array_push(neighbors, _neighbor_object);
    }
    function costs_reset()  {
        cost_from_start = infinity;
        cost_to_goal = infinity;
        cost_total = infinity;
        parent = undefined;
        priority_queue_added = false;
    }
    function init() {
        switch (type)  {
            case E_ENEMY_PATHFINDING_TILE_TYPES.EMPTY:
                traversable = true;
                cost_base = 1.0;
                break;

            case E_ENEMY_PATHFINDING_TILE_TYPES.DOOR_OPEN:
                traversable = true;
                cost_base = 1.0;
                break;

            case E_ENEMY_PATHFINDING_TILE_TYPES.DOOR_CLOSED:
                traversable = true;
                cost_base = 10.0;
                break;

            case E_ENEMY_PATHFINDING_TILE_TYPES.WINDOW_OPEN:
                traversable = true;
                cost_base = 2.0;
                break;

            case E_ENEMY_PATHFINDING_TILE_TYPES.WINDOW_CLOSED:
                traversable = true;
                cost_base = 4.0;
                break;

            case E_ENEMY_PATHFINDING_TILE_TYPES.WALL:
                traversable = false;
                cost_base = infinity;
                break;
        }
    }
}

function init_pathfinding() {
    pathfinding_priority_queue = ds_priority_create();
    pathfinding_grid_cell_size = (GRID_CELL_SIZE / PATHFINDING_GRID_CELL_DIVISOR);

    var _level_current = global.master_instance.level_selected_current;
    enemy_pathfinding_grid_width = ceil(global.level_border_width / pathfinding_grid_cell_size);
    enemy_pathfinding_grid_height = ceil(global.level_border_height / pathfinding_grid_cell_size);
    enemy_pathfinding_cells_affected = {};

    execute_grid_bake();

    pathfinding_debug = false;
}

function execute_grid_reset_costs() {
    for (var _grid_x = 0; _grid_x < enemy_pathfinding_grid_width; _grid_x ++) {
        for (var _grid_y = 0; _grid_y < enemy_pathfinding_grid_height; _grid_y ++) {
            enemy_pathfinding_grid[_grid_x][_grid_y].costs_reset();
        }
    }
}
function execute_grid_add_object(_instance_id, _type)  {
    var _instance_uuid = string(_instance_id.uuid);
    var _cell_left = floor(_instance_id.bbox_left / pathfinding_grid_cell_size);
    var _cell_top = floor(_instance_id.bbox_top / pathfinding_grid_cell_size);
    var _cell_right = floor((_instance_id.bbox_right - 1) / pathfinding_grid_cell_size);
    var _cell_bottom = floor((_instance_id.bbox_bottom - 1) / pathfinding_grid_cell_size);

    for (var _grid_x = _cell_left; _grid_x <= _cell_right; _grid_x ++) {
        for (var _grid_y = _cell_top; _grid_y <= _cell_bottom; _grid_y ++) {
            var _affected_cells_array = enemy_pathfinding_cells_affected[$ _instance_uuid];
            if is_undefined(_affected_cells_array) {
                _affected_cells_array = [];
                enemy_pathfinding_cells_affected[$ _instance_uuid] = _affected_cells_array;
            }
            if not return_pathfinding_coordinate_valid(_grid_x, _grid_y) {
                continue;
            }
            var _node = enemy_pathfinding_grid[_grid_x][_grid_y];
            _node.type = _type;
            _node.init();

            array_push(_affected_cells_array, _node);
        }
    }
}
function execute_grid_update_object(_instance_id, _type)   {
    var _instance_uuid = _instance_id.uuid;
    var _affected_cells = enemy_pathfinding_cells_affected[$ _instance_uuid];
    if is_undefined(_affected_cells) {
        return;
    }
    for (var _cell_index = 0; _cell_index < array_length(_affected_cells); _cell_index++) {
        var _cell = _affected_cells[_cell_index];
        _cell.type = _type;
        _cell.init();
        _cell.neighbors = [];
        for (var _neighbor_offset_x = -1; _neighbor_offset_x <= 1; _neighbor_offset_x++) {
            for (var _neighbor_offset_y = -1; _neighbor_offset_y <= 1; _neighbor_offset_y++) {
                var _neighbor_x = _cell.x + _neighbor_offset_x;
                var _neighbor_y = _cell.y + _neighbor_offset_y;
                if return_pathfinding_coordinate_valid(_neighbor_x, _neighbor_y) {
                    var _neighbor = enemy_pathfinding_grid[_neighbor_x][_neighbor_y];
                    if _neighbor.traversable {
                        _cell.add_neighbor(_neighbor);
                    }
                }
            }
        }
    }
}
function execute_grid_bake()    {
    enemy_pathfinding_grid = [];
    for (var _grid_x = 0; _grid_x < enemy_pathfinding_grid_width; _grid_x ++) {
        enemy_pathfinding_grid[_grid_x] = [];
        for (var _grid_y = 0; _grid_y < enemy_pathfinding_grid_height; _grid_y ++) {
            var _node_object = new enemy_pathfinding_node(_grid_x, _grid_y, E_ENEMY_PATHFINDING_TILE_TYPES.EMPTY);
            _node_object.init();
            enemy_pathfinding_grid[_grid_x][_grid_y] = _node_object;
        }
    }

    var _level_cell_coordinates = return_pathfinding_cell_coordinate;
    with (Wall) {
        other.execute_grid_add_object(id, E_ENEMY_PATHFINDING_TILE_TYPES.WALL);
    }

    with (Door) {
        var _mask_index = mask_index;
        mask_index = mskWall;
        if not opened   {
            other.execute_grid_add_object(id, E_ENEMY_PATHFINDING_TILE_TYPES.DOOR_CLOSED);
        }
        mask_index = _mask_index;
    }

    with (Corner)   {
        other.execute_grid_add_object(id, E_ENEMY_PATHFINDING_TILE_TYPES.WALL);
    }

    with (Window)   {
        var _type = window_barricaded ? E_ENEMY_PATHFINDING_TILE_TYPES.WINDOW_CLOSED : E_ENEMY_PATHFINDING_TILE_TYPES.WINDOW_OPEN;
        other.execute_grid_add_object(id, _type);
    }

    for (var _grid_x = 0; _grid_x < enemy_pathfinding_grid_width; _grid_x ++) {
        for (var _grid_y = 0; _grid_y < enemy_pathfinding_grid_height; _grid_y ++) {
            for (var _neighbor_x = -1; _neighbor_x <= 1; _neighbor_x ++) {
                for (var _neighbor_y = -1; _neighbor_y <= 1; _neighbor_y ++) {
                    var _neighbor_x_index = _grid_x + _neighbor_x;
                    var _neighbor_y_index = _grid_y + _neighbor_y;
                    var _neighbor_coordinate_valid = return_pathfinding_coordinate_valid(_neighbor_x_index, _neighbor_y_index);
                    if (_neighbor_coordinate_valid) {
                        var _neighbor_node = enemy_pathfinding_grid[_neighbor_x_index][_neighbor_y_index];
                        if (_neighbor_node.traversable) {
                            enemy_pathfinding_grid[_grid_x][_grid_y].add_neighbor(_neighbor_node);
                        }
                    }
                }
            }
        }
    }
}

function return_pathfinding_coordinate_valid(_cell_x, _cell_y)  {
    if (_cell_x < 0 || _cell_x >= enemy_pathfinding_grid_width) {
        return false;
    }
    if (_cell_y < 0 || _cell_y >= enemy_pathfinding_grid_height) {
        return false;
    }
    return true;
}
function return_pathfinding_result(_node_begin, _node_end) {
    execute_grid_reset_costs();
    ds_priority_clear(pathfinding_priority_queue);
    var _enemy_pathfinding_open = [];
    _node_begin.cost_from_start = 0;
    _node_begin.cost_to_goal = return_pathfinding_heuristic(_node_begin, _node_end);
    _node_begin.cost_total = _node_begin.cost_to_goal;
    ds_priority_add(pathfinding_priority_queue, _node_begin, _node_begin.cost_total);

    var _nearest_traversable_node = undefined;
    var _min_distance = infinity;

    while (not ds_priority_empty(pathfinding_priority_queue)) {
        var _node_current = ds_priority_delete_min(pathfinding_priority_queue);

        if (return_pathfinding_coordinate_valid(_node_current.x, _node_current.y)) {
            var _distance_to_end = return_pathfinding_heuristic(_node_current, _node_end);
            if (_distance_to_end < _min_distance) {
                _nearest_traversable_node = _node_current;
                _min_distance = _distance_to_end;
            }
        }

        if (_node_current == _node_end) {
            if return_pathfinding_coordinate_valid(_node_end.x, _node_end.y) {
                return return_pathfinding_path_array_reconstructed(_node_begin, _node_end);
            }
        }

        for (var _neighbor_index = 0; _neighbor_index < array_length(_node_current.neighbors); _neighbor_index++) {
            var _neighbor_object = _node_current.neighbors[_neighbor_index];
            var _neighbor_node = _neighbor_object.node;
            var _neighbor_cost = _neighbor_object.cost;
            var _cost_from_start = _node_current.cost_from_start + _neighbor_cost;
            var _cost_to_goal = return_pathfinding_heuristic(_neighbor_node, _node_end);
            var _cost_total = _cost_from_start + _cost_to_goal;

            if (_cost_total < _neighbor_node.cost_total) {
                _neighbor_node.cost_from_start = _cost_from_start;
                _neighbor_node.cost_to_goal = _cost_to_goal;
                _neighbor_node.cost_total = _cost_total;
                _neighbor_node.parent = _node_current;

                if not _neighbor_node.priority_queue_added {
                    ds_priority_add(pathfinding_priority_queue, _neighbor_node, _neighbor_node.cost_total);
                    _neighbor_node.priority_queue_added = true;
                }
            }
        }
    }

    if (_nearest_traversable_node != undefined) {
        return return_pathfinding_path_array_reconstructed(_node_begin, _nearest_traversable_node);
    }

    return undefined;
}
function return_pathfinding_path_array_reconstructed(_node_begin, _node_end)  {
    var _node_current = _node_end;
    var _path_array = [];
    while (_node_current != _node_begin) {
        array_insert(_path_array, 0, {
            x: (_node_current.x * pathfinding_grid_cell_size) + (pathfinding_grid_cell_size / 2),
            y: (_node_current.y * pathfinding_grid_cell_size) + (pathfinding_grid_cell_size / 2),
        });

        _node_current = _node_current.parent;
    }
    return _path_array;
}
function return_pathfinding_path(_begin_x, _begin_y, _end_x, _end_y)    {
    var _begin_coordinates = return_pathfinding_cell_coordinate(_begin_x, _begin_y);
    var _end_coordinates = return_pathfinding_cell_coordinate(_end_x, _end_y);

    if not return_pathfinding_coordinate_valid(_begin_coordinates.x, _begin_coordinates.y) {
        return undefined;
    }
    if not return_pathfinding_coordinate_valid(_end_coordinates.x, _end_coordinates.y) {
        return undefined;
    }

    var _node_begin = return_pathfinding_node(_begin_coordinates.x, _begin_coordinates.y);
    var _node_end = return_pathfinding_node(_end_coordinates.x, _end_coordinates.y);
    var _node_path = return_pathfinding_result(_node_begin, _node_end);

    if is_undefined(_node_path) or array_length(_node_path) == 0 {
        return undefined;
    }

    array_push(_node_path, {
        x: _end_x,
        y: _end_y
    });

    return _node_path;
}
function return_pathfinding_cell_coordinate(_room_pos_x, _room_pos_y) {
    var _cell_x = floor(_room_pos_x / pathfinding_grid_cell_size);
    var _cell_y = floor(_room_pos_y / pathfinding_grid_cell_size);
    return { x: _cell_x, y: _cell_y };
}
function return_pathfinding_node(_cell_x, _cell_y)  {
    if not return_pathfinding_coordinate_valid(_cell_x, _cell_y) {
        return undefined;
    }
    return enemy_pathfinding_grid[_cell_x][_cell_y];
}
function return_pathfinding_node_nearest_traversable(_start_x, _start_y)    {
    var _node_array = [{
        x: _start_x,
        y: _start_y
    }];
    var _nodes_visited = [];

    array_push(_nodes_visited, {
        x: _start_x,
        y: _start_y
    });
}
function return_actor_position_valid(_pos_x, _pos_y)    {
    var _cell_coordinates = return_pathfinding_cell_coordinate(_pos_x, _pos_y);
    if not return_pathfinding_coordinate_valid(_cell_coordinates.x, _cell_coordinates.y) {
        return false;
    }
    var _node = return_pathfinding_node(_cell_coordinates.x, _cell_coordinates.y);
    switch (_node.type) {
        case E_ENEMY_PATHFINDING_TILE_TYPES.WALL:
            return false;
    }
    return true;
}
function return_pathfinding_heuristic(_node_current, _node_target) {
    if PATHFINDING_GRID_CELL_DIAGONAL_ENABLED {
        var _direction_x = abs(_node_current.x - _node_target.x);
        var _direction_y = abs(_node_current.y - _node_target.y);
        return sqrt((_direction_x * _direction_x) + (_direction_y * _direction_y));
    }
    var _distance_x = abs(_node_current.x - _node_target.x);
    var _distance_y = abs(_node_current.y - _node_target.y);
    return _distance_x + _distance_y;
}

function draw_debug_grid()  {
    if not pathfinding_debug return;
    draw_set_halign(fa_center);
    draw_set_valign(fa_middle);
    draw_set_font(global.font_main);
    for (var _grid_x = 0; _grid_x < enemy_pathfinding_grid_width; _grid_x ++) {
        for (var _grid_y = 0; _grid_y < enemy_pathfinding_grid_height; _grid_y ++) {
            var _node = enemy_pathfinding_grid[_grid_x][_grid_y];
            var _node_x = _node.x * pathfinding_grid_cell_size;
            var _node_y = _node.y * pathfinding_grid_cell_size;

            switch (_node.type) {
                case E_ENEMY_PATHFINDING_TILE_TYPES.EMPTY:
                    draw_set_color(c_white);
                    break;

                case E_ENEMY_PATHFINDING_TILE_TYPES.DOOR_OPEN:
                    draw_set_color(c_aqua);
                    break;

                case E_ENEMY_PATHFINDING_TILE_TYPES.DOOR_CLOSED:
                    draw_set_color(c_navy);
                    break;

                case E_ENEMY_PATHFINDING_TILE_TYPES.WINDOW_OPEN:
                    draw_set_color(c_lime);
                    break;

                case E_ENEMY_PATHFINDING_TILE_TYPES.WINDOW_CLOSED:
                    draw_set_color(c_yellow);
                    break;

                case E_ENEMY_PATHFINDING_TILE_TYPES.WALL:
                    draw_set_color(c_red);
                    break;
            }

            draw_set_alpha(0.1);
            draw_rectangle(_node_x, _node_y, _node_x + pathfinding_grid_cell_size, _node_y + pathfinding_grid_cell_size, false);
            draw_set_colour(c_white);
            draw_set_alpha(0.6);
            var _text = string(floor(_node.cost_total));
            draw_text_transformed(_node_x + (pathfinding_grid_cell_size / 2), _node_y + (pathfinding_grid_cell_size / 2), _text, 0.4, 0.4, 0);
        }
    }
    draw_set_alpha(1.0);
}

init_pathfinding();