diff options
author | Max Horn | 2003-06-08 17:59:09 +0000 |
---|---|---|
committer | Max Horn | 2003-06-08 17:59:09 +0000 |
commit | f034b339cd5251fc2017973939e6c5bf980a0fe3 (patch) | |
tree | ca526ff5929f4425e7d78b500ecd771a5bddd6c6 /scumm/boxes.cpp | |
parent | ab7f8b337869b367a7a18d6235a9b481f9d05cfb (diff) | |
download | scummvm-rg350-f034b339cd5251fc2017973939e6c5bf980a0fe3.tar.gz scummvm-rg350-f034b339cd5251fc2017973939e6c5bf980a0fe3.tar.bz2 scummvm-rg350-f034b339cd5251fc2017973939e6c5bf980a0fe3.zip |
reimplemented createBoxMatrix; this is much cleaner and easier to understand than the original code (IMHO); in a few cases it gives slightly different results (because the old code didn't always find the shortest path), but that shouldn't cause any problems
svn-id: r8403
Diffstat (limited to 'scumm/boxes.cpp')
-rw-r--r-- | scumm/boxes.cpp | 316 |
1 files changed, 106 insertions, 210 deletions
diff --git a/scumm/boxes.cpp b/scumm/boxes.cpp index ae320bebc8..78fe56bdba 100644 --- a/scumm/boxes.cpp +++ b/scumm/boxes.cpp @@ -73,17 +73,8 @@ struct Box { /* Internal walkbox file format */ #pragma END_PACK_STRUCTS #endif -struct PathNode { /* Linked list of walkpath nodes */ - uint index; - struct PathNode *left, *right; -}; - -struct PathVertex { /* Linked list of walkpath nodes */ - PathNode *left; - PathNode *right; -}; - #define BOX_MATRIX_SIZE 2000 +#define BOX_DEBUG 0 static bool compareSlope(int X1, int Y1, int X2, int Y2, int X3, int Y3); @@ -750,233 +741,138 @@ bool Actor::findPathTowards(byte box1nr, byte box2nr, byte box3nr, int16 &foundP return false; } - -class BoxHeap { - int heapSize, heapCurrentIndex; - byte *heapCurrent, *heapStart; - - void *getHeapBlock(int size) { - byte *ptr = heapCurrent; - - heapCurrent += size; - heapCurrentIndex += size; - - if (heapCurrentIndex >= heapSize) - error("Box path vertex heap overflow"); - - return ptr; - } - -public: - BoxHeap() { - heapSize = 1000; - heapStart = heapCurrent = (byte *)calloc(heapSize, 1); - heapCurrentIndex = 0; - } - - ~BoxHeap() { - free(heapStart); - } - - PathNode *unkMatrixProc2(PathVertex *vtx, int i) { - PathNode *node; - - if (vtx == NULL) - return NULL; - - node = (PathNode *)getHeapBlock(sizeof(PathNode)); - node->index = i; - node->left = 0; - node->right = 0; - - if (!vtx->right) { - vtx->left = node; - } else { - vtx->right->left = node; - node->right = vtx->right; +#if BOX_DEBUG +static void printMatrix(byte *boxm, int num) { + int i; + for (i = 0; i < num; i++) { + printf("%d: ", i); + while (*boxm != 0xFF) { + printf("%d, ", *boxm); + boxm++; } - - vtx->right = node; - - return vtx->right; - } - - - PathVertex *newPathVertex() { - // Reset the heap - heapCurrent = heapStart; - heapCurrentIndex = 0; - - // Add a single new PathVertex to the heap - return (PathVertex *)getHeapBlock(sizeof(PathVertex)); - } - -}; - -class BoxMatrix { - int matrixSize; - byte *matrixPtr; - -public: - BoxMatrix(byte *matrix) { - assert(matrix); - matrixSize = 0; - matrixPtr = matrix; - } - - void add(byte b) { - if (++matrixSize > BOX_MATRIX_SIZE) - error("Box matrix overflow"); - *matrixPtr++ = b; - } -}; - - -PathVertex *unkMatrixProc1(PathVertex *vtx, PathNode *node) { - if (node == NULL || vtx == NULL) - return NULL; - - if (!node->right) { - vtx->left = node->left; - } else { - node->right->left = node->left; + boxm++; + printf("\n"); } +} - if (!node->left) { - vtx->right = node->right; - } else { - node->left->right = node->right; +static void printMatrix2(byte *matrix, int num) { + int i, j; + printf(" "); + for (i = 0; i < num; i++) + printf("%2d ", i); + printf("\n"); + for (i = 0; i < num; i++) { + printf("%2d: ", i); + for (j = 0; j < num; j++) { + int val = matrix[i * 64 + j]; + if (val == 250) + printf(" ? "); + else + printf("%2d ", val); + } + printf("\n"); } - - if (vtx->left) - return vtx; - - return NULL; } +#endif void Scumm::createBoxMatrix() { - int num, i, j; - byte flags; - int table_1[66], table_2[66]; - int counter, val; - int code; - byte *distanceMatrix; - - - // A heap (an optiimsation to avoid calling malloc/free extremly often) - BoxHeap heap; - - // Temporary 64*65 distance matrix - distanceMatrix = (byte *)calloc(65, 64); - - // The result "matrix" in the special format used by Scumm. - BoxMatrix boxMatrix(createResource(rtMatrix, 1, BOX_MATRIX_SIZE)); + int num, i, j, k; + byte *adjacentMatrix, *itineraryMatrix; + // The total number of boxes num = getNumBoxes(); + assert(num <= 64); + + // Allocate the adjacent & itinerary matrices + adjacentMatrix = (byte *)malloc(64 * 64); + itineraryMatrix = (byte *)malloc(64 * 64); - // Initialise the distance matrix: each box has distance 0 to itself, + // Initialise the adjacent matrix: each box has distance 0 to itself, // and distance 1 to its direct neighbors. Initially, it has distance - // 250 (= infinity) to all other boxes. + // 255 (= infinity) to all other boxes. for (i = 0; i < num; i++) { for (j = 0; j < num; j++) { if (i == j) { - distanceMatrix[i * 64 + j] = 0; + adjacentMatrix[i * 64 + j] = 0; + itineraryMatrix[i * 64 + j] = j; } else if (areBoxesNeighbours(i, j)) { - distanceMatrix[i * 64 + j] = 1; + adjacentMatrix[i * 64 + j] = 1; + itineraryMatrix[i * 64 + j] = j; } else { - distanceMatrix[i * 64 + j] = 250; + adjacentMatrix[i * 64 + j] = 255; + itineraryMatrix[i * 64 + j] = 0; } } } - - // Iterate over all boxes - for (j = 0; j < num; j++) { - flags = getBoxFlags(j); - if (flags & kBoxInvisible) { - // Locked/invisible boxes are only reachable from themselves. - boxMatrix.add(0xFF); - boxMatrix.add(j); - boxMatrix.add(j); - boxMatrix.add(j); - } else { - PathNode *node, *node2 = NULL; - PathVertex *vtx = heap.newPathVertex(); - for (i = 0; i < num; i++) { - flags = getBoxFlags(j); - if (!(flags & kBoxInvisible)) { - node = heap.unkMatrixProc2(vtx, i); - if (i == j) - node2 = node; - } - } - table_1[j] = 0; - table_2[j] = j; - vtx = unkMatrixProc1(vtx, node2); - node = vtx ? vtx->left : NULL; - - counter = 250; - while (node) { - val = distanceMatrix[j * 64 + node->index]; - table_1[node->index] = val; - if (val < counter) - counter = val; - - if (table_1[node->index] != 250) - table_2[node->index] = node->index; - else - table_2[node->index] = -1; - - node = node->left; - } - while (vtx) { - counter = 250; - node2 = node = vtx->left; - - while (node) { - if (table_1[node->index] < counter) { - counter = table_1[node->index]; - node2 = node; - } - node = node->left; - } - vtx = unkMatrixProc1(vtx, node2); - node = vtx ? vtx->left : NULL; - while (node) { - code = distanceMatrix[node2->index * 64 + node->index]; - code += table_1[node2->index]; - if (code < table_1[node->index]) { - table_1[node->index] = code; - table_2[node->index] = table_2[node2->index]; - } - node = node->left; + // Compute the shortest routes between boxes via Kleene's algorithm. + // The original code used some kind of mangled Dijkstra's algorithm; + // while that might in theory be slightly faster, it was + // a) extremly obfuscated + // b) incorrect: it didn't always find the shortest paths + // c) not any faster in reality for our sparse & small adjacent matrices + for (k = 1; k < num; k++) { + for (i = 1; i < num; i++) { + for (j = 1; j < num; j++) { + if (i == j) + continue; + byte distIK = adjacentMatrix[64 * i + k]; + byte distKJ = adjacentMatrix[64 * k + j]; + if (adjacentMatrix[64 * i + j] > distIK + distKJ) { + adjacentMatrix[64 * i + j] = distIK + distKJ; + itineraryMatrix[64 * i + j] = itineraryMatrix[64 * i + k]; } } + } + + } - boxMatrix.add(0xFF); - for (i = 1; i < num; i++) { - if (table_2[i - 1] != -1) { - boxMatrix.add(i - 1); /* lo */ - while (table_2[i - 1] == table_2[i]) { - ++i; - if (i == num) - break; - } - boxMatrix.add(i - 1); /* hi */ - boxMatrix.add(table_2[i - 1]); /* dst */ - } - } - if (i == num && table_2[i - 1] != -1) { - boxMatrix.add(i - 1); /* lo */ - boxMatrix.add(i - 1); /* hi */ - boxMatrix.add(table_2[i - 1]); /* dest */ + // "Compress" the distance matrix into the box matrix format used + // by the engine. The format is like this: + // For each box (from 0 to num) there is first a byte with value 0xFF, + // followed by an arbitrary number of byte triples; the end is marked + // again by the lead 0xFF for the next "row". The meaning of the + // byte triples is as follows: the first two bytes define a range + // of box numbers (e.g. 7-11), while the third byte defines an + // itineray box. Assuming we are in the 5th "row" and encounter + // the triplet 7,11,15: this means to get from box 5 to any of + // the boxes 7,8,9,10,11 the shortest way is to go via box 15. + // See also getPathToDestBox. + + byte *matrixStart = createResource(rtMatrix, 1, BOX_MATRIX_SIZE); + const byte *matrixEnd = matrixStart + BOX_MATRIX_SIZE; + + #define addToMatrix(b) do { *matrixStart++ = (b); assert(matrixStart < matrixEnd); } while (0) + + addToMatrix(0xFF); + addToMatrix(0); + addToMatrix(0); + addToMatrix(0); + for (i = 1; i < num; i++) { + addToMatrix(0xFF); + for (j = 1; j < num; j++) { + byte itinerary = itineraryMatrix[64 * i + j]; + if (itinerary != 0) { + addToMatrix(j); + while (j < num && itinerary == itineraryMatrix[64 * i + (j + 1)]) + j++; + addToMatrix(j); + addToMatrix(itinerary); } } } - - boxMatrix.add(0xFF); + addToMatrix(0xFF); - free(distanceMatrix); + +#if BOX_DEBUG + printf("Itinerary matrix:\n"); + printMatrix2(itineraryMatrix, num); + printf("compressed matrix:\n"); + printMatrix(getBoxMatrixBaseAddr(), num); +#endif + + free(adjacentMatrix); + free(itineraryMatrix); } /** Check if two boxes are neighbours. */ |