• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
lavenderwong

Pathfinding problem

19 posts in this topic

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

0

Share this post


Link to post
Share on other sites

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
1

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.

0

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?

0

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

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 [tt]if (temp.equals(end))[/tt] works correctly. And you'll need one in your Point class, so that [tt]if (ground.contains(up))[/tt] 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
1

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
0

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 [tt]List[/tt] (and its derivatives, e.g. [tt]ArrayList[/tt] and [tt]LinkedList[/tt]) only use the [tt]equals[/tt] method but there are other collection classes, like a [tt]Set[/tt], which will also need the [tt]hashCode()[/tt] method to be overriden in addition to [tt]equals()[/tt].
 

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 [tt]Point[/tt] 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 [tt]Point[/tt] 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
0

Share this post


Link to post
Share on other sites

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
0

Share this post


Link to post
Share on other sites

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.

0

Share this post


Link to post
Share on other sites

I guess it is now getting stuck in an infinite loop because [tt]getAdjacentNode[/tt] always constructs new instances of [tt]Node[/tt] so they will always have their [tt]marked[/tt] flag set to false - you will never get a [tt]Node[/tt] returned by [tt]getAdjacentNode[/tt] with a [tt]marked[/tt] flag of true. This kind of screws up your check that prevents getting stuck in cycles: [tt]if (!n.isMarked()).[/tt]
 
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
0

Share this post


Link to post
Share on other sites

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

1

Share this post


Link to post
Share on other sites

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.

1

Share this post


Link to post
Share on other sites

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

0

Share this post


Link to post
Share on other sites

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
0

Share this post


Link to post
Share on other sites

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?

0

Share this post


Link to post
Share on other sites

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 [tt]getAdjacentNode[/tt] always constructs new instances of [tt]Node[/tt] so they will always have their [tt]marked[/tt] flag set to false - you will never get a [tt]Node[/tt] returned by [tt]getAdjacentNode[/tt] with a [tt]marked[/tt] flag of true. This kind of screws up your check that prevents getting stuck in cycles: [tt]if (!n.isMarked()).[/tt]
 
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.
0

Share this post


Link to post
Share on other sites

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
0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0