A* Pathfinding seems to give up before target

Game Mechanics Artificial Intelligence
#21

I have a guess as to my problem:

When I determine the lowest step, top gets precidence so maybe the F values are the same and those get priority? Just a thought. If so, please help me fix it.

// Determine the lowest step
			double min = min(topleftF, topF, toprightF, leftF, rightF, bottomleftF, bottomF, bottomrightF);
			if(check(min, topleftF) && available(topleft)){
				active = topleft;
			} 
			else if(check(min, topF) && available(top)){
				active = top;
			}
			else if(check(min, toprightF) && available(topright)){
				active = topright;
			}
			else if(check(min, leftF) && available(left)){
				active = left;
			}
			else if(check(min, rightF) && available(right)){
				active = right;
			}
			else if(check(min, bottomleftF) && available(bottomleft)){
				active = bottomleft;
			}
			else if(check(min, bottomF) && available(bottom)){
				active = bottom;
			}
			else if(check(min, bottomrightF) && available(bottomright)){
				active = bottomright;
			}

CopyableCougar4

#22

It’s definitely the above section of code. When I made all those else if statements if statements, the path filled the bottom of the screen. I need a way to choose the next tile unbiased towards a given order. :point:

CopyableCougar4

#23

I have tweaked the above mentioned code and I am really close to a solution :slight_smile: I just need to find out why it doesn’t just go diagonal rather than not going diagonal.

Pathfinder class

public class Pathfinder {
	
	private TileMap map;
	
	public Pathfinder(TileMap map){
		this.map = map;
	}
	
	private ArrayList<ITile> open = new ArrayList<ITile>();
	private ArrayList<ITile> closed = new ArrayList<ITile>();
	private ArrayList<ITile> possible = new ArrayList<ITile>();
	
	public Path getPath(int tx, int ty, int sx, int sy){
		long before = System.currentTimeMillis();
		int ax = sx, ay = sy; // active tiles
		Path path = new Path();
		ITile active = map.getTile(ax, ay);
		open.add(active);
		path.addTile(active);
		while(!(ax == tx && ay == ty)){	// continue until the path has been completed or there are no possible tiles left
			active = path.last();
			// Get the surrounding tiles
			ITile topleft = map.getTile(ax - 1, ay - 1);
			if(topleft != null) topleft.setParent(active);
			ITile top = map.getTile(ax, ay - 1);
			if(top != null) top.setParent(active);
			ITile topright = map.getTile(ax + 1, ay - 1);
			if(topright != null) topright.setParent(active);
			ITile left = map.getTile(ax - 1, ay);
			if(left != null) left.setParent(active);
			ITile right = map.getTile(ax + 1, ay);
			if(right != null) right.setParent(active);
			ITile bottomleft = map.getTile(ax - 1, ay + 1);
			if(bottomleft != null) bottomleft.setParent(active);
			ITile bottom = map.getTile(ax, ay + 1);
			if(bottom != null) bottom.setParent(active);
			ITile bottomright = map.getTile(ax + 1, ay + 1);
			if(bottomright != null) bottomright.setParent(active);
			// Swap out the tiles
			if(topleft != null && topleft.weight < 100 && available(topleft)){
				open.add(topleft);
			}
			if(top != null && top.weight < 100 && good(top)){
				open.add(top);
			}
			if(topright != null && topright.weight < 100 && good(topright)){
				open.add(topright);
			}
			if(left != null && left.weight < 100 && good(left)){
				open.add(left);
			}
			if(right != null && right.weight < 100 && good(right)){
				open.add(right);
			}
			if(bottomleft != null && bottomleft.weight < 100 && good(bottomleft)){
				open.add(bottomleft);
			}
			if(bottom != null && bottom.weight < 100 && good(bottom)){
				open.add(bottom);
			}
			if(bottomright != null && bottomright.weight < 100 && good(bottomright)){
				open.add(bottomright);
			}
			// Get their values
			double topleftF = F(sx, sy, tx, ty, ax, ay);
			double topF = F(sx, sy, tx, ty, ax, ay);
			double toprightF = F(sx, sy, tx, ty, ax, ay);
			double leftF = F(sx, sy, tx, ty, ax, ay);
			double rightF = F(sx, sy, tx, ty, ax, ay);
			double bottomleftF = F(sx, sy, tx, ty, ax, ay);
			double bottomF = F(sx, sy, tx, ty, ax, ay);
			double bottomrightF = F(sx, sy, tx, ty, ax, ay);
			// Determine the lowest step
			possible.clear();
			double min = min(topleftF, topF, toprightF, leftF, rightF, bottomleftF, bottomF, bottomrightF);
			if(check(min, topleftF) && available(topleft)){
				possible.add(topleft);
			} 
			if(check(min, topF) && available(top)){
				possible.add(top);
			}
			if(check(min, toprightF) && available(topright)){
				possible.add(topright);
			}
			if(check(min, leftF) && available(left)){
				possible.add(left);
			}
			if(check(min, rightF) && available(right)){
				possible.add(right);
			}
			if(check(min, bottomleftF) && available(bottomleft)){
				possible.add(bottomleft);
			}
			if(check(min, bottomF) && available(bottom)){
				possible.add(bottom);
			}
			if(check(min, bottomrightF) && available(bottomright)){
				possible.add(bottomright);
			}
			ITile possibleTile = null;
			for(ITile tile : possible){
				if(tile.tx == tx && tile.ty == ty){
					possibleTile = tile;
					break;
				}
				if(possibleTile == null){
					possibleTile = tile;
				} else {
					if(G(tx, ty, tile) < G(tx, ty, possibleTile)){
						possibleTile = tile;
					}
				}
			}
			active = possibleTile;
			// Remove the tiles
			ax = active.tx;
			ay = active.ty;
			swap(active);
			// Add the step
			path.addTile(active);
			System.out.println(ax + ", " + ay);
			if((ax == tx && ay == ty)){
				break;
			}
		}
		// Add the target tile
		path.addTile(map.getTile(tx, ty));
		long after = System.currentTimeMillis();
		path.setOverall(map.getTile(sx, sy), map.getTile(tx, ty));
		path.setMillis(after - before);
		return path;
	}
	
