Java-Gaming.org Hi !
Featured games (83)
games approved by the League of Dukes
Games in Showcase (539)
Games in Android Showcase (132)
games submitted by our members
Games in WIP (603)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  A* Trouble  (Read 798 times)
0 Members and 1 Guest are viewing this topic.
Offline Cypherix

Senior Newbie





« Posted 2011-09-11 17: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;

    }
Offline ReBirth
« Reply #1 - Posted 2011-09-12 03: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.

Offline Cypherix

Senior Newbie





« Reply #2 - Posted 2011-09-12 04: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!
Legends of Yore - The Casual Retro Roguelike
Offline Gudradain
« Reply #3 - Posted 2011-09-12 05: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! Smiley

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.
Offline Cypherix

Senior Newbie





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

Thanks, Looks good. I do have a problem with it, but I pm'd you Smiley
Hopefully all will be well.
Offline Cypherix

Senior Newbie





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

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 Smiley
Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

rwatson462 (36 views)
2014-12-15 09:26:44

Mr.CodeIt (29 views)
2014-12-14 19:50:38

BurntPizza (61 views)
2014-12-09 22:41:13

BurntPizza (98 views)
2014-12-08 04:46:31

JscottyBieshaar (58 views)
2014-12-05 12:39:02

SHC (74 views)
2014-12-03 16:27:13

CopyableCougar4 (76 views)
2014-11-29 21:32:03

toopeicgaming1999 (137 views)
2014-11-26 15:22:04

toopeicgaming1999 (127 views)
2014-11-26 15:20:36

toopeicgaming1999 (37 views)
2014-11-26 15:20:08
Resources for WIP games
by kpars
2014-12-18 10:26:14

Understanding relations between setOrigin, setScale and setPosition in libGdx
by mbabuskov
2014-10-09 22:35:00

Definite guide to supporting multiple device resolutions on Android (2014)
by mbabuskov
2014-10-02 22:36:02

List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!