/**
 **	Chunks.cc - Chunks (16x16 tiles) on the map.
 **
 **	Written: 10/1/98 - JSF
 **/

/*
Copyright (C) 2000 The Exult Team

This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
*/

#ifdef HAVE_CONFIG_H
#  include <config.h>
#endif

#include "chunks.h"
#include "chunkter.h"
#include "gamewin.h"
#include "gamemap.h"
#include "shapeinf.h"
#include "citerate.h"
#include "egg.h"
#include "objiter.h"
#include "objs.h"
#include "ordinfo.h"
#include "game.h"
#include "animate.h"
#include "dir.h"
#include "actors.h"

#if 0
#include <iostream>
using std::cout;
using std::endl;
#endif

#ifndef UNDER_CE
using std::memset;
using std::rand;
#endif

/*
 *	Create the cached data storage for a chunk.
 */

Chunk_cache::Chunk_cache
	(
	) : egg_objects(4)
	{
	memset((char *) &blocked[0], 0, sizeof(blocked));
	memset((char *) &eggs[0], 0, sizeof(eggs));
	}

/*
 *	Delete cache.
 */

Chunk_cache::~Chunk_cache
	(
	)
	{
	}

/*
 *	This mask gives the low bits (b0) for a given # of ztiles.
 */
unsigned long tmasks[16] = {		0x0L,
				        0x1L,
				        0x5L,
				       0x15L,
				       0x55L,
				      0x155L,
				      0x555L,
				     0x1555L,
				     0x5555L,
				    0x15555L,
				    0x55555L,
				   0x155555L,
				   0x555555L,
				  0x1555555L,
				  0x5555555L,
				 0x15555555L
			};

/*
 *	Set (actually, increment count) for a given tile.
 *	Want:	00 => 01,	01 => 10,
 *		10 => 11,	11 => 11.
 *	So:	newb0 = !b0 OR b1,
 *		newb1 =  b1 OR b0
 */
inline void Set_blocked_tile
	(
	unsigned long *blocked,		// 16x16 flags,
	int tx, int ty,			// Tile #'s (0-15).
	int lift,			// Starting lift to set.
	int ztiles			// # tiles along z-axis.
	)
	{
	unsigned long& val = blocked[ty*c_tiles_per_chunk + tx];
					// Get mask for the bit0's:
	unsigned long mask0 = tmasks[ztiles]<<2*lift;
	unsigned long mask1 = mask0<<1;	// Mask for the bit1's.
	unsigned long val0s = val&mask0;
	unsigned long Nval0s = (~val)&mask0;
	unsigned long val1s = val&mask1;
	unsigned long newval = val1s | (val0s<<1) | Nval0s | (val1s>>1);
					// Replace old values with new.
	val = (val&~(mask0|mask1)) | newval;
	}

/*
 *	Clear (actually, decrement count) for a given tile.
 *	Want:	00 => 00,	01 => 00,
 *		10 => 01,	11 => 10.
 *	So:	newb0 =  b1 AND !b0
 *		newb1 =  b1 AND  b0
 */
inline void Clear_blocked_tile
	(
	unsigned long *blocked,		// 16x16 flags,
	int tx, int ty,			// Tile #'s (0-15).
	int lift,			// Starting lift to set.
	int ztiles			// # tiles along z-axis.
	)
	{
	unsigned long& val = blocked[ty*c_tiles_per_chunk + tx];
					// Get mask for the bit0's:
	unsigned long mask0 = tmasks[ztiles]<<2*lift;
	unsigned long mask1 = mask0<<1;	// Mask for the bit1's.
	unsigned long val0s = val&mask0;
	unsigned long Nval0s = (~val)&mask0;
	unsigned long val1s = val&mask1;
	unsigned long newval = (val1s & (val0s<<1)) | ((val1s>>1) & Nval0s);
					// Replace old values with new.
	val = (val&~(mask0|mask1)) | newval;
	}

/*
 *	Set/unset the blocked flags in a region.
 */

void Chunk_cache::set_blocked
	(
	int startx, int starty,		// Starting tile #'s.
	int endx, int endy,		// Ending tile #'s.
	int lift, int ztiles,		// Lift, height info.
	bool set				// 1 to add, 0 to remove.
	)
	{
	if (set)
		{
		for (int y = starty; y <= endy; y++)
			for (int x = startx; x <= endx; x++)
				Set_blocked_tile(blocked, x, y, lift, ztiles);
		}
	else
		{
		for (int y = starty; y <= endy; y++)
			for (int x = startx; x <= endx; x++)
				Clear_blocked_tile(blocked,x, y, lift, ztiles);
		}
	}

/*
 *	Add/remove an object to/from the cache.
 */

void Chunk_cache::update_object
	(
	Map_chunk *chunk,
	Game_object *obj,
	bool add				// 1 to add, 0 to remove.
	)
	{
	Shape_info& info = obj->get_info();
	if (info.is_door())		// Special door list.
		if (add)
			doors.append(obj);
		else
			doors.remove(obj);
	int ztiles = info.get_3d_height(); 
	if (!ztiles || !info.is_solid())
		return;			// Skip if not an obstacle.
					// Get lower-right corner of obj.
	int endx = obj->get_tx();
	int endy = obj->get_ty();
	int frame = obj->get_framenum();// Get footprint dimensions.
	int xtiles = info.get_3d_xtiles(frame);
	int ytiles = info.get_3d_ytiles(frame);
	int lift = obj->get_lift();
	if (xtiles == 1 && ytiles == 1)	// Simplest case?
		{
		if (add)
			Set_blocked_tile(blocked, endx, endy, lift, ztiles);
		else
			Clear_blocked_tile(blocked, endx, endy, lift, ztiles);
		return;
		}
	Rectangle footprint = obj->get_footprint();
					// Go through interesected chunks.
	Chunk_intersect_iterator next_chunk(footprint);
	Rectangle tiles;
	int cx, cy;
	while (next_chunk.get_next(tiles, cx, cy))
		gmap->get_chunk(cx, cy)->set_blocked(tiles.x, tiles.y, 
			tiles.x + tiles.w - 1, tiles.y + tiles.h - 1, lift,
								ztiles, add);
	}

