server/common/los.C

/*
 * This file is part of Deliantra, the Roguelike Realtime MMORPG.
 * 
 * Copyright (©) 2005,2006,2007,2008 Marc Alexander Lehmann / Robin Redeker / the Deliantra team
 * Copyright (©) 2002,2007 Mark Wedel & Crossfire Development Team
 * Copyright (©) 1992,2007 Frank Tore Johansen
 * 
 * Deliantra 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 3 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, see <http://www.gnu.org/licenses/>.
 * 
 * The authors can be reached via e-mail to <support@deliantra.net>
 */

/* Nov 95 - inserted USE_LIGHTING code stuff in here - b.t. */

#include <global.h>
#include <cmath>

static void expand_lighted_sight (object *op);

enum {
  LOS_XI = 0x01,
  LOS_YI = 0x02,
};

struct los_info
{
  sint8 xo, yo;  // obscure angle
  sint8 xe, ye;  // angle deviation
  uint8 culled;  // culled from "tree"
  uint8 queued;  // already queued
  uint8 visible;
  uint8 flags;   // LOS_XI/YI
};

// temporary storage for the los algorithm,
// one los_info for each lightable map space
static los_info los[MAP_CLIENT_X][MAP_CLIENT_Y];

struct point
{
  sint8 x, y;
};

// minimum size, but must be a power of two
#define QUEUE_LENGTH ((MAP_CLIENT_X + MAP_CLIENT_Y) * 2)

// a queue of spaces to calculate
static point queue [QUEUE_LENGTH];
static int q1, q2; // queue start, end

/*
 * Clears/initialises the los-array associated to the player
 * controlling the object.
 */
void
player::clear_los (sint8 value)
{
  memset (los, value, sizeof (los));
}

// enqueue a single mapspace, but only if it hasn't
// been enqueued yet.
static void
enqueue (sint8 dx, sint8 dy, uint8 flags = 0)
{
  sint8 x = LOS_X0 + dx;
  sint8 y = LOS_Y0 + dy;

  if (x < 0 || x >= MAP_CLIENT_X) return;
  if (y < 0 || y >= MAP_CLIENT_Y) return;

  los_info &l = los[x][y];

  l.flags |= flags;

  if (l.queued)
    return;

  l.queued = 1;

  queue[q1].x = dx;
  queue[q1].y = dy;

  q1 = (q1 + 1) & (QUEUE_LENGTH - 1);
}

// run the los algorithm
// this is a variant of a spiral los algorithm taken from
// http://www.geocities.com/temerra/los_rays.html
// which has been simplified and changed considerably, but
// still is basically the same algorithm.
static void
do_los (object *op)
{
  player *pl = op->contr;

  int max_radius = max (pl->ns->mapx, pl->ns->mapy) / 2;

  memset (los, 0, sizeof (los));

  q1 = 0; q2 = 0; // initialise queue, not strictly required
  enqueue (0, 0); // enqueue center

  // treat the origin specially
  los[LOS_X0][LOS_Y0].visible = 1;
  pl->los[LOS_X0][LOS_Y0] = 0;

  // loop over all enqueued points until the queue is empty
  // the order in which this is done ensures that we
  // never touch a mapspace whose input spaces we haven't checked
  // yet.
  while (q1 != q2)
    {
      sint8 dx = queue[q2].x;
      sint8 dy = queue[q2].y;

      q2 = (q2 + 1) & (QUEUE_LENGTH - 1);

      sint8 x = LOS_X0 + dx;
      sint8 y = LOS_Y0 + dy;

      //int distance = idistance (dx, dy); if (distance > max_radius) continue;//D
      int distance = 0;//D

      los_info &l = los[x][y];

      if (expect_true (l.flags & (LOS_XI | LOS_YI)))
        {
          l.culled = 1;

          // check contributing spaces, first horizontal
          if (expect_true (l.flags & LOS_XI))
            {
              los_info *xi = &los[x - sign (dx)][y];

              // don't cull unless obscured
              l.culled &= !xi->visible;

              /* merge input space */
              if (expect_false (xi->xo || xi->yo))
                {
                  // The X input can provide two main pieces of information: 
                  // 1. Progressive X obscurity.
                  // 2. Recessive Y obscurity.
                          
                  // Progressive X obscurity, favouring recessive input angle
                  if (xi->xe > 0 && l.xo == 0)
                    {
                      l.xe = xi->xe - xi->yo;
                      l.ye = xi->ye + xi->yo;
                      l.xo = xi->xo;
                      l.yo = xi->yo;
                    }

                  // Recessive Y obscurity
                  if (xi->ye <= 0 && xi->yo > 0 && xi->xe > 0)
                    {
                      l.ye = xi->yo + xi->ye;
                      l.xe = xi->xe - xi->yo;
                      l.xo = xi->xo;
                      l.yo = xi->yo;
                    }
                }
            }
                
          // check contributing spaces, last vertical, identical structure
          if (expect_true (l.flags & LOS_YI))
            {
              los_info *yi = &los[x][y - sign (dy)];

              // don't cull unless obscured
              l.culled &= !yi->visible;

              /* merge input space */
              if (expect_false (yi->yo || yi->xo))
                {
                  // The Y input can provide two main pieces of information: 
                  // 1. Progressive Y obscurity.
                  // 2. Recessive X obscurity.
                          
                  // Progressive Y obscurity, favouring recessive input angle
                  if (yi->ye > 0 && l.yo == 0)
                    {
                      l.ye = yi->ye - yi->xo;
                      l.xe = yi->xe + yi->xo;
                      l.yo = yi->yo;
                      l.xo = yi->xo;
                    }

                  // Recessive X obscurity
                  if (yi->xe <= 0 && yi->xo > 0 && yi->ye > 0)
                    {
                      l.xe = yi->xo + yi->xe;
                      l.ye = yi->ye - yi->xo;
                      l.yo = yi->yo;
                      l.xo = yi->xo;
                    }
                }
            }

          // check whether this space blocks the view
          maptile *m = op->map;
          sint16 nx = op->x + dx;
          sint16 ny = op->y + dy;

          if (expect_true (!xy_normalise (m, nx, ny))
              || expect_false (m->at (nx, ny).flags () & P_BLOCKSVIEW))
            {
              l.xo = l.xe = abs (dx);
              l.yo = l.ye = abs (dy);

              // we obscure dependents, but might be visible
              // copy the los from the square towards the player,
              // so outward diagonal corners are lit.
              pl->los[x][y] = los[x - sign0 (dx)][y - sign0 (dy)].visible ? 0 : LOS_BLOCKED;
              l.visible = false;
            }
          else
            {
              // we are not blocked, so calculate visibility, by checking
              // whether we are inside or outside the shadow
              l.visible = (l.xe <= 0 || l.xe > l.xo)
                       && (l.ye <= 0 || l.ye > l.yo);

              pl->los[x][y] = l.culled  ? LOS_BLOCKED
                            : l.visible ? max (0, 2 - max_radius + distance)
                                        : 3;
            }

        }

      // Expands by the unit length in each component's current direction.
      // If a component has no direction, then it is expanded in both of its 
      // positive and negative directions.
      if (!l.culled)
        {
          if (dx >= 0) enqueue (dx + 1, dy, LOS_XI);
          if (dx <= 0) enqueue (dx - 1, dy, LOS_XI);
          if (dy >= 0) enqueue (dx, dy + 1, LOS_YI);
          if (dy <= 0) enqueue (dx, dy - 1, LOS_YI);
        }
    }
}

