Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (494)
Games in Android Showcase (114)
games submitted by our members
Games in WIP (563)
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  
  Pathfinding problems  (Read 2283 times)
0 Members and 1 Guest are viewing this topic.
Offline Cypherix

Senior Newbie





« Posted 2011-09-14 16:58:39 »

This current algorithm I'm using is quick for down and right, slow for up and left, and really slow for diagonal moves... So much that it OutOfMemoryExceptions get thrown.... I was wondering if anyone would be able to help make it faster or get me some more efficient code?

http://www.mediafire.com/?8b3gmpbj1sz9cil

AStar.java
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  
94  
95  
96  
97  
98  
99  
100  
101  
102  
103  
104  
105  
106  
107  
108  
109  
110  
111  
112  
113  
114  
115  
116  
117  
118  
119  
120  
121  
122  
123  
124  
125  
126  
127  
128  
129  
130  
131  
132  
133  
134  
135  
136  
137  
138  
139  
140  
141  
142  
143  
144  
145  
146  
147  
148  
149  
150  
151  
152  
153  
154  
155  
156  
157  
158  
159  
160  
161  
162  
163  
164  
165  
166  
167  
168  
169  
170  
package citystates.astar;

import java.awt.Point;
import java.util.*;

public abstract class AStar
{

   
    private PriorityQueue<Path> paths;
    private HashMap<Node, Double> mindists;
    private Double lastCost;
    private int expandedCounter;
   
   
    Point goal;
    private boolean reverse;
   
    // Default constructor.
   public AStar ()
    {
        paths = new PriorityQueue<Path> ();
        mindists = new HashMap<Node, Double> ();
        expandedCounter = 0;
        lastCost = 0.0;
    }

    protected abstract List<Node> generateSuccessors (Node node);
   
    //Check if the current node is a goal for the problem.
   protected abstract boolean isGoal (Node node);

    //Cost for the operation to go to <code>to</code> from <code>from</from>.
   protected abstract Double g (Node from, Node to);

    // Estimated cost to reach a goal node. An admissible heuristic never gives a cost bigger than the real one.
   protected abstract Double h (Node from, Node to);

    // Check how many times a node was expanded.
   public int getExpandedCounter ()
    {
        return expandedCounter;
    }


    // Total cost function to reach the node <code>to</code> from <code>from</code>
   protected Double f (Path p, Node from, Node to)
    {
        Double g = g (from, to) + ((p.parent != null) ? p.parent.g : 0.0);
        Double h = h (from, to);

        p.g = g;
        p.f = g + h;

        return p.f;
    }

    // Expand a path.
   private void expand (Path path)
    {
        Node p = path.getPoint ();
        Double min = mindists.get (path.getPoint ());

        //If a better path passing for this point already exists then don't expand it.
       
        if (min == null || min.doubleValue () > path.f.doubleValue ())
        {
            mindists.put (path.getPoint (), path.f);
        } else
        {
            return;
        }

        List<Node> successors = generateSuccessors (p);

        for (Node t : successors)
        {
            Path newPath = new Path (path);
            newPath.setPoint (t);
            f (newPath, path.getPoint (), t);
            paths.offer (newPath);
        }

        expandedCounter++;
    }

    // Get the cost to reach the last node in the path.
   public Double getCost ()
    {
        return lastCost;
    }

    //Find the shortest path to a goal starting from the start
   public List<Node> compute (Node start, Node end)
    {
        try
        {
            Node startNode = null;
            Node endNode = null;
           
            if (end.y < start.y || end.x < start.x)
            {
                startNode = end;
                endNode = start;
                reverse = true;
            }
            else
            {
                startNode = start;
                endNode = end;
                reverse = false;
            }
            goal = new Point(endNode.x, endNode.y);
            start = startNode;
           
            Path root = new Path ();
            root.setPoint (start);

            //Needed if the initial point has a cost.
           f (root, start, start);

            expand (root);

            while (true)
            {
                Path p = paths.poll ();

                if (p == null)
                {
                    lastCost = Double.MAX_VALUE;
                    return null;
                }

                Node last = p.getPoint ();

                lastCost = p.g;

                if (isGoal (last))
                {
                    LinkedList<Node> retPath = new LinkedList<Node> ();

                    for (Path i = p; i != null; i = i.parent)
                    {
                        retPath.addFirst (i.getPoint ());
                    }
                   
                    if (!reverse)
                    {
                        return retPath;
                    }
                    else
                    {
                        LinkedList<Node> retPath2 = new LinkedList();
                        for (int i = retPath.size () - 1; i > 0; i --)
                        {
                            retPath2.add (retPath.get (i));
                        }
                        return retPath2;
                    }
                }
                expand (p);
            }
        } catch (Exception e)
        {
            e.printStackTrace ();
        }
        return null;

    }
}