/*
 *	Set a rectangle of tiles within this chunk to be under the influence
 *	of a given egg, or clear it.
 */

void Chunk_cache::set_egged
	(
	Egg_object *egg,
	Rectangle& tiles,		// Range of tiles within chunk.
	bool add				// 1 to add, 0 to remove.
	)
	{
					// Egg already there?
	int eggnum = egg_objects.find(egg);
	if (add)
		{
		if (eggnum < 0)		// No, so add it.
			eggnum = egg_objects.put(egg);
		if (eggnum > 15)	// We only have 16 bits.
			eggnum = 15;
		short mask = (1<<eggnum);
		int stopx = tiles.x + tiles.w, stopy = tiles.y + tiles.h;
		for (int ty = tiles.y; ty < stopy; ++ty)
			for (int tx = tiles.x; tx < stopx; ++tx)
				eggs[ty*c_tiles_per_chunk + tx] |= mask;
		}
	else				// Remove.
		{
		if (eggnum < 0 || eggnum >= egg_objects.size())
			return;		// Not there.
		egg_objects[eggnum] = NULL;
		if (eggnum >= 15)	// We only have 16 bits.
			{		// Last one at 15 or above?
			for (Egg_vector::const_iterator it = 
				egg_objects.begin() + 15; 
					it != egg_objects.end(); ++it)
				if (*it != 0)
					// No, so leave bits alone.
					return;
			eggnum = 15;
			}
		short mask = ~(1<<eggnum);
		int stopx = tiles.x + tiles.w, stopy = tiles.y + tiles.h;
		for (int ty = tiles.y; ty < stopy; ty++)
			for (int tx = tiles.x; tx < stopx; tx++)
				eggs[ty*c_tiles_per_chunk + tx] &= mask;
		}
	}

/*
 *	Add/remove an egg to the cache.
 */

void Chunk_cache::update_egg
	(
	Map_chunk *chunk,
	Egg_object *egg,
	bool add				// 1 to add, 0 to remove.
	)
	{
					// Get footprint with abs. tiles.
	Rectangle foot = egg->get_area();
	if (!foot.w)
		return;			// Empty (probability = 0).
	Rectangle crect;		// Gets tiles within each chunk.
	int cx, cy;
	if (egg->is_solid_area())
		{			// Do solid rectangle.
		Chunk_intersect_iterator all(foot);
		while (all.get_next(crect, cx, cy))
			gmap->get_chunk(cx, cy)->set_egged(egg, crect, add);
		return;
		}
					// Just do the perimeter.
	Rectangle top(foot.x, foot.y, foot.w, 1);
	Rectangle bottom(foot.x, foot.y + foot.h - 1, foot.w, 1);
	Rectangle left(foot.x, foot.y + 1, 1, foot.h - 2);
	Rectangle right(foot.x + foot.w - 1, foot.y + 1, 1, foot.h - 2);
					// Go through intersected chunks.
	Chunk_intersect_iterator tops(top);
	while (tops.get_next(crect, cx, cy))
		gmap->get_chunk(cx, cy)->set_egged(egg, crect, add);
	Chunk_intersect_iterator bottoms(bottom);
	while (bottoms.get_next(crect, cx, cy))
		gmap->get_chunk(cx, cy)->set_egged(egg, crect, add);
	Chunk_intersect_iterator lefts(left);
	while (lefts.get_next(crect, cx, cy))
		gmap->get_chunk(cx, cy)->set_egged(egg, crect, add);
	Chunk_intersect_iterator rights(right);
	while (rights.get_next(crect, cx, cy))
		gmap->get_chunk(cx, cy)->set_egged(egg, crect, add);

	}

/*
 *	Create the cached data for a chunk.
 */

void Chunk_cache::setup
	(
	Map_chunk *chunk
	)
	{
	Game_object *obj;		// Set 'blocked' tiles.
	Object_iterator next(chunk->get_objects());
	while ((obj = next.get_next()) != 0)
		if (obj->is_egg())
			update_egg(chunk, (Egg_object *) obj, 1);
		else
			update_object(chunk, obj, 1);
			
	obj_list = chunk;
	}

/*
 *	Get highest blocked lift below a given level for a given tile.
 *
 *	Output:	Highest lift that's blocked by an object, or -1 if none.
 */

inline int Chunk_cache::get_highest_blocked
	(
	int lift,			// Look below this lift.
	unsigned long tflags		// Flags for desired tile.
	)
	{
	int i;				// Look downwards.
	for (i = lift - 1; i >= 0 && !(tflags & (3<<(2*i))); i--)
		;
	return i;
	}

/*
 *	Get highest blocked lift below a given level for a given tile.
 *
 *	Output:	Highest lift that's blocked by an object, or -1 if none.
 */

int Chunk_cache::get_highest_blocked
	(
	int lift,			// Look below this lift.
	int tx, int ty			// Square to test.
	)
	{
	return get_highest_blocked(lift, blocked[ty*c_tiles_per_chunk + tx]);
	}

/*
 *	Get highest blocked lift below a given level for a given tile.
 *
 *	Output:	Highest lift that's blocked by an object, or -1 if none.
 */

inline int Chunk_cache::get_lowest_blocked
	(
	int lift,			// Look above this lift.
	unsigned long tflags		// Flags for desired tile.
	)
	{
	int i;				// Look upward.
	for (i = lift; i < 16 && !(tflags & (3<<(2*i))); i++)
		;
	if (i == 16) return -1;
	return i;
	}

/*
 *	Get lowest blocked lift above a given level for a given tile.
 *
 *	Output:	Lowest lift that's blocked by an object, or -1 if none.
 */

int Chunk_cache::get_lowest_blocked
	(
	int lift,			// Look below this lift.
	int tx, int ty			// Square to test.
	)
	{
	return get_lowest_blocked(lift, blocked[ty*c_tiles_per_chunk + tx]);
	}

/*
 *	See if a tile is water or land.
 */

inline void Check_terrain
	(
	Map_chunk *nlist,	// Chunk.
	int tx, int ty,			// Tile within chunk.
	int& terrain			// Sets: bit0 if land, bit1 if water,
					//   bit2 if solid.
	)
	{
	ShapeID flat = nlist->get_flat(tx, ty);
	if (!flat.is_invalid())
		{
		if (flat.get_info().is_water())
			terrain |= 2;
		else if (flat.get_info().is_solid())
			terrain |= 4;
		else
			terrain |= 1;
		}

	}

