Kezarus
Endless Game Maker
Hi! I'm making a pathfind code and I'm wondering if there is anything that I could do to reduce the impact of it.
I am already using some shenanigans to reduce it. Those are:
Here is my full code:
I am already using some shenanigans to reduce it. Those are:
- Manhattan heuristics
- Max distance allowance
- Lookup lists
Here is my full code:
GML:
//THE CLASS
function Pathpoint(_cellX, _cellY, _score, _heuristic, _cameFrom) constructor{
cellX = _cellX;
cellY = _cellY;
Score = _score;
Heuristic = _heuristic;
CameFrom = _cameFrom; //an array of Pathpoints
static Value = function(){
return Score+Heuristic;
}
}
GML:
//https://en.wikipedia.org/wiki/A*_search_algorithm
function Pathfind(iniX, iniY, endX, endY){
var mapWidth = ds_grid_width(global.grdBiome);
var mapHeight = ds_grid_height(global.grdBiome);
//CHANGE COORD TO CELL
iniX = clamp(iniX div CELL_SIZE, 0, mapWidth-1);
iniY = clamp(iniY div CELL_SIZE, 0, mapHeight-1);
endX = clamp(endX div CELL_SIZE, 0, mapWidth-1);
endY = clamp(endY div CELL_SIZE, 0, mapHeight-1);
//MAX DISTANCE
var maxDist = 25;
if( point_distance(iniX, iniY, endX, endY) > maxDist ){
var dir = point_direction(iniX, iniY, endX, endY);
endX = floor(iniX + lengthdir_x(maxDist, dir));
endY = floor(iniY + lengthdir_y(maxDist, dir));
}
//PREPARING VARIABLES
var result = [];
var iterations = 0;
var lstOpen = ds_list_create();
var lstOpenLookup = ds_list_create();
var lstCloseLookup = ds_list_create();
var wScore = 1;
var wHeuristic = 0;
var wCameFrom = [];
//FIRST NODE
ds_list_add(lstOpen, new Pathpoint(iniX, iniY, wScore, wHeuristic, []));
ds_list_add(lstOpenLookup, string(iniX) + "*" + string(iniY));
//REAL PATHFINDING
var pointNow, posX, posY, point, arr, lookup;
while( !ds_list_empty(lstOpen) ){
iterations++;
//FIND SMALLEST SCORE IN OPEN LIST
var lesserScore = 1000000, lesserIndex=0;
var lstSize = ds_list_size(lstOpen);
for(var i=0; i<lstSize; i++){
point = lstOpen[| i];
if( point.Value() < lesserScore ){
lesserScore = point.Value();
lesserIndex = i;
}
}
pointNow = lstOpen[| lesserIndex];
posX = pointNow.cellX; //THIS IS THE CURRENT NODE X
posY = pointNow.cellY; //THIS IS THE CURRENT NODE Y
//CHECK IF ARRIVED
if( posX == endX && posY == endY ){
//THEN CONSTRUCT THE RETURN
//ADD THE CURRENT POINT
array_push(pointNow.CameFrom, [posX, posY]);
//INVERT THE ARRAY
for(i=array_length(pointNow.CameFrom)-1; i>0; i--){ //DISCARD THE FIRST POINT
array_push(result, pointNow.CameFrom[i]);
}
break; //BREAK THE LOOP
}else{
//REMOVE FROM OPEN LIST
ds_list_delete(lstOpen, lesserIndex);
ds_list_delete(lstOpenLookup, lesserIndex);
//ADD TO CLOSE LIST
lookup = string(posX) + "*" + string(posY);
ds_list_add(lstCloseLookup, lookup);
//ADD NEIGHBORS
var Neighbors;
Neighbors[0] = [posX+1, posY+0];
Neighbors[1] = [posX-1, posY+0];
Neighbors[2] = [posX+0, posY+1];
Neighbors[3] = [posX+0, posY-1];
var wx, wy, pointNeighbor;
for( var i=0; i<array_length(Neighbors); i++ ){
//VERIFY BOUNDARIES
arr = Neighbors[i];
wx = arr[0];
wy = arr[1];
if( wx < 0 ){ continue; }
if( wy < 0 ){ continue; }
if( wx >= mapWidth ){ continue; }
if( wy >= mapHeight ){ continue; }
//DON'T ADD IF ALREADY IN CLOSE LIST
lookup = string(wx) + "*" + string(wy);
if( ds_list_find_index(lstCloseLookup, lookup) != -1 ){
continue;
}
//CALCULATE SCORE AND HEURISTIC
wScore = pointNow.Score + PathfindGetScore(wx, wy);
wHeuristic = PathfindGetHeuristic(wx, wy, endX, endY);
//DUPLICATE AND PATH TO HERE AND ADD POINT
wCameFrom = array_duplicate(pointNow.CameFrom);
array_push(wCameFrom, [pointNow.cellX, pointNow.cellY]);
//CREATE PATH POINT
pointNeighbor = new Pathpoint(wx, wy, wScore, wHeuristic, wCameFrom);
//IF NOT IN OPEN LIST
var indexInOpen = PathfindSearchPointIndex(lstOpenLookup, pointNeighbor);
if( indexInOpen == -1 ){
//ADD TO OPEN
ds_list_add(lstOpen, pointNeighbor);
ds_list_add(lstOpenLookup, string(wx) + "*" + string(wy));
}else{
//FIND THE OPEN SCORE
var pointInOpen = lstOpen[| indexInOpen];
//IS THIS PATH SHORTER?
if( pointInOpen.Value() > pointNeighbor.Value() ){
//SUBSTITUTE
lstOpen[| indexInOpen] = pointNeighbor;
}
}
} //END OF FOR NEIGHBORS
} //END OF IF ARRIVED
} //END OF WHILE
ds_list_destroy(lstOpen);
ds_list_destroy(lstOpenLookup);
ds_list_destroy(lstCloseLookup);
//alert("iterations", iterations);
return result;
}
GML:
function PathfindGetScore(wx, wy){
switch( global.grdBiome[# wx, wy] ){
case MapGenBiomesEnum.Void: return 1; break;
case MapGenBiomesEnum.Ocean: return 5; break;
case MapGenBiomesEnum.River: return 4; break;
case MapGenBiomesEnum.Grass:
case MapGenBiomesEnum.Desert: return 1; break;
case MapGenBiomesEnum.ForestBoreal:
case MapGenBiomesEnum.ForestTemperate:
case MapGenBiomesEnum.ForestTropical: return 2; break;
case MapGenBiomesEnum.Alpine:
case MapGenBiomesEnum.Mountain:
case MapGenBiomesEnum.Mesa: return 3; break;
default: return 1;
}
}
GML:
//http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html#manhattan-distance
function PathfindGetHeuristic(nowX, nowY, endX, endY){
var deltaX = abs(nowX - endX);
var deltaY = abs(nowY - endY);
var factor = 1.75;
return factor*(deltaX+deltaY);
}
GML:
function PathfindSearchPointIndex(list, point){
return ds_list_find_index(list, string(point.cellX)+"*"+string(point.cellY));
}
GML:
function array_duplicate(arraySource){
var len = array_length(arraySource);
var arrayDest = [];
array_copy(arrayDest, 0, arraySource, 0, len);
return arrayDest;
}