";
+
+ stream << "";
+
+ // set up grid
+ stream << "\n";
+
+ // Dump hierarchical regions on another one.
+ stream << "";
+ stream << "";
+
+ HierarchicalPathfinder& hier = ((CCmpPathfinder*)cmpPathfinder.operator->())->m_LongPathfinder.GetHierarchicalPathfinder();
+
+ stream << "\n";
+
+ // Ok let's check out MakeGoalReachable
+ // pick a point
+ fixed X,Z;
+ X = fixed::FromInt(sx);
+ Z = fixed::FromInt(sz);
+ u16 gridSize = obstructions.m_W;
+ // Convert the start coordinates to tile indexes
+ u16 i0, j0;
+ Pathfinding::NearestNavcell(X, Z, i0, j0, gridSize, gridSize);
+
+ // Dump as HTML so that it's on top and add fancy shadows so it's easy to see.
+ stream << "";
+
+ hier.FindNearestPassableNavcell(i0, j0, obstructionsMask);
+ stream << "";
+
+ // Make the goal reachable. This includes shortening the path if the goal is in a non-passable
+ // region, transforming non-point goals to reachable point goals, etc.
+
+ PathGoal goal;
+ goal.type = PathGoal::POINT;
+ goal.x = fixed::FromInt(gx);
+ goal.z = fixed::FromInt(gz);
+ goal.u = CFixedVector2D(fixed::FromInt(1), fixed::Zero());
+ goal.v = CFixedVector2D(fixed::Zero(),fixed::FromInt(1));
+ goal.hh = fixed::FromInt(0);
+ goal.hw = fixed::FromInt(0);
+
+ u16 i1, j1;
+ Pathfinding::NearestNavcell(goal.x, goal.z, i1, j1, gridSize, gridSize);
+ stream << "";
+
+ stream << "";
+ stream << "";
+
+ stream << "\n";
+
+ Pathfinding::NearestNavcell(goalCopy.x, goalCopy.z, i1, j1, gridSize, gridSize);
+ stream << "";
+ stream << "\n";
+ stream.close();
+
+ // Perf test. This is a little primitive, but should work well enough to give an idea of the algo.
+ double t = timer_Time();
+
+ srand(1234);
+ for (size_t j = 0; j < 10000; ++j)
+ {
+ PathGoal oldGoal = goal;
+ hier.MakeGoalReachable(i0, j0, goal, obstructionsMask);
+ goal = oldGoal;
+ }
+
+ t = timer_Time() - t;
+ printf("\nPoint Goal: [%f]\n", t);
+
+ goal.type = PathGoal::CIRCLE;
+ goal.hh = fixed::FromInt(40);
+ goal.hw = fixed::FromInt(40);
+
+ t = timer_Time();
+
+ srand(1234);
+ for (size_t j = 0; j < 10000; ++j)
+ {
+ PathGoal oldGoal = goal;
+ hier.MakeGoalReachable(i0, j0, goal, obstructionsMask);
+ goal = oldGoal;
+ }
+
+ t = timer_Time() - t;
+ printf("\nCircle Goal: [%f]\n", t);
+ }
+
+ void test_MakeGoalReachable_performance_DISABLED()
+ {
+ struct test
+ {
+ CStr map;
+ u16 sx;
+ u16 sz;
+ u16 gx;
+ u16 gz;
+ };
+ /*
+ * Initially this was done to compare A* to the earlier flood-fill method, which has since been removed.
+ * Compare performance on a few cases:
+ * - short path, good case for the flood fill (it finds immediately the point/circle and stops)
+ * - short path, bad case for the flood fill (it will not find the correct region right away, so it's literally about 100x slower than the former)
+ * - long path around the bend, close to worst-case for A*
+ * - Long unreachable path, but the "closest point" is reachable in almost a straight direction.
+ * - Inverse of the former (the region to fill is much smaller)
+ * - large island, A* still has a lot to fill here
+ * - straight with obstructions
+ * - straight, fewer obstructions
+ * - bad case (U shape around the start containing A*)
+ * - bad case: U shape + unreachable. We need to return something reasonably close, not in the first U
+ * - bad calse: two U shapes tripping A*
+ */
+ std::vector maps = {
+ { "maps/scenarios/Peloponnese.pmp", 600, 800, 800, 800 },
+ { "maps/scenarios/Peloponnese.pmp", 600, 800, 600, 900 },
+ { "maps/scenarios/Peloponnese.pmp", 600, 800, 770, 1400 },
+ { "maps/scenarios/Peloponnese.pmp", 1000, 300, 1500, 1450 },
+ { "maps/scenarios/Peloponnese.pmp", 1500, 1450, 1000, 300 },
+ { "maps/skirmishes/Corsica and Sardinia (4).pmp", 300, 1300, 1300, 300 },
+ { "maps/skirmishes/Alpine_Mountains_(3).pmp", 200, 200, 800, 800 },
+ { "maps/skirmishes/Corinthian Isthmus (2).pmp", 200, 200, 800, 800 },
+ { "maps/skirmishes/Mediterranean Cove (2).pmp", 200, 200, 800, 800 },
+ { "maps/skirmishes/Dueling Cliffs (3v3).pmp", 200, 200, 800, 800 },
+ { "maps/skirmishes/Dueling Cliffs (3v3).pmp", 350, 200, 900, 900 },
+ { "maps/skirmishes/Dueling Cliffs (3v3).pmp", 200, 200, 950, 950 },
+ };
+
+ for (auto t : maps)
+ {
+ MakeGoalReachable_testIteration(t.map, t.sx, t.sz, t.gx, t.gz);
+ }
+ }
+
void DumpPath(std::ostream& stream, int i0, int j0, int i1, int j1, CmpPtr& cmpPathfinder)
{
entity_pos_t x0 = entity_pos_t::FromInt(i0);
Index: source/simulation2/helpers/Geometry.h
===================================================================
--- source/simulation2/helpers/Geometry.h
+++ source/simulation2/helpers/Geometry.h
@@ -30,6 +30,21 @@
namespace Geometry
{
+/*
+ * Check if we should treat a square as a circle, given the radius
+ * of the resulting circle and a distance to it
+ * used by UnitMotion and ObstructionManager
+ */
+inline bool ShouldTreatTargetAsCircle(const fixed& range, const fixed& circleRadius)
+{
+ // Given a square, plus a target range we should reach, the shape at that distance
+ // is a round-cornered square which we can approximate as either a circle or as a square.
+ // Previously, we used the shape that minimized the worst-case error.
+ // However that is unsage in some situations. So let's be less clever and
+ // just check if our range is at least three times bigger than the circleradius
+ return (range > circleRadius*3);
+}
+
/**
* Checks if a point is inside the given rotated rectangle.
* Points precisely on an edge are considered to be inside.
Index: source/simulation2/helpers/HierarchicalPathfinder.h
===================================================================
--- source/simulation2/helpers/HierarchicalPathfinder.h
+++ source/simulation2/helpers/HierarchicalPathfinder.h
@@ -24,10 +24,13 @@
#include "Render.h"
#include "graphics/SColor.h"
+#include
+#include
+
/**
* Hierarchical pathfinder.
*
- * It doesn't find shortest paths, but deals with connectivity.
+ * Deals with connectivity (can point A reach point B?)
*
* The navcell-grid representation of the map is split into fixed-size chunks.
* Within a chunk, each maximal set of adjacently-connected passable navcells
@@ -35,18 +38,31 @@
* Each region is a vertex in the hierarchical pathfinder's graph.
* When two regions in adjacent chunks are connected by passable navcells,
* the graph contains an edge between the corresponding two vertexes.
- * (There will never be an edge between two regions in the same chunk.)
+ * (by design, there can never be an edge between two regions in the same chunk.)
+ *
+ * Those fixed-size chunks are used to efficiently compute "global regions" by effectively flood-filling.
+ * Those can then be used to immediately determine if two reachables points are connected
+ *
+ * The main use of this class is to convert an arbitrary PathGoal to a reachable navcell
+ * This happens in MakeGoalReachable, which implements A* over the chunks.
+ * Currently, the resulting path is unused.
*
- * Since regions are typically fairly large, it is possible to determine
- * connectivity between any two navcells by mapping them onto their appropriate
- * region and then doing a relatively small graph search.
*/
+#ifdef TEST
+class TestCmpPathfinder;
+#endif
+
class HierarchicalOverlay;
class HierarchicalPathfinder
{
+#ifdef TEST
+ friend class TestCmpPathfinder;
+#endif
public:
+ typedef u32 GlobalRegionID;
+
struct RegionID
{
u8 ci, cj; // chunk ID
@@ -54,7 +70,7 @@
RegionID(u8 ci, u8 cj, u16 r) : ci(ci), cj(cj), r(r) { }
- bool operator<(RegionID b) const
+ bool operator<(const RegionID& b) const
{
// Sort by chunk ID, then by per-chunk region ID
if (ci < b.ci)
@@ -68,7 +84,7 @@
return r < b.r;
}
- bool operator==(RegionID b) const
+ bool operator==(const RegionID& b) const
{
return ((ci == b.ci) && (cj == b.cj) && (r == b.r));
}
@@ -89,18 +105,25 @@
bool IsChunkDirty(int ci, int cj, const Grid& dirtinessGrid) const;
RegionID Get(u16 i, u16 j, pass_class_t passClass);
+ GlobalRegionID GetGlobalRegion(u16 i, u16 j, pass_class_t passClass);
/**
- * Updates @p goal so that it's guaranteed to be reachable from the navcell
+ * Updates @p goal to a point goal guaranteed to be reachable from the original navcell
* @p i0, @p j0 (which is assumed to be on a passable navcell).
*
- * If the goal is not reachable, it is replaced with a point goal nearest to
- * the goal center.
+ * If the goal is not reachable, it is replaced with an acceptable point goal
+ * This function does not necessarily return the closest navcell to the goal
+ * but the one with the lowest f score of the A* algorithm.
+ * This means it is usually a tradeoff between walking time and distance to the goal.
*
* In the case of a non-point reachable goal, it is replaced with a point goal
* at the reachable navcell of the goal which is nearest to the starting navcell.
+ * TODO: since A* is used, it could return the reachable navcell nearest to the penultimate region visited.
+ * which is probably better (imagine a path that must bend around).
+ *
+ * @returns true if the goal was reachable, false otherwise.
*/
- void MakeGoalReachable(u16 i0, u16 j0, PathGoal& goal, pass_class_t passClass);
+ bool MakeGoalReachable(u16 i0, u16 j0, PathGoal& goal, pass_class_t passClass);
/**
* Updates @p i, @p j (which is assumed to be an impassable navcell)
@@ -125,12 +148,12 @@
private:
static const u8 CHUNK_SIZE = 96; // number of navcells per side
- // TODO PATHFINDER: figure out best number. Probably 64 < n < 128
+ // TODO: figure out best number. Probably 64 < n < 128
struct Chunk
{
u8 m_ChunkI, m_ChunkJ; // chunk ID
- u16 m_NumRegions; // number of local region IDs (starting from 1)
+ std::vector m_RegionsID; // IDs of local region, without 0
u16 m_Regions[CHUNK_SIZE][CHUNK_SIZE]; // local region ID per navcell
cassert(CHUNK_SIZE*CHUNK_SIZE/2 < 65536); // otherwise we could overflow m_NumRegions with a checkerboard pattern
@@ -144,16 +167,41 @@
void RegionNavcellNearest(u16 r, int iGoal, int jGoal, int& iBest, int& jBest, u32& dist2Best) const;
bool RegionNearestNavcellInGoal(u16 r, u16 i0, u16 j0, const PathGoal& goal, u16& iOut, u16& jOut, u32& dist2Best) const;
+
+#ifdef TEST
+ bool operator==(const Chunk& b) const
+ {
+ return (m_ChunkI == b.m_ChunkI && m_ChunkJ == b.m_ChunkJ && m_RegionsID == b.m_RegionsID && memcmp(&m_Regions, &b.m_Regions, sizeof(u16) * CHUNK_SIZE * CHUNK_SIZE) == 0);
+ }
+#endif
};
typedef std::map > EdgesMap;
- void FindEdges(u8 ci, u8 cj, pass_class_t passClass, EdgesMap& edges);
+ void RecomputeAllEdges(pass_class_t passClass, EdgesMap& edges);
+ void UpdateEdges(u8 ci, u8 cj, pass_class_t passClass, EdgesMap& edges);
void FindReachableRegions(RegionID from, std::set& reachable, pass_class_t passClass);
void FindPassableRegions(std::set& regions, pass_class_t passClass);
+ void FindGoalRegions(u16 gi, u16 gj, const PathGoal& goal, std::set& regions, pass_class_t passClass);
+
+ /*
+ * Helpers for the A* implementation of MakeGoalReachable.
+ * We reuse flat_XX containers to have good cache locality and avoid the cost of allocating memory. Flat_XX implementa map/set as a sorted vector
+ */
+ boost::container::flat_map m_Astar_Predecessor;
+ boost::container::flat_map m_Astar_GScore;
+ boost::container::flat_map m_Astar_FScore;
+ boost::container::flat_set m_Astar_ClosedNodes;
+ boost::container::flat_set m_Astar_OpenNodes;
+
+ inline int DistBetween(const RegionID& a, const RegionID& b)
+ {
+ return (abs(a.ci - b.ci) + abs(a.cj - b.cj)) * CHUNK_SIZE - 30;
+ };
+
/**
* Updates @p iGoal and @p jGoal to the navcell that is the nearest to the
* initial goal coordinates, in one of the given @p regions.
@@ -174,6 +222,9 @@
std::map m_Edges;
+ std::map> m_GlobalRegions;
+ std::vector m_AvailableGlobalRegionIDs; // TODO: actually push back deleted global regions here.
+
// Passability classes for which grids will be updated when calling Update
std::map m_PassClassMasks;
Index: source/simulation2/helpers/HierarchicalPathfinder.cpp
===================================================================
--- source/simulation2/helpers/HierarchicalPathfinder.cpp
+++ source/simulation2/helpers/HierarchicalPathfinder.cpp
@@ -111,13 +111,12 @@
}
// Directly point the root ID
- m_NumRegions = 0;
for (u16 i = 1; i < regionID+1; ++i)
{
- if (connect[i] == i)
- ++m_NumRegions;
- else
+ if (connect[i] != i)
connect[i] = RootID(i, connect);
+ if (std::find(m_RegionsID.begin(),m_RegionsID.end(), connect[i]) == m_RegionsID.end())
+ m_RegionsID.push_back(connect[i]);
}
// Replace IDs by the root ID
@@ -224,6 +223,8 @@
{
case PathGoal::POINT:
{
+ if (gi/CHUNK_SIZE != m_ChunkI || gj/CHUNK_SIZE != m_ChunkJ)
+ return false;
if (m_Regions[gj-m_ChunkJ * CHUNK_SIZE][gi-m_ChunkI * CHUNK_SIZE] == r)
{
iOut = gi;
@@ -366,6 +367,10 @@
m_Chunks.clear();
m_Edges.clear();
+ // reset global regions
+ m_AvailableGlobalRegionIDs.clear();
+ m_AvailableGlobalRegionIDs.push_back(1);
+
for (auto& passClassMask : allPassClasses)
{
pass_class_t passClass = passClassMask.second;
@@ -381,16 +386,35 @@
}
// Construct the search graph over the regions
-
EdgesMap& edges = m_Edges[passClass];
+ RecomputeAllEdges(passClass, edges);
- for (int cj = 0; cj < m_ChunksH; ++cj)
- {
- for (int ci = 0; ci < m_ChunksW; ++ci)
- {
- FindEdges(ci, cj, passClass, edges);
- }
- }
+ // Spread global regions.
+ std::map& globalRegion = m_GlobalRegions[passClass];
+ globalRegion.clear();
+ for (u8 cj = 0; cj < m_ChunksH; ++cj)
+ for (u8 ci = 0; ci < m_ChunksW; ++ci)
+ for (u16 rid : GetChunk(ci, cj, passClass).m_RegionsID)
+ {
+ RegionID reg{ci,cj,rid};
+ if (globalRegion.find(reg) == globalRegion.end())
+ {
+ GlobalRegionID ID = m_AvailableGlobalRegionIDs.back();
+ m_AvailableGlobalRegionIDs.pop_back();
+ if (m_AvailableGlobalRegionIDs.empty())
+ m_AvailableGlobalRegionIDs.push_back(ID+1);
+
+ globalRegion.insert({ reg, ID });
+ // avoid creating an empty link if possible, FindReachableRegions uses [] which calls the default constructor
+ if (edges.find(reg) != edges.end())
+ {
+ std::set reachable;
+ FindReachableRegions(reg, reachable, passClass);
+ for (const RegionID& region : reachable)
+ globalRegion.insert({ region, ID });
+ }
+ }
+ }
}
if (m_DebugOverlay)
@@ -405,9 +429,10 @@
{
PROFILE3("Hierarchical Update");
- for (int cj = 0; cj < m_ChunksH; ++cj)
+ std::vector updated;
+ for (u8 cj = 0; cj < m_ChunksH; ++cj)
{
- for (int ci = 0; ci < m_ChunksW; ++ci)
+ for (u8 ci = 0; ci < m_ChunksW; ++ci)
{
if (!IsChunkDirty(ci, cj, dirtinessGrid))
continue;
@@ -415,25 +440,79 @@
{
pass_class_t passClass = passClassMask.second;
Chunk& a = m_Chunks[passClass].at(ci + cj*m_ChunksW);
+
+ // Clean up edges and global region ID
+ EdgesMap& edgeMap = m_Edges[passClass];
+ for (u16 i : a.m_RegionsID)
+ {
+ RegionID reg{ci, cj, i};
+ m_GlobalRegions[passClass].erase(reg);
+ for (const RegionID& neighbor : edgeMap[reg])
+ {
+ edgeMap[neighbor].erase(reg);
+ if (edgeMap[neighbor].empty())
+ edgeMap.erase(neighbor);
+ }
+ edgeMap.erase(reg);
+ }
+
+ // recompute
a.InitRegions(ci, cj, grid, passClass);
+
+ for (u16 i : a.m_RegionsID)
+ updated.push_back(RegionID{ci, cj, i});
+
+ // add back edges
+ UpdateEdges(ci, cj, passClass, edgeMap);
}
}
}
- // TODO: Also be clever with edges
- m_Edges.clear();
- for (const std::pair& passClassMask : m_PassClassMasks)
- {
- pass_class_t passClass = passClassMask.second;
- EdgesMap& edges = m_Edges[passClass];
+ // Add back global region ID
+ // To try and be clever we'll run a custom flood-fill that stops as soon as it runs into something we know,
+ // and if nothing then we'll create a new global region.
+ // It also keeps track of all connected regions with no IDs in case of contiguous dirtiness (likely) to be faster if possible.
+ // This probably scales poorly with a large enough update?
- for (int cj = 0; cj < m_ChunksH; ++cj)
+ for (const RegionID& reg : updated)
+ for (const std::pair& passClassMask : m_PassClassMasks)
{
- for (int ci = 0; ci < m_ChunksW; ++ci)
+ std::set visited;
+ std::vector open;
+ std::vector updating = { reg };
+ open.push_back(reg);
+
+ GlobalRegionID ID = 0;
+ std::map& globalRegion = m_GlobalRegions[passClassMask.second];
+ EdgesMap& edgeMap = m_Edges[passClassMask.second];
+ // avoid creating empty edges.
+ bool unlinked = edgeMap.find(reg) == edgeMap.end();
+ while (!open.empty() && ID == 0 && !unlinked)
{
- FindEdges(ci, cj, passClass, edges);
+ RegionID curr = open.back();
+ open.pop_back();
+ for (const RegionID& region : edgeMap[curr])
+ if (visited.insert(region).second)
+ {
+ open.push_back(region);
+ if (globalRegion.find(region) != globalRegion.end())
+ {
+ ID = globalRegion.at(region);
+ break;
+ }
+ else
+ updating.push_back(region);
+ }
}
- }
+ if (ID == 0)
+ {
+ ID = m_AvailableGlobalRegionIDs.back();
+ m_AvailableGlobalRegionIDs.pop_back();
+ if (m_AvailableGlobalRegionIDs.empty())
+ m_AvailableGlobalRegionIDs.push_back(ID+1);
+ }
+ for (const RegionID& reg : updating)
+ globalRegion[reg] = ID;
}
if (m_DebugOverlay)
@@ -462,22 +541,15 @@
}
/**
- * Find edges between regions in this chunk and the adjacent below/left chunks.
+ * Connect a chunk's regions to their neighbors. Not optimised for global recomputing.
+ * TODO: reduce code duplication with below
*/
-void HierarchicalPathfinder::FindEdges(u8 ci, u8 cj, pass_class_t passClass, EdgesMap& edges)
+void HierarchicalPathfinder::UpdateEdges(u8 ci, u8 cj, pass_class_t passClass, EdgesMap& edges)
{
std::vector& chunks = m_Chunks[passClass];
Chunk& a = chunks.at(cj*m_ChunksW + ci);
- // For each edge between chunks, we loop over every adjacent pair of
- // navcells in the two chunks. If they are both in valid regions
- // (i.e. are passable navcells) then add a graph edge between those regions.
- // (We don't need to test for duplicates since EdgesMap already uses a
- // std::set which will drop duplicate entries.)
- // But as set.insert can be quite slow on large collection, and that we usually
- // try to insert the same values, we cache the previous one for a fast test.
-
if (ci > 0)
{
Chunk& b = chunks.at(cj*m_ChunksW + (ci-1));
@@ -499,6 +571,27 @@
}
}
+ if (ci < m_ChunksW-1)
+ {
+ Chunk& b = chunks.at(cj*m_ChunksW + (ci+1));
+ RegionID raPrev(0,0,0);
+ RegionID rbPrev(0,0,0);
+ for (int j = 0; j < CHUNK_SIZE; ++j)
+ {
+ RegionID ra = a.Get(CHUNK_SIZE-1, j);
+ RegionID rb = b.Get(0, j);
+ if (ra.r && rb.r)
+ {
+ if (ra == raPrev && rb == rbPrev)
+ continue;
+ edges[ra].insert(rb);
+ edges[rb].insert(ra);
+ raPrev = ra;
+ rbPrev = rb;
+ }
+ }
+ }
+
if (cj > 0)
{
Chunk& b = chunks.at((cj-1)*m_ChunksW + ci);
@@ -520,6 +613,94 @@
}
}
+ if (cj < m_ChunksH - 1)
+ {
+ Chunk& b = chunks.at((cj+1)*m_ChunksW + ci);
+ RegionID raPrev(0,0,0);
+ RegionID rbPrev(0,0,0);
+ for (int i = 0; i < CHUNK_SIZE; ++i)
+ {
+ RegionID ra = a.Get(i, CHUNK_SIZE-1);
+ RegionID rb = b.Get(i, 0);
+ if (ra.r && rb.r)
+ {
+ if (ra == raPrev && rb == rbPrev)
+ continue;
+ edges[ra].insert(rb);
+ edges[rb].insert(ra);
+ raPrev = ra;
+ rbPrev = rb;
+ }
+ }
+ }
+}
+
+/**
+ * Find edges between regions in all chunks, in an optimised manner (only look at top/left)
+ */
+void HierarchicalPathfinder::RecomputeAllEdges(pass_class_t passClass, EdgesMap& edges)
+{
+ std::vector& chunks = m_Chunks[passClass];
+
+ edges.clear();
+
+ for (int cj = 0; cj < m_ChunksH; ++cj)
+ {
+ for (int ci = 0; ci < m_ChunksW; ++ci)
+ {
+ Chunk& a = chunks.at(cj*m_ChunksW + ci);
+
+ // For each edge between chunks, we loop over every adjacent pair of
+ // navcells in the two chunks. If they are both in valid regions
+ // (i.e. are passable navcells) then add a graph edge between those regions.
+ // (We don't need to test for duplicates since EdgesMap already uses a
+ // std::set which will drop duplicate entries.)
+ // But as set.insert can be quite slow on large collection, and that we usually
+ // try to insert the same values, we cache the previous one for a fast test.
+
+ if (ci > 0)
+ {
+ Chunk& b = chunks.at(cj*m_ChunksW + (ci-1));
+ RegionID raPrev(0,0,0);
+ RegionID rbPrev(0,0,0);
+ for (int j = 0; j < CHUNK_SIZE; ++j)
+ {
+ RegionID ra = a.Get(0, j);
+ RegionID rb = b.Get(CHUNK_SIZE-1, j);
+ if (ra.r && rb.r)
+ {
+ if (ra == raPrev && rb == rbPrev)
+ continue;
+ edges[ra].insert(rb);
+ edges[rb].insert(ra);
+ raPrev = ra;
+ rbPrev = rb;
+ }
+ }
+ }
+
+ if (cj > 0)
+ {
+ Chunk& b = chunks.at((cj-1)*m_ChunksW + ci);
+ RegionID raPrev(0,0,0);
+ RegionID rbPrev(0,0,0);
+ for (int i = 0; i < CHUNK_SIZE; ++i)
+ {
+ RegionID ra = a.Get(i, 0);
+ RegionID rb = b.Get(i, CHUNK_SIZE-1);
+ if (ra.r && rb.r)
+ {
+ if (ra == raPrev && rb == rbPrev)
+ continue;
+ edges[ra].insert(rb);
+ edges[rb].insert(ra);
+ raPrev = ra;
+ rbPrev = rb;
+ }
+ }
+ }
+ }
+ }
}
/**
@@ -557,7 +738,7 @@
xz.push_back(b.Y.ToFloat());
m_DebugOverlayLines.emplace_back();
- m_DebugOverlayLines.back().m_Color = CColor(1.0, 1.0, 1.0, 1.0);
+ m_DebugOverlayLines.back().m_Color = CColor(1.0, 0.0, 0.0, 1.0);
SimRender::ConstructLineOnGround(*m_SimContext, xz, m_DebugOverlayLines.back(), true);
}
}
@@ -571,75 +752,283 @@
return m_Chunks[passClass][cj*m_ChunksW + ci].Get(i % CHUNK_SIZE, j % CHUNK_SIZE);
}
-void HierarchicalPathfinder::MakeGoalReachable(u16 i0, u16 j0, PathGoal& goal, pass_class_t passClass)
+HierarchicalPathfinder::GlobalRegionID HierarchicalPathfinder::GetGlobalRegion(u16 i, u16 j, pass_class_t passClass)
{
- PROFILE2("MakeGoalReachable");
+ RegionID region = Get(i, j, passClass);
+ if (region.r == 0)
+ return (GlobalRegionID)0;
+ return m_GlobalRegions[passClass][region];
+}
+
+#define OUTPUT 0
+
+#if OUTPUT
+ #include
+#endif
+
+#if OUTPUT
+// also change the header
+bool HierarchicalPathfinder::MakeGoalReachable(u16 i0, u16 j0, PathGoal& goal, pass_class_t passClass, std::ofstream& stream)
+#else
+bool HierarchicalPathfinder::MakeGoalReachable(u16 i0, u16 j0, PathGoal& goal, pass_class_t passClass)
+#endif
+{
+ /*
+ * Relatively straightforward implementation of A* on the hierarchical pathfinder graph.
+ * Since this isn't a grid, we cannot use JPS (though I'm fairly sure it could sort of be extended to work, but it's probably not trivial/worth it)
+ * Uses flat_set and flat_map over std::set and std::map since testing proves that reusing the memory ends up being more efficient
+ * The main optimisations are:
+ * - picking the best item directly from the open list when we can be sure we know which one it is (see fasttrack)
+ * - checking whether the goal is reachable or not, and if it isn't stopping early to avoid slowly flood-filling everything
+ *
+ * Since we'd like to return the best possible navcell, if the goal is reachable, we'll stop A* once we've reached any goal region
+ * since then presumably other reachable goal-regions would be reachable following roughtly the same path.
+ * Then we'll loop over goal regions to get the best navcell and reconstruct the path from there.
+ *
+ * NB: since the path is currently unused, I skip the A* part for reachable goals.
+ */
RegionID source = Get(i0, j0, passClass);
- // Find everywhere that's reachable
- std::set reachableRegions;
- FindReachableRegions(source, reachableRegions, passClass);
+ u16 gi, gj;
+ Pathfinding::NearestNavcell(goal.x, goal.z, gi, gj, m_W, m_H);
- // Check whether any reachable region contains the goal
- // And get the navcell that's the closest to the point
+ // determine if we will be able to reach the goal.
+ // If not, we can stop A* earlier by being clever.
+ std::set goalRegions;
+ FindGoalRegions(gi, gj, goal, goalRegions, passClass);
+
+ std::vector reachableGoalRegions;
+
+ GlobalRegionID startID = GetGlobalRegion(i0, j0, passClass);
+ bool reachable = false;
+ for (const RegionID& r : goalRegions)
+ if (m_GlobalRegions[passClass][r] == startID)
+ {
+ reachable = true;
+ reachableGoalRegions.push_back(r);
+ }
- u16 bestI = 0;
- u16 bestJ = 0;
- u32 dist2Best = std::numeric_limits::max();
+#if OUTPUT
+ stream << "context.fillStyle = 'rgba(1,0,1,1)';\n";
+ for (const RegionID& r : goalRegions)
+ {
+ entity_pos_t x0 = Pathfinding::NAVCELL_SIZE * (r.ci * CHUNK_SIZE);
+ entity_pos_t z0 = Pathfinding::NAVCELL_SIZE * (r.cj * CHUNK_SIZE);
+ stream << "context2.fillRect(" << x0.ToInt_RoundToZero() << " * scale," << z0.ToInt_RoundToZero() << " * scale," << (int)CHUNK_SIZE << " * scale," << (int)CHUNK_SIZE << " * scale);\n";
+ }
+#endif
+
+ // In general, our maps are relatively open, so it's usually a better bet to be biaised towards minimal distance over path length.
+ int (*DistEstimate)(u16, u16, u16, u16) = [](u16 regI, u16 regJ, u16 gi, u16 gj) -> int { return (regI - gi)*(regI - gi) + (regJ - gj)*(regJ - gj); };
+ // However, run unbiaised euclidian if we know the goal is unreachable, since we want to get as close as possible efficiently.
+ // multiply by 20 because we want distance to goal to matter a lot
+ if (!reachable)
+ DistEstimate = [](u16 regI, u16 regJ, u16 gi, u16 gj) -> int {
+ return 20 * isqrt64((regI - gi)*(regI - gi) + (regJ - gj)*(regJ - gj));
+ };
+
+ m_Astar_ClosedNodes.clear();
+ m_Astar_OpenNodes.clear();
+ m_Astar_OpenNodes.insert(source);
+
+ m_Astar_Predecessor.clear();
+
+ m_Astar_GScore.clear();
+ m_Astar_GScore[source] = 0;
+
+ m_Astar_FScore.clear();
+ m_Astar_FScore[source] = DistEstimate(source.ci * CHUNK_SIZE + CHUNK_SIZE/2, source.cj * CHUNK_SIZE + CHUNK_SIZE/2, gi, gj);
+
+ RegionID current {0,0,0};
+
+ u16 bestI, bestJ;
+ u32 dist2;
+
+ u32 timeSinceLastFScoreImprovement = 0;
+#if OUTPUT
+ int step = 0;
+#endif
+
+ RegionID fastTrack = source;
+ int currentFScore = m_Astar_FScore[source];
+ int secondBestFScore = currentFScore;
+ int globalBestFScore = currentFScore;
+
+ EdgesMap& edgeMap = m_Edges[passClass];
+
+ // NB: to re-enable A* for the reachable case (if you want to use the path), remove the "!reachable" part of this check
+ while (!reachable && !m_Astar_OpenNodes.empty())
+ {
+ // Since we are not using a fancy open list, we have to go through all nodes each time
+ // So when we are sure that we know the best node (because the last run gave us a node better than us, which was already the best
+ // we can fast-track and not sort but just pick that one instead.
+ // In cases where the obvious path is the best, we hardly ever sort and it's a little faster
+ if (fastTrack.r)
+ {
+ current = fastTrack;
+ currentFScore = m_Astar_FScore[current];
+ secondBestFScore = currentFScore;
+ }
+ else
+ {
+ auto iter = m_Astar_OpenNodes.begin();
+ current = *iter;
+ currentFScore = m_Astar_FScore[current];
+ secondBestFScore = currentFScore;
+ while (++iter != m_Astar_OpenNodes.end())
+ {
+ int score = m_Astar_FScore[*iter];
+ if (score < currentFScore)
+ {
+ current = *iter;
+ secondBestFScore = currentFScore;
+ currentFScore = score;
+ }
+ }
+ }
- for (const RegionID& region : reachableRegions)
- {
- // Skip region if its chunk doesn't contain the goal area
- entity_pos_t x0 = Pathfinding::NAVCELL_SIZE * (region.ci * CHUNK_SIZE);
- entity_pos_t z0 = Pathfinding::NAVCELL_SIZE * (region.cj * CHUNK_SIZE);
+ m_Astar_OpenNodes.erase(current);
+ m_Astar_ClosedNodes.emplace(current);
+ if (reachable)
+ m_Astar_FScore.erase(current);
+ m_Astar_GScore.erase(current);
+
+ // Stop heuristic in case we know we cannot reach the goal.
+ // Indeed this would cause A* to become an inacceptably slow flood fill.
+ // We keep track of our best fScore, we'll early-exit if we're too far from it
+ // or we haven't found a better path in a while.
+ // This will cause us to return largely suboptimal paths now and then,
+ // but then again those should be rare and the player can just re-order a move.
+ if (!reachable)
+ {
+ if (currentFScore < globalBestFScore)
+ {
+ globalBestFScore = currentFScore;
+ timeSinceLastFScoreImprovement = 0;
+ }
+ else if ( (++timeSinceLastFScoreImprovement > 3 && currentFScore > globalBestFScore * 2) || timeSinceLastFScoreImprovement > m_ChunksW)
+ break;
+ }
+
+ entity_pos_t x0 = Pathfinding::NAVCELL_SIZE * (current.ci * CHUNK_SIZE);
+ entity_pos_t z0 = Pathfinding::NAVCELL_SIZE * (current.cj * CHUNK_SIZE);
entity_pos_t x1 = x0 + Pathfinding::NAVCELL_SIZE * CHUNK_SIZE;
entity_pos_t z1 = z0 + Pathfinding::NAVCELL_SIZE * CHUNK_SIZE;
- if (!goal.RectContainsGoal(x0, z0, x1, z1))
- continue;
- u16 i,j;
- u32 dist2;
+#if OUTPUT
+ stream << "context.fillStyle = 'rgba(" < 0 ? 255 : 0) <<",0.8)';\n maxStep = " << step+1 << ";\n";
+ stream << "if (step >= " << step << ") context.fillRect(" << x0.ToInt_RoundToZero() << " * scale," << z0.ToInt_RoundToZero() << " * scale," << (int)CHUNK_SIZE << " * scale," << (int)CHUNK_SIZE << " * scale);\n";
+#endif
+
+ fastTrack = RegionID{0,0,0};
+
+ // TODO: we should get those first and then validate here, instead of recomputing for each.
+ if (goal.RectContainsGoal(x0, z0, x1, z1))
+ if (GetChunk(current.ci, current.cj, passClass).RegionNearestNavcellInGoal(current.r, i0, j0, goal, bestI, bestJ, dist2))
+ break;
- // If the region contains the goal area, the goal is reachable
- // Remember the best point for optimization.
- if (GetChunk(region.ci, region.cj, passClass).RegionNearestNavcellInGoal(region.r, i0, j0, goal, i, j, dist2))
- {
- // If it's a point, no need to move it, we're done
- if (goal.type == PathGoal::POINT)
- return;
- if (dist2 < dist2Best)
+ int currScore = m_Astar_GScore[current];
+ for (const RegionID& neighbor : edgeMap[current])
+ {
+ if (m_Astar_ClosedNodes.find(neighbor) != m_Astar_ClosedNodes.end())
+ continue;
+ int temp_m_Astar_GScore = currScore + DistBetween(neighbor, current);
+ auto iter = m_Astar_OpenNodes.emplace(neighbor);
+ if (!iter.second && temp_m_Astar_GScore >= m_Astar_GScore[neighbor])
+ continue;
+#if OUTPUT
+ x0 = Pathfinding::NAVCELL_SIZE * (neighbor.ci * CHUNK_SIZE);
+ z0 = Pathfinding::NAVCELL_SIZE * (neighbor.cj * CHUNK_SIZE);
+ stream << "context2.fillStyle = 'rgba(255,255,0,0.3)';\n";
+ stream << "if (step >= " << step << ") context2.fillRect(" << x0.ToInt_RoundToZero() << " * scale," << z0.ToInt_RoundToZero() << " * scale," << (int)CHUNK_SIZE << " * scale," << (int)CHUNK_SIZE << " * scale);\n";
+#endif
+
+ m_Astar_GScore[neighbor] = temp_m_Astar_GScore;
+ // no default constructor so we'll use this hack in the meantime
+ auto alreadyThere = m_Astar_Predecessor.emplace( boost::container::flat_map::value_type{ neighbor, current });
+ alreadyThere.first->second = current;
+ int score;
+ // if the goal is reachable, we don't care much about fscore precision so pick the center
+ if (reachable)
+ score = temp_m_Astar_GScore + DistEstimate(neighbor.ci * CHUNK_SIZE + CHUNK_SIZE/2, neighbor.cj * CHUNK_SIZE + CHUNK_SIZE/2, gi, gj);
+ else
{
- bestI = i;
- bestJ = j;
- dist2Best = dist2;
+ // if it's unreachable, it's more important however. So when we're close, get the "region center".
+ entity_pos_t x0 = Pathfinding::NAVCELL_SIZE * (neighbor.ci * CHUNK_SIZE);
+ entity_pos_t z0 = Pathfinding::NAVCELL_SIZE * (neighbor.cj * CHUNK_SIZE);
+ entity_pos_t x1 = x0 + Pathfinding::NAVCELL_SIZE * CHUNK_SIZE;
+ entity_pos_t z1 = z0 + Pathfinding::NAVCELL_SIZE * CHUNK_SIZE;
+ if (goal.RectContainsGoal(x0, z0, x1, z1))
+ {
+ int ri, rj;
+ GetChunk(neighbor.ci, neighbor.cj, passClass).RegionCenter(neighbor.r, ri, rj);
+ score = temp_m_Astar_GScore + DistEstimate((u16)ri, (u16)rj, gi, gj);
+ }
+ else
+ score = temp_m_Astar_GScore + DistEstimate(neighbor.ci * CHUNK_SIZE + CHUNK_SIZE/2, neighbor.cj * CHUNK_SIZE + CHUNK_SIZE/2, gi, gj);
}
+ if (score < secondBestFScore)
+ {
+ secondBestFScore = score;
+ fastTrack = neighbor;
+ }
+ m_Astar_FScore[neighbor] = score;
}
+#if OUTPUT
+ step++;
+#endif
}
- // If the goal area wasn't reachable,
- // find the navcell that's nearest to the goal's center
- if (dist2Best == std::numeric_limits::max())
- {
- u16 iGoal, jGoal;
- Pathfinding::NearestNavcell(goal.x, goal.z, iGoal, jGoal, m_W, m_H);
-
- FindNearestNavcellInRegions(reachableRegions, iGoal, jGoal, passClass);
-
- // Construct a new point goal at the nearest reachable navcell
- PathGoal newGoal;
- newGoal.type = PathGoal::POINT;
- Pathfinding::NavcellCenter(iGoal, jGoal, newGoal.x, newGoal.z);
- goal = newGoal;
- return;
+#if OUTPUT
+ fixed x0 = Pathfinding::NAVCELL_SIZE * (current.ci * CHUNK_SIZE);
+ fixed z0 = Pathfinding::NAVCELL_SIZE * (current.cj * CHUNK_SIZE);
+ stream << "context.fillStyle = 'rgba(255,0,0,0.6)';\n";
+ stream << "if (step >= " << step << ") context.fillRect(" << x0.ToInt_RoundToZero() << " * scale," << z0.ToInt_RoundToZero() << " * scale," << (int)CHUNK_SIZE << " * scale," << (int)CHUNK_SIZE << " * scale);\n";
+#endif
+
+ if (!reachable)
+ {
+ // I don't believe this is possible, nor should it.
+ ENSURE(!m_Astar_ClosedNodes.empty());
+
+ // Pick best and roll with that.
+ current = *std::min_element(m_Astar_ClosedNodes.begin(), m_Astar_ClosedNodes.end(),
+ [this](const RegionID& a, const RegionID& b) -> bool { return m_Astar_FScore[a] < m_Astar_FScore[b]; });
+
+ std::set set = { current };
+ Pathfinding::NearestNavcell(goal.x, goal.z, bestI, bestJ, m_W, m_H);
+
+ FindNearestNavcellInRegions(set, bestI, bestJ, passClass);
+ }
+ else
+ {
+ u32 bestDist = std::numeric_limits::max();
+ // loop through reachable goal regions and get the best navcell.
+ // TODO: we probably could skip some of those if our gScore/fScore were good enough.
+ for (const RegionID& region : reachableGoalRegions)
+ {
+ u16 ri, rj;
+ u32 dist;
+ // TODO: using the A* path, we should consider from predecessor and not from source
+ GetChunk(region.ci, region.cj, passClass).RegionNearestNavcellInGoal(region.r, i0, j0, goal, ri, rj, dist);
+ if (dist < bestDist)
+ {
+ bestI = ri;
+ bestJ = rj;
+ bestDist = dist;
+ }
+ }
}
- ENSURE(dist2Best != std::numeric_limits::max());
PathGoal newGoal;
newGoal.type = PathGoal::POINT;
Pathfinding::NavcellCenter(bestI, bestJ, newGoal.x, newGoal.z);
goal = newGoal;
+
+ return reachable;
}
+
void HierarchicalPathfinder::FindNearestPassableNavcell(u16& i, u16& j, pass_class_t passClass)
{
std::set regions;
@@ -710,15 +1099,16 @@
// collecting all the regions that are reachable via edges
std::vector open;
+ open.reserve(64);
open.push_back(from);
reachable.insert(from);
+ EdgesMap& edgeMap = m_Edges[passClass];
while (!open.empty())
{
RegionID curr = open.back();
open.pop_back();
-
- for (const RegionID& region : m_Edges[passClass][curr])
+ for (const RegionID& region : edgeMap[curr])
// Add to the reachable set; if this is the first time we added
// it then also add it to the open list
if (reachable.insert(region).second)
@@ -731,12 +1121,43 @@
// Construct a set of all regions of all chunks for this pass class
for (const Chunk& chunk : m_Chunks[passClass])
{
- // region 0 is impassable tiles
- for (int r = 1; r <= chunk.m_NumRegions; ++r)
+ for (u16 r : chunk.m_RegionsID)
regions.insert(RegionID(chunk.m_ChunkI, chunk.m_ChunkJ, r));
}
}
+void HierarchicalPathfinder::FindGoalRegions(u16 gi, u16 gj, const PathGoal& goal, std::set& regions, pass_class_t passClass)
+{
+ if (goal.type == PathGoal::POINT)
+ {
+ RegionID region = Get(gi, gj, passClass);
+ if (region.r > 0)
+ regions.insert(region);
+ return;
+ }
+
+ // For non-point cases, we'll test each region inside the bounds of the goal.
+ // we might occasionally test a few too many for circles but it's not too bad.
+ // Note that this also works in the Inverse-circle / Inverse-square case
+ // Since our ranges are inclusive, we will necessarily test at least the perimeter/outer bound of the goal.
+ // If we find a navcell, great, if not, well then we'll be surrounded by an impassable barrier.
+ // Since in the Inverse-XX case we're supposed to start inside, then we can't ever reach the goal so it's good enough.
+ // It's not worth it to skip the "inner" regions since we'd need ranges above CHUNK_SIZE for that to start mattering
+ // (and even then not always) and that just doesn't happen for Inverse-XX goals
+ int size = (std::max(goal.hh, goal.hw) * 3 / 2).ToInt_RoundToInfinity();
+
+ u16 a,b; u32 c; // unused params for RegionNearestNavcellInGoal
+
+ for (u8 sz = (gj - size) / CHUNK_SIZE; sz <= (gj + size) / CHUNK_SIZE; ++sz)
+ for (u8 sx = (gi - size) / CHUNK_SIZE; sx <= (gi + size) / CHUNK_SIZE; ++sx)
+ {
+ Chunk& chunk = GetChunk(sx, sz, passClass);
+ for (u16 i : chunk.m_RegionsID)
+ if (chunk.RegionNearestNavcellInGoal(i, 0, 0, goal, a, b, c))
+ regions.insert(RegionID{sx, sz, i});
+ }
+}
+
void HierarchicalPathfinder::FillRegionOnGrid(const RegionID& region, pass_class_t passClass, u16 value, Grid& grid)
{
ENSURE(grid.m_W == m_W && grid.m_H == m_H);
Index: source/simulation2/helpers/LongPathfinder.h
===================================================================
--- source/simulation2/helpers/LongPathfinder.h
+++ source/simulation2/helpers/LongPathfinder.h
@@ -164,6 +164,10 @@
LongPathfinder();
~LongPathfinder();
+#ifdef TEST
+ HierarchicalPathfinder& GetHierarchicalPathfinder() { return m_PathfinderHier; }
+#endif
+
void SetDebugOverlay(bool enabled);
void SetHierDebugOverlay(bool enabled, const CSimContext *simContext)
@@ -239,6 +243,16 @@
void ComputePath(entity_pos_t x0, entity_pos_t z0, const PathGoal& origGoal,
pass_class_t passClass, std::vector excludedRegions, WaypointPath& path);
+ bool MakeGoalReachable(u16 i0, u16 j0, PathGoal &goal, pass_class_t passClass) { return m_PathfinderHier.MakeGoalReachable(i0, j0, goal, passClass); };
+
+ void FindNearestPassableNavcell(u16& i, u16& j, pass_class_t passClass) { return m_PathfinderHier.FindNearestPassableNavcell(i, j, passClass); };
+
+ bool NavcellIsReachable(u16 i0, u16 j0, u16 i1, u16 j1, pass_class_t passClass)
+ {
+ return m_PathfinderHier.GetGlobalRegion(i0, j0, passClass) == m_PathfinderHier.GetGlobalRegion(i1, j1, passClass);
+ };
+
+
Grid GetConnectivityGrid(pass_class_t passClass)
{
return m_PathfinderHier.GetConnectivityGrid(passClass);
Index: source/simulation2/helpers/PathGoal.h
===================================================================
--- source/simulation2/helpers/PathGoal.h
+++ source/simulation2/helpers/PathGoal.h
@@ -28,6 +28,7 @@
* part of the goal.
* Also, it can be an 'inverted' circle/square, where any point outside
* the shape is part of the goal.
+ * In both cases, points on the range (ie at the frontier) are considered inside.
*/
class PathGoal
{
Index: source/simulation2/helpers/Pathfinding.h
===================================================================
--- source/simulation2/helpers/Pathfinding.h
+++ source/simulation2/helpers/Pathfinding.h
@@ -129,6 +129,7 @@
* between translation units.
* TODO: figure out whether this is actually needed. It was added back in r8751 (in 2010) for unclear reasons
* and it does not seem to really improve behavior today
+ * Note by Wraitii to wraitii: you just removed this in UnitMotion, delete it if it ends up being unecessary as expected.
*/
const entity_pos_t GOAL_DELTA = NAVCELL_SIZE/8;
Index: source/simulation2/scripting/MessageTypeConversions.cpp
===================================================================
--- source/simulation2/scripting/MessageTypeConversions.cpp
+++ source/simulation2/scripting/MessageTypeConversions.cpp
@@ -267,20 +267,74 @@
////////////////////////////////
-JS::Value CMessageMotionChanged::ToJSVal(ScriptInterface& scriptInterface) const
+JS::Value CMessageBeginMove::ToJSVal(ScriptInterface& scriptInterface) const
{
TOJSVAL_SETUP();
- SET_MSG_PROPERTY(starting);
- SET_MSG_PROPERTY(error);
return JS::ObjectValue(*obj);
}
-CMessage* CMessageMotionChanged::FromJSVal(ScriptInterface& scriptInterface, JS::HandleValue val)
+CMessage* CMessageBeginMove::FromJSVal(ScriptInterface& scriptInterface, JS::HandleValue val)
{
FROMJSVAL_SETUP();
- GET_MSG_PROPERTY(bool, starting);
- GET_MSG_PROPERTY(bool, error);
- return new CMessageMotionChanged(starting, error);
+ return new CMessageBeginMove();
+}
+
+////////////////////////////////
+
+JS::Value CMessagePausedMove::ToJSVal(ScriptInterface& scriptInterface) const
+{
+ TOJSVAL_SETUP();
+ return JS::ObjectValue(*obj);
+}
+
+CMessage* CMessagePausedMove::FromJSVal(ScriptInterface& scriptInterface, JS::HandleValue val)
+{
+ FROMJSVAL_SETUP();
+ return new CMessagePausedMove();
+}
+
+////////////////////////////////
+
+JS::Value CMessageFinishedMove::ToJSVal(ScriptInterface& scriptInterface) const
+{
+ TOJSVAL_SETUP();
+ SET_MSG_PROPERTY(failed);
+ return JS::ObjectValue(*obj);
+}
+
+CMessage* CMessageFinishedMove::FromJSVal(ScriptInterface& scriptInterface, JS::HandleValue val)
+{
+ FROMJSVAL_SETUP();
+ GET_MSG_PROPERTY(bool, failed);
+ return new CMessageFinishedMove(failed);
+}
+
+////////////////////////////////
+
+JS::Value CMessageMoveSuccess::ToJSVal(ScriptInterface& scriptInterface) const
+{
+ TOJSVAL_SETUP();
+ return JS::ObjectValue(*obj);
+}
+
+CMessage* CMessageMoveSuccess::FromJSVal(ScriptInterface& scriptInterface, JS::HandleValue val)
+{
+ FROMJSVAL_SETUP();
+ return new CMessageMoveSuccess();
+}
+
+////////////////////////////////
+
+JS::Value CMessageMoveFailure::ToJSVal(ScriptInterface& scriptInterface) const
+{
+ TOJSVAL_SETUP();
+ return JS::ObjectValue(*obj);
+}
+
+CMessage* CMessageMoveFailure::FromJSVal(ScriptInterface& scriptInterface, JS::HandleValue val)
+{
+ FROMJSVAL_SETUP();
+ return new CMessageMoveFailure();
}
////////////////////////////////
Index: source/tools/atlas/GameInterface/ActorViewer.cpp
===================================================================
--- source/tools/atlas/GameInterface/ActorViewer.cpp
+++ source/tools/atlas/GameInterface/ActorViewer.cpp
@@ -375,7 +375,7 @@
{
CmpPtr cmpUnitMotion(m.Simulation2, m.Entity);
if (cmpUnitMotion)
- speed = cmpUnitMotion->GetWalkSpeed().ToFloat();
+ speed = cmpUnitMotion->GetBaseSpeed().ToFloat();
else
speed = 7.f; // typical unit speed
@@ -385,7 +385,7 @@
{
CmpPtr cmpUnitMotion(m.Simulation2, m.Entity);
if (cmpUnitMotion)
- speed = cmpUnitMotion->GetRunSpeed().ToFloat();
+ speed = cmpUnitMotion->GetBaseSpeed().ToFloat() * cmpUnitMotion->GetTopSpeedRatio().ToFloat();
else
speed = 12.f; // typical unit speed