ocrm.bsky.social
the game where you go into mines and start crafting! but for consoles (forked directly from smartcmd's github)
1#include "stdafx.h"
2#include "net.minecraft.world.entity.h"
3#include "net.minecraft.world.level.h"
4#include "net.minecraft.world.level.material.h"
5#include "net.minecraft.world.level.tile.h"
6#include "net.minecraft.world.phys.h"
7#include "BinaryHeap.h"
8#include "Node.h"
9#include "Path.h"
10#include "PathFinder.h"
11
12PathFinder::PathFinder(LevelSource *level, bool canPassDoors, bool canOpenDoors, bool avoidWater, bool canFloat)
13{
14 neighbors = new NodeArray(32);
15
16 this->canPassDoors = canPassDoors;
17 this->canOpenDoors = canOpenDoors;
18 this->avoidWater = avoidWater;
19 this->canFloat = canFloat;
20 this->level = level;
21}
22
23PathFinder::~PathFinder()
24{
25 // All the nodes should be uniquely referenced in the nodes map, and everything else should just be duplicate
26 // references to the same things, so just need to destroy their containers
27 delete [] neighbors->data;
28 delete neighbors;
29 AUTO_VAR(itEnd, nodes.end());
30 for( AUTO_VAR(it, nodes.begin()); it != itEnd; it++ )
31 {
32 delete it->second;
33 }
34}
35
36Path *PathFinder::findPath(Entity *from, Entity *to, float maxDist)
37{
38 return findPath(from, to->x, to->bb->y0, to->z, maxDist);
39}
40
41Path *PathFinder::findPath(Entity *from, int x, int y, int z, float maxDist)
42{
43 return findPath(from, x + 0.5f, y + 0.5f, z + 0.5f, maxDist);
44}
45
46Path *PathFinder::findPath(Entity *e, double xt, double yt, double zt, float maxDist)
47{
48 openSet.clear();
49 nodes.clear();
50
51 bool resetAvoidWater = avoidWater;
52 int startY = Mth::floor(e->bb->y0 + 0.5f);
53 if (canFloat && e->isInWater())
54 {
55 startY = (int) (e->bb->y0);
56 int tileId = level->getTile((int) Mth::floor(e->x), startY, (int) Mth::floor(e->z));
57 while (tileId == Tile::water_Id || tileId == Tile::calmWater_Id)
58 {
59 ++startY;
60 tileId = level->getTile((int) Mth::floor(e->x), startY, (int) Mth::floor(e->z));
61 }
62 resetAvoidWater = avoidWater;
63 avoidWater = false;
64 } else startY = Mth::floor(e->bb->y0 + 0.5f);
65
66 Node *from = getNode((int) floor(e->bb->x0), startY, (int) floor(e->bb->z0));
67 Node *to = getNode((int) floor(xt - e->bbWidth / 2), (int) floor(yt), (int) floor(zt - e->bbWidth / 2));
68
69 Node *size = new Node((int) floor(e->bbWidth + 1), (int) floor(e->bbHeight + 1), (int) floor(e->bbWidth + 1));
70 Path *path = findPath(e, from, to, size, maxDist);
71 delete size;
72
73 avoidWater = resetAvoidWater;
74 return path;
75}
76
77// function A*(start,goal)
78Path *PathFinder::findPath(Entity *e, Node *from, Node *to, Node *size, float maxDist)
79{
80 from->g = 0;
81 from->h = from->distanceToSqr(to);
82 from->f = from->h;
83
84 openSet.clear();
85 openSet.insert(from);
86
87 Node *closest = from;
88
89 while (!openSet.isEmpty())
90 {
91 Node *x = openSet.pop();
92
93 if (x->equals(to))
94 {
95 return reconstruct_path(from, to);
96 }
97
98 if (x->distanceToSqr(to) < closest->distanceToSqr(to))
99 {
100 closest = x;
101 }
102 x->closed = true;
103
104 int neighborCount = getNeighbors(e, x, size, to, maxDist);
105 for (int i = 0; i < neighborCount; i++)
106 {
107 Node *y = neighbors->data[i];
108
109 float tentative_g_score = x->g + x->distanceToSqr(y);
110 if (!y->inOpenSet() || tentative_g_score < y->g)
111 {
112 y->cameFrom = x;
113 y->g = tentative_g_score;
114 y->h = y->distanceToSqr(to);
115 if (y->inOpenSet())
116 {
117 openSet.changeCost(y, y->g + y->h);
118 }
119 else
120 {
121 y->f = y->g + y->h;
122 openSet.insert(y);
123 }
124 }
125 }
126 }
127
128 if (closest == from) return NULL;
129 return reconstruct_path(from, closest);
130}
131
132int PathFinder::getNeighbors(Entity *entity, Node *pos, Node *size, Node *target, float maxDist)
133{
134 int p = 0;
135
136 int jumpSize = 0;
137 if (isFree(entity, pos->x, pos->y + 1, pos->z, size) == TYPE_OPEN) jumpSize = 1;
138
139 Node *n = getNode(entity, pos->x, pos->y, pos->z + 1, size, jumpSize);
140 Node *w = getNode(entity, pos->x - 1, pos->y, pos->z, size, jumpSize);
141 Node *e = getNode(entity, pos->x + 1, pos->y, pos->z, size, jumpSize);
142 Node *s = getNode(entity, pos->x, pos->y, pos->z - 1, size, jumpSize);
143
144 if (n != NULL && !n->closed && n->distanceTo(target) < maxDist) neighbors->data[p++] = n;
145 if (w != NULL && !w->closed && w->distanceTo(target) < maxDist) neighbors->data[p++] = w;
146 if (e != NULL && !e->closed && e->distanceTo(target) < maxDist) neighbors->data[p++] = e;
147 if (s != NULL && !s->closed && s->distanceTo(target) < maxDist) neighbors->data[p++] = s;
148
149 return p;
150}
151
152Node *PathFinder::getNode(Entity *entity, int x, int y, int z, Node *size, int jumpSize)
153{
154 Node *best = NULL;
155 int pathType = isFree(entity, x, y, z, size);
156 if (pathType == TYPE_WALKABLE) return getNode(x, y, z);
157 if (pathType == TYPE_OPEN) best = getNode(x, y, z);
158 if (best == NULL && jumpSize > 0 && pathType != TYPE_FENCE && pathType != TYPE_TRAP && isFree(entity, x, y + jumpSize, z, size) == TYPE_OPEN)
159 {
160 best = getNode(x, y + jumpSize, z);
161 y += jumpSize;
162 }
163
164 if (best != NULL)
165 {
166 int drop = 0;
167 int cost = 0;
168 while (y > 0)
169 {
170 cost = isFree(entity, x, y - 1, z, size);
171 if (avoidWater && cost == TYPE_WATER) return NULL;
172 if (cost != TYPE_OPEN) break;
173 // fell too far?
174 if (++drop >= 4) return NULL; // 4J - rolling this back to pre-java 1.6.4 version as we're suspicious of the performance implications of this
175// if (drop++ >= entity->getMaxFallDistance()) return NULL;
176 y--;
177
178 if (y > 0) best = getNode(x, y, z);
179 }
180 // fell into lava?
181 if (cost == TYPE_LAVA) return NULL;
182 }
183
184 return best;
185}
186
187/*final*/ Node *PathFinder::getNode(int x, int y, int z)
188{
189 int i = Node::createHash(x, y, z);
190 Node *node;
191 AUTO_VAR(it, nodes.find(i));
192 if ( it == nodes.end() )
193 {
194 MemSect(54);
195 node = new Node(x, y, z);
196 MemSect(0);
197 nodes.insert( unordered_map<int, Node *>::value_type(i, node) );
198 }
199 else
200 {
201 node = (*it).second;
202 }
203 return node;
204}
205
206int PathFinder::isFree(Entity *entity, int x, int y, int z, Node *size)
207{
208 return isFree(entity, x, y, z, size, avoidWater, canOpenDoors, canPassDoors);
209}
210
211int PathFinder::isFree(Entity *entity, int x, int y, int z, Node *size, bool avoidWater, bool canOpenDoors, bool canPassDoors)
212{
213 bool walkable = false;
214 for (int xx = x; xx < x + size->x; xx++)
215 for (int yy = y; yy < y + size->y; yy++)
216 for (int zz = z; zz < z + size->z; zz++)
217 {
218 int tileId = entity->level->getTile(xx, yy, zz);
219 if(tileId <= 0) continue;
220 if (tileId == Tile::trapdoor_Id) walkable = true;
221 else if (tileId == Tile::water_Id || tileId == Tile::calmWater_Id)
222 {
223 if (avoidWater) return TYPE_WATER;
224 else walkable = true;
225 }
226 else if (!canPassDoors && tileId == Tile::door_wood_Id)
227 {
228 return TYPE_BLOCKED;
229 }
230
231 Tile *tile = Tile::tiles[tileId];
232
233 // 4J Stu - Use new getTileRenderShape passing in the tileId we have already got
234 if (entity->level->getTileRenderShape(tileId) == Tile::SHAPE_RAIL)
235 {
236 int xt = Mth::floor(entity->x);
237 int yt = Mth::floor(entity->y);
238 int zt = Mth::floor(entity->z);
239 if (entity->level->getTileRenderShape(xt, yt, zt) == Tile::SHAPE_RAIL
240 || entity->level->getTileRenderShape(xt, yt - 1, zt) == Tile::SHAPE_RAIL)
241 {
242 continue;
243 }
244 else
245 {
246 return TYPE_FENCE;
247 }
248 }
249
250 if (tile->isPathfindable(entity->level, xx, yy, zz)) continue;
251 if (canOpenDoors && tileId == Tile::door_wood_Id) continue;
252
253 int renderShape = tile->getRenderShape();
254 if (renderShape == Tile::SHAPE_FENCE || tileId == Tile::fenceGate_Id || renderShape == Tile::SHAPE_WALL) return TYPE_FENCE;
255 if (tileId == Tile::trapdoor_Id) return TYPE_TRAP;
256 Material *m = tile->material;
257 if (m == Material::lava)
258 {
259 if (entity->isInLava()) continue;
260 return TYPE_LAVA;
261 }
262 return TYPE_BLOCKED;
263 }
264
265 return walkable ? TYPE_WALKABLE : TYPE_OPEN;
266}
267
268// function reconstruct_path(came_from,current_node)
269Path *PathFinder::reconstruct_path(Node *from, Node *to)
270{
271 int count = 1;
272 Node *n = to;
273 while (n->cameFrom != NULL)
274 {
275 count++;
276 n = n->cameFrom;
277 }
278
279 NodeArray nodes = NodeArray(count);
280 n = to;
281 nodes.data[--count] = n;
282 while (n->cameFrom != NULL)
283 {
284 n = n->cameFrom;
285 nodes.data[--count] = n;
286 }
287 Path *ret = new Path(nodes);
288 delete [] nodes.data;
289 return ret;
290}