A* Pathfinding Libgdx?

tommohawkaction · July 1, 2015, 6:49pm

Okay I posted not long ago about path finding which i have finally had a look at, I understand how it works but cannot implement it into code
Can someone advice me on what i need to do next please

	private ArrayList<Node> openList;
	private ArrayList<Node> closedList;
	
	public APathfind() {
		openList = new ArrayList<Node>();
		closedList = new ArrayList<Node>();
	}
	
	public void calculatePath(Vector2 start,Vector2 target,MasterTile[][] map){
		openList.clear();
		closedList.clear();
		
		
		Node startNode = new Node();
		openList.add(startNode);
		
		
	}

Node

public float h; // Distance from a node to the target node (Manhatten)
	public float g; // Movement cost from node to another node
	public float f; // h+g
	
	public Node parent;
	
	public Node(float h,float g,float f) {
		this.h = h;
		this.g = g;
		this.f = f;
	}
	public Node() {
		this(0,0,0);
	}

chrislo27 · July 1, 2015, 7:01pm

Putting forth your code and asking us to try to complete most of it doesn’t help you learn. Have you tried to implement it at all?

This article is really helpful. It has the source code and a very thorough breakdown of how everything works. Try using that article first and see if you can try to implement some more things yourself. I’m not asking you to solve it yourself, if you’re really stuck then ask us and we’ll deliver.

tommohawkaction · July 1, 2015, 7:32pm

Thanks or replying, I have looked at the link and have attempted a bit more
I am mainly following this tut http://www.policyalmanac.org/games/aStarTutorial.htm which makes a lot of sense but i am having trouble with implementing it

private ArrayList<Node> openList;
	private ArrayList<Node> closedList;
	private TileMap map;
	private Node[][] nodes;
	
	public APathfind(TileMap map) {
		openList = new ArrayList<Node>();
		closedList = new ArrayList<Node>();
		this.map = map;
		nodes = new Node[map.getWidth()][map.getHeight()];
	}
	
	public void calculatePath(int startTileX,int startTileY,int targetTileX,int targetTileY){
		openList.clear();
		closedList.clear();
		
		Node startNode = new Node();
		nodes[startTileX][startTileY] = startNode;
		
		int currentX = startTileX;
		int currentY = startTileY;
		
		openList.add(startNode);
		while ((currentX != targetTileX && currentY != targetTileY) || closedList.contains(nodes[targetTileX][targetTileY])){
			
		}
	}

CopyableCougar4 · July 1, 2015, 7:42pm

Then how much sense is it really making?

tommohawkaction · July 1, 2015, 7:51pm

I understand the concept… I get to the point where i am trying to calculate the f,g,h and i am not completely sure how i am meant to do this… or if i am even doing it correctly

		while ((currentX != targetTileX && currentY != targetTileY) || closedList.contains(nodes[targetTileX][targetTileY])){
			// Top
			Node top = new Node();
		}

BurntPizza · July 1, 2015, 8:00pm

I don’t know what specifically what will do it for you, but I can link my favorite A* walkthrough: http://www.redblobgames.com/pathfinding/a-star/introduction.html
It starts with BFS and goes through the evolution into A*, including where f g and h come from.

tommohawkaction · July 1, 2015, 8:05pm

I found that one really confusing but i really liked the interactions

Am i doing this right??

		while ((currentX != targetTileX && currentY != targetTileY) || closedList.contains(nodes[targetTileX][targetTileY])){
			// Top
			// H (From current to target)
			float hx = Math.abs(targetTileX - currentX);
			float hy = Math.abs(targetTileY - (currentY+1));
			float h = hx + hy;
			
			// G (Movement Cost)
			float g = parent.g + 10;
			
			// F (G + H)
			float f = g+h;
			
			Node top = new Node(h,g,f);
		}

tommohawkaction · July 1, 2015, 8:50pm

