c++ - A* pathfinding not taking shortest path -
my a* pathfinding function gets intended destination, goes bit out of way. here's example:
[i made nice image show issue, apparently won't post until reputation reaches 10; sorry, i'm new. :p]
essentially, pulls left or as possible without adding more tiles path. sounds issue calculating gscore or possibly part tile's parent can reassigned based on neighboring tiles' gscores, can't figure out it's going wrong. i've combed on code weeks , browsed dozens of online posts, i'm still stuck. fyi, compiler/debugger have use doesn't support breakpoints or step-through debugging, i'm stuck simple text output. can spot i'm doing wrong?
here's primary function (note: in angelscript. it's based on c++, there small differences):
int cardinal_cost = 10; int diagonal_cost = 14; array<vector2> findpath(vector2 startposition, vector2 endposition) { //translate start , end positions grid coordinates startposition = _level.gettilegridposition(startposition); endposition = _level.gettilegridposition(endposition); //the path returned array<vector2> path(0); //create closed array<vector2> closedset(0); //create open set. these nodes considered. array<vector2> openset(0); //add startposition open set. openset.insertlast(startposition); //create camefrom (path) array. each entry hods tile's parent tile. array<array<vector2>> camefrom; camefrom = array<array<vector2>>(_level.width(), array<vector2>(_level.height())); //create gscore array. gscore cost start current tile. array<array<int>> gscore; gscore = array<array<int>>(_level.width(), array<int>(_level.height())); //set start position score 0 gscore[startposition.x][startposition.y] = 0; //create fscore array. fscore gscore + heuristic cost. array<array<int>> fscore; fscore = array<array<int>>(_level.width(), array<int>(_level.height())); //set start position score estimated (heuristic) cost. //gscore start 0, that's not included in equation. fscore[startposition.x][startposition.y] = getheuristiccost(startposition, endposition); //required variables bool searchcomplete = false; vector2 currenttile = startposition; int x = 0; int y = 0; string tiletype = ""; vector2 nexttile(0,0); vector2 neighbortile(0,0); int lowestscore = 0; int tempscore = 0; int index = 0; while(!searchcomplete) { //find tile in openset lowest fscore. lowestscore = fscore[openset[0].x][openset[0].y]; neighbortile = openset[0];//may not "neighbor" in case, looking lowest fscore. for(int = 0; < openset.length(); i++) { if(fscore[neighbortile.x][neighbortile.y] < lowestscore || == 0) { lowestscore = fscore[neighbortile.x][neighbortile.y]; nexttile.x = neighbortile.x; nexttile.y = neighbortile.y; } } //drop "nexttile" openset , add closedset index = openset.find(nexttile); openset.removeat(openset.find(nexttile)); closedset.insertlast(nexttile); //set currenttile currenttile = nexttile; //get fscore each neighboring tile for(x = currenttile.x - 1; x <= currenttile.x + 1; x++) { for(y = currenttile.y - 1; y <= currenttile.y + 1; y++) { //safety: make sure x , y aren't out of bounds if(x < 0) x = 0; else if(x > _level.width()) x = _level.width(); if(y < 0) y = 0; else if (y > _level.height()) y = _level.height(); //set x,y pair neighbortile neighbortile.x = x; neighbortile.y = y; //get tile type if(_level.tilearray()[neighbortile.x][neighbortile.y] != null) tiletype = _level.tilearray()[neighbortile.x][neighbortile.y].getstring("type"); else tiletype = ""; //make sure aren't looking @ current tile, tile not closed, , tile floor or door. if(neighbortile != currenttile && closedset.find(neighbortile) == -1 && (tiletype == "floor" || tiletype == "door")) { //if neighboring tile in open set, check see if currenttile's gscore less if tile parent. //if is, set currenttile's parent , reset fscore , gscore it. if(openset.find(neighbortile) != -1) { if(gscore[neighbortile.x][neighbortile.y] < gscore[camefrom[currenttile.x][currenttile.y].x][camefrom[currenttile.x][currenttile.y].y]) { camefrom[currenttile.x][currenttile.y] = neighbortile; //if tile diagonal move if(neighbortile.x - currenttile.x != 0 && neighbortile.y - currenttile.y != 0) gscore[currenttile.x][currenttile.y] = gscore[neighbortile.x][neighbortile.y] + diagonal_cost; else//if tile cardinal (n,s,e,w) move gscore[currenttile.x][currenttile.y] = gscore[neighbortile.x][neighbortile.y] + cardinal_cost; fscore[currenttile.x][currenttile.y] = gscore[currenttile.x][currenttile.y] + getheuristiccost(currenttile, endposition); } } else//add tile open set { openset.insertlast(neighbortile); //record tile's parent camefrom[neighbortile.x][neighbortile.y] = currenttile; //if tile diagonal move if(neighbortile.x - currenttile.x != 0 && neighbortile.y - currenttile.y != 0) gscore[neighbortile.x][neighbortile.y] = gscore[currenttile.x][currenttile.y] + diagonal_cost; else//if tile cardinal (n,s,e,w) move gscore[neighbortile.x][neighbortile.y] = gscore[currenttile.x][currenttile.y] + cardinal_cost; //get fscore tile fscore[neighbortile.x][neighbortile.y] = gscore[neighbortile.x][neighbortile.y] + getheuristiccost(neighbortile, endposition); } } } } //check see if have arrived @ endtile if(currenttile == endposition) { searchcomplete = true; path = reconstructpath(camefrom, startposition, endposition); } else { //check see if openset empty if(openset.length() == 0) searchcomplete = true; } }//while(!searchcomplete) return path; } my heuristic uses manhattan method:
int getheuristiccost(vector2 startposition, vector2 endposition) { //using manhattan method: int x = abs(startposition.x - endposition.x)*10; int y = abs(startposition.y - endposition.y)*10; return x+y; } and finally, here's path reconstructing function:
array<vector2> reconstructpath(array<array<vector2>> &in camefrom, vector2 &in startposition, vector2 &in endposition) { //start adding in end position array<vector2> totalpath(1); vector2 currenttile = endposition; totalpath[0] = endposition; int x = endposition.x; int y = endposition.y; int angle = 0; while(vector2(x, y) != startposition) { currenttile = camefrom[x][y]; totalpath.insertat(0,currenttile); x = currenttile.x; y = currenttile.y; } return totalpath; }
for(int = 0; < openset.length(); i++) { if(fscore[neighbortile.x][neighbortile.y] < lowestscore || == 0) { lowestscore = fscore[neighbortile.x][neighbortile.y]; nexttile.x = neighbortile.x; nexttile.y = neighbortile.y; } } this loop looks @ neighbortile on , over. did mean go on elements of openset?
Comments
Post a Comment