/* returns true if op carries one or more lights
 * This is a trivial function now days, but it used to
 * be a bit longer.  Probably better for callers to just
 * check the op->glow_radius instead of calling this.
 */
int
has_carried_lights (const object *op)
{
  /* op may glow! */
  if (op->glow_radius > 0)
    return 1;

  return 0;
}

/* radius, distance => lightness adjust */
static sint8 light_atten[MAX_LIGHT_RADIUS * 2 + 1][MAX_LIGHT_RADIUS * 3 / 2 + 1];

static struct los_init
{
  los_init ()
  {
    for (int radius = -MAX_LIGHT_RADIUS; radius <= MAX_LIGHT_RADIUS; ++radius)
      for (int distance = 0; distance <= MAX_LIGHT_RADIUS * 3 / 2; ++distance)
        {
          // max intensity
          int intensity = min (LOS_MAX, abs (radius) + 1);

          // actual intensity
          intensity = max (0, lerp_rd (distance, 0, abs (radius) + 1, intensity, 0));

          light_atten [radius + MAX_LIGHT_RADIUS][distance] = radius < 0
            ? min (3, intensity)
            : LOS_MAX - intensity;
        }
  }
} los_init;

sint8
los_brighten (sint8 b, sint8 l)
{
  return b == LOS_BLOCKED ? b : min (b, l);
}

sint8
los_darken (sint8 b, sint8 l)
{
  return max (b, l);
}

template<sint8 change_it (sint8, sint8)>
static void
apply_light (object *op, int dx, int dy, int light, const sint8 *atten_table)
{
  // min or max the circular area around basex, basey
  player *pl = op->contr;

  dx += LOS_X0;
  dy += LOS_Y0;

  int hx = op->contr->ns->mapx / 2;
  int hy = op->contr->ns->mapy / 2;

  int ax0 = max (LOS_X0 - hx, dx - light);
  int ay0 = max (LOS_Y0 - hy, dy - light);
  int ax1 = min (dx + light, LOS_X0 + hx);
  int ay1 = min (dy + light, LOS_Y0 + hy);

  for (int ax = ax0; ax <= ax1; ax++)
    for (int ay = ay0; ay <= ay1; ay++)
      pl->los[ax][ay] =
        change_it (pl->los[ax][ay], atten_table [idistance (ax - dx, ay - dy)]);
}

/* add light, by finding all (non-null) nearby light sources, then 
 * mark those squares specially.
 */
static void
apply_lights (object *op)
{
  int darklevel, mflags, light, x1, y1;
  maptile *m = op->map;
  sint16 nx, ny;

  darklevel = m->darkness;

  /* If the player can see in the dark, lower the darklevel for him */
  if (QUERY_FLAG (op, FLAG_SEE_IN_DARK))
    darklevel -= LOS_MAX / 2;

  /* Do a sanity check.  If not valid, some code below may do odd
   * things.
   */
  if (darklevel > MAX_DARKNESS)
    {
      LOG (llevError, "Map darkness for %s on %s is too high (%d)\n", &op->name, &op->map->path, darklevel);
      darklevel = MAX_DARKNESS;
    }

  int half_x = op->contr->ns->mapx / 2;
  int half_y = op->contr->ns->mapy / 2;

  int min_x = op->x - half_x - MAX_LIGHT_RADIUS;
  int min_y = op->y - half_y - MAX_LIGHT_RADIUS;
  int max_x = op->x + half_x + MAX_LIGHT_RADIUS;
  int max_y = op->y + half_y + MAX_LIGHT_RADIUS;

  int pass2 = 0; // negative lights have an extra pass

  if (darklevel < 1)
    pass2 = 1;
  else
    {
      /* first, make everything totally dark */
      for (int dx = -half_x; dx <= half_x; dx++)
        for (int dy = -half_x; dy <= half_y; dy++)
          if (op->contr->los[dx + LOS_X0][dy + LOS_Y0] != LOS_BLOCKED)
            op->contr->los[dx + LOS_X0][dy + LOS_Y0] = LOS_MAX;

      /*
       * Only process the area of interest.
       * the basex, basey values represent the position in the op->contr->los
       * array. Its easier to just increment them here (and start with the right
       * value) than to recalculate them down below.
       */
      for (int x = min_x; x <= max_x; x++)
        for (int y = min_y; y <= max_y; y++)
          {
            maptile *m = op->map;
            sint16 nx = x;
            sint16 ny = y;

            if (!xy_normalise (m, nx, ny))
              continue;

            mapspace &ms = m->at (nx, ny);
            ms.update ();
            sint8 light = ms.light;

            if (expect_false (light))
              if (light < 0)
                pass2 = 1;
              else
                apply_light<los_brighten> (op, x - op->x, y - op->y, light, light_atten [light + MAX_LIGHT_RADIUS]);
          }

      /* grant some vision to the player, based on the darklevel */
      {
        int light = clamp (MAX_DARKNESS - darklevel, 0, MAX_LIGHT_RADIUS);

        apply_light<los_brighten> (op, 0, 0, light, light_atten [light + MAX_LIGHT_RADIUS]);
      }
    }

  // possibly do 2nd pass for rare negative glow radii
  // for effect, those are always considered to be stronger than anything else
  // but they can't darken a place completely
  if (pass2)
    for (int x = min_x; x <= max_x; x++)
      for (int y = min_y; y <= max_y; y++)
        {
          maptile *m = op->map;
          sint16 nx = x;
          sint16 ny = y;

          if (!xy_normalise (m, nx, ny))
            continue;

          mapspace &ms = m->at (nx, ny);
          ms.update ();
          sint8 light = ms.light;

          if (expect_false (light < 0))
            apply_light<los_darken> (op, x - op->x, y - op->y, -light, light_atten [light + MAX_LIGHT_RADIUS]);
        }
}

/* blinded_sight() - sets all viewable squares to blocked except 
 * for the one the central one that the player occupies.  A little
 * odd that you can see yourself (and what your standing on), but
 * really need for any reasonable game play.
 */
static void
blinded_sight (object *op)
{
  op->contr->los[LOS_X0][LOS_Y0] = 3;
}

/*
 * update_los() recalculates the array which specifies what is
 * visible for the given player-object.
 */
void
update_los (object *op)
{
  if (QUERY_FLAG (op, FLAG_REMOVED))
    return;

  op->contr->clear_los ();

  if (QUERY_FLAG (op, FLAG_WIZ) /* ||XRAYS(op) */ )
    memset (op->contr->los, 0, sizeof (op->contr->los));
  else if (QUERY_FLAG (op, FLAG_BLIND))      /* player is blind */
    blinded_sight (op);
  else
    {
      do_los (op);
      apply_lights (op);
    }

  if (QUERY_FLAG (op, FLAG_XRAYS))
    for (int dx = -2; dx <= 2; dx++)
      for (int dy = -2; dy <= 2; dy++)
        op->contr->los[dx + LOS_X0][dy + LOS_X0] = 0;
}

/* update all_map_los is like update_all_los below,
 * but updates everyone on the map, no matter where they
 * are. This generally should not be used, as a per
 * specific map change doesn't make much sense when tiling
 * is considered (lowering darkness would certainly be a
 * strange effect if done on a tile map, as it makes
 * the distinction between maps much more obvious to the
 * players, which is should not be.
 * Currently, this function is called from the
 * change_map_light function
 */
void
update_all_map_los (maptile *map)
{
  for_all_players (pl)
    if (pl->ob && pl->ob->map == map)
      pl->do_los = 1;
}

/*
 * This function makes sure that update_los() will be called for all
 * players on the given map within the next frame.
 * It is triggered by removal or inserting of objects which blocks
 * the sight in the map.
 * Modified by MSW 2001-07-12 to take a coordinate of the changed
 * position, and to also take map tiling into account.  This change
 * means that just being on the same map is not sufficient - the
 * space that changes must be withing your viewable area.
 *
 * map is the map that changed, x and y are the coordinates.
 */
void
update_all_los (const maptile *map, int x, int y)
{
  for_all_players (pl)
    {
      /* Player should not have a null map, but do this
       * check as a safety
       */
      if (!pl->ob || !pl->ob->map || !pl->ns)
        continue;

      /* Same map is simple case - see if pl is close enough.
       * Note in all cases, we did the check for same map first,
       * and then see if the player is close enough and update
       * los if that is the case.  If the player is on the
       * corresponding map, but not close enough, then the
       * player can't be on another map that may be closer,
       * so by setting it up this way, we trim processing
       * some.
       */
      if (pl->ob->map == map)
        {
          if ((abs (pl->ob->x - x) <= pl->ns->mapx / 2) && (abs (pl->ob->y - y) <= pl->ns->mapy / 2))
            pl->do_los = 1;
        }

      /* Now we check to see if player is on adjacent
       * maps to the one that changed and also within
       * view.  The tile_maps[] could be null, but in that
       * case it should never match the pl->ob->map, so
       * we want ever try to dereference any of the data in it.
       *
       * The logic for 0 and 3 is to see how far the player is
       * from the edge of the map (height/width) - pl->ob->(x,y)
       * and to add current position on this map - that gives a
       * distance.
       * For 1 and 2, we check to see how far the given
       * coordinate (x,y) is from the corresponding edge,
       * and then add the players location, which gives
       * a distance.
       */
      else if (pl->ob->map == map->tile_map[0])
        {
          if ((abs (pl->ob->x - x) <= pl->ns->mapx / 2) && (abs (y + map->tile_map[0]->height - pl->ob->y) <= pl->ns->mapy / 2))
            pl->do_los = 1;
        }
      else if (pl->ob->map == map->tile_map[2])
        {
          if ((abs (pl->ob->x - x) <= pl->ns->mapx / 2) && (abs (pl->ob->y + map->height - y) <= pl->ns->mapy / 2))
            pl->do_los = 1;
        }
      else if (pl->ob->map == map->tile_map[1])
        {
          if ((abs (pl->ob->x + map->width - x) <= pl->ns->mapx / 2) && (abs (pl->ob->y - y) <= pl->ns->mapy / 2))
            pl->do_los = 1;
        }
      else if (pl->ob->map == map->tile_map[3])
        {
          if ((abs (x + map->tile_map[3]->width - pl->ob->x) <= pl->ns->mapx / 2) && (abs (pl->ob->y - y) <= pl->ns->mapy / 2))
            pl->do_los = 1;
        }
    }
}