	// -------------[ UTILITIES ]-------------
	
	private void swap(ITile tile){
		if(tile == null) return;
		open.remove(tile);
		closed.add(tile);
	}
	
	private boolean good(ITile tile){
		if(tile == null) return false;
		return !closed.contains(tile);
	}
	
	private boolean available(ITile tile){
		if(tile == null) return false;
		if(!open.contains(tile)){
			return false;
		}
		if(closed.contains(tile)){
			return false;
		}
		return open.contains(tile) && !closed.contains(tile);
	}
	
	private boolean check(double min, double F){
		return min == F;
	}
	
	private double min(double... doubles){
		double min = 1000000;
		for(double double_ : doubles){
			min = Math.min(double_, min);
		}
		return min;
	}
	
	private double G(int ax, int ay, ITile tile){
		double dx = tile.tx - ax, dy = tile.ty - ay;
		double G = Math.sqrt(dx * dx + dy * dy);
		return G;
	}
	private double F(int sx, int sy, int tx, int ty, int ax, int ay){
		if(ax < 0 || ay < 0 || ay >= map.getHeight() || ax >= map.getWidth()){
			return 1000;
		}
		int dx = tx - ax, dy = ty - ay;
		double G = Math.sqrt(dx * dx + dy * dy);
		double H = Math.abs(dx + dy);
		double F = G + H;
		return map.getTile(ax, ay).weight + F; // Add to the weight of the tile
	}

}

CopyableCougar4

#24

I think I fixed it… I used some hacky if statements to prevent the paths like the last post. I will post later if it fails to keep working.

CopyableCougar4

#25

Hi, glad the pathfinder’s working now!

I just skimmed through the code and can’t resist trying to give you a few pointers :smiley: Here’s 3 things that jump out:

There is a lot of repeated code. This makes for bugs - any changes need making in several different places (usually 8 here) and sometimes you’ll miss one. It also makes it harder to read.

Try to factor things down so that nothing is repeated. Whenever you see big blocks of repeated stuff like this

ITile topleft = map.getTile(ax - 1, ay - 1);
if(topleft != null) topleft.setParent(active);
ITile top = map.getTile(ax, ay - 1);
if(top != null) top.setParent(active);

or especially this with a constant that might change

if(topright != null && topright.weight < 100 && good(topright)){
    open.add(topright);
}
if(left != null && left.weight < 100 && good(left)){
    open.add(left);
}

… replace them with function calls where the parameters are the only varying things, e.g.

ITile topleft = setParentAndAdd(-1, -1);
ITile top = setParentAndAdd(0, -1);

(Just an example. In your code there are several groups of 8 repeated sections which ought to all be consolidated. This will make it much more readable, and as a result more debuggable. I dare say you could trim a half or 3/4 of the code bloat from this pathfinder class.)

The function

private double min(double... doubles){
    double min = 1000000;
    for(double double_ : doubles){

has a bug! What if we pass in two values: 2000000 and 2000001? It will return 1000000! In min or max functions of this kind, use Double.MAX_VALUE (or Integer.MAX_VALUE or whatever the type) is as the starting value.

Also I’d advise “d” instead of the rather confusing “double_” for the loop variable. Actually in general I think most of your function and variable names are questionable, but whatever floats your boat I guess :smiley:

This is bad code:

private boolean good(ITile tile){
    if(tile == null) return false;
    return !closed.contains(tile);
}

Why? Because the function is testing if a tile is good, and if the tile doesn’t exist we’re saying no it’s not good, which is the same return code as if it did exist and it wasn’t good. So if some other piece of code calls here with a null (which is clearly a bug in that calling code) we’re causing them bigger problems by pretending their parameter was valid. They will proceed to do stuff as if it was a bad tile, and weird problems will arise somewhat later and be hard to understand.

As it happens in your code before you call good() you’re testing for a null tile, which is right. Here in the function, it should either ignore nulls (caller would get an null pointer exception and the bug is easily pinpointed) or throw its own IllegalArgumentException e.g. “Null tile passed into good()” which is definitely overkill here but wouldn’t be in a more complex function.

Hope some of that helps - keep on coding!! :smiley: