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