Create a gist now

Instantly share code, notes, and snippets.

A* for libgdx that is simple but optimized, includes runnable demo. Uses a binary heap for the open list. Nodes are cached in a PathNode[], which is also used to make finding a node in the open list fast. A "run id" is used to avoid needing to clear the nodes for a new run.
// A* for libgdx that is simple but optimized.
package test;
import com.badlogic.gdx.ApplicationAdapter;
import com.badlogic.gdx.Gdx;
import com.badlogic.gdx.backends.lwjgl.LwjglApplication;
import com.badlogic.gdx.graphics.Color;
import com.badlogic.gdx.graphics.GL10;
import com.badlogic.gdx.graphics.glutils.ShapeRenderer;
import com.badlogic.gdx.graphics.glutils.ShapeRenderer.ShapeType;
import com.badlogic.gdx.utils.BinaryHeap;
import com.badlogic.gdx.utils.BinaryHeap.Node;
import com.badlogic.gdx.utils.IntArray;
/** @author Nathan Sweet */
public class AstarTest extends ApplicationAdapter {
ShapeRenderer shapes;
Astar astar;
boolean[] map;
public void create () {
shapes = new ShapeRenderer();
map = new boolean[10 * 10];
map[5 + 5 * 10] = true;
map[6 + 5 * 10] = true;
map[7 + 5 * 10] = true;
map[7 + 6 * 10] = true;
map[8 + 6 * 10] = true;
astar = new Astar(10, 10) {
protected boolean isValid (int x, int y) {
return !map[x + y * 10];
}
};
}
public void resize (int width, int height) {
shapes.getProjectionMatrix().setToOrtho2D(0, 0, width, height);
}
public void render () {
Gdx.gl.glClear(GL10.GL_COLOR_BUFFER_BIT);
int width = Gdx.graphics.getWidth();
int height = Gdx.graphics.getHeight();
int mapWidth = astar.getWidth();
int mapHeight = astar.getHeight();
int cellWidth = width / mapWidth;
int cellHeight = height / mapHeight;
shapes.setColor(Color.GRAY);
shapes.begin(ShapeType.Line);
for (int x = 0; x < mapWidth; x++)
shapes.line(x * cellWidth, 0, x * cellWidth, height);
for (int y = 0; y < mapHeight; y++)
shapes.line(0, y * cellHeight, width, y * cellHeight);
shapes.end();
shapes.setColor(Color.BLUE);
shapes.begin(ShapeType.Filled);
for (int x = 0; x < mapWidth; x++)
for (int y = 0; y < mapHeight; y++)
if (map[x + y * mapWidth]) shapes.rect(x * cellWidth, y * cellHeight, cellWidth, cellHeight);
int startX = Gdx.input.getX() / cellWidth;
int startY = (height - Gdx.input.getY()) / cellHeight;
shapes.setColor(Color.GREEN);
shapes.rect(startX * cellWidth, startY * cellHeight, cellWidth, cellHeight);
int targetX = 8;
int targetY = 9;
shapes.setColor(Color.RED);
shapes.rect(targetX * cellWidth, targetY * cellHeight, cellWidth, cellHeight);
if (startX >= 0 && startY >= 0 && startX < mapWidth && startY < mapHeight) {
shapes.setColor(Color.GREEN);
IntArray path = astar.getPath(startX, startY, targetX, targetY);
for (int i = 0, n = path.size; i < n; i += 2) {
int x = path.get(i);
int y = path.get(i + 1);
shapes.circle(x * cellWidth + cellWidth / 2, y * cellHeight + cellHeight / 2, cellWidth / 4, 30);
}
}
shapes.end();
}
public static void main (String[] args) throws Exception {
new LwjglApplication(new AstarTest());
}
/** @author Nathan Sweet */
static public class Astar {
private final int width, height;
private final BinaryHeap<PathNode> open;
private final PathNode[] nodes;
int runID;
private final IntArray path = new IntArray();
private int targetX, targetY;
public Astar (int width, int height) {
this.width = width;
this.height = height;
open = new BinaryHeap(width * 4, false);
nodes = new PathNode[width * height];
}
/** Returns x,y pairs that are the path from the target to the start. */
public IntArray getPath (int startX, int startY, int targetX, int targetY) {
this.targetX = targetX;
this.targetY = targetY;
path.clear();
open.clear();
runID++;
if (runID < 0) runID = 1;
int index = startY * width + startX;
PathNode root = nodes[index];
if (root == null) {
root = new PathNode(0);
root.x = startX;
root.y = startY;
nodes[index] = root;
}
root.parent = null;
root.pathCost = 0;
open.add(root, 0);
int lastColumn = width - 1, lastRow = height - 1;
int i = 0;
while (open.size > 0) {
PathNode node = open.pop();
if (node.x == targetX && node.y == targetY) {
while (node != root) {
path.add(node.x);
path.add(node.y);
node = node.parent;
}
break;
}
node.closedID = runID;
int x = node.x;
int y = node.y;
if (x < lastColumn) {
addNode(node, x + 1, y, 10);
if (y < lastRow) addNode(node, x + 1, y + 1, 14); // Diagonals cost more, roughly equivalent to sqrt(2).
if (y > 0) addNode(node, x + 1, y - 1, 14);
}
if (x > 0) {
addNode(node, x - 1, y, 10);
if (y < lastRow) addNode(node, x - 1, y + 1, 14);
if (y > 0) addNode(node, x - 1, y - 1, 14);
}
if (y < lastRow) addNode(node, x, y + 1, 10);
if (y > 0) addNode(node, x, y - 1, 10);
i++;
}
return path;
}
private void addNode (PathNode parent, int x, int y, int cost) {
if (!isValid(x, y)) return;
int pathCost = parent.pathCost + cost;
float score = pathCost + Math.abs(x - targetX) + Math.abs(y - targetY);
int index = y * width + x;
PathNode node = nodes[index];
if (node != null && node.runID == runID) { // Node already encountered for this run.
if (node.closedID != runID && pathCost < node.pathCost) { // Node isn't closed and new cost is lower.
// Update the existing node.
open.setValue(node, score);
node.parent = parent;
node.pathCost = pathCost;
}
} else {
// Use node from the cache or create a new one.
if (node == null) {
node = new PathNode(0);
node.x = x;
node.y = y;
nodes[index] = node;
}
open.add(node, score);
node.runID = runID;
node.parent = parent;
node.pathCost = pathCost;
}
}
protected boolean isValid (int x, int y) {
return true;
}
public int getWidth () {
return width;
}
public int getHeight () {
return height;
}
static private class PathNode extends Node {
int runID, closedID, x, y, pathCost;
PathNode parent;
public PathNode (float value) {
super(value);
}
}
}
}
@just4phil

hi nate!
is it possible to use this for diagonal moves too?

@nbilyk
nbilyk commented Sep 20, 2014

It looks like that would work for diagonal moves, see the 14 weight.

@NeoFreak
NeoFreak commented Jul 2, 2016

Cool! perfect!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment