1 /*-------------------------------------------------------------------------------
2
3 BARONY
4 File: paths.cpp
5 Desc: contains functions to generate paths through a level
6
7 Copyright 2013-2016 (c) Turning Wheel LLC, all rights reserved.
8 See LICENSE for details.
9
10 -------------------------------------------------------------------------------*/
11
12 #include "main.hpp"
13 #include "game.hpp"
14 #include "stat.hpp"
15 #include "entity.hpp"
16 #include "monster.hpp"
17 #include "collision.hpp"
18 #include "paths.hpp"
19 #include "items.hpp"
20 #include "net.hpp"
21 #include "magic/magic.hpp"
22
23 int* pathMapFlying = NULL;
24 int* pathMapGrounded = NULL;
25 int pathMapZone = 1;
26
27 #define STRAIGHTCOST 10
28 #define DIAGONALCOST 14
29
30 /*-------------------------------------------------------------------------------
31
32 heuristic
33
34 Uses the Manhattan Method to calculate the path heuristic from x1, y1
35 to x2, y2
36
37 -------------------------------------------------------------------------------*/
38
heuristic(int x1,int y1,int x2,int y2)39 Uint32 heuristic(int x1, int y1, int x2, int y2)
40 {
41 Uint32 h;
42 h = (abs(x2 - x1) + abs(y2 - y1)) * STRAIGHTCOST;
43 return h;
44 }
45
46 /*-------------------------------------------------------------------------------
47
48 heapAdd
49
50 Adds a pathnode to the heap
51
52 -------------------------------------------------------------------------------*/
53
heapAdd(pathnode_t ** heap,pathnode_t * pathnode,long * length)54 pathnode_t** heapAdd(pathnode_t** heap, pathnode_t* pathnode, long* length)
55 {
56 long x;
57
58 *length += 1;
59 heap[*length] = pathnode;
60 for ( x = *length; x > 1; x = x >> 1 )
61 {
62 if ( heap[x >> 1]->g + heap[x >> 1]->h > pathnode->g + pathnode->h )
63 {
64 pathnode = heap[x];
65 heap[x] = heap[x >> 1];
66 heap[x >> 1] = pathnode;
67 }
68 else
69 {
70 heap[x] = pathnode;
71 break;
72 }
73 }
74
75 return heap;
76 }
77
78 /*-------------------------------------------------------------------------------
79
80 heapRemove
81
82 Removes a pathnode from the heap
83
84 -------------------------------------------------------------------------------*/
85
heapRemove(pathnode_t ** heap,long * length)86 pathnode_t** heapRemove(pathnode_t** heap, long* length)
87 {
88 long u, v = 1;
89 pathnode_t* pathnode;
90
91 heap[1] = heap[*length];
92 *length -= 1;
93 while ( 1 )
94 {
95 u = v;
96
97 if ( (u << 1) + 1 <= *length )
98 {
99 if ( heap[u << 1]->g + heap[u << 1]->h < heap[u]->g + heap[u]->h )
100 {
101 v = u << 1;
102 }
103 if ( heap[(u << 1) + 1]->g + heap[(u << 1) + 1]->h < heap[v]->g + heap[v]->h )
104 {
105 v = (u << 1) + 1;
106 }
107 }
108 else if ( u << 1 <= *length )
109 {
110 if ( heap[u << 1]->g + heap[u << 1]->h < heap[u]->g + heap[u]->h )
111 {
112 v = u << 1;
113 }
114 }
115
116 if ( u != v )
117 {
118 pathnode = heap[u];
119 heap[u] = heap[v];
120 heap[v] = pathnode;
121 }
122 else
123 {
124 break;
125 }
126 }
127
128 return heap;
129 }
130
131 /*-------------------------------------------------------------------------------
132
133 pathCheckObstacle
134
135 -------------------------------------------------------------------------------*/
136
pathCheckObstacle(long x,long y,Entity * my,Entity * target)137 int pathCheckObstacle(long x, long y, Entity* my, Entity* target)
138 {
139 int u = std::min(std::max<unsigned int>(0, x >> 4), map.width);
140 int v = std::min(std::max<unsigned int>(0, y >> 4), map.height); //TODO: Why are int and long int being compared?
141 int index = v * MAPLAYERS + u * MAPLAYERS * map.height;
142
143 if ( map.tiles[OBSTACLELAYER + index] || !map.tiles[index] || lavatiles[map.tiles[index]] )
144 {
145 return 1;
146 }
147
148 node_t* node;
149 std::vector<list_t*> entLists = TileEntityList.getEntitiesWithinRadiusAroundEntity(my, 0);
150 for ( std::vector<list_t*>::iterator it = entLists.begin(); it != entLists.end(); ++it )
151 {
152 list_t* currentList = *it;
153 for ( node = currentList->first; node != nullptr; node = node->next )
154 {
155 Entity* entity = (Entity*)node->element;
156 if ( entity->sprite == 14
157 || entity->sprite == 15
158 || entity->sprite == 19
159 || entity->sprite == 20
160 || entity->sprite == 39
161 || entity->sprite == 44 )
162 {
163 if ( (int)floor(entity->x / 16) == u && (int)floor(entity->y / 16) == v )
164 {
165 return 1;
166 }
167 }
168 }
169 }
170
171 return 0;
172 }
173
174 /*-------------------------------------------------------------------------------
175
176 generatePath
177
178 generates a path through the level using the A* pathfinding algorithm.
179 Takes a starting point and destination in map coordinates, and returns
180 a list of pathnodes which lead from the starting point to the destination.
181 If no path connecting the two positions is possible, generatePath returns
182 NULL.
183
184 -------------------------------------------------------------------------------*/
185
generatePath(int x1,int y1,int x2,int y2,Entity * my,Entity * target,bool lavaIsPassable)186 list_t* generatePath(int x1, int y1, int x2, int y2, Entity* my, Entity* target, bool lavaIsPassable)
187 {
188 if (!my)
189 {
190 return NULL;
191 }
192
193 pathnode_t* pathnode, *childnode, *parent;
194 list_t* openList, *closedList;
195 list_t* path;
196 node_t* node;
197 bool alreadyadded;
198 Sint32 x, y, z, h, g;
199 pathnode_t** binaryheap;
200 long heaplength = 0;
201 node_t* entityNode = NULL;
202
203 int* pathMap = (int*) calloc(map.width * map.height, sizeof(int));
204
205 bool levitating = false;
206
207 x1 = std::min<unsigned int>(std::max(0, x1), map.width - 1);
208 y1 = std::min<unsigned int>(std::max(0, y1), map.height - 1);
209 x2 = std::min<unsigned int>(std::max(0, x2), map.width - 1);
210 y2 = std::min<unsigned int>(std::max(0, y2), map.height - 1); //TODO: Why are int and unsigned int being compared?
211
212 // get levitation status
213 Stat* stats = my->getStats();
214 if ( stats )
215 {
216 levitating = isLevitating(stats);
217 }
218 if ( my )
219 {
220 if ( my->behavior == &actItem || my->behavior == &actArrowTrap || my->behavior == &actBoulderTrap )
221 {
222 levitating = true;
223 }
224 }
225
226 // for boulders falling and checking if a player can reach the ladder.
227 bool playerCheckPathToExit = (my && my->behavior == &actPlayer
228 && target && (target->behavior == &actLadder || target->behavior == &actPortal));
229 bool playerCheckAchievement = (my && my->behavior == &actPlayer
230 && target && (target->behavior == &actBomb || target->behavior == &actPlayerLimb || target->behavior == &actItem || target->behavior == &actSwitch));
231
232 if ( !loading )
233 {
234 if ( levitating || playerCheckPathToExit )
235 {
236 memcpy(pathMap, pathMapFlying, map.width * map.height * sizeof(int));
237 }
238 else
239 {
240 memcpy(pathMap, pathMapGrounded, map.width * map.height * sizeof(int));
241 }
242 }
243
244 int myPathMap = pathMap[y1 + x1 * map.height];
245 if ( !loading )
246 {
247 if ( !myPathMap || myPathMap != pathMap[y2 + x2 * map.height] || !pathMap[y2 + x2 * map.height] || (x1 == x2 && y1 == y2) )
248 {
249 free(pathMap);
250 return NULL;
251 }
252 }
253
254 // for boulders falling and checking if a player can reach the ladder.
255 // if we're not levitating, we use the flying path map (for water/lava) and here we remove the empty air tiles from the pathMap.
256 if ( playerCheckPathToExit && !levitating )
257 {
258 for ( int y = 0; y < map.height; ++y )
259 {
260 for ( int x = 0; x < map.width; ++x )
261 {
262 if ( !map.tiles[y * MAPLAYERS + x * MAPLAYERS * map.height] )
263 {
264 pathMap[y + x * map.height] = 0;
265 }
266 }
267 }
268 }
269
270 Uint32 standingOnTrap = 0; // 0 - not checked.
271
272 for ( entityNode = map.entities->first; entityNode != nullptr; entityNode = entityNode->next )
273 {
274 Entity* entity = (Entity*)entityNode->element;
275 if ( entity->flags[PASSABLE] )
276 {
277 if ( entity->behavior == &actSpearTrap
278 && (my->getRace() == HUMAN || my->monsterAllyGetPlayerLeader() ) )
279 {
280 // humans/followers know better than that!
281
282 // unless they're standing on a trap...
283 if ( standingOnTrap == 0 )
284 {
285 std::vector<list_t*> entLists = TileEntityList.getEntitiesWithinRadiusAroundEntity(my, 0);
286 for ( std::vector<list_t*>::iterator it = entLists.begin(); it != entLists.end() && !standingOnTrap; ++it )
287 {
288 list_t* currentList = *it;
289 node_t* node;
290 if ( currentList )
291 {
292 for ( node = currentList->first; node != nullptr && !standingOnTrap; node = node->next )
293 {
294 Entity* entity = (Entity*)node->element;
295 if ( entity && entity->behavior == &actSpearTrap )
296 {
297 standingOnTrap = 1; // 1 - standing on the trap.
298 }
299 }
300 }
301 }
302 if ( standingOnTrap == 0 )
303 {
304 standingOnTrap = 2; // 2 - have run the check but failed.
305 }
306 }
307 if ( standingOnTrap == 1 )
308 {
309 continue;
310 }
311 }
312 else
313 {
314 continue;
315 }
316 }
317 if ( entity->behavior == &actDoorFrame || entity->behavior == &actDoor || entity->behavior == &actMagicMissile )
318 {
319 continue;
320 }
321 if ( playerCheckPathToExit && entity->behavior == &actGate )
322 {
323 continue;
324 }
325 if ( entity == target || entity == my )
326 {
327 continue;
328 }
329 if ( entity->behavior == &actMonster && !my->checkEnemy(entity) )
330 {
331 continue;
332 }
333 if ( entity->behavior == &actPlayer && my->monsterAllyIndex >= 0
334 && (my->monsterTarget == 0 || my->monsterAllyState == ALLY_STATE_MOVETO) )
335 {
336 continue;
337 }
338 if ( lavaIsPassable &&
339 (entity->sprite == 41
340 || lavatiles[map.tiles[static_cast<int>(entity->y / 16) * MAPLAYERS + static_cast<int>(entity->x / 16) * MAPLAYERS * map.height]]
341 || swimmingtiles[map.tiles[static_cast<int>(entity->y / 16) * MAPLAYERS + static_cast<int>(entity->x / 16) * MAPLAYERS * map.height]])
342 )
343 {
344 //Fix to make ladders generate in hell.
345 continue;
346 }
347 if ( playerCheckAchievement &&
348 (entity->behavior == &actMonster || entity->behavior == &actPlayer) )
349 {
350 continue;
351 }
352 int x = std::min<unsigned int>(std::max<int>(0, entity->x / 16), map.width - 1); //TODO: Why are int and double being compared? And why are int and unsigned int being compared?
353 int y = std::min<unsigned int>(std::max<int>(0, entity->y / 16), map.height - 1); //TODO: Why are int and double being compared? And why are int and unsigned int being compared?
354 pathMap[y + x * map.height] = 0;
355 }
356
357 openList = (list_t*) malloc(sizeof(list_t));
358 openList->first = NULL;
359 openList->last = NULL;
360 closedList = (list_t*) malloc(sizeof(list_t));
361 closedList->first = NULL;
362 closedList->last = NULL;
363 binaryheap = (pathnode_t**) malloc(sizeof(pathnode_t*)*map.width * map.height);
364 binaryheap[0] = NULL;
365
366 // create starting node in list
367 pathnode = newPathnode(openList, x1, y1, NULL, 1);
368 pathnode->g = 0;
369 pathnode->h = heuristic(x1, y1, x2, y2);
370 heapAdd(binaryheap, pathnode, &heaplength);
371 int tries = 0;
372 while ( openList->first != NULL && tries < 10000 )
373 {
374 /*pathnode = (pathnode_t *)openList->first->element;
375 for( node=openList->first; node!=NULL; node=node->next ) {
376 childnode = (pathnode_t *)node->element;
377 if( childnode->g+childnode->h < pathnode->g+pathnode->h )
378 pathnode=childnode;
379 }*/
380 pathnode = binaryheap[1];
381
382 x = pathnode->x;
383 y = pathnode->y;
384 h = pathnode->h;
385 g = pathnode->g;
386 parent = pathnode->parent;
387 list_RemoveNode(pathnode->node);
388 heapRemove(binaryheap, &heaplength);
389 pathnode = newPathnode(closedList, x, y, parent, 1);
390 pathnode->h = h;
391 pathnode->g = g;
392 if ( pathnode->x == x2 && pathnode->y == y2 )
393 {
394 // found target, retrace path
395 path = (list_t*) malloc(sizeof(list_t));
396 path->first = NULL;
397 path->last = NULL;
398 list_FreeAll(openList);
399 free(openList);
400 for ( childnode = pathnode; childnode != NULL; childnode = pathnode->parent )
401 {
402 if ( childnode->parent == NULL )
403 {
404 parent->parent = NULL;
405 break;
406 }
407 parent = newPathnode(path, childnode->x, childnode->y, childnode->parent, 0);
408 pathnode = pathnode->parent;
409 }
410 list_FreeAll(closedList);
411 free(closedList);
412 free(binaryheap);
413 free(pathMap);
414 return path;
415 }
416
417 // expand search
418 for ( y = -1; y <= 1; y++ )
419 {
420 for ( x = -1; x <= 1; x++ )
421 {
422 if ( x == 0 && y == 0 )
423 {
424 continue;
425 }
426 z = 0;
427 if ( !loading )
428 {
429 if ( !pathMap[(pathnode->y + y) + (pathnode->x + x)*map.height] )
430 {
431 z++;
432 }
433 if ( x && y )
434 {
435 if ( !pathMap[(pathnode->y) + (pathnode->x + x)*map.height] )
436 {
437 z++;
438 }
439 if ( !pathMap[(pathnode->y + y) + (pathnode->x)*map.height] )
440 {
441 z++;
442 }
443 }
444 }
445 else
446 {
447 if ( pathCheckObstacle(((pathnode->x + x) << 4) + 8, ((pathnode->y + y) << 4) + 8, my, target) )
448 {
449 z++;
450 }
451 if ( x && y )
452 {
453 if ( pathCheckObstacle(((pathnode->x) << 4) + 8, ((pathnode->y + y) << 4) + 8, my, target) )
454 {
455 z++;
456 }
457 if ( pathCheckObstacle(((pathnode->x + x) << 4) + 8, ((pathnode->y) << 4) + 8, my, target) )
458 {
459 z++;
460 }
461 }
462 }
463 if ( !z )
464 {
465 alreadyadded = false;
466 for ( node = closedList->first; node != NULL; node = node->next )
467 {
468 childnode = (pathnode_t*)node->element;
469 if ( childnode->x == pathnode->x + x && childnode->y == pathnode->y + y )
470 {
471 alreadyadded = true;
472 break;
473 }
474 }
475 for ( node = openList->first; node != NULL; node = node->next )
476 {
477 childnode = (pathnode_t*)node->element;
478 if ( childnode->x == pathnode->x + x && childnode->y == pathnode->y + y )
479 {
480 alreadyadded = true;
481 if ( x && y )
482 {
483 if ( childnode->g > pathnode->g + DIAGONALCOST )
484 {
485 childnode->parent = pathnode;
486 childnode->g = pathnode->g + DIAGONALCOST;
487 }
488 }
489 else
490 {
491 if ( childnode->g > pathnode->g + STRAIGHTCOST )
492 {
493 childnode->parent = pathnode;
494 childnode->g = pathnode->g + STRAIGHTCOST;
495 }
496 }
497 break;
498 }
499 }
500 if ( alreadyadded == false )
501 {
502 if ( list_Size(openList) >= 1000 )
503 {
504 list_FreeAll(openList);
505 list_FreeAll(closedList);
506 free(openList);
507 free(closedList);
508 free(binaryheap);
509 free(pathMap);
510 return NULL;
511 }
512 childnode = newPathnode(openList, pathnode->x + x, pathnode->y + y, pathnode, 1);
513 if ( x && y )
514 {
515 childnode->g = pathnode->g + DIAGONALCOST;
516 }
517 else
518 {
519 childnode->g = pathnode->g + STRAIGHTCOST;
520 }
521 childnode->h = heuristic(childnode->x, childnode->y, x2, y2);
522 heapAdd(binaryheap, childnode, &heaplength);
523 }
524 }
525 }
526 }
527 ++tries;
528 }
529 //messagePlayer(0, "tries %d", tries);
530 list_FreeAll(openList);
531 list_FreeAll(closedList);
532 free(openList);
533 free(closedList);
534 free(binaryheap);
535 free(pathMap);
536 return NULL;
537 }
538
539 /*-------------------------------------------------------------------------------
540
541 generatePathMaps
542
543 Maps out islands in the game map for the path generator
544
545 -------------------------------------------------------------------------------*/
546
547 void fillPathMap(int* pathMap, int x, int y, int zone);
548
generatePathMaps()549 void generatePathMaps()
550 {
551 int x, y;
552
553 if ( pathMapGrounded )
554 {
555 free(pathMapGrounded);
556 }
557 pathMapGrounded = (int*) calloc(map.width * map.height, sizeof(int));
558 if ( pathMapFlying )
559 {
560 free(pathMapFlying);
561 }
562 pathMapFlying = (int*) calloc(map.width * map.height, sizeof(int));
563
564 pathMapZone = 1;
565 for ( y = 0; y < map.height; y++ )
566 {
567 for ( x = 0; x < map.width; x++ )
568 {
569 if ( !pathMapGrounded[y + x * map.height] )
570 {
571 fillPathMap(pathMapGrounded, x, y, pathMapZone);
572 }
573 if ( !pathMapFlying[y + x * map.height] )
574 {
575 fillPathMap(pathMapFlying, x, y, pathMapZone);
576 }
577 }
578 }
579 }
580
fillPathMap(int * pathMap,int x,int y,int zone)581 void fillPathMap(int* pathMap, int x, int y, int zone)
582 {
583 bool obstacle = true;
584
585 int index = y * MAPLAYERS + x * MAPLAYERS * map.height;
586 if ( !map.tiles[OBSTACLELAYER + index] && map.tiles[index]
587 && !(swimmingtiles[map.tiles[index]] || lavatiles[map.tiles[index]]) )
588 {
589 obstacle = false;
590 }
591 else if ( pathMap == pathMapFlying && !map.tiles[OBSTACLELAYER + index] )
592 {
593 obstacle = false;
594 }
595 if ( obstacle == false )
596 {
597 node_t* node;
598 list_t* list = checkTileForEntity(x, y);
599 if ( list )
600 {
601 for ( node = list->first; node != NULL; node = node->next )
602 {
603 Entity* entity = (Entity*)node->element;
604 if ( entity )
605 {
606 if ( isPathObstacle(entity) )
607 {
608 obstacle = true;
609 break;
610 }
611 else if ( entity->behavior == &actWallBuilder || entity->behavior == &actWallBuster )
612 {
613 obstacle = false;
614 break;
615 }
616 }
617 }
618 //list_FreeAll(list);
619 //free(list);
620 }
621 }
622
623 if ( obstacle )
624 {
625 return;
626 }
627
628 pathMap[y + x * map.height] = zone;
629 bool repeat;
630 do
631 {
632 repeat = false;
633
634 int u, v;
635 for ( u = 0; u < map.width; u++ )
636 {
637 for ( v = 0; v < map.height; v++ )
638 {
639 if ( pathMap[v + u * map.height] == zone )
640 {
641 if ( u < map.width - 1 )
642 {
643 if ( !pathMap[v + (u + 1)*map.height] )
644 {
645 bool foundObstacle = false;
646 bool foundWallModifier = false;
647 list_t* list = checkTileForEntity(u + 1, v);
648 if ( list )
649 {
650 node_t* node;
651 for ( node = list->first; node != NULL; node = node->next )
652 {
653 Entity* entity = (Entity*)node->element;
654 if ( entity )
655 {
656 if ( isPathObstacle(entity) )
657 {
658 foundObstacle = true;
659 break;
660 }
661 else if ( entity->behavior == &actWallBuilder || entity->behavior == &actWallBuster )
662 {
663 foundWallModifier = true;
664 break;
665 }
666 }
667 }
668 if ( foundWallModifier )
669 {
670 pathMap[v + (u + 1)*map.height] = zone;
671 repeat = true;
672 }
673 //list_FreeAll(list);
674 //free(list);
675 }
676 if ( !foundWallModifier && !foundObstacle )
677 {
678 int index = v * MAPLAYERS + (u + 1) * MAPLAYERS * map.height;
679 if ( !map.tiles[OBSTACLELAYER + index] && (pathMap == pathMapFlying
680 || (map.tiles[index] && !(swimmingtiles[map.tiles[index]] || lavatiles[map.tiles[index]]) )) )
681 {
682 pathMap[v + (u + 1)*map.height] = zone;
683 repeat = true;
684 }
685 }
686 }
687 }
688 if ( u > 0 )
689 {
690 if ( !pathMap[v + (u - 1)*map.height] )
691 {
692 bool foundObstacle = false;
693 bool foundWallModifier = false;
694 list_t* list = checkTileForEntity(u - 1, v);
695 if ( list )
696 {
697 node_t* node;
698 for ( node = list->first; node != NULL; node = node->next )
699 {
700 Entity* entity = (Entity*)node->element;
701 if ( entity )
702 {
703 if ( isPathObstacle(entity) )
704 {
705 foundObstacle = true;
706 break;
707 }
708 else if ( entity->behavior == &actWallBuilder || entity->behavior == &actWallBuster )
709 {
710 foundWallModifier = true;
711 break;
712 }
713 }
714 }
715 if ( foundWallModifier )
716 {
717 pathMap[v + (u - 1)*map.height] = zone;
718 repeat = true;
719 }
720 //list_FreeAll(list);
721 //free(list);
722 }
723 if ( !foundWallModifier && !foundObstacle )
724 {
725 int index = v * MAPLAYERS + (u - 1) * MAPLAYERS * map.height;
726 if ( !map.tiles[OBSTACLELAYER + index] && (pathMap == pathMapFlying
727 || (map.tiles[index] && !(swimmingtiles[map.tiles[index]] || lavatiles[map.tiles[index]])) ) )
728 {
729 pathMap[v + (u - 1)*map.height] = zone;
730 repeat = true;
731 }
732 }
733 }
734 }
735 if ( v < map.height - 1 )
736 {
737 if ( !pathMap[(v + 1) + u * map.height] )
738 {
739 bool foundObstacle = false;
740 bool foundWallModifier = false;
741 list_t* list = checkTileForEntity(u, v + 1);
742 if ( list )
743 {
744 node_t* node;
745 for ( node = list->first; node != NULL; node = node->next )
746 {
747 Entity* entity = (Entity*)node->element;
748 if ( entity )
749 {
750 if ( isPathObstacle(entity) )
751 {
752 foundObstacle = true;
753 break;
754 }
755 else if ( entity->behavior == &actWallBuilder || entity->behavior == &actWallBuster )
756 {
757 foundWallModifier = true;
758 break;
759 }
760 }
761 }
762 if ( foundWallModifier )
763 {
764 pathMap[(v + 1) + u * map.height] = zone;
765 repeat = true;
766 }
767 //list_FreeAll(list);
768 //free(list);
769 }
770 if ( !foundWallModifier && !foundObstacle )
771 {
772 int index = (v + 1) * MAPLAYERS + u * MAPLAYERS * map.height;
773 if ( !map.tiles[OBSTACLELAYER + index] && (pathMap == pathMapFlying
774 || (map.tiles[index] && !(swimmingtiles[map.tiles[index]] || lavatiles[map.tiles[index]])) ) )
775 {
776 pathMap[(v + 1) + u * map.height] = zone;
777 repeat = true;
778 }
779 }
780 }
781 }
782 if ( v > 0 )
783 {
784 if ( !pathMap[(v - 1) + u * map.height] )
785 {
786 bool foundObstacle = false;
787 bool foundWallModifier = false;
788 list_t* list = checkTileForEntity(u, v - 1);
789 if ( list )
790 {
791 node_t* node;
792 for ( node = list->first; node != NULL; node = node->next )
793 {
794 Entity* entity = (Entity*)node->element;
795 if ( entity )
796 {
797 if ( isPathObstacle(entity) )
798 {
799 foundObstacle = true;
800 break;
801 }
802 else if ( entity->behavior == &actWallBuilder || entity->behavior == &actWallBuster )
803 {
804 foundWallModifier = true;
805 break;
806 }
807 }
808 }
809 if ( foundWallModifier )
810 {
811 pathMap[(v - 1) + u * map.height] = zone;
812 repeat = true;
813 }
814 //list_FreeAll(list);
815 //free(list);
816 }
817 if ( !foundWallModifier && !foundObstacle )
818 {
819 int index = (v - 1) * MAPLAYERS + u * MAPLAYERS * map.height;
820 if ( !map.tiles[OBSTACLELAYER + index] && (pathMap == pathMapFlying
821 || (map.tiles[index] && !(swimmingtiles[map.tiles[index]] || lavatiles[map.tiles[index]]) )) )
822 {
823 pathMap[(v - 1) + u * map.height] = zone;
824 repeat = true;
825 }
826 }
827 }
828 }
829 }
830 }
831 }
832 }
833 while ( repeat );
834 pathMapZone++;
835 }
836
837
838
isPathObstacle(Entity * entity)839 bool isPathObstacle(Entity* entity)
840 {
841 if ( entity->behavior == &actHeadstone )
842 {
843 return true;
844 }
845 else if(entity->behavior == &actSink )
846 {
847 return true;
848 }
849 else if ( entity->behavior == &actFountain )
850 {
851 return true;
852 }
853 else if ( entity->behavior == &actPowerCrystal || entity->behavior == &actPowerCrystalBase )
854 {
855 return true;
856 }
857 else if ( entity->behavior == &actPedestalBase || entity->behavior == &actPedestalOrb )
858 {
859 return true;
860 }
861
862 return false;
863 }
864