Patch #2969 - Doom! Currently only working on the H300.

git-svn-id: svn://svn.rockbox.org/rockbox/trunk@9312 a1c6a512-1295-4272-9138-f99709370657

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 0000000..a2ef132
--- /dev/null
+++ b/apps/plugins/doom/p_maputl.c
@@ -0,0 +1,700 @@
+/* Emacs style mode select   -*- C++ -*-
+ *-----------------------------------------------------------------------------
+ *
+ *
+ *  PrBoom a Doom port merged with LxDoom and LSDLDoom
+ *  based on BOOM, a modified and improved DOOM engine
+ *  Copyright (C) 1999 by
+ *  id Software, Chi Hoang, Lee Killough, Jim Flynn, Rand Phares, Ty Halderman
+ *  Copyright (C) 1999-2000 by
+ *  Jess Haas, Nicolas Kalkhof, Colin Phipps, Florian Schulze
+ *
+ *  This program is free software; you can redistribute it and/or
+ *  modify it under the terms of the GNU General Public License
+ *  as published by the Free Software Foundation; either version 2
+ *  of the License, or (at your option) any later version.
+ *
+ *  This program is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *  GNU General Public License for more details.
+ *
+ *  You should have received a copy of the GNU General Public License
+ *  along with this program; if not, write to the Free Software
+ *  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
+ *  02111-1307, USA.
+ *
+ * DESCRIPTION:
+ *      Movement/collision utility functions,
+ *      as used by function in p_map.c.
+ *      BLOCKMAP Iterator functions,
+ *      and some PIT_* functions to use for iteration.
+ *
+ *-----------------------------------------------------------------------------*/
+
+#include "doomstat.h"
+#include "m_bbox.h"
+#include "r_main.h"
+#include "p_maputl.h"
+#include "p_map.h"
+#include "p_setup.h"
+#include "rockmacros.h"
+//
+// P_AproxDistance
+// Gives an estimation of distance (not exact)
+//
+
+fixed_t CONSTFUNC P_AproxDistance(fixed_t dx, fixed_t dy)
+{
+   dx = D_abs(dx);
+   dy = D_abs(dy);
+   if (dx < dy)
+      return dx+dy-(dx>>1);
+   return dx+dy-(dy>>1);
+}
+
+//
+// P_PointOnLineSide
+// Returns 0 or 1
+//
+// killough 5/3/98: reformatted, cleaned up
+
+int CONSTFUNC P_PointOnLineSide(fixed_t x, fixed_t y, const line_t *line)
+{
+   return
+   !line->dx ? x <= line->v1->x ? line->dy > 0 : line->dy < 0 :
+   !line->dy ? y <= line->v1->y ? line->dx < 0 : line->dx > 0 :
+      FixedMul(y-line->v1->y, line->dx>>FRACBITS) >=
+      FixedMul(line->dy>>FRACBITS, x-line->v1->x);
+}
+
+//
+// P_BoxOnLineSide
+// Considers the line to be infinite
+// Returns side 0 or 1, -1 if box crosses the line.
+//
+// killough 5/3/98: reformatted, cleaned up
+
+int CONSTFUNC P_BoxOnLineSide(const fixed_t *tmbox, const line_t *ld)
+{
+   switch (ld->slopetype)
+   {
+      int p;
+   default: // shut up compiler warnings -- killough
+   case ST_HORIZONTAL:
+      return
+         (tmbox[BOXBOTTOM] > ld->v1->y) == (p = tmbox[BOXTOP] > ld->v1->y) ?
+         p ^ (ld->dx < 0) : -1;
+   case ST_VERTICAL:
+      return
+         (tmbox[BOXLEFT] < ld->v1->x) == (p = tmbox[BOXRIGHT] < ld->v1->x) ?
+         p ^ (ld->dy < 0) : -1;
+   case ST_POSITIVE:
+      return
+         P_PointOnLineSide(tmbox[BOXRIGHT], tmbox[BOXBOTTOM], ld) ==
+         (p = P_PointOnLineSide(tmbox[BOXLEFT], tmbox[BOXTOP], ld)) ? p : -1;
+   case ST_NEGATIVE:
+      return
+         (P_PointOnLineSide(tmbox[BOXLEFT], tmbox[BOXBOTTOM], ld)) ==
+         (p = P_PointOnLineSide(tmbox[BOXRIGHT], tmbox[BOXTOP], ld)) ? p : -1;
+   }
+}
+
+//
+// P_PointOnDivlineSide
+// Returns 0 or 1.
+//
+// killough 5/3/98: reformatted, cleaned up
+
+int CONSTFUNC P_PointOnDivlineSide(fixed_t x, fixed_t y, const divline_t *line)
+{
+   return
+   !line->dx ? x <= line->x ? line->dy > 0 : line->dy < 0 :
+   !line->dy ? y <= line->y ? line->dx < 0 : line->dx > 0 :
+      (line->dy^line->dx^(x -= line->x)^(y -= line->y)) < 0 ? (line->dy^x) < 0 :
+      FixedMul(y>>8, line->dx>>8) >= FixedMul(line->dy>>8, x>>8);
+}
+
+//
+// P_MakeDivline
+//
+
+void P_MakeDivline(const line_t *li, divline_t *dl)
+{
+   dl->x = li->v1->x;
+   dl->y = li->v1->y;
+   dl->dx = li->dx;
+   dl->dy = li->dy;
+}
+
+//
+// P_InterceptVector
+// Returns the fractional intercept point
+// along the first divline.
+// This is only called by the addthings
+// and addlines traversers.
+//
+// killough 5/3/98: reformatted, cleaned up
+
+fixed_t CONSTFUNC P_InterceptVector(const divline_t *v2, const divline_t *v1)
+{
+   fixed_t den = FixedMul(v1->dy>>8, v2->dx) - FixedMul(v1->dx>>8, v2->dy);
+   return den ? FixedDiv((FixedMul((v1->x-v2->x)>>8, v1->dy) +
+                          FixedMul((v2->y-v1->y)>>8, v1->dx)), den) : 0;
+}
+
+//
+// P_LineOpening
+// Sets opentop and openbottom to the window
+// through a two sided line.
+// OPTIMIZE: keep this precalculated
+//
+
+fixed_t opentop;
+fixed_t openbottom;
+fixed_t openrange;
+fixed_t lowfloor;
+
+// moved front and back outside P-LineOpening and changed    // phares 3/7/98
+// them to these so we can pick up the new friction value
+// in PIT_CheckLine()
+sector_t *openfrontsector; // made global                    // phares
+sector_t *openbacksector;  // made global
+
+void P_LineOpening(const line_t *linedef)
+{
+   if (linedef->sidenum[1] == -1)      // single sided line
+   {
+      openrange = 0;
+      return;
+   }
+
+   openfrontsector = linedef->frontsector;
+   openbacksector = linedef->backsector;
+
+   if (openfrontsector->ceilingheight < openbacksector->ceilingheight)
+      opentop = openfrontsector->ceilingheight;
+   else
+      opentop = openbacksector->ceilingheight;
+
+   if (openfrontsector->floorheight > openbacksector->floorheight)
+   {
+      openbottom = openfrontsector->floorheight;
+      lowfloor = openbacksector->floorheight;
+   }
+   else
+   {
+      openbottom = openbacksector->floorheight;
+      lowfloor = openfrontsector->floorheight;
+   }
+   openrange = opentop - openbottom;
+}
+
+//
+// THING POSITION SETTING
+//
+
+//
+// P_UnsetThingPosition
+// Unlinks a thing from block map and sectors.
+// On each position change, BLOCKMAP and other
+// lookups maintaining lists ot things inside
+// these structures need to be updated.
+//
+
+void P_UnsetThingPosition (mobj_t *thing)
+{
+   if (!(thing->flags & MF_NOSECTOR))
+   {
+      /* invisible things don't need to be in sector list
+       * unlink from subsector
+       *
+       * killough 8/11/98: simpler scheme using pointers-to-pointers for prev
+       * pointers, allows head node pointers to be treated like everything else
+       */
+
+      mobj_t **sprev = thing->sprev;
+      mobj_t  *snext = thing->snext;
+      if ((*sprev = snext))  // unlink from sector list
+         snext->sprev = sprev;
+
+      // phares 3/14/98
+      //
+      // Save the sector list pointed to by touching_sectorlist.
+      // In P_SetThingPosition, we'll keep any nodes that represent
+      // sectors the Thing still touches. We'll add new ones then, and
+      // delete any nodes for sectors the Thing has vacated. Then we'll
+      // put it back into touching_sectorlist. It's done this way to
+      // avoid a lot of deleting/creating for nodes, when most of the
+      // time you just get back what you deleted anyway.
+      //
+      // If this Thing is being removed entirely, then the calling
+      // routine will clear out the nodes in sector_list.
+
+      sector_list = thing->touching_sectorlist;
+      thing->touching_sectorlist = NULL; //to be restored by P_SetThingPosition
+   }
+
+   if (!(thing->flags & MF_NOBLOCKMAP))
+   {
+      /* inert things don't need to be in blockmap
+       *
+       * killough 8/11/98: simpler scheme using pointers-to-pointers for prev
+       * pointers, allows head node pointers to be treated like everything else
+       *
+       * Also more robust, since it doesn't depend on current position for
+       * unlinking. Old method required computing head node based on position
+       * at time of unlinking, assuming it was the same position as during
+       * linking.
+       */
+
+      mobj_t *bnext, **bprev = thing->bprev;
+      if (bprev && (*bprev = bnext = thing->bnext))  // unlink from block map
+         bnext->bprev = bprev;
+   }
+}
+
+//
+// P_SetThingPosition
+// Links a thing into both a block and a subsector
+// based on it's x y.
+// Sets thing->subsector properly
+//
+// killough 5/3/98: reformatted, cleaned up
+
+void P_SetThingPosition(mobj_t *thing)
+{                                                      // link into subsector
+   subsector_t *ss = thing->subsector = R_PointInSubsector(thing->x, thing->y);
+   if (!(thing->flags & MF_NOSECTOR))
+   {
+      // invisible things don't go into the sector links
+
+      // killough 8/11/98: simpler scheme using pointer-to-pointer prev
+      // pointers, allows head nodes to be treated like everything else
+
+      mobj_t **link = &ss->sector->thinglist;
+      mobj_t *snext = *link;
+      if ((thing->snext = snext))
+         snext->sprev = &thing->snext;
+      thing->sprev = link;
+      *link = thing;
+
+      // phares 3/16/98
+      //
+      // If sector_list isn't NULL, it has a collection of sector
+      // nodes that were just removed from this Thing.
+
+      // Collect the sectors the object will live in by looking at
+      // the existing sector_list and adding new nodes and deleting
+      // obsolete ones.
+
+      // When a node is deleted, its sector links (the links starting
+      // at sector_t->touching_thinglist) are broken. When a node is
+      // added, new sector links are created.
+
+      P_CreateSecNodeList(thing,thing->x,thing->y);
+      thing->touching_sectorlist = sector_list; // Attach to Thing's mobj_t
+      sector_list = NULL; // clear for next time
+   }
+
+   // link into blockmap
+   if (!(thing->flags & MF_NOBLOCKMAP))
+   {
+      // inert things don't need to be in blockmap
+      int blockx = (thing->x - bmaporgx)>>MAPBLOCKSHIFT;
+      int blocky = (thing->y - bmaporgy)>>MAPBLOCKSHIFT;
+      if (blockx>=0 && blockx < bmapwidth && blocky>=0 && blocky < bmapheight)
+      {
+         // killough 8/11/98: simpler scheme using pointer-to-pointer prev
+         // pointers, allows head nodes to be treated like everything else
+
+         mobj_t **link = &blocklinks[blocky*bmapwidth+blockx];
+         mobj_t *bnext = *link;
+         if ((thing->bnext = bnext))
+            bnext->bprev = &thing->bnext;
+         thing->bprev = link;
+         *link = thing;
+      }
+      else        // thing is off the map
+         thing->bnext = NULL, thing->bprev = NULL;
+   }
+}
+
+// killough 3/15/98:
+//
+// A fast function for testing intersections between things and linedefs.
+
+boolean CONSTFUNC ThingIsOnLine(const mobj_t *t, const line_t *l)
+{
+   int dx = l->dx >> FRACBITS;                             // Linedef vector
+   int dy = l->dy >> FRACBITS;
+   int a = (l->v1->x >> FRACBITS) - (t->x >> FRACBITS);    // Thing-->v1 vector
+   int b = (l->v1->y >> FRACBITS) - (t->y >> FRACBITS);
+   int r = t->radius >> FRACBITS;                          // Thing radius
+
+   // First make sure bounding boxes of linedef and thing intersect.
+   // Leads to quick rejection using only shifts and adds/subs/compares.
+
+   if (D_abs(a*2+dx)-D_abs(dx) > r*2 || D_abs(b*2+dy)-D_abs(dy) > r*2)
+      return 0;
+
+   // Next, make sure that at least one thing crosshair intersects linedef's
+   // extension. Requires only 3-4 multiplications, the rest adds/subs/
+   // shifts/xors (writing the steps out this way leads to better codegen).
+
+   a *= dy;
+   b *= dx;
+   a -= b;
+   b = dx + dy;
+   b *= r;
+   if (((a-b)^(a+b)) < 0)
+      return 1;
+   dy -= dx;
+   dy *= r;
+   b = a+dy;
+   a -= dy;
+   return (a^b) < 0;
+}
+
+//
+// BLOCK MAP ITERATORS
+// For each line/thing in the given mapblock,
+// call the passed PIT_* function.
+// If the function returns false,
+// exit with false without checking anything else.
+//
+
+//
+// P_BlockLinesIterator
+// The validcount flags are used to avoid checking lines
+// that are marked in multiple mapblocks,
+// so increment validcount before the first call
+// to P_BlockLinesIterator, then make one or more calls
+// to it.
+//
+// killough 5/3/98: reformatted, cleaned up
+
+boolean P_BlockLinesIterator(int x, int y, boolean func(line_t*))
+{
+   int        offset;
+   const long *list;   // killough 3/1/98: for removal of blockmap limit
+
+   if (x<0 || y<0 || x>=bmapwidth || y>=bmapheight)
+      return true;
+   offset = y*bmapwidth+x;
+   offset = *(blockmap+offset);
+   list = blockmaplump+offset;     // original was reading         // phares
+   // delmiting 0 as linedef 0     // phares
+
+   // killough 1/31/98: for compatibility we need to use the old method.
+   // Most demos go out of sync, and maybe other problems happen, if we
+   // don't consider linedef 0. For safety this should be qualified.
+
+   if (!demo_compatibility) // killough 2/22/98: demo_compatibility check
+      list++;     // skip 0 starting delimiter                      // phares
+   for ( ; *list != -1 ; list++)                                   // phares
+   {
+      line_t *ld = &lines[*list];
+      if (ld->validcount == validcount)
+         continue;       // line has already been checked
+      ld->validcount = validcount;
+      if (!func(ld))
+         return false;
+   }
+   return true;  // everything was checked
+}
+
+//
+// P_BlockThingsIterator
+//
+// killough 5/3/98: reformatted, cleaned up
+
+boolean P_BlockThingsIterator(int x, int y, boolean func(mobj_t*))
+{
+   mobj_t *mobj;
+   if (!(x<0 || y<0 || x>=bmapwidth || y>=bmapheight))
+      for (mobj = blocklinks[y*bmapwidth+x]; mobj; mobj = mobj->bnext)
+         if (!func(mobj))
+            return false;
+   return true;
+}
+
+//
+// INTERCEPT ROUTINES
+//
+
+// 1/11/98 killough: Intercept limit removed
+static intercept_t *intercepts, *intercept_p;
+
+// Check for limit and double size if necessary -- killough
+static void check_intercept(void)
+{
+   static size_t num_intercepts;
+   size_t offset = intercept_p - intercepts;
+   if (offset >= num_intercepts)
+   {
+      num_intercepts = num_intercepts ? num_intercepts*2 : 128;
+      intercepts = realloc(intercepts, sizeof(*intercepts)*num_intercepts);
+      intercept_p = intercepts + offset;
+   }
+}
+
+divline_t trace;
+
+// PIT_AddLineIntercepts.
+// Looks for lines in the given block
+// that intercept the given trace
+// to add to the intercepts list.
+//
+// A line is crossed if its endpoints
+// are on opposite sides of the trace.
+//
+// killough 5/3/98: reformatted, cleaned up
+
+boolean PIT_AddLineIntercepts(line_t *ld)
+{
+   int       s1;
+   int       s2;
+   fixed_t   frac;
+   divline_t dl;
+
+   // avoid precision problems with two routines
+   if (trace.dx >  FRACUNIT*16 || trace.dy >  FRACUNIT*16 ||
+         trace.dx < -FRACUNIT*16 || trace.dy < -FRACUNIT*16)
+   {
+      s1 = P_PointOnDivlineSide (ld->v1->x, ld->v1->y, &trace);
+      s2 = P_PointOnDivlineSide (ld->v2->x, ld->v2->y, &trace);
+   }
+   else
+   {
+      s1 = P_PointOnLineSide (trace.x, trace.y, ld);
+      s2 = P_PointOnLineSide (trace.x+trace.dx, trace.y+trace.dy, ld);
+   }
+
+   if (s1 == s2)
+      return true;        // line isn't crossed
+
+   // hit the line
+   P_MakeDivline(ld, &dl);
+   frac = P_InterceptVector(&trace, &dl);
+
+   if (frac < 0)
+      return true;        // behind source
+
+   check_intercept();    // killough
+
+   intercept_p->frac = frac;
+   intercept_p->isaline = true;
+   intercept_p->d.line = ld;
+   intercept_p++;
+
+   return true;  // continue
+}
+
+//
+// PIT_AddThingIntercepts
+//
+// killough 5/3/98: reformatted, cleaned up
+
+boolean PIT_AddThingIntercepts(mobj_t *thing)
+{
+   fixed_t   x1, y1;
+   fixed_t   x2, y2;
+   int       s1, s2;
+   divline_t dl;
+   fixed_t   frac;
+
+   // check a corner to corner crossection for hit
+   if ((trace.dx ^ trace.dy) > 0)
+   {
+      x1 = thing->x - thing->radius;
+      y1 = thing->y + thing->radius;
+      x2 = thing->x + thing->radius;
+      y2 = thing->y - thing->radius;
+   }
+   else
+   {
+      x1 = thing->x - thing->radius;
+      y1 = thing->y - thing->radius;
+      x2 = thing->x + thing->radius;
+      y2 = thing->y + thing->radius;
+   }
+
+   s1 = P_PointOnDivlineSide (x1, y1, &trace);
+   s2 = P_PointOnDivlineSide (x2, y2, &trace);
+
+   if (s1 == s2)
+      return true;                // line isn't crossed
+
+   dl.x = x1;
+   dl.y = y1;
+   dl.dx = x2-x1;
+   dl.dy = y2-y1;
+
+   frac = P_InterceptVector (&trace, &dl);
+
+   if (frac < 0)
+      return true;                // behind source
+
+   check_intercept();            // killough
+
+   intercept_p->frac = frac;
+   intercept_p->isaline = false;
+   intercept_p->d.thing = thing;
+   intercept_p++;
+
+   return true;          // keep going
+}
+
+//
+// P_TraverseIntercepts
+// Returns true if the traverser function returns true
+// for all lines.
+//
+// killough 5/3/98: reformatted, cleaned up
+
+boolean P_TraverseIntercepts(traverser_t func, fixed_t maxfrac)
+{
+   intercept_t *in = NULL;
+   int count = intercept_p - intercepts;
+   while (count--)
+   {
+      fixed_t dist = INT_MAX;
+      intercept_t *scan;
+      for (scan = intercepts; scan < intercept_p; scan++)
+         if (scan->frac < dist)
+            dist = (in=scan)->frac;
+      if (dist > maxfrac)
+         return true;    // checked everything in range
+      if (!func(in))
+         return false;           // don't bother going farther
+      in->frac = INT_MAX;
+   }
+   return true;                  // everything was traversed
+}
+
+//
+// P_PathTraverse
+// Traces a line from x1,y1 to x2,y2,
+// calling the traverser function for each.
+// Returns true if the traverser function returns true
+// for all lines.
+//
+// killough 5/3/98: reformatted, cleaned up
+
+boolean P_PathTraverse(fixed_t x1, fixed_t y1, fixed_t x2, fixed_t y2,
+                       int flags, boolean trav(intercept_t *))
+{
+   fixed_t xt1, yt1;
+   fixed_t xt2, yt2;
+   fixed_t xstep, ystep;
+   fixed_t partial;
+   fixed_t xintercept, yintercept;
+   int     mapx, mapy;
+   int     mapxstep, mapystep;
+   int     count;
+
+   validcount++;
+   intercept_p = intercepts;
+
+   if (!((x1-bmaporgx)&(MAPBLOCKSIZE-1)))
+      x1 += FRACUNIT;     // don't side exactly on a line
+
+   if (!((y1-bmaporgy)&(MAPBLOCKSIZE-1)))
+      y1 += FRACUNIT;     // don't side exactly on a line
+
+   trace.x = x1;
+   trace.y = y1;
+   trace.dx = x2 - x1;
+   trace.dy = y2 - y1;
+
+   x1 -= bmaporgx;
+   y1 -= bmaporgy;
+   xt1 = x1>>MAPBLOCKSHIFT;
+   yt1 = y1>>MAPBLOCKSHIFT;
+
+   x2 -= bmaporgx;
+   y2 -= bmaporgy;
+   xt2 = x2>>MAPBLOCKSHIFT;
+   yt2 = y2>>MAPBLOCKSHIFT;
+
+   if (xt2 > xt1)
+   {
+      mapxstep = 1;
+      partial = FRACUNIT - ((x1>>MAPBTOFRAC)&(FRACUNIT-1));
+      ystep = FixedDiv (y2-y1,D_abs(x2-x1));
+   }
+   else
+      if (xt2 < xt1)
+      {
+         mapxstep = -1;
+         partial = (x1>>MAPBTOFRAC)&(FRACUNIT-1);
+         ystep = FixedDiv (y2-y1,D_abs(x2-x1));
+      }
+      else
+      {
+         mapxstep = 0;
+         partial = FRACUNIT;
+         ystep = 256*FRACUNIT;
+      }
+
+   yintercept = (y1>>MAPBTOFRAC) + FixedMul(partial, ystep);
+
+   if (yt2 > yt1)
+   {
+      mapystep = 1;
+      partial = FRACUNIT - ((y1>>MAPBTOFRAC)&(FRACUNIT-1));
+      xstep = FixedDiv (x2-x1,D_abs(y2-y1));
+   }
+   else
+      if (yt2 < yt1)
+      {
+         mapystep = -1;
+         partial = (y1>>MAPBTOFRAC)&(FRACUNIT-1);
+         xstep = FixedDiv (x2-x1,D_abs(y2-y1));
+      }
+      else
+      {
+         mapystep = 0;
+         partial = FRACUNIT;
+         xstep = 256*FRACUNIT;
+      }
+
+   xintercept = (x1>>MAPBTOFRAC) + FixedMul (partial, xstep);
+
+   // Step through map blocks.
+   // Count is present to prevent a round off error
+   // from skipping the break.
+
+   mapx = xt1;
+   mapy = yt1;
+
+   for (count = 0; count < 64; count++)
+   {
+      if (flags & PT_ADDLINES)
+         if (!P_BlockLinesIterator(mapx, mapy,PIT_AddLineIntercepts))
+            return false; // early out
+
+      if (flags & PT_ADDTHINGS)
+         if (!P_BlockThingsIterator(mapx, mapy,PIT_AddThingIntercepts))
+            return false; // early out
+
+      if (mapx == xt2 && mapy == yt2)
+         break;
+
+      if ((yintercept >> FRACBITS) == mapy)
+      {
+         yintercept += ystep;
+         mapx += mapxstep;
+      }
+      else
+         if ((xintercept >> FRACBITS) == mapx)
+         {
+            xintercept += xstep;
+            mapy += mapystep;
+         }
+   }
+
+   // go through the sorted list
+   return P_TraverseIntercepts(trav, FRACUNIT);
+}