1 /* ScummVM - Graphic Adventure Engine
2 *
3 * ScummVM is the legal property of its developers, whose names
4 * are too numerous to list here. Please refer to the COPYRIGHT
5 * file distributed with this source distribution.
6 *
7 * This program is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU General Public License
9 * as published by the Free Software Foundation; either version 2
10 * of the License, or (at your option) any later version.
11 *
12 * This program is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with this program; if not, write to the Free Software
19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
20 *
21 */
22
23 /*
24 * This code is based on Broken Sword 2.5 engine
25 *
26 * Copyright (c) Malte Thiesen, Daniel Queteschiner and Michael Elsdoerfer
27 *
28 * Licensed under GNU GPL v2
29 *
30 */
31
32 #include "sword25/kernel/kernel.h"
33 #include "sword25/kernel/inputpersistenceblock.h"
34 #include "sword25/kernel/outputpersistenceblock.h"
35 #include "sword25/math/walkregion.h"
36 #include "sword25/math/line.h"
37
38 namespace Sword25 {
39
40 static const int Infinity = 0x7fffffff;
41
WalkRegion()42 WalkRegion::WalkRegion() {
43 _type = RT_WALKREGION;
44 }
45
WalkRegion(InputPersistenceBlock & reader,uint handle)46 WalkRegion::WalkRegion(InputPersistenceBlock &reader, uint handle) :
47 Region(reader, handle) {
48 _type = RT_WALKREGION;
49 unpersist(reader);
50 }
51
~WalkRegion()52 WalkRegion::~WalkRegion() {
53 }
54
init(const Polygon & contour,const Common::Array<Polygon> * pHoles)55 bool WalkRegion::init(const Polygon &contour, const Common::Array<Polygon> *pHoles) {
56 // Default initialisation of the region
57 if (!Region::init(contour, pHoles)) return false;
58
59 // Prepare structures for pathfinding
60 initNodeVector();
61 computeVisibilityMatrix();
62
63 // Signal success
64 return true;
65 }
66
queryPath(Vertex startPoint,Vertex endPoint,BS_Path & path)67 bool WalkRegion::queryPath(Vertex startPoint, Vertex endPoint, BS_Path &path) {
68 assert(path.empty());
69
70 // If the start and finish are identical, no path can be found trivially
71 if (startPoint == endPoint)
72 return true;
73
74 // Ensure that the start and finish are valid and find new start points if either
75 // are outside the polygon
76 if (!checkAndPrepareStartAndEnd(startPoint, endPoint)) return false;
77
78 // If between the start and point a line of sight exists, then it can be returned.
79 if (isLineOfSight(startPoint, endPoint)) {
80 path.push_back(startPoint);
81 path.push_back(endPoint);
82 return true;
83 }
84
85 return findPath(startPoint, endPoint, path);
86 }
87
88 struct DijkstraNode {
89 typedef Common::Array<DijkstraNode> Container;
90 typedef Container::iterator Iter;
91 typedef Container::const_iterator ConstIter;
92
DijkstraNodeSword25::DijkstraNode93 DijkstraNode() : parentIter(), cost(Infinity), chosen(false) {}
94 ConstIter parentIter;
95 int cost;
96 bool chosen;
97 };
98
initDijkstraNodes(DijkstraNode::Container & dijkstraNodes,const Region & region,const Vertex & start,const Common::Array<Vertex> & nodes)99 static void initDijkstraNodes(DijkstraNode::Container &dijkstraNodes, const Region ®ion,
100 const Vertex &start, const Common::Array<Vertex> &nodes) {
101 // Allocate sufficient space in the array
102 dijkstraNodes.resize(nodes.size());
103
104 // Initialize all the nodes which are visible from the starting node
105 DijkstraNode::Iter dijkstraIter = dijkstraNodes.begin();
106 for (Common::Array<Vertex>::const_iterator nodesIter = nodes.begin();
107 nodesIter != nodes.end(); nodesIter++, dijkstraIter++) {
108 (*dijkstraIter).parentIter = dijkstraNodes.end();
109 if (region.isLineOfSight(*nodesIter, start))(*dijkstraIter).cost = (*nodesIter).distance(start);
110 }
111 assert(dijkstraIter == dijkstraNodes.end());
112 }
113
chooseClosestNode(DijkstraNode::Container & nodes)114 static DijkstraNode::Iter chooseClosestNode(DijkstraNode::Container &nodes) {
115 DijkstraNode::Iter closestNodeInter = nodes.end();
116 int minCost = Infinity;
117
118 for (DijkstraNode::Iter iter = nodes.begin(); iter != nodes.end(); iter++) {
119 if (!(*iter).chosen && (*iter).cost < minCost) {
120 minCost = (*iter).cost;
121 closestNodeInter = iter;
122 }
123 }
124
125 return closestNodeInter;
126 }
127
relaxNodes(DijkstraNode::Container & nodes,const Common::Array<Common::Array<int>> & visibilityMatrix,const DijkstraNode::ConstIter & curNodeIter)128 static void relaxNodes(DijkstraNode::Container &nodes,
129 const Common::Array< Common::Array<int> > &visibilityMatrix,
130 const DijkstraNode::ConstIter &curNodeIter) {
131 // All the successors of the current node that have not been chosen will be
132 // inserted into the boundary node list, and the cost will be updated if
133 // a shorter path has been found to them.
134
135 int curNodeIndex = curNodeIter - nodes.begin();
136 for (uint i = 0; i < nodes.size(); i++) {
137 int cost = visibilityMatrix[curNodeIndex][i];
138 if (!nodes[i].chosen && cost != Infinity) {
139 int totalCost = (*curNodeIter).cost + cost;
140 if (totalCost < nodes[i].cost) {
141 nodes[i].parentIter = curNodeIter;
142 nodes[i].cost = totalCost;
143 }
144 }
145 }
146 }
147
relaxEndPoint(const Vertex & curNodePos,const DijkstraNode::ConstIter & curNodeIter,const Vertex & endPointPos,DijkstraNode & endPoint,const Region & region)148 static void relaxEndPoint(const Vertex &curNodePos,
149 const DijkstraNode::ConstIter &curNodeIter,
150 const Vertex &endPointPos,
151 DijkstraNode &endPoint,
152 const Region ®ion) {
153 if (region.isLineOfSight(curNodePos, endPointPos)) {
154 int totalCost = (*curNodeIter).cost + curNodePos.distance(endPointPos);
155 if (totalCost < endPoint.cost) {
156 endPoint.parentIter = curNodeIter;
157 endPoint.cost = totalCost;
158 }
159 }
160 }
161
162 template<class T>
reverseArray(Common::Array<T> & arr)163 void reverseArray(Common::Array<T> &arr) {
164 const uint size = arr.size();
165 if (size < 2)
166 return;
167
168 for (uint i = 0; i <= (size / 2 - 1); ++i) {
169 SWAP(arr[i], arr[size - i - 1]);
170 }
171 }
172
findPath(const Vertex & start,const Vertex & end,BS_Path & path) const173 bool WalkRegion::findPath(const Vertex &start, const Vertex &end, BS_Path &path) const {
174 // This is an implementation of Dijkstra's algorithm
175
176 // Initialize edge node list
177 DijkstraNode::Container dijkstraNodes;
178 initDijkstraNodes(dijkstraNodes, *this, start, _nodes);
179
180 // The end point is treated separately, since it does not exist in the visibility graph
181 DijkstraNode endPoint;
182
183 // Since a node is selected each round from the node list, and can never be selected again
184 // after that, the maximum number of loop iterations is limited by the number of nodes
185 for (uint i = 0; i < _nodes.size(); i++) {
186 // Determine the nearest edge node in the node list
187 DijkstraNode::Iter nodeInter = chooseClosestNode(dijkstraNodes);
188
189 // If no free nodes are absent from the edge node list, there is no path from start
190 // to end node. This case should never occur, since the number of loop passes is
191 // limited, but etter safe than sorry
192 if (nodeInter == dijkstraNodes.end())
193 return false;
194
195 // If the destination point is closer than the point cost, scan can stop
196 (*nodeInter).chosen = true;
197 if (endPoint.cost <= (*nodeInter).cost) {
198 // Insert the end point in the list
199 path.push_back(end);
200
201 // The list is done in reverse order and inserted into the path
202 DijkstraNode::ConstIter curNode = endPoint.parentIter;
203 while (curNode != dijkstraNodes.end()) {
204 assert((*curNode).chosen);
205 path.push_back(_nodes[curNode - dijkstraNodes.begin()]);
206 curNode = (*curNode).parentIter;
207 }
208
209 // The starting point is inserted into the path
210 path.push_back(start);
211
212 // The nodes of the path must be untwisted, as they were extracted in reverse order.
213 // This step could be saved if the path from end to the beginning was desired
214 reverseArray<Vertex>(path);
215
216 return true;
217 }
218
219 // Relaxation step for nodes of the graph, and perform the end nodes
220 relaxNodes(dijkstraNodes, _visibilityMatrix, nodeInter);
221 relaxEndPoint(_nodes[nodeInter - dijkstraNodes.begin()], nodeInter, end, endPoint, *this);
222 }
223
224 // If the loop has been completely run through, all the nodes have been chosen, and still
225 // no path was found. There is therefore no path available
226 return false;
227 }
228
initNodeVector()229 void WalkRegion::initNodeVector() {
230 // Empty the Node list
231 _nodes.clear();
232
233 // Determine the number of nodes
234 int nodeCount = 0;
235 {
236 for (uint i = 0; i < _polygons.size(); i++)
237 nodeCount += _polygons[i].vertexCount;
238 }
239
240 // Knoten-Vector füllen
241 _nodes.reserve(nodeCount);
242 {
243 for (uint j = 0; j < _polygons.size(); j++)
244 for (int i = 0; i < _polygons[j].vertexCount; i++)
245 _nodes.push_back(_polygons[j].vertices[i]);
246 }
247 }
248
computeVisibilityMatrix()249 void WalkRegion::computeVisibilityMatrix() {
250 // Initialize visibility matrix
251 _visibilityMatrix = Common::Array< Common::Array <int> >();
252 for (uint idx = 0; idx < _nodes.size(); ++idx) {
253 Common::Array<int> arr;
254 for (uint idx2 = 0; idx2 < _nodes.size(); ++idx2)
255 arr.push_back(Infinity);
256
257 _visibilityMatrix.push_back(arr);
258 }
259
260 // Calculate visibility been vertecies
261 for (uint j = 0; j < _nodes.size(); ++j) {
262 for (uint i = j; i < _nodes.size(); ++i) {
263 if (isLineOfSight(_nodes[i], _nodes[j])) {
264 // There is a line of sight, so save the distance between the two
265 int distance = _nodes[i].distance(_nodes[j]);
266 _visibilityMatrix[i][j] = distance;
267 _visibilityMatrix[j][i] = distance;
268 } else {
269 // There is no line of sight, so save Infinity as the distance
270 _visibilityMatrix[i][j] = Infinity;
271 _visibilityMatrix[j][i] = Infinity;
272 }
273 }
274 }
275 }
276
checkAndPrepareStartAndEnd(Vertex & start,Vertex & end) const277 bool WalkRegion::checkAndPrepareStartAndEnd(Vertex &start, Vertex &end) const {
278 if (!isPointInRegion(start)) {
279 Vertex newStart = findClosestRegionPoint(start);
280
281 // Check to make sure the point is really in the region. If not, stop with an error
282 if (!isPointInRegion(newStart)) {
283 error("Constructed startpoint ((%d,%d) from (%d,%d)) is not inside the region.",
284 newStart.x, newStart.y,
285 start.x, start.y);
286 return false;
287 }
288
289 start = newStart;
290 }
291
292 // If the destination is outside the region, a point is determined that is within the region,
293 // and that is used as an endpoint instead
294 if (!isPointInRegion(end)) {
295 Vertex newEnd = findClosestRegionPoint(end);
296
297 // Make sure that the determined point is really within the region
298 if (!isPointInRegion(newEnd)) {
299 error("Constructed endpoint ((%d,%d) from (%d,%d)) is not inside the region.",
300 newEnd.x, newEnd.y,
301 end.x, end.y);
302 return false;
303 }
304
305 end = newEnd;
306 }
307
308 // Signal success
309 return true;
310 }
311
setPos(int x,int y)312 void WalkRegion::setPos(int x, int y) {
313 // Calculate the difference between old and new position
314 Vertex Delta(x - _position.x, y - _position.y);
315
316 // Move all the nodes
317 for (uint i = 0; i < _nodes.size(); i++)
318 _nodes[i] += Delta;
319
320 // Move regions
321 Region::setPos(x, y);
322 }
323
persist(OutputPersistenceBlock & writer)324 bool WalkRegion::persist(OutputPersistenceBlock &writer) {
325 bool result = true;
326
327 // Persist the parent region
328 result &= Region::persist(writer);
329
330 // Persist the nodes
331 writer.write((uint32)_nodes.size());
332 Common::Array<Vertex>::const_iterator it = _nodes.begin();
333 while (it != _nodes.end()) {
334 writer.write((int32)it->x);
335 writer.write((int32)it->y);
336 ++it;
337 }
338
339 // Persist the visibility matrix
340 writer.write((uint32)_visibilityMatrix.size());
341 Common::Array< Common::Array<int> >::const_iterator rowIter = _visibilityMatrix.begin();
342 while (rowIter != _visibilityMatrix.end()) {
343 writer.write((uint32)rowIter->size());
344 Common::Array<int>::const_iterator colIter = rowIter->begin();
345 while (colIter != rowIter->end()) {
346 writer.write((int32)*colIter);
347 ++colIter;
348 }
349
350 ++rowIter;
351 }
352
353 return result;
354 }
355
unpersist(InputPersistenceBlock & reader)356 bool WalkRegion::unpersist(InputPersistenceBlock &reader) {
357 bool result = true;
358
359 // The parent object was already loaded in the constructor of BS_Region, so at
360 // this point only the additional data from BS_WalkRegion needs to be loaded
361
362 // Node load
363 uint32 nodeCount;
364 reader.read(nodeCount);
365 _nodes.clear();
366 _nodes.resize(nodeCount);
367 Common::Array<Vertex>::iterator it = _nodes.begin();
368 while (it != _nodes.end()) {
369 reader.read(it->x);
370 reader.read(it->y);
371 ++it;
372 }
373
374 // Visibility matrix load
375 uint32 rowCount;
376 reader.read(rowCount);
377 _visibilityMatrix.clear();
378 _visibilityMatrix.resize(rowCount);
379 Common::Array< Common::Array<int> >::iterator rowIter = _visibilityMatrix.begin();
380 while (rowIter != _visibilityMatrix.end()) {
381 uint32 colCount;
382 reader.read(colCount);
383 rowIter->resize(colCount);
384 Common::Array<int>::iterator colIter = rowIter->begin();
385 while (colIter != rowIter->end()) {
386 int32 t;
387 reader.read(t);
388 *colIter = t;
389 ++colIter;
390 }
391
392 ++rowIter;
393 }
394
395 return result && reader.isGood();
396 }
397
398 } // End of namespace Sword25
399