// Sample implementation of A* search on a simple 2D Cartesian space
//
// v1.0   2007-10-06, Chaos of Lost Souls MUD, http://lostsouls.org/
// v1.1   2013-08-18, Chaos; graph terminology update
// v2.0   2015-06-17, Chaos: adapt for interface changes, improve style

#include <astar.h>

inherit "/mod/algorithm/astar";

#define Map_Min_X   1
#define Map_Max_X   20
#define Map_Min_Y   1
#define Map_Max_Y   10
#define X           0
#define Y           1

// Neighbors rule produces nodes and edges for the points adjacent to us.

mixed * astar_neighbors_rule(mixed * pathfind) {
	int * node = pathfind[Astar_Pathfind_Active_Node];
	mixed * out = ({});
	if(node[X] > Map_Min_X)
		out += ({
		    ({
				({ node[X] - 1, node[Y] }),     // Adjacent node
				({ -1, 0 }),                    // Edge to adjacent node
				1,                              // Cost of edge
			})
		});
	if(node[X] < Map_Max_X)
		out += ({
		    ({
				({ node[X] + 1, node[Y] }),     // Adjacent node
				({ 1, 0 }),                     // Edge to adjacent node
				1,                              // Cost of edge
			}),
		});
	if(node[Y] > Map_Min_Y)
		out += ({
		    ({
				({ node[X], node[Y] - 1 }),     // Adjacent node
				({ 0, -1 }),                    // Edge to adjacent node
				1,                              // Cost of edge
			}),
		});
	if(node[Y] < Map_Max_Y)
		out += ({
		    ({
				({ node[X], node[Y] + 1 }),     // Adjacent node
				({ 0, 1 }),                     // Edge to adjacent node
				1,                              // Cost of edge
			}),
		});
	return out;
}

// Distance rule calculates the distance from a point to the target
// node.  Using the Pythagorean Theorem, yo.

float astar_distance_rule(mixed * pathfind) {
	int * a = pathfind[Astar_Pathfind_Active_Node];
	int * b = pathfind[Astar_Pathfind_To];
	int dx = a[X] - b[X];
	int dy = a[Y] - b[Y];
	return sqrt(dx * dx + dy * dy);
}

// Node key rule gives us a unique value corresponding to a node that
// can be reliably used as a mapping key.  Since we're using arbitrary
// two-element arrays as nodes, and arrays are pointers that will give
// unpredictable behavior when used as mapping keys, we need to use this
// so the algorithm can tell where it's been.

int astar_node_key_rule(int * node) {
	return (node[X] << 16) | node[Y];
}

// Run limit rule tells the algorithm when to stop running and continue
// on a call_out.

int astar_run_limit_rule(mixed * pathfind) {
	return get_eval_cost() < __MAX_EVAL_COST__ / 2;
}

// Set up the A* module.

void create() {
	set_astar_neighbors_rule(#'astar_neighbors_rule);
	set_astar_distance_rule(#'astar_distance_rule);
	set_astar_node_key_rule(#'astar_node_key_rule);
	set_astar_run_limit_rule(#'astar_run_limit_rule);
	set_astar_caching(1);
}

// This is our callback when pathfinding completes (for better or worse);
// it displays the path to this_player().

void end_random_pathfind(mixed * pathfind) {
	mixed res = pathfind[Astar_Pathfind_Result];
	if(pointerp(res)) {
		mixed * path = res;
		mixed * nodes = path[Astar_Path_Nodes];
		int last = path[Astar_Path_Length] - 1;
		write("Path from " + nodes[0][X] + "," + nodes[0][Y] + " to " +
			nodes[last][X] + "," + nodes[last][Y] + ":\n");
		for(int ix = 0; ix <= last; ix++) {
			mixed * node = nodes[ix];
			write("    " + node[X] + "," + node[Y] + "\n");
		}
	} else {
		write("Cannot find path: result " + res + "\n");
	}
}

// Picks two random points in our coordinate space and pathfinds between
// them.

void start_random_pathfind() {
	int * start = ({
	    Map_Min_X + random(Map_Max_X - Map_Min_X + 1),
		Map_Min_Y + random(Map_Max_Y - Map_Min_Y + 1),
	});
	int * target = ({
	    Map_Min_X + random(Map_Max_X - Map_Min_X + 1),
		Map_Min_Y + random(Map_Max_Y - Map_Min_Y + 1),
	});
	astar_find_path(start, target, 0, #'end_random_pathfind);
}