From b8aa38b18d7f7ab78766d2be94e8738e503bacca Mon Sep 17 00:00:00 2001 From: wiseoldman95 Date: Wed, 6 May 2015 17:23:07 +0300 Subject: (duplicate) AI - Livestock escape fixed, water jumping fixed --- src/Mobs/Path.cpp | 25 ------------------------- 1 file changed, 25 deletions(-) (limited to 'src/Mobs/Path.cpp') diff --git a/src/Mobs/Path.cpp b/src/Mobs/Path.cpp index 84d888bf2..ebfb5b630 100644 --- a/src/Mobs/Path.cpp +++ b/src/Mobs/Path.cpp @@ -54,31 +54,6 @@ cPath::cPath( return; } - // If destination in water, set water surface as destination. - cChunk * Chunk = m_Chunk->GetNeighborChunk(m_Destination.x, m_Destination.z); - if ((Chunk != nullptr) && Chunk->IsValid()) - { - BLOCKTYPE BlockType; - NIBBLETYPE BlockMeta; - int RelX = m_Destination.x - Chunk->GetPosX() * cChunkDef::Width; - int RelZ = m_Destination.z - Chunk->GetPosZ() * cChunkDef::Width; - bool inwater = false; - for (;;) - { - Chunk->GetBlockTypeMeta(RelX, m_Destination.y, RelZ, BlockType, BlockMeta); - if (BlockType != E_BLOCK_STATIONARY_WATER) - { - break; - } - inwater = true; - m_Destination+=Vector3d(0, 1, 0); - } - if (inwater) - { - m_Destination+=Vector3d(0, -1, 0); - } - } - m_Status = ePathFinderStatus::CALCULATING; m_StepsLeft = a_MaxSteps; -- cgit v1.2.3 From 7771091099fad43025c63694ccf9362cce384aa8 Mon Sep 17 00:00:00 2001 From: worktycho Date: Wed, 6 May 2015 17:26:59 +0100 Subject: Actually empty the open list --- src/Mobs/Path.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/Mobs/Path.cpp') diff --git a/src/Mobs/Path.cpp b/src/Mobs/Path.cpp index 84d888bf2..60f88f525 100644 --- a/src/Mobs/Path.cpp +++ b/src/Mobs/Path.cpp @@ -245,7 +245,7 @@ void cPath::FinishCalculation() } m_Map.clear(); - m_OpenList.empty(); + m_OpenList = std::priority_queue, compareHeuristics>{}; } -- cgit v1.2.3 From 290bc2e37730c14df85b9ce9acd63611ca185434 Mon Sep 17 00:00:00 2001 From: wiseoldman95 Date: Fri, 8 May 2015 17:07:36 +0300 Subject: Spaces in cPath --- src/Mobs/Path.cpp | 1 + 1 file changed, 1 insertion(+) (limited to 'src/Mobs/Path.cpp') diff --git a/src/Mobs/Path.cpp b/src/Mobs/Path.cpp index 6fc9e06c3..8abbc4cac 100644 --- a/src/Mobs/Path.cpp +++ b/src/Mobs/Path.cpp @@ -1,3 +1,4 @@ + #include "Globals.h" #include -- cgit v1.2.3 From 8a576a0a35d0db0cfe510213bfb5ec5af1323777 Mon Sep 17 00:00:00 2001 From: wiseoldman95 Date: Sun, 10 May 2015 09:08:42 +0300 Subject: PF - Less calcs per tick --- src/Mobs/Path.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/Mobs/Path.cpp') diff --git a/src/Mobs/Path.cpp b/src/Mobs/Path.cpp index 8abbc4cac..ba7d615ae 100644 --- a/src/Mobs/Path.cpp +++ b/src/Mobs/Path.cpp @@ -8,7 +8,7 @@ #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 60 // Higher means more CPU load but faster path calculations. +#define CALCULATIONS_PER_STEP 5 // 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}; -- cgit v1.2.3 From a8878dd2b6cee69b7cc92b19c740cc4deb7c9735 Mon Sep 17 00:00:00 2001 From: SafwatHalaby Date: Fri, 15 May 2015 20:25:44 +0300 Subject: uniquePTR --- src/Mobs/Path.cpp | 9 ++------- 1 file changed, 2 insertions(+), 7 deletions(-) (limited to 'src/Mobs/Path.cpp') diff --git a/src/Mobs/Path.cpp b/src/Mobs/Path.cpp index ba7d615ae..dd306af13 100644 --- a/src/Mobs/Path.cpp +++ b/src/Mobs/Path.cpp @@ -215,11 +215,6 @@ bool cPath::Step_Internal() void cPath::FinishCalculation() { - for (auto && pair : m_Map) - { - delete pair.second; - } - m_Map.clear(); m_OpenList = std::priority_queue, compareHeuristics>{}; } @@ -348,7 +343,7 @@ cPathCell * cPath::GetCell(const Vector3i & a_Location) { Cell = new cPathCell(); Cell->m_Location = a_Location; - m_Map[a_Location] = Cell; + m_Map[a_Location] = UniquePtr(Cell); Cell->m_IsSolid = IsSolid(a_Location); Cell->m_Status = eCellStatus::NOLIST; #ifdef COMPILING_PATHFIND_DEBUGGER @@ -360,6 +355,6 @@ cPathCell * cPath::GetCell(const Vector3i & a_Location) } else { - return m_Map[a_Location]; + return m_Map[a_Location].get(); } } -- cgit v1.2.3 From 5c3a85fba10e801c6553fa943fa85605bbcd4f41 Mon Sep 17 00:00:00 2001 From: worktycho Date: Fri, 15 May 2015 18:54:45 +0100 Subject: Revert "PathFinder - smart pointers" --- src/Mobs/Path.cpp | 9 +++++++-- 1 file changed, 7 insertions(+), 2 deletions(-) (limited to 'src/Mobs/Path.cpp') diff --git a/src/Mobs/Path.cpp b/src/Mobs/Path.cpp index dd306af13..ba7d615ae 100644 --- a/src/Mobs/Path.cpp +++ b/src/Mobs/Path.cpp @@ -215,6 +215,11 @@ bool cPath::Step_Internal() void cPath::FinishCalculation() { + for (auto && pair : m_Map) + { + delete pair.second; + } + m_Map.clear(); m_OpenList = std::priority_queue, compareHeuristics>{}; } @@ -343,7 +348,7 @@ cPathCell * cPath::GetCell(const Vector3i & a_Location) { Cell = new cPathCell(); Cell->m_Location = a_Location; - m_Map[a_Location] = UniquePtr(Cell); + m_Map[a_Location] = Cell; Cell->m_IsSolid = IsSolid(a_Location); Cell->m_Status = eCellStatus::NOLIST; #ifdef COMPILING_PATHFIND_DEBUGGER @@ -355,6 +360,6 @@ cPathCell * cPath::GetCell(const Vector3i & a_Location) } else { - return m_Map[a_Location].get(); + return m_Map[a_Location]; } } -- cgit v1.2.3 From 4ffc6621a9ca976f95eeda80e7c073ee932af85f Mon Sep 17 00:00:00 2001 From: SafwatHalaby Date: Fri, 15 May 2015 20:25:44 +0300 Subject: PathFinder uses UniquePtr for cell map. --- src/Mobs/Path.cpp | 9 ++------- 1 file changed, 2 insertions(+), 7 deletions(-) (limited to 'src/Mobs/Path.cpp') diff --git a/src/Mobs/Path.cpp b/src/Mobs/Path.cpp index ba7d615ae..dd306af13 100644 --- a/src/Mobs/Path.cpp +++ b/src/Mobs/Path.cpp @@ -215,11 +215,6 @@ bool cPath::Step_Internal() void cPath::FinishCalculation() { - for (auto && pair : m_Map) - { - delete pair.second; - } - m_Map.clear(); m_OpenList = std::priority_queue, compareHeuristics>{}; } @@ -348,7 +343,7 @@ cPathCell * cPath::GetCell(const Vector3i & a_Location) { Cell = new cPathCell(); Cell->m_Location = a_Location; - m_Map[a_Location] = Cell; + m_Map[a_Location] = UniquePtr(Cell); Cell->m_IsSolid = IsSolid(a_Location); Cell->m_Status = eCellStatus::NOLIST; #ifdef COMPILING_PATHFIND_DEBUGGER @@ -360,6 +355,6 @@ cPathCell * cPath::GetCell(const Vector3i & a_Location) } else { - return m_Map[a_Location]; + return m_Map[a_Location].get(); } } -- cgit v1.2.3 From 29e31c5be95abd6a7122a525f53d80f4576e49b2 Mon Sep 17 00:00:00 2001 From: SafwatHalaby Date: Sat, 16 May 2015 14:05:33 +0300 Subject: Pathfinder - approximated paths when original destination unreachable --- src/Mobs/Path.cpp | 98 +++++++++++++++++++++++++++++++++++++++++-------------- 1 file changed, 74 insertions(+), 24 deletions(-) (limited to 'src/Mobs/Path.cpp') diff --git a/src/Mobs/Path.cpp b/src/Mobs/Path.cpp index dd306af13..ba8046a2b 100644 --- a/src/Mobs/Path.cpp +++ b/src/Mobs/Path.cpp @@ -8,7 +8,7 @@ #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}; @@ -44,7 +44,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 +56,7 @@ cPath::cPath( return; } + m_NearestPointToTarget = GetCell(m_Source); m_Status = ePathFinderStatus::CALCULATING; m_StepsLeft = a_MaxSteps; @@ -81,15 +83,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 +109,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 +119,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 +137,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 +168,29 @@ 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 (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,6 +227,38 @@ bool cPath::Step_Internal() +void cPath::AttemptToFindAlternative() +{ + if (m_NearestPointToTarget == GetCell(m_Source)) + { + 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(); @@ -225,6 +271,10 @@ void cPath::FinishCalculation() void cPath::FinishCalculation(ePathFinderStatus a_NewStatus) { + if (m_BadChunkFound) + { + a_NewStatus = ePathFinderStatus::PATH_NOT_FOUND; + } m_Status = a_NewStatus; FinishCalculation(); } @@ -250,7 +300,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(); -- cgit v1.2.3