/*
 *	Paths.cc - Various pathfinding clients.
 *
 *  Copyright (C) 2000-2001  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 "paths.h"
#include "Astar.h"
#include "Zombie.h"
#include "gamewin.h"
#include "gamemap.h"
#include "actors.h"

/*
 *	Create for given NPC.
 */

Actor_pathfinder_client::Actor_pathfinder_client
	(
	Actor *n,
	int d
	) : dist(d), npc(n)
	{
					// +++++Shouldn't need this anymore?
	set_move_flags(npc->get_type_flags());
	}

/*
 *	Figure when to give up.
 */

int Actor_pathfinder_client::get_max_cost
	(
	int cost_to_goal		// From estimate_cost().
	)
	{
	int max_cost = 3*cost_to_goal;
	Game_window *gwin = Game_window::get_instance();
					// Do at least 3 screens width.
	int min_max_cost = (gwin->get_width()/c_tilesize)*2*3;
	return max_cost > min_max_cost ? max_cost : min_max_cost;
	}

/*
 *	Figure cost going from one tile to an adjacent tile (for pathfinding).
 *
 *	Output:	Cost, or -1 if blocked.
 *		The 'tz' field in tile may be modified.
 */

int Actor_pathfinder_client::get_step_cost
	(
	Tile_coord from,
	Tile_coord& to			// The tile we're going to.  The 'tz'
					//   field may be modified.
	)
	{
	Game_window *gwin = Game_window::get_instance();
	int cx = to.tx/c_tiles_per_chunk, cy = to.ty/c_tiles_per_chunk;
	Map_chunk *olist = gwin->get_map()->get_chunk(cx, cy);
	int tx = to.tx%c_tiles_per_chunk;	// Get tile within chunk.
	int ty = to.ty%c_tiles_per_chunk;
	int cost = 1;
	olist->setup_cache();		// Make sure cache is valid.
	int water, poison;		// Get tile info.
	Actor::get_tile_info(0, gwin, olist, tx, ty, water, poison);
	int old_lift = to.tz;		// Might climb/descend.
	if (npc->is_blocked(to, &from))
		{			// Blocked, but check for a door.
		Game_object *block = Game_object::find_door(to);
		if (!block)
			return -1;
		if (!block->is_closed_door() ||
					// Can't get past locked doors.
		    block->get_framenum()%4 >= 2)
			return -1;
					// Can't be either end of door.
		Rectangle foot = block->get_footprint();
		if (foot.h == 1 && (to.tx == foot.x || to.tx == foot.x +
							foot.w - 1))
			return -1;
		else if (foot.w == 1 && (to.ty == foot.y || to.ty == foot.y + 
							foot.h - 1))
			return -1;
		if (foot.has_point(from.tx, from.ty))
			return -1;	// Don't walk within doorway.
		cost++;			// But try to avoid them.
		}
	if (old_lift != to.tz)
		cost++;
					// On the diagonal?
	if (from.tx != to.tx || from.ty != to.ty)
		cost *= 3;		// Make it 50% more expensive.
	else
		cost *= 2;
	if (poison && to.tz == 0)
		cost *= 2;		// And avoid poison if possible.
					// Get 'flat' shapenum.
	ShapeID flat = olist->get_flat(tx, ty);
	int shapenum = flat.get_shapenum();
	if (shapenum == 24)		// Cobblestone path in BlackGate?
		{
		int framenum = flat.get_framenum();
		if (framenum <= 1)
			cost--;
		}
	return (cost);
	}

/*
 *	Estimate cost from one point to another.
 */

int Actor_pathfinder_client::estimate_cost
	(
	Tile_coord& from,
	Tile_coord& to
	)
	{
	int dx = to.tx - from.tx;
	if (dx < -c_num_tiles/2)	// Wrap around the world.
		dx += c_num_tiles;
	else if (dx < 0)
		dx = -dx;
	int dy = to.ty - from.ty;
	if (dy < -c_num_tiles/2)
		dy += c_num_tiles;
	else if (dy < 0)
		dy = -dy;
	int larger, smaller;		// Start with larger.
	if (dy <= dx)
		{
		larger = dx;
		smaller = dy;
		}
	else
		{
		larger = dy;
		smaller = dx;
		}
	return (2*larger + smaller);	// Straight = 2, diag = 3.
	}

