diff options
Diffstat (limited to 'src/Mobs/Path.cpp')
| -rw-r--r-- | src/Mobs/Path.cpp | 131 |
1 files changed, 87 insertions, 44 deletions
diff --git a/src/Mobs/Path.cpp b/src/Mobs/Path.cpp index ba7d615ae..eba29be7e 100644 --- a/src/Mobs/Path.cpp +++ b/src/Mobs/Path.cpp @@ -6,20 +6,14 @@ #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. -#define CALCULATIONS_PER_STEP 5 // Higher means more CPU load but faster path calculations. +#define CALCULATIONS_PER_STEP 10 // Higher means more CPU load but faster path calculations. // The only version which guarantees the shortest path is 0, 0. -enum class eCellStatus {OPENLIST, CLOSEDLIST, NOLIST}; -struct cPathCell -{ - Vector3i m_Location; // Location of the cell in the world. - int m_F, m_G, m_H; // F, G, H as defined in regular A*. - eCellStatus m_Status; // Which list is the cell in? Either non, open, or closed. - cPathCell * m_Parent; // Cell's parent, as defined in regular A*. - bool m_IsSolid; // Is the cell an air or a solid? Partial solids are currently considered solids. -}; + + @@ -44,7 +38,8 @@ cPath::cPath( m_Destination(a_EndingPoint.Floor()), m_Source(a_StartingPoint.Floor()), m_CurrentPoint(0), // GetNextPoint increments this to 1, but that's fine, since the first cell is always a_StartingPoint - m_Chunk(&a_Chunk) + 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 @@ -55,6 +50,7 @@ cPath::cPath( return; } + m_NearestPointToTarget = GetCell(m_Source); m_Status = ePathFinderStatus::CALCULATING; m_StepsLeft = a_MaxSteps; @@ -81,15 +77,20 @@ cPath::~cPath() ePathFinderStatus cPath::Step(cChunk & a_Chunk) { m_Chunk = &a_Chunk; - if (m_Status != ePathFinderStatus::CALCULATING) { return m_Status; } - if (m_StepsLeft == 0) + if (m_BadChunkFound) { FinishCalculation(ePathFinderStatus::PATH_NOT_FOUND); + return m_Status; + } + + if (m_StepsLeft == 0) + { + AttemptToFindAlternative(); } else { @@ -102,9 +103,9 @@ ePathFinderStatus cPath::Step(cChunk & a_Chunk) break; // if we're here, m_Status must have changed either to PATH_FOUND or PATH_NOT_FOUND. } } - } - m_Chunk = nullptr; + m_Chunk = nullptr; + } return m_Status; } @@ -112,6 +113,17 @@ ePathFinderStatus cPath::Step(cChunk & a_Chunk) +Vector3i cPath::AcceptNearbyPath() +{ + ASSERT(m_Status == ePathFinderStatus::NEARBY_FOUND); + m_Status = ePathFinderStatus::PATH_FOUND; + return m_Destination; +} + + + + + bool cPath::IsSolid(const Vector3i & a_Location) { ASSERT(m_Chunk != nullptr); @@ -119,6 +131,7 @@ bool cPath::IsSolid(const Vector3i & a_Location) auto Chunk = m_Chunk->GetNeighborChunk(a_Location.x, a_Location.z); if ((Chunk == nullptr) || !Chunk->IsValid()) { + m_BadChunkFound = true; return true; } m_Chunk = Chunk; @@ -149,34 +162,36 @@ bool cPath::Step_Internal() { cPathCell * CurrentCell = OpenListPop(); - // Path not reachable, open list exauhsted. + // Path not reachable. if (CurrentCell == nullptr) { - FinishCalculation(ePathFinderStatus::PATH_NOT_FOUND); - ASSERT(m_Status == ePathFinderStatus::PATH_NOT_FOUND); + AttemptToFindAlternative(); return true; } // Path found. - if ( - (CurrentCell->m_Location == m_Destination + Vector3i(0, 0, 1)) || - (CurrentCell->m_Location == m_Destination + Vector3i(1, 0, 0)) || - (CurrentCell->m_Location == m_Destination + Vector3i(-1, 0, 0)) || - (CurrentCell->m_Location == m_Destination + Vector3i(0, 0, -1)) || - (CurrentCell->m_Location == m_Destination + Vector3i(0, -1, 0)) - ) + if (CurrentCell->m_Location == m_Destination) { - do - { - m_PathPoints.push_back(CurrentCell->m_Location); // Populate the cPath with points. - CurrentCell = CurrentCell->m_Parent; - } while (CurrentCell != nullptr); - + BuildPath(); FinishCalculation(ePathFinderStatus::PATH_FOUND); return true; } - // Calculation not finished yet, process a currentCell by inspecting all neighbors. + // Calculation not finished yet. + // Check if we have a new NearestPoint. + + if ((m_Destination - CurrentCell->m_Location).Length() < 5) + { + if (m_Rand.NextInt(4) == 0) + { + m_NearestPointToTarget = CurrentCell; + } + } + else if (CurrentCell->m_H < m_NearestPointToTarget->m_H) + { + m_NearestPointToTarget = CurrentCell; + } + // process a currentCell by inspecting all neighbors. // Check North, South, East, West on all 3 different heights. int i; @@ -213,13 +228,40 @@ bool cPath::Step_Internal() -void cPath::FinishCalculation() +void cPath::AttemptToFindAlternative() { - for (auto && pair : m_Map) + if (m_NearestPointToTarget == GetCell(m_Source)) { - delete pair.second; + FinishCalculation(ePathFinderStatus::PATH_NOT_FOUND); } + else + { + m_Destination = m_NearestPointToTarget->m_Location; + BuildPath(); + FinishCalculation(ePathFinderStatus::NEARBY_FOUND); + } +} + + + + +void cPath::BuildPath() +{ + cPathCell * CurrentCell = GetCell(m_Destination); + do + { + m_PathPoints.push_back(CurrentCell->m_Location); // Populate the cPath with points. + CurrentCell = CurrentCell->m_Parent; + } while (CurrentCell != nullptr); +} + + + + + +void cPath::FinishCalculation() +{ m_Map.clear(); m_OpenList = std::priority_queue<cPathCell *, std::vector<cPathCell *>, compareHeuristics>{}; } @@ -230,6 +272,10 @@ void cPath::FinishCalculation() void cPath::FinishCalculation(ePathFinderStatus a_NewStatus) { + if (m_BadChunkFound) + { + a_NewStatus = ePathFinderStatus::PATH_NOT_FOUND; + } m_Status = a_NewStatus; FinishCalculation(); } @@ -255,7 +301,7 @@ cPathCell * cPath::OpenListPop() // Popping from the open list also means addin { if (m_OpenList.size() == 0) { - return nullptr; // We've exhausted the search space and nothing was found, this will trigger a PATH_NOT_FOUND status. + return nullptr; // We've exhausted the search space and nothing was found, this will trigger a PATH_NOT_FOUND or NEARBY_FOUND status. } cPathCell * Ret = m_OpenList.top(); @@ -343,23 +389,20 @@ void cPath::ProcessCell(cPathCell * a_Cell, cPathCell * a_Caller, int a_GDelta) cPathCell * cPath::GetCell(const Vector3i & a_Location) { // Create the cell in the hash table if it's not already there. - cPathCell * Cell; if (m_Map.count(a_Location) == 0) // Case 1: Cell is not on any list. We've never checked this cell before. { - Cell = new cPathCell(); - Cell->m_Location = a_Location; - m_Map[a_Location] = Cell; - Cell->m_IsSolid = IsSolid(a_Location); - Cell->m_Status = eCellStatus::NOLIST; + m_Map[a_Location].m_Location = a_Location; + m_Map[a_Location].m_IsSolid = IsSolid(a_Location); + m_Map[a_Location].m_Status = eCellStatus::NOLIST; #ifdef COMPILING_PATHFIND_DEBUGGER #ifdef COMPILING_PATHFIND_DEBUGGER_MARK_UNCHECKED si::setBlock(a_Location.x, a_Location.y, a_Location.z, debug_unchecked, Cell->m_IsSolid ? NORMAL : MINI); #endif #endif - return Cell; + return &m_Map[a_Location]; } else { - return m_Map[a_Location]; + return &m_Map[a_Location]; } } |