TomTuff
2011-04-09 20:47:49
Here is Jacmobs A* algorithm:
More Info: http://villavu.com/forum/showpost.php?p=793691&postcount=9
It would be awesome if someone could write this for Simba + Reflection :)
/**
* A* impl using local rs collision map.
*
* @author Jacmob
*/
static class AStar {
private static class Node {
public int x, y;
public Node prev;
public double g, f;
public Node(int x, int y) {
this.x = x;
this.y = y;
g = f = 0;
}
@Override
public int hashCode() {
return (x << 4) | y;
}
@Override
public boolean equals(Object o) {
if (o instanceof Node) {
Node n = (Node) o;
return x == n.x && y == n.y;
}
return false;
}
@Override
public String toString() {
return "(" + x + "," + y + ")";
}
public RSTile toRSTile(int baseX, int baseY) {
return new RSTile(x + baseX, y + baseY);
}
}
private Walking walking;
private Game game;
private int[][] flags;
private int off_x, off_y;
public void init(Game game, Walking walking) {
this.game = game;
this.walking = walking;
}
public RSTile[] findPath(RSTile start, RSTile end) {
int base_x = game.getBaseX(), base_y = game.getBaseY();
int curr_x = start.getX() - base_x, curr_y = start.getY() - base_y;
int dest_x = end.getX() - base_x, dest_y = end.getY() - base_y;
// load client data
flags = walking.getCollisionFlags(game.getPlane());
RSTile offset = walking.getCollisionOffset(game.getPlane());
off_x = offset.getX();
off_y = offset.getY();
// loaded region only
if (flags == null || curr_x < 0 || curr_y < 0 ||
curr_x >= flags.length || curr_y >= flags.length ||
dest_x < 0 || dest_y < 0 ||
dest_x >= flags.length || dest_y >= flags.length) {
return null;
}
// structs
HashSet<Node> open = new HashSet<Node>();
HashSet<Node> closed = new HashSet<Node>();
Node curr = new Node(curr_x, curr_y);
Node dest = new Node(dest_x, dest_y);
curr.f = heuristic(curr, dest);
open.add(curr);
// search
while (!open.isEmpty()) {
curr = lowest_f(open);
if (curr.equals(dest)) {
// reconstruct from pred tree
return path(curr, base_x, base_y);
}
open.remove(curr);
closed.add(curr);
for (Node next : successors(curr)) {
if (!closed.contains(next)) {
double t = curr.g + dist(curr, next);
boolean use_t = false;
if (!open.contains(next)) {
open.add(next);
use_t = true;
} else if (t < next.g) {
use_t = true;
}
if (use_t) {
next.prev = curr;
next.g = t;
next.f = t + heuristic(next, dest);
}
}
}
}
// no path
return null;
}
private double heuristic(Node start, Node end) {
double dx = start.x - end.x;
double dy = start.y - end.y;
if (dx < 0) dx = -dx;
if (dy < 0) dy = -dy;
return dx < dy ? dy : dx;
//double diagonal = dx > dy ? dy : dx;
//double manhattan = dx + dy;
//return 1.41421356 * diagonal + (manhattan - 2 * diagonal);
}
private double dist(Node start, Node end) {
if (start.x != end.x && start.y != end.y) {
return 1.41421356;
} else {
return 1.0;
}
}
private Node lowest_f(Set<Node> open) {
Node best = null;
for (Node t : open) {
if (best == null || t.f < best.f) {
best = t;
}
}
return best;
}
private RSTile[] path(Node end, int base_x, int base_y) {
LinkedList<RSTile> path = new LinkedList<RSTile>();
Node p = end;
while (p != null) {
path.addFirst(p.toRSTile(base_x, base_y));
p = p.prev;
}
return path.toArray(new RSTile[path.size()]);
}
private java.util.List<Node> successors(Node t) {
LinkedList<Node> tiles = new LinkedList<Node>();
int x = t.x, y = t.y;
int f_x = x - off_x, f_y = y - off_y;
int here = flags[f_x][f_y];
if (f_y > 0 && (here & WALL_SOUTH) == 0 && (flags[f_x][f_y - 1] & BLOCKED) == 0) {
tiles.add(new Node(x, y - 1));
}
if (f_x > 0 && (here & WALL_WEST) == 0 && (flags[f_x - 1][f_y] & BLOCKED) == 0) {
tiles.add(new Node(x - 1, y));
}
if (f_y < 103 && (here & WALL_NORTH) == 0 && (flags[f_x][f_y + 1] & BLOCKED) == 0) {
tiles.add(new Node(x, y + 1));
}
if (f_x < 103 && (here & WALL_EAST) == 0 && (flags[f_x + 1][f_y] & BLOCKED) == 0) {
tiles.add(new Node(x + 1, y));
}
if (f_x > 0 && f_y > 0 && (here & (WALL_SOUTH_WEST | WALL_SOUTH | WALL_WEST)) == 0
&& (flags[f_x - 1][f_y - 1] & BLOCKED) == 0
&& (flags[f_x][f_y - 1] & (BLOCKED | WALL_WEST)) == 0
&& (flags[f_x - 1][f_y] & (BLOCKED | WALL_SOUTH)) == 0) {
tiles.add(new Node(x - 1, y - 1));
}
if (f_x > 0 && f_y < 103 && (here & (WALL_NORTH_WEST | WALL_NORTH | WALL_WEST)) == 0
&& (flags[f_x - 1][f_y + 1] & BLOCKED) == 0
&& (flags[f_x][f_y + 1] & (BLOCKED | WALL_WEST)) == 0
&& (flags[f_x - 1][f_y] & (BLOCKED | WALL_NORTH)) == 0) {
tiles.add(new Node(x - 1, y + 1));
}
if (f_x < 103 && f_y > 0 && (here & (WALL_SOUTH_EAST | WALL_SOUTH | WALL_EAST)) == 0
&& (flags[f_x + 1][f_y - 1] & BLOCKED) == 0
&& (flags[f_x][f_y - 1] & (BLOCKED | WALL_EAST)) == 0
&& (flags[f_x + 1][f_y] & (BLOCKED | WALL_SOUTH)) == 0) {
tiles.add(new Node(x + 1, y - 1));
}
if (f_x > 0 && f_y < 103 && (here & (WALL_NORTH_EAST | WALL_NORTH | WALL_EAST)) == 0
&& (flags[f_x + 1][f_y + 1] & BLOCKED) == 0
&& (flags[f_x][f_y + 1] & (BLOCKED | WALL_EAST)) == 0
&& (flags[f_x + 1][f_y] & (BLOCKED | WALL_NORTH)) == 0) {
tiles.add(new Node(x + 1, y + 1));
}
return tiles;
}
}More Info: http://villavu.com/forum/showpost.php?p=793691&postcount=9
It would be awesome if someone could write this for Simba + Reflection :)