source: lost-perception/astar/QuadTree.java

Last change on this file 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: 5.3 KB
Line 
1package astar;
2
3import java.awt.Graphics;
4import java.awt.Rectangle;
5
6import main.MapObject;
7
8public class QuadTree {
9 private QuadTree[] arr;
10 private AStarNode node;
11 private int depth;
12 private int x;
13 private int y;
14 private int width;
15 private int height;
16
17 public QuadTree(final QuadTree tree1, final QuadTree tree2, final QuadTree tree3, final QuadTree tree4) {
18 (this.arr = new QuadTree[4])[0] = tree1;
19 this.arr[1] = tree2;
20 this.arr[2] = tree3;
21 this.arr[3] = tree4;
22 this.depth = 1;
23 tree1.depth = this.depth + 1;
24 tree2.depth = this.depth + 1;
25 tree3.depth = this.depth + 1;
26 tree4.depth = this.depth + 1;
27 this.node = null;
28 }
29
30 public QuadTree(final int x, final int y, final int width, final int height) {
31 this.arr = null;
32 this.node = new AStarNode(this);
33 this.x = x;
34 this.y = y;
35 this.width = width;
36 this.height = height;
37 this.depth = 1;
38 }
39
40 public int getX() {
41 return this.x;
42 }
43
44 public int getY() {
45 return this.y;
46 }
47
48 public int getHeight() {
49 return this.height;
50 }
51
52 public int getWidth() {
53 return this.width;
54 }
55
56 public int getDepth() {
57 return this.depth;
58 }
59
60 public boolean isLeaf() {
61 return this.arr == null;
62 }
63
64 public QuadTree[] getChildren() {
65 return this.arr;
66 }
67
68 public AStarNode getNode() {
69 return this.node;
70 }
71
72 public void expandTree(final QuadTree tree1, final QuadTree tree2, final QuadTree tree3, final QuadTree tree4) {
73 if (!this.isLeaf()) {
74 return;
75 }
76 (this.arr = new QuadTree[4])[0] = tree1;
77 this.arr[1] = tree2;
78 this.arr[2] = tree3;
79 this.arr[3] = tree4;
80 tree1.depth = this.depth + 1;
81 tree2.depth = this.depth + 1;
82 tree3.depth = this.depth + 1;
83 tree4.depth = this.depth + 1;
84 this.node = null;
85 }
86
87 public void addObstacle(final MapObject o) {
88 if (o.getBound() == null) {
89 return;
90 }
91 if (!this.isLeaf()) {
92 this.arr[0].addObstacle(o);
93 this.arr[1].addObstacle(o);
94 this.arr[2].addObstacle(o);
95 this.arr[3].addObstacle(o);
96 return;
97 }
98 final Rectangle square = new Rectangle(this.getX(), this.getY(), this.getWidth(), this.getHeight());
99 if (!this.getNode().passable || !o.getBound().intersects(square, o)) {
100 return;
101 }
102 if (this.depth == 4 || o.getBound().contains(square, o)) {
103 this.getNode().passable = false;
104 return;
105 }
106 final int newWidth = this.getWidth() / 2;
107 final int newHeight = this.getHeight() / 2;
108 final QuadTree qt1 = new QuadTree(this.getX(), this.getY(), newWidth, newHeight);
109 final QuadTree qt2 = new QuadTree(this.getX() + newWidth, this.getY(), newWidth, newHeight);
110 final QuadTree qt3 = new QuadTree(this.getX(), this.getY() + newHeight, newWidth, newHeight);
111 final QuadTree qt4 = new QuadTree(this.getX() + newWidth, this.getY() + newHeight, newWidth, newHeight);
112 this.expandTree(qt1, qt2, qt3, qt4);
113 this.arr[0].addObstacle(o);
114 this.arr[1].addObstacle(o);
115 this.arr[2].addObstacle(o);
116 this.arr[3].addObstacle(o);
117 }
118
119 public void coalesce() {
120 if (this.isLeaf()) {
121 return;
122 }
123 this.arr[0].coalesce();
124 this.arr[1].coalesce();
125 this.arr[2].coalesce();
126 this.arr[3].coalesce();
127 if (!this.arr[0].isLeaf() || this.arr[0].node.passable) {
128 return;
129 }
130 if (!this.arr[1].isLeaf() || this.arr[1].node.passable) {
131 return;
132 }
133 if (!this.arr[2].isLeaf() || this.arr[2].node.passable) {
134 return;
135 }
136 if (!this.arr[3].isLeaf() || this.arr[3].node.passable) {
137 return;
138 }
139 this.x = this.arr[0].x;
140 this.y = this.arr[0].y;
141 this.width = this.arr[0].width * 2;
142 this.height = this.arr[0].height * 2;
143 this.arr = null;
144 this.node = new AStarNode(this);
145 this.node.passable = false;
146 }
147
148 public void draw(final Graphics g, final int x, final int y, final boolean fill) {
149 if (this.isLeaf()) {
150 if (fill) {
151 g.fillRect(this.getX() + x, this.getY() + y, this.getWidth(), this.getHeight());
152 }
153 else {
154 g.drawRect(this.getX() + x, this.getY() + y, this.getWidth(), this.getHeight());
155 }
156 }
157 else {
158 this.arr[0].draw(g, x, y, fill);
159 this.arr[1].draw(g, x, y, fill);
160 this.arr[2].draw(g, x, y, fill);
161 this.arr[3].draw(g, x, y, fill);
162 }
163 }
164
165 public void drawBlocked(final Graphics g, final int x, final int y) {
166 if (this.isLeaf()) {
167 if (!this.getNode().passable) {
168 g.fillRect(this.getX() + x, this.getY() + y, this.getWidth(), this.getHeight());
169 }
170 }
171 else {
172 this.arr[0].drawBlocked(g, x, y);
173 this.arr[1].drawBlocked(g, x, y);
174 this.arr[2].drawBlocked(g, x, y);
175 this.arr[3].drawBlocked(g, x, y);
176 }
177 }
178}
Note: See TracBrowser for help on using the repository browser.