diff options
Diffstat (limited to 'apps/plugins/doom/p_maputl.c')
-rw-r--r-- | apps/plugins/doom/p_maputl.c | 700 |
1 files changed, 700 insertions, 0 deletions
diff --git a/apps/plugins/doom/p_maputl.c b/apps/plugins/doom/p_maputl.c new file mode 100644 index 0000000000..a2ef132d11 --- /dev/null +++ b/apps/plugins/doom/p_maputl.c | |||
@@ -0,0 +1,700 @@ | |||
1 | /* Emacs style mode select -*- C++ -*- | ||
2 | *----------------------------------------------------------------------------- | ||
3 | * | ||
4 | * | ||
5 | * PrBoom a Doom port merged with LxDoom and LSDLDoom | ||
6 | * based on BOOM, a modified and improved DOOM engine | ||
7 | * Copyright (C) 1999 by | ||
8 | * id Software, Chi Hoang, Lee Killough, Jim Flynn, Rand Phares, Ty Halderman | ||
9 | * Copyright (C) 1999-2000 by | ||
10 | * Jess Haas, Nicolas Kalkhof, Colin Phipps, Florian Schulze | ||
11 | * | ||
12 | * This program is free software; you can redistribute it and/or | ||
13 | * modify it under the terms of the GNU General Public License | ||
14 | * as published by the Free Software Foundation; either version 2 | ||
15 | * of the License, or (at your option) any later version. | ||
16 | * | ||
17 | * This program is distributed in the hope that it will be useful, | ||
18 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | ||
19 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | ||
20 | * GNU General Public License for more details. | ||
21 | * | ||
22 | * You should have received a copy of the GNU General Public License | ||
23 | * along with this program; if not, write to the Free Software | ||
24 | * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA | ||
25 | * 02111-1307, USA. | ||
26 | * | ||
27 | * DESCRIPTION: | ||
28 | * Movement/collision utility functions, | ||
29 | * as used by function in p_map.c. | ||
30 | * BLOCKMAP Iterator functions, | ||
31 | * and some PIT_* functions to use for iteration. | ||
32 | * | ||
33 | *-----------------------------------------------------------------------------*/ | ||
34 | |||
35 | #include "doomstat.h" | ||
36 | #include "m_bbox.h" | ||
37 | #include "r_main.h" | ||
38 | #include "p_maputl.h" | ||
39 | #include "p_map.h" | ||
40 | #include "p_setup.h" | ||
41 | #include "rockmacros.h" | ||
42 | // | ||
43 | // P_AproxDistance | ||
44 | // Gives an estimation of distance (not exact) | ||
45 | // | ||
46 | |||
47 | fixed_t CONSTFUNC P_AproxDistance(fixed_t dx, fixed_t dy) | ||
48 | { | ||
49 | dx = D_abs(dx); | ||
50 | dy = D_abs(dy); | ||
51 | if (dx < dy) | ||
52 | return dx+dy-(dx>>1); | ||
53 | return dx+dy-(dy>>1); | ||
54 | } | ||
55 | |||
56 | // | ||
57 | // P_PointOnLineSide | ||
58 | // Returns 0 or 1 | ||
59 | // | ||
60 | // killough 5/3/98: reformatted, cleaned up | ||
61 | |||
62 | int CONSTFUNC P_PointOnLineSide(fixed_t x, fixed_t y, const line_t *line) | ||
63 | { | ||
64 | return | ||
65 | !line->dx ? x <= line->v1->x ? line->dy > 0 : line->dy < 0 : | ||
66 | !line->dy ? y <= line->v1->y ? line->dx < 0 : line->dx > 0 : | ||
67 | FixedMul(y-line->v1->y, line->dx>>FRACBITS) >= | ||
68 | FixedMul(line->dy>>FRACBITS, x-line->v1->x); | ||
69 | } | ||
70 | |||
71 | // | ||
72 | // P_BoxOnLineSide | ||
73 | // Considers the line to be infinite | ||
74 | // Returns side 0 or 1, -1 if box crosses the line. | ||
75 | // | ||
76 | // killough 5/3/98: reformatted, cleaned up | ||
77 | |||
78 | int CONSTFUNC P_BoxOnLineSide(const fixed_t *tmbox, const line_t *ld) | ||
79 | { | ||
80 | switch (ld->slopetype) | ||
81 | { | ||
82 | int p; | ||
83 | default: // shut up compiler warnings -- killough | ||
84 | case ST_HORIZONTAL: | ||
85 | return | ||
86 | (tmbox[BOXBOTTOM] > ld->v1->y) == (p = tmbox[BOXTOP] > ld->v1->y) ? | ||
87 | p ^ (ld->dx < 0) : -1; | ||
88 | case ST_VERTICAL: | ||
89 | return | ||
90 | (tmbox[BOXLEFT] < ld->v1->x) == (p = tmbox[BOXRIGHT] < ld->v1->x) ? | ||
91 | p ^ (ld->dy < 0) : -1; | ||
92 | case ST_POSITIVE: | ||
93 | return | ||
94 | P_PointOnLineSide(tmbox[BOXRIGHT], tmbox[BOXBOTTOM], ld) == | ||
95 | (p = P_PointOnLineSide(tmbox[BOXLEFT], tmbox[BOXTOP], ld)) ? p : -1; | ||
96 | case ST_NEGATIVE: | ||
97 | return | ||
98 | (P_PointOnLineSide(tmbox[BOXLEFT], tmbox[BOXBOTTOM], ld)) == | ||
99 | (p = P_PointOnLineSide(tmbox[BOXRIGHT], tmbox[BOXTOP], ld)) ? p : -1; | ||
100 | } | ||
101 | } | ||
102 | |||
103 | // | ||
104 | // P_PointOnDivlineSide | ||
105 | // Returns 0 or 1. | ||
106 | // | ||
107 | // killough 5/3/98: reformatted, cleaned up | ||
108 | |||
109 | int CONSTFUNC P_PointOnDivlineSide(fixed_t x, fixed_t y, const divline_t *line) | ||
110 | { | ||
111 | return | ||
112 | !line->dx ? x <= line->x ? line->dy > 0 : line->dy < 0 : | ||
113 | !line->dy ? y <= line->y ? line->dx < 0 : line->dx > 0 : | ||
114 | (line->dy^line->dx^(x -= line->x)^(y -= line->y)) < 0 ? (line->dy^x) < 0 : | ||
115 | FixedMul(y>>8, line->dx>>8) >= FixedMul(line->dy>>8, x>>8); | ||
116 | } | ||
117 | |||
118 | // | ||
119 | // P_MakeDivline | ||
120 | // | ||
121 | |||
122 | void P_MakeDivline(const line_t *li, divline_t *dl) | ||
123 | { | ||
124 | dl->x = li->v1->x; | ||
125 | dl->y = li->v1->y; | ||
126 | dl->dx = li->dx; | ||
127 | dl->dy = li->dy; | ||
128 | } | ||
129 | |||
130 | // | ||
131 | // P_InterceptVector | ||
132 | // Returns the fractional intercept point | ||
133 | // along the first divline. | ||
134 | // This is only called by the addthings | ||
135 | // and addlines traversers. | ||
136 | // | ||
137 | // killough 5/3/98: reformatted, cleaned up | ||
138 | |||
139 | fixed_t CONSTFUNC P_InterceptVector(const divline_t *v2, const divline_t *v1) | ||
140 | { | ||
141 | fixed_t den = FixedMul(v1->dy>>8, v2->dx) - FixedMul(v1->dx>>8, v2->dy); | ||
142 | return den ? FixedDiv((FixedMul((v1->x-v2->x)>>8, v1->dy) + | ||
143 | FixedMul((v2->y-v1->y)>>8, v1->dx)), den) : 0; | ||
144 | } | ||
145 | |||
146 | // | ||
147 | // P_LineOpening | ||
148 | // Sets opentop and openbottom to the window | ||
149 | // through a two sided line. | ||
150 | // OPTIMIZE: keep this precalculated | ||
151 | // | ||
152 | |||
153 | fixed_t opentop; | ||
154 | fixed_t openbottom; | ||
155 | fixed_t openrange; | ||
156 | fixed_t lowfloor; | ||
157 | |||
158 | // moved front and back outside P-LineOpening and changed // phares 3/7/98 | ||
159 | // them to these so we can pick up the new friction value | ||
160 | // in PIT_CheckLine() | ||
161 | sector_t *openfrontsector; // made global // phares | ||
162 | sector_t *openbacksector; // made global | ||
163 | |||
164 | void P_LineOpening(const line_t *linedef) | ||
165 | { | ||
166 | if (linedef->sidenum[1] == -1) // single sided line | ||
167 | { | ||
168 | openrange = 0; | ||
169 | return; | ||
170 | } | ||
171 | |||
172 | openfrontsector = linedef->frontsector; | ||
173 | openbacksector = linedef->backsector; | ||
174 | |||
175 | if (openfrontsector->ceilingheight < openbacksector->ceilingheight) | ||
176 | opentop = openfrontsector->ceilingheight; | ||
177 | else | ||
178 | opentop = openbacksector->ceilingheight; | ||
179 | |||
180 | if (openfrontsector->floorheight > openbacksector->floorheight) | ||
181 | { | ||
182 | openbottom = openfrontsector->floorheight; | ||
183 | lowfloor = openbacksector->floorheight; | ||
184 | } | ||
185 | else | ||
186 | { | ||
187 | openbottom = openbacksector->floorheight; | ||
188 | lowfloor = openfrontsector->floorheight; | ||
189 | } | ||
190 | openrange = opentop - openbottom; | ||
191 | } | ||
192 | |||
193 | // | ||
194 | // THING POSITION SETTING | ||
195 | // | ||
196 | |||
197 | // | ||
198 | // P_UnsetThingPosition | ||
199 | // Unlinks a thing from block map and sectors. | ||
200 | // On each position change, BLOCKMAP and other | ||
201 | // lookups maintaining lists ot things inside | ||
202 | // these structures need to be updated. | ||
203 | // | ||
204 | |||
205 | void P_UnsetThingPosition (mobj_t *thing) | ||
206 | { | ||
207 | if (!(thing->flags & MF_NOSECTOR)) | ||
208 | { | ||
209 | /* invisible things don't need to be in sector list | ||
210 | * unlink from subsector | ||
211 | * | ||
212 | * killough 8/11/98: simpler scheme using pointers-to-pointers for prev | ||
213 | * pointers, allows head node pointers to be treated like everything else | ||
214 | */ | ||
215 | |||
216 | mobj_t **sprev = thing->sprev; | ||
217 | mobj_t *snext = thing->snext; | ||
218 | if ((*sprev = snext)) // unlink from sector list | ||
219 | snext->sprev = sprev; | ||
220 | |||
221 | // phares 3/14/98 | ||
222 | // | ||
223 | // Save the sector list pointed to by touching_sectorlist. | ||
224 | // In P_SetThingPosition, we'll keep any nodes that represent | ||
225 | // sectors the Thing still touches. We'll add new ones then, and | ||
226 | // delete any nodes for sectors the Thing has vacated. Then we'll | ||
227 | // put it back into touching_sectorlist. It's done this way to | ||
228 | // avoid a lot of deleting/creating for nodes, when most of the | ||
229 | // time you just get back what you deleted anyway. | ||
230 | // | ||
231 | // If this Thing is being removed entirely, then the calling | ||
232 | // routine will clear out the nodes in sector_list. | ||
233 | |||
234 | sector_list = thing->touching_sectorlist; | ||
235 | thing->touching_sectorlist = NULL; //to be restored by P_SetThingPosition | ||
236 | } | ||
237 | |||
238 | if (!(thing->flags & MF_NOBLOCKMAP)) | ||
239 | { | ||
240 | /* inert things don't need to be in blockmap | ||
241 | * | ||
242 | * killough 8/11/98: simpler scheme using pointers-to-pointers for prev | ||
243 | * pointers, allows head node pointers to be treated like everything else | ||
244 | * | ||
245 | * Also more robust, since it doesn't depend on current position for | ||
246 | * unlinking. Old method required computing head node based on position | ||
247 | * at time of unlinking, assuming it was the same position as during | ||
248 | * linking. | ||
249 | */ | ||
250 | |||
251 | mobj_t *bnext, **bprev = thing->bprev; | ||
252 | if (bprev && (*bprev = bnext = thing->bnext)) // unlink from block map | ||
253 | bnext->bprev = bprev; | ||
254 | } | ||
255 | } | ||
256 | |||
257 | // | ||
258 | // P_SetThingPosition | ||
259 | // Links a thing into both a block and a subsector | ||
260 | // based on it's x y. | ||
261 | // Sets thing->subsector properly | ||
262 | // | ||
263 | // killough 5/3/98: reformatted, cleaned up | ||
264 | |||
265 | void P_SetThingPosition(mobj_t *thing) | ||
266 | { // link into subsector | ||
267 | subsector_t *ss = thing->subsector = R_PointInSubsector(thing->x, thing->y); | ||
268 | if (!(thing->flags & MF_NOSECTOR)) | ||
269 | { | ||
270 | // invisible things don't go into the sector links | ||
271 | |||
272 | // killough 8/11/98: simpler scheme using pointer-to-pointer prev | ||
273 | // pointers, allows head nodes to be treated like everything else | ||
274 | |||
275 | mobj_t **link = &ss->sector->thinglist; | ||
276 | mobj_t *snext = *link; | ||
277 | if ((thing->snext = snext)) | ||
278 | snext->sprev = &thing->snext; | ||
279 | thing->sprev = link; | ||
280 | *link = thing; | ||
281 | |||
282 | // phares 3/16/98 | ||
283 | // | ||
284 | // If sector_list isn't NULL, it has a collection of sector | ||
285 | // nodes that were just removed from this Thing. | ||
286 | |||
287 | // Collect the sectors the object will live in by looking at | ||
288 | // the existing sector_list and adding new nodes and deleting | ||
289 | // obsolete ones. | ||
290 | |||
291 | // When a node is deleted, its sector links (the links starting | ||
292 | // at sector_t->touching_thinglist) are broken. When a node is | ||
293 | // added, new sector links are created. | ||
294 | |||
295 | P_CreateSecNodeList(thing,thing->x,thing->y); | ||
296 | thing->touching_sectorlist = sector_list; // Attach to Thing's mobj_t | ||
297 | sector_list = NULL; // clear for next time | ||
298 | } | ||
299 | |||
300 | // link into blockmap | ||
301 | if (!(thing->flags & MF_NOBLOCKMAP)) | ||
302 | { | ||
303 | // inert things don't need to be in blockmap | ||
304 | int blockx = (thing->x - bmaporgx)>>MAPBLOCKSHIFT; | ||
305 | int blocky = (thing->y - bmaporgy)>>MAPBLOCKSHIFT; | ||
306 | if (blockx>=0 && blockx < bmapwidth && blocky>=0 && blocky < bmapheight) | ||
307 | { | ||
308 | // killough 8/11/98: simpler scheme using pointer-to-pointer prev | ||
309 | // pointers, allows head nodes to be treated like everything else | ||
310 | |||
311 | mobj_t **link = &blocklinks[blocky*bmapwidth+blockx]; | ||
312 | mobj_t *bnext = *link; | ||
313 | if ((thing->bnext = bnext)) | ||
314 | bnext->bprev = &thing->bnext; | ||
315 | thing->bprev = link; | ||
316 | *link = thing; | ||
317 | } | ||
318 | else // thing is off the map | ||
319 | thing->bnext = NULL, thing->bprev = NULL; | ||
320 | } | ||
321 | } | ||
322 | |||
323 | // killough 3/15/98: | ||
324 | // | ||
325 | // A fast function for testing intersections between things and linedefs. | ||
326 | |||
327 | boolean CONSTFUNC ThingIsOnLine(const mobj_t *t, const line_t *l) | ||
328 | { | ||
329 | int dx = l->dx >> FRACBITS; // Linedef vector | ||
330 | int dy = l->dy >> FRACBITS; | ||
331 | int a = (l->v1->x >> FRACBITS) - (t->x >> FRACBITS); // Thing-->v1 vector | ||
332 | int b = (l->v1->y >> FRACBITS) - (t->y >> FRACBITS); | ||
333 | int r = t->radius >> FRACBITS; // Thing radius | ||
334 | |||
335 | // First make sure bounding boxes of linedef and thing intersect. | ||
336 | // Leads to quick rejection using only shifts and adds/subs/compares. | ||
337 | |||
338 | if (D_abs(a*2+dx)-D_abs(dx) > r*2 || D_abs(b*2+dy)-D_abs(dy) > r*2) | ||
339 | return 0; | ||
340 | |||
341 | // Next, make sure that at least one thing crosshair intersects linedef's | ||
342 | // extension. Requires only 3-4 multiplications, the rest adds/subs/ | ||
343 | // shifts/xors (writing the steps out this way leads to better codegen). | ||
344 | |||
345 | a *= dy; | ||
346 | b *= dx; | ||
347 | a -= b; | ||
348 | b = dx + dy; | ||
349 | b *= r; | ||
350 | if (((a-b)^(a+b)) < 0) | ||
351 | return 1; | ||
352 | dy -= dx; | ||
353 | dy *= r; | ||
354 | b = a+dy; | ||
355 | a -= dy; | ||
356 | return (a^b) < 0; | ||
357 | } | ||
358 | |||
359 | // | ||
360 | // BLOCK MAP ITERATORS | ||
361 | // For each line/thing in the given mapblock, | ||
362 | // call the passed PIT_* function. | ||
363 | // If the function returns false, | ||
364 | // exit with false without checking anything else. | ||
365 | // | ||
366 | |||
367 | // | ||
368 | // P_BlockLinesIterator | ||
369 | // The validcount flags are used to avoid checking lines | ||
370 | // that are marked in multiple mapblocks, | ||
371 | // so increment validcount before the first call | ||
372 | // to P_BlockLinesIterator, then make one or more calls | ||
373 | // to it. | ||
374 | // | ||
375 | // killough 5/3/98: reformatted, cleaned up | ||
376 | |||
377 | boolean P_BlockLinesIterator(int x, int y, boolean func(line_t*)) | ||
378 | { | ||
379 | int offset; | ||
380 | const long *list; // killough 3/1/98: for removal of blockmap limit | ||
381 | |||
382 | if (x<0 || y<0 || x>=bmapwidth || y>=bmapheight) | ||
383 | return true; | ||
384 | offset = y*bmapwidth+x; | ||
385 | offset = *(blockmap+offset); | ||
386 | list = blockmaplump+offset; // original was reading // phares | ||
387 | // delmiting 0 as linedef 0 // phares | ||
388 | |||
389 | // killough 1/31/98: for compatibility we need to use the old method. | ||
390 | // Most demos go out of sync, and maybe other problems happen, if we | ||
391 | // don't consider linedef 0. For safety this should be qualified. | ||
392 | |||
393 | if (!demo_compatibility) // killough 2/22/98: demo_compatibility check | ||
394 | list++; // skip 0 starting delimiter // phares | ||
395 | for ( ; *list != -1 ; list++) // phares | ||
396 | { | ||
397 | line_t *ld = &lines[*list]; | ||
398 | if (ld->validcount == validcount) | ||
399 | continue; // line has already been checked | ||
400 | ld->validcount = validcount; | ||
401 | if (!func(ld)) | ||
402 | return false; | ||
403 | } | ||
404 | return true; // everything was checked | ||
405 | } | ||
406 | |||
407 | // | ||
408 | // P_BlockThingsIterator | ||
409 | // | ||
410 | // killough 5/3/98: reformatted, cleaned up | ||
411 | |||
412 | boolean P_BlockThingsIterator(int x, int y, boolean func(mobj_t*)) | ||
413 | { | ||
414 | mobj_t *mobj; | ||
415 | if (!(x<0 || y<0 || x>=bmapwidth || y>=bmapheight)) | ||
416 | for (mobj = blocklinks[y*bmapwidth+x]; mobj; mobj = mobj->bnext) | ||
417 | if (!func(mobj)) | ||
418 | return false; | ||
419 | return true; | ||
420 | } | ||
421 | |||
422 | // | ||
423 | // INTERCEPT ROUTINES | ||
424 | // | ||
425 | |||
426 | // 1/11/98 killough: Intercept limit removed | ||
427 | static intercept_t *intercepts, *intercept_p; | ||
428 | |||
429 | // Check for limit and double size if necessary -- killough | ||
430 | static void check_intercept(void) | ||
431 | { | ||
432 | static size_t num_intercepts; | ||
433 | size_t offset = intercept_p - intercepts; | ||
434 | if (offset >= num_intercepts) | ||
435 | { | ||
436 | num_intercepts = num_intercepts ? num_intercepts*2 : 128; | ||
437 | intercepts = realloc(intercepts, sizeof(*intercepts)*num_intercepts); | ||
438 | intercept_p = intercepts + offset; | ||
439 | } | ||
440 | } | ||
441 | |||
442 | divline_t trace; | ||
443 | |||
444 | // PIT_AddLineIntercepts. | ||
445 | // Looks for lines in the given block | ||
446 | // that intercept the given trace | ||
447 | // to add to the intercepts list. | ||
448 | // | ||
449 | // A line is crossed if its endpoints | ||
450 | // are on opposite sides of the trace. | ||
451 | // | ||
452 | // killough 5/3/98: reformatted, cleaned up | ||
453 | |||
454 | boolean PIT_AddLineIntercepts(line_t *ld) | ||
455 | { | ||
456 | int s1; | ||
457 | int s2; | ||
458 | fixed_t frac; | ||
459 | divline_t dl; | ||
460 | |||
461 | // avoid precision problems with two routines | ||
462 | if (trace.dx > FRACUNIT*16 || trace.dy > FRACUNIT*16 || | ||
463 | trace.dx < -FRACUNIT*16 || trace.dy < -FRACUNIT*16) | ||
464 | { | ||
465 | s1 = P_PointOnDivlineSide (ld->v1->x, ld->v1->y, &trace); | ||
466 | s2 = P_PointOnDivlineSide (ld->v2->x, ld->v2->y, &trace); | ||
467 | } | ||
468 | else | ||
469 | { | ||
470 | s1 = P_PointOnLineSide (trace.x, trace.y, ld); | ||
471 | s2 = P_PointOnLineSide (trace.x+trace.dx, trace.y+trace.dy, ld); | ||
472 | } | ||
473 | |||
474 | if (s1 == s2) | ||
475 | return true; // line isn't crossed | ||
476 | |||
477 | // hit the line | ||
478 | P_MakeDivline(ld, &dl); | ||
479 | frac = P_InterceptVector(&trace, &dl); | ||
480 | |||
481 | if (frac < 0) | ||
482 | return true; // behind source | ||
483 | |||
484 | check_intercept(); // killough | ||
485 | |||
486 | intercept_p->frac = frac; | ||
487 | intercept_p->isaline = true; | ||
488 | intercept_p->d.line = ld; | ||
489 | intercept_p++; | ||
490 | |||
491 | return true; // continue | ||
492 | } | ||
493 | |||
494 | // | ||
495 | // PIT_AddThingIntercepts | ||
496 | // | ||
497 | // killough 5/3/98: reformatted, cleaned up | ||
498 | |||
499 | boolean PIT_AddThingIntercepts(mobj_t *thing) | ||
500 | { | ||
501 | fixed_t x1, y1; | ||
502 | fixed_t x2, y2; | ||
503 | int s1, s2; | ||
504 | divline_t dl; | ||
505 | fixed_t frac; | ||
506 | |||
507 | // check a corner to corner crossection for hit | ||
508 | if ((trace.dx ^ trace.dy) > 0) | ||
509 | { | ||
510 | x1 = thing->x - thing->radius; | ||
511 | y1 = thing->y + thing->radius; | ||
512 | x2 = thing->x + thing->radius; | ||
513 | y2 = thing->y - thing->radius; | ||
514 | } | ||
515 | else | ||
516 | { | ||
517 | x1 = thing->x - thing->radius; | ||
518 | y1 = thing->y - thing->radius; | ||
519 | x2 = thing->x + thing->radius; | ||
520 | y2 = thing->y + thing->radius; | ||
521 | } | ||
522 | |||
523 | s1 = P_PointOnDivlineSide (x1, y1, &trace); | ||
524 | s2 = P_PointOnDivlineSide (x2, y2, &trace); | ||
525 | |||
526 | if (s1 == s2) | ||
527 | return true; // line isn't crossed | ||
528 | |||
529 | dl.x = x1; | ||
530 | dl.y = y1; | ||
531 | dl.dx = x2-x1; | ||
532 | dl.dy = y2-y1; | ||
533 | |||
534 | frac = P_InterceptVector (&trace, &dl); | ||
535 | |||
536 | if (frac < 0) | ||
537 | return true; // behind source | ||
538 | |||
539 | check_intercept(); // killough | ||
540 | |||
541 | intercept_p->frac = frac; | ||
542 | intercept_p->isaline = false; | ||
543 | intercept_p->d.thing = thing; | ||
544 | intercept_p++; | ||
545 | |||
546 | return true; // keep going | ||
547 | } | ||
548 | |||
549 | // | ||
550 | // P_TraverseIntercepts | ||
551 | // Returns true if the traverser function returns true | ||
552 | // for all lines. | ||
553 | // | ||
554 | // killough 5/3/98: reformatted, cleaned up | ||
555 | |||
556 | boolean P_TraverseIntercepts(traverser_t func, fixed_t maxfrac) | ||
557 | { | ||
558 | intercept_t *in = NULL; | ||
559 | int count = intercept_p - intercepts; | ||
560 | while (count--) | ||
561 | { | ||
562 | fixed_t dist = INT_MAX; | ||
563 | intercept_t *scan; | ||
564 | for (scan = intercepts; scan < intercept_p; scan++) | ||
565 | if (scan->frac < dist) | ||
566 | dist = (in=scan)->frac; | ||
567 | if (dist > maxfrac) | ||
568 | return true; // checked everything in range | ||
569 | if (!func(in)) | ||
570 | return false; // don't bother going farther | ||
571 | in->frac = INT_MAX; | ||
572 | } | ||
573 | return true; // everything was traversed | ||
574 | } | ||
575 | |||
576 | // | ||
577 | // P_PathTraverse | ||
578 | // Traces a line from x1,y1 to x2,y2, | ||
579 | // calling the traverser function for each. | ||
580 | // Returns true if the traverser function returns true | ||
581 | // for all lines. | ||
582 | // | ||
583 | // killough 5/3/98: reformatted, cleaned up | ||
584 | |||
585 | boolean P_PathTraverse(fixed_t x1, fixed_t y1, fixed_t x2, fixed_t y2, | ||
586 | int flags, boolean trav(intercept_t *)) | ||
587 | { | ||
588 | fixed_t xt1, yt1; | ||
589 | fixed_t xt2, yt2; | ||
590 | fixed_t xstep, ystep; | ||
591 | fixed_t partial; | ||
592 | fixed_t xintercept, yintercept; | ||
593 | int mapx, mapy; | ||
594 | int mapxstep, mapystep; | ||
595 | int count; | ||
596 | |||
597 | validcount++; | ||
598 | intercept_p = intercepts; | ||
599 | |||
600 | if (!((x1-bmaporgx)&(MAPBLOCKSIZE-1))) | ||
601 | x1 += FRACUNIT; // don't side exactly on a line | ||
602 | |||
603 | if (!((y1-bmaporgy)&(MAPBLOCKSIZE-1))) | ||
604 | y1 += FRACUNIT; // don't side exactly on a line | ||
605 | |||
606 | trace.x = x1; | ||
607 | trace.y = y1; | ||
608 | trace.dx = x2 - x1; | ||
609 | trace.dy = y2 - y1; | ||
610 | |||
611 | x1 -= bmaporgx; | ||
612 | y1 -= bmaporgy; | ||
613 | xt1 = x1>>MAPBLOCKSHIFT; | ||
614 | yt1 = y1>>MAPBLOCKSHIFT; | ||
615 | |||
616 | x2 -= bmaporgx; | ||
617 | y2 -= bmaporgy; | ||
618 | xt2 = x2>>MAPBLOCKSHIFT; | ||
619 | yt2 = y2>>MAPBLOCKSHIFT; | ||
620 | |||
621 | if (xt2 > xt1) | ||
622 | { | ||
623 | mapxstep = 1; | ||
624 | partial = FRACUNIT - ((x1>>MAPBTOFRAC)&(FRACUNIT-1)); | ||
625 | ystep = FixedDiv (y2-y1,D_abs(x2-x1)); | ||
626 | } | ||
627 | else | ||
628 | if (xt2 < xt1) | ||
629 | { | ||
630 | mapxstep = -1; | ||
631 | partial = (x1>>MAPBTOFRAC)&(FRACUNIT-1); | ||
632 | ystep = FixedDiv (y2-y1,D_abs(x2-x1)); | ||
633 | } | ||
634 | else | ||
635 | { | ||
636 | mapxstep = 0; | ||
637 | partial = FRACUNIT; | ||
638 | ystep = 256*FRACUNIT; | ||
639 | } | ||
640 | |||
641 | yintercept = (y1>>MAPBTOFRAC) + FixedMul(partial, ystep); | ||
642 | |||
643 | if (yt2 > yt1) | ||
644 | { | ||
645 | mapystep = 1; | ||
646 | partial = FRACUNIT - ((y1>>MAPBTOFRAC)&(FRACUNIT-1)); | ||
647 | xstep = FixedDiv (x2-x1,D_abs(y2-y1)); | ||
648 | } | ||
649 | else | ||
650 | if (yt2 < yt1) | ||
651 | { | ||
652 | mapystep = -1; | ||
653 | partial = (y1>>MAPBTOFRAC)&(FRACUNIT-1); | ||
654 | xstep = FixedDiv (x2-x1,D_abs(y2-y1)); | ||
655 | } | ||
656 | else | ||
657 | { | ||
658 | mapystep = 0; | ||
659 | partial = FRACUNIT; | ||
660 | xstep = 256*FRACUNIT; | ||
661 | } | ||
662 | |||
663 | xintercept = (x1>>MAPBTOFRAC) + FixedMul (partial, xstep); | ||
664 | |||
665 | // Step through map blocks. | ||
666 | // Count is present to prevent a round off error | ||
667 | // from skipping the break. | ||
668 | |||
669 | mapx = xt1; | ||
670 | mapy = yt1; | ||
671 | |||
672 | for (count = 0; count < 64; count++) | ||
673 | { | ||
674 | if (flags & PT_ADDLINES) | ||
675 | if (!P_BlockLinesIterator(mapx, mapy,PIT_AddLineIntercepts)) | ||
676 | return false; // early out | ||
677 | |||
678 | if (flags & PT_ADDTHINGS) | ||
679 | if (!P_BlockThingsIterator(mapx, mapy,PIT_AddThingIntercepts)) | ||
680 | return false; // early out | ||
681 | |||
682 | if (mapx == xt2 && mapy == yt2) | ||
683 | break; | ||
684 | |||
685 | if ((yintercept >> FRACBITS) == mapy) | ||
686 | { | ||
687 | yintercept += ystep; | ||
688 | mapx += mapxstep; | ||
689 | } | ||
690 | else | ||
691 | if ((xintercept >> FRACBITS) == mapx) | ||
692 | { | ||
693 | xintercept += xstep; | ||
694 | mapy += mapystep; | ||
695 | } | ||
696 | } | ||
697 | |||
698 | // go through the sorted list | ||
699 | return P_TraverseIntercepts(trav, FRACUNIT); | ||
700 | } | ||