   A* possible bug in my implementation?
  Hi,I'm a little lost at the moment (can't seem to wrap my head around it) so I thought I'd try here. I have created an ActionScript3 implementation of A* and I'm wondering if I could have a little bug in my implementation. I can't think of a situation where it might go wrong, but maybe you guys can.So, here's a little fragment of my code://loop over all the neighbours of the current nodewhile(i-- > [[0]]){//cN is the current neighbor that is being examinedcN = neighbours as DataTile;//makes sure that cN.getCost() is multiplied by [[[1]]].[[[4]]] if this path is diagonalcN.setDiag(_map.isDiagonal(current.getPosition(), cN.getPosition()));if(!cN.getOpen()){//add to open-arrayopenTile(cN, cN.getPosition(), current.getG(), this._end, current);}else{//already in open, check if F via current node is lowernewF = cN.calculateUpdateF(current.getG()); if(newF < cN.getF()){pos = this._heap.getPosition(cN);cN.setParent(current);cN.setG(current.getG());this._heap.update_heap(pos);}}}I think the code is pretty self explanatory, but if it's not, just let me know.Now, the actual question: I think that 'cN.setDiag()' shouldn't be there. setDiag() makes sure that getCost() is multiplied by 1.4 if you access it diagonally. I think that the multiplier should only be used in calculateUpdateF (since you might want to access the tile diagonally) and right before/after calling setParent()getCost() is used in calculateUpdateF() and is of course used in the getF() that's used by my binary heap to get the next best option.If I'm asking for too much or my code isn't clear enough or anything else, just let me know.Thanks!   
  i dont know if this helps, but when i implemented this in C++ i had methods to calculate F, G and H which were defined when the open list object was instantiated and never changed afterwards. Instead of a setdiag, i had a Cost() function which returned 10 for non-diagonal squares and 14 for diagnonal squares, given the x and y position of the centre square and the x and y position of the square being checked (this can simply be represented as abs(x1-x2) == 1 && abs(y1-y2) == 1)This is the part of my code that adds the eight neigbours, similar to your own code snippet: /* Add all eight adjacent squares to the OPEN list */ for (int x = Curr->x - 1; x < Curr->x + 2; ++x) {    for (int y = Curr->y - 1; y < Curr->y + 2; ++y)    {  if (x == Curr->x && y == Curr->y)continue;  /* Ignore unwalkable squares */  if (!IsUnwalkable(unwalkable, Point(x, y), Start))  {/* Find out if this square is already on the OPEN list */std::map<int, Location*>::iterator item = List.find(LHASH(x, y));Location* newloc = NULL;/* If it is, we need to find out which is better, our new version, or the old version */if (item != List.end()){   /* Replace it, if our G-score is better than the old one */   if (item->second->Open())   { if (item->second->GetG() > Curr->GetG() + (Cost(Curr->x, Curr->y, x, y))) {    delete item->second;    newloc = new Location(x, y, Curr); } else    /* Keep it if the old square is better scored */    continue;   }   else /* Item exists, but is in the closed list, we don't mess with it */ continue;}else{   /* Item is in neither open or closed list, add it to the OPEN list */   newloc = new Location(x, y, Curr);}/* For the new item we added (if we added one) set te G score and the H score. * As above, G score is the cost to get to this square from the starting position, * and the H score is the cost to get to this square from the END location ignoring * unwalkables and travelling only horizontally and vertically. */newloc->SetG(Curr->GetG() + (Cost(Curr->x, Curr->y, x, y)));newloc->SetH(End);List[LHASH(x, y)] = newloc;  }    } }Hope this helps!   ;  Thanks for your input!For your implementation to work, you would have to create a new tile object if a better path to an already open tile is found, right? (It seems like that way in your code too). This would confirm my that the f() (and the cost()) of the new tile should only change when a better path has been found, which would suggest that my implementation is 'wrong'.So I now know how it should be programmed, but I'm wondering if my current implementation can actually generate false results ...   ;  Hi DauntlessCrowd,yes you should only change the tile's values if the F score is less than the score of the tile it is to replace and is not on the closed list.I used the following tutorial to produce my algorithm which i found very useful: http://www.policyalmanac.org/games/aStarTutorial.htm   