Annotation of brogue-ce/src/brogue/Dijkstra.c, Revision 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