public void calculatePath(int startTileX,int startTileY,int targetTileX,int targetTileY){
		openList.clear();
		closedList.clear();
		
		Node parent = new Node();
		nodes[startTileX][startTileY] = parent;
		
		int currentX = startTileX;
		int currentY = startTileY;
		
		
		while ((currentX != targetTileX && currentY != targetTileY) || closedList.contains(nodes[targetTileX][targetTileY])){
			Node top = calculateNode(currentX, currentY+1, targetTileX, targetTileY, parent,10);
			Node bottom = calculateNode(currentX, currentY-1, targetTileX, targetTileY, parent,10);
			Node left = calculateNode(currentX-1, currentY, targetTileX, targetTileY, parent,10);
			Node right = calculateNode(currentX+1, currentY, targetTileX, targetTileY, parent,10);
			
			Node topRight = calculateNode(currentX+1, currentY+1, targetTileX, targetTileY, parent,14);
			Node topLeft = calculateNode(currentX-1, currentY+1, targetTileX, targetTileY, parent,14);
			Node bottomRight = calculateNode(currentX+1, currentY-1, targetTileX, targetTileY, parent,14);
			Node bottomLeft = calculateNode(currentX-1, currentY-1, targetTileX, targetTileY, parent,14);
			
			MasterTile[][] mapTiles = map.getMapData();
			// TODO make a method in Collision Engine which will return if the tile is soild or not
			
			// Adjacent  tiles
			if(!CollisionTileEngine.checkCollisionTile(currentX, currentY+1, mapTiles)){
				openList.add(top);
			}
			if(!CollisionTileEngine.checkCollisionTile(currentX, currentY-1, mapTiles)){
				openList.add(bottom);
			}
			if(!CollisionTileEngine.checkCollisionTile(currentX-1, currentY, mapTiles)){
				openList.add(left);
			}
			if(!CollisionTileEngine.checkCollisionTile(currentX+1, currentY, mapTiles)){
				openList.add(right);
			}

			
			if(!CollisionTileEngine.checkCollisionTile(currentX+1, currentY+1, mapTiles)){
				openList.add(topRight);
			}
			if(!CollisionTileEngine.checkCollisionTile(currentX-1, currentY+1, mapTiles)){
				openList.add(topLeft);
			}
			if(!CollisionTileEngine.checkCollisionTile(currentX+1, currentY-1, mapTiles)){
				openList.add(bottomRight);
			}
			if(!CollisionTileEngine.checkCollisionTile(currentX-1, currentY-1, mapTiles)){
				openList.add(bottomLeft);
			}
			
			openList.remove(parent);
			closedList.add(parent);
			
			
			
		}
		
			
	}
	
	private Node calculateNode(int currentX,int currentY,int targetTileX,int targetTileY,Node parent,int moveCost){
		// Top
		// H (From current to target)
		float hx = Math.abs(targetTileX - currentX);
		float hy = Math.abs(targetTileY - (currentY+moveCost));
		float h = hx + hy;
		
		// G (Movement Cost)
		float g = parent.g;
		
		// F (G + H)
		float f = g+h;
		Node node = new Node(h,g,f,parent);
		return node;
	}

Am i doing this right??

seismic · July 2, 2015, 7:32am

I think nowadays LibGDX has its own A* pathfinding implementation somewhere in Gdx-Ai, so you don’t have to do it yourself.

tommohawkaction · July 2, 2015, 8:04am

What am i doing wrong?

private ArrayList<Node> openList;
	private ArrayList<Node> closedList;
	private TileMap map;
	private Node[][] nodes;
	private Node finalResult;

	public APathfind(TileMap map) {
		openList = new ArrayList<Node>();
		closedList = new ArrayList<Node>();
		this.map = map;
		nodes = new Node[map.getWidth()][map.getHeight()];
	}

	public void calculatePath(int startTileX, int startTileY, int targetTileX, int targetTileY) {
		openList.clear();
		closedList.clear();

		Node parent = new Node(startTileX,startTileY);
		nodes[startTileX][startTileY] = parent;
		openList.add(parent);

		int currentX = startTileX;
		int currentY = startTileY;

		while ((currentX != targetTileX && currentY != targetTileY) || closedList.contains(nodes[targetTileX][targetTileY])) {
			Node top = calculateNode(currentX, currentY + 1, targetTileX, targetTileY, parent, 10);
			Node bottom = calculateNode(currentX, currentY - 1, targetTileX, targetTileY, parent, 10);
			Node left = calculateNode(currentX - 1, currentY, targetTileX, targetTileY, parent, 10);
			Node right = calculateNode(currentX + 1, currentY, targetTileX, targetTileY, parent, 10);

			Node topRight = calculateNode(currentX + 1, currentY + 1, targetTileX, targetTileY, parent, 14);
			Node topLeft = calculateNode(currentX - 1, currentY + 1, targetTileX, targetTileY, parent, 14);
			Node bottomRight = calculateNode(currentX + 1, currentY - 1, targetTileX, targetTileY, parent, 14);
			Node bottomLeft = calculateNode(currentX - 1, currentY - 1, targetTileX, targetTileY, parent, 14);

			MasterTile[][] mapTiles = map.getMapData();

			// Adjacent tiles
			if (!CollisionTileEngine.checkCollisionTile(currentX, currentY + 1, mapTiles)) {
				checkNodeOpenList(top, parent);
			}
			if (!CollisionTileEngine.checkCollisionTile(currentX, currentY - 1, mapTiles)) {
				checkNodeOpenList(bottom, parent);
			}
			if (!CollisionTileEngine.checkCollisionTile(currentX - 1, currentY, mapTiles)) {
				checkNodeOpenList(left, parent);
			}
			if (!CollisionTileEngine.checkCollisionTile(currentX + 1, currentY, mapTiles)) {
				checkNodeOpenList(right, parent);
			}

			if (!CollisionTileEngine.checkCollisionTile(currentX + 1, currentY + 1, mapTiles)) {
				checkNodeOpenList(topRight, parent);
			}
			if (!CollisionTileEngine.checkCollisionTile(currentX - 1, currentY + 1, mapTiles)) {
				checkNodeOpenList(topLeft, parent);
			}
			if (!CollisionTileEngine.checkCollisionTile(currentX + 1, currentY - 1, mapTiles)) {
				checkNodeOpenList(bottomRight, parent);
			}
			if (!CollisionTileEngine.checkCollisionTile(currentX - 1, currentY - 1, mapTiles)) {
				checkNodeOpenList(bottomLeft, parent);
			}


			
			// Checks for smaller F
			float maxF = Float.MAX_VALUE;
			int index = 0;
			for (int i = 0; i < openList.size(); i++) {
				Node currentNode = openList.get(i);
				if(currentNode.f < maxF && !closedList.equals(currentNode)){
					maxF = currentNode.f;
					index = i;
				}
			}
			parent = openList.get(index);
			currentX = parent.currentX;
			currentY = parent.currentY;

			openList.remove(parent);
			closedList.add(parent);
		}
		finalResult = parent;

	}
	public Node getFinalResult() {
		return finalResult;
	}
	private void checkNodeOpenList(Node n,Node parent){
		for(int i = 0;i < openList.size();i++){
			Node current = openList.get(i);
			if(current.currentX == n.currentX && current.currentY == n.currentY){
				if(n.g < current.g){
					System.out.println("bestter path");
					current.parent = n.parent;
					return;
				}
				return;
			}
		}
		openList.add(n);
	}

	private Node calculateNode(int currentX, int currentY, int targetTileX, int targetTileY, Node parent, int moveCost) {
		// Top
		// H (From current to target)
		float hx = Math.abs(targetTileX - currentX);
		float hy = Math.abs(targetTileY - (currentY + moveCost));
		float h = hx + hy;

		// G (Movement Cost)
		float g = parent.g;

		// F (G + H)
		float f = g + h;
		Node node = new Node(h, g, f, parent,currentX,currentY);
		return node;
	}

Jesse · July 2, 2015, 8:49am

It can be kind of hard to spot errors in this kind of code just from reading through it online. As has probably been mentioned elsewhere, you’d probably have better luck digging into it with debugging tools to figure out what’s going on. Also, I don’t see an indication in your most recent post of where the path is supposed to begin and end, and in absence of that it’s difficult to diagnose the problem based on the screenshot. Maybe the path start and end are correct though and it’s only the ‘zigzag’ behavior at the bottom of the screenshot that’s wrong.

In any case, I skimmed the code and am wondering about your ‘calculate node’ function. Here:

      float hx = Math.abs(targetTileX - currentX);
      float hy = Math.abs(targetTileY - (currentY + moveCost));
      float h = hx + hy;

