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 : #include "precompiled.h"
19 :
20 : #include "Pathfinding.h"
21 :
22 : #include "graphics/Terrain.h"
23 : #include "ps/CLogger.h"
24 : #include "simulation2/helpers/Grid.h"
25 : #include "simulation2/system/ParamNode.h"
26 :
27 : namespace Pathfinding
28 : {
29 0 : bool CheckLineMovement(entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1,
30 : pass_class_t passClass, const Grid<NavcellData>& grid)
31 : {
32 : // We shouldn't allow lines between diagonally-adjacent navcells.
33 : // It doesn't matter whether we allow lines precisely along the edge
34 : // of an impassable navcell.
35 :
36 : // To rasterise the line:
37 : // If the line is (e.g.) aiming up-right, then we start at the navcell
38 : // containing the start point and the line must either end in that navcell
39 : // or else exit along the top edge or the right edge (or through the top-right corner,
40 : // which we'll arbitrary treat as the horizontal edge).
41 : // So we jump into the adjacent navcell across that edge, and continue.
42 :
43 : // To handle the special case of units that are stuck on impassable cells,
44 : // we allow them to move from an impassable to a passable cell (but not
45 : // vice versa).
46 :
47 : u16 i0, j0, i1, j1;
48 0 : NearestNavcell(x0, z0, i0, j0, grid.m_W, grid.m_H);
49 0 : NearestNavcell(x1, z1, i1, j1, grid.m_W, grid.m_H);
50 :
51 : // Find which direction the line heads in
52 0 : int di = (i0 < i1 ? +1 : i1 < i0 ? -1 : 0);
53 0 : int dj = (j0 < j1 ? +1 : j1 < j0 ? -1 : 0);
54 :
55 0 : u16 i = i0;
56 0 : u16 j = j0;
57 :
58 0 : bool currentlyOnImpassable = !IS_PASSABLE(grid.get(i0, j0), passClass);
59 :
60 : while (true)
61 : {
62 : // Make sure we are still in the limits
63 0 : ENSURE(
64 : ((di > 0 && i0 <= i && i <= i1) || (di < 0 && i1 <= i && i <= i0) || (di == 0 && i == i0)) &&
65 : ((dj > 0 && j0 <= j && j <= j1) || (dj < 0 && j1 <= j && j <= j0) || (dj == 0 && j == j0)));
66 :
67 : // Fail if we're moving onto an impassable navcell
68 0 : bool passable = IS_PASSABLE(grid.get(i, j), passClass);
69 0 : if (passable)
70 0 : currentlyOnImpassable = false;
71 0 : else if (!currentlyOnImpassable)
72 0 : return false;
73 :
74 : // Succeed if we're at the target
75 0 : if (i == i1 && j == j1)
76 0 : return true;
77 :
78 : // If we can only move horizontally/vertically, then just move in that direction
79 : // If we are reaching the limits, we can go straight to the end
80 0 : if (di == 0 || i == i1)
81 : {
82 0 : j += dj;
83 0 : continue;
84 : }
85 0 : else if (dj == 0 || j == j1)
86 : {
87 0 : i += di;
88 0 : continue;
89 : }
90 :
91 : // Otherwise we need to check which cell to move into:
92 :
93 : // Check whether the line intersects the horizontal (top/bottom) edge of
94 : // the current navcell.
95 : // Horizontal edge is (i, j + (dj>0?1:0)) .. (i + 1, j + (dj>0?1:0))
96 : // Since we already know the line is moving from this navcell into a different
97 : // navcell, we simply need to test that the edge's endpoints are not both on the
98 : // same side of the line.
99 :
100 : // If we are crossing exactly a vertex of the grid, we will get dota or dotb equal
101 : // to 0. In that case we arbitrarily choose to move of dj.
102 : // This only works because we handle the case (i == i1 || j == j1) beforehand.
103 : // Otherwise we could go outside the j limits and never reach the final navcell.
104 :
105 0 : entity_pos_t xia = entity_pos_t::FromInt(i).Multiply(Pathfinding::NAVCELL_SIZE);
106 0 : entity_pos_t xib = entity_pos_t::FromInt(i+1).Multiply(Pathfinding::NAVCELL_SIZE);
107 0 : entity_pos_t zj = entity_pos_t::FromInt(j + (dj+1)/2).Multiply(Pathfinding::NAVCELL_SIZE);
108 :
109 0 : CFixedVector2D perp = CFixedVector2D(x1 - x0, z1 - z0).Perpendicular();
110 0 : entity_pos_t dota = (CFixedVector2D(xia, zj) - CFixedVector2D(x0, z0)).Dot(perp);
111 0 : entity_pos_t dotb = (CFixedVector2D(xib, zj) - CFixedVector2D(x0, z0)).Dot(perp);
112 :
113 : // If the horizontal edge is fully on one side of the line, so the line doesn't
114 : // intersect it, we should move across the vertical edge instead
115 0 : if ((dota < entity_pos_t::Zero() && dotb < entity_pos_t::Zero()) ||
116 0 : (dota > entity_pos_t::Zero() && dotb > entity_pos_t::Zero()))
117 0 : i += di;
118 : else
119 0 : j += dj;
120 0 : }
121 : }
122 : }
123 :
124 15 : PathfinderPassability::PathfinderPassability(pass_class_t mask, const CParamNode& node) : m_Mask(mask)
125 : {
126 15 : if (node.GetChild("MinWaterDepth").IsOk())
127 3 : m_MinDepth = node.GetChild("MinWaterDepth").ToFixed();
128 : else
129 12 : m_MinDepth = std::numeric_limits<fixed>::min();
130 :
131 15 : if (node.GetChild("MaxWaterDepth").IsOk())
132 6 : m_MaxDepth = node.GetChild("MaxWaterDepth").ToFixed();
133 : else
134 9 : m_MaxDepth = std::numeric_limits<fixed>::max();
135 :
136 15 : if (node.GetChild("MaxTerrainSlope").IsOk())
137 9 : m_MaxSlope = node.GetChild("MaxTerrainSlope").ToFixed();
138 : else
139 6 : m_MaxSlope = std::numeric_limits<fixed>::max();
140 :
141 15 : if (node.GetChild("MinShoreDistance").IsOk())
142 3 : m_MinShore = node.GetChild("MinShoreDistance").ToFixed();
143 : else
144 12 : m_MinShore = std::numeric_limits<fixed>::min();
145 :
146 15 : if (node.GetChild("MaxShoreDistance").IsOk())
147 3 : m_MaxShore = node.GetChild("MaxShoreDistance").ToFixed();
148 : else
149 12 : m_MaxShore = std::numeric_limits<fixed>::max();
150 :
151 15 : if (node.GetChild("Clearance").IsOk())
152 : {
153 0 : m_Clearance = node.GetChild("Clearance").ToFixed();
154 :
155 : /* According to Philip who designed the original doc (in docs/pathfinder.pdf),
156 : * clearance should usually be integer to ensure consistent behavior when rasterizing
157 : * the passability map.
158 : * This seems doubtful to me and my pathfinder fix makes having a clearance of 0.8 quite convenient
159 : * so I comment out this check, but leave it here for the purpose of documentation should a bug arise.
160 :
161 : if (!(m_Clearance % Pathfinding::NAVCELL_SIZE).IsZero())
162 : {
163 : // If clearance isn't an integer number of navcells then we'll
164 : // probably get weird behaviour when expanding the navcell grid
165 : // by clearance, vs expanding static obstructions by clearance
166 : LOGWARNING("Pathfinder passability class has clearance %f, should be multiple of %f",
167 : m_Clearance.ToFloat(), Pathfinding::NAVCELL_SIZE.ToFloat());
168 : }*/
169 : }
170 : else
171 15 : m_Clearance = fixed::Zero();
172 :
173 15 : if (node.GetChild("Obstructions").IsOk())
174 : {
175 0 : const std::string& obstructions = node.GetChild("Obstructions").ToString();
176 0 : if (obstructions == "none")
177 0 : m_Obstructions = NONE;
178 0 : else if (obstructions == "pathfinding")
179 0 : m_Obstructions = PATHFINDING;
180 0 : else if (obstructions == "foundation")
181 0 : m_Obstructions = FOUNDATION;
182 : else
183 : {
184 0 : LOGERROR("Invalid value for Obstructions in pathfinder.xml for pass class %d", mask);
185 0 : m_Obstructions = NONE;
186 : }
187 : }
188 : else
189 15 : m_Obstructions = NONE;
190 15 : }
|