/*
 *	Is tile at goal?
 */

int Actor_pathfinder_client::at_goal
	(
	Tile_coord& tile,
	Tile_coord& goal
	)
	{
	return tile.distance(goal) <= dist &&
		(goal.tz == -1 || tile.tz == goal.tz);
	}

/*
 *	Estimate cost from one point to another.
 */

int Onecoord_pathfinder_client::estimate_cost
	(
	Tile_coord& from,
	Tile_coord& to			// Should be the goal.
	)
	{
	if (to.tx == -1)		// Just care about Y?
		{			// Cost = 2/tile.
		int dy = to.ty - from.ty;
		if (dy < -c_num_tiles/2)
			dy += c_num_tiles;
		else if (dy < 0)
			dy = -dy;
		return (2*dy);
		}
	else if (to.ty == -1)
		{
		int dx = to.tx - from.tx;
		if (dx < -c_num_tiles/2)
			dx += c_num_tiles;
		else if (dx < 0)
			dx = -dx;
		return (2*dx);
		}
	else				// Shouldn't get here.
		return Actor_pathfinder_client::estimate_cost(from, to);
	}

/*
 *	Is tile at goal?
 */

int Onecoord_pathfinder_client::at_goal
	(
	Tile_coord& tile,
	Tile_coord& goal
	)
	{
	return ((goal.tx == -1 || tile.tx == goal.tx) && 
		(goal.ty == -1 || tile.ty == goal.ty) &&
		(goal.tz == -1 || tile.tz == goal.tz));
	}

/*
 *	Client to get offscreen.
 */

Offscreen_pathfinder_client::Offscreen_pathfinder_client
	(
	Actor *n
	) : Actor_pathfinder_client(n), screen(
	      Game_window::get_instance()->get_win_tile_rect().enlarge(3)),
	    best(-1, -1, -1)
	{
	}

/*
 *	Client to get offscreen.
 */

Offscreen_pathfinder_client::Offscreen_pathfinder_client
	(
	Actor *n,
	Tile_coord b			// Best offscreen pt. to aim for.
	) : Actor_pathfinder_client(n), screen(
	      Game_window::get_instance()->get_win_tile_rect().enlarge(3)),
	    best(b)
	{
	if (best.tx != -1)		// Scale (roughly) to edge of screen.
		{
		Rectangle scr = 
			Game_window::get_instance()->get_win_tile_rect();
					// Get center.
		int cx = scr.x + scr.w/2, cy = scr.y + scr.h/2;
					// More than 4 screens away?
		if (best.distance(Tile_coord(cx, cy, 0)) > 4*scr.w)
			{
			best.tx = best.ty = -1;
			return;
			}
		if (best.tx > cx + scr.w)
					// Too far to right of screen.
			best.tx = scr.x + scr.w + 1;
		else if (best.tx < cx - scr.w)
			best.tx = scr.x - 1;
		if (best.ty > cy + scr.h)
			best.ty = scr.y + scr.h + 1;
		else if (best.ty < cy - scr.h)
			best.ty = scr.y - 1;
					// Give up if it doesn't look right.
		if (best.distance(Tile_coord(cx, cy, 0)) > scr.w)
			best.tx = best.ty = -1;
		}
	}

/*
 *	Figure cost going from one tile to an adjacent tile (for pathfinding).
 *
 *	Output:	Cost, or -1 if blocked.
 *		The 'tz' field in tile may be modified.
 */

int Offscreen_pathfinder_client::get_step_cost
	(
	Tile_coord from,
	Tile_coord& to			// The tile we're going to.  The 'tz'
					//   field may be modified.
	)
	{
	int cost = Actor_pathfinder_client::get_step_cost(from, to);
	if (cost == -1)
		return cost;
	if (best.tx != -1)		// Penalize for moving away from best.
		{
		if ((to.tx - from.tx)*(best.tx - from.tx) < 0)
			cost++;
		if ((to.ty - from.ty)*(best.ty - from.ty) < 0)
			cost++;
		}
	return cost;
	}