/*
 *	Is a given square occupied at a given lift?
 *
 *	Output: 1 if so, else 0.
 *		If 0 (tile is free), new_lift contains the new height that
 *		   an actor will be at if he walks onto the tile.
 */

int Chunk_cache::is_blocked
	(
	int height,			// Height (in tiles) of obj. being
					//   tested.
	int lift,			// Given lift.
	int tx, int ty,			// Square to test.
	int& new_lift,			// New lift returned.
	const int move_flags,
	int max_drop,			// Max. drop/rise allowed.
	int max_rise			// Max. rise, or -1 to use old beha-
					//   viour (max_drop if FLY, else 1).
	)
{

	// Ethereal beings always return not blocked
	// and can only move horizontally
	if (move_flags & MOVE_ETHEREAL)
	{
		new_lift = lift;
		return 0;
	}
					// Get bits.
	unsigned long tflags = blocked[ty*c_tiles_per_chunk + tx];
					// Figure max lift allowed.
	if (max_rise == -1)
		max_rise = (move_flags & MOVE_FLY) ? max_drop : 1;
	int max_lift = lift + max_rise;
	if (max_lift > 15)
		max_lift = 15;		// As high as we can go.
	for (new_lift = lift; new_lift <= max_lift; new_lift++)
		{
		if ((tflags & (3 << (2*new_lift))) == 0)
			{		// Not blocked?
			int new_high = get_lowest_blocked(new_lift, tflags);
					// Not blocked above?
			if (new_high == -1 || new_high >= (new_lift + height))
				break;	// Okay.
			}
		}
	if (new_lift > max_lift)	// Spot not found at lift or higher?
		{			// Look downwards.
		new_lift = get_highest_blocked(lift, tflags) + 1;
		if (new_lift >= lift)	// Couldn't drop?
			return 1;
		int new_high = get_lowest_blocked(new_lift, tflags);
		if (new_high != -1 && new_high < new_lift + height)
			return 1;	// Still blocked above.
		}
	if (new_lift <= lift)		// Not going up?  See if falling.
		{
		new_lift =  (move_flags & MOVE_NODROP) ? lift :
				get_highest_blocked(lift, tflags) + 1;
					// Don't allow fall of > max_drop.
		if (lift - new_lift > max_drop)
			{		// Map-editing?  Suspend in air there.
			if (move_flags & MOVE_MAPEDIT)
				new_lift = lift - max_drop;
			else
				return 1;
			}
		int new_high = get_lowest_blocked (new_lift, tflags);
	
		// Make sure that where we want to go is tall enough for us
		if (new_high != -1 && new_high < (new_lift + height)) 
			return 1;
		}
	
	// Found a new place to go, lets test if we can actually move there
	
	// Lift 0 tests
	if (new_lift == 0)
	{
		if (move_flags & MOVE_MAPEDIT)
			return 0;	// Map-editor, so anything is okay.
		int ter = 0;
		Check_terrain (obj_list, tx, ty, ter);
		if (ter & 2)		// Water
		{
			if (move_flags & (MOVE_FLY+MOVE_SWIM))
				return 0;
			else
				return 1;
		}
		else if (ter & 1)	// Land
		{
			if (move_flags & (MOVE_FLY|MOVE_WALK))
				return 0;
			else
				return 1;
		}
		else if (ter & 4)	// Blocked
		{
			if (move_flags & MOVE_FLY)
				return 0;
			else
				return 1;
		}
		else	// Other
			return 0;
	}
	else if (move_flags & (MOVE_FLY|MOVE_WALK))
		return 0;

	return 1;
}

/*
 *	Activate nearby eggs.
 */

void Chunk_cache::activate_eggs
	(
	Game_object *obj,		// Object (actor) that's near.
	Map_chunk *chunk,		// Chunk this is attached to.
	int tx, int ty, int tz,		// Tile (absolute).
	int from_tx, int from_ty,	// Tile walked from.
	unsigned short eggbits,		// Eggs[tile].
	bool now			// Do them immediately.
	)
{
	int i;				// Go through eggs.
	for (i = 0; i < 8*(int)sizeof(eggbits) - 1 && eggbits; 
						i++, eggbits = eggbits >> 1)
	{
		Egg_object *egg;
		if ((eggbits&1) && i < egg_objects.size() &&
		    (egg = egg_objects[i]) &&
		    egg->is_active(obj, tx, ty, tz, from_tx, from_ty))
		{
			egg->activate(obj, now);
			if (chunk->get_cache() != this)
				return;	// A teleport could have deleted us!
		}
	}
	if (eggbits)			// Check 15th bit.
	{				// DON'T use an iterator here, since
					//   the list can change as eggs are
					//   activated, causing a CRASH!
		int sz = egg_objects.size();
		for (  ; i < sz; i++)
		{
			Egg_object *egg = egg_objects[i];
			if (egg && egg->is_active(obj, tx, ty, tz, from_tx, from_ty))
			{
				egg->activate(obj, now);
				if (chunk->get_cache() != this)
					return;	// A teleport could have deleted us!			
			}
		}
	}
}

/*
 *	Find door blocking a given tile.
 */

Game_object *Chunk_cache::find_door
	(
	Tile_coord tile
	)
	{
	for (Game_object_vector::iterator it = doors.begin();
						it != doors.end(); ++it)
		if ((*it)->blocks(tile))
			return *it;	// Found it.
	return 0;
	}

/*
 *	Create list for a given chunk.
 */

Map_chunk::Map_chunk
	(
	int chunkx, int chunky		// Absolute chunk coords.
	) : objects(0), terrain(0), first_nonflat(0), ice_dungeon(0x00),
	    dungeon_levels(0), cache(0), roof(0),
	    dungeon_lights(0), non_dungeon_lights(0),
	    cx(chunkx), cy(chunky), from_below(0), from_right(0),
	    from_below_right(0)
	{
	}

/*
 *	Delete all objects contained within.
 */

Map_chunk::~Map_chunk
	(
	)
	{
	delete cache;
	delete [] dungeon_levels;
	}

