source: lost-perception/astar/AStarMap.java@ 5db343b

Last change on this file since 5db343b was ebd3538, checked in by Dmitry Portnoy <dmitry.portnoy@…>, 6 years ago

Initial commit. This codebase for the Lost Perception game was created by decompiling code from a jar file.
  • Property mode set to 100644
File size: 9.6 KB
Line 
1package astar;
2
3import java.awt.Rectangle;
4import java.awt.Shape;
5import java.awt.geom.AffineTransform;
6import java.util.Collection;
7import java.util.LinkedList;
8import java.awt.geom.Point2D;
9import java.awt.Point;
10
11import main.MapObject;
12
13import collision.Bound;
14
15public class AStarMap {
16 public QuadTree[][] map;
17 private int width;
18 private int height;
19 public static final int ROOT_SIZE = 40;
20 public static final int MAX_TREE_DEPTH = 4;
21
22 public AStarMap(final int width, final int height) {
23 this.map = new QuadTree[width][height];
24 this.width = width;
25 this.height = height;
26 for (int x = 0; x < width; ++x) {
27 for (int y = 0; y < height; ++y) {
28 this.map[x][y] = new QuadTree(x * 40, y * 40, 40, 40);
29 }
30 }
31 }
32
33 public AStarNode getNode(final int x, final int y) {
34 return this.getLeaf(this.map[x / 40][y / 40], x, y);
35 }
36
37 public boolean validPath(final Point source, final Point dest) {
38 final double frac = 5.0 / source.distance(dest);
39 final int xTotal = dest.x - source.x;
40 final int yTotal = dest.y - source.y;
41 for (double xLen = frac * xTotal, yLen = frac * yTotal, xCur = 0.0, yCur = 0.0; Math.abs(xCur) < Math.abs(xTotal); xCur += xLen, yCur += yLen) {
42 final AStarNode curNode = this.getNode((int)xCur + source.x, (int)yCur + source.y);
43 if (!curNode.passable) {
44 return false;
45 }
46 }
47 return true;
48 }
49
50 private AStarNode getLeaf(final QuadTree qt, final int x, final int y) {
51 if (qt.isLeaf()) {
52 return qt.getNode();
53 }
54 int child = -1;
55 if (x < qt.getX() + qt.getWidth() / 2) {
56 if (y < qt.getY() + qt.getHeight() / 2) {
57 child = 0;
58 }
59 else {
60 child = 2;
61 }
62 }
63 else if (y < qt.getY() + qt.getHeight() / 2) {
64 child = 1;
65 }
66 else {
67 child = 3;
68 }
69 return this.getLeaf(qt.getChildren()[child], x, y);
70 }
71
72 public void generateAllNeighbors() {
73 for (int x = 0; x < this.width; ++x) {
74 for (int y = 0; y < this.height; ++y) {
75 this.generateNeighborsHelper(this.map[x][y]);
76 }
77 }
78 }
79
80 public void generateNeighborsHelper(final QuadTree qt) {
81 if (qt.isLeaf()) {
82 qt.getNode().neighbors = this.getNeighbors(qt.getNode());
83 }
84 else {
85 this.generateNeighborsHelper(qt.getChildren()[0]);
86 this.generateNeighborsHelper(qt.getChildren()[1]);
87 this.generateNeighborsHelper(qt.getChildren()[2]);
88 this.generateNeighborsHelper(qt.getChildren()[3]);
89 }
90 }
91
92 public LinkedList<AStarNode> getNeighbors(final AStarNode n) {
93 final LinkedList<AStarNode> neighbors = new LinkedList<AStarNode>();
94 final int xTop = n.getParent().getX() / 40;
95 final int yTop = (n.getParent().getY() - 1) / 40;
96 if (xTop >= 0 && xTop < this.width && yTop >= 0 && yTop < this.height) {
97 if (1 <= xTop) {
98 neighbors.addAll(this.getTopNeighbors(this.map[xTop - 1][yTop], n));
99 }
100 neighbors.addAll(this.getTopNeighbors(this.map[xTop][yTop], n));
101 if (xTop < this.width - 1) {
102 neighbors.addAll(this.getTopNeighbors(this.map[xTop + 1][yTop], n));
103 }
104 }
105 final int xBottom = n.getParent().getX() / 40;
106 final int yBottom = (n.getParent().getY() + n.getParent().getHeight()) / 40;
107 if (xBottom >= 0 && xBottom < this.width && yBottom >= 0 && yBottom < this.height) {
108 if (1 <= xBottom) {
109 neighbors.addAll(this.getBottomNeighbors(this.map[xBottom - 1][yBottom], n));
110 }
111 neighbors.addAll(this.getBottomNeighbors(this.map[xBottom][yBottom], n));
112 if (xBottom < this.width - 1) {
113 neighbors.addAll(this.getBottomNeighbors(this.map[xBottom + 1][yBottom], n));
114 }
115 }
116 final int xLeft = (n.getParent().getX() - 1) / 40;
117 final int yLeft = n.getParent().getY() / 40;
118 if (xLeft >= 0 && xLeft < this.width && yLeft >= 0 && yLeft < this.height) {
119 neighbors.addAll(this.getLeftNeighbors(this.map[xLeft][yLeft], n));
120 }
121 final int xRight = (n.getParent().getX() + n.getParent().getWidth()) / 40;
122 final int yRight = n.getParent().getY() / 40;
123 if (xRight >= 0 && xRight < this.width && yRight >= 0 && yRight < this.height) {
124 neighbors.addAll(this.getRightNeighbors(this.map[xRight][yRight], n));
125 }
126 return neighbors;
127 }
128
129 private LinkedList<AStarNode> getTopNeighbors(final QuadTree p, final AStarNode n) {
130 final LinkedList<AStarNode> neighbors = new LinkedList<AStarNode>();
131 final int y = n.getParent().getY();
132 if (p.isLeaf()) {
133 final int xMin = n.getParent().getX();
134 final int xMax = xMin + n.getParent().getWidth();
135 if (p.getY() + p.getHeight() == y && xMax >= p.getX() && p.getX() + p.getWidth() >= xMin) {
136 neighbors.add(p.getNode());
137 }
138 }
139 else if (y <= p.getY() + p.getHeight() / 2) {
140 neighbors.addAll(this.getTopNeighbors(p.getChildren()[0], n));
141 neighbors.addAll(this.getTopNeighbors(p.getChildren()[1], n));
142 }
143 else {
144 neighbors.addAll(this.getTopNeighbors(p.getChildren()[2], n));
145 neighbors.addAll(this.getTopNeighbors(p.getChildren()[3], n));
146 }
147 return neighbors;
148 }
149
150 private LinkedList<AStarNode> getBottomNeighbors(final QuadTree p, final AStarNode n) {
151 final LinkedList<AStarNode> neighbors = new LinkedList<AStarNode>();
152 final int y = n.getParent().getY() + n.getParent().getHeight();
153 if (p.isLeaf()) {
154 final int xMin = n.getParent().getX();
155 final int xMax = xMin + n.getParent().getWidth();
156 if (p.getY() == y && xMax >= p.getX() && p.getX() + p.getWidth() >= xMin) {
157 neighbors.add(p.getNode());
158 }
159 }
160 else if (y < p.getY() + p.getHeight() / 2) {
161 neighbors.addAll(this.getBottomNeighbors(p.getChildren()[0], n));
162 neighbors.addAll(this.getBottomNeighbors(p.getChildren()[1], n));
163 }
164 else {
165 neighbors.addAll(this.getBottomNeighbors(p.getChildren()[2], n));
166 neighbors.addAll(this.getBottomNeighbors(p.getChildren()[3], n));
167 }
168 return neighbors;
169 }
170
171 private LinkedList<AStarNode> getLeftNeighbors(final QuadTree p, final AStarNode n) {
172 final LinkedList<AStarNode> neighbors = new LinkedList<AStarNode>();
173 final int x = n.getParent().getX();
174 if (p.isLeaf()) {
175 final int yMin = n.getParent().getY();
176 final int yMax = yMin + n.getParent().getHeight();
177 if (p.getX() + p.getWidth() == x && yMax >= p.getY() && p.getY() + p.getHeight() >= yMin) {
178 neighbors.add(p.getNode());
179 }
180 }
181 else if (x <= p.getX() + p.getWidth() / 2) {
182 neighbors.addAll(this.getLeftNeighbors(p.getChildren()[0], n));
183 neighbors.addAll(this.getLeftNeighbors(p.getChildren()[2], n));
184 }
185 else {
186 neighbors.addAll(this.getLeftNeighbors(p.getChildren()[1], n));
187 neighbors.addAll(this.getLeftNeighbors(p.getChildren()[3], n));
188 }
189 return neighbors;
190 }
191
192 private LinkedList<AStarNode> getRightNeighbors(final QuadTree p, final AStarNode n) {
193 final LinkedList<AStarNode> neighbors = new LinkedList<AStarNode>();
194 final int x = n.getParent().getX() + n.getParent().getWidth();
195 if (p.isLeaf()) {
196 final int yMin = n.getParent().getY();
197 final int yMax = yMin + n.getParent().getHeight();
198 if (p.getX() == x && yMax >= p.getY() && p.getY() + p.getHeight() >= yMin) {
199 neighbors.add(p.getNode());
200 }
201 }
202 else if (x < p.getX() + p.getWidth() / 2) {
203 neighbors.addAll(this.getRightNeighbors(p.getChildren()[0], n));
204 neighbors.addAll(this.getRightNeighbors(p.getChildren()[2], n));
205 }
206 else {
207 neighbors.addAll(this.getRightNeighbors(p.getChildren()[1], n));
208 neighbors.addAll(this.getRightNeighbors(p.getChildren()[3], n));
209 }
210 return neighbors;
211 }
212
213 public void addObstacle(final MapObject o) {
214 if (o.getBound() == null) {
215 return;
216 }
217 final Bound realBound = new Bound(o.getBound().createTransformedArea(new AffineTransform(1.0f, 0.0f, 0.0f, 1.0f, o.getBoundX(), o.getBoundY())));
218 final Rectangle rect = realBound.getBounds();
219 int lowXBound = rect.x / 40;
220 int lowYBound = rect.y / 40;
221 int highXBound = (rect.x + rect.width) / 40 + 1;
222 int highYBound = (rect.y + rect.height) / 40 + 1;
223 if (lowXBound < 0) {
224 lowXBound = 0;
225 }
226 if (highXBound > this.width - 1) {
227 highXBound = this.width - 1;
228 }
229 if (lowYBound < 0) {
230 lowYBound = 0;
231 }
232 if (highYBound > this.height - 1) {
233 highYBound = this.height - 1;
234 }
235 for (int x = lowXBound; x <= highXBound; ++x) {
236 for (int y = lowYBound; y <= highYBound; ++y) {
237 this.map[x][y].addObstacle(o);
238 }
239 }
240 }
241
242 public void coalesceQuadTrees() {
243 for (int x = 0; x < this.width; ++x) {
244 for (int y = 0; y < this.height; ++y) {
245 this.map[x][y].coalesce();
246 }
247 }
248 }
249}
Note: See TracBrowser for help on using the repository browser.