/*
 *	Estimate cost from one point to another.
 */

int Offscreen_pathfinder_client::estimate_cost
	(
	Tile_coord& from,
	Tile_coord& to			// Should be the goal.
	)
	{
	if (best.tx != -1)		// Off-screen goal?
		return Actor_pathfinder_client::estimate_cost(from, best);
//++++++World-wrapping here????
	int dx = from.tx - screen.x;	// Figure shortest dist.
	int dx1 = screen.x + screen.w - from.tx;
	if (dx1 < dx)
		dx = dx1;
	int dy = from.ty - screen.y;
	int dy1 = screen.y + screen.h - from.ty;
	if (dy1 < dy)
		dy = dy1;
	int cost = dx < dy ? dx : dy;
	if (cost < 0)
		cost = 0;
	if (to.tz != -1 && from.tz != to.tz)
		cost++;
	return 2*cost;
	}

/*
 *	Is tile at goal?
 */

int Offscreen_pathfinder_client::at_goal
	(
	Tile_coord& tile,
	Tile_coord& goal
	)
	{
	return !screen.has_point(tile.tx - tile.tz/2, tile.ty - tile.tz/2);//&&
					// Z-coord shouldn't matter.
//		(goal.tz == -1 || tile.tz == goal.tz);
	}

/*
 *	Figure when to give up.
 */

int Fast_pathfinder_client::get_max_cost
	(
	int cost_to_goal		// From estimate_cost().
	)
	{
	int max_cost = 2*cost_to_goal;	// Don't try too hard.
	if (max_cost < 8)
		max_cost = 8;
	else if (max_cost > 64)
		max_cost = 64;
	return max_cost;
	}

/*
 *	Figure cost going from one tile to an adjacent tile (for pathfinding).
 *
 *	Output:	Cost, or -1 if blocked.
 *		The 'tz' field in tile may be modified.
 */

int Fast_pathfinder_client::get_step_cost
	(
	Tile_coord from,
	Tile_coord& to			// The tile we're going to.  The 'tz'
					//   field may be modified.
	)
	{
	Game_window *gwin = Game_window::get_instance();
	int cx = to.tx/c_tiles_per_chunk, cy = to.ty/c_tiles_per_chunk;
	Map_chunk *olist = gwin->get_map()->get_chunk(cx, cy);
	int tx = to.tx%c_tiles_per_chunk;	// Get tile within chunk.
	int ty = to.ty%c_tiles_per_chunk;
	olist->setup_cache();		// Make sure cache is valid.
	int new_lift;			// Might climb/descend.
					// For now, look at 1 tile's height,
					//   and step up/down 2 (needed for SI
					//   Crystal Ball).
	if (olist->is_blocked(1, to.tz, tx, ty, new_lift, get_move_flags(), 
									2, 2))
		return -1;
	to.tz = new_lift;		// (I don't think we should do this
					//    above...)
	return 1;
	}

/*
 *	Estimate cost from one point to another.
 */

int Fast_pathfinder_client::estimate_cost
	(
	Tile_coord& from,
	Tile_coord& to
	)
	{
	return from.distance(to);	// Distance() does world-wrapping.
	}

/*
 *	Is tile at goal?
 */

int Fast_pathfinder_client::at_goal
	(
	Tile_coord& tile,
	Tile_coord& goal
	)
	{
	if (tile.distance(goal) > dist)
		return 0;		// Not close enough.
	int dz = tile.tz - goal.tz;	// Want to be within 1 story.
	return dz <= 5 && dz >= -5;
	}

/*
 *	Just test to see if an object can be grabbed.
 */

int Fast_pathfinder_client::is_grabable
	(
	Tile_coord from,		// From this spot.
	Tile_coord to			// To this spot.
	)
	{
//No.	from.tz = to.tz;		// Just look along dest's lift.
	if (from.distance(to) <= 1)
		return 1;		// Already okay.
	Fast_pathfinder_client client(1, 
	   Game_window::get_instance()->get_main_actor()->get_type_flags());
	Astar path;
	return path.NewPath(from, to, &client);
	}

/*
 *	Check for an unblocked straight path.
 *	NOTE1:  This really has nothing to do with Fast_pathfinder_client.
 *	NOTE2:	This version doesn't check the z-coord at all.
 */

