1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:

package infoboard;

import java.util.HashMap;

public class Field implements Comparable<Field> {
	public int x; //so habe ich dir das nicht gegeben. Bei mir war das private
	public int y;
	private HashMap<Field, Double> neighbors = new HashMap<Field, Double>();
	private double f;
	private double g;
	public boolean blocked;
	private Field predecessor;

	public Field(int x, int y, boolean blocked) {
		this.x = x;
		this.y = y;
		this.blocked = blocked;
	}

	public void addNeighbor(Field neighbor) {
		double delta = Math.sqrt(((this.x - neighbor.x) * (this.x - neighbor.x)) + ((this.y - neighbor.y) * (this.y - neighbor.y)));
		if (!neighbor.blocked && this != neighbor) {
			neighbors.put(neighbor, delta);
		}
	}

	public HashMap<Field, Double> getNeighbors() {
		return neighbors;
	}

	public double getF() {
		return f;
	}

	public void setF(double f) {
		this.f = f;
	}

	public double getG() {
		return g;
	}

	public void setG(double g) {
		this.g = g;
	}

	public Field getPredecessor() {
		return predecessor;
	}

	public void setPredecessor(Field predecessor) {
		this.predecessor = predecessor;
	}

	public double calch(Field target) {
		double dx = Math.abs(this.x - target.x);
		double dy = Math.abs(this.y - target.y);
		return (Math.sqrt(2) - 1) * Math.min(dx, dy) + Math.max(dx, dy);
	}

	@Override
	public String toString() {
		return x + "/" + y;
	}

	@Override
	public int compareTo(Field o) {
		return 4 * (int) Math.signum(this.f - o.f) + 2 * (int) Math.signum(this.x - o.x) + (int) Math.signum(this.y - o.y);
	}
}

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:

package infoboard;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import java.util.TreeSet;

public class AStar {
	public static ArrayList<Field> AStaralgorithm(int xFrom, int yFrom, int xTo, int yTo, boolean[][] grid, int width, int height) {
		Field[][] fields = new Field[width][height];
		for (int x = 0; x < width; x += 1) {
			for (int y = 0; y < height; y += 1) {
				fields[x][y] = new Field(x, y, grid[x][y]);
			}
		}
		for (int x = 0; x < width; x += 1) {
			for (int y = 0; y < height; y += 1) {
				for (int dx = -1; dx <= 1; dx += 1) {
					for (int dy = -1; dy <= 1; dy += 1) {
						if (x + dx < 0 || x + dx >= width || y + dy < 0 || y + dy >= height) {
							continue;
						}
						if (!fields[x + dx][y].blocked || !fields[x][y + dy].blocked)
							fields[x][y].addNeighbor(fields[x + dx][y + dy]);
					}
				}
			}
		}
		TreeSet<Field> openList = new TreeSet<Field>();
		Set<Field> closedList = new HashSet<Field>();
		openList.add(fields[xFrom][yFrom]);
		Field target = fields[xTo][yTo];
		while (!openList.isEmpty()) {
			Field current = openList.first();
			openList.remove(current);
			if (current == target) {
				ArrayList<Field> result = new ArrayList<Field>();
				Field tmp = target;
				while (tmp != null) {
					result.add(0, tmp);
					tmp = tmp.getPredecessor();
				}
				return result;
			}
			closedList.add(current);
			expandNode(current, target, openList, closedList);
		}
		return null;
	}

	public static void expandNode(Field current, Field target, Set<Field> openList, Set<Field> closedList) {
		HashMap<Field, Double> successors = current.getNeighbors();
		Iterator<Entry<Field, Double>> it = successors.entrySet().iterator();
		while (it.hasNext()) {
			Map.Entry<Field, Double> pair = it.next();
			Field successor = pair.getKey();
			if (closedList.contains(successor)) {
				continue;
			}
			double tentative_g = current.getG() + pair.getValue();
			if (openList.contains(successor) && tentative_g >= successor.getG()) {
				continue;
			}
			successor.setPredecessor(current);
			successor.setG(tentative_g);
			double f = tentative_g + successor.calch(target);
			openList.remove(successor);
			successor.setF(f);
			openList.add(successor);
		}
	}
}