PathFinder.java
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  
94  
95  
package citystates.astar;

import java.awt.Point;
import java.util.*;

public class PathFinder extends AStar
{

    private int[][] map;

    public PathFinder (int[][] map)
    {
        this.map = map;
    }

    protected boolean isGoal (Node node)
    {
        return (node.x == goal.x) && (node.y == goal.y);
    }

    protected Double g (Node from, Node to)
    {

        if (from.x == to.x && from.y == to.y)
        {
            return 0.0;
        }

        if (map[to.y][to.x] == 1)
        {
            return 1.0;
        }

        return Double.MAX_VALUE;
    }

    protected Double h (Node from, Node to)
    {
        // Use the Manhattan distance heuristic.
       return new Double (Math.abs (map[0].length - 1 - to.x) + Math.abs (map.length - 1 - to.y));
    }

    protected List<Node> generateSuccessors (Node node)
    {
        List<Node> returnList = new LinkedList<Node> ();
        int x = node.x;
        int y = node.y;
        // DOWN
       if (y < map.length - 1 && map[y + 1][x] == 1)
        {
            returnList.add (new Node (x, y + 1));
        }
        // UP
       if (y > 0 && map[y - 1][x] == 1)
        {
            returnList.add (new Node (x, y - 1));
        }

        // RIGHT
       if (x < map[0].length - 1 && map[y][x + 1] == 1)
        {
            returnList.add (new Node (x + 1, y));
        }

        // LEFT
       if (x > 0 && map[y][x - 1] == 1)
        {
            returnList.add (new Node (x - 1, y));
        }
        // TOP LEFT
       if (x > 0 && y > 0 && map[y - 1][x - 1] == 1)
        {
            returnList.add (new Node (y - 1, x - 1));
        }
        // TOP RIGHT
       if (x < map[0].length - 1 && y > 1 && map[y - 1][x + 1] == 1)
        {
            returnList.add (new Node (y - 1, x + 1));
        }

        // BOTTOM LEFT
       if (y < map.length - 1 && x > 1 && map[y + 1][x - 1] == 1)
        {
            returnList.add (new Node (y + 1, x - 1));
        }

        if (y < map.length - 1 && x < map[0].length - 1 && map[y + 1][x + 1] == 1)
        {
            returnList.add (new Node (y + 1, x + 1));
        }


        return returnList;
    }
}
Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Reply #1 - Posted 2011-09-14 17:30:47 »

Why not just paste the code here? Nobody is going to want to go to mediafire.

See my work:
OTC Software
Offline Cypherix

Senior Newbie





« Reply #2 - Posted 2011-09-15 01:50:30 »

Code posted...
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline ReBirth
« Reply #3 - Posted 2011-09-15 03:17:03 »

Based on my experience, OutOfMemoryExceptions is usually thrown by List, ArrayList and HashMap in case you populate them without trying to reduce the size.

In line 153 I see a recursion inside while(true) which is seems dangerous. Does that recursive have an end point?

Offline ra4king

JGO Kernel


Medals: 345
Projects: 3
Exp: 5 years


I'm the King!


« Reply #4 - Posted 2011-09-15 03:39:04 »

Don't use multiline comments here on JGO, since there is a bug in the Java code syntax highlighter that causes everything below it to be highlighted green also, which is a pain to read.

Offline Cypherix

Senior Newbie





« Reply #5 - Posted 2011-09-15 03:58:33 »

