A* Trouble - Java-Gaming.org

Cypherix

Senior Newbie

A* Trouble

« Posted 2011-09-11 19:45:31 »

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?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

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;

    }

ReBirth

JGO Wizard

Medals: 66
Projects: 4

Re: A* Trouble

« Reply #1 - Posted 2011-09-12 05:33:59 »

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.

Personal Site || MAGNET (Android, Free, No ads)

Cypherix

Senior Newbie

Re: A* Trouble

« Reply #2 - Posted 2011-09-12 06:25:47 »

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.

Games published by our own members! Check 'em out!

Try the Free Demo of Revenge of the Titans

Gudradain

JGO Coder

Medals: 6
Projects: 1

Re: A* Trouble

« Reply #3 - Posted 2011-09-12 07:24:38 »

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!

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/topics/astar-pathfinding/23672/view.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.

Cypherix

Senior Newbie

Re: A* Trouble

« Reply #4 - Posted 2011-09-12 08:29:29 »

Thanks, Looks good. I do have a problem with it, but I pm'd you

Hopefully all will be well.

Cypherix

Senior Newbie

Re: A* Trouble

« Reply #5 - Posted 2011-09-13 05:01:47 »

Quote from: Cypherix on 2011-09-12 08:20:24

After adding your code and running it, the following exception was thrown:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

Exception in thread "AWT-EventQueue-0" java.lang.ArrayIndexOutOfBoundsException: -1
   at java.util.ArrayList.get(ArrayList.java:324)
   at citystates.astar.grid.util.GridDouble.get(GridDouble.java:36)
   at citystates.astar.grid.astar.GridAstar.createLocation(GridAstar.java:229)
   at citystates.astar.grid.astar.GridAstar.findNextLocation(GridAstar.java:210)
   at citystates.astar.grid.astar.GridAstar.traceBackThePath(GridAstar.java:126)
   at citystates.astar.grid.astar.GridAstar.getPath(GridAstar.java:80)
   at citystates.astar.grid.GridPathfinding.getPath(GridPathfinding.java:31)
   at citystates.astar.PathFinder.getPath(PathFinder.java:54)
   at citystates.astar.Test.<init>(Test.java:38)
   at citystates.ui.LoginPanel.jButton1ActionPerformed(LoginPanel.java:138)
   at citystates.ui.LoginPanel.access$000(LoginPanel.java:18)
   at citystates.ui.LoginPanel$1.actionPerformed(LoginPanel.java:100)
   at javax.swing.AbstractButton.fireActionPerformed(AbstractButton.java:1995)
   at javax.swing.AbstractButton$Handler.actionPerformed(AbstractButton.java:2318)
   at javax.swing.DefaultButtonModel.fireActionPerformed(DefaultButtonModel.java:387)
   at javax.swing.DefaultButtonModel.setPressed(DefaultButtonModel.java:242)
   at javax.swing.plaf.basic.BasicButtonListener.mouseReleased(BasicButtonListener.java:236)
   at java.awt.Component.processMouseEvent(Component.java:6288)
   at javax.swing.JComponent.processMouseEvent(JComponent.java:3267)
   at java.awt.Component.processEvent(Component.java:6053)
   at java.awt.Container.processEvent(Container.java:2041)
   at java.awt.Component.dispatchEventImpl(Component.java:4651)
   at java.awt.Container.dispatchEventImpl(Container.java:2099)
   at java.awt.Component.dispatchEvent(Component.java:4481)
   at java.awt.LightweightDispatcher.retargetMouseEvent(Container.java:4577)
   at java.awt.LightweightDispatcher.processMouseEvent(Container.java:4238)
   at java.awt.LightweightDispatcher.dispatchEvent(Container.java:4168)
   at java.awt.Container.dispatchEventImpl(Container.java:2085)
   at java.awt.Window.dispatchEventImpl(Window.java:2478)
   at java.awt.Component.dispatchEvent(Component.java:4481)
   at java.awt.EventQueue.dispatchEventImpl(EventQueue.java:643)
   at java.awt.EventQueue.access$000(EventQueue.java:84)
   at java.awt.EventQueue$1.run(EventQueue.java:602)
   at java.awt.EventQueue$1.run(EventQueue.java:600)
   at java.security.AccessController.doPrivileged(Native Method)
   at java.security.AccessControlContext$1.doIntersectionPrivilege(AccessControlContext.java:87)
   at java.security.AccessControlContext$1.doIntersectionPrivilege(AccessControlContext.java:98)
   at java.awt.EventQueue$2.run(EventQueue.java:616)
   at java.awt.EventQueue$2.run(EventQueue.java:614)
   at java.security.AccessController.doPrivileged(Native Method)
   at java.security.AccessControlContext$1.doIntersectionPrivilege(AccessControlContext.java:87)
   at java.awt.EventQueue.dispatchEvent(EventQueue.java:613)
   at java.awt.EventDispatchThread.pumpOneEventForFilters(EventDispatchThread.java:269)
   at java.awt.EventDispatchThread.pumpEventsForFilter(EventDispatchThread.java:184)
   at java.awt.EventDispatchThread.pumpEventsForHierarchy(EventDispatchThread.java:174)
   at java.awt.EventDispatchThread.pumpEvents(EventDispatchThread.java:169)
   at java.awt.EventDispatchThread.pumpEvents(EventDispatchThread.java:161)
   at java.awt.EventDispatchThread.run(EventDispatchThread.java:122)

Here is how I added your code:
http://www.mediafire.com/?2896ppyhlzewxtd

Thanks for your help

Pages: [1]

ignore | Print