/*
 * make_sure_seen: The object is supposed to be visible through walls, thus
 * check if any players are nearby, and edit their LOS array.
 */
void
make_sure_seen (const object *op)
{
  for_all_players (pl)
    if (pl->ob->map == op->map &&
        pl->ob->y - pl->ns->mapy / 2 <= op->y &&
        pl->ob->y + pl->ns->mapy / 2 >= op->y && pl->ob->x - pl->ns->mapx / 2 <= op->x && pl->ob->x + pl->ns->mapx / 2 >= op->x)
      pl->los[op->x - pl->ob->x + LOS_X0][op->y - pl->ob->y + LOS_X0] = 0;
}

/*
 * make_sure_not_seen: The object which is supposed to be visible through
 * walls has just been removed from the map, so update the los of any
 * players within its range
 */
void
make_sure_not_seen (const object *op)
{
  for_all_players (pl)
    if (pl->ob->map == op->map &&
        pl->ob->y - pl->ns->mapy / 2 <= op->y &&
        pl->ob->y + pl->ns->mapy / 2 >= op->y && pl->ob->x - pl->ns->mapx / 2 <= op->x && pl->ob->x + pl->ns->mapx / 2 >= op->x)
      pl->do_los = 1;
}
Revision:	1.44
Committed:	Sun Dec 21 21:20:35 2008 UTC (15 years, 5 months ago) by root
Content type:	text/plain
Branch:	MAIN
Changes since 1.43:	+11 -12 lines
Log Message:	* empty log message *
#	User	Rev	Content
1	elmex	1.1	/*
2	root	1.29	* This file is part of Deliantra, the Roguelike Realtime MMORPG.
3	pippijn	1.19	*
4	root	1.30	* Copyright (©) 2005,2006,2007,2008 Marc Alexander Lehmann / Robin Redeker / the Deliantra team
5	root	1.26	* Copyright (©) 2002,2007 Mark Wedel & Crossfire Development Team
6			* Copyright (©) 1992,2007 Frank Tore Johansen
7	pippijn	1.19	*
8	root	1.29	* Deliantra is free software: you can redistribute it and/or modify
9	root	1.28	* it under the terms of the GNU General Public License as published by
10			* the Free Software Foundation, either version 3 of the License, or
11			* (at your option) any later version.
12	pippijn	1.19	*
13	root	1.28	* This program is distributed in the hope that it will be useful,
14			* but WITHOUT ANY WARRANTY; without even the implied warranty of
15			* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16			* GNU General Public License for more details.
17	pippijn	1.19	*
18	root	1.28	* You should have received a copy of the GNU General Public License
19			* along with this program. If not, see <http://www.gnu.org/licenses/>.
20	root	1.26	*
21	root	1.29	* The authors can be reached via e-mail to <support@deliantra.net>
22	pippijn	1.19	*/
23	elmex	1.1
24			/* Nov 95 - inserted USE_LIGHTING code stuff in here - b.t. */
25
26			#include <global.h>
27	root	1.41	#include <cmath>
28	elmex	1.1
29	root	1.41	static void expand_lighted_sight (object *op);
30	elmex	1.1
31	root	1.41	enum {
32			LOS_XI = 0x01,
33			LOS_YI = 0x02,
34			};
35
36			struct los_info
37			{
38	root	1.43	sint8 xo, yo; // obscure angle
39			sint8 xe, ye; // angle deviation
40			uint8 culled; // culled from "tree"
41			uint8 queued; // already queued
42	root	1.41	uint8 visible;
43	root	1.43	uint8 flags; // LOS_XI/YI
44	root	1.41	};
45
46			// temporary storage for the los algorithm,
47			// one los_info for each lightable map space
48			static los_info los[MAP_CLIENT_X][MAP_CLIENT_Y];
49
50			struct point
51			{
52			sint8 x, y;
53			};
54
55			// minimum size, but must be a power of two
56			#define QUEUE_LENGTH ((MAP_CLIENT_X + MAP_CLIENT_Y) * 2)
57
58			// a queue of spaces to calculate
59			static point queue [QUEUE_LENGTH];
60			static int q1, q2; // queue start, end
61	elmex	1.1
62			/*
63	root	1.41	* Clears/initialises the los-array associated to the player
64			* controlling the object.
65	elmex	1.1	*/
66	root	1.41	void
67	root	1.42	player::clear_los (sint8 value)
68	root	1.41	{
69	root	1.42	memset (los, value, sizeof (los));
70	root	1.41	}
71	elmex	1.1
72	root	1.41	// enqueue a single mapspace, but only if it hasn't
73			// been enqueued yet.
74	root	1.4	static void
75	root	1.41	enqueue (sint8 dx, sint8 dy, uint8 flags = 0)
76	root	1.4	{
77	root	1.41	sint8 x = LOS_X0 + dx;
78			sint8 y = LOS_Y0 + dy;
79
80			if (x < 0 \|\| x >= MAP_CLIENT_X) return;
81			if (y < 0 \|\| y >= MAP_CLIENT_Y) return;
82
83			los_info &l = los[x][y];
84
85			l.flags \|= flags;
86
87			if (l.queued)
88			return;
89	elmex	1.1
90	root	1.41	l.queued = 1;
91
92			queue[q1].x = dx;
93			queue[q1].y = dy;
94	elmex	1.1
95	root	1.41	q1 = (q1 + 1) & (QUEUE_LENGTH - 1);
96	elmex	1.1	}
97
98	root	1.41	// run the los algorithm
99			// this is a variant of a spiral los algorithm taken from
100			// http://www.geocities.com/temerra/los_rays.html
101			// which has been simplified and changed considerably, but
102			// still is basically the same algorithm.
103			static void
104			do_los (object *op)
105	root	1.4	{
106	root	1.41	player *pl = op->contr;
107	root	1.4
108	root	1.41	int max_radius = max (pl->ns->mapx, pl->ns->mapy) / 2;
109	root	1.4
110	root	1.41	memset (los, 0, sizeof (los));
111	root	1.4
112	root	1.41	q1 = 0; q2 = 0; // initialise queue, not strictly required
113			enqueue (0, 0); // enqueue center
114	root	1.4
115	root	1.41	// treat the origin specially
116			los[LOS_X0][LOS_Y0].visible = 1;
117			pl->los[LOS_X0][LOS_Y0] = 0;
118
119			// loop over all enqueued points until the queue is empty
120			// the order in which this is done ensures that we
121			// never touch a mapspace whose input spaces we haven't checked
122			// yet.
123			while (q1 != q2)
124			{
125			sint8 dx = queue[q2].x;
126			sint8 dy = queue[q2].y;
127	root	1.4
128	root	1.41	q2 = (q2 + 1) & (QUEUE_LENGTH - 1);
129	root	1.4
130	root	1.41	sint8 x = LOS_X0 + dx;
131			sint8 y = LOS_Y0 + dy;
132	elmex	1.1
133	root	1.41	//int distance = idistance (dx, dy); if (distance > max_radius) continue;//D
134			int distance = 0;//D
135	root	1.4
136	root	1.41	los_info &l = los[x][y];
137	elmex	1.1
138	root	1.41	if (expect_true (l.flags & (LOS_XI \| LOS_YI)))
139			{
140			l.culled = 1;
141	elmex	1.1
142	root	1.41	// check contributing spaces, first horizontal
143			if (expect_true (l.flags & LOS_XI))
144			{
145			los_info *xi = &los[x - sign (dx)][y];
146	elmex	1.1
147	root	1.41	// don't cull unless obscured
148			l.culled &= !xi->visible;
149	elmex	1.1
150	root	1.41	/* merge input space */
151			if (expect_false (xi->xo \|\| xi->yo))
152			{
153			// The X input can provide two main pieces of information:
154			// 1. Progressive X obscurity.
155			// 2. Recessive Y obscurity.
156
157			// Progressive X obscurity, favouring recessive input angle
158			if (xi->xe > 0 && l.xo == 0)
159			{
160			l.xe = xi->xe - xi->yo;
161			l.ye = xi->ye + xi->yo;
162			l.xo = xi->xo;
163			l.yo = xi->yo;
164			}
165	root	1.4
166	root	1.41	// Recessive Y obscurity
167			if (xi->ye <= 0 && xi->yo > 0 && xi->xe > 0)
168			{
169			l.ye = xi->yo + xi->ye;
170			l.xe = xi->xe - xi->yo;
171			l.xo = xi->xo;
172			l.yo = xi->yo;
173			}
174			}
175			}
176
177			// check contributing spaces, last vertical, identical structure
178			if (expect_true (l.flags & LOS_YI))
179			{
180			los_info *yi = &los[x][y - sign (dy)];
181	elmex	1.1
182	root	1.41	// don't cull unless obscured
183			l.culled &= !yi->visible;
184	elmex	1.1
185	root	1.41	/* merge input space */
186			if (expect_false (yi->yo \|\| yi->xo))
187			{
188			// The Y input can provide two main pieces of information:
189			// 1. Progressive Y obscurity.
190			// 2. Recessive X obscurity.
191
192			// Progressive Y obscurity, favouring recessive input angle
193			if (yi->ye > 0 && l.yo == 0)
194			{
195			l.ye = yi->ye - yi->xo;
196			l.xe = yi->xe + yi->xo;
197			l.yo = yi->yo;
198			l.xo = yi->xo;
199			}
200	elmex	1.1
201	root	1.41	// Recessive X obscurity
202			if (yi->xe <= 0 && yi->xo > 0 && yi->ye > 0)
203			{
204			l.xe = yi->xo + yi->xe;
205			l.ye = yi->ye - yi->xo;
206			l.yo = yi->yo;
207			l.xo = yi->xo;
208			}
209			}
210			}
211	elmex	1.1
212	root	1.41	// check whether this space blocks the view
213			maptile *m = op->map;
214			sint16 nx = op->x + dx;
215			sint16 ny = op->y + dy;
216	elmex	1.1
217	root	1.41	if (expect_true (!xy_normalise (m, nx, ny))
218			\|\| expect_false (m->at (nx, ny).flags () & P_BLOCKSVIEW))
219			{
220			l.xo = l.xe = abs (dx);
221			l.yo = l.ye = abs (dy);
222	elmex	1.1
223	root	1.41	// we obscure dependents, but might be visible
224			// copy the los from the square towards the player,
225			// so outward diagonal corners are lit.
226			pl->los[x][y] = los[x - sign0 (dx)][y - sign0 (dy)].visible ? 0 : LOS_BLOCKED;
227			l.visible = false;
228			}
229			else
230			{
231			// we are not blocked, so calculate visibility, by checking
232			// whether we are inside or outside the shadow
233			l.visible = (l.xe <= 0 \|\| l.xe > l.xo)
234			&& (l.ye <= 0 \|\| l.ye > l.yo);
235
236			pl->los[x][y] = l.culled ? LOS_BLOCKED
237			: l.visible ? max (0, 2 - max_radius + distance)
238			: 3;
239	root	1.37	}
240	root	1.41
241	root	1.37	}
242	root	1.4
243	root	1.41	// Expands by the unit length in each component's current direction.
244			// If a component has no direction, then it is expanded in both of its
245			// positive and negative directions.
246			if (!l.culled)
247			{
248			if (dx >= 0) enqueue (dx + 1, dy, LOS_XI);
249			if (dx <= 0) enqueue (dx - 1, dy, LOS_XI);
250			if (dy >= 0) enqueue (dx, dy + 1, LOS_YI);
251			if (dy <= 0) enqueue (dx, dy - 1, LOS_YI);
252			}
253			}
254	elmex	1.1	}
255
256			/* returns true if op carries one or more lights
257			* This is a trivial function now days, but it used to
258			* be a bit longer. Probably better for callers to just
259			* check the op->glow_radius instead of calling this.
260			*/
261	root	1.4	int
262			has_carried_lights (const object *op)
263			{
264			/* op may glow! */
265			if (op->glow_radius > 0)
266			return 1;
267
268			return 0;
269			}
270
271	root	1.32	/* radius, distance => lightness adjust */
272	root	1.44	static sint8 light_atten[MAX_LIGHT_RADIUS * 2 + 1][MAX_LIGHT_RADIUS * 3 / 2 + 1];
273	root	1.32
274	root	1.44	static struct los_init
275	root	1.32	{
276	root	1.44	los_init ()
277	root	1.32	{
278			for (int radius = -MAX_LIGHT_RADIUS; radius <= MAX_LIGHT_RADIUS; ++radius)
279	root	1.35	for (int distance = 0; distance <= MAX_LIGHT_RADIUS * 3 / 2; ++distance)
280	root	1.32	{
281			// max intensity
282	root	1.36	int intensity = min (LOS_MAX, abs (radius) + 1);
283	root	1.32
284			// actual intensity
285			intensity = max (0, lerp_rd (distance, 0, abs (radius) + 1, intensity, 0));
286
287	root	1.44	light_atten [radius + MAX_LIGHT_RADIUS][distance] = radius < 0
288	root	1.35	? min (3, intensity)
289	root	1.36	: LOS_MAX - intensity;
290	root	1.32	}
291			}
292	root	1.44	} los_init;
293	root	1.32
294	root	1.39	sint8
295			los_brighten (sint8 b, sint8 l)
296			{
297			return b == LOS_BLOCKED ? b : min (b, l);
298			}
299
300			sint8
301			los_darken (sint8 b, sint8 l)
302			{
303			return max (b, l);
304			}
305
306			template<sint8 change_it (sint8, sint8)>
307			static void
308	root	1.44	apply_light (object op, int dx, int dy, int light, const sint8 atten_table)
309	root	1.39	{
310	root	1.41	// min or max the circular area around basex, basey
311	root	1.39	player *pl = op->contr;
312
313	root	1.41	dx += LOS_X0;
314			dy += LOS_Y0;
315
316			int hx = op->contr->ns->mapx / 2;
317			int hy = op->contr->ns->mapy / 2;
318
319			int ax0 = max (LOS_X0 - hx, dx - light);
320			int ay0 = max (LOS_Y0 - hy, dy - light);
321			int ax1 = min (dx + light, LOS_X0 + hx);
322			int ay1 = min (dy + light, LOS_Y0 + hy);
323	root	1.39
324			for (int ax = ax0; ax <= ax1; ax++)
325			for (int ay = ay0; ay <= ay1; ay++)
326	root	1.41	pl->los[ax][ay] =
327	root	1.44	change_it (pl->los[ax][ay], atten_table [idistance (ax - dx, ay - dy)]);
328	root	1.39	}
329
330			/* add light, by finding all (non-null) nearby light sources, then
331			* mark those squares specially.
332			*/
333	root	1.4	static void
334	root	1.41	apply_lights (object *op)
335	root	1.4	{
336	root	1.39	int darklevel, mflags, light, x1, y1;
337	root	1.6	maptile *m = op->map;
338	root	1.4	sint16 nx, ny;
339
340	root	1.14	darklevel = m->darkness;
341	root	1.4
342			/* If the player can see in the dark, lower the darklevel for him */
343			if (QUERY_FLAG (op, FLAG_SEE_IN_DARK))
344	root	1.36	darklevel -= LOS_MAX / 2;
345	root	1.4
346			/* Do a sanity check. If not valid, some code below may do odd
347			* things.
348			*/
349			if (darklevel > MAX_DARKNESS)
350			{
351	root	1.15	LOG (llevError, "Map darkness for %s on %s is too high (%d)\n", &op->name, &op->map->path, darklevel);
352	root	1.4	darklevel = MAX_DARKNESS;
353	elmex	1.1	}
354
355	root	1.32	int half_x = op->contr->ns->mapx / 2;
356			int half_y = op->contr->ns->mapy / 2;
357
358			int min_x = op->x - half_x - MAX_LIGHT_RADIUS;
359			int min_y = op->y - half_y - MAX_LIGHT_RADIUS;
360			int max_x = op->x + half_x + MAX_LIGHT_RADIUS;
361			int max_y = op->y + half_y + MAX_LIGHT_RADIUS;
362
363			int pass2 = 0; // negative lights have an extra pass
364
365	root	1.39	if (darklevel < 1)
366			pass2 = 1;
367			else
368			{
369			/* first, make everything totally dark */
370	root	1.41	for (int dx = -half_x; dx <= half_x; dx++)
371			for (int dy = -half_x; dy <= half_y; dy++)
372			if (op->contr->los[dx + LOS_X0][dy + LOS_Y0] != LOS_BLOCKED)
373			op->contr->los[dx + LOS_X0][dy + LOS_Y0] = LOS_MAX;
374	root	1.39
375			/*
376			* Only process the area of interest.
377	root	1.41	* the basex, basey values represent the position in the op->contr->los
378			* array. Its easier to just increment them here (and start with the right
379	root	1.39	* value) than to recalculate them down below.
380			*/
381	root	1.41	for (int x = min_x; x <= max_x; x++)
382			for (int y = min_y; y <= max_y; y++)
383	root	1.39	{
384			maptile *m = op->map;
385			sint16 nx = x;
386			sint16 ny = y;
387
388			if (!xy_normalise (m, nx, ny))
389			continue;
390
391			mapspace &ms = m->at (nx, ny);
392			ms.update ();
393			sint8 light = ms.light;
394
395			if (expect_false (light))
396			if (light < 0)
397			pass2 = 1;
398			else
399	root	1.44	apply_light<los_brighten> (op, x - op->x, y - op->y, light, light_atten [light + MAX_LIGHT_RADIUS]);
400	root	1.39	}
401
402			/* grant some vision to the player, based on the darklevel */
403	root	1.32	{
404	root	1.44	int light = clamp (MAX_DARKNESS - darklevel, 0, MAX_LIGHT_RADIUS);
405	root	1.39
406	root	1.44	apply_light<los_brighten> (op, 0, 0, light, light_atten [light + MAX_LIGHT_RADIUS]);
407	root	1.32	}
408	root	1.39	}
409	root	1.4
410	root	1.38	// possibly do 2nd pass for rare negative glow radii
411	root	1.39	// for effect, those are always considered to be stronger than anything else
412			// but they can't darken a place completely
413			if (pass2)
414	root	1.41	for (int x = min_x; x <= max_x; x++)
415			for (int y = min_y; y <= max_y; y++)
416	root	1.4	{
417	root	1.32	maptile *m = op->map;
418			sint16 nx = x;
419			sint16 ny = y;
420	root	1.4
421	root	1.32	if (!xy_normalise (m, nx, ny))
422			continue;
423	root	1.4
424	root	1.32	mapspace &ms = m->at (nx, ny);
425			ms.update ();
426			sint8 light = ms.light;
427	root	1.4
428	root	1.32	if (expect_false (light < 0))
429	root	1.44	apply_light<los_darken> (op, x - op->x, y - op->y, -light, light_atten [light + MAX_LIGHT_RADIUS]);
430	root	1.18	}
431	elmex	1.1	}
432
433	root	1.31	/* blinded_sight() - sets all viewable squares to blocked except
434	elmex	1.1	* for the one the central one that the player occupies. A little
435			* odd that you can see yourself (and what your standing on), but
436			* really need for any reasonable game play.
437			*/
438	root	1.4	static void
439			blinded_sight (object *op)
440			{
441	root	1.41	op->contr->los[LOS_X0][LOS_Y0] = 3;
442	elmex	1.1	}
443
444			/*
445			* update_los() recalculates the array which specifies what is
446			* visible for the given player-object.
447			*/
448	root	1.4	void
449			update_los (object *op)
450			{
451			if (QUERY_FLAG (op, FLAG_REMOVED))
452			return;
453	elmex	1.1
454	root	1.42	op->contr->clear_los ();
455	root	1.27
456	root	1.4	if (QUERY_FLAG (op, FLAG_WIZ) /* \|\|XRAYS(op) */ )
457	root	1.41	memset (op->contr->los, 0, sizeof (op->contr->los));
458			else if (QUERY_FLAG (op, FLAG_BLIND)) /* player is blind */
459	root	1.4	blinded_sight (op);
460			else
461	root	1.41	{
462			do_los (op);
463			apply_lights (op);
464			}
465	root	1.4
466			if (QUERY_FLAG (op, FLAG_XRAYS))
467	root	1.41	for (int dx = -2; dx <= 2; dx++)
468			for (int dy = -2; dy <= 2; dy++)
469			op->contr->los[dx + LOS_X0][dy + LOS_X0] = 0;
470	elmex	1.1	}
471
472			/* update all_map_los is like update_all_los below,
473			* but updates everyone on the map, no matter where they
474	root	1.12	* are. This generally should not be used, as a per
475	elmex	1.1	* specific map change doesn't make much sense when tiling
476			* is considered (lowering darkness would certainly be a
477			* strange effect if done on a tile map, as it makes
478			* the distinction between maps much more obvious to the
479			* players, which is should not be.
480			* Currently, this function is called from the
481			* change_map_light function
482			*/
483	root	1.4	void
484	root	1.6	update_all_map_los (maptile *map)
485	root	1.4	{
486	root	1.11	for_all_players (pl)
487	root	1.12	if (pl->ob && pl->ob->map == map)
488	root	1.11	pl->do_los = 1;
489	elmex	1.1	}
490
491			/*
492			* This function makes sure that update_los() will be called for all
493			* players on the given map within the next frame.
494			* It is triggered by removal or inserting of objects which blocks
495			* the sight in the map.
496			* Modified by MSW 2001-07-12 to take a coordinate of the changed
497			* position, and to also take map tiling into account. This change
498			* means that just being on the same map is not sufficient - the
499			* space that changes must be withing your viewable area.
500			*
501			* map is the map that changed, x and y are the coordinates.
502			*/
503	root	1.4	void
504	root	1.6	update_all_los (const maptile *map, int x, int y)
505	root	1.4	{
506	root	1.11	for_all_players (pl)
507	root	1.4	{
508			/* Player should not have a null map, but do this
509			* check as a safety
510			*/
511	root	1.12	if (!pl->ob \|\| !pl->ob->map \|\| !pl->ns)
512	root	1.4	continue;
513
514			/* Same map is simple case - see if pl is close enough.
515			* Note in all cases, we did the check for same map first,
516			* and then see if the player is close enough and update
517			* los if that is the case. If the player is on the
518			* corresponding map, but not close enough, then the
519			* player can't be on another map that may be closer,
520			* so by setting it up this way, we trim processing
521			* some.
522			*/
523			if (pl->ob->map == map)
524			{
525	root	1.10	if ((abs (pl->ob->x - x) <= pl->ns->mapx / 2) && (abs (pl->ob->y - y) <= pl->ns->mapy / 2))
526	root	1.4	pl->do_los = 1;
527	root	1.2	}
528	root	1.12
529	root	1.4	/* Now we check to see if player is on adjacent
530			* maps to the one that changed and also within
531			* view. The tile_maps[] could be null, but in that
532			* case it should never match the pl->ob->map, so
533			* we want ever try to dereference any of the data in it.
534	root	1.12	*
535			* The logic for 0 and 3 is to see how far the player is
536	root	1.4	* from the edge of the map (height/width) - pl->ob->(x,y)
537			* and to add current position on this map - that gives a
538			* distance.
539			* For 1 and 2, we check to see how far the given
540			* coordinate (x,y) is from the corresponding edge,
541			* and then add the players location, which gives
542			* a distance.
543			*/
544			else if (pl->ob->map == map->tile_map[0])
545			{
546	root	1.13	if ((abs (pl->ob->x - x) <= pl->ns->mapx / 2) && (abs (y + map->tile_map[0]->height - pl->ob->y) <= pl->ns->mapy / 2))
547	root	1.4	pl->do_los = 1;
548	root	1.2	}
549	root	1.4	else if (pl->ob->map == map->tile_map[2])
550			{
551	root	1.13	if ((abs (pl->ob->x - x) <= pl->ns->mapx / 2) && (abs (pl->ob->y + map->height - y) <= pl->ns->mapy / 2))
552	root	1.4	pl->do_los = 1;
553	root	1.2	}
554	root	1.4	else if (pl->ob->map == map->tile_map[1])
555			{
556	root	1.13	if ((abs (pl->ob->x + map->width - x) <= pl->ns->mapx / 2) && (abs (pl->ob->y - y) <= pl->ns->mapy / 2))
557	root	1.4	pl->do_los = 1;
558	root	1.2	}
559	root	1.4	else if (pl->ob->map == map->tile_map[3])
560			{
561	root	1.13	if ((abs (x + map->tile_map[3]->width - pl->ob->x) <= pl->ns->mapx / 2) && (abs (pl->ob->y - y) <= pl->ns->mapy / 2))
562	root	1.4	pl->do_los = 1;
563	root	1.2	}
564	elmex	1.1	}
565			}
566
567			/*
568			* make_sure_seen: The object is supposed to be visible through walls, thus
569			* check if any players are nearby, and edit their LOS array.
570			*/
571	root	1.4	void
572			make_sure_seen (const object *op)
573			{
574	root	1.11	for_all_players (pl)
575	root	1.4	if (pl->ob->map == op->map &&
576	root	1.10	pl->ob->y - pl->ns->mapy / 2 <= op->y &&
577			pl->ob->y + pl->ns->mapy / 2 >= op->y && pl->ob->x - pl->ns->mapx / 2 <= op->x && pl->ob->x + pl->ns->mapx / 2 >= op->x)
578	root	1.41	pl->los[op->x - pl->ob->x + LOS_X0][op->y - pl->ob->y + LOS_X0] = 0;
579	elmex	1.1	}
580
581			/*
582			* make_sure_not_seen: The object which is supposed to be visible through
583			* walls has just been removed from the map, so update the los of any
584			* players within its range
585			*/
586	root	1.4	void
587			make_sure_not_seen (const object *op)
588			{
589	root	1.11	for_all_players (pl)
590	root	1.4	if (pl->ob->map == op->map &&
591	root	1.10	pl->ob->y - pl->ns->mapy / 2 <= op->y &&
592			pl->ob->y + pl->ns->mapy / 2 >= op->y && pl->ob->x - pl->ns->mapx / 2 <= op->x && pl->ob->x + pl->ns->mapx / 2 >= op->x)
593	root	1.4	pl->do_los = 1;
594	elmex	1.1	}