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:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:

package infoboard;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;

public class Main
{
	public static void main(String[] args)
	{
		int n = 20;
		boolean[][] grid = new boolean[2 * n][n];
		for (int i = 3; i <= 15; i++) {
			grid[i][15] = true;
			grid[15][i] = true;
		}
		ArrayList<Field> path = AStar(3, 3, 30, 15, grid, 2 * n, n);
		if (path != null) {
			for (Field f : path)
				System.out.println(f);
		}
	}

	public static ArrayList<Field> AStar(int xFrom, int yFrom, int xTo, int yTo, boolean[][] grid, int w, int h) {
		//create Fields
		Field[][] fields = new Field[w][h];
		for (int x = 0; x < w; x++) {
			for (int y = 0; y < h; y++) {
				fields[x][y] = new Field(x, y, grid[x][y]);
			}
		}
		//add neighbors
		for (int x = 0; x < w; x++) {
			for (int y = 0; y < h; y++) {
				for (int dx = -1; dx <= 1; dx++) {
					for (int dy = -1; dy <= 1; dy++) {
						if (x + dx < 0 || x + dx >= w || y + dy < 0 || y + dy >= h)
							continue;
						fields[x][y].addNeighbor(fields[x + dx][y + dy]);
					}
				}
			}
		}

		//init
		HashSet<Field> openList = new HashSet<Field>(); //HashSet nicht ideal
		HashSet<Field> closedList = new HashSet<Field>();
		openList.add(fields[xFrom][yFrom]);
		Field target = fields[xTo][yTo];

		while (!openList.isEmpty()) {
			//find min in openList
			Field current = null;
			for (Field f : openList) {
				if (current == null || current.getF() > f.getF()) {
					current = f;
				}
			}
			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;
	}

	private static void expandNode(Field current, Field target, HashSet<Field> openList, HashSet<Field> closedList) {
		HashMap<Field, Double> successors = current.getNeighbors();
		Iterator it = successors.entrySet().iterator();
		while (it.hasNext()) {
			Map.Entry<Field, Double> pair = (Map.Entry<Field, Double>) 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);
			successor.setF(f);
			openList.add(successor);
		}
	}
}

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:

package infoboard;

import java.util.HashMap;

public class Field {

	private int x;
	private int y;
	private boolean blocked;
	private HashMap<Field, Double> neighbors = new HashMap<Field, Double>();
	private double f;
	private double g;
	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) {
		if (!neighbor.blocked && this != neighbor) {
			neighbors.put(neighbor, Math.sqrt(
					(this.x - neighbor.x) * (this.x - neighbor.x) +
							(this.y - neighbor.y) * (this.y - neighbor.y)));
		}
	}

	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) {
		int dx = Math.abs(this.x - target.x);
		int 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;
	}
}