From 16b6fc9b5d59ac795e139b2a597da97953690d82 Mon Sep 17 00:00:00 2001 From: wiseoldman95 Date: Fri, 1 May 2015 18:53:24 +0300 Subject: PathFinding - Chunk querying optimization and improve cPath::IsSolid --- src/Mobs/Monster.cpp | 8 +++---- src/Mobs/Monster.h | 2 +- src/Mobs/Path.cpp | 67 ++++++++++++++++++++-------------------------------- src/Mobs/Path.h | 27 ++++++--------------- 4 files changed, 38 insertions(+), 66 deletions(-) diff --git a/src/Mobs/Monster.cpp b/src/Mobs/Monster.cpp index e225ff9b1..e9b171e49 100644 --- a/src/Mobs/Monster.cpp +++ b/src/Mobs/Monster.cpp @@ -121,7 +121,7 @@ void cMonster::SpawnOn(cClientHandle & a_Client) -void cMonster::TickPathFinding() +void cMonster::TickPathFinding(cChunk & a_Chunk) { if (m_Path == nullptr) @@ -131,12 +131,12 @@ void cMonster::TickPathFinding() // Can someone explain why are these two NOT THE SAME??? // m_Path = new cPath(GetWorld(), GetPosition(), m_FinalDestination, 30); - m_Path = new cPath(GetWorld(), Vector3d(floor(position.x), floor(position.y), floor(position.z)), Vector3d(floor(Dest.x), floor(Dest.y), floor(Dest.z)), 20); + m_Path = new cPath(&a_Chunk, Vector3d(floor(position.x), floor(position.y), floor(position.z)), Vector3d(floor(Dest.x), floor(Dest.y), floor(Dest.z)), 20); m_IsFollowingPath = false; } - m_PathStatus = m_Path->Step(); + m_PathStatus = m_Path->Step(&a_Chunk); switch (m_PathStatus) { @@ -293,7 +293,7 @@ void cMonster::Tick(std::chrono::milliseconds a_Dt, cChunk & a_Chunk) } } - TickPathFinding(); + TickPathFinding(a_Chunk); Vector3d Distance = m_Destination - GetPosition(); if (!ReachedDestination() && !ReachedFinalDestination()) // If we haven't reached any sort of destination, move diff --git a/src/Mobs/Monster.h b/src/Mobs/Monster.h index 43861e021..56efa056a 100644 --- a/src/Mobs/Monster.h +++ b/src/Mobs/Monster.h @@ -206,7 +206,7 @@ protected: /** Finds the next place to go This is based on the ultimate, final destination and the current position, as well as the traversed coordinates, and any environmental hazards */ - void TickPathFinding(void); + void TickPathFinding(cChunk & a_Chunk); /** Finishes a pathfinding task, be it due to failure or something else */ void FinishPathFinding(void); /** Sets the body yaw and head yaw/pitch based on next/ultimate destinations */ diff --git a/src/Mobs/Path.cpp b/src/Mobs/Path.cpp index 0cb03c925..32eff9d2b 100644 --- a/src/Mobs/Path.cpp +++ b/src/Mobs/Path.cpp @@ -1,12 +1,9 @@ #include "Globals.h" -#ifndef COMPILING_PATHFIND_DEBUGGER - /* MCServer headers */ - #include "../World.h" - #include "../Chunk.h" -#endif #include + #include "Path.h" +#include "../Chunk.h" #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. @@ -38,18 +35,17 @@ bool compareHeuristics::operator()(cPathCell * & a_Cell1, cPathCell * & a_Cell2) /* cPath implementation */ cPath::cPath( - cWorld * a_World, + 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 ) { + ASSERT(m_Chunk != nullptr); // TODO: if src not walkable OR dest not walkable, then abort. // Borrow a new "isWalkable" from ProcessIfWalkable, make ProcessIfWalkable also call isWalkable - m_World = a_World; - // m_World = cRoot::Get()->GetDefaultWorld(); - + m_Chunk = a_Chunk; m_Source = a_StartingPoint.Floor(); m_Destination = a_EndingPoint.Floor(); @@ -65,6 +61,7 @@ cPath::cPath( m_PointCount = 0; ProcessCell(GetCell(a_StartingPoint), nullptr, 0); + m_Chunk = nullptr; } @@ -83,8 +80,10 @@ cPath::~cPath() -ePathFinderStatus cPath::Step() +ePathFinderStatus cPath::Step(cChunk * a_Chunk) { + m_Chunk = a_Chunk; + ASSERT(m_Chunk != nullptr); if (m_Status != ePathFinderStatus::CALCULATING) { return m_Status; @@ -106,6 +105,7 @@ ePathFinderStatus cPath::Step() } } } + m_Chunk = nullptr; return m_Status; } @@ -113,15 +113,25 @@ ePathFinderStatus cPath::Step() -#ifndef COMPILING_PATHFIND_DEBUGGER bool cPath::IsSolid(const Vector3d & a_Location) { - int ChunkX, ChunkZ; - m_Item_CurrentBlock = a_Location; - cChunkDef::BlockToChunk(a_Location.x, a_Location.z, ChunkX, ChunkZ); - return !m_World->DoWithChunk(ChunkX, ChunkZ, * this); + ASSERT(m_Chunk != nullptr); + m_Chunk = m_Chunk->GetNeighborChunk(a_Location.x, a_Location.z); + if (!m_Chunk->IsValid()) + { + return true; + } + 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_FENCE_GATE)) + { + GetCell(a_Location + Vector3d(0, 1, 0))->m_IsSolid = true; // Mobs will always think that the fence is 2 blocks high and therefore won't jump over. + } + return cBlockInfo::IsSolid(BlockType); } -#endif @@ -352,28 +362,3 @@ void cPath::AddPoint(Vector3d a_Vector) m_PathPoints.push_back(a_Vector); ++m_PointCount; } - - - - - -#ifndef COMPILING_PATHFIND_DEBUGGER -bool cPath::Item(cChunk * a_Chunk) // returns FALSE if there's a solid or if we failed. -{ - int RelX = m_Item_CurrentBlock.x - a_Chunk->GetPosX() * cChunkDef::Width; - int RelZ = m_Item_CurrentBlock.z - a_Chunk->GetPosZ() * cChunkDef::Width; - - if (!a_Chunk->IsValid()) - { - return false; - } - BLOCKTYPE BlockType; - NIBBLETYPE BlockMeta; - a_Chunk->GetBlockTypeMeta(RelX, m_Item_CurrentBlock.y, RelZ, BlockType, BlockMeta); - return (!cBlockInfo::IsSolid(BlockType)); - - // TODO Maybe I should queue several blocks and call item() at once for all of them for better performance? - // I think Worktycho said each item() call needs 2 locks. - -} -#endif diff --git a/src/Mobs/Path.h b/src/Mobs/Path.h index 05fd59155..9927d0a34 100644 --- a/src/Mobs/Path.h +++ b/src/Mobs/Path.h @@ -18,12 +18,8 @@ Put this in your .cpp: #include -/* MCServer forward declarations */ -#ifndef COMPILING_PATHFIND_DEBUGGER - -// fwd: cChunkMap.h -typedef cItemCallback cChunkCallback; -#endif +//fwd: ../Chunk.h +class cChunk; /* Various little structs and classes */ enum class ePathFinderStatus {CALCULATING, PATH_FOUND, PATH_NOT_FOUND}; @@ -35,9 +31,6 @@ public: }; class cPath -#ifndef COMPILING_PATHFIND_DEBUGGER -: public cChunkCallback -#endif { public: /** Creates a pathfinder instance. A Mob will probably need a single pathfinder instance for its entire life. @@ -59,7 +52,7 @@ public: @param a_EndingPoint "The block where the Zombie's knees want to be". @param a_MaxSteps The maximum steps before giving up. */ cPath( - cWorld * a_World, + cChunk * a_Chunk, const Vector3d & a_StartingPoint, const Vector3d & a_EndingPoint, int a_MaxSteps, double a_BoundingBoxWidth = 1, double a_BoundingBoxHeight = 2, int a_MaxUp = 1, int a_MaxDown = 1 @@ -69,7 +62,7 @@ public: ~cPath(); /** Performs part of the path calculation and returns true if the path computation has finished. */ - ePathFinderStatus Step(); + ePathFinderStatus Step(cChunk * a_Chunk); /* Point retrieval functions, inlined for performance. */ /** Returns the next point in the path. */ @@ -147,15 +140,9 @@ private: std::vector m_PathPoints; void AddPoint(Vector3d a_Vector); - /* Interfacing with MCServer's world */ - cWorld * m_World; - #ifndef COMPILING_PATHFIND_DEBUGGER - Vector3d m_Item_CurrentBlock; // Read by Item();, it's the only way to "pass it" parameters -protected: - virtual bool Item(cChunk * a_Chunk) override; - - /* Interfacing with Irrlicht, has nothing to do with MCServer*/ - #else + /* Interfacing with the world */ + cChunk * m_Chunk; // Only valid inside Step()! + #ifdef COMPILING_PATHFIND_DEBUGGER #include "../path_irrlicht.cpp" #endif }; -- cgit v1.2.3