A* between two points on a TiledmapTileLayer. Assumes that all non-null cells on the layer are pathable.

A_Star.java

package org.worldsproject.dwis.org.worldsproject.dwis.ai;

import com.badlogic.gdx.maps.tiled.TiledMap;
import com.badlogic.gdx.maps.tiled.TiledMapTileLayer;
import com.badlogic.gdx.maps.tiled.TiledMapTileLayer.Cell;
import com.badlogic.gdx.math.Vector2;

import java.awt.*;
import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * User: Tim Butram
 *       WorldsProject LLC
 * Date: 12/4/13
 * Time: 1:29 PM
 * Copyright: GPL3
 */
public class A_Star {
    public static final String LOG = A_Star.class.getSimpleName();
    private TiledMapTileLayer pathing_layer;

    public A_Star(TiledMapTileLayer layer) {
        pathing_layer = layer;
    }

    public LinkedList<Vector2> getPath(Vector2 start, Vector2 end) {
        HashSet<Node> closedSet = new HashSet<Node>();
        PriorityQueue<Node> openSet = new PriorityQueue<Node>();

        Node s = new Node(start);
        openSet.add(s);

        while(openSet.isEmpty() == false) {
            Node q = openSet.remove();

            ArrayList<Node> neighbors = getNeighbors(q);

            for(Node neighbor : neighbors) {
                if(neighbor.me.equals(end)) {
                    return resolve_path(neighbor);
                }

                float g = q.g + cost_estimate(neighbor.me, q.me);
                float h = cost_estimate(neighbor.me, end);
                float f = g + h;

                if(openSet.contains(neighbor) && neighbor.f < f) {
                    continue;
                } else if(closedSet.contains(neighbor) && neighbor.f < f) {
                    continue;
                } else {
                    neighbor.f = f;
                    neighbor.g = g;
                    neighbor.h = h;
                    openSet.add(neighbor);
                }
            }

            closedSet.add(q);
        }

        return null;
    }

    private LinkedList<Vector2> resolve_path(Node end) {
        LinkedList<Vector2> rv = new LinkedList<Vector2>();
        Node current = end;
        rv.push(end.me);
        while(current.parent != null) {
            rv.push(current.parent.me);
            current = current.parent;
        }

        return rv;
    }

    private float cost_estimate(Vector2 start, Vector2 end) {
        float xs = start.x - end.x;
        float ys = start.y - end.y;

        return xs*xs + ys*ys;
    }

    private ArrayList<Node> getNeighbors(Node cell) {
        Vector2 top_left = new Vector2(cell.me.x-1, cell.me.y+1);
        Vector2 top_middle = new Vector2(cell.me.x, cell.me.y+1);
        Vector2 top_right = new Vector2(cell.me.x+1, cell.me.y+1);

        Vector2 center_left = new Vector2(cell.me.x-1, cell.me.y);
        Vector2 center_right = new Vector2(cell.me.x+1, cell.me.y);

        Vector2 bottom_left = new Vector2(cell.me.x-1, cell.me.y-1);
        Vector2 bottom_middle = new Vector2(cell.me.x, cell.me.y-1);
        Vector2 bottom_right = new Vector2(cell.me.x+1, cell.me.y-1);

        ArrayList<Node> rv = new ArrayList<Node>();

        addToList(rv, top_left, cell);
        addToList(rv, top_middle, cell);
        addToList(rv, top_right, cell);
        addToList(rv, center_left, cell);
        addToList(rv, center_right, cell);
        addToList(rv, bottom_left, cell);
        addToList(rv, bottom_middle, cell);
        addToList(rv, bottom_right, cell);

        return rv;
    }

    private void addToList(ArrayList<Node> list, Vector2 item, Node parent) {
       if(pathing_layer.getCell((int)item.x, (int)item.y) != null) {
           Node n = new Node(item);
           n.parent = parent;
           list.add(n);
        }
    }

    private class Node implements Comparable<Node>{
        public Vector2 me;
        public Node parent;
        public float g = 0;
        public float f = 0;
        public float h = 0;

        public Node(Vector2 me) {
            this.me = me;
        }

        @Override
        public int compareTo(Node other) {
            if(f < other.f) {
                return -1;
            } else if(f == other.f) {
                return 0;
            } else {
                return 1;
            }
        }

        public String toString() {
            return me.toString();
        }
    }
}