Back to General and Gameplay Programming

Pathfinding problem

General and Gameplay Programming Programming

Started by lavenderwong December 03, 2013 05:49 AM

18 comments, last by lavenderwong 10 years, 4 months ago

4,872

December 04, 2013 11: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."

David Gill :: GitHub :: twitter .

lavenderwong

106

Author

December 04, 2013 11: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.

dmatter

4,872

December 04, 2013 02:30 PM

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.

David Gill :: GitHub :: twitter .

Eck

7,699

December 04, 2013 02:43 PM

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

EckTech Games - Games and Unity Assets I'm working on
Still Flying - My GameDev journal
The Shilwulf Dynasty - Campaign notes for my Rogue Trader RPG

dmatter

4,872

December 04, 2013 02:51 PM

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.

David Gill :: GitHub :: twitter .

Eck

7,699

December 04, 2013 02:58 PM

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

EckTech Games - Games and Unity Assets I'm working on
Still Flying - My GameDev journal
The Shilwulf Dynasty - Campaign notes for my Rogue Trader RPG

lavenderwong

106

Author

December 05, 2013 06: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.

lavenderwong

106

Author

December 05, 2013 03:59 PM

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?

dmatter

4,872

December 05, 2013 04:07 PM

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.

David Gill :: GitHub :: twitter .

lavenderwong

106

Author

December 05, 2013 04:38 PM

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

Pathfinding problem

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Pathfinding problem

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines