A* Trouble

Okay So I started programming a pathfinding algo in Java. It doesn’t seem to work, I can’t figure out why… Can anyone offer a better way to do it or a fix to this?


public ArrayList<Node> getPath (Node start, Node end) throws Exception
    {
        int height = Node.MAP[0].length;
        int width = Node.MAP.length;

        ArrayList<Node> path = new ArrayList ();
        Node[] neighbours = new Node[0];

        int steps = 0;
        Node[][] map = getNodes (height, width);

        int endX = end.getX ();
        int endY = end.getY ();

        map[endX][endY].distance = 0;

        while (true)
        {
            boolean madeProgress = false;

            for (Node mainPoint : getAllNodes (height, width))
            {

                if (mainPoint.isValidMove ())
                {
                    int passHere = mainPoint.distance;

                    for (Node movePoint : getValidMoves (mainPoint))
                    {
                        int newPass = passHere + 1;
                        
                        int x = movePoint.getX ();
                        int y = movePoint.getY ();
                        
                        if (map[movePoint.getX ()][movePoint.getY ()].distance > newPass)
                        {
                            map[movePoint.getX ()][movePoint.getY ()].distance = newPass;
                            madeProgress = true;
                        }
                    }
                }
            }
            if (!madeProgress)
            {
                break;
            }
        }

        int pointX = start.getX ();
        int pointY = start.getY ();

        while (true)
        {
            Node lowestNode = null;
            int lowest = 10000;

            for (Node movePoint : getValidMoves (map[pointX][pointY]))
            {
                int count = map[movePoint.getX ()][movePoint.getY ()].distance;
                if (count < lowest)
                {
                    lowest = count;
                    lowestNode = movePoint;
                }
            }
            if (lowest != 10000)
            {
                map[lowestNode.getX ()][ lowestNode.getY ()].isPath = true;
                pointX = lowestNode.getX ();
                pointY = lowestNode.getY ();
            } else
            {
                break;
            }

            if (map[pointX][pointY].equals (end))
            {
                break;
            }
        }
        
        for (int x = 0; x < width; x++)
        {
            for (int y = 0; y < height; y++)
            {
                if (map[x][y].isPath)
                    path.add (map[x][y]);
            }
        
        }
        return path;

    }

Can you narrow down the problem? “It doesn’t seem to work” can mean “it results nothing/wrong” or “nothing happen”. It can help other member to save time.

for first, your use of while(true) is kinda dangerous. the while(true)'s lifetime depends on those two break lines. make sure the while(true) can break and go to return line. second, you have 0 as array’s length value for neighbours.

It runs the method rather quickly, It just doesn’t find the path (as in… The ArrayList it return has a “size” of zero). To test, I chose two nodes which were two indexes apart, nothing to block the path, just a simple straight line. I was going to test it with some more difficult paths, however, it is always empty.

I won’t try to understand your code but for an A* algorithm it looks a bit short…

Anyway, if you want fast working A* with simple interface : use my code! :slight_smile:

http://code.google.com/p/gudrasoft/downloads/list

You can refer to this post if you want explanation how to use it.

http://www.java-gaming.org/index.php/topic,23672.0.html

N.B. : The zip is the most current version. The speed difference between this version and the one in the thread is probably a factor of 100 to 1000.

Thanks, Looks good. I do have a problem with it, but I pm’d you :slight_smile:
Hopefully all will be well.