# 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);
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)) {
}
if (top != null && top.weight < 100 && good(top)) {
}
if (topright != null && topright.weight < 100 && good(topright)) {
}
if (left != null && left.weight < 100 && good(left)) {
}
if (right != null && right.weight < 100 && good(right)) {
}
if (bottomleft != null && bottomleft.weight < 100 && good(bottomleft)) {
}
if (bottom != null && bottom.weight < 100 && good(bottom)) {
}
if (bottomright != null && bottomright.weight < 100 && good(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)) {
}
if (check(min, topF) && available(top)) {
}
if (check(min, toprightF) && available(topright)) {
}
if (check(min, leftF) && available(left)) {
}
if (check(min, rightF) && available(right)) {
}
if (check(min, bottomleftF) && available(bottomleft)) {
}
if (check(min, bottomF) && available(bottom)) {
}
if (check(min, bottomrightF) && available(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);
Log.print(ax + ", " + ay);
if ((ax == tx && ay == ty)) {
break;
}
}
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);
}

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

CopyableCougar4