Jump to content

  • Log In with Google      Sign In   
  • Create Account

Pathfinding problem


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
19 replies to this topic

#1 lavenderwong   Members   -  Reputation: 106

Like
0Likes
Like

Posted 02 December 2013 - 11:49 PM

I am using BFS to get the path for my car with the following code. But it seems that the program cannot add any node in the path... could anyone point out my problem, please?

private void pathFinding_BFS(Node start, Node end){
        LinkedList<Node> queue = new LinkedList<Node>();
        queue.add(start);
        start.setMarked();
        while (!queue.isEmpty()){
            Node temp = queue.poll();
            if (temp.equals(end)){
                temp.setPrevNodeInPath(temp);
                return;
            }
            for (Node n : temp.getAdjacentNode()){
                if (!n.isMarked()){
                    n.setMarked();
                    n.setPrevNodeInPath(temp);
                    queue.add(n);
                }
            }
        }        
    }
    
    public  List<Point> getShortestPath(Point start, Point end){
        Node src = new Node(start);
        Node destination = new Node(end);
        pathFinding_BFS(src, destination);
        List<Point> path = new ArrayList<Point>();
        while (destination.getPrevNodeInPath(destination) != null){
            destination = destination.getPrevNodeInPath(destination);
            path.add(destination.getPointInPath(destination));
        }
        Collections.reverse(path);
        return path;
    
    }
   
    public class Node{
        private Point loc;
        private Node prevNodeInPath;
        private boolean marked = false;
    
        public Node(Point p){
            loc = p;
        }

        public void setPrevNodeInPath(Node n){
            prevNodeInPath = n;
        }
        
        public Node getPrevNodeInPath(Node n){
            return prevNodeInPath;
        }
        
        public Point getPointInPath(Node n){
            return loc;
        }
        
        public void setMarked(){
            this.marked = true;
        }
    
        public boolean isMarked(){
            return marked;
        }
        
        public List<Node> getAdjacentNode(){
            List<Node> adj = new ArrayList<Node>();
            Point up = new Point(loc.x, loc.y+1);
            Point down = new Point(loc.x, loc.y-1);
            Point left = new Point(loc.x-1, loc.y);
            Point right = new Point(loc.x+1, loc.y);
            if (ground.contains(up))
                adj.add(new Node(up));
            if (ground.contains(down))
                adj.add(new Node(down));
            if (ground.contains(left))
                adj.add(new Node(left));
            if (ground.contains(right))
                adj.add(new Node(right));
            return adj;
        }
    }

Thank you!!



Sponsor:

#2 Eck   Crossbones+   -  Reputation: 3347

Like
1Likes
Like

Posted 03 December 2013 - 09:02 AM

Debuggers are your buddy! Put a breakpoint in your code and see exactly where it's failing.

 

I've noticed a couple of potential issues, but I'm not a Java guy so hopefully I'm not wasting your time. smile.png

 

I think this is probably your problem. In pathFinding_BFS, you're setting the (temp) last node's previous node to itself but not adjusting the "end" node. Maybe it should be something like:

end.setPrevNodeInPath(temp.getPrevNodeInPath());
 
I also noticed in your getAdjacentNode, you're creating new instances of Nodes rather than looking up and returning an existing node. This will always return a fresh unmarked node so you'll never be pruning out nodes you've already visited. With a breadth first search, I think you'll eventually get a solution but you'll be wasting time revisiting nodes.
 

I don't think this is your issue, but it's worth considering. Since this is Java, I'm not sure if it treats Point as a reference type or a value type. If it's a reference type and ground is a list of points, then your ground.contains(x) will always return false. Reference types are equal if they reference the same item (but yours can't since you just new'ed them up). See a related post of mine for more details: 

http://www.gamedev.net/topic/649248-list-remove/#entry5103729

 

Definitely not your problem, but getPreviousNodeInPath and getPointInPath probably shouldn't take a node parameter.

 

I hope this helps. If not, use the debugger/breakpoints and you'll be able to better tell what the heck is going on.

 

- Eck


Edited by Eck, 03 December 2013 - 09:05 AM.


#3 lavenderwong   Members   -  Reputation: 106

Like
0Likes
Like

Posted 03 December 2013 - 09:28 AM

Thank you for your reply. I really appreciate it.

 

i am still new to the java program and my knowledge is limited, hope you don't mind.

 

for the debugger problem, i am using notepad++ to build my program, so i guess i can't use any debugger with it...

 

i had declared ground with List<Point>, i guess List.contain is accepting object type parameter, so i think Point is accepted, isn't it?

 

and thanks for your advice, i had removed the node parameter in the getPrevNodeInPath and getPointInPath.



#4 KnolanCross   Members   -  Reputation: 1361

Like
0Likes
Like

Posted 03 December 2013 - 09:31 AM

I am no java expert but those two lines got my attention:

if (temp.equals(end)){
   temp.setPrevNodeInPath(temp);

And this one:

while (destination.getPrevNodeInPath(destination) != null){

Wouldn't the end node point to itself in the getPrev node?

 

Also, you are not checking for the "No path" condition. I would add a console print (or whatever the command is for java) after the while to tell you if no path was found.

 

Semi OT: have you consider using A* instead?


Currently working on a scene editor for ORX (http://orx-project.org), using kivy (http://kivy.org).


#5 lavenderwong   Members   -  Reputation: 106

Like
0Likes
Like

Posted 03 December 2013 - 09:34 AM

a* maybe too much to my program as the path to find is not that complex.. also, it's complex to me in term of coding....

 

I have revised some of the code from your comment. But the result is still the same. you may right that i cannot add any node into the list, the problem may be really in ground.contains(up)..etc

private void pathFinding_BFS(Node start, Node end){
		LinkedList<Node> queue = new LinkedList<Node>();
		queue.add(start);
		start.setMarked();
		while (!queue.isEmpty()){
			Node temp = queue.poll();
			if (temp.equals(end)){
				//temp.setPrevNodeInPath();
				end.setPrevNodeInPath(temp.getPrevNodeInPath());
				return;
			}
			for (Node n : temp.getAdjacentNode()){
				if (!n.isMarked()){
					n.setMarked();
					n.setPrevNodeInPath(temp);
					queue.add(n);
				}
			}
		}		
	}
	
	public  List<Point> getShortestPath(Point start, Point end){
		Node src = new Node(start);
		Node destination = new Node(end);
		pathFinding_BFS(src, destination);
		List<Point> path = new ArrayList<Point>();
		while (destination.getPrevNodeInPath() != null){
			destination = destination.getPrevNodeInPath();
			path.add(destination.getPointInPath());
		}
		Collections.reverse(path);
		return path;
	
	}	
	
	public class Node{
		private Point loc;
		private Node prevNodeInPath;
		private boolean marked = false;
	
		public Node(Point p){
			loc = p;
		}

		public void setPrevNodeInPath(Node n){
			prevNodeInPath = n;
		}
		
		public Node getPrevNodeInPath(){
			return prevNodeInPath;
		}
		
		public Point getPointInPath(){
			return loc;
		}
		
		public void setMarked(){
			this.marked = true;
		}
	
		public boolean isMarked(){
			return marked;
		}
		
		public List<Node> getAdjacentNode(){
			List<Node> adj = new ArrayList<Node>();
			Point up = new Point(loc.x, loc.y+1);
			Point down = new Point(loc.x, loc.y-1);
			Point left = new Point(loc.x-1, loc.y);
			Point right = new Point(loc.x+1, loc.y);
			if (ground.contains(up))
				adj.add(new Node(up));
			if (ground.contains(down))
				adj.add(new Node(down));
			if (ground.contains(left))
				adj.add(new Node(left));
			if (ground.contains(right))
				adj.add(new Node(right));
			return adj;
		}
	}


#6 KnolanCross   Members   -  Reputation: 1361

Like
0Likes
Like

Posted 03 December 2013 - 09:58 AM

It seems correct to me now. Still, I would change the pathfinding_BFS to return a Bool telling if it found the path or not.

 

PS: If you don't care about performance, the easiest algorithm to use is Floyd Warshal.

http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm


Currently working on a scene editor for ORX (http://orx-project.org), using kivy (http://kivy.org).


#7 dmatter   Crossbones+   -  Reputation: 3297

Like
1Likes
Like

Posted 03 December 2013 - 11:51 AM

I think the thing that is preventing your program from working is your use of Java's equality model (which is actually fundamentally broken in its own right, but oh well, it is what it is). Namely, at minimum, you need to provide a suitable equals() method and it is standard practice to also provide a hash() function whenever you overload equals(), but that actually isn't strictly necessary here.

You'll need an equals() method in your Node class so that your condition if (temp.equals(end)) works correctly. And you'll need one in your Point class, so that if (ground.contains(up)) works.

You may well say that two nodes are equal if they are at the same location (regardless of their other fields), ergo we can define your Node's equals method like this..
 
boolean equals(Object o) {
    if (o == null || !(o instanceof Node)) { return false; } // o is null or not a Node object, defo not equal
    Node other = (Node)o;
    return this.loc.equals(other.loc); // nodes are equal if their locations are equal
}
Your Point class's equals method probably looks something like this:
 
boolean equals(Object o) {
    if (o == null || !(o instanceof Point)) { return false; } // o is null or not a Point object, defo not equal
    Point other = (Point)o;
    return this.x == other.x && this.y == other.y; // component-wise equality
}
Next up, a comment on your BFS algorithm.

Rather than waiting until you pull off the 'end' node from the queue, you could move that check into the adjacent nodes loop. That way once you find an adjacent node which equals the 'end' node then you can stop right there. As things stand at the moment you'll encounter the 'end' node in the adjacent nodes loop, add it to the back of the queue and have to process all the nodes in-front of it (needlessly, since the 'end' node is in the queue already, none of the nodes still in the queue can possibly be on the shortest path) until eventually the 'end' node is poll'd off the front of the queue.

Hope that helps.

Edited by dmatter, 03 December 2013 - 11:56 AM.


#8 lavenderwong   Members   -  Reputation: 106

Like
0Likes
Like

Posted 03 December 2013 - 11:26 PM

Thanks for your advice. I could add the equal method in my node class.

 

But for Point class, i am using the list.contains to check if the adjacent point is also a ground, could i know how changing the point.equal method could connect to the list.contains method?

 

Also, i actually do not know how to override the method in Point class. is it like adding the following method in my code ? and it knows overriding the point.equal method?

@Override

public boolean equal(Object o){

....}

 

sorry for my silly question..


Edited by lavenderwong, 03 December 2013 - 11:50 PM.


#9 dmatter   Crossbones+   -  Reputation: 3297

Like
0Likes
Like

Posted 04 December 2013 - 04:12 AM

But for Point class, i am using the list.contains to check if the adjacent point is also a ground, could i know how changing the point.equal method could connect to the list.contains method?

Sure! It is simply defined by Oracle to be that way and stated in their documentation for List#contains():

"Returns true if this list contains the specified element. More formally, returns true if and only if this list contains at least one element e such that (o==null ? e==null : o.equals(e))."

So they're saying that internally the contains() method will use the equals() method of your class to work out whether the list contains the object.
 
Note that List (and its derivatives, e.g. ArrayList and LinkedList) only use the equals method but there are other collection classes, like a Set, which will also need the hashCode() method to be overriden in addition to equals().
 

Also, i actually do not know how to override the method in Point class. is it like adding the following method in my code ? and it knows overriding the point.equal method?
@Override
public boolean equal(Object o){
....}
 
sorry for my silly question..

It's not a silly question at all!

If Point is a class that you've defined then yes, if you put that code in your Point class (just like you did with Node presumably) then it will override the equals method that is inherited from Object. All classes implicitly inherit from the Object class, which is where the default equals() implementation lives, the problem with the default equals() implementation is that it only compares the references (rather like when using ==) which is usually not what you want especially when you have two separate instances that need to compare as equal.

If Point is not a class that you've defined yourself, so it comes from a library, then there's an excellent chance that the library writers have already done it. You could find out by looking in their Javadoc.


Edited by dmatter, 04 December 2013 - 04:25 AM.


#10 lavenderwong   Members   -  Reputation: 106

Like
0Likes
Like

Posted 04 December 2013 - 05:09 AM

I am using the Point class (http://docs.oracle.com/javase/7/docs/api/java/awt/Point.html#equals%28java.lang.Object%29).

 

I check in

 

http://docs.oracle.com/javase/7/docs/api/java/awt/Point.html#equals%28java.lang.Object%29

 

it said the object parameter refers to the object to be compared with this Point2D, is that means point type is comparable?



#11 dmatter   Crossbones+   -  Reputation: 3297

Like
0Likes
Like

Posted 04 December 2013 - 05:16 AM

I am using the Point class (http://docs.oracle.com/javase/7/docs/api/java/awt/Point.html#equals%28java.lang.Object%29).

 

I check in

 

http://docs.oracle.com/javase/7/docs/api/java/awt/Point.html#equals%28java.lang.Object%29

 

it said the object parameter refers to the object to be compared with this Point2D, is that means point type is comparable?

 

Indeed they are comparable.

For me the two main giveaways are:

 

1) The fact that the equals() method has a section there at all means it was overridden. If it wasn't overriden it would merely gain a small mention in the section titled "Methods inherited from class java.lang.Object".

 

2) The description that states how they have chosen to define equality matches the description that we would need: "Two instances of Point2D are equal if the values of their x and y member fields, representing their position in the coordinate space, are the same."


Edited by dmatter, 04 December 2013 - 05:17 AM.


#12 lavenderwong   Members   -  Reputation: 106

Like
0Likes
Like

Posted 04 December 2013 - 05:20 AM

If this is the case, i would need to seek the problems in my program as it still cannot return anything in the path list.



#13 dmatter   Crossbones+   -  Reputation: 3297

Like
0Likes
Like

Posted 04 December 2013 - 08:30 AM

I guess it is now getting stuck in an infinite loop because getAdjacentNode always constructs new instances of Node so they will always have their marked flag set to false - you will never get a Node returned by getAdjacentNode with a marked flag of true. This kind of screws up your check that prevents getting stuck in cycles: if (!n.isMarked()).
 
You may have to reconsider the way you track previously explored nodes. For example maybe you can keep a collection of previously explored nodes (or points), every time you encounter one add it to the collection, when you want to see if you've encountered a node before then you just look in that collection. I.e. A node (or point) either is or is not in the collection, which acts as your boolean flag.

 

Edit: Although, thinking about it, a breadth-first search should always complete, even with cycles.


Edited by dmatter, 04 December 2013 - 08:54 AM.


#14 Eck   Crossbones+   -  Reputation: 3347

Like
1Likes
Like

Posted 04 December 2013 - 08:43 AM

Well, I think you have a few options. 

 

1. Download an IDE with a debugger instead of using Notepad++. This is what I recommend, though I can't point you to what you should use. Perhaps Eclipse?

2. Debug it the old-fashioned way. Print stuff to the screen or a file that gives information about where you're at, what conditions are true, contents of variables, etc.

3. Find someone who knows Java at school or work who can help you dig into it more.

 

I recommend option 1. Learning how to use a debugger will show you EXACTLY what is going on and is an invaluable skill. So many times I've helped co-workers just by setting a break point and stepping through the code. You can inspect variables and watch line by line what is happening (among other cool things).

 

- Eck



#15 dmatter   Crossbones+   -  Reputation: 3297

Like
1Likes
Like

Posted 04 December 2013 - 08:51 AM

1. Download an IDE with a debugger instead of using Notepad++. This is what I recommend, though I can't point you to what you should use. Perhaps Eclipse?

 

Eclipse is a good IDE for Java (I use it). So is NetBeans and IntelliJ IDEA.



#16 Eck   Crossbones+   -  Reputation: 3347

Like
0Likes
Like

Posted 04 December 2013 - 08:58 AM

Also what is happening specifically? Is it returning nothing or never returning? Those are two very different problems. :)

 

If it's returning nothing, I suspect the line that is failing is still your ground.Contains(point) logic. Using my option 2, you could output the count of nodes your List<Node> adj, at the end of your getAdjacentNode() function right before you return. If you see 0's it could mean a few things.

ground could be empty? Maybe you never filled your map. :)

ground.Contains is not returning true when you think it should.

 

I don't see where you've defined ground or populated it. Is it a global variable? Make sure you've actually loaded your map.

 

If it's never returning, the problem is probably related to always newing up nodes instead of keeping up with visited nodes like I and dmatter suggested. With a breadth first search, you will find a solution if one exists. If one doesn't exist, you will get stuck in an infinite loop as your pathfinder keeps reexploring all the nodes.

 

- Eck



#17 lavenderwong   Members   -  Reputation: 106

Like
0Likes
Like

Posted 05 December 2013 - 12:14 AM

After getting a debugger, I found several null point exception n I had solved them.

However, my program is stuck and respond abnormally slow. I checked that my bfs problem, may be the loop doesn't end in pathFinding_BFS. But i get no clue to it.


Edited by lavenderwong, 05 December 2013 - 09:37 AM.


#18 lavenderwong   Members   -  Reputation: 106

Like
0Likes
Like

Posted 05 December 2013 - 09:59 AM

is it possible that if there are no feasible path between the starting point and exit, the loop will keep running?

 

how to know if there is no feasible path?



#19 dmatter   Crossbones+   -  Reputation: 3297

Like
0Likes
Like

Posted 05 December 2013 - 10:07 AM

is it possible that if there are no feasible path between the starting point and exit, the loop will keep running?

Yes, that's exactly what would happen. To quote Eck...
 

If it's never returning, the problem is probably related to always newing up nodes instead of keeping up with visited nodes like I and dmatter suggested. With a breadth first search, you will find a solution if one exists. If one doesn't exist, you will get stuck in an infinite loop as your pathfinder keeps reexploring all the nodes.


That's what I was talking about here (along with suggesting a possible solution)...
 

I guess it is now getting stuck in an infinite loop because getAdjacentNode always constructs new instances of Node so they will always have their marked flag set to false - you will never get a Node returned by getAdjacentNode with a marked flag of true. This kind of screws up your check that prevents getting stuck in cycles: if (!n.isMarked()).
 
You may have to reconsider the way you track previously explored nodes. For example maybe you can keep a collection of previously explored nodes (or points), every time you encounter one add it to the collection, when you want to see if you've encountered a node before then you just look in that collection. I.e. A node (or point) either is or is not in the collection, which acts as your boolean flag.


To answer your other question...
 

how to know if there is no feasible path?


Once your fix the above issue with re-exploring nodes. Then you'll be able to detect a no-path case because your queue will empty and you won't have discovered the 'end' node; if that happens you know there is no path.

#20 lavenderwong   Members   -  Reputation: 106

Like
0Likes
Like

Posted 05 December 2013 - 10:38 AM

Sorry, i couldn't get your meaning at that time. and i think if the ground doesn't contain the up, down, left or right node, then the node will not be created?

 

anyway, i had debugged my pathFinding_BFS function line by  line, other part seems ok, but if i include the line queue.add(n), the program will stuck and not responding (seems like an infinite loop) but it seems to me that it's not about infinite loop... it's about adding the node n in the queue. (if i remove queue.add(n), my program becomes normal). i just have no clue why the queue.add(n) will hang my program... as it's just an addition of node action.

 

my latest code

private boolean pathFinding_BFS(Node start, Node end){
		LinkedList<Node> queue = new LinkedList<Node>();
		queue.add(start);
		start.setMarked();
		while (!queue.isEmpty()){
			Node temp = (Node)queue.poll();
			System.out.println("first node:" + temp.getPointInPath().getX() + " y " + temp.getPointInPath().getY());
			if (temp.equals(end)){
				//temp.setPrevNodeInPath(temp);
				end.setPrevNodeInPath(temp.getPrevNodeInPath());
				return true;
			}else{
				//for (Node n : temp.getAdjacentNode()){	
				for (int i=0; i<temp.getAdjacentNode().size();i++){
					Node n = new Node(temp.getAdjacentNode().get(i).getPointInPath());
					System.out.println("in node:" + n.getPointInPath().getX() + " y " + n.getPointInPath().getY());
					if (!n.isMarked()){
						n.setMarked();
						n.setPrevNodeInPath(temp);
						queue.add(n);  //problem here
					}
				}
			}
						
		}
		return false;
	}

Edited by lavenderwong, 06 December 2013 - 10:22 AM.





Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS