Line data Source code
1 : /* Copyright (C) 2021 Wildfire Games.
2 : * This file is part of 0 A.D.
3 : *
4 : * 0 A.D. is free software: you can redistribute it and/or modify
5 : * it under the terms of the GNU General Public License as published by
6 : * the Free Software Foundation, either version 2 of the License, or
7 : * (at your option) any later version.
8 : *
9 : * 0 A.D. is distributed in the hope that it will be useful,
10 : * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 : * GNU General Public License for more details.
13 : *
14 : * You should have received a copy of the GNU General Public License
15 : * along with 0 A.D. If not, see <http://www.gnu.org/licenses/>.
16 : */
17 :
18 : #ifndef INCLUDED_VERTEXPATHFINDER
19 : #define INCLUDED_VERTEXPATHFINDER
20 :
21 : #include "graphics/Overlay.h"
22 : #include "simulation2/helpers/Pathfinding.h"
23 : #include "simulation2/system/CmpPtr.h"
24 :
25 : #include <atomic>
26 : #include <vector>
27 :
28 : // A vertex around the corners of an obstruction
29 : // (paths will be sequences of these vertexes)
30 0 : struct Vertex
31 : {
32 : enum
33 : {
34 : UNEXPLORED,
35 : OPEN,
36 : CLOSED,
37 : };
38 :
39 : CFixedVector2D p;
40 : fixed g, h;
41 : u16 pred;
42 : u8 status;
43 : u8 quadInward : 4; // the quadrant which is inside the shape (or NONE)
44 : u8 quadOutward : 4; // the quadrants of the next point on the path which this vertex must be in, given 'pred'
45 : };
46 :
47 : // Obstruction edges (paths will not cross any of these).
48 : // Defines the two points of the edge.
49 : struct Edge
50 : {
51 : CFixedVector2D p0, p1;
52 : };
53 :
54 : // Axis-aligned obstruction squares (paths will not cross any of these).
55 : // Defines the opposing corners of an axis-aligned square
56 : // (from which four individual edges can be trivially computed), requiring p0 <= p1
57 : struct Square
58 : {
59 : CFixedVector2D p0, p1;
60 : };
61 :
62 : // Axis-aligned obstruction edges.
63 : // p0 defines one end; c1 is either the X or Y coordinate of the other end,
64 : // depending on the context in which this is used.
65 : struct EdgeAA
66 : {
67 : CFixedVector2D p0;
68 : fixed c1;
69 : };
70 :
71 : class ICmpObstructionManager;
72 : class CSimContext;
73 : class SceneCollector;
74 :
75 21 : class VertexPathfinder
76 : {
77 : public:
78 12 : VertexPathfinder(const u16& gridSize, Grid<NavcellData>* const & terrainOnlyGrid) : m_GridSize(gridSize), m_TerrainOnlyGrid(terrainOnlyGrid) {};
79 : VertexPathfinder(const VertexPathfinder&) = delete;
80 9 : VertexPathfinder(VertexPathfinder&& o) : m_GridSize(o.m_GridSize), m_TerrainOnlyGrid(o.m_TerrainOnlyGrid) {}
81 :
82 : /**
83 : * Compute a precise path from the given point to the goal, and return the set of waypoints.
84 : * The path is based on the full set of obstructions that pass the filter, such that
85 : * a unit of clearance 'clearance' will be able to follow the path with no collisions.
86 : * The path is restricted to a box of radius 'range' from the starting point.
87 : * Defined in CCmpPathfinder_Vertex.cpp
88 : */
89 : WaypointPath ComputeShortPath(const ShortPathRequest& request, CmpPtr<ICmpObstructionManager> cmpObstructionManager) const;
90 :
91 : private:
92 :
93 : // References to the Pathfinder for convenience.
94 : const u16& m_GridSize;
95 : Grid<NavcellData>* const & m_TerrainOnlyGrid;
96 :
97 : // These vectors are expensive to recreate on every call, so we cache them here.
98 : // They are made mutable to allow using them in the otherwise const ComputeShortPath.
99 :
100 : mutable std::vector<Edge> m_EdgesUnaligned;
101 : mutable std::vector<EdgeAA> m_EdgesLeft;
102 : mutable std::vector<EdgeAA> m_EdgesRight;
103 : mutable std::vector<EdgeAA> m_EdgesBottom;
104 : mutable std::vector<EdgeAA> m_EdgesTop;
105 :
106 : // List of obstruction vertexes (plus start/end points); we'll try to find paths through
107 : // the graph defined by these vertexes.
108 : mutable std::vector<Vertex> m_Vertexes;
109 : // List of collision edges - paths must never cross these.
110 : // (Edges are one-sided so intersections are fine in one direction, but not the other direction.)
111 : mutable std::vector<Edge> m_Edges;
112 : mutable std::vector<Square> m_EdgeSquares; // Axis-aligned squares; equivalent to 4 edges.
113 : };
114 :
115 : /**
116 : * There are several vertex pathfinders running asynchronously, so their debug output
117 : * might conflict. To remain thread-safe, this single class will handle the debug data.
118 : * NB: though threadsafe, the way things are setup means you can have a few
119 : * more graphs and edges than you'd expect showing up in the rendered graph.
120 : */
121 2 : class VertexPathfinderDebugOverlay
122 : {
123 : friend class VertexPathfinder;
124 : public:
125 3 : void SetDebugOverlay(bool enabled) { m_DebugOverlay = enabled; }
126 : void RenderSubmit(SceneCollector& collector);
127 : protected:
128 :
129 : void DebugRenderGoal(const CSimContext& simContext, const PathGoal& goal);
130 : void DebugRenderGraph(const CSimContext& simContext, const std::vector<Vertex>& vertexes, const std::vector<Edge>& edges, const std::vector<Square>& edgeSquares);
131 : void DebugRenderEdges(const CSimContext& simContext, bool visible, CFixedVector2D curr, CFixedVector2D npos);
132 :
133 : std::atomic<bool> m_DebugOverlay = false;
134 : // The data is double buffered: the first is the 'work-in-progress' state, the second the last RenderSubmit state.
135 : std::vector<SOverlayLine> m_DebugOverlayShortPathLines;
136 : std::vector<SOverlayLine> m_DebugOverlayShortPathLinesSubmitted;
137 : };
138 :
139 : extern VertexPathfinderDebugOverlay g_VertexPathfinderDebugOverlay;
140 :
141 : #endif // INCLUDED_VERTEXPATHFINDER
|
