/*
 * Copyright (C) 2002-2007 The Warp Rogue Team
 * Part of the Warp Rogue Project
 *
 * This software is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License.
 * This software is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY.
 *
 * See the license.txt file for more details.
 */

/*
 * Module Name: Pathfinder
 * Description: -
 */

#define Uses_Area
#define Uses_Sector
#define Uses_Terrain
#define Uses_Object
#define Uses_ProgramManager
#define Uses_Util
#define Uses_Ai
#define Uses_Perception
#define Uses_Movement
#include "mheader.h"

#include "pathfind.h"

#include "path.h"


#define MIN_DIFF_TO_MATTER	5



static const PATH_NODE *	find_any_ai_path(const CHARACTER *, 
					const AREA_POINT *
				);

static bool			find_path_with_ptf(const AREA_POINT *,
					const AREA_POINT *
				);

static void			store_path(void);

static int			obstacle_at(int, int);



/*
 * the starting point of the currently calculated path
 */
static const AREA_POINT *	PathStart;


/*
 * the most recently calculated path
 */
static PATH_NODE *		Path = NULL;
static AREA_DISTANCE		PathLength;


/*
 * the stored path
 */
static PATH_NODE *		StoredPath = NULL;
static AREA_DISTANCE		StoredPathLength;
static bool			StoredPathExists;


/*
 * the character who is trying to find a path
 */
static const CHARACTER *	PathSubject;


/*
 * pathfinder options
 */
static bool			IgnoreCharacters;
static bool			IgnoreDestructable;
static bool			IgnoreDangerous;




/*
 * pathfinder module init
 */
void pathfinder_init(void)
{
	const AREA_SECTION *bounds;
	
	Path = checked_malloc(MAX_PATH * sizeof *Path);

	StoredPath = checked_malloc(MAX_PATH * sizeof *StoredPath);

	bounds = area_bounds();
	
	ptf_setup(bounds->bottom + 1, bounds->right + 1, 
		MAX_PATH, obstacle_at
	);
}



/*
 * pathfinder module clean up
 */
void pathfinder_clean_up(void)
{

	ptf_clean_up();

	if (StoredPath != NULL) {
		
		free(StoredPath);
	}

	if (Path != NULL) {
		
		free(Path);
	}
}



/*
 * tries to find a path for the AI
 * 
 * this version tries really hard to find a path, and will return
 * dangerous paths and paths which are blocked by destructable obstacles
 * if no better paths are available
 *
 * this function does NOT treat characters as obstacles
 *
 */
const PATH_NODE * find_ai_path(const CHARACTER *character, 
	const AREA_POINT *target_point
)
{	
	PathSubject = character;
	
	StoredPathExists = false;

	if (find_safe_ai_path(character, target_point) != NULL) {

		if (PathLength <= MAX_SHORT_PATH) {
			
			return Path;
			
		} else {

			store_path();
		}
	}
	
	if (find_any_ai_path(character, target_point) != NULL) {

		if (StoredPathExists) {
			
			if (PathLength + MIN_DIFF_TO_MATTER <
				StoredPathLength) {

				return Path;
			}
			
		} else {
		
			return Path;
		}
	}

	if (StoredPathExists) {
		
		return StoredPath;
	}
	
	return NULL;
}



/*
 * tries to find a safe path for the AI
 *
 * this function will either return a clean path or no path at all
 *
 * this function does NOT treat characters as obstacles
 *
 */
const PATH_NODE * find_safe_ai_path(const CHARACTER *character, 
	const AREA_POINT *target_point
)
{

	PathSubject = character;

	IgnoreDestructable = false;
	IgnoreDangerous = false;
	IgnoreCharacters = true;

	if (find_path_with_ptf(&character->location, target_point)) {

		return Path;
	}	

	return NULL;
}



/*
 * tries to find a safe path which bypasses characters
 */
const PATH_NODE * find_bypass_characters_path(const CHARACTER *character,
	const AREA_POINT *target_point
)
{

	PathSubject = character;

	IgnoreCharacters = false;
	IgnoreDestructable = false;
	IgnoreDangerous = false;

	if (find_path_with_ptf(&character->location, target_point)) {

		return Path;
	}

	return NULL;
}




/*
 * tries to find a path (run command version)
 */
const PATH_NODE * find_run_command_path(const CHARACTER *character,
	const AREA_POINT *target_point
)
{

	PathSubject = character;

	IgnoreCharacters = false;
	IgnoreDestructable = false;
	IgnoreDangerous = true;

	if (find_path_with_ptf(&character->location, target_point)) {

		return Path;
	}

	return NULL;
}



/*
 * tries to find a path (jump version)
 */
const PATH_NODE * find_jump_path(const CHARACTER *character, 
	const AREA_POINT *target
)
{

	PathSubject = character;

	IgnoreCharacters = true;
	IgnoreDangerous = true;
	IgnoreDestructable = false;

	if (find_path_with_ptf(&character->location, target)) {

		return Path;
	}

	return NULL;
}



/*
 * returns the length of a path
 */
AREA_DISTANCE path_length(const PATH_NODE *node)
{
	if (node == Path) {
		
		return PathLength;
	}
	
	if (node == StoredPath) {

		return StoredPathLength;
	}

	die("*** CORE ERROR *** bug in path_length()");

	/* NEVER REACHED */
	return 0;
}



/*
 * returns true if a character blocks the first step on the
 * passed path
 */
bool character_blocks_path(const CHARACTER *character, const PATH_NODE *path)
{
	const AREA_POINT *first_step;
	const SECTOR *sector;

	first_step = path_first_step(path);
	sector = sector_at(first_step);

	if (sector->character == NULL) {
		
		return false;
	}
		
	if (unnoticed_enemy_at(character, first_step) ||
		can_push_past(character, sector->character)) {

		return false;
	}

	return true;
}



/*
 * returns true if there is a destructable obstacle at the passed
 * point
 *
 * this is an AI specific function; it only returns true if the
 * AI considers the obstacle destructable i.e. if its condition 
 * is below a certain limit
 *
 */
bool destructable_obstacle_at(const AREA_POINT *point)
{
	const OBJECT *object;
	
	object = object_at(point);

	if (object != NULL && 
		object_has_attribute(object, OA_IMPASSABLE) &&
		object->condition != CONDITION_INDESTRUCTABLE &&
		object->condition <= AI_OBSTACLE_DESTRUCTION_MAX) {
	
		return true;
	}

	return false;
}



/*
 * tries to find a path for the AI
 *
 * this function may return dangerous paths and/or paths blocked
 * by destructable obstacles
 *
 * this function does NOT treat characters as obstacles
 *
 */
static const PATH_NODE * find_any_ai_path(const CHARACTER *character,
	const AREA_POINT *target_point
)
{

	PathSubject = character;
	
	IgnoreCharacters = true;
	IgnoreDangerous = true;
	IgnoreDestructable = true;

	if (find_path_with_ptf(&character->location, target_point)) {

		return Path;
	}

	return NULL;
}



/*
 * tries to find a path by using the PTF pathfinding lib
 */
static bool find_path_with_ptf(const AREA_POINT *start, 
	const AREA_POINT *target_point
)
{
	const PTF_PATH_NODE *path;
	const PTF_PATH_NODE *node;
	int i;

	PathStart = start;
	
	path = ptf_find_path(start->y, start->x, 
		target_point->y, target_point->x
	);

	if (path == NULL) {
		
		return false;
	}

	for (node = path, i = 0;
		node != NULL && i < MAX_PATH;
		node = node->parent, i++) {

		Path[i].p.y = node->y;
		Path[i].p.x = node->x;

		if (i < MAX_PATH - 1) {

			Path[i].parent = &Path[i + 1];
		}
	}

	Path[i - 1].parent = NULL;
	PathLength = i;

	return true;
}

	




/*
 * stores the current path
 */
static void store_path(void)
{

	memcpy(StoredPath, Path, MAX_PATH * sizeof *Path);
	
	StoredPathLength = PathLength;
	
	StoredPathExists = true;
}



/*
 * returns 1 if there is an obstacle at the passed point
 * or 0 if there is no obstacle
 */
static int obstacle_at(int y, int x)
{
	AREA_POINT point;
	SECTOR *sector;
	TERRAIN *terrain;
	OBJECT *object;
	CHARACTER *character;

	point.y = y;
	point.x = x;
	
	if (area_points_equal(&point, PathStart)) {

		return false;
	}
	
	sector = sector_at(&point);
	
	character = sector->character;
	if (!IgnoreCharacters && character != NULL) {

		return true;
	}

	object = sector->object;
	if (object != NULL && object_has_attribute(object, OA_IMPASSABLE)) {
		
		if (!IgnoreDestructable || 
			!destructable_obstacle_at(&point)) {

			return true;
		}
	}

	terrain = sector->terrain;
	if (terrain != NULL) {
		const TERRAIN_DATA *terrain_data;

		terrain_data = terrain_static_data(terrain);

		if (terrain_data->attribute[TA_IMPASSABLE]) {
			
			return true;
		}

		if (!IgnoreDangerous &&
			terrain_data->attribute[TA_DANGEROUS]) {

			return terrain_dangerous_for(PathSubject,
				terrain
			);
		}
	}

	return false;
}