Debian Codegraph @

CorsixTH/Src/th_pathfind.cpp

raw
1 /*
2 Copyright (c) 2009 Peter "Corsix" Cawley
3
4 Permission is hereby granted, free of charge, to any person obtaining a copy of
5 this software and associated documentation files (the "Software"), to deal in
6 the Software without restriction, including without limitation the rights to
7 use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
8 of the Software, and to permit persons to whom the Software is furnished to do
9 so, subject to the following conditions:
10
11 The above copyright notice and this permission notice shall be included in all
12 copies or substantial portions of the Software.
13
14 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
19 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
20 SOFTWARE.
21 */
22
23 #include "th_pathfind.h"
24
25 #include "config.h"
26
27 #include <cmath>
28 #include <cstdlib>
29 #include <initializer_list>
30 #include <list>
31 #include <new>
32 #include <stdexcept>
33 #include <vector>
34
35 #include "lua.hpp"
36 #include "persist_lua.h"
37 #include "th_map.h"
38
39 abstract_pathfinder::abstract_pathfinder(pathfinder* pf)
40 : parent(pf), map(nullptr) {}
41
42 path_node* abstract_pathfinder::init(const level_map* pMap, int iStartX,
43 int iStartY) {
44 int iWidth = pMap->get_width();
45 parent->destination = nullptr;
46 parent->allocate_node_cache(iWidth, pMap->get_height());
47 path_node* pNode = &parent->nodes.at(iStartY * iWidth + iStartX);
48 pNode->prev = nullptr;
49 pNode->distance = 0;
50 pNode->guess = guess_distance(pNode);
51 pNode->visited = true;
52 parent->dirty_node_list[0] = pNode;
53 parent->dirty_node_count = 1;
54 parent->open_heap.clear();
55 return pNode;
56 }
57
58 /*! No need to check for the node being on the map edge, as the N/E/S/W
59 flags are set as to prevent travelling off the map (as well as to
60 prevent walking through walls).
61 */
62 bool abstract_pathfinder::search_neighbours(path_node* pNode,
63 map_tile_flags flags, int iWidth) {
64 if (flags.can_travel_w) {
65 if (try_node(pNode, flags, pNode - 1, travel_direction::west)) {
66 return true;
67 }
68 }
69
70 if (flags.can_travel_e) {
71 if (try_node(pNode, flags, pNode + 1, travel_direction::east)) {
72 return true;
73 }
74 }
75
76 if (flags.can_travel_n) {
77 if (try_node(pNode, flags, pNode - iWidth, travel_direction::north)) {
78 return true;
79 }
80 }
81
82 if (flags.can_travel_s) {
83 if (try_node(pNode, flags, pNode + iWidth, travel_direction::south)) {
84 return true;
85 }
86 }
87
88 return false;
89 }
90
91 void abstract_pathfinder::record_neighbour_if_passable(
92 path_node* pNode, map_tile_flags neighbour_flags, bool passable,
93 path_node* pNeighbour) {
94 if (pNeighbour->visited) {
95 return;
96 }
97 if (passable && !neighbour_flags.passable) {
98 return;
99 }
100
101 if (pNeighbour->prev == pNeighbour) {
102 pNeighbour->prev = pNode;
103 pNeighbour->distance = pNode->distance + 1;
104 pNeighbour->guess = guess_distance(pNeighbour);
105 parent->dirty_node_list[parent->dirty_node_count++] = pNeighbour;
106 parent->push_to_open_heap(pNeighbour);
107 } else if (pNode->distance + 1 < pNeighbour->distance) {
108 pNeighbour->prev = pNode;
109 pNeighbour->distance = pNode->distance + 1;
110 /* guess doesn't change, and already in the dirty list */
111 parent->open_heap_promote(pNeighbour);
112 }
113 }
114
115 int basic_pathfinder::guess_distance(path_node* pNode) {
116 // As diagonal movement is not allowed, the minimum distance between two
117 // points is the sum of the distance in X and the distance in Y.
118 return abs(pNode->x - destination_x) + abs(pNode->y - destination_y);
119 }
120
121 bool basic_pathfinder::try_node(path_node* pNode, map_tile_flags flags,
122 path_node* pNeighbour,
123 travel_direction direction) {
124 map_tile_flags neighbour_flags =
125 map->get_tile_unchecked(pNeighbour->x, pNeighbour->y)->flags;
126 record_neighbour_if_passable(pNode, neighbour_flags, flags.passable,
127 pNeighbour);
128 return false;
129 }
130
131 bool basic_pathfinder::find_path(const level_map* pMap, int iStartX,
132 int iStartY, int iEndX, int iEndY) {
133 if (pMap == nullptr) {
134 pMap = parent->default_map;
135 }
136 if (pMap == nullptr || pMap->get_tile(iEndX, iEndY) == nullptr ||
137 !pMap->get_tile_unchecked(iEndX, iEndY)->flags.passable) {
138 parent->destination = nullptr;
139 return false;
140 }
141
142 map = pMap;
143 destination_x = iEndX;
144 destination_y = iEndY;
145
146 path_node* pNode = init(pMap, iStartX, iStartY);
147 int iWidth = pMap->get_width();
148 path_node* pTarget = &parent->nodes.at(iEndY * iWidth + iEndX);
149
150 while (true) {
151 if (pNode == pTarget) {
152 parent->destination = pTarget;
153 return true;
154 }
155
156 map_tile_flags flags = pMap->get_tile_unchecked(pNode->x, pNode->y)->flags;
157 if (search_neighbours(pNode, flags, iWidth)) {
158 return true;
159 }
160
161 if (parent->open_heap.empty()) {
162 parent->destination = nullptr;
163 break;
164 } else {
165 pNode = parent->pop_from_open_heap();
166 }
167 }
168 return false;
169 }
170
171 int hospital_finder::guess_distance(path_node* pNode) { return 0; }
172
173 bool hospital_finder::try_node(path_node* pNode, map_tile_flags flags,
174 path_node* pNeighbour,
175 travel_direction direction) {
176 map_tile_flags neighbour_flags =
177 map->get_tile_unchecked(pNeighbour->x, pNeighbour->y)->flags;
178 record_neighbour_if_passable(pNode, neighbour_flags, flags.passable,
179 pNeighbour);
180 return false;
181 }
182
183 bool hospital_finder::find_path_to_hospital(const level_map* pMap, int iStartX,
184 int iStartY) {
185 if (pMap == nullptr) {
186 pMap = parent->default_map;
187 }
188 if (pMap == nullptr || pMap->get_tile(iStartX, iStartY) == nullptr ||
189 !pMap->get_tile_unchecked(iStartX, iStartY)->flags.passable) {
190 parent->destination = nullptr;
191 return false;
192 }
193
194 map = pMap;
195
196 path_node* pNode = init(pMap, iStartX, iStartY);
197 int iWidth = pMap->get_width();
198
199 while (true) {
200 pNode->visited = true;
201 map_tile_flags flags = pMap->get_tile_unchecked(pNode->x, pNode->y)->flags;
202
203 if (flags.hospital) {
204 parent->destination = pNode;
205 return true;
206 }
207
208 if (search_neighbours(pNode, flags, iWidth)) {
209 return true;
210 }
211
212 if (parent->open_heap.empty()) {
213 parent->destination = nullptr;
214 break;
215 } else {
216 pNode = parent->pop_from_open_heap();
217 }
218 }
219 return false;
220 }
221
222 int idle_tile_finder::guess_distance(path_node* pNode) { return 0; }
223
224 bool idle_tile_finder::try_node(path_node* pNode, map_tile_flags flags,
225 path_node* pNeighbour,
226 travel_direction direction) {
227 if (pNeighbour->visited) {
228 return false;
229 }
230
231 map_tile_flags neighbour_flags =
232 map->get_tile_unchecked(pNeighbour->x, pNeighbour->y)->flags;
233 /* When finding an idle tile, do not navigate through doors */
234 switch (direction) {
235 case travel_direction::north:
236 if (!flags.door_north) {
237 record_neighbour_if_passable(pNode, neighbour_flags, flags.passable,
238 pNeighbour);
239 }
240 break;
241
242 case travel_direction::east:
243 if (!neighbour_flags.door_west) {
244 record_neighbour_if_passable(pNode, neighbour_flags, flags.passable,
245 pNeighbour);
246 }
247 break;
248
249 case travel_direction::south:
250 if (!neighbour_flags.door_north) {
251 record_neighbour_if_passable(pNode, neighbour_flags, flags.passable,
252 pNeighbour);
253 }
254 break;
255
256 case travel_direction::west:
257 if (!flags.door_west) {
258 record_neighbour_if_passable(pNode, neighbour_flags, flags.passable,
259 pNeighbour);
260 }
261 break;
262 }
263
264 /* Identify the neighbour in the open list nearest to the start */
265 if (pNeighbour->prev != pNeighbour) {
266 int iDX = pNeighbour->x - start_x;
267 int iDY = pNeighbour->y - start_y;
268 double fDistance = sqrt((double)(iDX * iDX + iDY * iDY));
269 if (best_next_node == nullptr || fDistance < best_distance) {
270 best_next_node = pNeighbour;
271 best_distance = fDistance;
272 }
273 }
274 return false;
275 }
276
277 bool idle_tile_finder::find_idle_tile(const level_map* pMap, int iStartX,
278 int iStartY, int iN, int parcelId) {
279 if (pMap == nullptr) {
280 pMap = parent->default_map;
281 }
282 if (pMap == nullptr) {
283 parent->destination = nullptr;
284 return false;
285 }
286
287 start_x = iStartX;
288 start_y = iStartY;
289 map = pMap;
290
291 if (parcelId <= 0 || parcelId > pMap->get_parcel_count() ||
292 pMap->get_parcel_owner(parcelId) == 0)
293 parcelId = 0;
294
295 path_node* pNode = init(pMap, iStartX, iStartY);
296 int iWidth = pMap->get_width();
297 path_node* pPossibleResult = nullptr;
298
299 while (true) {
300 pNode->visited = true;
301
302 // Check whether pNode is a feasible destination.
303 const map_tile* node_tile = pMap->get_tile_unchecked(pNode->x, pNode->y);
304 map_tile_flags flags = node_tile->flags;
305
306 bool correct_parcel = parcelId == 0 || parcelId == node_tile->iParcelId;
307 if (!flags.do_not_idle && flags.passable && flags.hospital &&
308 correct_parcel) {
309 // Try to delay returning an idle tile until we find the Nth tile.
310 if (iN == 0) {
311 parent->destination = pNode;
312 return true;
313 } else {
314 pPossibleResult = pNode;
315 --iN;
316 }
317 }
318
319 best_next_node = nullptr;
320 best_distance = 0.0;
321
322 if (search_neighbours(pNode, flags, iWidth)) {
323 return true;
324 }
325
326 if (parent->open_heap.empty()) {
327 parent->destination = nullptr;
328 break;
329 }
330
331 if (best_next_node) {
332 // Promote the best neighbour to the front of the open list
333 // This causes sequential iN to give neighbouring results for most
334 // iN
335 best_next_node->guess = -best_next_node->distance;
336 parent->open_heap_promote(best_next_node);
337 }
338 pNode = parent->pop_from_open_heap();
339 }
340 if (pPossibleResult) {
341 parent->destination = pPossibleResult;
342 return true;
343 }
344 return false;
345 }
346
347 int object_visitor::guess_distance(path_node* pNode) { return 0; }
348
349 bool object_visitor::try_node(path_node* pNode, map_tile_flags flags,
350 path_node* pNeighbour,
351 travel_direction direction) {
352 int iObjectNumber = 0;
353 const map_tile* pMapNode =
354 map->get_tile_unchecked(pNeighbour->x, pNeighbour->y);
355 map_tile_flags neighbour_flags =
356 map->get_tile_unchecked(pNeighbour->x, pNeighbour->y)->flags;
357 for (auto thob : pMapNode->objects) {
358 if (thob == target) {
359 iObjectNumber++;
360 }
361 }
362 if (target_any_object_type) {
363 iObjectNumber = 1;
364 }
365 bool bSucces = false;
366 for (int i = 0; i < iObjectNumber; i++) {
367 /* call the given Lua function, passing four arguments: */
368 /* The x and y position of the object (Lua tile co-ords) */
369 /* The direction which was last travelled in to reach (x,y); */
370 /* 0 (north), 1 (east), 2 (south), 3 (west) */
371 /* The distance to the object from the search starting point */
372 lua_pushvalue(L, visit_function_index);
373 lua_pushinteger(L, pNeighbour->x + 1);
374 lua_pushinteger(L, pNeighbour->y + 1);
375 lua_pushinteger(L, static_cast<int>(direction));
376 lua_pushinteger(L, pNode->distance);
377 lua_call(L, 4, 1);
378 if (lua_toboolean(L, -1) != 0) {
379 bSucces = true;
380 }
381 lua_pop(L, 1);
382 }
383 if (bSucces) {
384 return true;
385 }
386
387 if (pNode->distance < max_distance) {
388 switch (direction) {
389 case travel_direction::north:
390 if (!flags.door_north) {
391 record_neighbour_if_passable(pNode, neighbour_flags, flags.passable,
392 pNeighbour);
393 }
394 break;
395
396 case travel_direction::east:
397 if (!neighbour_flags.door_west) {
398 record_neighbour_if_passable(pNode, neighbour_flags, flags.passable,
399 pNeighbour);
400 }
401 break;
402
403 case travel_direction::south:
404 if (!neighbour_flags.door_north) {
405 record_neighbour_if_passable(pNode, neighbour_flags, flags.passable,
406 pNeighbour);
407 }
408 break;
409
410 case travel_direction::west:
411 if (!flags.door_west) {
412 record_neighbour_if_passable(pNode, neighbour_flags, flags.passable,
413 pNeighbour);
414 }
415 break;
416 }
417 }
418 return false;
419 }
420
421 bool object_visitor::visit_objects(const level_map* pMap, int iStartX,
422 int iStartY, object_type eTHOB,
423 int iMaxDistance, lua_State* L,
424 int iVisitFunction, bool anyObjectType) {
425 if (pMap == nullptr) {
426 pMap = parent->default_map;
427 }
428 if (pMap == nullptr) {
429 parent->destination = nullptr;
430 return false;
431 }
432
433 this->L = L;
434 visit_function_index = iVisitFunction;
435 max_distance = iMaxDistance;
436 target_any_object_type = anyObjectType;
437 target = eTHOB;
438 map = pMap;
439
440 path_node* pNode = init(pMap, iStartX, iStartY);
441 int iWidth = pMap->get_width();
442
443 while (true) {
444 pNode->visited = true;
445 map_tile_flags flags = pMap->get_tile_unchecked(pNode->x, pNode->y)->flags;
446 if (search_neighbours(pNode, flags, iWidth)) {
447 return true;
448 }
449
450 if (parent->open_heap.empty()) {
451 parent->destination = nullptr;
452 break;
453 } else {
454 pNode = parent->pop_from_open_heap();
455 }
456 }
457 return false;
458 }
459
460 pathfinder::pathfinder()
461 : default_map(nullptr),
462 nodes({}),
463 dirty_node_list(nullptr),
464 destination(nullptr),
465 node_cache_width(0),
466 node_cache_height(0),
467 dirty_node_count(0),
468 basic_pathfinder(this),
469 hospital_finder(this),
470 idle_tile_finder(this),
471 object_visitor(this) {}
472
473 pathfinder::~pathfinder() { delete[] dirty_node_list; }
474
475 void pathfinder::set_default_map(const level_map* pMap) { default_map = pMap; }
476
477 void pathfinder::allocate_node_cache(int iWidth, int iHeight) {
478 if (node_cache_width != iWidth || node_cache_height != iHeight) {
479 nodes = std::vector<path_node>(iWidth * iHeight);
480 for (int iY = 0; iY < iHeight; ++iY) {
481 for (int iX = 0; iX < iWidth; ++iX) {
482 path_node& node = nodes[iY * iWidth + iX];
483 node.prev = &node;
484 node.x = iX;
485 node.y = iY;
486 node.visited = false;
487 // Other fields are undefined as the node is not part of a
488 // path, and thus can be left uninitialised.
489 }
490 }
491 delete[] dirty_node_list;
492 dirty_node_list = new path_node*[iWidth * iHeight];
493 node_cache_width = iWidth;
494 node_cache_height = iHeight;
495 } else {
496 for (int i = 0; i < dirty_node_count; ++i) {
497 dirty_node_list[i]->prev = dirty_node_list[i];
498 dirty_node_list[i]->visited = false;
499 // Other fields are undefined as the node is not part of a path,
500 // and thus can keep their old values.
501 }
502 }
503 dirty_node_count = 0;
504 }
505
506 int pathfinder::get_path_length() const {
507 if (destination != nullptr) {
508 return destination->distance;
509 } else {
510 return -1;
511 }
512 }
513
514 bool pathfinder::get_path_end(int* pX, int* pY) const {
515 if (destination == nullptr) {
516 if (pX) {
517 *pX = -1;
518 }
519 if (pY) {
520 *pY = -1;
521 }
522 return false;
523 }
524 if (pX) {
525 *pX = destination->x;
526 }
527 if (pY) {
528 *pY = destination->y;
529 }
530 return true;
531 }
532
533 void pathfinder::push_result(lua_State* L) const {
534 lua_checkstack(L, 3);
535
536 if (destination == nullptr) {
537 lua_pushnil(L);
538 lua_pushliteral(L, "no path");
539 return;
540 }
541
542 int iLength = destination->distance;
543 lua_createtable(L, iLength + 1, 0);
544 lua_createtable(L, iLength + 1, 0);
545
546 for (const path_node* pNode = destination; pNode; pNode = pNode->prev) {
547 lua_pushinteger(L, pNode->x + 1);
548 lua_rawseti(L, -3, pNode->distance + 1);
549 lua_pushinteger(L, pNode->y + 1);
550 lua_rawseti(L, -2, pNode->distance + 1);
551 }
552 }
553
554 void pathfinder::push_to_open_heap(path_node* pNode) {
555 pNode->open_idx = open_heap.size();
556 open_heap.push_back(pNode);
557 open_heap_promote(pNode);
558 }
559
560 void pathfinder::open_heap_promote(path_node* pNode) {
561 size_t i = pNode->open_idx;
562 if (open_heap.at(i) != pNode) {
563 throw std::runtime_error(
564 "Invalid open_idx on node. Does not point to itself in the open heap");
565 }
566
567 while (i > 0) {
568 size_t parent = (i - 1) / 2;
569 path_node* pParent = open_heap[parent];
570 if (pParent->value() <= pNode->value()) {
571 break;
572 }
573 pParent->open_idx = i;
574 open_heap[i] = pParent;
575 open_heap[parent] = pNode;
576 i = parent;
577 }
578 pNode->open_idx = i;
579 }
580
581 path_node* pathfinder::pop_from_open_heap() {
582 path_node* pResult = open_heap[0];
583 path_node* pNode = open_heap.back();
584 open_heap.pop_back();
585
586 if (open_heap.empty()) {
587 return pResult;
588 }
589
590 open_heap[0] = pNode;
591 int i = 0;
592 int min = 0;
593 int left = i * 2 + 1;
594 const int value = pNode->value();
595 while (left < open_heap.size()) {
596 min = i;
597 const int right = (i + 1) * 2;
598 int minvalue = value;
599 path_node* pSwap = nullptr;
600 path_node* pTest = open_heap[left];
601 if (pTest->value() < minvalue) {
602 min = left;
603 minvalue = pTest->value();
604 pSwap = pTest;
605 }
606 if (right < open_heap.size()) {
607 pTest = open_heap[right];
608 if (pTest->value() < minvalue) {
609 min = right;
610 pSwap = pTest;
611 }
612 }
613 if (min == i) {
614 break;
615 }
616
617 pSwap->open_idx = i;
618 open_heap[i] = pSwap;
619 open_heap[min] = pNode;
620 i = min;
621 left = i * 2 + 1;
622 }
623 pNode->open_idx = min;
624 return pResult;
625 }
626
627 void pathfinder::persist(lua_persist_writer* pWriter) const {
628 if (destination == nullptr) {
629 pWriter->write_uint(0);
630 return;
631 }
632 pWriter->write_uint(get_path_length() + 1);
633 pWriter->write_uint(node_cache_width);
634 pWriter->write_uint(node_cache_height);
635 for (const path_node* pNode = destination; pNode; pNode = pNode->prev) {
636 pWriter->write_uint(pNode->x);
637 pWriter->write_uint(pNode->y);
638 }
639 }
640
641 void pathfinder::depersist(lua_persist_reader* pReader) {
642 int iLength;
643 if (!pReader->read_uint(iLength)) {
644 return;
645 }
646 if (iLength == 0) {
647 return;
648 }
649 int iWidth, iHeight;
650 if (!pReader->read_uint(iWidth) || !pReader->read_uint(iHeight)) {
651 return;
652 }
653 allocate_node_cache(iWidth, iHeight);
654 int iX, iY;
655 if (!pReader->read_uint(iX) || !pReader->read_uint(iY)) {
656 return;
657 }
658 path_node* pNode = &nodes[iY * iWidth + iX];
659 destination = pNode;
660 for (int i = 0; i <= iLength - 2; ++i) {
661 if (!pReader->read_uint(iX) || !pReader->read_uint(iY)) {
662 return;
663 }
664 path_node* pPrevNode = &nodes[iY * iWidth + iX];
665 pNode->distance = iLength - 1 - i;
666 pNode->prev = pPrevNode;
667 dirty_node_list[dirty_node_count++] = pNode;
668 pNode = pPrevNode;
669 }
670 pNode->distance = 0;
671 pNode->prev = nullptr;
672 dirty_node_list[dirty_node_count++] = pNode;
673 }