c# - Astar algorithm goes in endless loop -
i working on a* search algorithm , followed this: a* search algorithm
using system; using system.collections.generic; using system.linq; using system.text; using system.threading.tasks; using mapdata.interfaces; namespace mapdata.algorithm { public class astar { idmap map; list<location2d> openset; list<location2d> closedset; list<location2d> path; dictionary<location2d, double> g_scores; dictionary<location2d, double> h_scores; dictionary<location2d, double> f_scores; dictionary<location2d, location2d> came_from; int[] arrayx = { 0, -1, -1, -1, 0, 1, 1, 1 }; int[] arrayy = { 1, 1, 0, -1, -1, -1, 0, 1 }; /// <summary> /// initing algorithm mapinfo /// </summary> /// <param name="map">dmap info.</param> public astar(idmap map) { this.map = map; } /// <summary> /// start searching untile it's find it's goal or return false. /// </summary> /// <param name="start">starting node.</param> /// <param name="goal">ending node.</param> public bool find( location2d start, location2d goal) { openset = new list<location2d>(); // set of tentative nodes evaluated, containing start node. closedset = new list<location2d>(); // set of nodes evaluated. path = new list<location2d>(); // path result. g_scores = new dictionary<location2d, double>(); // cost start along best known path. h_scores = new dictionary<location2d, double>(); // estimated cost node goal. f_scores = new dictionary<location2d, double>(); // estimated total cost start goal. came_from = new dictionary<location2d, location2d>(); // navigated nodes. openset.add(start); g_scores[start] = 0; h_scores[start] = gethvalue(start, goal); f_scores[start] = g_scores[start] + h_scores[start]; while (openset.count > 0) { // while openset not empty location2d current = checkbestnode(); //the node in openset having lowest f_score[] value if (current.equals(goal)) { reconstructpathrecursive(current); return true; } location2d neighbor = new location2d(); (int = 0; < 8; i++) { // neighbor nodes. neighbor.x = (ushort)(current.x + arrayx[i]); neighbor.y = (ushort)(current.y + arrayy[i]); bool tentative_is_better = false; if (closedset.contains(neighbor)) continue; if (!map.cells[neighbor.x, neighbor.y].walkable) continue; double tentative_g_score = g_scores[current] + distancebetween(current, neighbor); if (!openset.contains(neighbor)) { openset.add(neighbor); h_scores[neighbor] = gethvalue(neighbor, goal); tentative_is_better = true; } else if (tentative_g_score < g_scores[neighbor]) { tentative_is_better = true; } else { tentative_is_better = false; } if (tentative_is_better) { if (came_from.containskey(neighbor)) { came_from[neighbor] = current; } else { came_from[neighbor] = current; g_scores[neighbor] = tentative_g_score; f_scores[neighbor] = g_scores[neighbor] + h_scores[neighbor]; } } } } return false; } /// <summary> /// check best node has smallest f value; /// </summary> /// <returns>the best node.</returns> location2d checkbestnode() { var bestnode = f_scores.orderby(x => x.value).first().key; f_scores.remove(bestnode); openset.remove(bestnode); closedset.add(bestnode); return bestnode; } private void reconstructpathrecursive(location2d current_node) { location2d temp; if (came_from.trygetvalue(current_node, out temp)) { reconstructpathrecursive(temp); path.add(temp); } else { path.add(current_node); } } int gethvalue(location2d start, location2d goal) { int ndx = math.abs(start.x - goal.x); int ndy = math.abs(start.y - goal.y); if (ndx > ndy) return 10 * ndx + 6 * ndy; return 10 * ndy + 6 * ndx; } readonly double sqrt_2 = math.sqrt(2); protected double distancebetween(location2d instart, location2d inend) { int diffx = math.abs(instart.x - inend.x); int diffy = math.abs(instart.y - inend.y); switch (diffx + diffy) { case 1: return 1; case 2: return sqrt_2; case 0: return 0; default: throw new applicationexception(); } } public list<location2d> path { { return path; } } } } now have 2 issues:
if made check on walkable areas astar goes in endless loop , never finds path nor break.
if commented part checking walkable areas finds path not accurate, if goal location -> (444,444), path ends @ -> (444,443) or (443,444).
i can't see doing wrong here since followed wikipedia guide.
now, correct me if i'm wrong, seems like, looking @ other code, want if statements in loop iterates on current node's neighbors this:
if (!closedset.contains(neighbor)) continue; if (map.cells[neighbor.x, neighbor.y].walkable) continue; not this:
if (closedset.contains(neighbor)) continue; if (!map.cells[neighbor.x, neighbor.y].walkable) continue; your original code evaluates neighbor if it's on closed list , it's not walkable, don't believe want. updated code evaluates neighboring node if it's not on closed set , walkable.
for further understanding of a* algorithm , detailed description of how works, check out this link.
edit: said code provided inaccurate path, is, path doesn't lead way target square. looking @ reconstructpathrecursive() function, seems you've made crucial mistake. because list contains parent of every node traversed, you'll wind target square, because isn't parent of anything. target square should first square added list before begin working backwards reconstructing path parent of current node (which target square).
to fix behavior, suggest when find current node equals target node, add target node path list first, , after that's done, call reconstructpathrecursive() function final list.
Comments
Post a Comment