/*
 *	Set terrain.  Even if the terrain is the same, it still reloads the
 *	'flat' objects.
 */

void Map_chunk::set_terrain
	(
	Chunk_terrain *ter
	)
	{
	if (terrain)
		{
		terrain->remove_client();
					// Remove objs. from terrain.
		Game_object_vector removes;
		{			// Separate scope for Object_iterator.
		Object_iterator it(get_objects());
		Game_object *each;
		while ((each = it.get_next()) != 0)
					// Kind of nasty, I know:
			if (each->as_terrain())
				removes.push_back(each);
		}
		for (Game_object_vector::const_iterator it=removes.begin(); 
						it!=removes.end(); ++it)
			(*it)->remove_this();
		}
	terrain = ter;
	terrain->add_client();
					// Get RLE objects in chunk.
	for (int tiley = 0; tiley < c_tiles_per_chunk; tiley++)
		for (int tilex = 0; tilex < c_tiles_per_chunk; tilex++)
			{
			ShapeID id = ter->get_flat(tilex, tiley);
			Shape_frame *shape = id.get_shape();
			if (shape && shape->is_rle())
				{
				int shapenum = id.get_shapenum(),
				    framenum = id.get_framenum();
				Shape_info& info = id.get_info();
				Game_object *obj = info.is_animated() ?
					new Animated_object(shapenum,
					    	framenum, tilex, tiley)
					: new Terrain_game_object(shapenum,
					    	framenum, tilex, tiley);
				add(obj);
				}
			}
	}

/*
 *	Add rendering dependencies for a new object.
 */

void Map_chunk::add_dependencies
	(
	Game_object *newobj,		// Object to add.
	Ordering_info& newinfo		// Info. for new object's ordering.
	)
	{
	Game_object *obj;		// Figure dependencies.
	Nonflat_object_iterator next(this);
	while ((obj = next.get_next()) != 0)
		{
		//cout << "Here " << __LINE__ << " " << obj << endl;
		/* Compare returns -1 if lt, 0 if dont_care, 1 if gt. */
		int newcmp = Game_object::compare(newinfo, obj);
		int cmp = newcmp == -1 ? 1 : newcmp == 1 ? 0 : -1;
		if (!cmp)		// Bigger than this object?
			{
			newobj->dependencies.put(obj);
			obj->dependors.put(newobj);
			}
		else if (cmp == 1)	// Smaller than?
			{
			obj->dependencies.put(newobj);
			newobj->dependors.put(obj);
			}
		}
	}

/*
 *	Add rendering dependencies for a new object to another chunk.
 *	NOTE:  This is static.
 *
 *	Output:	->chunk that was checked.
 */

inline Map_chunk *Map_chunk::add_outside_dependencies
	(
	int cx, int cy,			// Chunk to check.
	Game_object *newobj,		// Object to add.
	Ordering_info& newinfo		// Info. for new object's ordering.
	)
	{
	Map_chunk *chunk = gmap->get_chunk(cx, cy);
	chunk->add_dependencies(newobj, newinfo);
	return chunk;
	}

/*
 *	Add a game object to a chunk's list.
 *
 *	Newobj's cx and cy fields are set to this chunk.
 */

void Map_chunk::add
	(
	Game_object *newobj		// Object to add.
	)
	{
	newobj->cx = get_cx();		// Set object's chunk.
	newobj->cy = get_cy();
	Ordering_info ord(gwin, newobj);
					// Put past flats.
	if (first_nonflat)
		objects.insert_before(newobj, first_nonflat);
	else
		objects.append(newobj);
					// Not flat?
	if (newobj->get_lift() || ord.info.get_3d_height())
		{			// Deal with dependencies.
		int ty = newobj->get_ty();
					// First this chunk.
		add_dependencies(newobj, ord);
		if (from_below)		// Overlaps from below?
			add_outside_dependencies(cx, INCR_CHUNK(cy), 
							newobj, ord);
		if (from_right)		// Overlaps from right?
			add_outside_dependencies(INCR_CHUNK(cx), cy, 
								newobj, ord);
		if (from_below_right)
			add_outside_dependencies(INCR_CHUNK(cx), 
					INCR_CHUNK(cy), newobj, ord);
					// See if newobj extends outside.
	/* Let's try boundary. YES.  This helps with statues through roofs!*/
		bool ext_left = (newobj->get_tx() - ord.xs) < 0 && cx > 0;
		bool ext_above = (newobj->get_ty() - ord.ys) < 0 && cy > 0;
		if (ext_left)
			{
			add_outside_dependencies(DECR_CHUNK(cx), cy, 
						newobj, ord)->from_right++;
			if (ext_above)
				add_outside_dependencies(DECR_CHUNK(cx), 
							 DECR_CHUNK(cy),
					newobj, ord)->from_below_right++;
			}
		if (ext_above)
			add_outside_dependencies(cx, DECR_CHUNK(cy),
					newobj, ord)->from_below++;
		first_nonflat = newobj;	// Inserted before old first_nonflat.
		}
	if (cache)			// Add to cache.
		cache->update_object(this, newobj, 1);
	if (ord.info.is_light_source())	// Count light sources.
		if (dungeon_levels && is_dungeon(newobj->get_tx(),
							newobj->get_ty()))
			dungeon_lights++;
		else
			non_dungeon_lights++;
	if (newobj->get_lift() >= 5)	// Looks like a roof?
		{
		if (ord.info.get_shape_class() == Shape_info::building)
			roof = 1;
		}
	}

/*
 *	Add an egg.
 */

void Map_chunk::add_egg
	(
	Egg_object *egg
	)
	{
	add(egg);			// Add it normally.
	egg->set_area();
// Messed up Moonshade after Banes if (cache)		// Add to cache.
	need_cache()->update_egg(this, egg, 1);
	}

/*
 *	Remove an egg.
 */

void Map_chunk::remove_egg
	(
	Egg_object *egg
	)
	{
	remove(egg);			// Remove it normally.
	if (cache)			// Remove from cache.
		cache->update_egg(this, egg, 0);
	}

/*
 *	Remove a game object from this list.  The object's cx and cy fields
 *	are set to invalid #'s (255,255).
 */

