1 /* Copyright (C) 2015 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 "Rasterize.h"
21
22 #include "simulation2/helpers/Geometry.h"
23
RasterizeRectWithClearance(Spans & spans,const ICmpObstructionManager::ObstructionSquare & shape,entity_pos_t clearance,entity_pos_t cellSize)24 void SimRasterize::RasterizeRectWithClearance(Spans& spans,
25 const ICmpObstructionManager::ObstructionSquare& shape,
26 entity_pos_t clearance, entity_pos_t cellSize)
27 {
28 // A long-standing issue with the pathfinding has been that the long-range one
29 // uses a AA navcell grid, while the short-range uses an accurate vector representation.
30 // This means we could get paths accepted by one but not both pathfinders.
31 // Since the new pathfinder, the short-range pathfinder's representation was usually
32 // encompassing the rasterisation of the long-range one for a building.
33 // This means that we could never get quite as close as the long-range pathfinder wanted.
34 // This could mean units tried going through impassable paths.
35 // To fix this, we need to make sure that the short-range pathfinder is always mostly
36 // included in the rasterisation. The easiest way is to rasterise more, thus this variable
37 // Since this is a very complicated subject, check out logs on 31/10/2015 for more detailled info.
38 // or ask wraitii about it.
39 // If the short-range pathfinder is sufficiently changed, this could become unnecessary and thus removed.
40 // A side effect is that the basic clearance has been set to 0.8, so removing this constant should be done
41 // in parallel with setting clearance back to 1 for the default passability class (though this isn't strictly necessary).
42 // Also: the code detecting foundation obstruction in CcmpObstructionManager had to be changed similarly.
43 entity_pos_t rasterClearance = clearance + Pathfinding::CLEARANCE_EXTENSION_RADIUS;
44
45 // Get the bounds of cells that might possibly be within the shape
46 // (We'll then test each of those cells more precisely)
47 CFixedVector2D shapeHalfSize(CFixedVector2D(shape.hw, shape.hh));
48 CFixedVector2D halfSize(shape.hw + rasterClearance, shape.hh + rasterClearance);
49 CFixedVector2D halfBound = Geometry::GetHalfBoundingBox(shape.u, shape.v, halfSize);
50 i16 i0 = ((shape.x - halfBound.X) / cellSize).ToInt_RoundToNegInfinity();
51 i16 j0 = ((shape.z - halfBound.Y) / cellSize).ToInt_RoundToNegInfinity();
52 i16 i1 = ((shape.x + halfBound.X) / cellSize).ToInt_RoundToInfinity();
53 i16 j1 = ((shape.z + halfBound.Y) / cellSize).ToInt_RoundToInfinity();
54
55 if (j1 <= j0)
56 return; // empty bounds - this shouldn't happen
57
58
59 rasterClearance = rasterClearance.Multiply(rasterClearance);
60
61 spans.reserve(j1 - j0);
62
63 for (i16 j = j0; j < j1; ++j)
64 {
65 // Find the min/max range of cells that are strictly inside the square+rasterClearance.
66 // (Since the square+rasterClearance is a convex shape, we can just test each
67 // corner of each cell is inside the shape.)
68 // When looping on i, if the previous cell was inside, no need to check again the left corners.
69 // and we can stop the loop when exiting the shape.
70 // Futhermore if one of the right corners of a cell is outside, no need to check the following cell
71 i16 spanI0 = std::numeric_limits<i16>::max();
72 i16 spanI1 = std::numeric_limits<i16>::min();
73 bool previousInside = false;
74 bool skipNextCell = false;
75 for (i16 i = i0; i < i1; ++i)
76 {
77 if (skipNextCell)
78 {
79 skipNextCell = false;
80 continue;
81 }
82
83 if (Geometry::DistanceToSquareSquared(CFixedVector2D(cellSize*(i+1)-shape.x, cellSize*j-shape.z),
84 shape.u, shape.v, shapeHalfSize, true) > rasterClearance)
85 {
86 if (previousInside)
87 break;
88 skipNextCell = true;
89 continue;
90 }
91
92 if (Geometry::DistanceToSquareSquared(CFixedVector2D(cellSize*(i+1)-shape.x, cellSize*(j+1)-shape.z),
93 shape.u, shape.v, shapeHalfSize, true) > rasterClearance)
94 {
95 if (previousInside)
96 break;
97 skipNextCell = true;
98 continue;
99 }
100
101 if (!previousInside)
102 {
103 if (Geometry::DistanceToSquareSquared(CFixedVector2D(cellSize*i-shape.x, cellSize*j-shape.z),
104 shape.u, shape.v, shapeHalfSize, true) > rasterClearance)
105 continue;
106
107 if (Geometry::DistanceToSquareSquared(CFixedVector2D(cellSize*i-shape.x, cellSize*(j+1)-shape.z),
108 shape.u, shape.v, shapeHalfSize, true) > rasterClearance)
109 continue;
110
111 previousInside = true;
112 spanI0 = i;
113 }
114
115 spanI1 = i+1;
116 }
117
118 // Add non-empty spans onto the list
119 if (spanI0 < spanI1)
120 {
121 Span span = { spanI0, spanI1, j };
122 spans.push_back(span);
123 }
124 }
125 }
126