Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- function scr_find_path(cellStart, cellEnd, grid, pushStart = false, size = [1, 1]){
- var frontier = ds_priority_create()
- var cameFrom = ds_map_create()
- var costSoFar = ds_map_create()
- var maxX = ds_grid_width(grid)
- if is_array(cellStart) {
- cellStart = cellStart[0] + cellStart[1] * maxX;
- }
- if is_array(cellEnd) {
- cellEnd = cellEnd[0] + cellEnd[1] * maxX;
- }
- ds_priority_add(frontier, cellStart, 0)
- ds_map_add(cameFrom, cellStart, noone)
- ds_map_add(costSoFar, cellStart, 0)
- var current = noone;
- while !ds_priority_empty(frontier)
- {
- current = ds_priority_delete_min(frontier)
- if (current == cellEnd) break
- var vneighbors = scr_neighbors(current, grid,,size) // Получаем ID-соседей
- for (var i = 0; i < array_length(vneighbors); ++i)
- {
- var ncellX = vneighbors[i] mod maxX;
- var ncellY = vneighbors[i] div maxX;
- var newCost = ds_map_find_value(costSoFar, current) + ds_grid_get(grid, ncellX, ncellY)
- if is_undefined(ds_map_find_value(costSoFar, vneighbors[i]))
- or newCost < ds_map_find_value(costSoFar, vneighbors[i])
- {
- var priority = newCost + scr_heuristic(cellEnd, vneighbors[i], grid)
- ds_map_add(costSoFar, vneighbors[i], newCost)
- ds_priority_add(frontier, vneighbors[i], priority)
- ds_map_add(cameFrom, vneighbors[i], current)
- }
- }
- }
- if (current == cellEnd)
- {
- var path = [];
- while current != cellStart
- {
- array_push(path, current)
- current = ds_map_find_value(cameFrom, current)
- }
- if (pushStart) array_push(path, cellStart);
- ds_map_destroy(cameFrom);
- ds_map_destroy(costSoFar);
- ds_priority_destroy(frontier);
- path = scr_reverse_array(path);
- return path
- }
- else
- {
- ds_map_destroy(cameFrom)
- ds_map_destroy(costSoFar)
- ds_priority_destroy(frontier)
- return [];
- }
- }
- function scr_neighbors(start, grid, fourSides = false, size = [1, 1])
- {
- var cellx, celly, cells;
- var neighborsAr = [];
- var maxX = ds_grid_width(grid);
- if is_array(start) {
- cellx = start[0];
- celly = start[1];
- }
- else {
- cellx = start mod maxX;
- celly = start div maxX;
- }
- if (fourSides) cells = [[cellx-1, celly], [cellx, celly-1], [cellx+1, celly], [cellx, celly+1]]
- else cells = [[cellx -1, celly-1], [cellx, celly-1], [cellx+1, celly-1], [cellx-1, celly], [cellx+1, celly], [cellx-1, celly+1], [cellx, celly+1], [cellx+1, celly+1]]
- for (var i = 0; i < array_length(cells); ++i)
- {
- var push = true;
- for (var sy = 0; sy < size[1]; ++sy) {
- for (var sx = 0; sx < size[0]; ++sx) {
- if cells[i][0] + sx < 0 or cells[i][0] + sx >= room_width div CW
- or cells[i][1] + sy < 0 or cells[i][1] + sy >= room_height div CH
- or ds_grid_get(grid, cells[i][0] + sx, cells[i][1] + sy) == 0
- {
- push = false;
- break;
- }
- }
- if !(push) break;
- }
- if !(push) continue
- if (push) {
- array_push(neighborsAr, cells[i][0] + cells[i][1] * maxX)
- }
- }
- return neighborsAr
- }
- function scr_heuristic(a,b, grid)
- {
- var maxX = ds_grid_width(grid);
- var ax, ay, bx, by;
- if !is_array(a) {
- ax = a mod maxX;
- ay = a div maxX;
- }
- else {
- ax = a[0];
- ay = a[1];
- }
- if !(is_array(b)) {
- bx = b mod maxX;
- by = b div maxX;
- }
- else {
- bx = b[0];
- by = b[1];
- }
- return abs(ax - bx) + abs(ay - by)
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement