/*
* 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 .
*
* The authors can be reached via e-mail to
*/
#include //D
#include
#include
// 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)
{
{
// 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, evening
// 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.
rectangular_mapspace_iterate_begin (pl->observe, -half_x, half_x, -half_y, half_y)
los_info &l = los [LOS_X0 + dx][LOS_Y0 + dy];
l.flags = m && m->at (nx, ny).flags () & P_BLOCKSVIEW ? FLG_BLOCKED : 0;
rectangular_mapspace_iterate_end
}
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);
}
}
}
/* 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 ()
{
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_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
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 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++)
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.
*/
rectangular_mapspace_iterate_begin (pl->observe, -half_x - MAX_LIGHT_RADIUS, half_x + MAX_LIGHT_RADIUS, -half_y - MAX_LIGHT_RADIUS, half_y + MAX_LIGHT_RADIUS)
if (m)
{
mapspace &ms = m->at (nx, ny);
ms.update ();
sint8 light = ms.light;
if (expect_false (light))
if (light < 0)
pass2 = 1;
else
apply_light (pl, dx, dy, light, light_atten [light + MAX_LIGHT_RADIUS]);
}
rectangular_mapspace_iterate_end
/* grant some vision to the player, based on the darklevel */
{
int light = clamp (MAX_DARKNESS - darklevel, 0, MAX_DARKNESS);
apply_light (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)
rectangular_mapspace_iterate_begin (pl->observe, -half_x - MAX_LIGHT_RADIUS, half_x + MAX_LIGHT_RADIUS, -half_y - MAX_LIGHT_RADIUS, half_y + MAX_LIGHT_RADIUS)
if (m)
{
mapspace &ms = m->at (nx, ny);
ms.update ();
sint8 light = ms.light;
if (expect_false (light < 0))
apply_light (pl, dx, dy, -light, light_atten [light + MAX_LIGHT_RADIUS]);
}
rectangular_mapspace_iterate_end
}
/* 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;
/* 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_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;
}