aboutsummaryrefslogtreecommitdiff
path: root/Minecraft.World/PathFinder.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'Minecraft.World/PathFinder.cpp')
-rw-r--r--Minecraft.World/PathFinder.cpp271
1 files changed, 271 insertions, 0 deletions
diff --git a/Minecraft.World/PathFinder.cpp b/Minecraft.World/PathFinder.cpp
new file mode 100644
index 00000000..878c74f1
--- /dev/null
+++ b/Minecraft.World/PathFinder.cpp
@@ -0,0 +1,271 @@
+#include "stdafx.h"
+#include "net.minecraft.world.entity.h"
+#include "net.minecraft.world.level.h"
+#include "net.minecraft.world.level.material.h"
+#include "net.minecraft.world.level.tile.h"
+#include "net.minecraft.world.phys.h"
+#include "BinaryHeap.h"
+#include "Node.h"
+#include "Path.h"
+#include "PathFinder.h"
+
+PathFinder::PathFinder(LevelSource *level, bool canPassDoors, bool canOpenDoors, bool avoidWater, bool canFloat)
+{
+ neighbors = new NodeArray(32);
+
+ this->canPassDoors = canPassDoors;
+ this->canOpenDoors = canOpenDoors;
+ this->avoidWater = avoidWater;
+ this->canFloat = canFloat;
+ this->level = level;
+}
+
+PathFinder::~PathFinder()
+{
+ // All the nodes should be uniquely referenced in the nodes map, and everything else should just be duplicate
+ // references to the same things, so just need to destroy their containers
+ delete [] neighbors->data;
+ delete neighbors;
+ AUTO_VAR(itEnd, nodes.end());
+ for( AUTO_VAR(it, nodes.begin()); it != itEnd; it++ )
+ {
+ delete it->second;
+ }
+}
+
+Path *PathFinder::findPath(Entity *from, Entity *to, float maxDist)
+{
+ return findPath(from, to->x, to->bb->y0, to->z, maxDist);
+}
+
+Path *PathFinder::findPath(Entity *from, int x, int y, int z, float maxDist)
+{
+ return findPath(from, x + 0.5f, y + 0.5f, z + 0.5f, maxDist);
+}
+
+Path *PathFinder::findPath(Entity *e, double xt, double yt, double zt, float maxDist)
+{
+ openSet.clear();
+ nodes.clear();
+
+ bool resetAvoidWater = avoidWater;
+ int startY = Mth::floor(e->bb->y0 + 0.5f);
+ if (canFloat && e->isInWater())
+ {
+ startY = (int) (e->bb->y0);
+ int tileId = level->getTile((int) Mth::floor(e->x), startY, (int) Mth::floor(e->z));
+ while (tileId == Tile::water_Id || tileId == Tile::calmWater_Id)
+ {
+ ++startY;
+ tileId = level->getTile((int) Mth::floor(e->x), startY, (int) Mth::floor(e->z));
+ }
+ resetAvoidWater = avoidWater;
+ avoidWater = false;
+ } else startY = Mth::floor(e->bb->y0 + 0.5f);
+
+ Node *from = getNode((int) floor(e->bb->x0), startY, (int) floor(e->bb->z0));
+ Node *to = getNode((int) floor(xt - e->bbWidth / 2), (int) floor(yt), (int) floor(zt - e->bbWidth / 2));
+
+ Node *size = new Node((int) floor(e->bbWidth + 1), (int) floor(e->bbHeight + 1), (int) floor(e->bbWidth + 1));
+ Path *path = findPath(e, from, to, size, maxDist);
+ delete size;
+
+ avoidWater = resetAvoidWater;
+ return path;
+}
+
+// function A*(start,goal)
+Path *PathFinder::findPath(Entity *e, Node *from, Node *to, Node *size, float maxDist)
+{
+ from->g = 0;
+ from->h = from->distanceToSqr(to);
+ from->f = from->h;
+
+ openSet.clear();
+ openSet.insert(from);
+
+ Node *closest = from;
+
+ while (!openSet.isEmpty())
+ {
+ Node *x = openSet.pop();
+
+ if (x->equals(to))
+ {
+ return reconstruct_path(from, to);
+ }
+
+ if (x->distanceToSqr(to) < closest->distanceToSqr(to))
+ {
+ closest = x;
+ }
+ x->closed = true;
+
+ int neighborCount = getNeighbors(e, x, size, to, maxDist);
+ for (int i = 0; i < neighborCount; i++)
+ {
+ Node *y = neighbors->data[i];
+
+ float tentative_g_score = x->g + x->distanceToSqr(y);
+ if (!y->inOpenSet() || tentative_g_score < y->g)
+ {
+ y->cameFrom = x;
+ y->g = tentative_g_score;
+ y->h = y->distanceToSqr(to);
+ if (y->inOpenSet())
+ {
+ openSet.changeCost(y, y->g + y->h);
+ }
+ else
+ {
+ y->f = y->g + y->h;
+ openSet.insert(y);
+ }
+ }
+ }
+ }
+
+ if (closest == from) return NULL;
+ return reconstruct_path(from, closest);
+}
+
+int PathFinder::getNeighbors(Entity *entity, Node *pos, Node *size, Node *target, float maxDist)
+{
+ int p = 0;
+
+ int jumpSize = 0;
+ if (isFree(entity, pos->x, pos->y + 1, pos->z, size) == TYPE_OPEN) jumpSize = 1;
+
+ Node *n = getNode(entity, pos->x, pos->y, pos->z + 1, size, jumpSize);
+ Node *w = getNode(entity, pos->x - 1, pos->y, pos->z, size, jumpSize);
+ Node *e = getNode(entity, pos->x + 1, pos->y, pos->z, size, jumpSize);
+ Node *s = getNode(entity, pos->x, pos->y, pos->z - 1, size, jumpSize);
+
+ if (n != NULL && !n->closed && n->distanceTo(target) < maxDist) neighbors->data[p++] = n;
+ if (w != NULL && !w->closed && w->distanceTo(target) < maxDist) neighbors->data[p++] = w;
+ if (e != NULL && !e->closed && e->distanceTo(target) < maxDist) neighbors->data[p++] = e;
+ if (s != NULL && !s->closed && s->distanceTo(target) < maxDist) neighbors->data[p++] = s;
+
+ return p;
+}
+
+Node *PathFinder::getNode(Entity *entity, int x, int y, int z, Node *size, int jumpSize)
+{
+ Node *best = NULL;
+ int pathType = isFree(entity, x, y, z, size);
+ if (pathType == TYPE_WALKABLE) return getNode(x, y, z);
+ if (pathType == TYPE_OPEN) best = getNode(x, y, z);
+ if (best == NULL && jumpSize > 0 && pathType != TYPE_FENCE && pathType != TYPE_TRAP && isFree(entity, x, y + jumpSize, z, size) == TYPE_OPEN)
+ {
+ best = getNode(x, y + jumpSize, z);
+ y += jumpSize;
+ }
+
+ if (best != NULL)
+ {
+ int drop = 0;
+ int cost = 0;
+ while (y > 0)
+ {
+ cost = isFree(entity, x, y - 1, z, size);
+ if (avoidWater && cost == TYPE_WATER) return NULL;
+ if (cost != TYPE_OPEN) break;
+ // fell too far?
+ if (++drop >= 4) return NULL;
+ y--;
+
+ if (y > 0) best = getNode(x, y, z);
+ }
+ // fell into lava?
+ if (cost == TYPE_LAVA) return NULL;
+ }
+
+ return best;
+}
+
+/*final*/ Node *PathFinder::getNode(int x, int y, int z)
+{
+ int i = Node::createHash(x, y, z);
+ Node *node;
+ AUTO_VAR(it, nodes.find(i));
+ if ( it == nodes.end() )
+ {
+ MemSect(54);
+ node = new Node(x, y, z);
+ MemSect(0);
+ nodes.insert( unordered_map<int, Node *>::value_type(i, node) );
+ }
+ else
+ {
+ node = (*it).second;
+ }
+ return node;
+}
+
+int PathFinder::isFree(Entity *entity, int x, int y, int z, Node *size)
+{
+ return isFree(entity, x, y, z, size, avoidWater, canOpenDoors, canPassDoors);
+}
+
+int PathFinder::isFree(Entity *entity, int x, int y, int z, Node *size, bool avoidWater, bool canOpenDoors, bool canPassDoors)
+{
+ bool walkable = false;
+ for (int xx = x; xx < x + size->x; xx++)
+ for (int yy = y; yy < y + size->y; yy++)
+ for (int zz = z; zz < z + size->z; zz++)
+ {
+ int tileId = entity->level->getTile(xx, yy, zz);
+ if(tileId <= 0) continue;
+ if (tileId == Tile::trapdoor_Id) walkable = true;
+ else if (tileId == Tile::water_Id || tileId == Tile::calmWater_Id)
+ {
+ if (avoidWater) return TYPE_WATER;
+ else walkable = true;
+ }
+ else if (!canPassDoors && tileId == Tile::door_wood_Id)
+ {
+ return TYPE_BLOCKED;
+ }
+
+ Tile *tile = Tile::tiles[tileId];
+ if (tile->isPathfindable(entity->level, xx, yy, zz)) continue;
+ if (canOpenDoors && tileId == Tile::door_wood_Id) continue;
+
+ int renderShape = tile->getRenderShape();
+ if (renderShape == Tile::SHAPE_FENCE || tileId == Tile::fenceGate_Id || renderShape == Tile::SHAPE_WALL) return TYPE_FENCE;
+ if (tileId == Tile::trapdoor_Id) return TYPE_TRAP;
+ Material *m = tile->material;
+ if (m == Material::lava)
+ {
+ if (entity->isInLava()) continue;
+ return TYPE_LAVA;
+ }
+ return TYPE_BLOCKED;
+ }
+
+ return walkable ? TYPE_WALKABLE : TYPE_OPEN;
+}
+
+// function reconstruct_path(came_from,current_node)
+Path *PathFinder::reconstruct_path(Node *from, Node *to)
+{
+ int count = 1;
+ Node *n = to;
+ while (n->cameFrom != NULL)
+ {
+ count++;
+ n = n->cameFrom;
+ }
+
+ NodeArray nodes = NodeArray(count);
+ n = to;
+ nodes.data[--count] = n;
+ while (n->cameFrom != NULL)
+ {
+ n = n->cameFrom;
+ nodes.data[--count] = n;
+ }
+ Path *ret = new Path(nodes);
+ delete [] nodes.data;
+ return ret;
+} \ No newline at end of file
generated by cgit v1.2.3 (git 2.46.0) at 2026-03-21 22:50:05 +0000