diff options
Diffstat (limited to 'src/Mobs/Path.cpp')
| -rw-r--r-- | src/Mobs/Path.cpp | 358 |
1 files changed, 251 insertions, 107 deletions
diff --git a/src/Mobs/Path.cpp b/src/Mobs/Path.cpp index 1c8a3657f..922e28cdb 100644 --- a/src/Mobs/Path.cpp +++ b/src/Mobs/Path.cpp @@ -7,6 +7,8 @@ #include "../Chunk.h" #define JUMP_G_COST 20 +#define NORMAL_G_COST 10 +#define DIAGONAL_G_COST 14 #define DISTANCE_MANHATTAN 0 // 1: More speed, a bit less accuracy 0: Max accuracy, less speed. #define HEURISTICS_ONLY 0 // 1: Much more speed, much less accurate. @@ -30,8 +32,7 @@ bool compareHeuristics::operator()(cPathCell * & a_Cell1, cPathCell * & a_Cell2) cPath::cPath( cChunk & a_Chunk, const Vector3d & a_StartingPoint, const Vector3d & a_EndingPoint, int a_MaxSteps, - double a_BoundingBoxWidth, double a_BoundingBoxHeight, - int a_MaxUp, int a_MaxDown + double a_BoundingBoxWidth, double a_BoundingBoxHeight ) : m_StepsLeft(a_MaxSteps), m_IsValid(true), @@ -39,10 +40,8 @@ cPath::cPath( m_Chunk(&a_Chunk), m_BadChunkFound(false) { - // TODO: if src not walkable OR dest not walkable, then abort. - // Borrow a new "isWalkable" from ProcessIfWalkable, make ProcessIfWalkable also call isWalkable - a_BoundingBoxWidth = 1; // Treat all mobs width as 1 until physics is improved. This would also require changes to stepOnce to work. + a_BoundingBoxWidth = 1; // Treat all mobs width as 1 until physics is improved. m_BoundingBoxWidth = CeilC(a_BoundingBoxWidth); m_BoundingBoxHeight = CeilC(a_BoundingBoxHeight); @@ -57,7 +56,7 @@ cPath::cPath( m_Destination.y = FloorC(a_EndingPoint.y); m_Destination.z = FloorC(a_EndingPoint.z - HalfWidthInt); - if (!IsWalkable(m_Source)) + if (!IsWalkable(m_Source, m_Source)) { m_Status = ePathFinderStatus::PATH_NOT_FOUND; return; @@ -126,51 +125,6 @@ Vector3i cPath::AcceptNearbyPath() -bool cPath::IsSolid(const Vector3i & a_Location) -{ - ASSERT(m_Chunk != nullptr); - - if (!cChunkDef::IsValidHeight(a_Location.y)) - { - return false; - } - auto Chunk = m_Chunk->GetNeighborChunk(a_Location.x, a_Location.z); - if ((Chunk == nullptr) || !Chunk->IsValid()) - { - m_BadChunkFound = true; - return true; - } - m_Chunk = Chunk; - - BLOCKTYPE BlockType; - NIBBLETYPE BlockMeta; - int RelX = a_Location.x - m_Chunk->GetPosX() * cChunkDef::Width; - int RelZ = a_Location.z - m_Chunk->GetPosZ() * cChunkDef::Width; - - m_Chunk->GetBlockTypeMeta(RelX, a_Location.y, RelZ, BlockType, BlockMeta); - if ( - (BlockType == E_BLOCK_FENCE) || - (BlockType == E_BLOCK_OAK_FENCE_GATE) || - (BlockType == E_BLOCK_NETHER_BRICK_FENCE) || - (BlockType == E_BLOCK_COBBLESTONE_WALL) || - ((BlockType >= E_BLOCK_SPRUCE_FENCE_GATE) && (BlockType <= E_BLOCK_ACACIA_FENCE)) - ) - { - // TODO move this out of IsSolid to a proper place. - GetCell(a_Location + Vector3i(0, 1, 0))->m_IsSolid = true; // Mobs will always think that the fence is 2 blocks high and therefore won't jump over. - } - if (BlockType == E_BLOCK_STATIONARY_WATER) - { - GetCell(a_Location + Vector3i(0, -1, 0))->m_IsSolid = true; - } - - return cBlockInfo::IsSolid(BlockType); -} - - - - - bool cPath::StepOnce() { cPathCell * CurrentCell = OpenListPop(); @@ -209,40 +163,47 @@ bool cPath::StepOnce() // Now we start checking adjacent cells. - bool done_east = false, - done_west = false, - done_north = false, - done_south = false; // If true, no need to do more checks in that direction + // If true, no need to do more checks in that direction + bool DoneEast = false, + DoneWest = false, + DoneNorth = false, + DoneSouth = false; + + // If true, we can walk in that direction without changing height + // This is used for deciding if to calculate diagonals + bool WalkableEast = false, + WalkableWest = false, + WalkableNorth = false, + WalkableSouth = false; // If we can jump without hitting the ceiling - if (BodyFitsIn(CurrentCell->m_Location + Vector3i(0, 1, 0))) + if (BodyFitsIn(CurrentCell->m_Location + Vector3i(0, 1, 0), CurrentCell->m_Location)) { + // For ladder climbing + ProcessIfWalkable(CurrentCell->m_Location + Vector3i(0, 1, 0), CurrentCell, JUMP_G_COST); + // Check east-up - if (GetCell(CurrentCell->m_Location + Vector3i(1, 0, 0))->m_IsSolid) + if (ProcessIfWalkable(CurrentCell->m_Location + Vector3i(1, 1, 0), CurrentCell, JUMP_G_COST)) { - ProcessIfWalkable(CurrentCell->m_Location + Vector3i(1, 1, 0), CurrentCell, JUMP_G_COST); - done_east = true; + DoneEast = true; } // Check west-up - if (GetCell(CurrentCell->m_Location + Vector3i(-1, 0, 0))->m_IsSolid) + if (ProcessIfWalkable(CurrentCell->m_Location + Vector3i(-1, 1, 0), CurrentCell, JUMP_G_COST)) { - ProcessIfWalkable(CurrentCell->m_Location + Vector3i(-1, 1, 0), CurrentCell, JUMP_G_COST); - done_west = true; + DoneWest = true; } // Check north-up - if (GetCell(CurrentCell->m_Location + Vector3i(0, 0, -1))->m_IsSolid) + if (ProcessIfWalkable(CurrentCell->m_Location + Vector3i(0, 1, -1), CurrentCell, JUMP_G_COST)) { - ProcessIfWalkable(CurrentCell->m_Location + Vector3i(0, 1, -1), CurrentCell, JUMP_G_COST); - done_north = true; + DoneNorth = true; } // Check south-up - if (GetCell(CurrentCell->m_Location + Vector3i(0, 0, 1))->m_IsSolid) + if (ProcessIfWalkable(CurrentCell->m_Location + Vector3i(0, 1, 1), CurrentCell, JUMP_G_COST)) { - ProcessIfWalkable(CurrentCell->m_Location + Vector3i(0, 1, 1), CurrentCell, JUMP_G_COST); - done_south = true; + DoneSouth = true; } } @@ -251,72 +212,87 @@ bool cPath::StepOnce() // Check North, South, East, West at our own height or below. We are willing to jump up to 3 blocks down. - if (!done_east) + if (!DoneEast) { - for (int i = 0; i >= -3; --i) + for (int y = 0; y >= -3; --y) { - if (ProcessIfWalkable(CurrentCell->m_Location + Vector3i(1, i, 0), CurrentCell, 10)) + if (ProcessIfWalkable(CurrentCell->m_Location + Vector3i(1, y, 0), CurrentCell, NORMAL_G_COST)) { - done_east = true; + DoneEast = true; + if (y == 0) + { + WalkableEast = true; + } break; } } } - if (!done_west) + if (!DoneWest) { - for (int i = 0; i >= -3; --i) + for (int y = 0; y >= -3; --y) { - if (ProcessIfWalkable(CurrentCell->m_Location + Vector3i(-1, i, 0), CurrentCell, 10)) + if (ProcessIfWalkable(CurrentCell->m_Location + Vector3i(-1, y, 0), CurrentCell, NORMAL_G_COST)) { - done_west = true; + DoneWest = true; + if (y == 0) + { + WalkableWest = true; + } break; } } } - if (!done_south) + if (!DoneSouth) { - for (int i = 0; i >= -3; --i) + for (int y = 0; y >= -3; --y) { - if (ProcessIfWalkable(CurrentCell->m_Location + Vector3i(0, i, 1), CurrentCell, 10)) + if (ProcessIfWalkable(CurrentCell->m_Location + Vector3i(0, y, 1), CurrentCell, NORMAL_G_COST)) { - done_west = true; + DoneWest = true; + if (y == 0) + { + WalkableSouth = true; + } break; } } } - if (!done_north) + if (!DoneNorth) { - for (int i = 0; i >= -3; --i) + for (int y = 0; y >= -3; --y) { - if (ProcessIfWalkable(CurrentCell->m_Location + Vector3i(0, i, -1), CurrentCell, 10)) + if (ProcessIfWalkable(CurrentCell->m_Location + Vector3i(0, y, -1), CurrentCell, NORMAL_G_COST)) { - done_north = true; + DoneNorth = true; + if (y == 0) + { + WalkableNorth = true; + } break; } } } - // Check diagonals - - for (int x = -1; x <= 1; x += 2) + if (WalkableNorth && WalkableEast) { - for (int z = -1; z <= 1; z += 2) - { - // This condition prevents diagonal corner cutting. - if (!GetCell(CurrentCell->m_Location + Vector3i(x, 0, 0))->m_IsSolid && !GetCell(CurrentCell->m_Location + Vector3i(0, 0, z))->m_IsSolid) - { - // This prevents falling of "sharp turns" e.g. a 1x1x20 rectangle in the air which breaks in a right angle suddenly. - if (GetCell(CurrentCell->m_Location + Vector3i(x, -1, 0))->m_IsSolid && GetCell(CurrentCell->m_Location + Vector3i(0, -1, z))->m_IsSolid) - { - ProcessIfWalkable(CurrentCell->m_Location + Vector3i(x, 0, z), CurrentCell, 14); // 14 is a good enough approximation of sqrt(10 + 10). - } - } - } + ProcessIfWalkable(CurrentCell->m_Location + Vector3i(1, 0, -1), CurrentCell, DIAGONAL_G_COST); + } + if (WalkableNorth && WalkableWest) + { + ProcessIfWalkable(CurrentCell->m_Location + Vector3i(-1, 0, -1), CurrentCell, DIAGONAL_G_COST); + } + if (WalkableSouth && WalkableEast) + { + ProcessIfWalkable(CurrentCell->m_Location + Vector3i(1, 0, 1), CurrentCell, DIAGONAL_G_COST); + } + if (WalkableSouth && WalkableWest) + { + ProcessIfWalkable(CurrentCell->m_Location + Vector3i(-1, 0, 1), CurrentCell, DIAGONAL_G_COST); } return false; @@ -349,6 +325,12 @@ void cPath::BuildPath() cPathCell * CurrentCell = GetCell(m_Destination); while (CurrentCell->m_Parent != nullptr) { + // Waypoints are cylinders that start at some particular x, y, z and have infinite height. + // Submerging water waypoints allows swimming mobs to be able to touch them. + if (GetCell(CurrentCell->m_Location + Vector3i(0, -1, 0))->m_BlockType == E_BLOCK_STATIONARY_WATER) + { + CurrentCell->m_Location.y -= 30; + } m_PathPoints.push_back(CurrentCell->m_Location); // Populate the cPath with points. All midpoints are added. Destination is added. Source is excluded. CurrentCell = CurrentCell->m_Parent; } @@ -418,7 +400,7 @@ cPathCell * cPath::OpenListPop() // Popping from the open list also means addin bool cPath::ProcessIfWalkable(const Vector3i & a_Location, cPathCell * a_Parent, int a_Cost) { - if (IsWalkable(a_Location)) + if (IsWalkable(a_Location, a_Parent->m_Location)) { ProcessCell(GetCell(a_Location), a_Parent, a_Cost); return true; @@ -486,13 +468,72 @@ void cPath::ProcessCell(cPathCell * a_Cell, cPathCell * a_Caller, int a_GDelta) +void cPath::FillCellAttributes(cPathCell & a_Cell) +{ + const Vector3i & Location = a_Cell.m_Location; + + ASSERT(m_Chunk != nullptr); + + if (!cChunkDef::IsValidHeight(Location.y)) + { + // Players can't build outside the game height, so it must be air + a_Cell.m_IsSolid = false; + a_Cell.m_IsSpecial = false; + a_Cell.m_BlockType = E_BLOCK_AIR; + return; + } + auto Chunk = m_Chunk->GetNeighborChunk(Location.x, Location.z); + if ((Chunk == nullptr) || !Chunk->IsValid()) + { + m_BadChunkFound = true; + a_Cell.m_IsSolid = true; + a_Cell.m_IsSpecial = false; + a_Cell.m_BlockType = E_BLOCK_AIR; // m_BlockType is never used when m_IsSpecial is false, but it may be used if we implement dijkstra + return; + } + m_Chunk = Chunk; + + BLOCKTYPE BlockType; + NIBBLETYPE BlockMeta; + int RelX = Location.x - m_Chunk->GetPosX() * cChunkDef::Width; + int RelZ = Location.z - m_Chunk->GetPosZ() * cChunkDef::Width; + + m_Chunk->GetBlockTypeMeta(RelX, Location.y, RelZ, BlockType, BlockMeta); + a_Cell.m_BlockType = BlockType; + a_Cell.m_BlockMeta = BlockMeta; + + + if (BlockTypeIsSpecial(BlockType)) + { + a_Cell.m_IsSpecial = true; + a_Cell.m_IsSolid = true; // Specials are solids only from a certain direction. But their m_IsSolid is always true + } + else if ((a_Cell.m_BlockType == E_BLOCK_AIR) && BlockTypeIsFence(GetCell(Location + Vector3i(0, -1, 0))->m_BlockType)) + { + // Air blocks with fences below them are consider Special Solids. That is, they sometimes behave as solids. + a_Cell.m_IsSpecial = true; + a_Cell.m_IsSolid = true; + } + else + { + + a_Cell.m_IsSpecial = false; + a_Cell.m_IsSolid = cBlockInfo::IsSolid(BlockType); + } + +} + + + + + cPathCell * cPath::GetCell(const Vector3i & a_Location) { // Create the cell in the hash table if it's not already there. if (m_Map.count(a_Location) == 0) // Case 1: Cell is not on any list. We've never checked this cell before. { m_Map[a_Location].m_Location = a_Location; - m_Map[a_Location].m_IsSolid = IsSolid(a_Location); + FillCellAttributes(m_Map[a_Location]); m_Map[a_Location].m_Status = eCellStatus::NOLIST; #ifdef COMPILING_PATHFIND_DEBUGGER #ifdef COMPILING_PATHFIND_DEBUGGER_MARK_UNCHECKED @@ -511,16 +552,16 @@ cPathCell * cPath::GetCell(const Vector3i & a_Location) -bool cPath::IsWalkable(const Vector3i & a_Location) +bool cPath::IsWalkable(const Vector3i & a_Location, const Vector3i & a_Source) { - return (HasSolidBelow(a_Location) && BodyFitsIn(a_Location)); + return (HasSolidBelow(a_Location) && BodyFitsIn(a_Location, a_Source)); } - -bool cPath::BodyFitsIn(const Vector3i & a_Location) +// We need the source because some special blocks are solid only from a certain direction e.g. doors +bool cPath::BodyFitsIn(const Vector3i & a_Location, const Vector3i & a_Source) { int x, y, z; for (y = 0; y < m_BoundingBoxHeight; ++y) @@ -529,9 +570,20 @@ bool cPath::BodyFitsIn(const Vector3i & a_Location) { for (z = 0; z < m_BoundingBoxWidth; ++z) { - if (GetCell(a_Location + Vector3i(x, y, z))->m_IsSolid) + cPathCell * CurrentCell = GetCell(a_Location + Vector3i(x, y, z)); + if (CurrentCell->m_IsSolid) { - return false; + if (CurrentCell->m_IsSpecial) + { + if (SpecialIsSolidFromThisDirection(CurrentCell->m_BlockType, CurrentCell->m_BlockMeta, a_Location - a_Source)) + { + return false; + } + } + else + { + return false; + } } } } @@ -543,6 +595,98 @@ bool cPath::BodyFitsIn(const Vector3i & a_Location) +bool cPath::BlockTypeIsSpecial(BLOCKTYPE a_Type) +{ + if (BlockTypeIsFence(a_Type)) + { + return true; + } + + switch (a_Type) + { + case E_BLOCK_OAK_DOOR: + case E_BLOCK_DARK_OAK_DOOR: + case E_BLOCK_TRAPDOOR: + case E_BLOCK_WATER: + case E_BLOCK_STATIONARY_WATER: + { + return true; + } + default: + { + return false; + } + } +} + +bool cPath::BlockTypeIsFence(BLOCKTYPE a_Type) +{ + switch (a_Type) + { + case E_BLOCK_COBBLESTONE_WALL: + case E_BLOCK_FENCE: + case E_BLOCK_OAK_FENCE_GATE: + case E_BLOCK_NETHER_BRICK_FENCE: + case E_BLOCK_SPRUCE_FENCE_GATE: + case E_BLOCK_BIRCH_FENCE_GATE: + case E_BLOCK_JUNGLE_FENCE_GATE: + case E_BLOCK_DARK_OAK_FENCE_GATE: + case E_BLOCK_ACACIA_FENCE_GATE: + case E_BLOCK_SPRUCE_FENCE: + case E_BLOCK_BIRCH_FENCE: + case E_BLOCK_JUNGLE_FENCE: + case E_BLOCK_DARK_OAK_FENCE: + case E_BLOCK_ACACIA_FENCE: + { + return true; + } + default: + { + return false; + } + } +} + + + + +bool cPath::SpecialIsSolidFromThisDirection(BLOCKTYPE a_Type, NIBBLETYPE a_Meta, const Vector3i & a_Direction) +{ + if (a_Direction == Vector3i(0, 0, 0)) + { + return false; + } + + + + switch (a_Type) + { + // Air is special only when above a fence + case E_BLOCK_AIR: + { + // Treat the air block as solid if the mob is going upward and trying to climb a fence + if (a_Direction.y > 0) + { + return true; + } + else + { + return false; + } + } + + // TODO Fill this with the other specials after physics is fixed + } + + + + return true; +} + + + + + bool cPath::HasSolidBelow(const Vector3i & a_Location) { int x, z; |