A star is born

I’ve just implemented the A* algorithm for the TileEngine. Might come handy for calculating the attack path in a “Tower Defense” style game, or for moving to  a location in touch based games like “Emily”.

import de.eppleton.fx2d.tileengine.TileMap;
import de.eppleton.fx2d.tileengine.TileMapLayer;
import java.util.*;

public class AStar {

    public static PathNode getPath(TileMap map, TileMapLayer layer, AStarTile start, AStarTile goal) {

        boolean[][] playField = new boolean[map.getWidth()][map.getHeight()];
        for (int x = 0; x < playField.length; x++) {
            boolean[] bs = playField[x];
            for (int y = 0; y < bs.length; y++) {
                int idx = x + (y * map.getWidth());
                bs[y] = layer.getGid(idx) == 0;
            }
        }

        PriorityQueue<PathNode> openList = new PriorityQueue<>();
        List<PathNode> closedList = new ArrayList<>();
        PathNode stn = new PathNode(null, 0, 0, start.x, start.y);
        openList.add(stn);
        while (!openList.isEmpty()) {
            PathNode toExpand = openList.poll();
            List<PathNode> successors = new ArrayList<>();
            int ex = toExpand.getX();
            int ey = toExpand.getY();
            addSuccessor(playField, ex - 1, ey, toExpand, goal, successors);
            addSuccessor(playField, ex, ey - 1, toExpand, goal, successors);
            addSuccessor(playField, ex + 1, ey, toExpand, goal, successors);
            addSuccessor(playField, ex, ey + 1, toExpand, goal, successors);
            for (PathNode candidate : successors) {
                if (candidate.x == goal.x && candidate.y == goal.y) {
                    return candidate;
                }
                if (alreadyFound(candidate, closedList)) {
                    continue;
                }
                if (alreadyFound(candidate, openList)) {
                    continue;
                }
                openList.add(candidate);

            }
            closedList.add(toExpand);
        }
        return null;
    }

    public static void addSuccessor(boolean[][] playField, int ex, int ey, PathNode toExpand, AStarTile goal, List<PathNode> successors) {
        if (ex < 0 || ey < 0 || ex >= playField.length || ey >= playField[ex].length) {
            return;
        }

        if (playField[ex][ey]) {
            PathNode n = new PathNode(toExpand, ex, ey);
            n.g = g(n);
            n.h = h(n, goal);
            n.f = n.g + n.h;
            successors.add(n);
        }
    }

    private static boolean alreadyFound(PathNode n, Collection<PathNode> l) {
        for (PathNode no : l) {
            if (no.getX() == n.getX() && no.getY() == n.getY() && no.getF() <= n.getF()) {
                return true;
            }
        }
        return false;
    }

    private static float g(PathNode n) {
        PathNode p = n.getParent();
        return p.g + 1;
    }

    private static float h(PathNode act, AStarTile goal) {
        int distX = Math.abs(act.getX() - goal.x);
        int distY = Math.abs(act.getY() - goal.y);
        float ret = (float) Math.sqrt(distX * distX + distY * distY);
        return ret;
    }

    public static class AStarTile {

        int x, y;

        public AStarTile(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static class PathNode implements Comparable<PathNode> {

        private PathNode parent;
        private float f, g, h;

        public PathNode getParent() {
            return parent;
        }
        private int x, y;

        public int getX() {
            return x;
        }

        public int getY() {
            return y;
        }

        float getF() {
            return f;
        }

        private PathNode(PathNode parent, float g, float h, int x, int y) {
            this.parent = parent;
            this.x = x;
            this.y = y;
            this.g = g;
            this.h = h;
            this.f = g + h;
        }

        private PathNode(PathNode parent, int x, int y) {
            this(parent, 0, 0, x, y);
        }

        @Override
        public int compareTo(PathNode o) {
            return f > o.f ? 1 : f == o.f ? 0 : -1;
        }
    }
}

Here I use it in the tilemap editor:

And here in a game prototype:

Placing obstacles forces recalculation (the guys who get stuck when I place a rock can’t find a path ’cause the start tile is invalid):