void Map_chunk::remove
	(
	Game_object *remove
	)
	{
	if (cache)			// Remove from cache.
		cache->update_object(this, remove, 0);
	remove->clear_dependencies();	// Remove all dependencies.
	Game_map *gmap = gwin->get_map();
	Shape_info& info = remove->get_info();
					// See if it extends outside.
	int frame = remove->get_framenum(), tx = remove->get_tx(),
					ty = remove->get_ty();
	/* Let's try boundary. YES.  Helps with statues through roofs. */
	bool ext_left = (tx - info.get_3d_xtiles(frame)) < 0 && cx > 0;
	bool ext_above = (ty - info.get_3d_ytiles(frame)) < 0 && cy > 0;
	if (ext_left)
		{
		gmap->get_chunk(cx - 1, cy)->from_below_right--;
		if (ext_above)
			gmap->get_chunk(cx - 1, cy - 1)->from_below_right--;
		}
	if (ext_above)
		gmap->get_chunk(cx, cy - 1)->from_below--;
	if (info.is_light_source())	// Count light sources.
		if (dungeon_levels && is_dungeon(tx, ty))
			dungeon_lights--;
		else
			non_dungeon_lights--;
	if (remove == first_nonflat)	// First nonflat?
		{			// Update.
		first_nonflat = remove->get_next();
		if (first_nonflat == objects.get_first())
			first_nonflat = 0;
		}
	objects.remove(remove);		// Remove from list.
	remove->set_invalid();		// No longer part of world.
	}

/*
 *	Is a given rectangle of tiles blocked at a given lift?
 *
 *	Output: 1 if so, else 0.
 *		If 0 (tile is free), new_lift contains the new height that
 *		   an actor will be at if he walks onto the tile.
 */

int Map_chunk::is_blocked
	(
	int height,			// Height (along lift) to check.
	int lift,			// Starting lift.
	int startx, int starty,		// Starting tile coords.
	int xtiles, int ytiles,		// Width, height in tiles.
	int& new_lift,			// New lift returned.
	const int move_flags,
	int max_drop,			// Max. drop/rise allowed.
	int max_rise			// Max. rise, or -1 to use old beha-
					//   viour (max_drop if FLY, else 1).
	)
	{
	Game_map *gmap = gwin->get_map();
	int tx, ty;
	new_lift = 0;
	startx %= c_num_tiles;		// Watch for wrapping.
	starty %= c_num_tiles;
	int stopy = (starty + ytiles)%c_num_tiles, 
	    stopx = (startx + xtiles)%c_num_tiles;
	for (ty = starty; ty != stopy; ty = INCR_TILE(ty))
		{			// Get y chunk, tile-in-chunk.
		int cy = ty/c_tiles_per_chunk, rty = ty%c_tiles_per_chunk;
		for (tx = startx; tx != stopx; tx = INCR_TILE(tx))
			{
			int this_lift;
			Map_chunk *olist = gmap->get_chunk(
					tx/c_tiles_per_chunk, cy);
			olist->setup_cache();
			if (olist->is_blocked(height, lift, 
				tx%c_tiles_per_chunk,
				rty, this_lift, move_flags, max_drop,max_rise))
				return (1);
					// Take highest one.
			new_lift = this_lift > new_lift ?
					this_lift : new_lift;
			}
		}
	return (0);
	}

/*
 *	Check an absolute tile position.
 *
 *	Output:	1 if blocked, 0 otherwise.
 *		Tile.tz may be updated for stepping onto square.
 */

int Map_chunk::is_blocked
	(
	Tile_coord& tile,
	int height,			// Height in tiles to check.
	const int move_flags,
	int max_drop,			// Max. drop/rise allowed.
	int max_rise			// Max. rise, or -1 to use old beha-
					//   viour (max_drop if FLY, else 1).
	)
	{
					// Get chunk tile is in.
	Game_map *gmap = gwin->get_map();
	Map_chunk *chunk = gmap->get_chunk_safely(
			tile.tx/c_tiles_per_chunk, tile.ty/c_tiles_per_chunk);
	if (!chunk)			// Outside the world?
		return 0;		// Then it's not blocked.
	chunk->setup_cache();		// Be sure cache is present.
	int new_lift;			// Check it within chunk.
	if (chunk->is_blocked(height, tile.tz, tile.tx%c_tiles_per_chunk,
		    tile.ty%c_tiles_per_chunk, new_lift, move_flags, max_drop,
								max_rise))
		return (1);
	tile.tz = new_lift;
	return (0);
	}

/*
 *	This one is used to see if an object of dims. possibly > 1X1 can
 *	step onto an adjacent square.
 */

