Index: ps/trunk/source/simulation2/components/CCmpPathfinder_Vertex.cpp
===================================================================
--- ps/trunk/source/simulation2/components/CCmpPathfinder_Vertex.cpp (revision 22252)
+++ ps/trunk/source/simulation2/components/CCmpPathfinder_Vertex.cpp (nonexistent)
@@ -1,931 +0,0 @@
-/* Copyright (C) 2017 Wildfire Games.
- * This file is part of 0 A.D.
- *
- * 0 A.D. is free software: you can redistribute it and/or modify
- * it under the terms of the GNU General Public License as published by
- * the Free Software Foundation, either version 2 of the License, or
- * (at your option) any later version.
- *
- * 0 A.D. is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with 0 A.D. If not, see .
- */
-
-/**
- * @file
- * Vertex-based algorithm for CCmpPathfinder.
- * Computes paths around the corners of rectangular obstructions.
- *
- * Useful search term for this algorithm: "points of visibility".
- *
- * Since we sometimes want to use this for avoiding moving units, there is no
- * pre-computation - the whole visibility graph is effectively regenerated for
- * each path, and it does A* over that graph.
- *
- * This scales very poorly in the number of obstructions, so it should be used
- * with a limited range and not exceedingly frequently.
- */
-
-#include "precompiled.h"
-
-#include "CCmpPathfinder_Common.h"
-
-#include "lib/timer.h"
-#include "ps/Profile.h"
-#include "simulation2/components/ICmpObstructionManager.h"
-#include "simulation2/helpers/PriorityQueue.h"
-#include "simulation2/helpers/Render.h"
-
-/* Quadrant optimisation:
- * (loosely based on GPG2 "Optimizing Points-of-Visibility Pathfinding")
- *
- * Consider the vertex ("@") at a corner of an axis-aligned rectangle ("#"):
- *
- * TL : TR
- * :
- * ####@ - - -
- * #####
- * #####
- * BL ## BR
- *
- * The area around the vertex is split into TopLeft, BottomRight etc quadrants.
- *
- * If the shortest path reaches this vertex, it cannot continue to a vertex in
- * the BL quadrant (it would be blocked by the shape).
- * Since the shortest path is wrapped tightly around the edges of obstacles,
- * if the path approached this vertex from the TL quadrant,
- * it cannot continue to the TL or TR quadrants (the path could be shorter if it
- * skipped this vertex).
- * Therefore it must continue to a vertex in the BR quadrant (so this vertex is in
- * *that* vertex's TL quadrant).
- *
- * That lets us significantly reduce the search space by quickly discarding vertexes
- * from the wrong quadrants.
- *
- * (This causes badness if the path starts from inside the shape, so we add some hacks
- * for that case.)
- *
- * (For non-axis-aligned rectangles it's harder to do this computation, so we'll
- * not bother doing any discarding for those.)
- */
-static const u8 QUADRANT_NONE = 0;
-static const u8 QUADRANT_BL = 1;
-static const u8 QUADRANT_TR = 2;
-static const u8 QUADRANT_TL = 4;
-static const u8 QUADRANT_BR = 8;
-static const u8 QUADRANT_BLTR = QUADRANT_BL|QUADRANT_TR;
-static const u8 QUADRANT_TLBR = QUADRANT_TL|QUADRANT_BR;
-static const u8 QUADRANT_ALL = QUADRANT_BLTR|QUADRANT_TLBR;
-
-// When computing vertexes to insert into the search graph,
-// add a small delta so that the vertexes of an edge don't get interpreted
-// as crossing the edge (given minor numerical inaccuracies)
-static const entity_pos_t EDGE_EXPAND_DELTA = entity_pos_t::FromInt(1)/16;
-
-/**
- * Check whether a ray from 'a' to 'b' crosses any of the edges.
- * (Edges are one-sided so it's only considered a cross if going from front to back.)
- */
-inline static bool CheckVisibility(const CFixedVector2D& a, const CFixedVector2D& b, const std::vector& edges)
-{
- CFixedVector2D abn = (b - a).Perpendicular();
-
- // Edges of general non-axis-aligned shapes
- for (size_t i = 0; i < edges.size(); ++i)
- {
- CFixedVector2D p0 = edges[i].p0;
- CFixedVector2D p1 = edges[i].p1;
-
- CFixedVector2D d = (p1 - p0).Perpendicular();
-
- // If 'a' is behind the edge, we can't cross
- fixed q = (a - p0).Dot(d);
- if (q < fixed::Zero())
- continue;
-
- // If 'b' is in front of the edge, we can't cross
- fixed r = (b - p0).Dot(d);
- if (r > fixed::Zero())
- continue;
-
- // The ray is crossing the infinitely-extended edge from in front to behind.
- // Check the finite edge is crossing the infinitely-extended ray too.
- // (Given the previous tests, it can only be crossing in one direction.)
- fixed s = (p0 - a).Dot(abn);
- if (s > fixed::Zero())
- continue;
-
- fixed t = (p1 - a).Dot(abn);
- if (t < fixed::Zero())
- continue;
-
- return false;
- }
-
- return true;
-}
-
-// Handle the axis-aligned shape edges separately (for performance):
-// (These are specialised versions of the general unaligned edge code.
-// They assume the caller has already excluded edges for which 'a' is
-// on the wrong side.)
-
-inline static bool CheckVisibilityLeft(const CFixedVector2D& a, const CFixedVector2D& b, const std::vector& edges)
-{
- if (a.X >= b.X)
- return true;
-
- CFixedVector2D abn = (b - a).Perpendicular();
-
- for (size_t i = 0; i < edges.size(); ++i)
- {
- if (b.X < edges[i].p0.X)
- continue;
-
- CFixedVector2D p0 (edges[i].p0.X, edges[i].c1);
- fixed s = (p0 - a).Dot(abn);
- if (s > fixed::Zero())
- continue;
-
- CFixedVector2D p1 (edges[i].p0.X, edges[i].p0.Y);
- fixed t = (p1 - a).Dot(abn);
- if (t < fixed::Zero())
- continue;
-
- return false;
- }
-
- return true;
-}
-
-inline static bool CheckVisibilityRight(const CFixedVector2D& a, const CFixedVector2D& b, const std::vector& edges)
-{
- if (a.X <= b.X)
- return true;
-
- CFixedVector2D abn = (b - a).Perpendicular();
-
- for (size_t i = 0; i < edges.size(); ++i)
- {
- if (b.X > edges[i].p0.X)
- continue;
-
- CFixedVector2D p0 (edges[i].p0.X, edges[i].c1);
- fixed s = (p0 - a).Dot(abn);
- if (s > fixed::Zero())
- continue;
-
- CFixedVector2D p1 (edges[i].p0.X, edges[i].p0.Y);
- fixed t = (p1 - a).Dot(abn);
- if (t < fixed::Zero())
- continue;
-
- return false;
- }
-
- return true;
-}
-
-inline static bool CheckVisibilityBottom(const CFixedVector2D& a, const CFixedVector2D& b, const std::vector& edges)
-{
- if (a.Y >= b.Y)
- return true;
-
- CFixedVector2D abn = (b - a).Perpendicular();
-
- for (size_t i = 0; i < edges.size(); ++i)
- {
- if (b.Y < edges[i].p0.Y)
- continue;
-
- CFixedVector2D p0 (edges[i].p0.X, edges[i].p0.Y);
- fixed s = (p0 - a).Dot(abn);
- if (s > fixed::Zero())
- continue;
-
- CFixedVector2D p1 (edges[i].c1, edges[i].p0.Y);
- fixed t = (p1 - a).Dot(abn);
- if (t < fixed::Zero())
- continue;
-
- return false;
- }
-
- return true;
-}
-
-inline static bool CheckVisibilityTop(const CFixedVector2D& a, const CFixedVector2D& b, const std::vector& edges)
-{
- if (a.Y <= b.Y)
- return true;
-
- CFixedVector2D abn = (b - a).Perpendicular();
-
- for (size_t i = 0; i < edges.size(); ++i)
- {
- if (b.Y > edges[i].p0.Y)
- continue;
-
- CFixedVector2D p0 (edges[i].p0.X, edges[i].p0.Y);
- fixed s = (p0 - a).Dot(abn);
- if (s > fixed::Zero())
- continue;
-
- CFixedVector2D p1 (edges[i].c1, edges[i].p0.Y);
- fixed t = (p1 - a).Dot(abn);
- if (t < fixed::Zero())
- continue;
-
- return false;
- }
-
- return true;
-}
-
-typedef PriorityQueueHeap VertexPriorityQueue;
-
-/**
- * Add edges and vertexes to represent the boundaries between passable and impassable
- * navcells (for impassable terrain).
- * Navcells i0 <= i <= i1, j0 <= j <= j1 will be considered.
- */
-static void AddTerrainEdges(std::vector& edges, std::vector& vertexes,
- int i0, int j0, int i1, int j1,
- pass_class_t passClass, const Grid& grid)
-{
- PROFILE("AddTerrainEdges");
-
- // Clamp the coordinates so we won't attempt to sample outside of the grid.
- // (This assumes the outermost ring of navcells (which are always impassable)
- // won't have a boundary with any passable navcells. TODO: is that definitely
- // safe enough?)
-
- i0 = clamp(i0, 1, grid.m_W-2);
- j0 = clamp(j0, 1, grid.m_H-2);
- i1 = clamp(i1, 1, grid.m_W-2);
- j1 = clamp(j1, 1, grid.m_H-2);
-
- for (int j = j0; j <= j1; ++j)
- {
- for (int i = i0; i <= i1; ++i)
- {
- if (IS_PASSABLE(grid.get(i, j), passClass))
- continue;
-
- if (IS_PASSABLE(grid.get(i+1, j), passClass) && IS_PASSABLE(grid.get(i, j+1), passClass) && IS_PASSABLE(grid.get(i+1, j+1), passClass))
- {
- Vertex vert;
- vert.status = Vertex::UNEXPLORED;
- vert.quadOutward = QUADRANT_ALL;
- vert.quadInward = QUADRANT_BL;
- vert.p = CFixedVector2D(fixed::FromInt(i+1)+EDGE_EXPAND_DELTA, fixed::FromInt(j+1)+EDGE_EXPAND_DELTA).Multiply(Pathfinding::NAVCELL_SIZE);
- vertexes.push_back(vert);
- }
-
- if (IS_PASSABLE(grid.get(i-1, j), passClass) && IS_PASSABLE(grid.get(i, j+1), passClass) && IS_PASSABLE(grid.get(i-1, j+1), passClass))
- {
- Vertex vert;
- vert.status = Vertex::UNEXPLORED;
- vert.quadOutward = QUADRANT_ALL;
- vert.quadInward = QUADRANT_BR;
- vert.p = CFixedVector2D(fixed::FromInt(i)-EDGE_EXPAND_DELTA, fixed::FromInt(j+1)+EDGE_EXPAND_DELTA).Multiply(Pathfinding::NAVCELL_SIZE);
- vertexes.push_back(vert);
- }
-
- if (IS_PASSABLE(grid.get(i+1, j), passClass) && IS_PASSABLE(grid.get(i, j-1), passClass) && IS_PASSABLE(grid.get(i+1, j-1), passClass))
- {
- Vertex vert;
- vert.status = Vertex::UNEXPLORED;
- vert.quadOutward = QUADRANT_ALL;
- vert.quadInward = QUADRANT_TL;
- vert.p = CFixedVector2D(fixed::FromInt(i+1)+EDGE_EXPAND_DELTA, fixed::FromInt(j)-EDGE_EXPAND_DELTA).Multiply(Pathfinding::NAVCELL_SIZE);
- vertexes.push_back(vert);
- }
-
- if (IS_PASSABLE(grid.get(i-1, j), passClass) && IS_PASSABLE(grid.get(i, j-1), passClass) && IS_PASSABLE(grid.get(i-1, j-1), passClass))
- {
- Vertex vert;
- vert.status = Vertex::UNEXPLORED;
- vert.quadOutward = QUADRANT_ALL;
- vert.quadInward = QUADRANT_TR;
- vert.p = CFixedVector2D(fixed::FromInt(i)-EDGE_EXPAND_DELTA, fixed::FromInt(j)-EDGE_EXPAND_DELTA).Multiply(Pathfinding::NAVCELL_SIZE);
- vertexes.push_back(vert);
- }
- }
- }
-
- // XXX rewrite this stuff
- std::vector segmentsR;
- std::vector segmentsL;
- for (int j = j0; j < j1; ++j)
- {
- segmentsR.clear();
- segmentsL.clear();
- for (int i = i0; i <= i1; ++i)
- {
- bool a = IS_PASSABLE(grid.get(i, j+1), passClass);
- bool b = IS_PASSABLE(grid.get(i, j), passClass);
- if (a && !b)
- segmentsL.push_back(i);
- if (b && !a)
- segmentsR.push_back(i);
- }
-
- if (!segmentsR.empty())
- {
- segmentsR.push_back(0); // sentinel value to simplify the loop
- u16 ia = segmentsR[0];
- u16 ib = ia + 1;
- for (size_t n = 1; n < segmentsR.size(); ++n)
- {
- if (segmentsR[n] == ib)
- ++ib;
- else
- {
- CFixedVector2D v0 = CFixedVector2D(fixed::FromInt(ia), fixed::FromInt(j+1)).Multiply(Pathfinding::NAVCELL_SIZE);
- CFixedVector2D v1 = CFixedVector2D(fixed::FromInt(ib), fixed::FromInt(j+1)).Multiply(Pathfinding::NAVCELL_SIZE);
- edges.emplace_back(Edge{ v0, v1 });
-
- ia = segmentsR[n];
- ib = ia + 1;
- }
- }
- }
-
- if (!segmentsL.empty())
- {
- segmentsL.push_back(0); // sentinel value to simplify the loop
- u16 ia = segmentsL[0];
- u16 ib = ia + 1;
- for (size_t n = 1; n < segmentsL.size(); ++n)
- {
- if (segmentsL[n] == ib)
- ++ib;
- else
- {
- CFixedVector2D v0 = CFixedVector2D(fixed::FromInt(ib), fixed::FromInt(j+1)).Multiply(Pathfinding::NAVCELL_SIZE);
- CFixedVector2D v1 = CFixedVector2D(fixed::FromInt(ia), fixed::FromInt(j+1)).Multiply(Pathfinding::NAVCELL_SIZE);
- edges.emplace_back(Edge{ v0, v1 });
-
- ia = segmentsL[n];
- ib = ia + 1;
- }
- }
- }
- }
- std::vector segmentsU;
- std::vector segmentsD;
- for (int i = i0; i < i1; ++i)
- {
- segmentsU.clear();
- segmentsD.clear();
- for (int j = j0; j <= j1; ++j)
- {
- bool a = IS_PASSABLE(grid.get(i+1, j), passClass);
- bool b = IS_PASSABLE(grid.get(i, j), passClass);
- if (a && !b)
- segmentsU.push_back(j);
- if (b && !a)
- segmentsD.push_back(j);
- }
-
- if (!segmentsU.empty())
- {
- segmentsU.push_back(0); // sentinel value to simplify the loop
- u16 ja = segmentsU[0];
- u16 jb = ja + 1;
- for (size_t n = 1; n < segmentsU.size(); ++n)
- {
- if (segmentsU[n] == jb)
- ++jb;
- else
- {
- CFixedVector2D v0 = CFixedVector2D(fixed::FromInt(i+1), fixed::FromInt(ja)).Multiply(Pathfinding::NAVCELL_SIZE);
- CFixedVector2D v1 = CFixedVector2D(fixed::FromInt(i+1), fixed::FromInt(jb)).Multiply(Pathfinding::NAVCELL_SIZE);
- edges.emplace_back(Edge{ v0, v1 });
-
- ja = segmentsU[n];
- jb = ja + 1;
- }
- }
- }
-
- if (!segmentsD.empty())
- {
- segmentsD.push_back(0); // sentinel value to simplify the loop
- u16 ja = segmentsD[0];
- u16 jb = ja + 1;
- for (size_t n = 1; n < segmentsD.size(); ++n)
- {
- if (segmentsD[n] == jb)
- ++jb;
- else
- {
- CFixedVector2D v0 = CFixedVector2D(fixed::FromInt(i+1), fixed::FromInt(jb)).Multiply(Pathfinding::NAVCELL_SIZE);
- CFixedVector2D v1 = CFixedVector2D(fixed::FromInt(i+1), fixed::FromInt(ja)).Multiply(Pathfinding::NAVCELL_SIZE);
- edges.emplace_back(Edge{ v0, v1 });
-
- ja = segmentsD[n];
- jb = ja + 1;
- }
- }
- }
- }
-}
-
-static void SplitAAEdges(const CFixedVector2D& a,
- const std::vector& edges,
- const std::vector& squares,
- std::vector& edgesUnaligned,
- std::vector& edgesLeft, std::vector& edgesRight,
- std::vector& edgesBottom, std::vector& edgesTop)
-{
-
- for (const Square& square : squares)
- {
- if (a.X <= square.p0.X)
- edgesLeft.emplace_back(EdgeAA{ square.p0, square.p1.Y });
- if (a.X >= square.p1.X)
- edgesRight.emplace_back(EdgeAA{ square.p1, square.p0.Y });
- if (a.Y <= square.p0.Y)
- edgesBottom.emplace_back(EdgeAA{ square.p0, square.p1.X });
- if (a.Y >= square.p1.Y)
- edgesTop.emplace_back(EdgeAA{ square.p1, square.p0.X });
- }
-
- for (const Edge& edge : edges)
- {
- if (edge.p0.X == edge.p1.X)
- {
- if (edge.p1.Y < edge.p0.Y)
- {
- if (!(a.X <= edge.p0.X))
- continue;
- edgesLeft.emplace_back(EdgeAA{ edge.p1, edge.p0.Y });
- }
- else
- {
- if (!(a.X >= edge.p0.X))
- continue;
- edgesRight.emplace_back(EdgeAA{ edge.p1, edge.p0.Y });
- }
- }
- else if (edge.p0.Y == edge.p1.Y)
- {
- if (edge.p0.X < edge.p1.X)
- {
- if (!(a.Y <= edge.p0.Y))
- continue;
- edgesBottom.emplace_back(EdgeAA{ edge.p0, edge.p1.X });
- }
- else
- {
- if (!(a.Y >= edge.p0.Y))
- continue;
- edgesTop.emplace_back(EdgeAA{ edge.p0, edge.p1.X });
- }
- }
- else
- edgesUnaligned.push_back(edge);
- }
-}
-
-/**
- * Functor for sorting edge-squares by approximate proximity to a fixed point.
- */
-struct SquareSort
-{
- CFixedVector2D src;
- SquareSort(CFixedVector2D src) : src(src) { }
- bool operator()(const Square& a, const Square& b) const
- {
- if ((a.p0 - src).CompareLength(b.p0 - src) < 0)
- return true;
- return false;
- }
-};
-
-void CCmpPathfinder::ComputeShortPath(const IObstructionTestFilter& filter,
- entity_pos_t x0, entity_pos_t z0, entity_pos_t clearance,
- entity_pos_t range, const PathGoal& goal, pass_class_t passClass, WaypointPath& path)
-{
- PROFILE("ComputeShortPath");
- m_DebugOverlayShortPathLines.clear();
-
- if (m_DebugOverlay)
- {
- // Render the goal shape
- m_DebugOverlayShortPathLines.push_back(SOverlayLine());
- m_DebugOverlayShortPathLines.back().m_Color = CColor(1, 0, 0, 1);
- switch (goal.type)
- {
- case PathGoal::POINT:
- {
- SimRender::ConstructCircleOnGround(GetSimContext(), goal.x.ToFloat(), goal.z.ToFloat(), 0.2f, m_DebugOverlayShortPathLines.back(), true);
- break;
- }
- case PathGoal::CIRCLE:
- case PathGoal::INVERTED_CIRCLE:
- {
- SimRender::ConstructCircleOnGround(GetSimContext(), goal.x.ToFloat(), goal.z.ToFloat(), goal.hw.ToFloat(), m_DebugOverlayShortPathLines.back(), true);
- break;
- }
- case PathGoal::SQUARE:
- case PathGoal::INVERTED_SQUARE:
- {
- float a = atan2f(goal.v.X.ToFloat(), goal.v.Y.ToFloat());
- SimRender::ConstructSquareOnGround(GetSimContext(), goal.x.ToFloat(), goal.z.ToFloat(), goal.hw.ToFloat()*2, goal.hh.ToFloat()*2, a, m_DebugOverlayShortPathLines.back(), true);
- break;
- }
- }
- }
-
- // List of collision edges - paths must never cross these.
- // (Edges are one-sided so intersections are fine in one direction, but not the other direction.)
- edges.clear();
- edgeSquares.clear(); // axis-aligned squares; equivalent to 4 edges
-
- // Create impassable edges at the max-range boundary, so we can't escape the region
- // where we're meant to be searching
- fixed rangeXMin = x0 - range;
- fixed rangeXMax = x0 + range;
- fixed rangeZMin = z0 - range;
- fixed rangeZMax = z0 + range;
-
- // we don't actually add the "search space" edges as edges, since we may want to cross them
- // in some cases (such as if we need to go around an obstruction that's partly out of the search range)
-
- // List of obstruction vertexes (plus start/end points); we'll try to find paths through
- // the graph defined by these vertexes
- vertexes.clear();
-
- // Add the start point to the graph
- CFixedVector2D posStart(x0, z0);
- fixed hStart = (posStart - goal.NearestPointOnGoal(posStart)).Length();
- Vertex start = { posStart, fixed::Zero(), hStart, 0, Vertex::OPEN, QUADRANT_NONE, QUADRANT_ALL };
- vertexes.push_back(start);
- const size_t START_VERTEX_ID = 0;
-
- // Add the goal vertex to the graph.
- // Since the goal isn't always a point, this a special magic virtual vertex which moves around - whenever
- // we look at it from another vertex, it is moved to be the closest point on the goal shape to that vertex.
- Vertex end = { CFixedVector2D(goal.x, goal.z), fixed::Zero(), fixed::Zero(), 0, Vertex::UNEXPLORED, QUADRANT_NONE, QUADRANT_ALL };
- vertexes.push_back(end);
- const size_t GOAL_VERTEX_ID = 1;
-
- // Find all the obstruction squares that might affect us
- CmpPtr cmpObstructionManager(GetSystemEntity());
- std::vector squares;
- size_t staticShapesNb = 0;
- cmpObstructionManager->GetStaticObstructionsInRange(filter, rangeXMin - clearance, rangeZMin - clearance, rangeXMax + clearance, rangeZMax + clearance, squares);
- staticShapesNb = squares.size();
- cmpObstructionManager->GetUnitObstructionsInRange(filter, rangeXMin - clearance, rangeZMin - clearance, rangeXMax + clearance, rangeZMax + clearance, squares);
-
- // Change array capacities to reduce reallocations
- vertexes.reserve(vertexes.size() + squares.size()*4);
- edgeSquares.reserve(edgeSquares.size() + squares.size()); // (assume most squares are AA)
-
- entity_pos_t pathfindClearance = clearance;
-
- // Convert each obstruction square into collision edges and search graph vertexes
- for (size_t i = 0; i < squares.size(); ++i)
- {
- CFixedVector2D center(squares[i].x, squares[i].z);
- CFixedVector2D u = squares[i].u;
- CFixedVector2D v = squares[i].v;
-
- if (i >= staticShapesNb)
- pathfindClearance = clearance - entity_pos_t::FromInt(1)/2;
-
- // Expand the vertexes by the moving unit's collision radius, to find the
- // closest we can get to it
-
- CFixedVector2D hd0(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
- bool aa = (u.X == fixed::FromInt(1) && u.Y == fixed::Zero() && v.X == fixed::Zero() && v.Y == fixed::FromInt(1));
-
- Vertex vert;
- vert.status = Vertex::UNEXPLORED;
- vert.quadInward = QUADRANT_NONE;
- vert.quadOutward = QUADRANT_ALL;
- vert.p.X = center.X - hd0.Dot(u); vert.p.Y = center.Y + hd0.Dot(v); if (aa) vert.quadInward = QUADRANT_BR; vertexes.push_back(vert);
- if (vert.p.X < rangeXMin) rangeXMin = vert.p.X;
- if (vert.p.Y < rangeZMin) rangeZMin = vert.p.Y;
- if (vert.p.X > rangeXMax) rangeXMax = vert.p.X;
- if (vert.p.Y > rangeZMax) rangeZMax = vert.p.Y;
- vert.p.X = center.X - hd1.Dot(u); vert.p.Y = center.Y + hd1.Dot(v); if (aa) vert.quadInward = QUADRANT_TR; vertexes.push_back(vert);
- if (vert.p.X < rangeXMin) rangeXMin = vert.p.X;
- if (vert.p.Y < rangeZMin) rangeZMin = vert.p.Y;
- if (vert.p.X > rangeXMax) rangeXMax = vert.p.X;
- if (vert.p.Y > rangeZMax) rangeZMax = vert.p.Y;
- vert.p.X = center.X + hd0.Dot(u); vert.p.Y = center.Y - hd0.Dot(v); if (aa) vert.quadInward = QUADRANT_TL; vertexes.push_back(vert);
- if (vert.p.X < rangeXMin) rangeXMin = vert.p.X;
- if (vert.p.Y < rangeZMin) rangeZMin = vert.p.Y;
- if (vert.p.X > rangeXMax) rangeXMax = vert.p.X;
- if (vert.p.Y > rangeZMax) rangeZMax = vert.p.Y;
- vert.p.X = center.X + hd1.Dot(u); vert.p.Y = center.Y - hd1.Dot(v); if (aa) vert.quadInward = QUADRANT_BL; vertexes.push_back(vert);
- if (vert.p.X < rangeXMin) rangeXMin = vert.p.X;
- if (vert.p.Y < rangeZMin) rangeZMin = vert.p.Y;
- if (vert.p.X > rangeXMax) rangeXMax = vert.p.X;
- if (vert.p.Y > rangeZMax) rangeZMax = vert.p.Y;
-
- // Add the edges:
-
- CFixedVector2D h0(squares[i].hw + pathfindClearance, squares[i].hh + pathfindClearance);
- CFixedVector2D h1(squares[i].hw + pathfindClearance, -(squares[i].hh + pathfindClearance));
-
- CFixedVector2D ev0(center.X - h0.Dot(u), center.Y + h0.Dot(v));
- CFixedVector2D ev1(center.X - h1.Dot(u), center.Y + h1.Dot(v));
- CFixedVector2D ev2(center.X + h0.Dot(u), center.Y - h0.Dot(v));
- CFixedVector2D ev3(center.X + h1.Dot(u), center.Y - h1.Dot(v));
- if (aa)
- edgeSquares.emplace_back(Square{ ev1, ev3 });
- else
- {
- edges.emplace_back(Edge{ ev0, ev1 });
- edges.emplace_back(Edge{ ev1, ev2 });
- edges.emplace_back(Edge{ ev2, ev3 });
- edges.emplace_back(Edge{ ev3, ev0 });
- }
-
- // TODO: should clip out vertexes and edges that are outside the range,
- // to reduce the search space
- }
-
- // Add terrain obstructions
- {
- 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(rangeXMax, rangeZMax, i1, j1, m_MapSize*Pathfinding::NAVCELLS_PER_TILE, m_MapSize*Pathfinding::NAVCELLS_PER_TILE);
- AddTerrainEdges(edges, vertexes, i0, j0, i1, j1, passClass, *m_TerrainOnlyGrid);
- }
-
- // Clip out vertices that are inside an edgeSquare (i.e. trivially unreachable)
- for (size_t i = 0; i < edgeSquares.size(); ++i)
- {
- // If the start point is inside the square, ignore it
- if (start.p.X >= edgeSquares[i].p0.X &&
- start.p.Y >= edgeSquares[i].p0.Y &&
- start.p.X <= edgeSquares[i].p1.X &&
- start.p.Y <= edgeSquares[i].p1.Y)
- continue;
-
- // Remove every non-start/goal vertex that is inside an edgeSquare;
- // since remove() would be inefficient, just mark it as closed instead.
- for (size_t j = 2; j < vertexes.size(); ++j)
- if (vertexes[j].p.X >= edgeSquares[i].p0.X &&
- vertexes[j].p.Y >= edgeSquares[i].p0.Y &&
- vertexes[j].p.X <= edgeSquares[i].p1.X &&
- vertexes[j].p.Y <= edgeSquares[i].p1.Y)
- vertexes[j].status = Vertex::CLOSED;
- }
-
- ENSURE(vertexes.size() < 65536); // we store array indexes as u16
-
- // Render the debug overlay
- if (m_DebugOverlay)
- {
-#define PUSH_POINT(p) STMT(xz.push_back(p.X.ToFloat()); xz.push_back(p.Y.ToFloat()))
- // Render the vertexes as little Pac-Man shapes to indicate quadrant direction
- for (size_t i = 0; i < vertexes.size(); ++i)
- {
- m_DebugOverlayShortPathLines.emplace_back();
- m_DebugOverlayShortPathLines.back().m_Color = CColor(1, 1, 0, 1);
-
- float x = vertexes[i].p.X.ToFloat();
- float z = vertexes[i].p.Y.ToFloat();
-
- float a0 = 0, a1 = 0;
- // Get arc start/end angles depending on quadrant (if any)
- if (vertexes[i].quadInward == QUADRANT_BL) { a0 = -0.25f; a1 = 0.50f; }
- else if (vertexes[i].quadInward == QUADRANT_TR) { a0 = 0.25f; a1 = 1.00f; }
- else if (vertexes[i].quadInward == QUADRANT_TL) { a0 = -0.50f; a1 = 0.25f; }
- else if (vertexes[i].quadInward == QUADRANT_BR) { a0 = 0.00f; a1 = 0.75f; }
-
- if (a0 == a1)
- SimRender::ConstructCircleOnGround(GetSimContext(), x, z, 0.5f,
- m_DebugOverlayShortPathLines.back(), true);
- else
- SimRender::ConstructClosedArcOnGround(GetSimContext(), x, z, 0.5f,
- a0 * ((float)M_PI*2.0f), a1 * ((float)M_PI*2.0f),
- m_DebugOverlayShortPathLines.back(), true);
- }
-
- // Render the edges
- for (size_t i = 0; i < edges.size(); ++i)
- {
- m_DebugOverlayShortPathLines.emplace_back();
- m_DebugOverlayShortPathLines.back().m_Color = CColor(0, 1, 1, 1);
- std::vector xz;
- PUSH_POINT(edges[i].p0);
- PUSH_POINT(edges[i].p1);
-
- // Add an arrowhead to indicate the direction
- CFixedVector2D d = edges[i].p1 - edges[i].p0;
- d.Normalize(fixed::FromInt(1)/8);
- CFixedVector2D p2 = edges[i].p1 - d*2;
- CFixedVector2D p3 = p2 + d.Perpendicular();
- CFixedVector2D p4 = p2 - d.Perpendicular();
- PUSH_POINT(p3);
- PUSH_POINT(p4);
- PUSH_POINT(edges[i].p1);
-
- SimRender::ConstructLineOnGround(GetSimContext(), xz, m_DebugOverlayShortPathLines.back(), true);
- }
-#undef PUSH_POINT
-
- // Render the axis-aligned squares
- for (size_t i = 0; i < edgeSquares.size(); ++i)
- {
- m_DebugOverlayShortPathLines.push_back(SOverlayLine());
- m_DebugOverlayShortPathLines.back().m_Color = CColor(0, 1, 1, 1);
- std::vector xz;
- Square s = edgeSquares[i];
- xz.push_back(s.p0.X.ToFloat());
- xz.push_back(s.p0.Y.ToFloat());
- xz.push_back(s.p0.X.ToFloat());
- xz.push_back(s.p1.Y.ToFloat());
- xz.push_back(s.p1.X.ToFloat());
- xz.push_back(s.p1.Y.ToFloat());
- xz.push_back(s.p1.X.ToFloat());
- xz.push_back(s.p0.Y.ToFloat());
- xz.push_back(s.p0.X.ToFloat());
- xz.push_back(s.p0.Y.ToFloat());
- SimRender::ConstructLineOnGround(GetSimContext(), xz, m_DebugOverlayShortPathLines.back(), true);
- }
- }
-
- // Do an A* search over the vertex/visibility graph:
-
- // Since we are just measuring Euclidean distance the heuristic is admissible,
- // so we never have to re-examine a node once it's been moved to the closed set.
-
- // To save time in common cases, we don't precompute a graph of valid edges between vertexes;
- // we do it lazily instead. When the search algorithm reaches a vertex, we examine every other
- // vertex and see if we can reach it without hitting any collision edges, and ignore the ones
- // we can't reach. Since the algorithm can only reach a vertex once (and then it'll be marked
- // as closed), we won't be doing any redundant visibility computations.
-
- PROFILE_START("Short pathfinding - A*");
-
- VertexPriorityQueue open;
- VertexPriorityQueue::Item qiStart = { START_VERTEX_ID, start.h, start.h };
- open.push(qiStart);
-
- u16 idBest = START_VERTEX_ID;
- fixed hBest = start.h;
-
- while (!open.empty())
- {
- // Move best tile from open to closed
- VertexPriorityQueue::Item curr = open.pop();
- vertexes[curr.id].status = Vertex::CLOSED;
-
- // If we've reached the destination, stop
- if (curr.id == GOAL_VERTEX_ID)
- {
- idBest = curr.id;
- break;
- }
-
- // Sort the edges by distance in order to check those first that have a high probability of blocking a ray.
- // The heuristic based on distance is very rough, especially for squares that are further away;
- // we're also only really interested in the closest squares since they are the only ones that block a lot of rays.
- // Thus we only do a partial sort; the threshold is just a somewhat reasonable value.
- if (edgeSquares.size() > 8)
- std::partial_sort(edgeSquares.begin(), edgeSquares.begin() + 8, edgeSquares.end(), SquareSort(vertexes[curr.id].p));
-
- edgesUnaligned.clear();
- edgesLeft.clear();
- edgesRight.clear();
- edgesBottom.clear();
- edgesTop.clear();
- SplitAAEdges(vertexes[curr.id].p, edges, edgeSquares, edgesUnaligned, edgesLeft, edgesRight, edgesBottom, edgesTop);
-
- // Check the lines to every other vertex
- for (size_t n = 0; n < vertexes.size(); ++n)
- {
- if (vertexes[n].status == Vertex::CLOSED)
- continue;
-
- // If this is the magical goal vertex, move it to near the current vertex
- CFixedVector2D npos;
- if (n == GOAL_VERTEX_ID)
- {
- npos = goal.NearestPointOnGoal(vertexes[curr.id].p);
-
- // 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
- // sometimes it happens), so clamp it to the current search range
- npos.X = clamp(npos.X, rangeXMin, rangeXMax);
- npos.Y = clamp(npos.Y, rangeZMin, rangeZMax);
- }
- else
- npos = vertexes[n].p;
-
- // Work out which quadrant(s) we're approaching the new vertex from
- u8 quad = 0;
- if (vertexes[curr.id].p.X <= npos.X && vertexes[curr.id].p.Y <= npos.Y) quad |= QUADRANT_BL;
- if (vertexes[curr.id].p.X >= npos.X && vertexes[curr.id].p.Y >= npos.Y) quad |= QUADRANT_TR;
- if (vertexes[curr.id].p.X <= npos.X && vertexes[curr.id].p.Y >= npos.Y) quad |= QUADRANT_TL;
- if (vertexes[curr.id].p.X >= npos.X && vertexes[curr.id].p.Y <= npos.Y) quad |= QUADRANT_BR;
-
- // Check that the new vertex is in the right quadrant for the old vertex
- if (!(vertexes[curr.id].quadOutward & quad))
- {
- // Hack: Always head towards the goal if possible, to avoid missing it if it's
- // inside another unit
- if (n != GOAL_VERTEX_ID)
- continue;
- }
-
- bool visible =
- CheckVisibilityLeft(vertexes[curr.id].p, npos, edgesLeft) &&
- CheckVisibilityRight(vertexes[curr.id].p, npos, edgesRight) &&
- CheckVisibilityBottom(vertexes[curr.id].p, npos, edgesBottom) &&
- CheckVisibilityTop(vertexes[curr.id].p, npos, edgesTop) &&
- CheckVisibility(vertexes[curr.id].p, npos, edgesUnaligned);
-
- /*
- // Render the edges that we examine
- m_DebugOverlayShortPathLines.push_back(SOverlayLine());
- m_DebugOverlayShortPathLines.back().m_Color = visible ? CColor(0, 1, 0, 0.5) : CColor(1, 0, 0, 0.5);
- std::vector xz;
- xz.push_back(vertexes[curr.id].p.X.ToFloat());
- xz.push_back(vertexes[curr.id].p.Y.ToFloat());
- xz.push_back(npos.X.ToFloat());
- xz.push_back(npos.Y.ToFloat());
- SimRender::ConstructLineOnGround(GetSimContext(), xz, m_DebugOverlayShortPathLines.back(), false);
- */
-
- if (visible)
- {
- fixed g = vertexes[curr.id].g + (vertexes[curr.id].p - npos).Length();
-
- // If this is a new tile, compute the heuristic distance
- if (vertexes[n].status == Vertex::UNEXPLORED)
- {
- // Add it to the open list:
- vertexes[n].status = Vertex::OPEN;
- vertexes[n].g = g;
- vertexes[n].h = goal.DistanceToPoint(npos);
- 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 (vertexes[n].quadInward && !(curr.id == START_VERTEX_ID && g < fixed::FromInt(8)))
- vertexes[n].quadOutward = ((~vertexes[n].quadInward) & quad) & 0xF;
-
- if (n == GOAL_VERTEX_ID)
- vertexes[n].p = npos; // remember the new best goal position
-
- VertexPriorityQueue::Item t = { (u16)n, g + vertexes[n].h, vertexes[n].h };
- open.push(t);
-
- // Remember the heuristically best vertex we've seen so far, in case we never actually reach the target
- if (vertexes[n].h < hBest)
- {
- idBest = (u16)n;
- hBest = vertexes[n].h;
- }
- }
- else // must be OPEN
- {
- // If we've already seen this tile, and the new path to this tile does not have a
- // better cost, then stop now
- if (g >= vertexes[n].g)
- continue;
-
- // Otherwise, we have a better path, so replace the old one with the new cost/parent
- fixed gprev = vertexes[n].g;
- vertexes[n].g = g;
- 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 (vertexes[n].quadInward)
- vertexes[n].quadOutward = ((~vertexes[n].quadInward) & quad) & 0xF;
-
- if (n == GOAL_VERTEX_ID)
- vertexes[n].p = npos; // remember the new best goal position
-
- open.promote((u16)n, gprev + vertexes[n].h, g + vertexes[n].h, vertexes[n].h);
- }
- }
- }
- }
-
- // Reconstruct the path (in reverse)
- for (u16 id = idBest; id != START_VERTEX_ID; id = vertexes[id].pred)
- path.m_Waypoints.emplace_back(Waypoint{ vertexes[id].p.X, vertexes[id].p.Y });
-
- PROFILE_END("Short pathfinding - A*");
-}
Property changes on: ps/trunk/source/simulation2/components/CCmpPathfinder_Vertex.cpp
___________________________________________________________________
Deleted: svn:eol-style
## -1 +0,0 ##
-native
\ No newline at end of property
Index: ps/trunk/source/simulation2/components/CCmpPathfinder.cpp
===================================================================
--- ps/trunk/source/simulation2/components/CCmpPathfinder.cpp (revision 22252)
+++ ps/trunk/source/simulation2/components/CCmpPathfinder.cpp (revision 22253)
@@ -1,890 +1,916 @@
-/* Copyright (C) 2018 Wildfire Games.
+/* Copyright (C) 2019 Wildfire Games.
* This file is part of 0 A.D.
*
* 0 A.D. is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 2 of the License, or
* (at your option) any later version.
*
* 0 A.D. is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with 0 A.D. If not, see .
*/
/**
* @file
* Common code and setup code for CCmpPathfinder.
*/
#include "precompiled.h"
#include "CCmpPathfinder_Common.h"
#include "ps/CLogger.h"
#include "ps/CStr.h"
#include "ps/Profile.h"
#include "ps/XML/Xeromyces.h"
#include "renderer/Scene.h"
#include "simulation2/MessageTypes.h"
#include "simulation2/components/ICmpObstruction.h"
#include "simulation2/components/ICmpObstructionManager.h"
#include "simulation2/components/ICmpTerrain.h"
#include "simulation2/components/ICmpWaterManager.h"
#include "simulation2/helpers/Rasterize.h"
+#include "simulation2/helpers/VertexPathfinder.h"
#include "simulation2/serialization/SerializeTemplates.h"
REGISTER_COMPONENT_TYPE(Pathfinder)
void CCmpPathfinder::Init(const CParamNode& UNUSED(paramNode))
{
m_MapSize = 0;
m_Grid = NULL;
m_TerrainOnlyGrid = NULL;
FlushAIPathfinderDirtinessInformation();
m_NextAsyncTicket = 1;
- m_DebugOverlay = false;
m_AtlasOverlay = NULL;
m_SameTurnMovesCount = 0;
+ m_VertexPathfinder = std::unique_ptr(new VertexPathfinder(m_MapSize, m_TerrainOnlyGrid));
+
// Register Relax NG validator
CXeromyces::AddValidator(g_VFS, "pathfinder", "simulation/data/pathfinder.rng");
// Since this is used as a system component (not loaded from an entity template),
// we can't use the real paramNode (it won't get handled properly when deserializing),
// so load the data from a special XML file.
CParamNode externalParamNode;
CParamNode::LoadXML(externalParamNode, L"simulation/data/pathfinder.xml", "pathfinder");
// Previously all move commands during a turn were
// queued up and processed asynchronously at the start
// of the next turn. Now we are processing queued up
// events several times duing the turn. This improves
// responsiveness and units move more smoothly especially.
// when in formation. There is still a call at the
// beginning of a turn to process all outstanding moves -
// this will handle any moves above the MaxSameTurnMoves
// threshold.
//
// TODO - The moves processed at the beginning of the
// turn do not count against the maximum moves per turn
// currently. The thinking is that this will eventually
// happen in another thread. Either way this probably
// will require some adjustment and rethinking.
const CParamNode pathingSettings = externalParamNode.GetChild("Pathfinder");
m_MaxSameTurnMoves = (u16)pathingSettings.GetChild("MaxSameTurnMoves").ToInt();
const CParamNode::ChildrenMap& passClasses = externalParamNode.GetChild("Pathfinder").GetChild("PassabilityClasses").GetChildren();
for (CParamNode::ChildrenMap::const_iterator it = passClasses.begin(); it != passClasses.end(); ++it)
{
std::string name = it->first;
ENSURE((int)m_PassClasses.size() <= PASS_CLASS_BITS);
pass_class_t mask = PASS_CLASS_MASK_FROM_INDEX(m_PassClasses.size());
m_PassClasses.push_back(PathfinderPassability(mask, it->second));
m_PassClassMasks[name] = mask;
}
}
+CCmpPathfinder::~CCmpPathfinder() {};
+
void CCmpPathfinder::Deinit()
{
SetDebugOverlay(false); // cleans up memory
SAFE_DELETE(m_AtlasOverlay);
SAFE_DELETE(m_Grid);
SAFE_DELETE(m_TerrainOnlyGrid);
}
struct SerializeLongRequest
{
template
void operator()(S& serialize, const char* UNUSED(name), AsyncLongPathRequest& value)
{
serialize.NumberU32_Unbounded("ticket", value.ticket);
serialize.NumberFixed_Unbounded("x0", value.x0);
serialize.NumberFixed_Unbounded("z0", value.z0);
SerializeGoal()(serialize, "goal", value.goal);
serialize.NumberU16_Unbounded("pass class", value.passClass);
serialize.NumberU32_Unbounded("notify", value.notify);
}
};
struct SerializeShortRequest
{
template
void operator()(S& serialize, const char* UNUSED(name), AsyncShortPathRequest& value)
{
serialize.NumberU32_Unbounded("ticket", value.ticket);
serialize.NumberFixed_Unbounded("x0", value.x0);
serialize.NumberFixed_Unbounded("z0", value.z0);
serialize.NumberFixed_Unbounded("clearance", value.clearance);
serialize.NumberFixed_Unbounded("range", value.range);
SerializeGoal()(serialize, "goal", value.goal);
serialize.NumberU16_Unbounded("pass class", value.passClass);
serialize.Bool("avoid moving units", value.avoidMovingUnits);
serialize.NumberU32_Unbounded("group", value.group);
serialize.NumberU32_Unbounded("notify", value.notify);
}
};
template
void CCmpPathfinder::SerializeCommon(S& serialize)
{
SerializeVector()(serialize, "long requests", m_AsyncLongPathRequests);
SerializeVector()(serialize, "short requests", m_AsyncShortPathRequests);
serialize.NumberU32_Unbounded("next ticket", m_NextAsyncTicket);
serialize.NumberU16_Unbounded("same turn moves count", m_SameTurnMovesCount);
serialize.NumberU16_Unbounded("map size", m_MapSize);
}
void CCmpPathfinder::Serialize(ISerializer& serialize)
{
SerializeCommon(serialize);
}
void CCmpPathfinder::Deserialize(const CParamNode& paramNode, IDeserializer& deserialize)
{
Init(paramNode);
SerializeCommon(deserialize);
}
void CCmpPathfinder::HandleMessage(const CMessage& msg, bool UNUSED(global))
{
switch (msg.GetType())
{
case MT_RenderSubmit:
{
const CMessageRenderSubmit& msgData = static_cast (msg);
RenderSubmit(msgData.collector);
break;
}
case MT_TerrainChanged:
m_TerrainDirty = true;
MinimalTerrainUpdate();
break;
case MT_WaterChanged:
case MT_ObstructionMapShapeChanged:
m_TerrainDirty = true;
UpdateGrid();
break;
case MT_TurnStart:
m_SameTurnMovesCount = 0;
break;
}
}
void CCmpPathfinder::RenderSubmit(SceneCollector& collector)
{
- for (size_t i = 0; i < m_DebugOverlayShortPathLines.size(); ++i)
- collector.Submit(&m_DebugOverlayShortPathLines[i]);
-
+ m_VertexPathfinder->RenderSubmit(collector);
m_LongPathfinder.HierarchicalRenderSubmit(collector);
}
+void CCmpPathfinder::SetDebugPath(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass)
+{
+ m_LongPathfinder.SetDebugPath(x0, z0, goal, passClass);
+}
+
+void CCmpPathfinder::SetDebugOverlay(bool enabled)
+{
+ m_VertexPathfinder->SetDebugOverlay(enabled);
+ m_LongPathfinder.SetDebugOverlay(enabled);
+}
+
+void CCmpPathfinder::SetHierDebugOverlay(bool enabled)
+{
+ m_LongPathfinder.SetHierDebugOverlay(enabled, &GetSimContext());
+}
+
+void CCmpPathfinder::GetDebugData(u32& steps, double& time, Grid& grid) const
+{
+ m_LongPathfinder.GetDebugData(steps, time, grid);
+}
+
void CCmpPathfinder::SetAtlasOverlay(bool enable, pass_class_t passClass)
{
if (enable)
{
if (!m_AtlasOverlay)
m_AtlasOverlay = new AtlasOverlay(this, passClass);
m_AtlasOverlay->m_PassClass = passClass;
}
else
SAFE_DELETE(m_AtlasOverlay);
}
pass_class_t CCmpPathfinder::GetPassabilityClass(const std::string& name) const
{
std::map::const_iterator it = m_PassClassMasks.find(name);
if (it == m_PassClassMasks.end())
{
LOGERROR("Invalid passability class name '%s'", name.c_str());
return 0;
}
return it->second;
}
void CCmpPathfinder::GetPassabilityClasses(std::map& passClasses) const
{
passClasses = m_PassClassMasks;
}
void CCmpPathfinder::GetPassabilityClasses(std::map& nonPathfindingPassClasses, std::map& pathfindingPassClasses) const
{
for (const std::pair& pair : m_PassClassMasks)
{
if ((GetPassabilityFromMask(pair.second)->m_Obstructions == PathfinderPassability::PATHFINDING))
pathfindingPassClasses[pair.first] = pair.second;
else
nonPathfindingPassClasses[pair.first] = pair.second;
}
}
const PathfinderPassability* CCmpPathfinder::GetPassabilityFromMask(pass_class_t passClass) const
{
for (const PathfinderPassability& passability : m_PassClasses)
{
if (passability.m_Mask == passClass)
return &passability;
}
return NULL;
}
const Grid& CCmpPathfinder::GetPassabilityGrid()
{
if (!m_Grid)
UpdateGrid();
return *m_Grid;
}
/**
* Given a grid of passable/impassable navcells (based on some passability mask),
* computes a new grid where a navcell is impassable (per that mask) if
* it is <=clearance navcells away from an impassable navcell in the original grid.
* The results are ORed onto the original grid.
*
* This is used for adding clearance onto terrain-based navcell passability.
*
* TODO PATHFINDER: might be nicer to get rounded corners by measuring clearances as
* Euclidean distances; currently it effectively does dist=max(dx,dy) instead.
* This would only really be a problem for big clearances.
*/
static void ExpandImpassableCells(Grid& grid, u16 clearance, pass_class_t mask)
{
PROFILE3("ExpandImpassableCells");
u16 w = grid.m_W;
u16 h = grid.m_H;
// First expand impassable cells horizontally into a temporary 1-bit grid
Grid tempGrid(w, h);
for (u16 j = 0; j < h; ++j)
{
// New cell (i,j) is blocked if (i',j) blocked for any i-clearance <= i' <= i+clearance
// Count the number of blocked cells around i=0
u16 numBlocked = 0;
for (u16 i = 0; i <= clearance && i < w; ++i)
if (!IS_PASSABLE(grid.get(i, j), mask))
++numBlocked;
for (u16 i = 0; i < w; ++i)
{
// Store a flag if blocked by at least one nearby cell
if (numBlocked)
tempGrid.set(i, j, 1);
// Slide the numBlocked window along:
// remove the old i-clearance value, add the new (i+1)+clearance
// (avoiding overflowing the grid)
if (i >= clearance && !IS_PASSABLE(grid.get(i-clearance, j), mask))
--numBlocked;
if (i+1+clearance < w && !IS_PASSABLE(grid.get(i+1+clearance, j), mask))
++numBlocked;
}
}
for (u16 i = 0; i < w; ++i)
{
// New cell (i,j) is blocked if (i,j') blocked for any j-clearance <= j' <= j+clearance
// Count the number of blocked cells around j=0
u16 numBlocked = 0;
for (u16 j = 0; j <= clearance && j < h; ++j)
if (tempGrid.get(i, j))
++numBlocked;
for (u16 j = 0; j < h; ++j)
{
// Add the mask if blocked by at least one nearby cell
if (numBlocked)
grid.set(i, j, grid.get(i, j) | mask);
// Slide the numBlocked window along:
// remove the old j-clearance value, add the new (j+1)+clearance
// (avoiding overflowing the grid)
if (j >= clearance && tempGrid.get(i, j-clearance))
--numBlocked;
if (j+1+clearance < h && tempGrid.get(i, j+1+clearance))
++numBlocked;
}
}
}
Grid CCmpPathfinder::ComputeShoreGrid(bool expandOnWater)
{
PROFILE3("ComputeShoreGrid");
CmpPtr cmpWaterManager(GetSystemEntity());
// TODO: these bits should come from ICmpTerrain
CTerrain& terrain = GetSimContext().GetTerrain();
// avoid integer overflow in intermediate calculation
const u16 shoreMax = 32767;
// First pass - find underwater tiles
Grid waterGrid(m_MapSize, m_MapSize);
for (u16 j = 0; j < m_MapSize; ++j)
{
for (u16 i = 0; i < m_MapSize; ++i)
{
fixed x, z;
Pathfinding::TileCenter(i, j, x, z);
bool underWater = cmpWaterManager && (cmpWaterManager->GetWaterLevel(x, z) > terrain.GetExactGroundLevelFixed(x, z));
waterGrid.set(i, j, underWater ? 1 : 0);
}
}
// Second pass - find shore tiles
Grid shoreGrid(m_MapSize, m_MapSize);
for (u16 j = 0; j < m_MapSize; ++j)
{
for (u16 i = 0; i < m_MapSize; ++i)
{
// Find a land tile
if (!waterGrid.get(i, j))
{
// If it's bordered by water, it's a shore tile
if ((i > 0 && waterGrid.get(i-1, j)) || (i > 0 && j < m_MapSize-1 && waterGrid.get(i-1, j+1)) || (i > 0 && j > 0 && waterGrid.get(i-1, j-1))
|| (i < m_MapSize-1 && waterGrid.get(i+1, j)) || (i < m_MapSize-1 && j < m_MapSize-1 && waterGrid.get(i+1, j+1)) || (i < m_MapSize-1 && j > 0 && waterGrid.get(i+1, j-1))
|| (j > 0 && waterGrid.get(i, j-1)) || (j < m_MapSize-1 && waterGrid.get(i, j+1))
)
shoreGrid.set(i, j, 0);
else
shoreGrid.set(i, j, shoreMax);
}
// If we want to expand on water, we want water tiles not to be shore tiles
else if (expandOnWater)
shoreGrid.set(i, j, shoreMax);
}
}
// Expand influences on land to find shore distance
for (u16 y = 0; y < m_MapSize; ++y)
{
u16 min = shoreMax;
for (u16 x = 0; x < m_MapSize; ++x)
{
if (!waterGrid.get(x, y) || expandOnWater)
{
u16 g = shoreGrid.get(x, y);
if (g > min)
shoreGrid.set(x, y, min);
else if (g < min)
min = g;
++min;
}
}
for (u16 x = m_MapSize; x > 0; --x)
{
if (!waterGrid.get(x-1, y) || expandOnWater)
{
u16 g = shoreGrid.get(x-1, y);
if (g > min)
shoreGrid.set(x-1, y, min);
else if (g < min)
min = g;
++min;
}
}
}
for (u16 x = 0; x < m_MapSize; ++x)
{
u16 min = shoreMax;
for (u16 y = 0; y < m_MapSize; ++y)
{
if (!waterGrid.get(x, y) || expandOnWater)
{
u16 g = shoreGrid.get(x, y);
if (g > min)
shoreGrid.set(x, y, min);
else if (g < min)
min = g;
++min;
}
}
for (u16 y = m_MapSize; y > 0; --y)
{
if (!waterGrid.get(x, y-1) || expandOnWater)
{
u16 g = shoreGrid.get(x, y-1);
if (g > min)
shoreGrid.set(x, y-1, min);
else if (g < min)
min = g;
++min;
}
}
}
return shoreGrid;
}
void CCmpPathfinder::UpdateGrid()
{
PROFILE3("UpdateGrid");
CmpPtr cmpTerrain(GetSimContext(), SYSTEM_ENTITY);
if (!cmpTerrain)
return; // error
u16 terrainSize = cmpTerrain->GetTilesPerSide();
if (terrainSize == 0)
return;
// If the terrain was resized then delete the old grid data
if (m_Grid && m_MapSize != terrainSize)
{
SAFE_DELETE(m_Grid);
SAFE_DELETE(m_TerrainOnlyGrid);
}
// Initialise the terrain data when first needed
if (!m_Grid)
{
m_MapSize = terrainSize;
m_Grid = new Grid(m_MapSize * Pathfinding::NAVCELLS_PER_TILE, m_MapSize * Pathfinding::NAVCELLS_PER_TILE);
SAFE_DELETE(m_TerrainOnlyGrid);
m_TerrainOnlyGrid = new Grid(m_MapSize * Pathfinding::NAVCELLS_PER_TILE, m_MapSize * Pathfinding::NAVCELLS_PER_TILE);
m_DirtinessInformation = { true, true, Grid(m_MapSize * Pathfinding::NAVCELLS_PER_TILE, m_MapSize * Pathfinding::NAVCELLS_PER_TILE) };
m_AIPathfinderDirtinessInformation = m_DirtinessInformation;
m_TerrainDirty = true;
}
// The grid should be properly initialized and clean. Checking the latter is expensive so do it only for debugging.
#ifdef NDEBUG
ENSURE(m_DirtinessInformation.dirtinessGrid.compare_sizes(m_Grid));
#else
ENSURE(m_DirtinessInformation.dirtinessGrid == Grid(m_MapSize * Pathfinding::NAVCELLS_PER_TILE, m_MapSize * Pathfinding::NAVCELLS_PER_TILE));
#endif
CmpPtr cmpObstructionManager(GetSimContext(), SYSTEM_ENTITY);
cmpObstructionManager->UpdateInformations(m_DirtinessInformation);
if (!m_DirtinessInformation.dirty && !m_TerrainDirty)
return;
// If the terrain has changed, recompute m_Grid
// Else, use data from m_TerrainOnlyGrid and add obstructions
if (m_TerrainDirty)
{
TerrainUpdateHelper();
*m_Grid = *m_TerrainOnlyGrid;
m_TerrainDirty = false;
m_DirtinessInformation.globallyDirty = true;
}
else if (m_DirtinessInformation.globallyDirty)
{
ENSURE(m_Grid->compare_sizes(m_TerrainOnlyGrid));
memcpy(m_Grid->m_Data, m_TerrainOnlyGrid->m_Data, (m_Grid->m_W)*(m_Grid->m_H)*sizeof(NavcellData));
}
else
{
ENSURE(m_Grid->compare_sizes(m_TerrainOnlyGrid));
for (u16 j = 0; j < m_DirtinessInformation.dirtinessGrid.m_H; ++j)
for (u16 i = 0; i < m_DirtinessInformation.dirtinessGrid.m_W; ++i)
if (m_DirtinessInformation.dirtinessGrid.get(i, j) == 1)
m_Grid->set(i, j, m_TerrainOnlyGrid->get(i, j));
}
// Add obstructions onto the grid
cmpObstructionManager->Rasterize(*m_Grid, m_PassClasses, m_DirtinessInformation.globallyDirty);
// Update the long-range pathfinder
if (m_DirtinessInformation.globallyDirty)
{
std::map nonPathfindingPassClasses, pathfindingPassClasses;
GetPassabilityClasses(nonPathfindingPassClasses, pathfindingPassClasses);
m_LongPathfinder.Reload(m_Grid, nonPathfindingPassClasses, pathfindingPassClasses);
}
else
m_LongPathfinder.Update(m_Grid, m_DirtinessInformation.dirtinessGrid);
// Remember the necessary updates that the AI pathfinder will have to perform as well
m_AIPathfinderDirtinessInformation.MergeAndClear(m_DirtinessInformation);
}
void CCmpPathfinder::MinimalTerrainUpdate()
{
TerrainUpdateHelper(false);
}
void CCmpPathfinder::TerrainUpdateHelper(bool expandPassability/* = true */)
{
PROFILE3("TerrainUpdateHelper");
CmpPtr cmpObstructionManager(GetSimContext(), SYSTEM_ENTITY);
CmpPtr cmpWaterManager(GetSimContext(), SYSTEM_ENTITY);
CmpPtr cmpTerrain(GetSimContext(), SYSTEM_ENTITY);
CTerrain& terrain = GetSimContext().GetTerrain();
if (!cmpTerrain || !cmpObstructionManager)
return;
u16 terrainSize = cmpTerrain->GetTilesPerSide();
if (terrainSize == 0)
return;
if (!m_TerrainOnlyGrid || m_MapSize != terrainSize)
{
m_MapSize = terrainSize;
SAFE_DELETE(m_TerrainOnlyGrid);
m_TerrainOnlyGrid = new Grid(m_MapSize * Pathfinding::NAVCELLS_PER_TILE, m_MapSize * Pathfinding::NAVCELLS_PER_TILE);
// If this update comes from a map resizing, we must reinitialize the other grids as well
if (!m_TerrainOnlyGrid->compare_sizes(m_Grid))
{
SAFE_DELETE(m_Grid);
m_Grid = new Grid(m_MapSize * Pathfinding::NAVCELLS_PER_TILE, m_MapSize * Pathfinding::NAVCELLS_PER_TILE);
m_DirtinessInformation = { true, true, Grid(m_MapSize * Pathfinding::NAVCELLS_PER_TILE, m_MapSize * Pathfinding::NAVCELLS_PER_TILE) };
m_AIPathfinderDirtinessInformation = m_DirtinessInformation;
}
}
Grid shoreGrid = ComputeShoreGrid();
// Compute initial terrain-dependent passability
for (int j = 0; j < m_MapSize * Pathfinding::NAVCELLS_PER_TILE; ++j)
{
for (int i = 0; i < m_MapSize * Pathfinding::NAVCELLS_PER_TILE; ++i)
{
// World-space coordinates for this navcell
fixed x, z;
Pathfinding::NavcellCenter(i, j, x, z);
// Terrain-tile coordinates for this navcell
int itile = i / Pathfinding::NAVCELLS_PER_TILE;
int jtile = j / Pathfinding::NAVCELLS_PER_TILE;
// Gather all the data potentially needed to determine passability:
fixed height = terrain.GetExactGroundLevelFixed(x, z);
fixed water;
if (cmpWaterManager)
water = cmpWaterManager->GetWaterLevel(x, z);
fixed depth = water - height;
// Exact slopes give kind of weird output, so just use rough tile-based slopes
fixed slope = terrain.GetSlopeFixed(itile, jtile);
// Get world-space coordinates from shoreGrid (which uses terrain tiles)
fixed shoredist = fixed::FromInt(shoreGrid.get(itile, jtile)).MultiplyClamp(TERRAIN_TILE_SIZE);
// Compute the passability for every class for this cell
NavcellData t = 0;
for (PathfinderPassability& passability : m_PassClasses)
if (!passability.IsPassable(depth, slope, shoredist))
t |= passability.m_Mask;
m_TerrainOnlyGrid->set(i, j, t);
}
}
// Compute off-world passability
// WARNING: CCmpRangeManager::LosIsOffWorld needs to be kept in sync with this
const int edgeSize = 3 * Pathfinding::NAVCELLS_PER_TILE; // number of tiles around the edge that will be off-world
NavcellData edgeMask = 0;
for (PathfinderPassability& passability : m_PassClasses)
edgeMask |= passability.m_Mask;
int w = m_TerrainOnlyGrid->m_W;
int h = m_TerrainOnlyGrid->m_H;
if (cmpObstructionManager->GetPassabilityCircular())
{
for (int j = 0; j < h; ++j)
{
for (int i = 0; i < w; ++i)
{
// Based on CCmpRangeManager::LosIsOffWorld
// but tweaked since it's tile-based instead.
// (We double all the values so we can handle half-tile coordinates.)
// This needs to be slightly tighter than the LOS circle,
// else units might get themselves lost in the SoD around the edge.
int dist2 = (i*2 + 1 - w)*(i*2 + 1 - w)
+ (j*2 + 1 - h)*(j*2 + 1 - h);
if (dist2 >= (w - 2*edgeSize) * (h - 2*edgeSize))
m_TerrainOnlyGrid->set(i, j, m_TerrainOnlyGrid->get(i, j) | edgeMask);
}
}
}
else
{
for (u16 j = 0; j < h; ++j)
for (u16 i = 0; i < edgeSize; ++i)
m_TerrainOnlyGrid->set(i, j, m_TerrainOnlyGrid->get(i, j) | edgeMask);
for (u16 j = 0; j < h; ++j)
for (u16 i = w-edgeSize+1; i < w; ++i)
m_TerrainOnlyGrid->set(i, j, m_TerrainOnlyGrid->get(i, j) | edgeMask);
for (u16 j = 0; j < edgeSize; ++j)
for (u16 i = edgeSize; i < w-edgeSize+1; ++i)
m_TerrainOnlyGrid->set(i, j, m_TerrainOnlyGrid->get(i, j) | edgeMask);
for (u16 j = h-edgeSize+1; j < h; ++j)
for (u16 i = edgeSize; i < w-edgeSize+1; ++i)
m_TerrainOnlyGrid->set(i, j, m_TerrainOnlyGrid->get(i, j) | edgeMask);
}
if (!expandPassability)
return;
// Expand the impassability grid, for any class with non-zero clearance,
// so that we can stop units getting too close to impassable navcells.
// Note: It's not possible to perform this expansion once for all passabilities
// with the same clearance, because the impassable cells are not necessarily the
// same for all these passabilities.
for (PathfinderPassability& passability : m_PassClasses)
{
if (passability.m_Clearance == fixed::Zero())
continue;
int clearance = (passability.m_Clearance / Pathfinding::NAVCELL_SIZE).ToInt_RoundToInfinity();
ExpandImpassableCells(*m_TerrainOnlyGrid, clearance, passability.m_Mask);
}
}
//////////////////////////////////////////////////////////
-// Async path requests:
-
u32 CCmpPathfinder::ComputePathAsync(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass, entity_id_t notify)
{
AsyncLongPathRequest req = { m_NextAsyncTicket++, x0, z0, goal, passClass, notify };
m_AsyncLongPathRequests.push_back(req);
return req.ticket;
}
u32 CCmpPathfinder::ComputeShortPathAsync(entity_pos_t x0, entity_pos_t z0, entity_pos_t clearance, entity_pos_t range, const PathGoal& goal, pass_class_t passClass, bool avoidMovingUnits, entity_id_t group, entity_id_t notify)
{
AsyncShortPathRequest req = { m_NextAsyncTicket++, x0, z0, clearance, range, goal, passClass, avoidMovingUnits, group, notify };
m_AsyncShortPathRequests.push_back(req);
return req.ticket;
}
+WaypointPath CCmpPathfinder::ComputeShortPath(const AsyncShortPathRequest& request) const
+{
+ return m_VertexPathfinder->ComputeShortPath(request, CmpPtr(GetSystemEntity()));
+}
+
+// Async processing:
+
void CCmpPathfinder::FinishAsyncRequests()
{
PROFILE2("Finish Async Requests");
// Save the request queue in case it gets modified while iterating
std::vector longRequests;
m_AsyncLongPathRequests.swap(longRequests);
std::vector shortRequests;
m_AsyncShortPathRequests.swap(shortRequests);
// TODO: we should only compute one path per entity per turn
// TODO: this computation should be done incrementally, spread
// across multiple frames (or even multiple turns)
ProcessLongRequests(longRequests);
ProcessShortRequests(shortRequests);
}
void CCmpPathfinder::ProcessLongRequests(const std::vector& longRequests)
{
PROFILE2("Process Long Requests");
for (size_t i = 0; i < longRequests.size(); ++i)
{
const AsyncLongPathRequest& req = longRequests[i];
WaypointPath path;
ComputePath(req.x0, req.z0, req.goal, req.passClass, path);
CMessagePathResult msg(req.ticket, path);
GetSimContext().GetComponentManager().PostMessage(req.notify, msg);
}
}
void CCmpPathfinder::ProcessShortRequests(const std::vector& shortRequests)
{
PROFILE2("Process Short Requests");
for (size_t i = 0; i < shortRequests.size(); ++i)
{
const AsyncShortPathRequest& req = shortRequests[i];
- WaypointPath path;
- ControlGroupMovementObstructionFilter filter(req.avoidMovingUnits, req.group);
- ComputeShortPath(filter, req.x0, req.z0, req.clearance, req.range, req.goal, req.passClass, path);
+ WaypointPath path = m_VertexPathfinder->ComputeShortPath(req, CmpPtr(GetSystemEntity()));
CMessagePathResult msg(req.ticket, path);
GetSimContext().GetComponentManager().PostMessage(req.notify, msg);
}
}
void CCmpPathfinder::ProcessSameTurnMoves()
{
if (!m_AsyncLongPathRequests.empty())
{
// Figure out how many moves we can do this time
i32 moveCount = m_MaxSameTurnMoves - m_SameTurnMovesCount;
if (moveCount <= 0)
return;
// Copy the long request elements we are going to process into a new array
std::vector longRequests;
if ((i32)m_AsyncLongPathRequests.size() <= moveCount)
{
m_AsyncLongPathRequests.swap(longRequests);
moveCount = (i32)longRequests.size();
}
else
{
longRequests.resize(moveCount);
copy(m_AsyncLongPathRequests.begin(), m_AsyncLongPathRequests.begin() + moveCount, longRequests.begin());
m_AsyncLongPathRequests.erase(m_AsyncLongPathRequests.begin(), m_AsyncLongPathRequests.begin() + moveCount);
}
ProcessLongRequests(longRequests);
m_SameTurnMovesCount = (u16)(m_SameTurnMovesCount + moveCount);
}
if (!m_AsyncShortPathRequests.empty())
{
// Figure out how many moves we can do now
i32 moveCount = m_MaxSameTurnMoves - m_SameTurnMovesCount;
if (moveCount <= 0)
return;
// Copy the short request elements we are going to process into a new array
std::vector shortRequests;
if ((i32)m_AsyncShortPathRequests.size() <= moveCount)
{
m_AsyncShortPathRequests.swap(shortRequests);
moveCount = (i32)shortRequests.size();
}
else
{
shortRequests.resize(moveCount);
copy(m_AsyncShortPathRequests.begin(), m_AsyncShortPathRequests.begin() + moveCount, shortRequests.begin());
m_AsyncShortPathRequests.erase(m_AsyncShortPathRequests.begin(), m_AsyncShortPathRequests.begin() + moveCount);
}
ProcessShortRequests(shortRequests);
m_SameTurnMovesCount = (u16)(m_SameTurnMovesCount + moveCount);
}
}
//////////////////////////////////////////////////////////
bool CCmpPathfinder::CheckMovement(const IObstructionTestFilter& filter,
entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1, entity_pos_t r,
pass_class_t passClass) const
{
PROFILE2_IFSPIKE("Check Movement", 0.001);
// Test against obstructions first. filter may discard pathfinding-blocking obstructions.
// Use more permissive version of TestLine to allow unit-unit collisions to overlap slightly.
// This makes movement smoother and more natural for units, overall.
CmpPtr cmpObstructionManager(GetSystemEntity());
if (!cmpObstructionManager || cmpObstructionManager->TestLine(filter, x0, z0, x1, z1, r, true))
return false;
// Then test against the terrain grid. This should not be necessary
// But in case we allow terrain to change it will become so.
return Pathfinding::CheckLineMovement(x0, z0, x1, z1, passClass, *m_TerrainOnlyGrid);
}
ICmpObstruction::EFoundationCheck CCmpPathfinder::CheckUnitPlacement(const IObstructionTestFilter& filter,
entity_pos_t x, entity_pos_t z, entity_pos_t r, pass_class_t passClass, bool UNUSED(onlyCenterPoint)) const
{
// Check unit obstruction
CmpPtr cmpObstructionManager(GetSystemEntity());
if (!cmpObstructionManager)
return ICmpObstruction::FOUNDATION_CHECK_FAIL_ERROR;
if (cmpObstructionManager->TestUnitShape(filter, x, z, r, NULL))
return ICmpObstruction::FOUNDATION_CHECK_FAIL_OBSTRUCTS_FOUNDATION;
// Test against terrain and static obstructions:
u16 i, j;
Pathfinding::NearestNavcell(x, z, i, j, m_MapSize*Pathfinding::NAVCELLS_PER_TILE, m_MapSize*Pathfinding::NAVCELLS_PER_TILE);
if (!IS_PASSABLE(m_Grid->get(i, j), passClass))
return ICmpObstruction::FOUNDATION_CHECK_FAIL_TERRAIN_CLASS;
// (Static obstructions will be redundantly tested against in both the
// obstruction-shape test and navcell-passability test, which is slightly
// inefficient but shouldn't affect behaviour)
return ICmpObstruction::FOUNDATION_CHECK_SUCCESS;
}
ICmpObstruction::EFoundationCheck CCmpPathfinder::CheckBuildingPlacement(const IObstructionTestFilter& filter,
entity_pos_t x, entity_pos_t z, entity_pos_t a, entity_pos_t w,
entity_pos_t h, entity_id_t id, pass_class_t passClass) const
{
return CCmpPathfinder::CheckBuildingPlacement(filter, x, z, a, w, h, id, passClass, false);
}
ICmpObstruction::EFoundationCheck CCmpPathfinder::CheckBuildingPlacement(const IObstructionTestFilter& filter,
entity_pos_t x, entity_pos_t z, entity_pos_t a, entity_pos_t w,
entity_pos_t h, entity_id_t id, pass_class_t passClass, bool UNUSED(onlyCenterPoint)) const
{
// Check unit obstruction
CmpPtr cmpObstructionManager(GetSystemEntity());
if (!cmpObstructionManager)
return ICmpObstruction::FOUNDATION_CHECK_FAIL_ERROR;
if (cmpObstructionManager->TestStaticShape(filter, x, z, a, w, h, NULL))
return ICmpObstruction::FOUNDATION_CHECK_FAIL_OBSTRUCTS_FOUNDATION;
// Test against terrain:
ICmpObstructionManager::ObstructionSquare square;
CmpPtr cmpObstruction(GetSimContext(), id);
if (!cmpObstruction || !cmpObstruction->GetObstructionSquare(square))
return ICmpObstruction::FOUNDATION_CHECK_FAIL_NO_OBSTRUCTION;
entity_pos_t expand;
const PathfinderPassability* passability = GetPassabilityFromMask(passClass);
if (passability)
expand = passability->m_Clearance;
SimRasterize::Spans spans;
SimRasterize::RasterizeRectWithClearance(spans, square, expand, Pathfinding::NAVCELL_SIZE);
for (const SimRasterize::Span& span : spans)
{
i16 i0 = span.i0;
i16 i1 = span.i1;
i16 j = span.j;
// Fail if any span extends outside the grid
if (i0 < 0 || i1 > m_TerrainOnlyGrid->m_W || j < 0 || j > m_TerrainOnlyGrid->m_H)
return ICmpObstruction::FOUNDATION_CHECK_FAIL_TERRAIN_CLASS;
// Fail if any span includes an impassable tile
for (i16 i = i0; i < i1; ++i)
if (!IS_PASSABLE(m_TerrainOnlyGrid->get(i, j), passClass))
return ICmpObstruction::FOUNDATION_CHECK_FAIL_TERRAIN_CLASS;
}
return ICmpObstruction::FOUNDATION_CHECK_SUCCESS;
}
Index: ps/trunk/source/simulation2/components/CCmpPathfinder_Common.h
===================================================================
--- ps/trunk/source/simulation2/components/CCmpPathfinder_Common.h (revision 22252)
+++ ps/trunk/source/simulation2/components/CCmpPathfinder_Common.h (revision 22253)
@@ -1,350 +1,258 @@
-/* Copyright (C) 2017 Wildfire Games.
+/* Copyright (C) 2019 Wildfire Games.
* This file is part of 0 A.D.
*
* 0 A.D. is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 2 of the License, or
* (at your option) any later version.
*
* 0 A.D. is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with 0 A.D. If not, see .
*/
#ifndef INCLUDED_CCMPPATHFINDER_COMMON
#define INCLUDED_CCMPPATHFINDER_COMMON
/**
* @file
* Declares CCmpPathfinder. Its implementation is mainly done in CCmpPathfinder.cpp,
* but the short-range (vertex) pathfinding is done in CCmpPathfinder_Vertex.cpp.
* This file provides common code needed for both files.
*
* The long-range pathfinding is done by a LongPathfinder object.
*/
#include "simulation2/system/Component.h"
#include "ICmpPathfinder.h"
#include "graphics/Overlay.h"
#include "graphics/Terrain.h"
#include "maths/MathUtil.h"
#include "ps/CLogger.h"
+#include "renderer/TerrainOverlay.h"
#include "simulation2/components/ICmpObstructionManager.h"
#include "simulation2/helpers/LongPathfinder.h"
+class VertexPathfinder;
+
class SceneCollector;
class AtlasOverlay;
#ifdef NDEBUG
#define PATHFIND_DEBUG 0
#else
#define PATHFIND_DEBUG 1
#endif
-
-struct AsyncLongPathRequest
-{
- u32 ticket;
- entity_pos_t x0;
- entity_pos_t z0;
- PathGoal goal;
- pass_class_t passClass;
- entity_id_t notify;
-};
-
-struct AsyncShortPathRequest
-{
- u32 ticket;
- entity_pos_t x0;
- entity_pos_t z0;
- entity_pos_t clearance;
- entity_pos_t range;
- PathGoal goal;
- pass_class_t passClass;
- bool avoidMovingUnits;
- entity_id_t group;
- entity_id_t notify;
-};
-
-// A vertex around the corners of an obstruction
-// (paths will be sequences of these vertexes)
-struct Vertex
-{
- enum
- {
- UNEXPLORED,
- OPEN,
- CLOSED,
- };
-
- CFixedVector2D p;
- fixed g, h;
- u16 pred;
- u8 status;
- u8 quadInward : 4; // the quadrant which is inside the shape (or NONE)
- u8 quadOutward : 4; // the quadrants of the next point on the path which this vertex must be in, given 'pred'
-};
-
-// Obstruction edges (paths will not cross any of these).
-// Defines the two points of the edge.
-struct Edge
-{
- CFixedVector2D p0, p1;
-};
-
-// Axis-aligned obstruction squares (paths will not cross any of these).
-// Defines the opposing corners of an axis-aligned square
-// (from which four individual edges can be trivially computed), requiring p0 <= p1
-struct Square
-{
- CFixedVector2D p0, p1;
-};
-
-// Axis-aligned obstruction edges.
-// p0 defines one end; c1 is either the X or Y coordinate of the other end,
-// depending on the context in which this is used.
-struct EdgeAA
-{
- CFixedVector2D p0;
- fixed c1;
-};
-
/**
* Implementation of ICmpPathfinder
*/
-class CCmpPathfinder : public ICmpPathfinder
+class CCmpPathfinder final : public ICmpPathfinder
{
public:
static void ClassInit(CComponentManager& componentManager)
{
componentManager.SubscribeToMessageType(MT_Update);
componentManager.SubscribeToMessageType(MT_RenderSubmit); // for debug overlays
componentManager.SubscribeToMessageType(MT_TerrainChanged);
componentManager.SubscribeToMessageType(MT_WaterChanged);
componentManager.SubscribeToMessageType(MT_ObstructionMapShapeChanged);
componentManager.SubscribeToMessageType(MT_TurnStart);
}
+ ~CCmpPathfinder();
+
DEFAULT_COMPONENT_ALLOCATOR(Pathfinder)
// Template state:
std::map m_PassClassMasks;
std::vector m_PassClasses;
// Dynamic state:
std::vector m_AsyncLongPathRequests;
std::vector m_AsyncShortPathRequests;
u32 m_NextAsyncTicket; // unique IDs for asynchronous path requests
u16 m_SameTurnMovesCount; // current number of same turn moves we have processed this turn
// Lazily-constructed dynamic state (not serialized):
u16 m_MapSize; // tiles per side
Grid* m_Grid; // terrain/passability information
Grid* m_TerrainOnlyGrid; // same as m_Grid, but only with terrain, to avoid some recomputations
// Keep clever updates in memory to avoid memory fragmentation from the grid.
// This should be used only in UpdateGrid(), there is no guarantee the data is properly initialized anywhere else.
GridUpdateInformation m_DirtinessInformation;
// The data from clever updates is stored for the AI manager
GridUpdateInformation m_AIPathfinderDirtinessInformation;
bool m_TerrainDirty;
+ std::unique_ptr m_VertexPathfinder;
// Interface to the long-range pathfinder.
LongPathfinder m_LongPathfinder;
// For responsiveness we will process some moves in the same turn they were generated in
u16 m_MaxSameTurnMoves; // max number of moves that can be created and processed in the same turn
- // memory optimizations: those vectors are created once, reused for all calculations;
- std::vector edgesUnaligned;
- std::vector edgesLeft;
- std::vector edgesRight;
- std::vector edgesBottom;
- std::vector edgesTop;
-
- // List of obstruction vertexes (plus start/end points); we'll try to find paths through
- // the graph defined by these vertexes
- std::vector vertexes;
- // List of collision edges - paths must never cross these.
- // (Edges are one-sided so intersections are fine in one direction, but not the other direction.)
- std::vector edges;
- std::vector edgeSquares; // axis-aligned squares; equivalent to 4 edges
-
- bool m_DebugOverlay;
- std::vector m_DebugOverlayShortPathLines;
AtlasOverlay* m_AtlasOverlay;
static std::string GetSchema()
{
return "";
}
virtual void Init(const CParamNode& paramNode);
virtual void Deinit();
template
void SerializeCommon(S& serialize);
virtual void Serialize(ISerializer& serialize);
virtual void Deserialize(const CParamNode& paramNode, IDeserializer& deserialize);
virtual void HandleMessage(const CMessage& msg, bool global);
virtual pass_class_t GetPassabilityClass(const std::string& name) const;
virtual void GetPassabilityClasses(std::map& passClasses) const;
virtual void GetPassabilityClasses(
std::map& nonPathfindingPassClasses,
std::map& pathfindingPassClasses) const;
const PathfinderPassability* GetPassabilityFromMask(pass_class_t passClass) const;
virtual entity_pos_t GetClearance(pass_class_t passClass) const
{
const PathfinderPassability* passability = GetPassabilityFromMask(passClass);
if (!passability)
return fixed::Zero();
return passability->m_Clearance;
}
virtual entity_pos_t GetMaximumClearance() const
{
entity_pos_t max = fixed::Zero();
for (const PathfinderPassability& passability : m_PassClasses)
if (passability.m_Clearance > max)
max = passability.m_Clearance;
return max + Pathfinding::CLEARANCE_EXTENSION_RADIUS;
}
virtual const Grid& GetPassabilityGrid();
virtual const GridUpdateInformation& GetAIPathfinderDirtinessInformation() const
{
return m_AIPathfinderDirtinessInformation;
}
virtual void FlushAIPathfinderDirtinessInformation()
{
m_AIPathfinderDirtinessInformation.Clean();
}
virtual Grid ComputeShoreGrid(bool expandOnWater = false);
virtual void ComputePath(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass, WaypointPath& ret)
{
m_LongPathfinder.ComputePath(x0, z0, goal, passClass, ret);
}
virtual u32 ComputePathAsync(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass, entity_id_t notify);
- virtual void ComputeShortPath(const IObstructionTestFilter& filter, entity_pos_t x0, entity_pos_t z0, entity_pos_t clearance, entity_pos_t range, const PathGoal& goal, pass_class_t passClass, WaypointPath& ret);
+ virtual WaypointPath ComputeShortPath(const AsyncShortPathRequest& request) const;
virtual u32 ComputeShortPathAsync(entity_pos_t x0, entity_pos_t z0, entity_pos_t clearance, entity_pos_t range, const PathGoal& goal, pass_class_t passClass, bool avoidMovingUnits, entity_id_t controller, entity_id_t notify);
- virtual void SetDebugPath(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass)
- {
- m_LongPathfinder.SetDebugPath(x0, z0, goal, passClass);
- }
+ virtual void SetDebugPath(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass);
- virtual void SetDebugOverlay(bool enabled)
- {
- m_DebugOverlay = enabled;
- m_LongPathfinder.SetDebugOverlay(enabled);
- }
+ virtual void SetDebugOverlay(bool enabled);
- virtual void SetHierDebugOverlay(bool enabled)
- {
- m_LongPathfinder.SetHierDebugOverlay(enabled, &GetSimContext());
- }
+ virtual void SetHierDebugOverlay(bool enabled);
- virtual void GetDebugData(u32& steps, double& time, Grid& grid) const
- {
- m_LongPathfinder.GetDebugData(steps, time, grid);
- }
+ virtual void GetDebugData(u32& steps, double& time, Grid& grid) const;
virtual void SetAtlasOverlay(bool enable, pass_class_t passClass = 0);
virtual bool CheckMovement(const IObstructionTestFilter& filter, entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1, entity_pos_t r, pass_class_t passClass) const;
virtual ICmpObstruction::EFoundationCheck CheckUnitPlacement(const IObstructionTestFilter& filter, entity_pos_t x, entity_pos_t z, entity_pos_t r, pass_class_t passClass, bool onlyCenterPoint) const;
virtual ICmpObstruction::EFoundationCheck CheckBuildingPlacement(const IObstructionTestFilter& filter, entity_pos_t x, entity_pos_t z, entity_pos_t a, entity_pos_t w, entity_pos_t h, entity_id_t id, pass_class_t passClass) const;
virtual ICmpObstruction::EFoundationCheck CheckBuildingPlacement(const IObstructionTestFilter& filter, entity_pos_t x, entity_pos_t z, entity_pos_t a, entity_pos_t w, entity_pos_t h, entity_id_t id, pass_class_t passClass, bool onlyCenterPoint) const;
virtual void FinishAsyncRequests();
void ProcessLongRequests(const std::vector& longRequests);
void ProcessShortRequests(const std::vector& shortRequests);
virtual void ProcessSameTurnMoves();
/**
* Regenerates the grid based on the current obstruction list, if necessary
*/
virtual void UpdateGrid();
/**
* Updates the terrain-only grid without updating the dirtiness informations.
* Useful for fast passability updates in Atlas.
*/
void MinimalTerrainUpdate();
/**
* Regenerates the terrain-only grid.
* Atlas doesn't need to have passability cells expanded.
*/
void TerrainUpdateHelper(bool expandPassability = true);
void RenderSubmit(SceneCollector& collector);
};
class AtlasOverlay : public TerrainTextureOverlay
{
public:
const CCmpPathfinder* m_Pathfinder;
pass_class_t m_PassClass;
AtlasOverlay(const CCmpPathfinder* pathfinder, pass_class_t passClass) :
TerrainTextureOverlay(Pathfinding::NAVCELLS_PER_TILE), m_Pathfinder(pathfinder), m_PassClass(passClass)
{
}
virtual void BuildTextureRGBA(u8* data, size_t w, size_t h)
{
// Render navcell passability, based on the terrain-only grid
u8* p = data;
for (size_t j = 0; j < h; ++j)
{
for (size_t i = 0; i < w; ++i)
{
SColor4ub color(0, 0, 0, 0);
if (!IS_PASSABLE(m_Pathfinder->m_TerrainOnlyGrid->get((int)i, (int)j), m_PassClass))
color = SColor4ub(255, 0, 0, 127);
*p++ = color.R;
*p++ = color.G;
*p++ = color.B;
*p++ = color.A;
}
}
}
};
#endif // INCLUDED_CCMPPATHFINDER_COMMON
Index: ps/trunk/source/simulation2/components/ICmpPathfinder.h
===================================================================
--- ps/trunk/source/simulation2/components/ICmpPathfinder.h (revision 22252)
+++ ps/trunk/source/simulation2/components/ICmpPathfinder.h (revision 22253)
@@ -1,199 +1,199 @@
-/* Copyright (C) 2017 Wildfire Games.
+/* Copyright (C) 2019 Wildfire Games.
* This file is part of 0 A.D.
*
* 0 A.D. is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 2 of the License, or
* (at your option) any later version.
*
* 0 A.D. is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with 0 A.D. If not, see .
*/
#ifndef INCLUDED_ICMPPATHFINDER
#define INCLUDED_ICMPPATHFINDER
#include "simulation2/system/Interface.h"
#include "simulation2/components/ICmpObstruction.h"
#include "simulation2/helpers/PathGoal.h"
#include "simulation2/helpers/Pathfinding.h"
#include "maths/FixedVector2D.h"
#include