int Fast_pathfinder_client::is_straight_path
	(
	Tile_coord from,		// From this spot.
	Tile_coord to			// To this spot.
	)
	{
	to.tz = from.tz;		// ++++++For now.
	Zombie path;
	if (!path.NewPath(from, to, 0))	// Should always succeed.
		return 0;
	Tile_coord t;			// Check each tile.
	bool done;
	while (path.GetNextStep(t, done))
		if (t != from && t != to && Map_chunk::is_blocked(t))
			return 0;	// Blocked.
	return 1;			// Looks okay.
	}

/*
 *	Create client for getting within a desired distance of a
 *	destination.
 */

Monster_pathfinder_client::Monster_pathfinder_client
	(
	Actor *npc,			// 'Monster'.
	Tile_coord dest,
	int dist
	) : Fast_pathfinder_client(dist), destbox(dest.tx, dest.ty, 0, 0)
	{
	intelligence = npc->get_property(Actor::intelligence);
	Shape_info& info1 = npc->get_info();
	axtiles = info1.get_3d_xtiles();
	aytiles = info1.get_3d_ytiles();
	aztiles = info1.get_3d_height();
	set_move_flags(npc->get_type_flags());
	destbox.enlarge(dist);		// How close we need to get.
	}

/*
 *	Create client for combat pathfinding.
 */

Monster_pathfinder_client::Monster_pathfinder_client
	(
	Actor *attacker,
	int reach,			// Weapon reach in tiles.
	Game_object *opponent
	) : Fast_pathfinder_client(reach), destbox(0, 0, 0, 0)
	{
	intelligence = attacker->get_property(Actor::intelligence);
	Shape_info& info1 = attacker->get_info();
	axtiles = info1.get_3d_xtiles();
	aytiles = info1.get_3d_ytiles();
	aztiles = info1.get_3d_height();
	if (!opponent)
		return;			// Means this isn't usable.
	set_move_flags(attacker->get_type_flags());
	Shape_info& info2 = opponent->get_info();
	Tile_coord opos = opponent->get_tile();
	int oxtiles = info2.get_3d_xtiles(), oytiles = info2.get_3d_ytiles();
	destbox = Rectangle(opos.tx - oxtiles + 1, opos.ty - oytiles + 1,
							oxtiles, oytiles);
	destbox.enlarge(reach);		// This is how close we need to get.
	}

/*
 *	Figure when to give up.
 */

int Monster_pathfinder_client::get_max_cost
	(
	int cost_to_goal		// From estimate_cost().
	)
	{
	int max_cost = 2*cost_to_goal;	// Don't try to hard.
	int icost = 2 + 2*intelligence;	// Limit by intelligence.
	if (max_cost > icost)		// Note: intel. ranges from 0 to 30.
		max_cost = icost;
	Game_window *gwin = Game_window::get_instance();
					// Limit to 3/4 screen width.
	int scost = ((3*gwin->get_width())/4)/c_tilesize;
	if (max_cost > scost)
		max_cost = scost;
	if (max_cost < 15)		// But not too small.
		max_cost = 15;
	return max_cost;
	}

/*
 *	Is tile at goal?
 */

int Monster_pathfinder_client::at_goal
	(
	Tile_coord& tile,
	Tile_coord& goal
	)
	{
	int dz = tile.tz - goal.tz;	// Got to be on same floor.
	if (dz/5 != 0)
		return 0;
	Rectangle abox(tile.tx - axtiles + 1, tile.ty - aytiles + 1,
						axtiles, aytiles);
	return abox.intersects(destbox);
	}

/*
 *	Figure cost going from one tile to an adjacent tile (for pathfinding).
 *
 *	Output:	Cost, or -1 if blocked.
 *		The 'tz' field in tile may be modified.
 */

int Monster_pathfinder_client::get_step_cost
	(
	Tile_coord from,
	Tile_coord& to			// The tile we're going to.  The 'tz'
					//   field may be modified.
	)
	{
	if (Map_chunk::is_blocked(axtiles, aytiles, aztiles,
						from, to, get_move_flags()))
		return -1;
	else
		return 1;
	}