int Map_chunk::is_blocked
	(
					// Object dims:
	int xtiles, int ytiles, int ztiles,
	Tile_coord from,		// Stepping from here.
	Tile_coord& to,			// Stepping to here.  Tz updated.
	const int move_flags,
	int max_drop,			// Max drop/rise allowed.
	int max_rise			// Max. rise, or -1 to use old beha-
					//   viour (max_drop if FLY, else 1).
	)
	{
	int vertx0, vertx1;		// Get x-coords. of vert. block
					//   to right/left.
	int horizx0, horizx1;		// Get x-coords of horiz. block
					//   above/below.
	int verty0, verty1;		// Get y-coords of horiz. block
					//   above/below.
	int horizy0, horizy1;		// Get y-coords of vert. block
					//   to right/left.
					// !Watch for wrapping.
	horizx0 = (to.tx + 1 - xtiles + c_num_tiles)%c_num_tiles;
	horizx1 = INCR_TILE(to.tx);
	if (Tile_coord::gte(to.tx, from.tx))		// Moving right?
		{			// Start to right of hot spot.
		vertx0 = INCR_TILE(from.tx);
		vertx1 = INCR_TILE(to.tx);	// Stop past dest.
		}
	else				// Moving left?
		{
		vertx0 = (to.tx + 1 - xtiles + c_num_tiles)%c_num_tiles;
		vertx1 = (from.tx + 1 - xtiles + c_num_tiles)%c_num_tiles;
		}
	verty0 = (to.ty + 1 - ytiles + c_num_tiles)%c_num_tiles;
	verty1 = INCR_TILE(to.ty);
	if (Tile_coord::gte(to.ty, from.ty))		// Moving down?
		{			// Start below hot spot.
		horizy0 = INCR_TILE(from.ty);	
		horizy1 = INCR_TILE(to.ty);	// End past dest.
		if (to.ty != from.ty)	// Includes bottom of vert. area.
			verty1 = DECR_TILE(verty1);
		}
	else				// Moving up?
		{
		horizy0 = (to.ty + 1 - ytiles + c_num_tiles)%c_num_tiles;
		horizy1 = (from.ty + 1 - ytiles + c_num_tiles)%c_num_tiles;
					// Includes top of vert. area.
		verty0 = INCR_TILE(verty0);
		}
	int x, y;			// Go through horiz. part.
	int new_lift = from.tz;
	int new_lift0 = -1;		// All lift changes must be same.
#ifdef DEBUG
	assert(Tile_coord::gte(horizy1, horizy0));
	assert(Tile_coord::gte(horizx1, horizx0));
	assert(Tile_coord::gte(verty1, verty0));
	assert(Tile_coord::gte(vertx1, vertx0));
#endif
	for (y = horizy0; y != horizy1; y = INCR_TILE(y))
		{			// Get y chunk, tile-in-chunk.
		int cy = y/c_tiles_per_chunk, rty = y%c_tiles_per_chunk;
		for (x = horizx0; x != horizx1; x = INCR_TILE(x))
			{
			Map_chunk *olist = gmap->get_chunk(
					x/c_tiles_per_chunk, cy);
			olist->setup_cache();
			int rtx = x%c_tiles_per_chunk;
			if (olist->is_blocked(ztiles, from.tz, rtx, rty,
				new_lift, move_flags, max_drop, max_rise))
				return 1;
			if (new_lift != from.tz)
				if (new_lift0 == -1)
					new_lift0 = new_lift;
				else if (new_lift != new_lift0)
					return (1);
			}
		}
					// Do vert. block.
	for (x = vertx0; x != vertx1; x = INCR_TILE(x))
		{			// Get x chunk, tile-in-chunk.
		int cx = x/c_tiles_per_chunk, rtx = x%c_tiles_per_chunk;
		for (y = verty0; y != verty1; y = INCR_TILE(y))
			{
			Map_chunk *olist = gmap->get_chunk(
					cx, y/c_tiles_per_chunk);
			olist->setup_cache();
			int rty = y%c_tiles_per_chunk;
			if (olist->is_blocked(ztiles, from.tz, rtx, rty,
				new_lift, move_flags, max_drop, max_rise))
				return 1;
			if (new_lift != from.tz)
				if (new_lift0 == -1)
					new_lift0 = new_lift;
				else if (new_lift != new_lift0)
					return (1);
			}
		}
	to.tz = new_lift;
	return (0);			// All clear.
	}

/*
 *	Get the list of tiles in a square perimeter around a given tile.
 *
 *	Output:	List (8*dist) of tiles, starting in Northwest corner and going
 *		   clockwise.  List is on heap.
 */

static Tile_coord *Get_square
	(
	Tile_coord& pos,		// Center of square.
	int dist			// Distance to perimeter (>0)
	)
	{
	Tile_coord *square = new Tile_coord[8*dist];
					// Upper left corner:
	square[0] = Tile_coord(DECR_TILE(pos.tx, dist), 
					DECR_TILE(pos.ty, dist), pos.tz);
	int i;				// Start with top row.
	int len = 2*dist + 1;
	int out = 1;
	for (i = 1; i < len; i++, out++)
		square[out] = Tile_coord(INCR_TILE(square[out - 1].tx),
			square[out - 1].ty, pos.tz);
					// Down right side.
	for (i = 1; i < len; i++, out++)
		square[out] = Tile_coord(square[out - 1].tx,
			INCR_TILE(square[out - 1].ty), pos.tz);
					// Bottom, going back to left.
	for (i = 1; i < len; i++, out++)
		square[out] = Tile_coord(DECR_TILE(square[out - 1].tx),
			square[out - 1].ty, pos.tz);
					// Left side, going up.
	for (i = 1; i < len - 1; i++, out++)
		square[out] = Tile_coord(square[out - 1].tx,
			DECR_TILE(square[out - 1].ty), pos.tz);
	return square;
	}

/*
 *	Check a spot against the 'where' paramater to find_spot.
 *
 *	Output:	true if it passes.
 */

inline bool Check_spot
	(
	Map_chunk::Find_spot_where where,
	int tx, int ty, int tz
	)
	{
	Game_map *gmap = Game_window::get_instance()->get_map();
	int cx = tx/c_tiles_per_chunk, cy = ty/c_tiles_per_chunk;
	Map_chunk *chunk = gmap->get_chunk_safely(cx, cy);
	return (where == Map_chunk::inside) == 
				(chunk->is_roof(tx % c_tiles_per_chunk, 
					ty % c_tiles_per_chunk, tz) < 31);
	}

/*
 *	Find a free area for an object of a given shape, looking outwards.
 *
 *	Output:	Tile if successful, else (-1, -1, -1).
 */

Tile_coord Map_chunk::find_spot
	(
	Tile_coord pos,			// Starting point.
	int dist,			// Distance to look outwards.  (0 means
					//   only check 'pos'.
	int shapenum,			// Shape, frame to find spot for.
	int framenum,
	int max_drop,			// Allow to drop by this much.
	int dir,			// Preferred direction (0-7), or -1 for
					//   random.
	Find_spot_where where		// Inside/outside.
	)
	{
	Shape_info& info = ShapeID::get_info(shapenum);
	int xs = info.get_3d_xtiles(framenum);
	int ys = info.get_3d_ytiles(framenum);
	int zs = info.get_3d_height();
					// The 'MOVE_FLY' flag really means
					//   we can look upwards by max_drop.
	const int mflags = MOVE_WALK|MOVE_FLY;
	int new_lift;
					// Start with original position.
	if (!Map_chunk::is_blocked(zs, pos.tz, pos.tx - xs + 1,
		pos.ty - ys + 1, xs, ys, new_lift, mflags, max_drop))
		return Tile_coord(pos.tx, pos.ty, new_lift);
	if (dir < 0)
		dir = rand()%8;		// Choose dir. randomly.
	dir = (dir + 1)%8;		// Make NW the 0 point.
	for (int d = 1; d <= dist; d++)	// Look outwards.
		{
		int square_cnt = 8*d	;// # tiles in square's perim.
					// Get square (starting in NW).
		Tile_coord *square = Get_square(pos, d);
		int index = dir*d;	// Get index of preferred spot.
					// Get start of preferred range.
		index = (index - d/2 + square_cnt)%square_cnt;
		for (int cnt = square_cnt; cnt; cnt--, index++)
			{
			Tile_coord& p = square[index%square_cnt];
			if (!Map_chunk::is_blocked(zs, p.tz, p.tx - xs + 1,
				p.ty - ys + 1, xs, ys, new_lift, mflags,
								max_drop) &&
			    (where == anywhere || 
				  Check_spot(where, p.tx, p.ty, new_lift)))
				{	// Use tile before deleting.
				Tile_coord ret(p.tx, p.ty, new_lift);
				delete [] square;
				return ret;
				}
			}
		delete [] square;
		}
	return Tile_coord(-1, -1, -1);
	}

