Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (494)
Games in Android Showcase (113)
games submitted by our members
Games in WIP (562)
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  
  Reconstruct A* path  (Read 1309 times)
0 Members and 1 Guest are viewing this topic.
Offline Regenuluz
« Posted 2013-03-17 10:34:32 »

Hey guys,

So I've made an implementation of an A* algorithm for my AI class, and the algo runs blazingly* fast, it has no trouble founding a path in a 256*256 grid, however the reconstructPath method I've made is slow and subject to run out of heap space. Sad

So the question is, how the heck can I improve this piece of code:

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
private static List<Node> reconstructPath(Node start, Node goal) {
   List<Node> path = new ArrayList<>();
   start.came_from = null; // Reset the came_from
  Node current = goal;

   while(current != null) {
      path.add(current);
      current = current.came_from;
   }

   return path;
}



* That's my claim, and I'm sticking with it!
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 793
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #1 - Posted 2013-03-17 10:37:20 »

On a 256x256 grid, there is no way that piece of code can run out of heap space (as the longest possible path has 64K nodes), unless there is a bug (cyclic references).

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline Regenuluz
« Reply #2 - Posted 2013-03-17 11:55:29 »

Hrmph, care to look at my code then? Because I've stared myself blind on it xD

Here's the entire A* algo: http://pastebin.java-gaming.org/5a331617b43
The Node: http://pastebin.java-gaming.org/a33117b7340
And my super epic awesome *cough* Runner: http://pastebin.java-gaming.org/3311b837044

Edit:
Actually, nevermind. I just fixed it myself. xD Or at least it isn't crashing anymore. Added "neighbor.came_from = null;" inside the if statement on line 46. xD

Though other feedback would be welcome. The assignment is to make pathfinding(what I've done now) and then be able to easily change it to be able to perform "logical deduction in propositional logic on clause form." I'm hoping that all I have to change is the Node, the way I've done it. Smiley

Edit edit:
Actually, I still think there's a bug in it, because it shows waaay too many nodes as being visited, compared to what I'd expect of A*. :/

Edit edit edit:
There *is* a bug in it. Sad Searching for a path from (0,2) to (0,7) in a grid of 20x20, it doesn't find the shortest path. Sad Time to debug.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 793
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #3 - Posted 2013-03-17 12:15:41 »

There are three steps in debugging pathfinding and finding good heuristics:
  • Visualize it
  • Render it
  • Draw it

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline Regenuluz
« Reply #4 - Posted 2013-03-17 12:19:18 »

Well, I fixed the bug that made it choose a weird route. But It's searching *way* to many nodes, compared to what it should. I think I might've screwed up in the compareTo function, in the node, and that causes the ordering if the TreeSet to be weird.
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 793
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #5 - Posted 2013-03-17 12:20:47 »

If you render every step in the path-finding algorithm, you'll see what happens, and when/why it touches specific nodes.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline Regenuluz
« Reply #6 - Posted 2013-03-17 12:31:42 »

Hm, I fixed it when changing the openSet from a TreeSet to an ArrayList, and then doing Collections.sort(openSet).

Though the runtime likely is worse, because it's O(n) to use contains, vs. O(log(n)) in the TreeSet.

But I suppose the conclusion is that I seem to have *no* clue of how to use TreeSet. xD
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 793
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #7 - Posted 2013-03-17 13:16:28 »

But I suppose the conclusion is that I seem to have *no* clue of how to use TreeSet. xD

Here's your problem:
1  
2  
3  
4  
5  
6  
class Node {
   @Override
   public int compareTo(Node node) {
      return this.f - node.f;
   }
}


If compareTo returns zero, the Node is considered to be equal to the other node, as per the spec of Comparable. Never return zero, unless this.equals(that).

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline Regenuluz
« Reply #8 - Posted 2013-03-17 15:21:21 »

Hm, then what should I return if their distance is the same?
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 793
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #9 - Posted 2013-03-17 15:26:11 »

Literally anything but zero.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Regenuluz
« Reply #10 - Posted 2013-03-17 15:38:44 »

I've tried that, but it still results in a lot more nodes being visited, compared to using an arraylist. :/ And it's kind of silly that it searches in the opposite direction of the goal, when it has the choice to search towards it.
Offline Regenuluz
« Reply #11 - Posted 2013-03-18 19:25:24 »

Well, I'm lost for a solution as to how to use a TreeSet in my algorithm.

Any suggestions on how to fix the issue would be awesome!
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 793
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #12 - Posted 2013-03-18 19:48:05 »

If the value of 'this.f' changes after the node is inserted into the tree, it will break all logic.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline Regenuluz
« Reply #13 - Posted 2013-03-18 19:51:20 »

Well, I did try to remove the node, before updating the this.f value and then reinserting it, but the search pattern still searches in a diamond shape, far bigger than the box it should search.

Edit:

And I'm a complete and utter idiot. I removed the node and inserted it _before_ i changed the f value... -.-

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 (15 views)
2014-09-12 09:08:26

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

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

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

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

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

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

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

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

mitcheeb (30 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!