path.cpp

Go to the documentation of this file.

 
#include "all.h"
 
 
DEVILUTION_BEGIN_NAMESPACE
PATHNODE path_nodes[MAXPATHNODES];
int gdwCurPathStep;
int gdwCurNodes;
int pnode_vals[MAX_PATH_LENGTH];
PATHNODE *pnode_ptr;
PATHNODE *pnode_tblptr[MAXPATHNODES];
PATHNODE *path_2_nodes;
PATHNODE path_unusednodes[MAXPATHNODES];
 
const char pathxdir[8] = { -1, -1, 1, 1, -1, 0, 1, 0 };
const char pathydir[8] = { -1, 1, -1, 1, 0, -1, 0, 1 };
 
/* data */
 
char path_directions[9] = { 5, 1, 6, 2, 0, 3, 8, 4, 7 };
 
int FindPath(BOOL (*PosOk)(int, int, int), int PosOkArg, int sx, int sy, int dx, int dy, char *path)
{
    PATHNODE *path_start, *next_node, *current;
    int path_length, i;
 
    // clear all nodes, create root nodes for the visited/frontier linked lists
    gdwCurNodes = 0;
    path_2_nodes = path_new_step();
    pnode_ptr = path_new_step();
    gdwCurPathStep = 0;
    path_start = path_new_step();
    path_start->g = 0;
    path_start->h = path_get_h_cost(sx, sy, dx, dy);
    path_start->x = sx;
    path_start->f = path_start->h + path_start->g;
    path_start->y = sy;
    path_2_nodes->NextNode = path_start;
    // A* search until we find (dx,dy) or fail
    while ((next_node = GetNextPath())) {
        // reached the end, success!
        if (next_node->x == dx && next_node->y == dy) {
            current = next_node;
            path_length = 0;
            while (current->Parent) {
                if (path_length >= MAX_PATH_LENGTH)
                    break;
                pnode_vals[path_length++] = path_directions[3 * (current->y - current->Parent->y) - current->Parent->x + 4 + current->x];
                current = current->Parent;
            }
            if (path_length != MAX_PATH_LENGTH) {
                for (i = 0; i < path_length; i++)
                    path[i] = pnode_vals[path_length - i - 1];
                return i;
            }
            return 0;
        }
        // ran out of nodes, abort!
        if (!path_get_path(PosOk, PosOkArg, next_node, dx, dy))
            return 0;
    }
    // frontier is empty, no path!
    return 0;
}
 
int path_get_h_cost(int sx, int sy, int dx, int dy)
{
    int delta_x = abs(sx - dx);
    int delta_y = abs(sy - dy);
 
    int min = delta_x < delta_y ? delta_x : delta_y;
    int max = delta_x > delta_y ? delta_x : delta_y;
 
    // see path_check_equal for why this is times 2
    return 2 * (min + max);
}
 
int path_check_equal(PATHNODE *pPath, int dx, int dy)
{
    if (pPath->x == dx || pPath->y == dy)
        return 2;
 
    return 3;
}
 
PATHNODE *GetNextPath()
{
    PATHNODE *result;
 
    result = path_2_nodes->NextNode;
    if (result == NULL) {
        return result;
    }
 
    path_2_nodes->NextNode = result->NextNode;
    result->NextNode = pnode_ptr->NextNode;
    pnode_ptr->NextNode = result;
    return result;
}
 
BOOL path_solid_pieces(PATHNODE *pPath, int dx, int dy)
{
    BOOL rv = TRUE;
    switch (path_directions[3 * (dy - pPath->y) + 3 - pPath->x + 1 + dx]) {
    case 5:
        rv = !nSolidTable[dPiece[dx][dy + 1]] && !nSolidTable[dPiece[dx + 1][dy]];
        break;
    case 6:
        rv = !nSolidTable[dPiece[dx][dy + 1]] && !nSolidTable[dPiece[dx - 1][dy]];
        break;
    case 7:
        rv = !nSolidTable[dPiece[dx][dy - 1]] && !nSolidTable[dPiece[dx - 1][dy]];
        break;
    case 8:
        rv = !nSolidTable[dPiece[dx + 1][dy]] && !nSolidTable[dPiece[dx][dy - 1]];
        break;
    }
    return rv;
}
 
BOOL path_get_path(BOOL (*PosOk)(int, int, int), int PosOkArg, PATHNODE *pPath, int x, int y)
{
    int dx, dy;
    int i;
    BOOL ok;
 
    for (i = 0; i < 8; i++) {
        dx = pPath->x + pathxdir[i];
        dy = pPath->y + pathydir[i];
        ok = PosOk(PosOkArg, dx, dy);
        if (ok && path_solid_pieces(pPath, dx, dy) || !ok && dx == x && dy == y) {
            if (!path_parent_path(pPath, dx, dy, x, y))
                return FALSE;
        }
    }
 
    return TRUE;
}
 