/*
 *	Find a free area for an object (usually an NPC) that we want to
 *	approach a given position.
 *
 *	Output:	Tile if successful, else (-1, -1, -1).
 */

Tile_coord Map_chunk::find_spot
	(
	Tile_coord pos,			// Starting point.
	int dist,			// Distance to look outwards.  (0 means
					//   only check 'pos'.
	Game_object *obj,		// Object that we want to move.
	int max_drop,			// Allow to drop by this much.
	Find_spot_where where		// Inside/outside.
	)
	{
	Tile_coord t2 = obj->get_tile();
					// Get direction from pos. to object.
	int dir = (int) Get_direction(pos.ty - t2.ty, t2.tx - pos.tx);
	return find_spot(pos, dist, obj->get_shapenum(), obj->get_framenum(),
			max_drop, dir, where);
	}

/*
 *	Find all desired objects within a given rectangle.
 *
 *	Output:	# found, appended to vec.
 */

int Map_chunk::find_in_area
	(
	Game_object_vector& vec,	// Returned here.
	Rectangle area,			// Area to search.
	int shapenum,
	int framenum
	)
	{
	int savesize = vec.size();
					// Go through interesected chunks.
	Chunk_intersect_iterator next_chunk(area);
	Rectangle tiles;		// (Tiles within intersected chunk).
	int eachcx, eachcy;
	Game_map *gmap = gwin->get_map();
	while (next_chunk.get_next(tiles, eachcx, eachcy))
		{
		Map_chunk *chunk = gmap->get_chunk_safely(eachcx, eachcy);
		if (!chunk)
			continue;
		Object_iterator next(chunk->objects);
		Game_object *each;
		while ((each = next.get_next()) != 0)
			if (each->get_shapenum() == shapenum &&
			    each->get_framenum() == framenum &&
			    tiles.has_point(each->get_tx(), each->get_ty()))
				vec.append(each);
		}
	return vec.size() - savesize;
	}



/*
 *	Test all nearby eggs when you've teleported in.
 */

void Map_chunk::try_all_eggs
	(
	Game_object *obj,		// Object (actor) that's near.
	int tx, int ty, int tz,		// Tile (absolute).
	int from_tx, int from_ty	// Tile walked from.
	)
	{
	static int norecurse = 0;	// NO recursion here.
	if (norecurse)
		return;
	norecurse++;
	Game_map *gmap = gwin->get_map();
	Tile_coord pos = obj->get_tile();
	const int dist = 32;		// See if this works okay.
	Rectangle area(pos.tx - dist, pos.ty - dist, 2*dist, 2*dist);
					// Go through interesected chunks.
	Chunk_intersect_iterator next_chunk(area);
	Rectangle tiles;		// (Ignored).
	int eachcx, eachcy;
	Egg_vector eggs(40);		// Get them here first, as activating
					//   an egg could affect chunk's list.
	while (next_chunk.get_next(tiles, eachcx, eachcy))
		{
		Map_chunk *chunk = gmap->get_chunk_safely(eachcx, eachcy);
		if (!chunk)
			continue;
		chunk->setup_cache();	// I think we should do this.
		Object_iterator next(chunk->objects);
		Game_object *each;
		while ((each = next.get_next()) != 0)
			if (each->is_egg())
				{
				Egg_object *egg = (Egg_object *) each;
					// Music eggs are causing problems.
				if (egg->get_type() != Egg_object::jukebox &&
					// And don't teleport a 2nd time.
				    egg->get_type() != Egg_object::teleport &&
			    	    egg->is_active(obj,
						tx, ty, tz, from_tx, from_ty))
					eggs.push_back(egg);
				}
		}
	for (Egg_vector::const_iterator it = eggs.begin(); it != eggs.end();
									++it)
		(*it)->activate(obj);
	norecurse--;
	}

/*
 *	Add a rectangle of dungeon tiles (but only if higher!).
 */

void Map_chunk::add_dungeon_levels
	(
	Rectangle& tiles, unsigned int lift
	)
{
	if (!dungeon_levels)
	{			// First one found.
		dungeon_levels = new unsigned char[256/2];
		memset(dungeon_levels, 0, 256/2);
	}
	int endy = tiles.y + tiles.h, endx = tiles.x + tiles.w;
	for (int ty = tiles.y; ty < endy; ty++)
	{
		for (int tx = tiles.x; tx < endx; tx++)
		{
			int tnum = (ty*c_tiles_per_chunk + tx)/2;
			if (GAME_SI)	// SI has roofs at random levels!!
				lift = 5;
			if (tx % 2)
			{
				dungeon_levels[tnum] &= 0x0F;
				dungeon_levels[tnum] |= lift << 4;
			}
			else
			{
				dungeon_levels[tnum] &= 0xF0;
				dungeon_levels[tnum] |= lift;
			}
		}
	}
}

/*
 *	Set up the dungeon levels (after IFIX objects read).
 */