Okay, done... Now can anyone help me (Without pointing me in the direction of JGO's special conventions -_-)

EDIT: Didn't see ReBirth
Based on my experience, OutOfMemoryExceptions is usually thrown by List, ArrayList and HashMap in case you populate them without trying to reduce the size.

In line 153 I see a recursion inside while(true) which is seems dangerous. Does that recursive have an end point?

Yes... Because it uses all of the jvm memory, which the garbage collector can not dispose of, because it's being used... I know...

Do you know a better way of doing it?

Currently it returns null if it's been through all of the paths, or returns the path if it has reached the end.
In either case, it's not a very good AStar algorithm, I will admit.
Offline Cypherix

Senior Newbie





« Reply #6 - Posted 2011-09-15 17:03:46 »

Are you guys serious... I just asked for some help, I'm sure you guys have all got experience with AStar and multiple path-finding algorithms, heuristic or not. I came here because whilst my ability to program in Java exceeds many, my experience in programming games does not. I just need someone to lead me in the right direction... Maybe give me some better code or assist me in improving this code...

Currently this code takes a long time to process any path, even across something as simple as a 10x10 grid... My first test was with a 10x10 grid of tiles which contained no blocked tiles, I first tested 0,0 to 8,8 worked fine... maybe not the best possible path but it still returned a path in about 40ms... then I tried 8,8 to 6,5... It took over 3000ms -__- Anything even further than that throws OutOfMemoryExceptions due to it using way to much memory.
Offline sproingie

JGO Kernel


Medals: 202



« Reply #7 - Posted 2011-09-15 17:11:32 »

Don't use multiline comments here on JGO, since there is a bug in the Java code syntax highlighter that causes everything below it to be highlighted green also, which is a pain to read.

Does that also apply to javadoc comments?  I'd hate to have to strip it all out of any code I paste in here.
Offline SimonH
« Reply #8 - Posted 2011-09-15 20:32:10 »

I skimmed through your code and nothing jumped out as being obviously wrong...
Have you tried the java profiler (it's in java_home/bin) on the code? That should at least give you an idea of what's soaking up all that memory!

People make games and games make people
Offline Cypherix

Senior Newbie





« Reply #9 - Posted 2011-09-16 03:06:38 »

My problem isn't not knowing why It's using so much memory.. I've just stated above that the reason it is using all this memory is because it keeps increasing the size of an arraylist way to much and the Garbage Collector can't dispose of it due to it still being used. The problem is my lack of experience in Game Development not my lack of experience in Java.

I need a better way to go about it, or simply just give me a complete different set of code using a more efficient way. I thought this forum would be full of people with plenty of experience in this topic...
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline theagentd
« Reply #10 - Posted 2011-09-16 09:19:01 »

My problem isn't not knowing why It's using so much memory.. I've just stated above that the reason it is using all this memory is because it keeps increasing the size of an arraylist way to much and the Garbage Collector can't dispose of it due to it still being used. The problem is my lack of experience in Game Development not my lack of experience in Java.

I need a better way to go about it, or simply just give me a complete different set of code using a more efficient way. I thought this forum would be full of people with plenty of experience in this topic...
Well, if you don't think we're helpful enough, why don't you ask on 4chan?
...
You're not using a closed list. You're not checking to see if the neighbors aren't already in the open list when you add them either. You're filling your <paths> list with duplicate and irrelevant nodes. The fact that your implementation is faulty and it's our fault for not being "smart" enough to fix it for you is kind of annoying.

Myomyomyo.
Offline Cypherix

Senior Newbie





« Reply #11 - Posted 2011-09-17 06:31:20 »

It is in no way the fault of anyone else and I couldn't care else about the intelligence levels of the members here. You's do however have experience in this and I recognise this expertise, I simply would like some assistance. How would I achieve my goal?
Offline theagentd
« Reply #12 - Posted 2011-09-17 08:26:54 »

Sigh... Why do I bother?

Your problem is a combination of generateSuccessors() and minDists. minDists should work as a closed list, but at the moment it doesn't. That's because you are creating new Nodes in generateSuccessors() all the time, and then expecting two different node objects with the same x and y to be the same object. Basically
1  
2  
3  
new Node(x, y) != new Node(x, y)
//And also
new Node(x, y).hashCode() != new Node(x, y).hashCode()

... so your hashmap won't work as it should either.
Therefore your minDists keeps filling up with new Node objects, and your paths list keeps keep filling up with Path objects as it thinks every tile it encounters is a new one.

There you have it. Run along and play. Now if you'll excuse me, I have a festival to attend.

Myomyomyo.
Offline ra4king

JGO Kernel


Medals: 345
Projects: 3
Exp: 5 years


I'm the King!


« Reply #13 - Posted 2011-09-18 01:10:48 »

Sigh... Why do I bother?
...
There you have it. Run along and play. Now if you'll excuse me, I have a festival to attend.
I would have expected a better tone from you. Behave yourself!

I agree with the OP, people were only giving him advice to look into the memory problem, when it was actually a problem with his code. However, @OP, you could have been a little bit more patient and wait for all our "experts" to show up.

Offline theagentd
« Reply #14 - Posted 2011-09-18 12:16:45 »

Sigh... Why do I bother?
...
There you have it. Run along and play. Now if you'll excuse me, I have a festival to attend.
I would have expected a better tone from you. Behave yourself!

I agree with the OP, people were only giving him advice to look into the memory problem, when it was actually a problem with his code. However, @OP, you could have been a little bit more patient and wait for all our "experts" to show up.
So this guy shows up with a problem in his code. Okay, he could debug it and easily find the problem, but maybe he's not using an IDE for some reason or don't know how to do that. That's okay, we've all been there. He uploads his code to MediaFire, and doesn't know about the comment bug in the code blocks. Can't blame him for that either, as he might be new to JGO, e.t.c. The only thing that annoyed me was his attitude.

Are you guys serious... I just asked for some help, I'm sure you guys have all got experience with AStar and multiple path-finding algorithms, heuristic or not. I came here because whilst my ability to program in Java exceeds many, my experience in programming games does not. I just need someone to lead me in the right direction... Maybe give me some better code or assist me in improving this code...
1. "This is the Internet, I demand help." ... which no one is obliged to give you. Scanning through somebody else's code is not easy and it usually takes some time to understand the flow of the program. I can see why he didn't get any quick answers.
2. Self-proclaimed Java Guru? That made me lol a little.

He then proceeds to ignore and not even mention SimonH's tip to use the profiler (he could have said he doesn't know how to use it or anything). He could have just acknowledged that he had actually gotten a tip or something instead of keeping saying "Do it for me.". The whole thing feels like we're doing his programming class homework.
It is in no way the fault of anyone else and I couldn't care else about the intelligence levels of the members here. You's do however have experience in this and I recognise this expertise, I simply would like some assistance. How would I achieve my goal?
This one is my favorite. I may be reading too much between the lines here, but from what I could make out he basically says "It's not your fault", "You are stupid" and "To prove you are not stupid, fix my code". Therefore my *sigh*.

All of these obviously warranted my rude response in my opinion. I can agree on that I could have been nicer, but I'm not going to apologize. He had it coming to be honest. Sure, he might have just had a shitty day or something, but I can't be nice to everyone who treats me (and other people on JGO) like personal code fixers. Sorry.
Sigh... Why do I bother?
...
There you have it. Run along and play. Now if you'll excuse me, I have a festival to attend.
I would have expected a better tone from you. Behave yourself!
I have a step dad on JGO.  Cool BTW, that festival involved carrying a shrine weighing Double.MAX_VALUE kilos, so if you believe in karma, that should be enough.

I did help him, you know. If you're annoyed over HOW I helped him, I'd like to redirect your wrath against how he asked for help.

Myomyomyo.
Offline Cypherix

Senior Newbie





« Reply #15 - Posted 2011-09-18 15:43:37 »

Oh I didn't realise this thread became a bitch-fest..

Quote
He then proceeds to ignore and not even mention SimonH's tip to use the profiler (he could have said he doesn't know how to use it or anything). He could have just acknowledged that he had actually gotten a tip or something instead of keeping saying "Do it for me.". The whole thing feels like we're doing his programming class homework.

Herp derp, My post was directed at all posts to do with memory related problems since I already knew what was causing the memory overload.


Quote
This one is my favorite. I may be reading too much between the lines here, but from what I could make out he basically says "It's not your fault", "You are stupid" and "To prove you are not stupid, fix my code". Therefore my *sigh*.

I don't think you should pursue a career in Human Psychology.. Nuf said.

Quote
1. "This is the Internet, I demand help." ... which no one is obliged to give you. Scanning through somebody else's code is not easy and it usually takes some time to understand the flow of the program. I can see why he didn't get any quick answers.
2. Self-proclaimed Java Guru? That made me lol a little.
1. Again, don't pursue a career in Psychology... Nor Support Desk
2. Prove otherwise




I'm thankful for the assistance, that is all I needed.
There is no need for an attitude, this is a forum; words are as is.
Offline theagentd
« Reply #16 - Posted 2011-09-18 16:08:46 »

Oh I didn't realise this thread became a bitch-fest..

Quote
He then proceeds to ignore and not even mention SimonH's tip to use the profiler (he could have said he doesn't know how to use it or anything). He could have just acknowledged that he had actually gotten a tip or something instead of keeping saying "Do it for me.". The whole thing feels like we're doing his programming class homework.

Herp derp, My post was directed at all posts to do with memory related problems since I already knew what was causing the memory overload.


Quote
This one is my favorite. I may be reading too much between the lines here, but from what I could make out he basically says "It's not your fault", "You are stupid" and "To prove you are not stupid, fix my code". Therefore my *sigh*.

I don't think you should pursue a career in Human Psychology.. Nuf said.

Quote
1. "This is the Internet, I demand help." ... which no one is obliged to give you. Scanning through somebody else's code is not easy and it usually takes some time to understand the flow of the program. I can see why he didn't get any quick answers.
2. Self-proclaimed Java Guru? That made me lol a little.
1. Again, don't pursue a career in Psychology... Nor Support Desk
2. Prove otherwise




I'm thankful for the assistance, that is all I needed.
There is no need for an attitude, this is a forum; words are as is.

You're not really helping with that kind of post, but you're welcome.

Myomyomyo.
Offline sproingie

JGO Kernel


Medals: 202



« Reply #17 - Posted 2011-09-19 16:34:03 »

Guy's cruising for a swift ban at this rate.
Offline Mike

JGO Wizard


Medals: 76
Projects: 1
Exp: 6 years


Java guru wanabee


« Reply #18 - Posted 2011-09-19 18:42:53 »

I really don't know what's going on between you two, get a room?

Two things to say:
I also want ra4king as my step dad, he's so cool!
I think this thread should be locked before it derails even more.

My current game, Minecraft meets Farmville and goes online Smiley
State of Fortune | Discussion thread @ JGO
Offline theagentd
« Reply #19 - Posted 2011-09-19 19:08:33 »

Guy's cruising for a swift ban at this rate.

Me or him? xD
I really don't know what's going on between you two, get a room?

Two things to say:
I also want ra4king as my step dad, he's so cool!
I think this thread should be locked before it derails even more.
Yeah, someone please lock this thread before I do something stupid. xD

Myomyomyo.
Offline Gudradain
« Reply #20 - Posted 2011-09-19 20:46:44 »

@Cypherix : Just one thing, learn how to do debugging in a game environment. That will be the most useful thing you can learn.
Offline ra4king

JGO Kernel


Medals: 345
Projects: 3
Exp: 5 years


I'm the King!


« Reply #21 - Posted 2011-09-19 22:25:09 »

I really don't know what's going on between you two, get a room?

Two things to say:
I also want ra4king as my step dad, he's so cool!
I think this thread should be locked before it derails even more.
Clean your room Cool

Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Reply #22 - Posted 2011-09-20 16:47:31 »

This topic has been locked and moderated. Let's keep things civil, no?  Yawn

See my work:
OTC Software
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.

Dwinin (22 views)
2014-09-12 09:08:26

Norakomi (55 views)
2014-09-10 13:57:51

TehJavaDev (66 views)
2014-09-10 06:39:09

Tekkerue (33 views)
2014-09-09 02:24:56

mitcheeb (54 views)
2014-09-08 06:06:29

BurntPizza (38 views)
2014-09-07 01:13:42

Longarmx (24 views)
2014-09-07 01:12:14

Longarmx (30 views)
2014-09-07 01:11:22

Longarmx (28 views)
2014-09-07 01:10:19

mitcheeb (37 views)
2014-09-04 23:08:59
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

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06

List of Learning Resources
by SilverTiger
2014-07-31 11:54:12

HotSpot Options
by dleskov
2014-07-08 01:59:08
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!