Nachdem hier ja immer noch über A* diskutiert wird, möchten vielleicht
einige von euch damit auch ein bischen experimentieren. Damit nun nicht
jeder eine Implementation selbst schreiben muss, hier mein Demo-Code mit
dem ich Paul Ebermanns Mutmaßungen überprüft habe.
Durch Implementieren der abstrakten Methoden der Klasse Pathfinder,
lassen sich verschiedene Heuristiken und Metriken austesten; einige
Beispiele sind ja schon im Code enthalten.
Viel Spass damit.
Und mal sehen, ob jemand mit einer besseren Heuristik als Manhattan
aufwarten kann. (OK, evtl. muss die Testmap komplexer gemacht werden.)
cu
package de.comp.lang.java;
import java.util.LinkedList;
import java.util.List;
public abstract class Pathfinder {
private static class Tile {
int x;
int y;
int fullCost;
int guaranteedCost;
int heuristicCost;
Tile prev;
Tile next;
int position; // == 0 means on closed list
boolean isTarget;
/** Construct a wall. */
private Tile() {
x = y = -1;
fullCost = guaranteedCost = heuristicCost = Integer.MIN_VALUE;
}
/** Construct a walkable tile. */
private Tile(int x, int y, int hCost) {
this.x = x;
this.y = y;
fullCost = guaranteedCost = Integer.MAX_VALUE;
heuristicCost = hCost;
}
/** Construct a target tile. */
private Tile(int x, int y) {
this.x = x;
this.y = y;
fullCost = guaranteedCost = Integer.MAX_VALUE;
heuristicCost = Integer.MIN_VALUE;
}
// only for demo
char charForEntry(int xStart, int yStart) {
if ((x < 0) || (y < 0))
return 'W';
if ((x == xStart) && (y == yStart))
return 'S';
if (isTarget)
return '*';
if (position < 10) {
return "C123456789".charAt(position);
}
return 'o';
}
public Tile getNext() {
return next;
}
public Tile getPrevious() {
return prev;
}
public int getX() {
return x;
}
public int getY() {
return y;
}
}
Tile start;
int xStart;
int yStart;
int pathLength;
Tile[] path;
private int width;
private int height;
Tile[] openList;
int openSize;
Tile[] map;
List<Tile> targets;
// remember walls between path finding, could be shared between
// multiple pathfinder instances
private Tile[] walls;
private final Tile WALL = new Tile();
private int steps;
public Pathfinder(int width, int height) {
this.width = width;
this.height = height;
openList = new Tile[width * height + 1];
map = new Tile[width * height];
walls = new Tile[width * height];
targets = new LinkedList<Tile>();
}
final int i4map(int x, int y) {
return x + y * width;
}
public void addBorder() {
for (int x = 0; x < width; x++) {
addWall(x, 0);
addWall(x, height - 1);
}
for (int y = 0; y < height; y++) {
addWall(0, y);
addWall(width - 1, y);
}
}
public void addWall(int x, int y) {
walls[i4map(x, y)] = WALL;
}
public void removeWall(int x, int y) {
walls[i4map(x, y)] = null;
}
public void setStart(int x, int y) {
xStart = x;
yStart = y;
}
public void addTarget(int x, int y) {
targets.add(new Tile(x, y));
}
public void clearTargets() {
targets.clear();
}
public void findPath() {
reset();
steps = 0;
start = lookup(xStart, yStart);
start.guaranteedCost = 0;
for (Tile target : targets) {
lookup(target.x, target.y).isTarget = true;
}
Tile current = null;
while (!isEmpty()) {
++steps;
showMap(steps);
current = removeHead();
if (current.isTarget)
break;
tryStep(current, 1, 1);
tryStep(current, 0, 1);
tryStep(current, -1, 1);
tryStep(current, 1, 0);
tryStep(current, -1, 0);
tryStep(current, 1, -1);
tryStep(current, 0, -1);
tryStep(current, -1, -1);
}
for (Tile t = current; t != null; t = t.prev) {
t.isTarget = true; // mark path demo only
if (t.prev != null) {
t.prev.next = t;
}
pathLength++;
}
showMap(steps);
}
public int[] toXYArray() {
int[] retval = new int[pathLength * 2];
int len = 0;
for (Tile t = start; t != null; t = t.next) {
retval[len++] = t.x;
retval[len++] = t.y;
}
return retval;
}
public int size() {
return pathLength;
}
public Tile get(int index) {
if (path == null) {
path = new Tile[pathLength];
int len = 0;
for (Tile t = start; t != null; t = t.next) {
path[len++] = t;
}
}
return path[index];
}
// demo only
private void showMap(int steps) {
System.out.println("=== #" + steps + " open: " + openSize);
for (int y = 0; y < height; y++) {
for (int x = 0; x < width; x++) {
Tile t = map[i4map(x, y)];
System.out.print(t == null ? '_' : t.charForEntry(xStart,
yStart));
}
System.out.println();
}
}
private void tryStep(Tile current, int dx, int dy) {
Tile next = lookup(current.x + dx, current.y + dy);
int newCost = current.guaranteedCost
+ calcStepCost(current, next, dx, dy);
if (newCost < next.guaranteedCost) {
next.guaranteedCost = newCost;
next.prev = current;
next.fullCost = newCost + next.heuristicCost;
// new full cost is always lower than old full cost,
// so only a fixUp on the position could be needed
fixUp(next.position);
}
}
private Tile lookup(int x, int y) {
Tile tile = map[i4map(x, y)];
if (tile == null) {
tile = new Tile(x, y, calcHeuristicCost(x, y));
map[i4map(x, y)] = tile;
// add to end of open list
openList[tile.position = ++openSize] = tile;
// no fixUp needed, fullCost is MAX_VALUE!!
}
return tile;
}
protected abstract int calcStepCost(Tile from, Tile to, int dx, int
dy);
protected abstract int calcHeuristicCost(int x, int y);
private Tile removeHead() {
Tile head = openList[1];
openList[1] = openList[openSize];
openList[1].position = 1;
openList[openSize--] = null;
fixDown(1);
head.position = 0;
return head;
}
/**
* Returns true if the fullCost openList contains no elements.
*/
public boolean isEmpty() {
return openSize == 0;
}
private void reset() {
for (int i = 1; i <= openSize; i++) {
openList[i].prev = null;
openList[i] = null;
}
openSize = 0;
System.arraycopy(walls, 0, map, 0, walls.length);
start = null;
pathLength = 0;
path = null;
}
/**
* Establishes the heap invariant (described above) assuming the heap
* satisfies the invariant except possibly for the leaf-node
indexed by k
* (which may have a fullCost less than its prev's).
*
* This method functions by "promoting" openList[k] up the
hierarchy (by
* swapping it with its prev) repeatedly until openList[k]'s
fullCost is
* greater than or equal to that of its prev.
*/
void fixUp(int k) {
while (k > 1) {
int j = k >> 1;
if (openList[j].fullCost <= openList[k].fullCost) {
break;
}
Tile tmp = openList[j];
openList[j] = openList[k];
openList[j].position = j;
openList[k] = tmp;
openList[k].position = k;
k = j;
}
}
/**
* Establishes the heap invariant (described above) in the subtree
rooted at
* k, which is assumed to satisfy the heap invariant except
possibly for
* node k itself (which may have a fullCost greater than its
children's).
*
* This method functions by "demoting" openList[k] down the
hierarchy (by
* swapping it with its smaller child) repeatedly until openList[k]'s
* fullCost is less than or equal to those of its children.
*/
private void fixDown(int k) {
int j;
while ((j = k << 1) <= openSize) {
if ((j < openSize)
&& (openList[j].fullCost > openList[j + 1].fullCost))
j++; // j indexes smallest kid
if (openList[k].fullCost <= openList[j].fullCost)
break;
Tile tmp = openList[j];
openList[j] = openList[k];
openList[j].position = j;
openList[k] = tmp;
openList[k].position = k;
k = j;
}
}
public static class AStar extends Pathfinder {
public AStar(int width, int height) {
super(width, height);
}
@Override
protected int calcStepCost(Tile from, Tile to, int dx, int dy) {
return ((dx & dy) == 0 ? 10 : 14);
}
@Override
protected int calcHeuristicCost(int x, int y) {
int hCost = Integer.MAX_VALUE;
for (Tile target : targets) {
int tmp = 10 * (Math.abs(target.x - x) +
Math.abs(target.y - y));
if (tmp < hCost) {
hCost = tmp;
}
}
return hCost;
}
}
public static class Dijkstra extends Pathfinder {
public Dijkstra(int width, int height) {
super(width, height);
}
@Override
protected int calcStepCost(Tile from, Tile to, int dx, int dy) {
return ((dx & dy) == 0 ? 10 : 14);
}
@Override
protected int calcHeuristicCost(int x, int y) {
return 0;
}
}
public static class Better extends Pathfinder {
public Better(int width, int height) {
super(width, height);
}
@Override
protected int calcStepCost(Tile from, Tile to, int dx, int dy) {
return ((dx & dy) == 0 ? 10 : 14);
}
@Override
protected int calcHeuristicCost(int x, int y) {
int hCost = Integer.MAX_VALUE;
for (Tile target : targets) {
int dx = Math.abs(target.x - x);
int dy = Math.abs(target.y - y);
int tmp = 10 * Math.max(dx, dy) + 4 * Math.min(dx, dy);
if (tmp < hCost) {
hCost = tmp;
}
}
return hCost;
}
}
public static class Ebermann extends Pathfinder {
public Ebermann(int width, int height) {
super(width, height);
}
@Override
protected int calcStepCost(Tile from, Tile to, int dx, int dy) {
return ((dx & dy) == 0 ? 100 : 141);
}
@Override
protected int calcHeuristicCost(int x, int y) {
int hCost = Integer.MAX_VALUE;
for (Tile target : targets) {
int dx = Math.abs(target.x - x);
int dy = Math.abs(target.y - y);
int tmp = 100 * (dx + dy) - 66 * Math.min(dx, dy);
if (tmp < hCost) {
hCost = tmp;
}
}
return hCost;
}
}
public static class Pythagoras extends Pathfinder {
public Pythagoras(int width, int height) {
super(width, height);
}
@Override
protected int calcStepCost(Tile from, Tile to, int dx, int dy) {
return ((dx & dy) == 0 ? 100 : 141);
}
@Override
protected int calcHeuristicCost(int x, int y) {
int hCost = Integer.MAX_VALUE;
for (Tile target : targets) {
int dx = Math.abs(target.x - x);
int dy = Math.abs(target.y - y);
int tmp = (int)(100 * Math.sqrt(dx*dx + dy*dy));
if (tmp < hCost) {
hCost = tmp;
}
}
return hCost;
}
}
public static void main(String... args) {
Pathfinder pf;
// pf = new Pathfinder.Dijkstra(15, 9);
// demoPathfinder(pf);
pf = new Pathfinder.AStar(15, 9);
demoPathfinder(pf);
// pf = new Pathfinder.Ebermann(15, 9);
// demoPathfinder(pf);
// pf = new Pathfinder.Pythagoras(15, 9);
// demoPathfinder(pf);
}
private static void demoPathfinder(Pathfinder pf) {
pf.addBorder();
pf.addWall(7, 3);
pf.addWall(7, 4);
pf.addWall(7, 5);
pf.setStart(4, 4);
pf.addTarget(10, 4);
pf.findPath();
System.out.println(pf.getClass().getSimpleName()+":
"+pf.steps+" iterations / path lentgh: "+pf.size());
for (int i = 0; i < pf.size(); i++) {
System.out.println(i + ": " + pf.get(i).getX() + "/"
+ pf.get(i).getY());
}
}
}