void Map_chunk::setup_dungeon_levels
	(
	)
{
	Game_map *gmap = gwin->get_map();

	Object_iterator next(objects);
	Game_object *each;
	while ((each = next.get_next()) != 0)
	{
		int shnum = each->get_shapenum();
					// Test for mountain-tops.
		if (shnum == 983 || shnum == 969 || shnum == 183 ||
		    shnum == 182 || shnum == 180 || shnum == 324 || 
		    ((shnum == 941 || shnum == 394) && 
					Game::get_game_type() == SERPENT_ISLE))
		{
			// SI shape 941, frame 0 => do whole chunk (I think).
			Rectangle area = 
				(shnum == 941 && each->get_framenum() == 0)
				? Rectangle(cx*c_tiles_per_chunk,
					    cy*c_tiles_per_chunk,
					    c_tiles_per_chunk,
					    c_tiles_per_chunk)
				: each->get_footprint();

					// Go through interesected chunks.
			Chunk_intersect_iterator next_chunk(area);
			Rectangle tiles;// Rel. tiles.
			int cx, cy;
			while (next_chunk.get_next(tiles, cx, cy))
				gmap->get_chunk(cx, cy)->add_dungeon_levels(
						tiles, each->get_lift());
		}			// Ice Dungeon Pieces in SI
		else if (Game::get_game_type() == SERPENT_ISLE && (
			shnum == 436 || shnum == 437 || shnum == 444 ||
			shnum == 448  || shnum == 466 || shnum == 477))
		{
			// HACK ALERT! This gets 320x200 to work, but it is a hack
			// This is not exactly accurate.
			ice_dungeon |= 1 << ( (each->get_tx()>>3) + 2*(each->get_ty()>>3) );

			Rectangle area = each->get_footprint();

					// Go through interesected chunks.
			Chunk_intersect_iterator next_chunk(area);
			Rectangle tiles;// Rel. tiles.
			int cx, cy;
			while (next_chunk.get_next(tiles, cx, cy))
				gmap->get_chunk(cx, cy)->add_dungeon_levels(
								tiles, each->get_lift());
		}
	}
	if (dungeon_levels)		// Recount lights.
		{
		dungeon_lights = non_dungeon_lights = 0;
		next.reset();
		while ((each = next.get_next()) != 0)
			if (each->get_info().is_light_source())
				if (is_dungeon(each->get_tx(), each->get_ty()))
					dungeon_lights++;
				else
					non_dungeon_lights++;
		}
}

/*
 *	Recursively apply gravity over a given rectangle that is known to be
 *	unblocked below a given lift.
 */

void Map_chunk::gravity
	(
	Rectangle area,			// Unblocked tiles (in abs. coords).
	int lift			// Lift where tiles are free.
	)
	{
	Game_object_vector dropped(20);	// Gets list of objs. that dropped.
					// Go through interesected chunks.
	Chunk_intersect_iterator next_chunk(area);
	Rectangle tiles;		// Rel. tiles.  Not used.
	int cx, cy, new_lift;
	while (next_chunk.get_next(tiles, cx, cy))
		{
		Map_chunk *chunk = gmap->get_chunk(cx, cy);
		Object_iterator objs(chunk->objects);
		Game_object *obj;
		while ((obj = objs.get_next()) != 0)
			{		// We DO want NPC's to fall.
			if (!obj->is_dragable() && 
						!obj->get_info().is_npc())
				continue;
			Tile_coord t = obj->get_tile();
					// Get footprint.
			Rectangle foot = obj->get_footprint();
					// Above area?
			if (t.tz >= lift && foot.intersects(area) &&
					// Unblocked below itself?
			    !is_blocked(1, t.tz - 1, foot.x, foot.y,
					foot.w, foot.h, new_lift,
						MOVE_ALL_TERRAIN, 0) &&
			    new_lift < t.tz)
				dropped.push_back(obj);
			}
		}
	Game_object_vector::const_iterator it;
					// Drop each one found.
	for (it = dropped.begin(); it != dropped.end(); ++it)
		{
		Game_object *obj = *it;
		Tile_coord t = obj->get_tile();
					// Get footprint.
		Rectangle foot = obj->get_footprint();
					// Let drop as far as possible.
		if (!is_blocked(1, t.tz - 1, foot.x, foot.y,
			foot.w, foot.h, new_lift, MOVE_ALL_TERRAIN, 100) &&
			    				new_lift < t.tz)
			{		// Drop & recurse.
			obj->move(t.tx, t.ty, new_lift);
			gravity(foot, obj->get_lift() +
					obj->get_info().get_3d_height());
			}
		}
#if 0
	for (it = dropped.begin(); it != dropped.end(); ++it)
		{			// Recurse on each one.
		Game_object *obj = *it;
					// Get footprint.
		Rectangle foot = obj->get_footprint();
		gravity(foot, obj->get_lift() +
					obj->get_info().get_3d_height());
		}
#endif
	}

/*
 *  Finds if there is a 'roof' above lift in tile (tx, ty)
 *  of the chunk. Point is taken 4 above lift
 *
 *  Roof can be any object, not just a literal roof
 *
 *  Output: height of the roof.
 *  A return of 31 means no roof
 *
 */
int Map_chunk::is_roof(int tx, int ty, int lift)
{
#if 1		/* Might be lying on bed at lift==2. */
	int height = get_lowest_blocked (lift+4, tx, ty);
#else		/* But this is even worse! */
	int height = get_lowest_blocked (lift+2, tx, ty);
#endif
	if (height == -1) return 31;
	return height;
}

void Map_chunk::kill_cache()
{
	// Get rid of terrain
	if (terrain) terrain->remove_client();
	terrain = 0;

	// Now remove the cachce
	delete cache;
	cache = 0;

	// Delete dungeon bits
	delete [] dungeon_levels;
	dungeon_levels = 0;
}

int Map_chunk::get_obj_actors(Game_object_vector &removes, Actor_vector &actors)
{
	int buf_size = 0;
	bool failed = false;

	// Separate scope for Object_iterator.
	Object_iterator it(get_objects());
	Game_object *each;
	while ((each = it.get_next()) != 0)
	{
		Actor *actor = each->as_actor();

		// Normal objects and monsters
		if (actor == 0 || (each->is_monster() && each->get_flag(Obj_flags::is_temporary))) {
			removes.push_back(each);
			int ireg_size = each->get_ireg_size();

			if (ireg_size < 0) failed = true;
			else buf_size += ireg_size;
		}
			// Actors/NPCs here
		else {
			actors.push_back(actor);
		}
	}

	return failed?-1:buf_size;
}