Is there a particular reason you’re adding the movement cost to the current y value? Maybe I’m missing something (and apologies if so), but that doesn’t seem to be correct. I’d expect the computation of ‘h’ to look more like this:

      float hx = Math.abs(targetTileX - currentX);
      float hy = Math.abs(targetTileY - currentY);
      float h = (hx + hy) * 10;

I think the tutorial suggests this as well.

You might also double-check that your ‘g’ values are being computed correctly - I’m not seeing right off how the ‘g’ values are being tracked. (Stepping through in the debugger with a simple straight-line path would be a good idea here - if it’s working correctly, the ‘g’ values for the nodes in the path should be successive nonnegative integer multiples of 10.)

Again, I only skimmed the code, and I haven’t implemented this algorithm in a while, so it’s possible that everything in this post is wrong (well, the advice about using your debugging tools is probably ok :)).

tommohawkaction · July 2, 2015, 10:33am

Thanks for pointing it out

		// Top
		// H (From current to target)
		float hx = Math.abs(targetTileX - currentX);
		float hy = Math.abs(targetTileY - currentY);
		float h = (hx + hy) * moveCost;

		// G (Movement Cost)
		float g = (float) (parent.g - Math.sqrt((currentX * currentX) + (currentY * currentY)));

The result was the same though

Jesse · July 2, 2015, 10:53am

Is this:

float g = (float) (parent.g - Math.sqrt((currentX * currentX) + (currentY * currentY)));

Based on the tutorial you’re following? It still doesn’t look right to me. For one thing, it seems the ‘g’ cost would get smaller with each successive node. Also, the distance from the origin to the current position isn’t really relevant here. And, I don’t see the move cost (10 or 14) incorporated anywhere.

Anyway, maybe the code could use another look. The best thing to do would probably be to step through it in the debugger, but at the very least, you could print out the ‘g’ cost at each step, just to make sure you’re getting sensible values (e.g. no negative numbers, etc.).

tommohawkaction · July 2, 2015, 12:22pm

Jesse:

Is this:
float g = (float) (parent.g - Math.sqrt((currentX * currentX) + (currentY * currentY)));
Based on the tutorial you’re following? It still doesn’t look right to me. For one thing, it seems the ‘g’ cost would get smaller with each successive node. Also, the distance from the origin to the current position isn’t really relevant here. And, I don’t see the move cost (10 or 14) incorporated anywhere.

Anyway, maybe the code could use another look. The best thing to do would probably be to step through it in the debugger, but at the very least, you could print out the ‘g’ cost at each step, just to make sure you’re getting sensible values (e.g. no negative numbers, etc.).

I have re wrote this code, and followed the tutorial extremely slow but nothing works?
I am following this tutorial

http://www.policyalmanac.org/games/aStarTutorial.htm

package com.hawk.linear.engine.path;

import java.util.ArrayList;

import com.hawk.linear.engine.collisioin.CollisionTileEngine;
import com.hawk.linear.engine.map.TileMap;

public class APathfind {

	private ArrayList<Node> openList;
	private ArrayList<Node> closedList;
	private TileMap map;
	private Node finalResult;

	public APathfind(TileMap map) {
		openList = new ArrayList<Node>();
		closedList = new ArrayList<Node>();
		this.map = map;
	}

