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