A* Pathfinding question

Game Mechanics Artificial Intelligence
#1

Hi,

I’ve been working on this for several hours now and it is time to head to bed. I decided to post up my current attempt at writing A* where the cost is 0 for all nodes.

Currently, when I run this, the solution (which is the open list), contains every single node that the algorithm looked at. I am going by this description of the algorithm:
http://ai-depot.com/Tutorial/PathFinding.html
Though either I am not understanding this properly or that example is flawed…

I know my algorithm is reaching the indicated node because it leaves a single node untouched…
So I need to know how to remove unwanted nodes from the list as I go.

Here is my code for the algorithm. If you require the entire program let me know.

The filled part tells the program to draw a filled rectangle as opposed to an outline of one.

Thanks for any assistance.


public static void pathFind(PathWindow window)
	{

		
		Node startNode = window.getColumns().get(0).getNodeList().get(0);
		int cols = window.getColumns().size();
		int rows = window.getColumns().get(0).getNodeList().size();
		Node endNode = window.getColumns().get(cols-1).getNodeList().get(rows-1);
		
		LinkedList<Node> openList = new LinkedList<Node>();
		
		openList.add(startNode);
		
		while(openList.size() > 0)
		{
			Node currentNode = openList.poll();
			
			//currentNode.setFilled(true);
			
			//If we are at the end.
			if(currentNode.equals(endNode))
			{
				//Add the current node back in since we removed it above.
				openList.add(currentNode);
				break;
			}
			
			//Successors
			
			if(currentNode.getAboveNode() != null)
			{
				if(openList.contains(currentNode.getAboveNode()) == false)
				{
					openList.add(currentNode);
					openList.add(currentNode.getAboveNode());
				}
			}
			if(currentNode.getUnderNode() != null)
			{
				if(openList.contains(currentNode.getUnderNode()) == false)
				{
					openList.add(currentNode);
					openList.add(currentNode.getUnderNode());
				}
			}
			if(currentNode.getLeftNode() != null)
			{
				if(openList.contains(currentNode.getLeftNode()) == false)
				{
					openList.add(currentNode);
					openList.add(currentNode.getLeftNode());
				}
			}
			if(currentNode.getRightNode() != null)
			{
				if(openList.contains(currentNode.getRightNode()) == false)
				{
					openList.add(currentNode);
					openList.add(currentNode.getRightNode());
				}
			}
			
		}
		
		System.out.println("openlist is:\n" + openList);
		
		//set all these nodes to filled.
		for(int i = 0;i<openList.size();i++)
		{
			openList.get(i).setFilled(true);
		}
		
		window.repaint();
}
#2

Without looking at the code; change the cost to 1.

#3

How would this change the affects? As they are all 1’s so if I am at a current node with a current cost of 10 and then all the nodes around me are cost 1, they’re all equal.

Thanks.

#4

If the cost is 0 then every path is the shortest path. For an A* search you should also keep a closed list as well so that you don’t add nodes you’ve already processed. Also out of curiosity what is the application? With edges of equal cost A* isn’t always the best option - although coding it is easy.

#5

Thanks for the reply. It’s for a game I’m making. I’m just trying to get the thing to work in any way and then I will be adding onto it. I’ll try adding the closed list.

I’ll let you know soon…

#6

Your suggestion worked and now I have basic pathfinding!

Thanks a lot.

On a side note, this turned out to be a lot easier than I was thinking it would be. I’ve put this off for over a year. It only took me about 6 hours to do (which includes reading tutorials, forums and other web pages). Thanks again for your help.

#7

Hello,

I have another question regarding this.

Given a map with a nice portion of walls so the path is a bit complex and all the costs of the nodes are 1, will A* come up with the same path every time (assume nothing changes except you want to calc another path)?

I’m trying to decide if I can afford the server to send the path to all the clients or have the clients do it themselves. It’s really a bandwidth question.

Thanks!

#8

If you are at the same source/dest then the paths will be the same unless the order of the lists change. You would probably want the clients to calculate the path and not the server, there’s just no need to do it that way.

#9

This is what I’m thinking…

I can have the client calculate the path and send it to the server. The server will check it to ensure it is not fake (going through walls, etc) and then tell all the other clients to generate the path. Then the server will tell the indicated character to move on the server. I have the server move all of the paths as well so that the clients can not do bogus things if they get out of synced. I send an update every 10 seconds. This sounds like a reasonable approach that won’t suck up the CPU of the server but keep things synced as well as secure to a good extent.

By the way, thanks for replying - you’ve been most helpful :slight_smile:

#10

Using A* with a path cost of 0 can be used as a “flood fill” algorithm to get areas instead of paths. If you want the forest, take any node and run a search where forest nodes cost 0 and all others cost 1. All 0 nodes will go in the list and then you have a list of all connected forest nodes.

General A* applications like this are described in the AI Game Programming Books. You can do a lot of stuff with A*. But for finding a single path, you’ll always need a cost. Otherwise the heuristic wont work which aims to keep the search space limited.

-JAW