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
calculate_los (player *pl)
{
  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 = pl->observe->map;
          sint16 nx = pl->observe->x + dx;
          sint16 ny = pl->observe->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 sint8 vision_atten[MAX_DARKNESS + 1][MAX_DARKNESS * 3 / 2 + 1];

static struct los_init
{
  los_init ()
  {
    /* for lights */
    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;
        }

    /* for general vision */
    for (int radius = 0; radius <= MAX_DARKNESS; ++radius)
      for (int distance = 0; distance <= MAX_DARKNESS * 3 / 2; ++distance)
        {
          vision_atten [radius][distance] = distance <= radius ? 3 : 4;
        }
  }
} 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 (player *pl, int dx, int dy, int light, const sint8 *atten_table)
{
  // min or max the circular area around basex, basey
  dx += LOS_X0;
  dy += LOS_Y0;

  int hx = pl->ns->mapx / 2;
  int hy = pl->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 (player *pl)
{
  object *op = pl->observe;
  int darklevel = op->map->darklevel ();

  /* If the player can see in the dark, lower the darklevel for him */
  if (op->flag [FLAG_SEE_IN_DARK])
    darklevel = max (0, darklevel - 2);

  int half_x = pl->ns->mapx / 2;
  int half_y = pl->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)
    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 (pl->los[dx + LOS_X0][dy + LOS_Y0] != LOS_BLOCKED)
            pl->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 = pl->observe->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> (pl, 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_DARKNESS);

        apply_light<los_brighten> (pl, 0, 0, light, vision_atten [light]);
      }
    }

  // 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 = pl->observe->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> (pl, 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 (player *pl)
{
  pl->los[LOS_X0][LOS_Y0] = 1;
}

/*
 * update_los() recalculates the array which specifies what is
 * visible for the given player-object.
 */
void
player::update_los ()
{
  if (ob->flag [FLAG_REMOVED])//D really needed?
    return;

  clear_los ();

  if (ob->flag [FLAG_WIZLOOK])
    memset (los, 0, sizeof (los));
  else if (observe->flag [FLAG_BLIND])      /* player is blind */
    blinded_sight (this);
  else
    {
      calculate_los (this);
      apply_lights (this);
    }

  if (observe->flag [FLAG_XRAYS])
    for (int dx = -2; dx <= 2; dx++)
      for (int dy = -2; dy <= 2; dy++)
        min_it (los[dx + LOS_X0][dy + LOS_X0], 1);
}

/* 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_on_map (pl, 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)
{
  map->at (x, y).invalidate ();

  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;
        }
    }
}

static const int season_darkness[5][HOURS_PER_DAY] = {
  /*0  1  2  3  4  5  6  7  8  9 10 11 12 13 14  1  2  3  4  5  6  7  8  9 10 11 12 13 */
  { 5, 5, 4, 4, 4, 4, 4, 3, 3, 3, 3, 2, 2, 1, 1, 0, 0, 0, 0, 1, 2, 2, 2, 3, 3, 4, 4, 5 },
  { 5, 5, 4, 4, 4, 4, 3, 3, 3, 2, 2, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4 },
  { 5, 4, 4, 4, 4, 3, 3, 2, 2, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 2, 3, 4, 4 },
  { 4, 4, 4, 4, 3, 3, 2, 2, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 2, 3, 4 },
  { 5, 5, 4, 4, 4, 3, 3, 3, 2, 2, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4 }
};

/*
 * Tell players the time and compute the darkness level for all maps in the game.
 * MUST be called exactly once per hour.
 */
void
maptile::adjust_daylight ()
{
  timeofday_t tod;

  get_tod (&tod);

  // log the time to log-1 every hour, and to chat every day
  {
    char todbuf[512];

    format_tod (todbuf, sizeof (todbuf), &tod);

    for_all_players (pl)
      pl->ns->send_msg (NDI_GREY, tod.hour == 15 ? CHAT_CHANNEL : LOG_CHANNEL, todbuf);
  }

  /* If the light level isn't changing, no reason to do all
   * the work below.
   */
  sint8 new_darkness = season_darkness[tod.season][tod.hour];

  if (new_darkness == maptile::outdoor_darkness)
    return;

  new_draw_info (NDI_GREY | NDI_UNIQUE | NDI_ALL, 1, 0,
                 new_darkness > maptile::outdoor_darkness
                 ? "It becomes darker."
                 : "It becomes brighter.");

  maptile::outdoor_darkness = new_darkness;

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