Page MenuHomeWildfire Games
Differential D1908 Diff 8861 source/simulation2/helpers/VertexPathfinder.cpp

Changeset View

Standalone View

View Options

source/simulation2/helpers/VertexPathfinder.cpp

Show First 20 Lines • Show All 575 Lines • ▼ Show 20 Lines for (size_t i = 0; i < squares.size(); ++i)
CFixedVector2D hd1(squares[i].hw + pathfindClearance + EDGE_EXPAND_DELTA, -(squares[i].hh + pathfindClearance + EDGE_EXPAND_DELTA)); CFixedVector2D hd1(squares[i].hw + pathfindClearance + EDGE_EXPAND_DELTA, -(squares[i].hh + pathfindClearance + EDGE_EXPAND_DELTA));
// Check whether this is an axis-aligned square // Check whether this is an axis-aligned square
bool aa = (u.X == fixed::FromInt(1) && u.Y == fixed::Zero() && v.X == fixed::Zero() && v.Y == fixed::FromInt(1)); bool aa = (u.X == fixed::FromInt(1) && u.Y == fixed::Zero() && v.X == fixed::Zero() && v.Y == fixed::FromInt(1));
Vertex vert; Vertex vert;
vert.status = Vertex::UNEXPLORED; vert.status = Vertex::UNEXPLORED;
vert.quadInward = QUADRANT_NONE; vert.quadInward = QUADRANT_NONE;
vert.quadOutward = QUADRANT_ALL;
vert.p.X = center.X - hd0.Dot(u); vert.p.X = center.X - hd0.Dot(u);
vert.p.Y = center.Y + hd0.Dot(v); vert.p.Y = center.Y + hd0.Dot(v);
if (aa) vert.quadInward = QUADRANT_BR; if (aa)
{
vert.quadInward = QUADRANT_BR;
vert.quadOutward = (~vert.quadInward) & 0xF;
}
if (vert.p.X >= rangeXMin && vert.p.Y >= rangeZMin && vert.p.X <= rangeXMax && vert.p.Y <= rangeZMax) if (vert.p.X >= rangeXMin && vert.p.Y >= rangeZMin && vert.p.X <= rangeXMax && vert.p.Y <= rangeZMax)
m_Vertexes.push_back(vert); m_Vertexes.push_back(vert);
vert.p.X = center.X - hd1.Dot(u); vert.p.X = center.X - hd1.Dot(u);
vert.p.Y = center.Y + hd1.Dot(v); vert.p.Y = center.Y + hd1.Dot(v);
if (aa) vert.quadInward = QUADRANT_TR; if (aa)
{
vert.quadInward = QUADRANT_TR;
vert.quadOutward = (~vert.quadInward) & 0xF;
}
if (vert.p.X >= rangeXMin && vert.p.Y >= rangeZMin && vert.p.X <= rangeXMax && vert.p.Y <= rangeZMax) if (vert.p.X >= rangeXMin && vert.p.Y >= rangeZMin && vert.p.X <= rangeXMax && vert.p.Y <= rangeZMax)
m_Vertexes.push_back(vert); m_Vertexes.push_back(vert);
vert.p.X = center.X + hd0.Dot(u); vert.p.X = center.X + hd0.Dot(u);
vert.p.Y = center.Y - hd0.Dot(v); vert.p.Y = center.Y - hd0.Dot(v);
if (aa) vert.quadInward = QUADRANT_TL; if (aa)
{
vert.quadInward = QUADRANT_TL;
vert.quadOutward = (~vert.quadInward) & 0xF;
}
if (vert.p.X >= rangeXMin && vert.p.Y >= rangeZMin && vert.p.X <= rangeXMax && vert.p.Y <= rangeZMax) if (vert.p.X >= rangeXMin && vert.p.Y >= rangeZMin && vert.p.X <= rangeXMax && vert.p.Y <= rangeZMax)
m_Vertexes.push_back(vert); m_Vertexes.push_back(vert);
vert.p.X = center.X + hd1.Dot(u); vert.p.X = center.X + hd1.Dot(u);
vert.p.Y = center.Y - hd1.Dot(v); vert.p.Y = center.Y - hd1.Dot(v);
if (aa) vert.quadInward = QUADRANT_BL; if (aa)
{
vert.quadInward = QUADRANT_BL;
vert.quadOutward = (~vert.quadInward) & 0xF;
}
if (vert.p.X >= rangeXMin && vert.p.Y >= rangeZMin && vert.p.X <= rangeXMax && vert.p.Y <= rangeZMax) if (vert.p.X >= rangeXMin && vert.p.Y >= rangeZMin && vert.p.X <= rangeXMax && vert.p.Y <= rangeZMax)
m_Vertexes.push_back(vert); m_Vertexes.push_back(vert);
// Add the edges: // Add the edges:
CFixedVector2D h0(squares[i].hw + pathfindClearance, squares[i].hh + pathfindClearance); CFixedVector2D h0(squares[i].hw + pathfindClearance, squares[i].hh + pathfindClearance);
CFixedVector2D h1(squares[i].hw + pathfindClearance, -(squares[i].hh + pathfindClearance)); CFixedVector2D h1(squares[i].hw + pathfindClearance, -(squares[i].hh + pathfindClearance));
Show All 17 LinesWaypointPath VertexPathfinder::ComputeShortPath(const ShortPathRequest& request, CmpPtr<ICmpObstructionManager> cmpObstructionManager) const
{ {
u16 i0, j0, i1, j1; u16 i0, j0, i1, j1;
Pathfinding::NearestNavcell(rangeXMin, rangeZMin, i0, j0, m_MapSize*Pathfinding::NAVCELLS_PER_TILE, m_MapSize*Pathfinding::NAVCELLS_PER_TILE); Pathfinding::NearestNavcell(rangeXMin, rangeZMin, i0, j0, m_MapSize*Pathfinding::NAVCELLS_PER_TILE, m_MapSize*Pathfinding::NAVCELLS_PER_TILE);
Pathfinding::NearestNavcell(rangeXMax, rangeZMax, i1, j1, m_MapSize*Pathfinding::NAVCELLS_PER_TILE, m_MapSize*Pathfinding::NAVCELLS_PER_TILE); Pathfinding::NearestNavcell(rangeXMax, rangeZMax, i1, j1, m_MapSize*Pathfinding::NAVCELLS_PER_TILE, m_MapSize*Pathfinding::NAVCELLS_PER_TILE);
AddTerrainEdges(m_Edges, m_Vertexes, i0, j0, i1, j1, request.passClass, *m_TerrainOnlyGrid); AddTerrainEdges(m_Edges, m_Vertexes, i0, j0, i1, j1, request.passClass, *m_TerrainOnlyGrid);
} }
// Clip out vertices that are inside an edgeSquare (i.e. trivially unreachable) // Clip out vertices that are inside an edgeSquare (i.e. trivially unreachable)
for (size_t i = 0; i < m_EdgeSquares.size(); ++i) for (size_t i = 2; i < m_EdgeSquares.size(); ++i)
{ {
// If the start point is inside the square, ignore it // If the start point is inside the square, ignore it
if (start.p.X >= m_EdgeSquares[i].p0.X && if (start.p.X >= m_EdgeSquares[i].p0.X &&
start.p.Y >= m_EdgeSquares[i].p0.Y && start.p.Y >= m_EdgeSquares[i].p0.Y &&
start.p.X <= m_EdgeSquares[i].p1.X && start.p.X <= m_EdgeSquares[i].p1.X &&
start.p.Y <= m_EdgeSquares[i].p1.Y) start.p.Y <= m_EdgeSquares[i].p1.Y)
continue; continue;
▲ Show 20 Lines • Show All 66 Lines • ▼ Show 20 Lines for (size_t n = 0; n < m_Vertexes.size(); ++n)
CFixedVector2D npos; CFixedVector2D npos;
if (n == GOAL_VERTEX_ID) if (n == GOAL_VERTEX_ID)
{ {
npos = request.goal.NearestPointOnGoal(m_Vertexes[curr.id].p); npos = request.goal.NearestPointOnGoal(m_Vertexes[curr.id].p);
// To prevent integer overflows later on, we need to ensure all vertexes are // To prevent integer overflows later on, we need to ensure all vertexes are
// 'close' to the source. The goal might be far away (not a good idea but // 'close' to the source. The goal might be far away (not a good idea but
// sometimes it happens), so clamp it to the current search range // sometimes it happens), so clamp it to the current search range
npos.X = clamp(npos.X, rangeXMin, rangeXMax); npos.X = clamp(npos.X, rangeXMin + EDGE_EXPAND_DELTA, rangeXMax - EDGE_EXPAND_DELTA);
npos.Y = clamp(npos.Y, rangeZMin, rangeZMax); npos.Y = clamp(npos.Y, rangeZMin + EDGE_EXPAND_DELTA, rangeZMax - EDGE_EXPAND_DELTA);
wraitiiAuthorUnsubmitted
Done
Inline Actions

This is needed so the target point doesn't occasionally get seen a being behind the domain edges.

wraitii: This is needed so the target point doesn't occasionally get seen a being behind the domain…
} }
else else
npos = m_Vertexes[n].p; npos = m_Vertexes[n].p;
// Work out which quadrant(s) we're approaching the new vertex from // Work out which quadrant(s) we're approaching the new vertex from
u8 quad = 0; u8 quad = 0;
if (m_Vertexes[curr.id].p.X <= npos.X && m_Vertexes[curr.id].p.Y <= npos.Y) quad |= QUADRANT_BL; if (m_Vertexes[curr.id].p.X <= npos.X && m_Vertexes[curr.id].p.Y <= npos.Y) quad |= QUADRANT_BL;
if (m_Vertexes[curr.id].p.X >= npos.X && m_Vertexes[curr.id].p.Y >= npos.Y) quad |= QUADRANT_TR; if (m_Vertexes[curr.id].p.X >= npos.X && m_Vertexes[curr.id].p.Y >= npos.Y) quad |= QUADRANT_TR;
if (m_Vertexes[curr.id].p.X <= npos.X && m_Vertexes[curr.id].p.Y >= npos.Y) quad |= QUADRANT_TL; if (m_Vertexes[curr.id].p.X <= npos.X && m_Vertexes[curr.id].p.Y >= npos.Y) quad |= QUADRANT_TL;
if (m_Vertexes[curr.id].p.X >= npos.X && m_Vertexes[curr.id].p.Y <= npos.Y) quad |= QUADRANT_BR; if (m_Vertexes[curr.id].p.X >= npos.X && m_Vertexes[curr.id].p.Y <= npos.Y) quad |= QUADRANT_BR;
// Check that the new vertex is in the right quadrant for the old vertex // Check that the new vertex is in the right quadrant for the old vertex
if (!(m_Vertexes[curr.id].quadOutward & quad)) if (!(m_Vertexes[curr.id].quadOutward & quad) && curr.id != START_VERTEX_ID)
{ {
// Hack: Always head towards the goal if possible, to avoid missing it if it's // Hack: Always head towards the goal if possible, to avoid missing it if it's
// inside another unit // inside another unit
if (n != GOAL_VERTEX_ID) if (n != GOAL_VERTEX_ID)
continue; continue;
} }
bool visible = bool visible =
Show All 14 Lines for (size_t n = 0; n < m_Vertexes.size(); ++n)
if (m_Vertexes[n].status == Vertex::UNEXPLORED) if (m_Vertexes[n].status == Vertex::UNEXPLORED)
{ {
// Add it to the open list: // Add it to the open list:
m_Vertexes[n].status = Vertex::OPEN; m_Vertexes[n].status = Vertex::OPEN;
m_Vertexes[n].g = g; m_Vertexes[n].g = g;
m_Vertexes[n].h = request.goal.DistanceToPoint(npos); m_Vertexes[n].h = request.goal.DistanceToPoint(npos);
m_Vertexes[n].pred = curr.id; m_Vertexes[n].pred = curr.id;
// If this is an axis-aligned shape, the path must continue in the same quadrant
// direction (but not go into the inside of the shape).
// Hack: If we started *inside* a shape then perhaps headed to its corner (e.g. the unit
// was very near another unit), don't restrict further pathing.
if (m_Vertexes[n].quadInward && !(curr.id == START_VERTEX_ID && g < fixed::FromInt(8)))
m_Vertexes[n].quadOutward = ((m_Vertexes[n].quadInward) & quad) & 0xF;
if (n == GOAL_VERTEX_ID) if (n == GOAL_VERTEX_ID)
m_Vertexes[n].p = npos; // remember the new best goal position m_Vertexes[n].p = npos; // remember the new best goal position
VertexPriorityQueue::Item t = { (u16)n, g + m_Vertexes[n].h, m_Vertexes[n].h }; VertexPriorityQueue::Item t = { (u16)n, g + m_Vertexes[n].h, m_Vertexes[n].h };
open.push(t); open.push(t);
// Remember the heuristically best vertex we've seen so far, in case we never actually reach the target // Remember the heuristically best vertex we've seen so far, in case we never actually reach the target
if (m_Vertexes[n].h < hBest) if (m_Vertexes[n].h < hBest)
Show All 9 Lines for (size_t n = 0; n < m_Vertexes.size(); ++n)
if (g >= m_Vertexes[n].g) if (g >= m_Vertexes[n].g)
continue; continue;
// Otherwise, we have a better path, so replace the old one with the new cost/parent // Otherwise, we have a better path, so replace the old one with the new cost/parent
fixed gprev = m_Vertexes[n].g; fixed gprev = m_Vertexes[n].g;
m_Vertexes[n].g = g; m_Vertexes[n].g = g;
m_Vertexes[n].pred = curr.id; m_Vertexes[n].pred = curr.id;
// If this is an axis-aligned shape, the path must continue in the same quadrant
// direction (but not go into the inside of the shape).
if (m_Vertexes[n].quadInward)
m_Vertexes[n].quadOutward = ((m_Vertexes[n].quadInward) & quad) & 0xF;
if (n == GOAL_VERTEX_ID) if (n == GOAL_VERTEX_ID)
m_Vertexes[n].p = npos; // remember the new best goal position m_Vertexes[n].p = npos; // remember the new best goal position
open.promote((u16)n, gprev + m_Vertexes[n].h, g + m_Vertexes[n].h, m_Vertexes[n].h); open.promote((u16)n, gprev + m_Vertexes[n].h, g + m_Vertexes[n].h, m_Vertexes[n].h);
} }
} }
} }
} }
▲ Show 20 Lines • Show All 157 Lines • Show Last 20 Lines
Wildfire Games · Phabricator