A_Star

function heuristic(a,b)
{
    // a, b - массивы, которые хранят x и y выбранных клеток
    a = global.grid_array[a]
    b = global.grid_array[b]
    return abs(a[0] - b[0]) + abs(a[1] - b[1])
}

function find_path(cell_start, cell_end)
{
    var frontier = ds_priority_create()
    var came_from = ds_map_create()
    var cost_so_far = ds_map_create()

    var cell_x = global.grid_array[cell_end][0]
    var cell_y = global.grid_array[cell_end][1]
    var need_neighbors = ds_grid_get(global.grid, cell_x, cell_y) == 0

    if need_neighbors
    {
        var end_neighbors = neighbors(cell_end)
    }
    var btb = false

    ds_priority_add(frontier, cell_start, 0)
    ds_map_add(came_from, cell_start, noone)
    ds_map_add(cost_so_far, cell_start, 0)

    while !ds_priority_empty(frontier)
    {
        current = ds_priority_delete_min(frontier)

        if need_neighbors
        {
            var close = scrFindInArray(end_neighbors, current)
        }
        // Если клетка, которую мы хотим достичь, непроходима и мы являемся соседом с ней
        // То выходим из цикла - путь найден
        if current == cell_end
        or need_neighbors
        and close != noone
        {
            btb = true
            break
        }

        vneighbors = neighbors(current)
        for (var i = 0; i < array_length(vneighbors); ++i)
        {
            new_cost = ds_map_find_value(cost_so_far, current) + ds_grid_get(global.grid, global.grid_array[vneighbors[i]][0], global.grid_array[vneighbors[i]][1])
            if is_undefined(ds_map_find_value(cost_so_far, vneighbors[i]))
            or new_cost < ds_map_find_value(cost_so_far, vneighbors[i])
            {
                priority = new_cost + heuristic(cell_end, vneighbors[i])
                ds_map_add(cost_so_far, vneighbors[i], new_cost)
                ds_priority_add(frontier, vneighbors[i], priority)
                ds_map_add(came_from, vneighbors[i], current)
            }
        }
    }

    // Если путь найден
    if current == cell_end
    or btb
    {
        var path = []
        while current != cell_start
        {
            array_push(path, current)
            current = ds_map_find_value(came_from, current)
        }
        array_push(path, cell_start)
        ds_map_destroy(came_from)
        ds_map_destroy(cost_so_far)
        ds_priority_destroy(frontier)
        return path
    }
    else
    {
        // Пути нет - возвращаем noone
        ds_map_destroy(came_from)
        ds_map_destroy(cost_so_far)
        ds_priority_destroy(frontier)
        return noone
    }
}