Faster A* Pathfinding

So I finally (5 days ago) seem to have achieved A* pathfinding. The only problem is that I want my pathfinding to be faster. A path of 180 steps takes 25 ms to complete, but I want to try to make this faster.

Pathfinder class:

package game.util;

import java.util.ArrayList;

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>();
	
	private ArrayList<int[]> oldTiles = new ArrayList<int[]>();
	
	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)) {
						if (oldTiles.size() >= 2) {
							int[] twoAgo = oldTiles.get(1);
							int[] oneAgo = oldTiles.get(0);
							// Check for paths that go bad diagonally
							if (twoAgo[0] == oneAgo[0] && tile.ty == oneAgo[1]) {
								path.removeLast();
							}
							if (twoAgo[1] == oneAgo[1] && tile.tx == oneAgo[0]) {
								path.removeLast();
							}
						}
						possibleTile = tile;
					}
				}
			}
			active = possibleTile;
			// Remove the tiles
			ax = active.tx;
			ay = active.ty;
			oldTiles.add(0, new int[]{ ax, ay });
			swap(active);
			// Add the step
			path.addTile(active);
			Log.print(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 tx, int ty, ITile tile) {
		double dx = tile.tx - tx, dy = tile.ty - ty;
		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;
		if (dx == dy) {
			F = Math.max(0, F - 2); // diagonal
		}
		return map.getTile(ax, ay).weight + F; // Add to the weight of the tile
	}

}

Any help would be appreciated :slight_smile:

CopyableCougar4