Help with my A* implementation T_T

Discussion in 'Developer Support' started by Geno, Dec 20, 2014.

  1. Geno

    Joined:
    Dec 15, 2014
    Messages:
    9
    Likes Received:
    1
    Hello, my A* implementation have been giving me a headache for the past hours and am now turning here for help.

    Here are 2 snippets of my code, 1 snippet is the part of my code that searches through the nodes and do the open/closed list operations and the second snippet is the part that constructs the path by going from parent to parent till it finds the start node. However, for some reason, when the construct path method gets called it's stuck in an infinite loop and I can't figure out why or if something is wrong with snippet 1.

    Snippet 1:

    Code (Text):
    1. private ArrayList<WebNode> findPath(Tile destination)
    2. {
    3. ArrayList<WebNode> openList = new ArrayList<WebNode>();
    4. ArrayList<WebNode> closedList = new ArrayList<WebNode>();
    5. WebNode startNode = closestReachableNodeOnMap();
    6. WebNode destinationNode = closestNodeToDestination(destination);
    7. System.out.println("Start Node: " + startNode.tile.toString());
    8. System.out.println("Destination Node: " + destinationNode.tile.toString());
    9. openList.add(startNode);
    10.  
    11. WebNode currentNode;
    12. int iterations = 0;
    13. while(!openList.isEmpty()) // Loop till we have a path :){
    14. iterations++;
    15. if(iterations > 100000) break;
    16. currentNode = findCurrentNode(openList);
    17. if(currentNode == destinationNode) return constructPath(currentNode, startNode); // We have our path constructed.openList.remove(currentNode);
    18. closedList.add(currentNode);
    19. for(WebNode edge : currentNode.edges)
    20. {
    21. edge.setParent(currentNode);
    22. updateCostForNode(edge, destinationNode.tile);
    23. }
    24.  
    25. for(WebNode edge : currentNode.edges)
    26. {
    27. if(edge == destinationNode) return constructPath(edge, startNode);
    28. // Optimization: Use boolean flag instead of 2 lists later. // If there is a node with the same parent in open or closed list but with lower f, skip.updateCostForNode(edge, destinationNode.tile);
    29. boolean betterAvailable = false;
    30. for(WebNode node : openList)
    31. {
    32. if(node.getParent() == edge.getParent())
    33. {
    34. if(node.f < edge.f)
    35. {
    36. betterAvailable = true;
    37. }
    38. }
    39. }
    40. for(WebNode node : closedList)
    41. {
    42. if(node.getParent() == edge.getParent())
    43. {
    44. if(node.f < edge.f)
    45. {
    46. betterAvailable = true;
    47. }
    48. }
    49. }
    50. // Else add to open listif(!betterAvailable)
    51. {
    52.  
    53. openList.add(edge);
    54. }
    55. }
    56. }
    57. System.out.println("Failed to find path :(");
    58. return null; // Failure}
    Snippet 2:
    Code (Text):
    1.  
    2. private ArrayList<WebNode> constructPath(WebNode endNode, WebNode startNode)
    3. {
    4. System.out.println("Path is possible :)");
    5. ArrayList<WebNode> path = new ArrayList<WebNode>();
    6. WebNode currentNode = endNode;
    7. while(!currentNode.equals(startNode))
    8. {
    9. path.add(currentNode);
    10. currentNode = currentNode.getParent();
    11. }
    12. path.add(startNode);
    13. // Path is in reverse order.Collections.reverse(path);
    14. // Return the constructed path :)return path;
    15. }
    Thanks for help / suggestions :)
     
  2. frazboyz

    Joined:
    Nov 15, 2013
    Messages:
    337
    Likes Received:
    55
    Why are you using Tiles? Did you find this on the web?
     
  3. Geno

    Joined:
    Dec 15, 2014
    Messages:
    9
    Likes Received:
    1
    No, read some research papers. I use tile position for the heurestic and more.
     
  4. frazboyz

    Joined:
    Nov 15, 2013
    Messages:
    337
    Likes Received:
    55
    Hm Sketchy, well i would recomend not starting with A* try write a path finding algorithm using BFS or Djkstras, both are easier.
     
  5. Geno

    Joined:
    Dec 15, 2014
    Messages:
    9
    Likes Received:
    1
    Why is it sketchy to use the manhattan distance between 2 tiles to evaluate the cost of g and h?
    I believe the search works since it calls the construct path which then leads to an infinite loop. I think I do something wrong when I set a nodes parent, which is an error Id do same with both algorithms you suggested since its not the heuristic im having problems with.
     
  6. Arbiter

    Arbiter Mod Automation

    Joined:
    Jul 26, 2013
    Messages:
    2,544
    Likes Received:
    1,061
    On a sidenote, I would recommend joining our Skype development chat. We love discussing stuff like this in detail. PM me if you're interested. :)
     
  7. Geno

    Joined:
    Dec 15, 2014
    Messages:
    9
    Likes Received:
    1
    Managed to fix the problem, a node would reset all the edges parents even if they already have one, resulting in a node having a parent that had their Child as the parent -> infinite loop.
    simply changed
    edge.setParent(currentNode);
    To:
    if(edge.getParent() == null) edge.setParent(currentNode);
     

Share This Page

Loading...