	public void calculatePath(int startTileX, int startTileY, int targetTileX, int targetTileY) {
		openList.clear();
		closedList.clear();

		int currentX = startTileX;
		int currentY = startTileY;

		Node startNode = new Node(currentX, currentY);
		Node parent = startNode;
		openList.add(startNode);

		while (currentX != targetTileX && currentY != targetTileY) {

			Node top = calculateNode(currentX, currentY + 1, targetTileX, targetTileY, parent, 10);
			Node bot = calculateNode(currentX, currentY - 1, targetTileX, targetTileY, parent, 10);
			Node left = calculateNode(currentX - 1, currentY, targetTileX, targetTileY, parent, 10);
			Node right = calculateNode(currentX + 1, currentY, targetTileX, targetTileY, parent, 10);

			Node topLeft = calculateNode(currentX - 1, currentY + 1, targetTileX, targetTileY, parent, 14);
			Node topRight = calculateNode(currentX + 1, currentY + 1, targetTileX, targetTileY, parent, 14);
			Node botLeft = calculateNode(currentX - 1, currentY - 1, targetTileX, targetTileY, parent, 14);
			Node botRight = calculateNode(currentX + 1, currentY - 1, targetTileX, targetTileY, parent, 14);

			if (!CollisionTileEngine.checkCollisionTile(top.currentX, top.currentY, map.getMapData())) {
				openList.add(top);
			}
			if (!CollisionTileEngine.checkCollisionTile(bot.currentX, bot.currentY, map.getMapData())) {
				openList.add(bot);
			}
			if (!CollisionTileEngine.checkCollisionTile(left.currentX, left.currentY, map.getMapData())) {
				openList.add(left);
			}
			if (!CollisionTileEngine.checkCollisionTile(right.currentX, right.currentY, map.getMapData())) {
				openList.add(right);
			}

			if (!CollisionTileEngine.checkCollisionTile(topLeft.currentX, topLeft.currentY, map.getMapData())) {
				openList.add(topLeft);
			}
			if (!CollisionTileEngine.checkCollisionTile(topRight.currentX, topRight.currentY, map.getMapData())) {
				openList.add(topRight);
			}
			if (!CollisionTileEngine.checkCollisionTile(botLeft.currentX, botLeft.currentY, map.getMapData())) {
				openList.add(botLeft);
			}
			if (!CollisionTileEngine.checkCollisionTile(botRight.currentX, botRight.currentY, map.getMapData())) {
				openList.add(botRight);
			}
			if (openList.contains(startNode)) {
				openList.remove(startNode);
				closedList.add(startNode);
			}

			// Checking smaller F cost
			float maxF = Float.MAX_VALUE;
			Node checkNode = null;
			for (Node n : openList) {
				if (n.f < maxF) {
					maxF = n.f;
					checkNode = n;
				}
			}
			// Set new parent
			openList.remove(checkNode);
			closedList.add(checkNode);

			parent = checkNode;
			currentX = checkNode.currentX;
			currentY = checkNode.currentY;

			checkOpenListNode(top, parent);
			checkOpenListNode(bot, parent);
			checkOpenListNode(left, parent);
			checkOpenListNode(right, parent);

			checkOpenListNode(topLeft, parent);
			checkOpenListNode(topRight, parent);
			checkOpenListNode(botLeft, parent);
			checkOpenListNode(botRight, parent);
		}
		
		for(Node node : openList){
			if(node.currentX == currentX && node.currentY == currentY){
				finalResult = node;
				return;
			}
		}
	}

	public Node getFinalResult() {
		return finalResult;
	}

	private void checkOpenListNode(Node node, Node parent) {
		for (Node n : openList) {
			if (n.currentX == node.currentX && n.currentY == node.currentY) {
				if (node.g < n.g) {
					n.g = node.g;
					n.f = node.f;
					n.parent = parent;
				}
			}
		}
	}

	private Node calculateNode(int currentX, int currentY, int targetTileX, int targetTileY, Node parent, int moveCost) {
		// H (From current to target)
		float hx = Math.abs(targetTileX - currentX);
		float hy = Math.abs(targetTileY - currentY);
		float h = (hx + hy);

		// G (Movement Cost)
		float g = (float) Math.sqrt((currentX * currentX) + (currentY * currentY));

		// F (G + H)
		float f = g + h;
		Node node = new Node(h,g,f, parent, currentX, currentY);
		return node;
	}
}

Jesse · July 2, 2015, 6:58pm

‘g’ still looks wrong. It still seems to have the same problems it did before (move cost not incorporated, and uses distance from origin to current position, which is irrelevant), and now it doesn’t appear to factor in the parent ‘g’ at all.

Does the tutorial explain how to compute ‘g’? Can you tell us where you’re getting your current code? Is that from the tutorial? Or maybe you could try explaining in words what you think ‘g’ is supposed to represent - that might help illuminate the problem.

A* (and graph algorithms in general) can be tricky to implement. Speaking for myself, I’ve implemented A* more than once, but if I had to implement it right now I’d still have to do some review and do everything very carefully in order to get it right. Unfortunately, getting close to ‘right’ generally won’t work - if even one little thing is wrong (such as how ‘g’ is computed), it’s unlikely to work. Also, because there are so many more ways to get it wrong than to get it right, trial and error probably isn’t a particularly effective way to proceed.

