Hallo,
ich habe wie folgt den A*-Algorithmus implementiert:
Zum Algorithmus an sich habe ich keine Frage. Der funktioniert soweit super.
Mir geht es darum, dass ich diese Implementierung flexibel halten möchte, sodass er öfter einsetzbar ist. Das habe ich durch die Schnittstellen World, CostsCalculator und Comparator<Node> versucht. Für die letzteren beiden wird eine Defaultimplementierung mitgeliefert.
Geht es auch anders? Es gibt keine Methoden- bzw. Funktionszeiger in Java soweit ich weiß und mit den Schnittstellen wollte ich mir einen Workaround basteln. Allerdings finde ich das nicht sehr sauber.
ich habe wie folgt den A*-Algorithmus implementiert:
Java:
package astar;
import java.awt.Point;
import java.util.*;
public abstract class AStar {
public static interface World {
public List<Node> getNeighbours(Node node);
}
public static interface CostsCalculator {
public int getMovementCosts(Node end);
public int getEstimatedCosts(Node start, Node end);
}
public static CostsCalculator costsCalculator;
public static Comparator<Node> costsComparator;
public static Stack<Point> getPath(World world, Node start, Node end) {
List<Node> openList = new ArrayList<Node>();
List<Node> closedList = new ArrayList<Node>();
openList.add(start);
while(!closedList.contains(end) || openList.isEmpty()) {
Collections.sort(openList, costsComparator);
start = openList.get(0);
openList.remove(start);
closedList.add(start);
for(Node neighbour : world.getNeighbours(start)) {
if(!closedList.contains(neighbour)) {
neighbour.previousNode = start;
neighbour.calculateCosts(costsCalculator, end);
if(!openList.contains(neighbour))
openList.add(neighbour);
}
}
}
Stack<Point> path = new Stack<Point>();
Node node = closedList.get(closedList.indexOf(end));
while(node.previousNode != null) {
path.push(node);
node = node.previousNode;
}
return path;
}
static {
costsCalculator = new CostsCalculator() {
@Override
public int getMovementCosts(Node end) {
int costs = 10;
if(end.previousNode != null)
costs += end.getCosts(Node.Costs.MOVEMENT);
return costs;
}
@Override
public int getEstimatedCosts(Node start, Node end) {
return (Math.abs(start.x - end.x)
+ Math.abs(start.y - end.y)) * 10;
}
};
costsComparator = new Comparator<Node>() {
@Override
public int compare(Node a, Node b) {
if(a.getCosts(Node.Costs.ALL) < b.getCosts(Node.Costs.ALL))
return -1;
else if(a.getCosts(Node.Costs.ALL) > b.getCosts(Node.Costs.ALL))
return 1;
return 0;
}
};
}
static class Node extends Point {
public static enum Costs {
ALL, MOVEMENT, ESTIMATED
}
public Node previousNode;
private int movementCosts;
private int estimatedCosts;
public Node(int x, int y) {
super(x, y);
previousNode = null;
movementCosts = 0;
estimatedCosts = 0;
}
public void calculateCosts(CostsCalculator c, Node node) {
movementCosts = c.getMovementCosts(node);
estimatedCosts = c.getEstimatedCosts(this, node);
}
public int getCosts(Costs costs) {
switch(costs) {
case ALL:
return movementCosts + estimatedCosts;
case MOVEMENT:
return movementCosts;
case ESTIMATED:
return estimatedCosts;
default:
return -1;
}
}
}
}Zum Algorithmus an sich habe ich keine Frage. Der funktioniert soweit super.
Mir geht es darum, dass ich diese Implementierung flexibel halten möchte, sodass er öfter einsetzbar ist. Das habe ich durch die Schnittstellen World, CostsCalculator und Comparator<Node> versucht. Für die letzteren beiden wird eine Defaultimplementierung mitgeliefert.
Geht es auch anders? Es gibt keine Methoden- bzw. Funktionszeiger in Java soweit ich weiß und mit den Schnittstellen wollte ich mir einen Workaround basteln. Allerdings finde ich das nicht sehr sauber.
