Java-Gaming.org Hi !
Featured games (83)
games approved by the League of Dukes
Games in Showcase (538)
Games in Android Showcase (132)
games submitted by our members
Games in WIP (601)
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  
  AStar Problem  (Read 667 times)
0 Members and 1 Guest are viewing this topic.
Offline Demiraid

Junior Newbie





« Posted 2012-08-28 09:30:51 »

Hello, I made a small game awhile back, and I had an A-Star algorithm used for making the NPC's follow a particular path. This algorithm worked fine until recently, I'm not exactly sure what i've touched. But it never seems to work anymore. I have tried to set up logging so that I can debug it, but I can't seem to figure out what the problem is. This is the output of the log

Quote
Path Not Found

Start (0, 0)
End (8, 1)

Path < (0,0)   (1,1)   (1,2)   (3,1)   >


Printing Map

 1 1 1 0 1 1 1 1 1 1 1
 0 1 1 1 1 1 1 1 1 1 1
 1 1 1 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 1 1 1
 0 0 0 0 0 0 0 0 1 1 0
 0 0 0 0 0 0 0 0 1 1 1
 1 1 1 1 1 1 1 1 0 0 0
 1 1 1 1 1 1 1 1 0 0 0

With 0 = Unwalkable 1 = Walkable

My code is as follows:

Pathfinder.java http://pastebin.com/KL43FbuD
NodeList.java http://pastebin.com/dqhuTDye
Node.java http://pastebin.com/BZqJgY9j
Movement.java http://pastebin.com/q5jUHJZ3
AStarMap.java http://pastebin.com/UF5h9Ux4

The method gets called like this:

1  
2  
3  
4  
5  
6  
7  
8  
Node startNode = new Node(npc.getX(), npc.getY());
Node endNode = new Node(8, 1);
     
AStarMap loader = new AStarMap(map);
PathFinder pathMaker = new PathFinder(loader.getMap());
pathMaker.findPath(startNode, endNode);
     
pathMaker.displayPath();


No matter what start and end position it is, it always returns that same path.
There are no exceptions being thrown, there is just a problem with my code. I would be so greatful for any assistance.
Offline UprightPath
« Reply #1 - Posted 2012-08-28 10:01:22 »

Ah, first: You're missing a few chunks of code that we might need to see. Movement and whatever the main(String[] args) or whatever you're using to call it is using.

Second: I'm betting that you're not filling your open list correctly. It seems that you've either got a broken method (getSuccessors(...)) or that your iteration through the list returned is broken.
1  
2  
3  
PathFinder.java Lines 53 & 54
if (movement == null)
    break;

That's my suspect in this. I mean, it's probably not what's ending it, however if you need this in there to get your program to work, then you're obviously having issues with things somewhere (Since there's no way that movement can be null, unless you're inserting a null value in there somewhere.

Ah, there could be other issues in there that I just can't see, 'cause of the way you code (Blame me at this point, I'm exhausted). However, it's considered bad practice to use 'cut-and-paste' coding. This is a quick readability rewrite, and one that'll let you ensure that you're not accidentally creating your Movement objects incorrectly.
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  
public ArrayList<Movement> getSuccessors(Node currentNode) {
   ArrayList<Movement> movements = new ArrayList();
   int x = currentNode.xPosition;
   int y = currentNode.yPosition;
   if(isIn(x - 1, y)) { // LEFT
      movements.add(getMovement(nodeMap[y][x - 1], currentNode));
   }
   if(isIn(x - 1, y - 1)) { // TOP LEFT
      movements.add(getMovement(nodeMap[y - 1][x - 1], currentNode));
   }
   /*
   * ...
   * Enter the other six directions
   * ...
   */

   return movements;
}
   
public Movement getMovement(Node next, Node currentNode, boolean diagonal) {
   int g = currentNode.movementCost + diagonal ? COST_DIAG : COST_NORM;
   int heuristicDistance = calculateHeuristic(node);
   return new Movement(node, g, heuristicDistance)
}

public boolean isIn(int posX, int posY) {
   return posX >= 0 && posX < sizeX && posY >= 0 && posY < sizeY;
}

Offline Demiraid

Junior Newbie





« Reply #2 - Posted 2012-08-28 14:20:25 »

Thankyou for the readability Advice. It made it easier to find what was wrong, there was a few places I had to fix up in the PathFinder class. One of them was in the getSuccessors methods, so thank you.

It was all really stupid mistakes that I overlooked haha

I really appreciate it 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 (30 views)
2014-12-15 09:26:44

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

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

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

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

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

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

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

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

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