/*----------------------------------------------------------------------------* | This file is part of DEU (Doom Editing Utilities), created by the DEU team:| | Raphael Quinet, Brendon Wyber, Ted Vessenes and others. See README.1ST or | | the "about" dialog box for full credits. | | | | DEU is an open project: if you think that you can contribute, please join | | the DEU team. You will be credited for any code (or ideas) included in | | the next version of the program. | | | | If you want to make any modifications and re-distribute them on your own, | | you must follow the conditions of the DEU license. Read the file LICENSE | | in this directory or README.1ST in the top directory. If do not have a | | copy of these files, you can request them from any member of the DEU team, | | or by mail: Raphael Quinet, Rue des Martyrs 9, B-4550 Nandrin (Belgium). | | | | This program comes with absolutely no warranty. Use it at your own risks! | *----------------------------------------------------------------------------* B_BLOCK.C - BlockMap builder Created on Jun 9 1994 by Johannes Plass Converted to DEU 5.3 style on Jan 24 1995 by Renaud Paquay */ /* Includes */ #include "deu.h" #include "w_levels.h" /* LevelInfo */ #include "d_misc.h" /* GetFarMemory() */ #include "b_block.h" /* MakeBlockMap() proto */ #include /*RP added to assert some array accesses */ #include /* Macros RP: Removed! Apr 15 1995 */ /* #define VSX(lll) (level->vertexes[level->linedefs[lll].start].x) #define VSY(lll) (level->vertexes[level->linedefs[lll].start].y) #define VEX(lll) (level->vertexes[level->linedefs[lll].end].x) #define VEY(lll) (level->vertexes[level->linedefs[lll].end].y) #define VX(vvv) level->vertexes[vvv].x #define VY(vvv) level->vertexes[vvv].y #define NUM_LINES level->num_linedefs #define NUM_VERT level->num_vertexes #define SIGN(sss) ((sss) >= 0 ? 1 : -1) */ /*! comment missing */ /* RP Comment on this function: This function adds a line index ('lndx') at the end of the 'block'. Parameters: . (*block) is an array of indexes, growing 5 by 5, and terminated by a -1. A zero entry means 'free entry'. A > 0 entry means a line index of 'entry - 1', because we store 'line index + 1'. . lndx is the line index to add to the end of the block. In fact, lndx+1 is stored, to be able to distinguish free entries (0) and line index entries (>0). RP: I think the bug there was the author forgot to zero init the array entries after a GetMemory, because GetMemory doesn't guarantee a zeroed allocated space. */ void AddLineToBlock(Int16 **block, Int16 lndx) { register Int16 k, j; /*RP no entries, allocate 5 free entries */ if ( *block == NULL ) { *block = (Int16 *)GetMemory(sizeof(Int16) * 5); /*RP Added this: Init. array with 0's (=free entries)*/ for (j = 0 ; j < 4 ; j++) (*block)[j] = 0; /*RP Add end marker */ (*block)[4] = -1; k = 0; } /*RP look for an free entry, or allocate 5 more */ else { /*RP Go to end of array (-1 entry) */ for (k = 0; (*block)[k] > 0; k++); /*RP If end of array, add 5 0's and one -1 */ if ((*block)[k] == -1) { /*RP Added assert here to check coherency of entries. Since we allocate 5 entries at a time, 'k+1' must be divisible by 5 */ assert( (k+1) % 5 == 0); /*RP 5 more entries (and +1 to transform index into number) */ j = k + 5 + 1; *block= (Int16*)ResizeMemory(*block, j * sizeof(Int16)); /*RP Zero init new (free) entries */ for (j = 0; j < 5; j ++) (*block)[k + j] = 0; /*RP End of array marker */ (*block)[k + 5] = -1; } } /*RP Add the line index (+1, since 0 means free entry) */ (*block)[k] = lndx + 1; } /*! comment missing */ /*! RP there's a lot of 'Conversion may loose significiant digit' in this function. Maybe we should change some Int32 vars to Int16. The original declaration of Int32 vars was 'long' */ void *MakeBlockmap(LevelPtr level, UInt32 *blockmapsize) { Int16 xmin, ymin, xmax,ymax; /* map coords min/max */ Int32 scl = 100000L; /* line following scaling */ Int32 size = 128L; /* block size (map coords) */ Int16 x0, y0; /* blockmap x,y origin */ Int16 xn, yn; /* # blocks in x,y dirs */ Int32 xcc, xcl; Int32 xs, xe, ys, ye; Int32 xd, yd; /* x direction, y direction */ Int16 o; /* o = index to origin of blockmap array */ Int16 t; /* t = index in blockmap array */ Int32 m; register Int16 **boxlist; /* array of blocks' lists */ Int16 b, p = 0, c = 0, i, l, k; Int16 *blockmap; /*RP Setup min and max coords of vertices */ xmin = 32767; xmax = -32767; ymin = 32767; ymax = -32767; for (i = 0; i < level->num_vertexes; i++) { VPtr v = &level->vertexes[i]; if (v->x < xmin) xmin = v->x; if (v->x > xmax) xmax = v->x; if (v->y < ymin) ymin = v->y; if (v->y > ymax) ymax = v->y; } x0 = xmin - 8; y0 = ymin - 8; /*RP Setup number of blocks */ xn = (Int16) ((xmax - xmin + size) / size); yn = (Int16) ((ymax - ymin + size) / size); /*RP BUG: Replaced sizeof(Int16) by sizeof(Int16 *) */ boxlist = (Int16 **)GetMemory(sizeof(Int16 *) * (xn * yn)); /*RP Added this: Init. pointers to NULL in array */ for (i = 0 ; i < xn * yn ; i++) boxlist[i] = NULL; t = 0; /* scan LINEDEFS here */ for (l = 0; l < level->num_linedefs; l++) { LDPtr pld = &level->linedefs[l]; VPtr vs = &level->vertexes[pld->start]; VPtr ve = &level->vertexes[pld->end]; xs = vs->x - x0; ys = vs->y - y0; xe = ve->x - x0; ye = ve->y - y0; xd = (xe - xs) > 0 ? 1 : -1; yd = (ye - ys) > 0 ? 1 : -1; switch (2 * (xe / size == xs / size) + (ye / size == ys/size)) { case 0: c = 0; p = yd * xn; break; case 1: c = abs(xe / size - xs / size) + 1; p = xd; break; case 2: c = abs(ye / size - ys / size) + 1; p = yd * xn; break; case 3: c = 0 + 1; p = 1; break; } b = xs / size + xn * (ys / size); for (i = 0; i < c; i ++, b += p) { /*RP Added assert here */ assert(b < (xn * yn)); AddLineToBlock(&(boxlist[b]), l); t ++; } if (! c) { m = (scl * (ye - ys)) / (xe - xs); xcl = xs; if (yd == -1) xcc = xs + (m / 2 + scl * ((ys / size) * size - 1 - ys)) / m; else xcc = xs + (m / 2 + scl * ((ys / size) * size + 128 - ys)) / m; do { for (c = 0; c < abs(xcc / size - xcl / size) + 1; c++, b += xd) { /*RP Added assert here */ assert(b < (xn * yn)); AddLineToBlock(&(boxlist[b]), l); t ++; } b += p - xd; xcl = xcc; xcc += (yd * scl * size) / m; if (xd * xcc > xd * xe) xcc = xe; } while (xd * xcl < xd * xe); } } /*RP Allocates blockmap bits */ *blockmapsize = (4 + xn * yn + t + 2 * xn * yn) * sizeof(Int16); /*RP added assert here */ assert(*blockmapsize < 65536L); blockmap = (Int16 *)GetMemory((UInt16)*blockmapsize); t = 0; blockmap[t++] = x0; blockmap[t++] = y0; blockmap[t++] = xn; blockmap[t++] = yn; o = t; t += xn * yn; /* insert the data */ for (i = 0 ; i < xn * yn; i++) { /*RP added assert here */ assert (o < *blockmapsize); assert (t < *blockmapsize); blockmap[o++] = t; blockmap[t++] = 0; if (boxlist[i]) { for (k = 0; boxlist[i][k] > 0; k++) { /*RP added assert here */ assert (t < *blockmapsize); assert (i < (xn * yn)); blockmap[t++] = boxlist[i][k] - 1; } /*RP added assert here */ assert (i < (xn * yn)); FreeMemory(boxlist[i]); } /*RP added assert here */ assert (t < *blockmapsize); blockmap[t++] = -1; } FreeMemory(boxlist); return blockmap; }