Annotation of brogue-ce/src/brogue/Dijkstra.c, Revision 1.1.1.1
1.1 rubenllo 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: struct pdsLink {
30: short distance;
31: short cost;
32: pdsLink *left, *right;
33: };
34:
35: struct pdsMap {
36: boolean eightWays;
37:
38: pdsLink front;
39: pdsLink links[DCOLS * DROWS];
40: };
41:
42: void pdsUpdate(pdsMap *map) {
43: short dir, dirs;
44: pdsLink *left = NULL, *right = NULL, *link = NULL;
45:
46: dirs = map->eightWays ? 8 : 4;
47:
48: pdsLink *head = map->front.right;
49: map->front.right = NULL;
50:
51: while (head != NULL) {
52: for (dir = 0; dir < dirs; dir++) {
53: link = head + (nbDirs[dir][0] + DCOLS * nbDirs[dir][1]);
54: if (link < map->links || link >= map->links + DCOLS * DROWS) continue;
55:
56: // verify passability
57: if (link->cost < 0) continue;
58: if (dir >= 4) {
59: pdsLink *way1, *way2;
60: way1 = head + nbDirs[dir][0];
61: way2 = head + DCOLS * nbDirs[dir][1];
62: if (way1->cost == PDS_OBSTRUCTION || way2->cost == PDS_OBSTRUCTION) continue;
63: }
64:
65: if (head->distance + link->cost < link->distance) {
66: link->distance = head->distance + link->cost;
67:
68: // reinsert the touched cell; it'll be close to the beginning of the list now, so
69: // this will be very fast. start by removing it.
70:
71: if (link->right != NULL) link->right->left = link->left;
72: if (link->left != NULL) link->left->right = link->right;
73:
74: left = head;
75: right = head->right;
76: while (right != NULL && right->distance < link->distance) {
77: left = right;
78: right = right->right;
79: }
80: if (left != NULL) left->right = link;
81: link->right = right;
82: link->left = left;
83: if (right != NULL) right->left = link;
84: }
85: }
86:
87: right = head->right;
88:
89: head->left = NULL;
90: head->right = NULL;
91:
92: head = right;
93: }
94: }
95:
96: void pdsClear(pdsMap *map, short maxDistance, boolean eightWays) {
97: short i;
98:
99: map->eightWays = eightWays;
100:
101: map->front.right = NULL;
102:
103: for (i=0; i < DCOLS*DROWS; i++) {
104: map->links[i].distance = maxDistance;
105: map->links[i].left = map->links[i].right = NULL;
106: }
107: }
108:
109: short pdsGetDistance(pdsMap *map, short x, short y) {
110: pdsUpdate(map);
111: return PDS_CELL(map, x, y)->distance;
112: }
113:
114: void pdsSetDistance(pdsMap *map, short x, short y, short distance) {
115: pdsLink *left, *right, *link;
116:
117: if (x > 0 && y > 0 && x < DCOLS - 1 && y < DROWS - 1) {
118: link = PDS_CELL(map, x, y);
119: if (link->distance > distance) {
120: link->distance = distance;
121:
122: if (link->right != NULL) link->right->left = link->left;
123: if (link->left != NULL) link->left->right = link->right;
124:
125: left = &map->front;
126: right = map->front.right;
127:
128: while (right != NULL && right->distance < link->distance) {
129: left = right;
130: right = right->right;
131: }
132:
133: link->right = right;
134: link->left = left;
135: left->right = link;
136: if (right != NULL) right->left = link;
137: }
138: }
139: }
140:
141: void pdsSetCosts(pdsMap *map, short **costMap) {
142: short i, j;
143:
144: for (i=0; i<DCOLS; i++) {
145: for (j=0; j<DROWS; j++) {
146: if (i != 0 && j != 0 && i < DCOLS - 1 && j < DROWS - 1) {
147: PDS_CELL(map, i, j)->cost = costMap[i][j];
148: } else {
149: PDS_CELL(map, i, j)->cost = PDS_FORBIDDEN;
150: }
151: }
152: }
153: }
154:
155: void pdsBatchInput(pdsMap *map, short **distanceMap, short **costMap, short maxDistance, boolean eightWays) {
156: short i, j;
157: pdsLink *left, *right;
158:
159: map->eightWays = eightWays;
160:
161: left = NULL;
162: right = NULL;
163:
164: map->front.right = NULL;
165: for (i=0; i<DCOLS; i++) {
166: for (j=0; j<DROWS; j++) {
167: pdsLink *link = PDS_CELL(map, i, j);
168:
169: if (distanceMap != NULL) {
170: link->distance = distanceMap[i][j];
171: } else {
172: if (costMap != NULL) {
173: // totally hackish; refactor
174: link->distance = maxDistance;
175: }
176: }
177:
178: int cost;
179:
180: if (i == 0 || j == 0 || i == DCOLS - 1 || j == DROWS - 1) {
181: cost = PDS_OBSTRUCTION;
182: } else if (costMap == NULL) {
183: if (cellHasTerrainFlag(i, j, T_OBSTRUCTS_PASSABILITY) && cellHasTerrainFlag(i, j, T_OBSTRUCTS_DIAGONAL_MOVEMENT)) cost = PDS_OBSTRUCTION;
184: else cost = PDS_FORBIDDEN;
185: } else {
186: cost = costMap[i][j];
187: }
188:
189: link->cost = cost;
190:
191: if (cost > 0) {
192: if (link->distance < maxDistance) {
193: if (right == NULL || right->distance > link->distance) {
194: // left and right are used to traverse the list; if many cells have similar values,
195: // some time can be saved by not clearing them with each insertion. this time,
196: // sadly, we have to start from the front.
197:
198: left = &map->front;
199: right = map->front.right;
200: }
201:
202: while (right != NULL && right->distance < link->distance) {
203: left = right;
204: right = right->right;
205: }
206:
207: link->right = right;
208: link->left = left;
209: left->right = link;
210: if (right != NULL) right->left = link;
211:
212: left = link;
213: } else {
214: link->right = NULL;
215: link->left = NULL;
216: }
217: } else {
218: link->right = NULL;
219: link->left = NULL;
220: }
221: }
222: }
223: }
224:
225: void pdsBatchOutput(pdsMap *map, short **distanceMap) {
226: short i, j;
227:
228: pdsUpdate(map);
229: // transfer results to the distanceMap
230: for (i=0; i<DCOLS; i++) {
231: for (j=0; j<DROWS; j++) {
232: distanceMap[i][j] = PDS_CELL(map, i, j)->distance;
233: }
234: }
235: }
236:
237: void pdsInvalidate(pdsMap *map, short maxDistance) {
238: pdsBatchInput(map, NULL, NULL, maxDistance, map->eightWays);
239: }
240:
241: void dijkstraScan(short **distanceMap, short **costMap, boolean useDiagonals) {
242: static pdsMap map;
243:
244: pdsBatchInput(&map, distanceMap, costMap, 30000, useDiagonals);
245: pdsBatchOutput(&map, distanceMap);
246: }
247:
248: void calculateDistances(short **distanceMap,
249: short destinationX, short destinationY,
250: unsigned long blockingTerrainFlags,
251: creature *traveler,
252: boolean canUseSecretDoors,
253: boolean eightWays) {
254: creature *monst;
255: static pdsMap map;
256:
257: short i, j;
258:
259: for (i=0; i<DCOLS; i++) {
260: for (j=0; j<DROWS; j++) {
261: char cost;
262: monst = monsterAtLoc(i, j);
263: if (monst
264: && (monst->info.flags & (MONST_IMMUNE_TO_WEAPONS | MONST_INVULNERABLE))
265: && (monst->info.flags & (MONST_IMMOBILE | MONST_GETS_TURN_ON_ACTIVATION))) {
266:
267: // Always avoid damage-immune stationary monsters.
268: cost = PDS_FORBIDDEN;
269: } else if (canUseSecretDoors
270: && cellHasTMFlag(i, j, TM_IS_SECRET)
271: && cellHasTerrainFlag(i, j, T_OBSTRUCTS_PASSABILITY)
272: && !(discoveredTerrainFlagsAtLoc(i, j) & T_OBSTRUCTS_PASSABILITY)) {
273:
274: cost = 1;
275: } else if (cellHasTerrainFlag(i, j, T_OBSTRUCTS_PASSABILITY)
276: || (traveler && traveler == &player && !(pmap[i][j].flags & (DISCOVERED | MAGIC_MAPPED)))) {
277:
278: cost = cellHasTerrainFlag(i, j, T_OBSTRUCTS_DIAGONAL_MOVEMENT) ? PDS_OBSTRUCTION : PDS_FORBIDDEN;
279: } else if ((traveler && monsterAvoids(traveler, i, j)) || cellHasTerrainFlag(i, j, blockingTerrainFlags)) {
280: cost = PDS_FORBIDDEN;
281: } else {
282: cost = 1;
283: }
284:
285: PDS_CELL(&map, i, j)->cost = cost;
286: }
287: }
288:
289: pdsClear(&map, 30000, eightWays);
290: pdsSetDistance(&map, destinationX, destinationY, 0);
291: pdsBatchOutput(&map, distanceMap);
292: }
293:
294: short pathingDistance(short x1, short y1, short x2, short y2, unsigned long blockingTerrainFlags) {
295: short retval, **distanceMap = allocGrid();
296: calculateDistances(distanceMap, x2, y2, blockingTerrainFlags, NULL, true, true);
297: retval = distanceMap[x1][y1];
298: freeGrid(distanceMap);
299: return retval;
300: }
301:
CVSweb
![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to Dijkstra.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [contributed] / brogue-ce / src / brogue