Advertisement Jump to content
Sign in to follow this  
lavenderwong

Pathfinding problem

This topic is 1872 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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!!

Share this post


Link to post
Share on other sites
Advertisement

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

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

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?

Share this post


Link to post
Share on other sites

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;
		}
	}

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!