1 /*- blockmap.c --------------------------------------------------------------*
2
3 Node builder for DOOM levels (c) 1998 Colin Reed, version 3.0 (dos extended)
4
5 Credit to:-
6
7 Raphael Quinet (A very small amount of code has been borrowed from DEU).
8
9 Matt Fell for the doom specs.
10
11 Lee Killough for performance tuning, support for multilevel wads, special
12 effects, and wads with lumps besides levels.
13
14 Also, the original idea for some of the techniques where also taken from the
15 comment at the bottom of OBJECTS.C in DEU, and the doc by Matt Fell about
16 the nodes.
17
18 Use this code for your own editors, but please credit me.
19
20 *---------------------------------------------------------------------------*/
21
22 /*
23 * Separated from bsp.c 2000/08/26 by Colin Phipps
24 */
25
26 #include "structs.h"
27 #include "bsp.h"
28
29 /*--------------------------------------------------------------------------*/
30
31 static int
IsLineDefInside(int ldnum,int xmin,int ymin,int xmax,int ymax)32 IsLineDefInside(int ldnum, int xmin, int ymin, int xmax, int ymax)
33 {
34 int x1 = vertices[linedefs[ldnum].start].x;
35 int y1 = vertices[linedefs[ldnum].start].y;
36 int x2 = vertices[linedefs[ldnum].end].x;
37 int y2 = vertices[linedefs[ldnum].end].y;
38 int count = 2;
39
40 for (;;)
41 if (y1 > ymax) {
42 if (y2 > ymax)
43 return (FALSE);
44 x1 = x1 + (x2 - x1) * (double) (ymax - y1) / (y2 - y1);
45 y1 = ymax;
46 count = 2;
47 } else if (y1 < ymin) {
48 if (y2 < ymin)
49 return (FALSE);
50 x1 = x1 + (x2 - x1) * (double) (ymin - y1) / (y2 - y1);
51 y1 = ymin;
52 count = 2;
53 } else if (x1 > xmax) {
54 if (x2 > xmax)
55 return (FALSE);
56 y1 = y1 + (y2 - y1) * (double) (xmax - x1) / (x2 - x1);
57 x1 = xmax;
58 count = 2;
59 } else if (x1 < xmin) {
60 if (x2 < xmin)
61 return (FALSE);
62 y1 = y1 + (y2 - y1) * (double) (xmin - x1) / (x2 - x1);
63 x1 = xmin;
64 count = 2;
65 } else {
66 int t;
67 if (!--count)
68 return (TRUE);
69 t = x1;
70 x1 = x2;
71 x2 = t;
72 t = y1;
73 y1 = y2;
74 y2 = t;
75 }
76 }
77
78 /*- Create blockmap --------------------------------------------------------*/
79
80 void
CreateBlockmap_old(const bbox_t bbox)81 CreateBlockmap_old(const bbox_t bbox)
82 {
83 struct Block blockhead;
84 short int *blockptrs;
85 short int *blocklists = NULL;
86 long blockptrs_size;
87
88 long blockoffs = 0;
89 int x, y, n;
90 int blocknum = 0;
91
92 Verbose("Creating Blockmap... ");
93
94 blockhead.minx = bbox[BB_LEFT] & -8;
95 blockhead.miny = bbox[BB_BOTTOM] & -8;
96 blockhead.xblocks = ((bbox[BB_RIGHT] - (bbox[BB_LEFT] & -8)) / 128) + 1;
97 blockhead.yblocks = ((bbox[BB_TOP] - (bbox[BB_BOTTOM] & -8)) / 128) + 1;
98
99 blockptrs_size = (blockhead.xblocks * blockhead.yblocks) * 2;
100 blockptrs = GetMemory(blockptrs_size);
101
102 for (y = 0; y < blockhead.yblocks; y++) {
103 for (x = 0; x < blockhead.xblocks; x++) {
104 progress();
105
106 blockptrs[blocknum] = (blockoffs + 4 + (blockptrs_size / 2));
107 swapshort((unsigned short *) blockptrs + blocknum);
108
109 blocklists = ResizeMemory(blocklists, ((blockoffs + 1) * 2));
110 blocklists[blockoffs] = 0;
111 blockoffs++;
112 for (n = 0; n < num_lines; n++) {
113 if (IsLineDefInside(n, (blockhead.minx + (x * 128)), (blockhead.miny + (y * 128)), (blockhead.minx + (x * 128)) + 127, (blockhead.miny + (y * 128)) + 127)) {
114 /*
115 * printf("found line %d in block
116 * %d\n",n,blocknum);
117 */
118 blocklists = ResizeMemory(blocklists, ((blockoffs + 1) * 2));
119 blocklists[blockoffs] = n;
120 swapshort((unsigned short *) blocklists + blockoffs);
121 blockoffs++;
122 }
123 }
124 blocklists = ResizeMemory(blocklists, ((blockoffs + 1) * 2));
125 blocklists[blockoffs] = -1;
126 swapshort((unsigned short *) blocklists + blockoffs);
127 blockoffs++;
128
129 blocknum++;
130 }
131 }
132 {
133 long blockmap_size = blockoffs * 2;
134 char *data = GetMemory(blockmap_size + blockptrs_size + 8);
135 memcpy(data, &blockhead, 8);
136 swapshort((unsigned short *) data + 0);
137 swapshort((unsigned short *) data + 1);
138 swapshort((unsigned short *) data + 2);
139 swapshort((unsigned short *) data + 3);
140 memcpy(data + 8, blockptrs, blockptrs_size);
141 memcpy(data + 8 + blockptrs_size, blocklists, blockmap_size);
142 free(blockptrs);
143 free(blocklists);
144 add_lump("BLOCKMAP", data, blockmap_size + blockptrs_size + 8);
145 }
146 Verbose("done.\n");
147 }
148
149 /*- Create blockmap (compressed) ----------------------------------------
150 * Contributed by Simon "fraggle" Howard <sdh300@ecs.soton.ac.uk>
151 * Merged 2001/11/17 */
152
153 struct blocklist_s {
154 int num_lines;
155 unsigned short offset;
156 unsigned short *lines;
157 struct blocklist_s *next; /* for hash table */
158 };
159
160 static struct blocklist_s **blockhash;
161 static int blockhash_size;
162 static int blocklist_size; /* size, in bytes of the blocklists */
163
164 /* offset pointers */
165
166 static struct blocklist_s **blockptrs;
167 static int num_blockptrs;
168
169 /* hashkey function for search */
170
blockhash_key(struct blocklist_s * bl)171 static int blockhash_key(struct blocklist_s *bl)
172 {
173 int i;
174 int hash = 0;
175
176 /* this is a pretty lame hash function
177 it has to be associative though (ie, 1 2 3 == 3 2 1) */
178
179 for(i=0; i<bl->num_lines; ++i)
180 hash += bl->lines[i];
181
182 return hash % blockhash_size;
183 }
184
185 /* compare two struct blocklist_s's
186 like strcmp: a 0 return value means they are identical */
187
blocklist_cmp(struct blocklist_s * bl1,struct blocklist_s * bl2)188 static int blocklist_cmp(struct blocklist_s *bl1, struct blocklist_s *bl2)
189 {
190 int i;
191
192 if(bl1->num_lines != bl2->num_lines)
193 return 1;
194
195 for(i=0; i<bl1->num_lines; ++i) {
196 if(bl1->lines[i] != bl2->lines[i])
197 return 1;
198 }
199
200 return 0;
201 }
202
203 /* search for an identical blocklist */
204
blockhash_search(struct blocklist_s * bl)205 static struct blocklist_s *blockhash_search(struct blocklist_s *bl)
206 {
207 int hash = blockhash_key(bl);
208 struct blocklist_s *search;
209
210 for(search=blockhash[hash]; search; search=search->next) {
211 if(!blocklist_cmp(bl, search))
212 return search;
213 }
214
215 /* not found */
216
217 return NULL;
218 }
219
220 /* add a new blocklist to the hashtable */
221
blockhash_add(struct blocklist_s * newbl)222 static struct blocklist_s *blockhash_add(struct blocklist_s *newbl)
223 {
224 struct blocklist_s *bl;
225 int hash;
226
227 /* first, check an identical one doesnt already exist */
228
229 bl = blockhash_search(newbl);
230
231 if(bl)
232 return bl;
233
234 /* need to add new blocklist */
235
236 /* make a copy */
237
238 bl = GetMemory(sizeof(*bl));
239 bl->num_lines = newbl->num_lines;
240 bl->lines = GetMemory(sizeof(*bl->lines) * bl->num_lines);
241 memcpy(bl->lines, newbl->lines,
242 sizeof(*bl->lines) * bl->num_lines);
243
244 /* link into hash table */
245
246 hash = blockhash_key(bl);
247
248 bl->next = blockhash[hash];
249 blockhash[hash] = bl;
250
251 /* maintain blocklist count */
252
253 blocklist_size += sizeof(*bl->lines) * bl->num_lines;
254
255 return bl;
256 }
257
blockmap_assemble(const struct Block * blockmaphead)258 static void blockmap_assemble(const struct Block* blockmaphead)
259 {
260 int i;
261 int offset;
262
263 /* build the lump itself */
264
265 size_t blockmap_size =
266 sizeof(*blockmaphead) +
267 num_blockptrs * sizeof(short) +
268 blocklist_size;
269 register short* blockmap = GetMemory(blockmap_size);
270
271 /* header */
272
273 memcpy(blockmap, blockmaphead, sizeof *blockmaphead);
274 swapshort(blockmap);
275 swapshort(blockmap+1);
276 swapshort(blockmap+2);
277 swapshort(blockmap+3);
278
279 /* every hash chain */
280
281 for(i=0,offset=num_blockptrs+sizeof(*blockmaphead)/sizeof(short);
282 i<blockhash_size; ++i) {
283 struct blocklist_s *bl;
284
285 /* every blocklist in the chain */
286
287 for(bl=blockhash[i]; bl; bl = bl->next) {
288
289 /* write */
290
291 int l;
292
293 /* offset is in short ints, not bytes */
294
295 bl->offset = offset;
296
297 /* write each line */
298
299 for(l=0; l<bl->num_lines; ++l) {
300 blockmap[offset] = bl->lines[l];
301 swapshort(blockmap + offset);
302 offset++;
303 }
304 }
305 }
306
307 offset = sizeof(*blockmaphead)/sizeof(short);
308
309 for(i=0; i<num_blockptrs; ++i) {
310 blockmap[offset+i] = blockptrs[i]->offset;
311 swapshort(blockmap+offset+i);
312 }
313
314 add_lump("BLOCKMAP", blockmap, blockmap_size);
315 }
316
317 void
CreateBlockmap_compressed(const bbox_t bbox)318 CreateBlockmap_compressed(const bbox_t bbox)
319 {
320 int x, y, n;
321 int blocknum = 0;
322 unsigned short *templines;
323 int num_templines;
324 struct Block blockhead;
325
326 fprintf(stderr,"Creating compressed blockmap... ");
327
328 /* header */
329
330 blockhead.minx = bbox[BB_LEFT] & -8;
331 blockhead.miny = bbox[BB_BOTTOM] & -8;
332 blockhead.xblocks = ((bbox[BB_RIGHT] - (bbox[BB_LEFT] & -8)) / 128) + 1;
333 blockhead.yblocks = ((bbox[BB_TOP] - (bbox[BB_BOTTOM] & -8)) / 128) + 1;
334
335 /* build hash table */
336
337 blockhash_size = blockhead.xblocks * blockhead.yblocks;
338 blockhash = GetMemory(blockhash_size * sizeof(*blockhash));
339 for(n=0; n<blockhash_size; ++n)
340 blockhash[n] = NULL;
341
342 /* pointers */
343
344 num_blockptrs = blockhead.xblocks * blockhead.yblocks;
345 blockptrs = GetMemory(num_blockptrs * sizeof(*blockptrs));
346
347 num_templines = 10240;
348 templines = GetMemory(num_templines * sizeof(*templines));
349
350 /* build all blocklists */
351
352 for (y = 0; y < blockhead.yblocks; y++) {
353 for (x = 0; x < blockhead.xblocks; x++) {
354 struct blocklist_s tempbl;
355
356 tempbl.num_lines = 0;
357 tempbl.lines = templines;
358
359 progress();
360
361 /* first line is a 0 */
362
363 tempbl.lines[tempbl.num_lines++] = 0;
364
365 for (n = 0; n < num_lines; n++) {
366 if (IsLineDefInside(n, (blockhead.minx + (x * 128)), (blockhead.miny + (y * 128)), (blockhead.minx + (x * 128)) + 127, (blockhead.miny + (y * 128)) + 127)) {
367 /*
368 * printf("found line %d in block
369 * %d\n",n,blocknum);
370 */
371
372 if(tempbl.num_lines >= num_templines-5) {
373 num_lines *= 2;
374 templines = ResizeMemory(templines,
375 num_templines * sizeof(*templines));
376 tempbl.lines = templines;
377 }
378
379 tempbl.lines[tempbl.num_lines++] = n;
380 }
381 }
382
383 /* last is 0xffff */
384
385 tempbl.lines[tempbl.num_lines++] = 0xffff;
386
387 blockptrs[blocknum++] = blockhash_add(&tempbl);
388 }
389 }
390
391 free(templines);
392
393 /* assemble */
394
395 blockmap_assemble(&blockhead);
396
397 /* deconstruct the hash table */
398
399 for(n=0; n<blockhash_size; ++n) {
400 while(blockhash[n]) {
401 struct blocklist_s *del = blockhash[n];
402 blockhash[n] = blockhash[n]->next;
403 free(del->lines);
404 free(del);
405 }
406 }
407
408 free(blockhash);
409 free(blockptrs);
410
411 Verbose("done.\n");
412
413 return;
414 }
415
416