1 /*
2  *  Dijkstra.c
3  *  Brogue
4  *
5  *  Copyright 2012. All rights reserved.
6  *
7  *  This file is part of Brogue.
8  *
9  *  This program is free software: you can redistribute it and/or modify
10  *  it under the terms of the GNU Affero General Public License as
11  *  published by the Free Software Foundation, either version 3 of the
12  *  License, or (at your option) any later version.
13  *
14  *  This program is distributed in the hope that it will be useful,
15  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
16  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
17  *  GNU Affero General Public License for more details.
18  *
19  *  You should have received a copy of the GNU Affero General Public License
20  *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
21  */
22 
23 // This code was created by Joshua Day, to replace my clunkier and slower Dijkstra scanning algorithm in Movement.c.
24 // Thanks very much, Joshua.
25 
26 #include "Rogue.h"
27 #include "IncludeGlobals.h"
28 
29 typedef struct pdsLink {
30     short distance;
31     short cost;
32     struct pdsLink *left;
33     struct pdsLink *right;
34 } pdsLink;
35 
36 typedef struct pdsMap {
37     pdsLink front;
38     pdsLink links[DCOLS * DROWS];
39 } pdsMap;
40 
pdsUpdate(pdsMap * map,boolean useDiagonals)41 static void pdsUpdate(pdsMap *map, boolean useDiagonals) {
42     short dirs = useDiagonals ? 8 : 4;
43 
44     pdsLink *head = map->front.right;
45     map->front.right = NULL;
46 
47     while (head != NULL) {
48         for (short dir = 0; dir < dirs; dir++) {
49             pdsLink *link = head + (nbDirs[dir][0] + DCOLS * nbDirs[dir][1]);
50             if (link < map->links || link >= map->links + DCOLS * DROWS) continue;
51 
52             // verify passability
53             if (link->cost < 0) continue;
54             if (dir >= 4) {
55                 pdsLink *way1 = head + nbDirs[dir][0];
56                 pdsLink *way2 = head + DCOLS * nbDirs[dir][1];
57                 if (way1->cost == PDS_OBSTRUCTION || way2->cost == PDS_OBSTRUCTION) continue;
58             }
59 
60             if (head->distance + link->cost < link->distance) {
61                 link->distance = head->distance + link->cost;
62 
63                 // reinsert the touched cell; it'll be close to the beginning of the list now, so
64                 // this will be very fast.  start by removing it.
65 
66                 if (link->right != NULL) link->right->left = link->left;
67                 if (link->left != NULL) link->left->right = link->right;
68 
69                 pdsLink *left = head;
70                 pdsLink *right = head->right;
71                 while (right != NULL && right->distance < link->distance) {
72                     left = right;
73                     right = right->right;
74                 }
75                 if (left != NULL) left->right = link;
76                 link->right = right;
77                 link->left = left;
78                 if (right != NULL) right->left = link;
79             }
80         }
81 
82         pdsLink *right = head->right;
83 
84         head->left = NULL;
85         head->right = NULL;
86 
87         head = right;
88     }
89 }
90 
pdsClear(pdsMap * map,short maxDistance)91 static void pdsClear(pdsMap *map, short maxDistance) {
92     map->front.right = NULL;
93 
94     for (int i=0; i < DCOLS*DROWS; i++) {
95         map->links[i].distance = maxDistance;
96         map->links[i].left = NULL;
97         map->links[i].right = NULL;
98     }
99 }
100 
pdsSetDistance(pdsMap * map,short x,short y,short distance)101 static void pdsSetDistance(pdsMap *map, short x, short y, short distance) {
102     if (x > 0 && y > 0 && x < DCOLS - 1 && y < DROWS - 1) {
103         pdsLink *link = PDS_CELL(map, x, y);
104         if (link->distance > distance) {
105             link->distance = distance;
106 
107             if (link->right != NULL) link->right->left = link->left;
108             if (link->left != NULL) link->left->right = link->right;
109 
110             pdsLink *left = &map->front;
111             pdsLink *right = map->front.right;
112 
113             while (right != NULL && right->distance < link->distance) {
114                 left = right;
115                 right = right->right;
116             }
117 
118             link->right = right;
119             link->left = left;
120             left->right = link;
121             if (right != NULL) right->left = link;
122         }
123     }
124 }
125 
pdsBatchInput(pdsMap * map,short ** distanceMap,short ** costMap,short maxDistance)126 static void pdsBatchInput(pdsMap *map, short **distanceMap, short **costMap, short maxDistance) {
127     pdsLink *left = NULL;
128     pdsLink *right = NULL;
129 
130     map->front.right = NULL;
131     for (int i=0; i<DCOLS; i++) {
132         for (int j=0; j<DROWS; j++) {
133             pdsLink *link = PDS_CELL(map, i, j);
134 
135             if (distanceMap != NULL) {
136                 link->distance = distanceMap[i][j];
137             } else {
138                 if (costMap != NULL) {
139                     // totally hackish; refactor
140                     link->distance = maxDistance;
141                 }
142             }
143 
144             int cost;
145 
146             if (i == 0 || j == 0 || i == DCOLS - 1 || j == DROWS - 1) {
147                 cost = PDS_OBSTRUCTION;
148             } else if (costMap == NULL) {
149                 if (cellHasTerrainFlag(i, j, T_OBSTRUCTS_PASSABILITY) && cellHasTerrainFlag(i, j, T_OBSTRUCTS_DIAGONAL_MOVEMENT)) cost = PDS_OBSTRUCTION;
150                 else cost = PDS_FORBIDDEN;
151             } else {
152                 cost = costMap[i][j];
153             }
154 
155             link->cost = cost;
156 
157             if (cost > 0) {
158                 if (link->distance < maxDistance) {
159                     if (right == NULL || right->distance > link->distance) {
160                         // left and right are used to traverse the list; if many cells have similar values,
161                         // some time can be saved by not clearing them with each insertion.  this time,
162                         // sadly, we have to start from the front.
163 
164                         left = &map->front;
165                         right = map->front.right;
166                     }
167 
168                     while (right != NULL && right->distance < link->distance) {
169                         left = right;
170                         right = right->right;
171                     }
172 
173                     link->right = right;
174                     link->left = left;
175                     left->right = link;
176                     if (right != NULL) right->left = link;
177 
178                     left = link;
179                 } else {
180                     link->right = NULL;
181                     link->left = NULL;
182                 }
183             } else {
184                 link->right = NULL;
185                 link->left = NULL;
186             }
187         }
188     }
189 }
190 
pdsBatchOutput(pdsMap * map,short ** distanceMap,boolean useDiagonals)191 static void pdsBatchOutput(pdsMap *map, short **distanceMap, boolean useDiagonals) {
192     pdsUpdate(map, useDiagonals);
193     // transfer results to the distanceMap
194     for (int i=0; i<DCOLS; i++) {
195         for (int j=0; j<DROWS; j++) {
196             distanceMap[i][j] = PDS_CELL(map, i, j)->distance;
197         }
198     }
199 }
200 
dijkstraScan(short ** distanceMap,short ** costMap,boolean useDiagonals)201 void dijkstraScan(short **distanceMap, short **costMap, boolean useDiagonals) {
202     static pdsMap map;
203 
204     pdsBatchInput(&map, distanceMap, costMap, 30000);
205     pdsBatchOutput(&map, distanceMap, useDiagonals);
206 }
207 
calculateDistances(short ** distanceMap,short destinationX,short destinationY,unsigned long blockingTerrainFlags,creature * traveler,boolean canUseSecretDoors,boolean eightWays)208 void calculateDistances(short **distanceMap,
209                         short destinationX, short destinationY,
210                         unsigned long blockingTerrainFlags,
211                         creature *traveler,
212                         boolean canUseSecretDoors,
213                         boolean eightWays) {
214     static pdsMap map;
215 
216     for (int i=0; i<DCOLS; i++) {
217         for (int j=0; j<DROWS; j++) {
218             signed char cost;
219             creature *monst = monsterAtLoc(i, j);
220             if (monst
221                 && (monst->info.flags & (MONST_IMMUNE_TO_WEAPONS | MONST_INVULNERABLE))
222                 && (monst->info.flags & (MONST_IMMOBILE | MONST_GETS_TURN_ON_ACTIVATION))) {
223 
224                 // Always avoid damage-immune stationary monsters.
225                 cost = PDS_FORBIDDEN;
226             } else if (canUseSecretDoors
227                 && cellHasTMFlag(i, j, TM_IS_SECRET)
228                 && cellHasTerrainFlag(i, j, T_OBSTRUCTS_PASSABILITY)
229                 && !(discoveredTerrainFlagsAtLoc(i, j) & T_OBSTRUCTS_PASSABILITY)) {
230 
231                 cost = 1;
232             } else if (cellHasTerrainFlag(i, j, T_OBSTRUCTS_PASSABILITY)
233                        || (traveler && traveler == &player && !(pmap[i][j].flags & (DISCOVERED | MAGIC_MAPPED)))) {
234 
235                 cost = cellHasTerrainFlag(i, j, T_OBSTRUCTS_DIAGONAL_MOVEMENT) ? PDS_OBSTRUCTION : PDS_FORBIDDEN;
236             } else if ((traveler && monsterAvoids(traveler, i, j)) || cellHasTerrainFlag(i, j, blockingTerrainFlags)) {
237                 cost = PDS_FORBIDDEN;
238             } else {
239                 cost = 1;
240             }
241 
242             PDS_CELL(&map, i, j)->cost = cost;
243         }
244     }
245 
246     pdsClear(&map, 30000);
247     pdsSetDistance(&map, destinationX, destinationY, 0);
248     pdsBatchOutput(&map, distanceMap, eightWays);
249 }
250 
pathingDistance(short x1,short y1,short x2,short y2,unsigned long blockingTerrainFlags)251 short pathingDistance(short x1, short y1, short x2, short y2, unsigned long blockingTerrainFlags) {
252     short **distanceMap = allocGrid();
253     calculateDistances(distanceMap, x2, y2, blockingTerrainFlags, NULL, true, true);
254     short retval = distanceMap[x1][y1];
255     freeGrid(distanceMap);
256     return retval;
257 }
258 
259