server/common/los.C

/*
 * This file is part of Deliantra, the Roguelike Realtime MMORPG.
 * 
 * Copyright (©) 2005,2006,2007,2008,2009 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 Affero 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 Affero GNU General Public License
 * and 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>
 */

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

#define SEE_IN_DARK_RADIUS 2
#define MAX_VISION 10 // maximum visible radius

// los flags
enum {
  FLG_XI      = 0x01, // we have an x-parent
  FLG_YI      = 0x02, // we have an y-parent
  FLG_BLOCKED = 0x04, // this space blocks the view
  FLG_QUEUED  = 0x80  // already queued in queue, or border
};

struct los_info
{
  uint8 flags;   // FLG_xxx
  uint8 culled;  // culled from "tree"
  uint8 visible;
  uint8 pad0;

  sint8 xo, yo;  // obscure angle
  sint8 xe, ye;  // angle deviation
};

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

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

  l.flags |= flags;

  if (l.flags & FLG_QUEUED)
    return;

  l.flags |= FLG_QUEUED;

  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)
{
  {
    memset (los, 0, sizeof (los));

    // we keep one line for ourselves, for the border flag
    // so the client area is actually MAP_CLIENT_(X|Y) - 2
    int half_x = min (LOS_X0 - 1, pl->ns->mapx / 2);
    int half_y = min (LOS_Y0 - 1, pl->ns->mapy / 2);

    // create borders, the corners are not touched
    for (int dx = -half_x; dx <= half_x; ++dx)
      los [dx + LOS_X0][LOS_Y0 - (half_y + 1)].flags =
      los [dx + LOS_X0][LOS_Y0 + (half_y + 1)].flags = FLG_QUEUED;

    for (int dy = -half_y; dy <= half_y; ++dy)
      los [LOS_X0 - (half_x + 1)][dy + LOS_Y0].flags =
      los [LOS_X0 + (half_x + 1)][dy + LOS_Y0].flags = FLG_QUEUED;

    // now reset the los area and also add blocked flags
    // which supposedly is faster than doing it inside the
    // spiral path algorithm below, except when very little
    // area is visible, in which case it is slower. which evens
    // out los calculation times between large and small los maps.
    // apply_lights also iterates over this area, maybe these
    // two passes could be combined somehow.
    unordered_mapwalk (pl->observe, -half_x, -half_y, half_x, half_y)
      {
        los_info &l = los [LOS_X0 + dx][LOS_Y0 + dy];
        l.flags = m->at (nx, ny).flags () & P_BLOCKSVIEW ? FLG_BLOCKED : 0;
      }
  }

  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;

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

      if (expect_true (l.flags & (FLG_XI | FLG_YI)))
        {
          l.culled = 1;
          l.xo = l.yo = l.xe = l.ye = 0;

          // check contributing spaces, first horizontal
          if (expect_true (l.flags & FLG_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 & FLG_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;
                    }
                }
            }

          if (l.flags & FLG_BLOCKED)
            {
              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 ? 0
                                        : 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, FLG_XI);
          if (dx <= 0) enqueue (dx - 1, dy, FLG_XI);
          if (dy >= 0) enqueue (dx, dy + 1, FLG_YI);
          if (dy <= 0) enqueue (dx, dy - 1, FLG_YI);
        }
    }
}

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

static struct los_init
{
  los_init ()
  {
    assert (("QUEUE_LENGTH, MAP_CLIENT_X and MAP_CLIENT_Y *must* be powers of two",
             !(QUEUE_LENGTH & (QUEUE_LENGTH - 1))));

    /* 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_ru (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_VISION; ++radius)
      for (int distance = 0; distance <= MAX_VISION * 3 / 2; ++distance)
        vision_atten [radius][distance] = distance <= radius ? clamp (lerp (radius, 0, MAX_DARKNESS, 3, 0), 0, 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 ();

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

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

  maprect *rects = pl->observe->map->split_to_tiles (
    pl->observe->x - half_x - MAX_LIGHT_RADIUS,
    pl->observe->y - half_y - MAX_LIGHT_RADIUS,
    pl->observe->x + half_x + MAX_LIGHT_RADIUS + 1,
    pl->observe->y + half_y + MAX_LIGHT_RADIUS + 1
  );

  /* If the player can see in the dark, increase light/vision radius */
  int bonus = op->flag [FLAG_SEE_IN_DARK] ? SEE_IN_DARK_RADIUS : 0;

  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++)
          max_it (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 (maprect *r = rects; r->m; ++r)
        rect_mapwalk (r, 0, 0)
          {
            mapspace &ms = m->at (nx, ny);
            ms.update ();
            sint8 light = ms.light;

            if (expect_false (light))
              if (light < 0)
                pass2 = 1;
              else
                {
                  light = clamp (light + bonus, 0, MAX_LIGHT_RADIUS);
                  apply_light<los_brighten> (pl, dx - pl->observe->x, dy - pl->observe->y, light, light_atten [light + MAX_LIGHT_RADIUS]);
                }
          }

      /* grant some vision to the player, based on outside, outdoor, and darklevel */
      {
        int light;

        if (!op->map->outdoor) // not outdoor, darkness becomes light radius
          light = MAX_DARKNESS - op->map->darkness;
        else if (op->map->darkness > 0) // outdoor and darkness > 0 => use darkness as max radius
          light = lerp_rd (maptile::outdoor_darkness + 0, 0, MAX_DARKNESS, MAX_DARKNESS - op->map->darkness, 0);
        else // outdoor and darkness <= 0 => start wide and decrease quickly
          light = lerp (maptile::outdoor_darkness + op->map->darkness, 0, MAX_DARKNESS, MAX_VISION, 2);

        light = clamp (light + bonus, 0, MAX_VISION);

        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 (maprect *r = rects; r->m; ++r)
      rect_mapwalk (r, 0, 0)
        {
          mapspace &ms = m->at (nx, ny);
          ms.update ();
          sint8 light = ms.light;

          if (expect_false (light < 0))
            {
              light = clamp (light - bonus, 0, MAX_DARKNESS);
              apply_light<los_darken> (pl, dx - pl->observe->x, dy - pl->observe->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;

  if (ob->flag [FLAG_WIZLOOK])
    clear_los (0);
  else if (observe->flag [FLAG_BLIND])      /* player is blind */
    {
      clear_los ();
      blinded_sight (this);
    }
  else
    {
      clear_los ();
      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_Y0], 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;

      rv_vector rv;

      get_rangevector_from_mapcoord (map, x, y, pl->ob, &rv);
      
      if ((abs (rv.distance_x) <= pl->ns->mapx / 2) && (abs (rv.distance_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_Y0] = 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.62
Committed:	Mon Oct 12 14:00:57 2009 UTC (14 years, 7 months ago) by root
Content type:	text/plain
Branch:	MAIN
CVS Tags:	rel-2_82, rel-2_81
Changes since 1.61:	+7 -6 lines
Log Message:	clarify license
#	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.60	* Copyright (©) 2005,2006,2007,2008,2009 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.62	* Deliantra is free software: you can redistribute it and/or modify it under
9			* the terms of the Affero GNU General Public License as published by the
10			* Free Software Foundation, either version 3 of the License, or (at your
11			* 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.62	* You should have received a copy of the Affero GNU General Public License
19			* and the GNU General Public License along with this program. If not, see
20			* <http://www.gnu.org/licenses/>.
21	root	1.26	*
22	root	1.29	* The authors can be reached via e-mail to <support@deliantra.net>
23	pippijn	1.19	*/
24	elmex	1.1
25			#include <global.h>
26	root	1.41	#include <cmath>
27	elmex	1.1
28	root	1.56	#define SEE_IN_DARK_RADIUS 2
29	root	1.57	#define MAX_VISION 10 // maximum visible radius
30	root	1.51
31	root	1.49	// los flags
32	root	1.41	enum {
33	root	1.49	FLG_XI = 0x01, // we have an x-parent
34			FLG_YI = 0x02, // we have an y-parent
35			FLG_BLOCKED = 0x04, // this space blocks the view
36			FLG_QUEUED = 0x80 // already queued in queue, or border
37	root	1.41	};
38
39			struct los_info
40			{
41	root	1.49	uint8 flags; // FLG_xxx
42			uint8 culled; // culled from "tree"
43			uint8 visible;
44			uint8 pad0;
45
46	root	1.43	sint8 xo, yo; // obscure angle
47			sint8 xe, ye; // angle deviation
48	root	1.41	};
49
50			// temporary storage for the los algorithm,
51			// one los_info for each lightable map space
52			static los_info los[MAP_CLIENT_X][MAP_CLIENT_Y];
53
54			struct point
55			{
56			sint8 x, y;
57			};
58
59			// minimum size, but must be a power of two
60			#define QUEUE_LENGTH ((MAP_CLIENT_X + MAP_CLIENT_Y) * 2)
61
62			// a queue of spaces to calculate
63			static point queue [QUEUE_LENGTH];
64			static int q1, q2; // queue start, end
65	elmex	1.1
66			/*
67	root	1.41	* Clears/initialises the los-array associated to the player
68			* controlling the object.
69	elmex	1.1	*/
70	root	1.41	void
71	root	1.42	player::clear_los (sint8 value)
72	root	1.41	{
73	root	1.42	memset (los, value, sizeof (los));
74	root	1.41	}
75	elmex	1.1
76	root	1.41	// enqueue a single mapspace, but only if it hasn't
77			// been enqueued yet.
78	root	1.4	static void
79	root	1.41	enqueue (sint8 dx, sint8 dy, uint8 flags = 0)
80	root	1.4	{
81	root	1.41	sint8 x = LOS_X0 + dx;
82			sint8 y = LOS_Y0 + dy;
83
84			los_info &l = los[x][y];
85
86			l.flags \|= flags;
87
88	root	1.49	if (l.flags & FLG_QUEUED)
89	root	1.41	return;
90	elmex	1.1
91	root	1.49	l.flags \|= FLG_QUEUED;
92	root	1.41
93			queue[q1].x = dx;
94			queue[q1].y = dy;
95	elmex	1.1
96	root	1.41	q1 = (q1 + 1) & (QUEUE_LENGTH - 1);
97	elmex	1.1	}
98
99	root	1.41	// run the los algorithm
100			// this is a variant of a spiral los algorithm taken from
101			// http://www.geocities.com/temerra/los_rays.html
102			// which has been simplified and changed considerably, but
103			// still is basically the same algorithm.
104			static void
105	root	1.48	calculate_los (player *pl)
106	root	1.4	{
107	root	1.49	{
108	root	1.52	memset (los, 0, sizeof (los));
109
110	root	1.49	// we keep one line for ourselves, for the border flag
111			// so the client area is actually MAP_CLIENT_(X\|Y) - 2
112			int half_x = min (LOS_X0 - 1, pl->ns->mapx / 2);
113			int half_y = min (LOS_Y0 - 1, pl->ns->mapy / 2);
114
115			// create borders, the corners are not touched
116			for (int dx = -half_x; dx <= half_x; ++dx)
117			los [dx + LOS_X0][LOS_Y0 - (half_y + 1)].flags =
118			los [dx + LOS_X0][LOS_Y0 + (half_y + 1)].flags = FLG_QUEUED;
119
120			for (int dy = -half_y; dy <= half_y; ++dy)
121			los [LOS_X0 - (half_x + 1)][dy + LOS_Y0].flags =
122			los [LOS_X0 + (half_x + 1)][dy + LOS_Y0].flags = FLG_QUEUED;
123
124			// now reset the los area and also add blocked flags
125			// which supposedly is faster than doing it inside the
126			// spiral path algorithm below, except when very little
127	root	1.54	// area is visible, in which case it is slower. which evens
128	root	1.49	// out los calculation times between large and small los maps.
129			// apply_lights also iterates over this area, maybe these
130			// two passes could be combined somehow.
131	root	1.52	unordered_mapwalk (pl->observe, -half_x, -half_y, half_x, half_y)
132			{
133			los_info &l = los [LOS_X0 + dx][LOS_Y0 + dy];
134			l.flags = m->at (nx, ny).flags () & P_BLOCKSVIEW ? FLG_BLOCKED : 0;
135			}
136	root	1.49	}
137	root	1.4
138	root	1.41	q1 = 0; q2 = 0; // initialise queue, not strictly required
139			enqueue (0, 0); // enqueue center
140	root	1.4
141	root	1.41	// treat the origin specially
142			los[LOS_X0][LOS_Y0].visible = 1;
143			pl->los[LOS_X0][LOS_Y0] = 0;
144
145			// loop over all enqueued points until the queue is empty
146			// the order in which this is done ensures that we
147			// never touch a mapspace whose input spaces we haven't checked
148			// yet.
149			while (q1 != q2)
150			{
151			sint8 dx = queue[q2].x;
152			sint8 dy = queue[q2].y;
153	root	1.4
154	root	1.41	q2 = (q2 + 1) & (QUEUE_LENGTH - 1);
155	root	1.4
156	root	1.41	sint8 x = LOS_X0 + dx;
157			sint8 y = LOS_Y0 + dy;
158	elmex	1.1
159	root	1.41	los_info &l = los[x][y];
160	elmex	1.1
161	root	1.49	if (expect_true (l.flags & (FLG_XI \| FLG_YI)))
162	root	1.41	{
163			l.culled = 1;
164	root	1.49	l.xo = l.yo = l.xe = l.ye = 0;
165	elmex	1.1
166	root	1.41	// check contributing spaces, first horizontal
167	root	1.49	if (expect_true (l.flags & FLG_XI))
168	root	1.41	{
169			los_info *xi = &los[x - sign (dx)][y];
170	elmex	1.1
171	root	1.41	// don't cull unless obscured
172			l.culled &= !xi->visible;
173	elmex	1.1
174	root	1.41	/* merge input space */
175			if (expect_false (xi->xo \|\| xi->yo))
176			{
177			// The X input can provide two main pieces of information:
178			// 1. Progressive X obscurity.
179			// 2. Recessive Y obscurity.
180
181			// Progressive X obscurity, favouring recessive input angle
182			if (xi->xe > 0 && l.xo == 0)
183			{
184			l.xe = xi->xe - xi->yo;
185			l.ye = xi->ye + xi->yo;
186			l.xo = xi->xo;
187			l.yo = xi->yo;
188			}
189	root	1.4
190	root	1.41	// Recessive Y obscurity
191			if (xi->ye <= 0 && xi->yo > 0 && xi->xe > 0)
192			{
193			l.ye = xi->yo + xi->ye;
194			l.xe = xi->xe - xi->yo;
195			l.xo = xi->xo;
196			l.yo = xi->yo;
197			}
198			}
199			}
200
201			// check contributing spaces, last vertical, identical structure
202	root	1.49	if (expect_true (l.flags & FLG_YI))
203	root	1.41	{
204			los_info *yi = &los[x][y - sign (dy)];
205	elmex	1.1
206	root	1.41	// don't cull unless obscured
207			l.culled &= !yi->visible;
208	elmex	1.1
209	root	1.41	/* merge input space */
210			if (expect_false (yi->yo \|\| yi->xo))
211			{
212			// The Y input can provide two main pieces of information:
213			// 1. Progressive Y obscurity.
214			// 2. Recessive X obscurity.
215
216			// Progressive Y obscurity, favouring recessive input angle
217			if (yi->ye > 0 && l.yo == 0)
218			{
219			l.ye = yi->ye - yi->xo;
220			l.xe = yi->xe + yi->xo;
221			l.yo = yi->yo;
222			l.xo = yi->xo;
223			}
224	elmex	1.1
225	root	1.41	// Recessive X obscurity
226			if (yi->xe <= 0 && yi->xo > 0 && yi->ye > 0)
227			{
228			l.xe = yi->xo + yi->xe;
229			l.ye = yi->ye - yi->xo;
230			l.yo = yi->yo;
231			l.xo = yi->xo;
232			}
233			}
234			}
235	elmex	1.1
236	root	1.49	if (l.flags & FLG_BLOCKED)
237	root	1.41	{
238			l.xo = l.xe = abs (dx);
239			l.yo = l.ye = abs (dy);
240	elmex	1.1
241	root	1.41	// we obscure dependents, but might be visible
242			// copy the los from the square towards the player,
243			// so outward diagonal corners are lit.
244			pl->los[x][y] = los[x - sign0 (dx)][y - sign0 (dy)].visible ? 0 : LOS_BLOCKED;
245	root	1.49
246	root	1.41	l.visible = false;
247			}
248			else
249			{
250			// we are not blocked, so calculate visibility, by checking
251			// whether we are inside or outside the shadow
252			l.visible = (l.xe <= 0 \|\| l.xe > l.xo)
253			&& (l.ye <= 0 \|\| l.ye > l.yo);
254
255			pl->los[x][y] = l.culled ? LOS_BLOCKED
256	root	1.49	: l.visible ? 0
257	root	1.41	: 3;
258	root	1.37	}
259	root	1.41
260	root	1.37	}
261	root	1.4
262	root	1.41	// Expands by the unit length in each component's current direction.
263			// If a component has no direction, then it is expanded in both of its
264			// positive and negative directions.
265			if (!l.culled)
266			{
267	root	1.49	if (dx >= 0) enqueue (dx + 1, dy, FLG_XI);
268			if (dx <= 0) enqueue (dx - 1, dy, FLG_XI);
269			if (dy >= 0) enqueue (dx, dy + 1, FLG_YI);
270			if (dy <= 0) enqueue (dx, dy - 1, FLG_YI);
271	root	1.41	}
272			}
273	elmex	1.1	}
274
275	root	1.32	/* radius, distance => lightness adjust */
276	root	1.44	static sint8 light_atten[MAX_LIGHT_RADIUS * 2 + 1][MAX_LIGHT_RADIUS * 3 / 2 + 1];
277	root	1.57	static sint8 vision_atten[MAX_VISION + 1][MAX_VISION * 3 / 2 + 1];
278	root	1.32
279	root	1.44	static struct los_init
280	root	1.32	{
281	root	1.44	los_init ()
282	root	1.32	{
283	root	1.49	assert (("QUEUE_LENGTH, MAP_CLIENT_X and MAP_CLIENT_Y must be powers of two",
284			!(QUEUE_LENGTH & (QUEUE_LENGTH - 1))));
285
286	root	1.45	/* for lights */
287	root	1.32	for (int radius = -MAX_LIGHT_RADIUS; radius <= MAX_LIGHT_RADIUS; ++radius)
288	root	1.35	for (int distance = 0; distance <= MAX_LIGHT_RADIUS * 3 / 2; ++distance)
289	root	1.32	{
290			// max intensity
291	root	1.36	int intensity = min (LOS_MAX, abs (radius) + 1);
292	root	1.32
293			// actual intensity
294	root	1.61	intensity = max (0, lerp_ru (distance, 0, abs (radius) + 1, intensity, 0));
295	root	1.32
296	root	1.44	light_atten [radius + MAX_LIGHT_RADIUS][distance] = radius < 0
297	root	1.35	? min (3, intensity)
298	root	1.36	: LOS_MAX - intensity;
299	root	1.32	}
300	root	1.45
301			/* for general vision */
302	root	1.57	for (int radius = 0; radius <= MAX_VISION; ++radius)
303			for (int distance = 0; distance <= MAX_VISION * 3 / 2; ++distance)
304			vision_atten [radius][distance] = distance <= radius ? clamp (lerp (radius, 0, MAX_DARKNESS, 3, 0), 0, 3) : 4;
305	root	1.32	}
306	root	1.44	} los_init;
307	root	1.32
308	root	1.39	sint8
309			los_brighten (sint8 b, sint8 l)
310			{
311			return b == LOS_BLOCKED ? b : min (b, l);
312			}
313
314			sint8
315			los_darken (sint8 b, sint8 l)
316			{
317			return max (b, l);
318			}
319
320			template<sint8 change_it (sint8, sint8)>
321			static void
322	root	1.48	apply_light (player pl, int dx, int dy, int light, const sint8 atten_table)
323	root	1.39	{
324	root	1.41	// min or max the circular area around basex, basey
325			dx += LOS_X0;
326			dy += LOS_Y0;
327
328	root	1.48	int hx = pl->ns->mapx / 2;
329			int hy = pl->ns->mapy / 2;
330	root	1.41
331			int ax0 = max (LOS_X0 - hx, dx - light);
332			int ay0 = max (LOS_Y0 - hy, dy - light);
333			int ax1 = min (dx + light, LOS_X0 + hx);
334			int ay1 = min (dy + light, LOS_Y0 + hy);
335	root	1.39
336			for (int ax = ax0; ax <= ax1; ax++)
337			for (int ay = ay0; ay <= ay1; ay++)
338	root	1.41	pl->los[ax][ay] =
339	root	1.44	change_it (pl->los[ax][ay], atten_table [idistance (ax - dx, ay - dy)]);
340	root	1.39	}
341
342			/* add light, by finding all (non-null) nearby light sources, then
343			* mark those squares specially.
344			*/
345	root	1.4	static void
346	root	1.48	apply_lights (player *pl)
347	root	1.4	{
348	root	1.48	object *op = pl->observe;
349			int darklevel = op->map->darklevel ();
350	root	1.4
351	root	1.48	int half_x = pl->ns->mapx / 2;
352			int half_y = pl->ns->mapy / 2;
353	root	1.32
354			int pass2 = 0; // negative lights have an extra pass
355
356	root	1.52	maprect *rects = pl->observe->map->split_to_tiles (
357			pl->observe->x - half_x - MAX_LIGHT_RADIUS,
358			pl->observe->y - half_y - MAX_LIGHT_RADIUS,
359			pl->observe->x + half_x + MAX_LIGHT_RADIUS + 1,
360			pl->observe->y + half_y + MAX_LIGHT_RADIUS + 1
361			);
362
363	root	1.57	/* If the player can see in the dark, increase light/vision radius */
364			int bonus = op->flag [FLAG_SEE_IN_DARK] ? SEE_IN_DARK_RADIUS : 0;
365
366	root	1.48	if (!darklevel)
367	root	1.39	pass2 = 1;
368			else
369			{
370			/* first, make everything totally dark */
371	root	1.41	for (int dx = -half_x; dx <= half_x; dx++)
372			for (int dy = -half_x; dy <= half_y; dy++)
373	root	1.49	max_it (pl->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.52	for (maprect *r = rects; r->m; ++r)
382			rect_mapwalk (r, 0, 0)
383	root	1.39	{
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	root	1.57	{
393			light = clamp (light + bonus, 0, MAX_LIGHT_RADIUS);
394			apply_light<los_brighten> (pl, dx - pl->observe->x, dy - pl->observe->y, light, light_atten [light + MAX_LIGHT_RADIUS]);
395			}
396	root	1.39	}
397
398	root	1.57	/* grant some vision to the player, based on outside, outdoor, and darklevel */
399	root	1.32	{
400	root	1.57	int light;
401	root	1.39
402	root	1.57	if (!op->map->outdoor) // not outdoor, darkness becomes light radius
403	root	1.58	light = MAX_DARKNESS - op->map->darkness;
404	root	1.57	else if (op->map->darkness > 0) // outdoor and darkness > 0 => use darkness as max radius
405			light = lerp_rd (maptile::outdoor_darkness + 0, 0, MAX_DARKNESS, MAX_DARKNESS - op->map->darkness, 0);
406			else // outdoor and darkness <= 0 => start wide and decrease quickly
407			light = lerp (maptile::outdoor_darkness + op->map->darkness, 0, MAX_DARKNESS, MAX_VISION, 2);
408
409	root	1.59	light = clamp (light + bonus, 0, MAX_VISION);
410	root	1.51
411	root	1.48	apply_light<los_brighten> (pl, 0, 0, light, vision_atten [light]);
412	root	1.32	}
413	root	1.39	}
414	root	1.4
415	root	1.38	// possibly do 2nd pass for rare negative glow radii
416	root	1.39	// for effect, those are always considered to be stronger than anything else
417			// but they can't darken a place completely
418			if (pass2)
419	root	1.52	for (maprect *r = rects; r->m; ++r)
420			rect_mapwalk (r, 0, 0)
421			{
422			mapspace &ms = m->at (nx, ny);
423			ms.update ();
424			sint8 light = ms.light;
425
426			if (expect_false (light < 0))
427	root	1.57	{
428			light = clamp (light - bonus, 0, MAX_DARKNESS);
429			apply_light<los_darken> (pl, dx - pl->observe->x, dy - pl->observe->y, -light, light_atten [light + MAX_LIGHT_RADIUS]);
430			}
431	root	1.52	}
432	elmex	1.1	}
433
434	root	1.31	/* blinded_sight() - sets all viewable squares to blocked except
435	elmex	1.1	* for the one the central one that the player occupies. A little
436			* odd that you can see yourself (and what your standing on), but
437			* really need for any reasonable game play.
438			*/
439	root	1.4	static void
440	root	1.48	blinded_sight (player *pl)
441	root	1.4	{
442	root	1.48	pl->los[LOS_X0][LOS_Y0] = 1;
443	elmex	1.1	}
444
445			/*
446			* update_los() recalculates the array which specifies what is
447			* visible for the given player-object.
448			*/
449	root	1.4	void
450	root	1.48	player::update_los ()
451	root	1.4	{
452	root	1.48	if (ob->flag [FLAG_REMOVED])//D really needed?
453	root	1.4	return;
454	elmex	1.1
455	root	1.48	if (ob->flag [FLAG_WIZLOOK])
456	root	1.49	clear_los (0);
457	root	1.48	else if (observe->flag [FLAG_BLIND]) /* player is blind */
458	root	1.49	{
459			clear_los ();
460			blinded_sight (this);
461			}
462	root	1.4	else
463	root	1.41	{
464	root	1.49	clear_los ();
465	root	1.48	calculate_los (this);
466			apply_lights (this);
467	root	1.41	}
468	root	1.4
469	root	1.48	if (observe->flag [FLAG_XRAYS])
470	root	1.41	for (int dx = -2; dx <= 2; dx++)
471			for (int dy = -2; dy <= 2; dy++)
472	root	1.49	min_it (los[dx + LOS_X0][dy + LOS_Y0], 1);
473	elmex	1.1	}
474
475			/* update all_map_los is like update_all_los below,
476			* but updates everyone on the map, no matter where they
477	root	1.12	* are. This generally should not be used, as a per
478	elmex	1.1	* specific map change doesn't make much sense when tiling
479			* is considered (lowering darkness would certainly be a
480			* strange effect if done on a tile map, as it makes
481			* the distinction between maps much more obvious to the
482			* players, which is should not be.
483			* Currently, this function is called from the
484			* change_map_light function
485			*/
486	root	1.4	void
487	root	1.6	update_all_map_los (maptile *map)
488	root	1.4	{
489	root	1.46	for_all_players_on_map (pl, map)
490			pl->do_los = 1;
491	elmex	1.1	}
492
493			/*
494			* This function makes sure that update_los() will be called for all
495			* players on the given map within the next frame.
496			* It is triggered by removal or inserting of objects which blocks
497			* the sight in the map.
498			* Modified by MSW 2001-07-12 to take a coordinate of the changed
499			* position, and to also take map tiling into account. This change
500			* means that just being on the same map is not sufficient - the
501			* space that changes must be withing your viewable area.
502			*
503			* map is the map that changed, x and y are the coordinates.
504			*/
505	root	1.4	void
506	root	1.6	update_all_los (const maptile *map, int x, int y)
507	root	1.4	{
508	root	1.46	map->at (x, y).invalidate ();
509
510	root	1.11	for_all_players (pl)
511	root	1.4	{
512			/* Player should not have a null map, but do this
513			* check as a safety
514			*/
515	root	1.12	if (!pl->ob \|\| !pl->ob->map \|\| !pl->ns)
516	root	1.4	continue;
517
518	root	1.61	rv_vector rv;
519
520			get_rangevector_from_mapcoord (map, x, y, pl->ob, &rv);
521
522			if ((abs (rv.distance_x) <= pl->ns->mapx / 2) && (abs (rv.distance_y) <= pl->ns->mapy / 2))
523			pl->do_los = 1;
524	elmex	1.1	}
525			}
526
527	root	1.48	static const int season_darkness[5][HOURS_PER_DAY] = {
528			/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 /
529			{ 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 },
530			{ 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 },
531			{ 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 },
532			{ 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 },
533			{ 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 }
534	root	1.47	};
535
536	root	1.48	/*
537			* Tell players the time and compute the darkness level for all maps in the game.
538			* MUST be called exactly once per hour.
539			*/
540	root	1.47	void
541	root	1.48	maptile::adjust_daylight ()
542	root	1.47	{
543			timeofday_t tod;
544
545			get_tod (&tod);
546
547	root	1.48	// log the time to log-1 every hour, and to chat every day
548			{
549			char todbuf[512];
550	root	1.47
551	root	1.48	format_tod (todbuf, sizeof (todbuf), &tod);
552	root	1.47
553	root	1.48	for_all_players (pl)
554			pl->ns->send_msg (NDI_GREY, tod.hour == 15 ? CHAT_CHANNEL : LOG_CHANNEL, todbuf);
555			}
556	root	1.47
557			/* If the light level isn't changing, no reason to do all
558			* the work below.
559			*/
560	root	1.48	sint8 new_darkness = season_darkness[tod.season][tod.hour];
561
562			if (new_darkness == maptile::outdoor_darkness)
563	root	1.47	return;
564
565	root	1.48	new_draw_info (NDI_GREY \| NDI_UNIQUE \| NDI_ALL, 1, 0,
566			new_darkness > maptile::outdoor_darkness
567			? "It becomes darker."
568			: "It becomes brighter.");
569	root	1.47
570	root	1.48	maptile::outdoor_darkness = new_darkness;
571	root	1.47
572	root	1.48	// we simply update the los for all players, which is unnecessarily
573			// costly, but should do for the moment.
574			for_all_players (pl)
575			pl->do_los = 1;
576	root	1.47	}
577
578	elmex	1.1	/*
579			* make_sure_seen: The object is supposed to be visible through walls, thus
580			* check if any players are nearby, and edit their LOS array.
581			*/
582	root	1.4	void
583			make_sure_seen (const object *op)
584			{
585	root	1.11	for_all_players (pl)
586	root	1.4	if (pl->ob->map == op->map &&
587	root	1.10	pl->ob->y - pl->ns->mapy / 2 <= op->y &&
588			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)
589	root	1.49	pl->los[op->x - pl->ob->x + LOS_X0][op->y - pl->ob->y + LOS_Y0] = 0;
590	elmex	1.1	}
591
592			/*
593			* make_sure_not_seen: The object which is supposed to be visible through
594			* walls has just been removed from the map, so update the los of any
595			* players within its range
596			*/
597	root	1.4	void
598			make_sure_not_seen (const object *op)
599			{
600	root	1.11	for_all_players (pl)
601	root	1.4	if (pl->ob->map == op->map &&
602	root	1.10	pl->ob->y - pl->ns->mapy / 2 <= op->y &&
603			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)
604	root	1.4	pl->do_los = 1;
605	elmex	1.1	}
606	root	1.52