BOOL path_parent_path(PATHNODE *pPath, int dx, int dy, int sx, int sy)
{
    int next_g;
    PATHNODE *dxdy;
    int i;
 
    next_g = pPath->g + path_check_equal(pPath, dx, dy);
 
    // 3 cases to consider
    // case 1: (dx,dy) is already on the frontier
    dxdy = path_get_node1(dx, dy);
    if (dxdy != NULL) {
        for (i = 0; i < 8; i++) {
            if (pPath->Child[i] == NULL)
                break;
        }
        pPath->Child[i] = dxdy;
        if (next_g < dxdy->g) {
            if (path_solid_pieces(pPath, dx, dy)) {
                // we'll explore it later, just update
                dxdy->Parent = pPath;
                dxdy->g = next_g;
                dxdy->f = next_g + dxdy->h;
            }
        }
    } else {
        // case 2: (dx,dy) was already visited
        dxdy = path_get_node2(dx, dy);
        if (dxdy != NULL) {
            for (i = 0; i < 8; i++) {
                if (pPath->Child[i] == NULL)
                    break;
            }
            pPath->Child[i] = dxdy;
            if (next_g < dxdy->g && path_solid_pieces(pPath, dx, dy)) {
                // update the node
                dxdy->Parent = pPath;
                dxdy->g = next_g;
                dxdy->f = next_g + dxdy->h;
                // already explored, so re-update others starting from that node
                path_set_coords(dxdy);
            }
        } else {
            // case 3: (dx,dy) is totally new
            dxdy = path_new_step();
            if (dxdy == NULL)
                return FALSE;
            dxdy->Parent = pPath;
            dxdy->g = next_g;
            dxdy->h = path_get_h_cost(dx, dy, sx, sy);
            dxdy->f = next_g + dxdy->h;
            dxdy->x = dx;
            dxdy->y = dy;
            // add it to the frontier
            path_next_node(dxdy);
 
            for (i = 0; i < 8; i++) {
                if (pPath->Child[i] == NULL)
                    break;
            }
            pPath->Child[i] = dxdy;
        }
    }
    return TRUE;
}
 
PATHNODE *path_get_node1(int dx, int dy)
{
    PATHNODE *result = path_2_nodes->NextNode;
    while (result != NULL && (result->x != dx || result->y != dy))
        result = result->NextNode;
    return result;
}
 
PATHNODE *path_get_node2(int dx, int dy)
{
    PATHNODE *result = pnode_ptr->NextNode;
    while (result != NULL && (result->x != dx || result->y != dy))
        result = result->NextNode;
    return result;
}
 
void path_next_node(PATHNODE *pPath)
{
    PATHNODE *next, *current;
    int f;
 
    next = path_2_nodes;
    if (!path_2_nodes->NextNode) {
        path_2_nodes->NextNode = pPath;
    } else {
        current = path_2_nodes;
        next = path_2_nodes->NextNode;
        f = pPath->f;
        while (next && next->f < f) {
            current = next;
            next = next->NextNode;
        }
        pPath->NextNode = next;
        current->NextNode = pPath;
    }
}
 
void path_set_coords(PATHNODE *pPath)
{
    PATHNODE *PathOld;
    PATHNODE *PathAct;
    int i;
 
    path_push_active_step(pPath);
    while (gdwCurPathStep) {
        PathOld = path_pop_active_step();
        for (i = 0; i < 8; i++) {
            PathAct = PathOld->Child[i];
            if (PathAct == NULL)
                break;
 
            if (PathOld->g + path_check_equal(PathOld, PathAct->x, PathAct->y) < PathAct->g) {
                if (path_solid_pieces(PathOld, PathAct->x, PathAct->y)) {
                    PathAct->Parent = PathOld;
                    PathAct->g = PathOld->g + path_check_equal(PathOld, PathAct->x, PathAct->y);
                    PathAct->f = PathAct->g + PathAct->h;
                    path_push_active_step(PathAct);
                }
            }
        }
    }
}
 
void path_push_active_step(PATHNODE *pPath)
{
    int stack_index = gdwCurPathStep;
    gdwCurPathStep++;
    pnode_tblptr[stack_index] = pPath;
}
 
PATHNODE *path_pop_active_step()
{
    gdwCurPathStep--;
    return pnode_tblptr[gdwCurPathStep];
}
 
PATHNODE *path_new_step()
{
    PATHNODE *new_node;
 
    if (gdwCurNodes == MAXPATHNODES)
        return NULL;
 
    new_node = &path_nodes[gdwCurNodes];
    gdwCurNodes++;
    memset(new_node, 0, sizeof(PATHNODE));
    return new_node;
}
 
DEVILUTION_END_NAMESPACE