Return to Dijkstra.c CVS log

Up to [contributed] / brogue-ce / src / brogue

Initial revision

/*
 *  Dijkstra.c
 *  Brogue
 *
 *  Copyright 2012. All rights reserved.
 *
 *  This file is part of Brogue.
 *
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU Affero General Public License as
 *  published by the Free Software Foundation, either version 3 of the
 *  License, or (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU Affero General Public License for more details.
 *
 *  You should have received a copy of the GNU Affero General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

// This code was created by Joshua Day, to replace my clunkier and slower Dijkstra scanning algorithm in Movement.c.
// Thanks very much, Joshua.

#include "Rogue.h"
#include "IncludeGlobals.h"

struct pdsLink {
    short distance;
    short cost;
    pdsLink *left, *right;
};

struct pdsMap {
    boolean eightWays;

    pdsLink front;
    pdsLink links[DCOLS * DROWS];
};

void pdsUpdate(pdsMap *map) {
    short dir, dirs;
    pdsLink *left = NULL, *right = NULL, *link = NULL;

    dirs = map->eightWays ? 8 : 4;

    pdsLink *head = map->front.right;
    map->front.right = NULL;

    while (head != NULL) {
        for (dir = 0; dir < dirs; dir++) {
            link = head + (nbDirs[dir][0] + DCOLS * nbDirs[dir][1]);
            if (link < map->links || link >= map->links + DCOLS * DROWS) continue;

            // verify passability
            if (link->cost < 0) continue;
            if (dir >= 4) {
                pdsLink *way1, *way2;
                way1 = head + nbDirs[dir][0];
                way2 = head + DCOLS * nbDirs[dir][1];
                if (way1->cost == PDS_OBSTRUCTION || way2->cost == PDS_OBSTRUCTION) continue;
            }

            if (head->distance + link->cost < link->distance) {
                link->distance = head->distance + link->cost;

                // reinsert the touched cell; it'll be close to the beginning of the list now, so
                // this will be very fast.  start by removing it.

                if (link->right != NULL) link->right->left = link->left;
                if (link->left != NULL) link->left->right = link->right;

                left = head;
                right = head->right;
                while (right != NULL && right->distance < link->distance) {
                    left = right;
                    right = right->right;
                }
                if (left != NULL) left->right = link;
                link->right = right;
                link->left = left;
                if (right != NULL) right->left = link;
            }
        }

        right = head->right;

        head->left = NULL;
        head->right = NULL;

        head = right;
    }
}

void pdsClear(pdsMap *map, short maxDistance, boolean eightWays) {
    short i;

    map->eightWays = eightWays;

    map->front.right = NULL;

    for (i=0; i < DCOLS*DROWS; i++) {
        map->links[i].distance = maxDistance;
        map->links[i].left = map->links[i].right = NULL;
    }
}

short pdsGetDistance(pdsMap *map, short x, short y) {
    pdsUpdate(map);
    return PDS_CELL(map, x, y)->distance;
}

void pdsSetDistance(pdsMap *map, short x, short y, short distance) {
    pdsLink *left, *right, *link;

    if (x > 0 && y > 0 && x < DCOLS - 1 && y < DROWS - 1) {
        link = PDS_CELL(map, x, y);
        if (link->distance > distance) {
            link->distance = distance;

            if (link->right != NULL) link->right->left = link->left;
            if (link->left != NULL) link->left->right = link->right;

            left = &map->front;
            right = map->front.right;

            while (right != NULL && right->distance < link->distance) {
                left = right;
                right = right->right;
            }

            link->right = right;
            link->left = left;
            left->right = link;
            if (right != NULL) right->left = link;
        }
    }
}

void pdsSetCosts(pdsMap *map, short **costMap) {
    short i, j;

    for (i=0; i<DCOLS; i++) {
        for (j=0; j<DROWS; j++) {
            if (i != 0 && j != 0 && i < DCOLS - 1 && j < DROWS - 1) {
                PDS_CELL(map, i, j)->cost = costMap[i][j];
            } else {
                PDS_CELL(map, i, j)->cost = PDS_FORBIDDEN;
            }
        }
    }
}

void pdsBatchInput(pdsMap *map, short **distanceMap, short **costMap, short maxDistance, boolean eightWays) {
    short i, j;
    pdsLink *left, *right;

    map->eightWays = eightWays;

    left = NULL;
    right = NULL;

    map->front.right = NULL;
    for (i=0; i<DCOLS; i++) {
        for (j=0; j<DROWS; j++) {
            pdsLink *link = PDS_CELL(map, i, j);

            if (distanceMap != NULL) {
                link->distance = distanceMap[i][j];
            } else {
                if (costMap != NULL) {
                    // totally hackish; refactor
                    link->distance = maxDistance;
                }
            }

            int cost;

            if (i == 0 || j == 0 || i == DCOLS - 1 || j == DROWS - 1) {
                cost = PDS_OBSTRUCTION;
            } else if (costMap == NULL) {
                if (cellHasTerrainFlag(i, j, T_OBSTRUCTS_PASSABILITY) && cellHasTerrainFlag(i, j, T_OBSTRUCTS_DIAGONAL_MOVEMENT)) cost = PDS_OBSTRUCTION;
                else cost = PDS_FORBIDDEN;
            } else {
                cost = costMap[i][j];
            }

            link->cost = cost;

            if (cost > 0) {
                if (link->distance < maxDistance) {
                    if (right == NULL || right->distance > link->distance) {
                        // left and right are used to traverse the list; if many cells have similar values,
                        // some time can be saved by not clearing them with each insertion.  this time,
                        // sadly, we have to start from the front.

                        left = &map->front;
                        right = map->front.right;
                    }

                    while (right != NULL && right->distance < link->distance) {
                        left = right;
                        right = right->right;
                    }

                    link->right = right;
                    link->left = left;
                    left->right = link;
                    if (right != NULL) right->left = link;

                    left = link;
                } else {
                    link->right = NULL;
                    link->left = NULL;
                }
            } else {
                link->right = NULL;
                link->left = NULL;
            }
        }
    }
}

void pdsBatchOutput(pdsMap *map, short **distanceMap) {
    short i, j;

    pdsUpdate(map);
    // transfer results to the distanceMap
    for (i=0; i<DCOLS; i++) {
        for (j=0; j<DROWS; j++) {
            distanceMap[i][j] = PDS_CELL(map, i, j)->distance;
        }
    }
}

void pdsInvalidate(pdsMap *map, short maxDistance) {
    pdsBatchInput(map, NULL, NULL, maxDistance, map->eightWays);
}

void dijkstraScan(short **distanceMap, short **costMap, boolean useDiagonals) {
    static pdsMap map;

    pdsBatchInput(&map, distanceMap, costMap, 30000, useDiagonals);
    pdsBatchOutput(&map, distanceMap);
}

void calculateDistances(short **distanceMap,
                        short destinationX, short destinationY,
                        unsigned long blockingTerrainFlags,
                        creature *traveler,
                        boolean canUseSecretDoors,
                        boolean eightWays) {
    creature *monst;
    static pdsMap map;

    short i, j;

    for (i=0; i<DCOLS; i++) {
        for (j=0; j<DROWS; j++) {
            char cost;
            monst = monsterAtLoc(i, j);
            if (monst
                && (monst->info.flags & (MONST_IMMUNE_TO_WEAPONS | MONST_INVULNERABLE))
                && (monst->info.flags & (MONST_IMMOBILE | MONST_GETS_TURN_ON_ACTIVATION))) {

                // Always avoid damage-immune stationary monsters.
                cost = PDS_FORBIDDEN;
            } else if (canUseSecretDoors
                && cellHasTMFlag(i, j, TM_IS_SECRET)
                && cellHasTerrainFlag(i, j, T_OBSTRUCTS_PASSABILITY)
                && !(discoveredTerrainFlagsAtLoc(i, j) & T_OBSTRUCTS_PASSABILITY)) {

                cost = 1;
            } else if (cellHasTerrainFlag(i, j, T_OBSTRUCTS_PASSABILITY)
                       || (traveler && traveler == &player && !(pmap[i][j].flags & (DISCOVERED | MAGIC_MAPPED)))) {

                cost = cellHasTerrainFlag(i, j, T_OBSTRUCTS_DIAGONAL_MOVEMENT) ? PDS_OBSTRUCTION : PDS_FORBIDDEN;
            } else if ((traveler && monsterAvoids(traveler, i, j)) || cellHasTerrainFlag(i, j, blockingTerrainFlags)) {
                cost = PDS_FORBIDDEN;
            } else {
                cost = 1;
            }

            PDS_CELL(&map, i, j)->cost = cost;
        }
    }

    pdsClear(&map, 30000, eightWays);
    pdsSetDistance(&map, destinationX, destinationY, 0);
    pdsBatchOutput(&map, distanceMap);
}

short pathingDistance(short x1, short y1, short x2, short y2, unsigned long blockingTerrainFlags) {
    short retval, **distanceMap = allocGrid();
    calculateDistances(distanceMap, x2, y2, blockingTerrainFlags, NULL, true, true);
    retval = distanceMap[x1][y1];
    freeGrid(distanceMap);
    return retval;
}