Also, if I may ask, what development tools are you using? Have you tried setting up a simple test case (e.g. a short, unobstructed straight-line path) and stepping through the code in the debugger?

tommohawkaction · July 2, 2015, 7:13pm

Jesse:

‘g’ still looks wrong. It still seems to have the same problems it did before (move cost not incorporated, and uses distance from origin to current position, which is irrelevant), and now it doesn’t appear to factor in the parent ‘g’ at all.

Does the tutorial explain how to compute ‘g’? Can you tell us where you’re getting your current code? Is that from the tutorial? Or maybe you could try explaining in words what you think ‘g’ is supposed to represent - that might help illuminate the problem.

A* (and graph algorithms in general) can be tricky to implement. Speaking for myself, I’ve implemented A* more than once, but if I had to implement it right now I’d still have to do some review and do everything very carefully in order to get it right. Unfortunately, getting close to ‘right’ generally won’t work - if even one little thing is wrong (such as how ‘g’ is computed), it’s unlikely to work. Also, because there are so many more ways to get it wrong than to get it right, trial and error probably isn’t a particularly effective way to proceed.

Also, if I may ask, what development tools are you using? Have you tried setting up a simple test case (e.g. a short, unobstructed straight-line path) and stepping through the code in the debugger?

Thanks Jesse for replying, I am using Eclipse, I am not sure what you mean?

I have just fixed the issue I think??

	private Node calculateNode(int currentX, int currentY, int targetTileX, int targetTileY, Node parent, int moveCost) {
		// H (From current to target)
		float hx = Math.abs(targetTileX - currentX);
		float hy = Math.abs(targetTileY - currentY);
		float h = (hx + hy);

		// G (Movement Cost)
		float g = moveCost;

		// F (G + H)
		float f = g + h;
		Node node = new Node(h,g,f, parent, currentX, currentY);
		return node;
	}

For tiles which are top, bottom,left,right of the parent is this has a movement cost of 10
and the diagonal tiles have a movement cost of 14

No result
I am not sure what i am doing wrong… I will rewrite it tomorrow after work…

Jesse · July 2, 2015, 7:24pm

Unless it’s factored in somewhere else, I think ‘g’ is still wrong because it doesn’t incorporate the parent cost. (Either that or I’m misremembering how to compute ‘g’.)

Do you know how to use the debugger in Eclipse? (It’s ok if the answer is no by the way I’m just trying to get a better picture of the situation.)

tommohawkaction · July 2, 2015, 7:27pm

Well yes i am working the G wrong just looked it up "G = the movement cost to move from the starting point A to a given square on the grid, following the path generated to get there. "
Also no i do not know how to use the debugger

tommohawkaction · July 2, 2015, 7:32pm

I have changed it but now when i run it crashes…

private Node calculateNode(Node start,int currentX, int currentY, int targetTileX, int targetTileY, Node parent, int moveCost) {
		// H (From current to target)
		float hx = Math.abs(targetTileX - currentX);
		float hy = Math.abs(targetTileY - currentY);
		float h = (hx + hy);

		// G (Movement Cost)
		float gx = Math.abs(start.currentX - currentX);
		float gy = Math.abs(start.currentY - currentY);
		float g = (gx+gy);

		// F (G + H)
		float f = g + h;
		Node node = new Node(h,g,f, parent, currentX, currentY);
		return node;
	}

BurntPizza · July 2, 2015, 7:47pm

From your linked tut:

[quote]Since we are calculating the G cost along a specific path to a given square, the way to figure out the G cost of that square is to take the G cost of its parent, and then add 10 or 14 depending on whether it is diagonal or orthogonal (non-diagonal) from that parent square.
[/quote]

float g = parent.g + movementCost(parent, currentX, currentY);

Where movementCost() is the cost to get from parent to (currentX, currentY). (the 10-or-14)

This definition of G says: “the cost to get from the starting point to where we are now is the cost of all previous steps in the path (the parent.g) plus the cost of this one last step.”
Each node builds onto the path, so G is a running tally of how costly the path has gotten.