/////////////////////////////////////////////////////////////////////////////////////////////
// copy the files inside this folder inside your gamestudio folder
// open level2.wmp, build it and run it using ai2.wdl
/////////////////////////////////////////////////////////////////////////////////////////////
// Perfect AI is constantly developed by George Pirvu george@acknex.net
// the maximum number of nodes that can be placed in the level is 1000
// this demo uses 30 nodes; increase the size of the arrays if you need more nodes in your level
// the distance between two consecutive nodes should be smaller than 1000 quants for this demo
/////////////////////////////////////////////////////////////////////////////////////////////

STRING* level2_wmb = "level2.wmb";
STRING* marker_mdl = "marker.mdl";

/////////////////////////////////////////////////////////////////////////////////////////////

var max_nodes = 30; // number of nodes used in this demo
var number_of_nodes = -1; // stores the number of nodes (0...29 in this demo)
var current_node = 0; // the current node that scans for the other nodes
var touched_node = 0;
var start_node = 0;
var target_node = 0; // closest node to the player that can "see" the player

var node_to_player[30]; // distance from the node to the player, up to 30 nodes
var see_player[30]; // sets the corresponding var to 1 if the node can see the player
var nodex[30]; // x coordinates for the nodes
var nodey[30]; // y coordinates for the nodes 
var node_to_node[900]; // stores the distance between any two nodes (30 x 30 elements)
var visited[900]; // stores the actual path from a node to any other node
var path[30]; // stores the elements of the actual path

var closest_distance = 999999; // will hold the distance from the closest visible node to the player
var index = 0; // used as a counter from 0 to 29
var distances_computed = 0; // will be set to 1 when the array is filled with the distances between nodes
var next_node; // next node on the shortest path

var i; // 4 counters with short names to make the code more readable
var j; 
var k; 
var l;

/////////////////////////////////////////////////////////////////////////////////////////////

SOUND* beep_sound = "beep.wav";

/////////////////////////////////////////////////////////////////////////////////////////////

FONT* system_font = "Arial#20b"; // truetype font 

/////////////////////////////////////////////////////////////////////////////////////////////

BMAP* pointer_pcx = "pointer.pcx";

/////////////////////////////////////////////////////////////////////////////////////////////

function trace_back();
function init_mouse();
function run_algorithm(); // Floyd - Dijkstra - George :) algorithm 
function display_path();
function dynamic_light();

/////////////////////////////////////////////////////////////////////////////////////////////

TEXT* ai_txt = // displays the texts on the screen
{
	font = system_font;
	pos_x = 0;
	pos_y = 30;
	string = "   Touched:\n   Start:\n   Target:";
	flags = VISIBLE;
}

//////////////////////////////////////////////////////////////////////////////////////////////

PANEL* ai_pan = // displays the numerical values on the screen
{
	pos_x = 0;
	pos_y = 0;
	layer = 10;
	digits = 120, 30, 2, system_font, 1, touched_node;
	digits = 120, 43, 2, system_font, 1, target_node;
	digits = 120, 56, 2, system_font, 1, start_node;

	digits = 0, 0, 4, system_font, 1, path[0]; // display the first 15 points on the shortest path
	digits = 30, 0, 4, system_font, 1, path[1]; // should be enough for everybody
	digits = 60, 0, 4, system_font, 1, path[2]; 
	digits = 90, 0, 4, system_font, 1, path[3];
	digits = 120, 0, 4, system_font, 1, path[4];
	digits = 150, 0, 4, system_font, 1, path[5];
	digits = 180, 0, 4, system_font, 1, path[6];
	digits = 210, 0, 4, system_font, 1, path[7];
	digits = 240, 0, 4, system_font, 1, path[8];
	digits = 270, 0, 4, system_font, 1, path[9];
	digits = 300, 0, 4, system_font, 1, path[10];
	digits = 330, 0, 4, system_font, 1, path[11];
	digits = 360, 0, 4, system_font, 1, path[12];
	digits = 390, 0, 4, system_font, 1, path[13];
	digits = 420, 0, 4, system_font, 1, path[14];

	flags = OVERLAY | VISIBLE;
}

///////////////////////////////////////////////////////////////////////////////////////////////

function main()
{	
	video_mode = 8; // 1024x768;
	video_depth = 16; // D3D mode
	mouse_range = 5000; // the nodes can be touched even if they are 5000 quants away
	fps_max = 60; // limit the frame rate to 60 fps
	clip_size = 0; // show all the triangles for all the models
	level_load(level2_wmb);
	wait (3); // wait for the level to be loaded
	camera.z = 2400; // choose a convenient camera height
	camera.tilt = -90; // and make it look down
	init_mouse();
	while (distances_computed == 0) {wait (1);}
	run_algorithm();
	while (1)	
	{
		index %= max_nodes; // limit "index" to 0...29 in this demo
		if ((node_to_player[index] < closest_distance) && (see_player[index] == 1))
		// if the distance from this node to the player is smaller than the current distance to the player
		// and we are dealing with a node that can see the player
		{
			closest_distance = node_to_player[index]; // then we have a new winner!
			target_node = index; // and the target is given by the current "index" value
		}
		else // haven't found a new winner?
		{
			closest_distance = node_to_player[target_node]; // then use the previous winner
		}
		index += 1;
		wait (1);
	}		
}

action player1()
{
	player = me; // I'm the player
	while (1)
	{
		my.pan += 4 * (key_cul - key_cur) * time_step; // rotates with the left / right arrow keys
		my.skill1 = 15 * (key_cuu - key_cud) * time_step; // moves forward / backward with the up / down arrow keys
		if (key_cuu + key_cud > 0) // if the player is walking
		{
			wait(1);
		}
		else // the player is standing
		{
			wait(1);
		}		
		c_move(me,my.skill1,nullvector,IGNORE_PASSABLE | GLIDE);		
		wait (1);
	}
}

action node() // using 30 nodes in this demo
{
	my.emask = ENABLE_SCAN | ENABLE_TOUCH | ENABLE_CLICK;
	my.event = trace_back;
	my.skill47 = 1234; // set this weird value for skill47 = I'm a node
	set(my,PASSABLE);
	number_of_nodes += 1; // get a unique number
	my.skill48 = number_of_nodes; // and store it in skill48
	nodex[my.skill48] = my.x; // store x and y
	nodey[my.skill48] = my.y; // for this node
	while (number_of_nodes < (max_nodes - 1)) {wait (1);} // wait for all the nodes to be placed in the level
	while (current_node <= number_of_nodes)
	{
		if (current_node == my.skill48) // I'm the current node!
		{
			VECTOR temp;
			temp.x = 360; // horizontal scanning angle 
			temp.y = 30; // vertical scanning angle
			temp.z = 1000; // scanning range
			c_scan(my.x,my.pan,temp,NULL);
			wait (1); // not needed but won't hurt anybody
			current_node += 1; // move to the next node
		}
		wait (1);
	}
	distances_computed = 1;
	while (player == NULL) {wait (1);} // wait until the player is created
	while (1)
	{
		node_to_player[my.skill48] = vec_dist(player.x, my.x); // store the distance to the player
		if (node_to_player[my.skill48] < 500) // if the player has come closer than 500 quants to this node
		{
			c_trace(my.x,player.x, IGNORE_ME | IGNORE_MODELS | IGNORE_PASSABLE);
			if (hit.entity = player) // if this node can "see" the player
			{
				see_player[my.skill48] = 1; // the node can see the player
			}
			else
			{
				see_player[my.skill48] = 0; // this node can't see the player
			}
		}
		wait(0.1); // trace 10 times a second
	}
}

function trace_back()
{
	if (event_type == EVENT_SCAN)
	{
		my.skill45 = handle(you); // store "you" because trace will destroy it
		c_trace(my.x, your.x, IGNORE_ME | IGNORE_MODELS | IGNORE_PASSABLE);		
		if (hit.entity = you) // if this node can "see" the node that scanned it
		{
			you = ptr_for_handle(my.skill45); // restore the "you" pointer
			index = you.skill48 + my.skill48 * max_nodes;
			node_to_node[index] = vec_dist(my.x, you.x);
		}
	}
	if (event_type == EVENT_TOUCH) // node touched with the mouse?
	{
		touched_node = my.skill48; // get the number of the node that was touched with the mouse pointer
	}
	if (event_type == EVENT_CLICK) // click with the mouse?
	{
		start_node = my.skill48; // this node will become start_node
	}
}

function init_mouse()
{
	mouse_map = pointer_pcx;
	mouse_mode = 2;
	while (1)
	{
		if (mouse_left == 1) {display_path();} // click the left mouse button to display the path
		mouse_pos.x = mouse_cursor.x;
		mouse_pos.y = mouse_cursor.y;
		wait (1);
	}
}

function run_algorithm()
{
	i = 0;
	j = 0;
	while (i < max_nodes)
	{
		while (j < max_nodes)
		{
			index = j + i * max_nodes; // compute the correct index in the array
			if (node_to_node[index] == 0) // if these nodes can't see each other
			{
				node_to_node[index] = 999999; // set a huge distance for the nodes that can't see each other
			}
			j += 1;
		}
		i += 1;
		j = 0;
	}
	i = 0;
	j = 0;
	k = 0;
	while (i < max_nodes)
	{
		while (j < max_nodes)
		{
			while (k < max_nodes) // go through all the nodes
			{
				// if dist(2,10) + dist(10,15) < dist(2,15) then 10 is a point on a shorter path 
				if ( (node_to_node[j + i * max_nodes] + node_to_node[i + k * max_nodes]) < (node_to_node[j + k * max_nodes]) )
				{
					// make the change: don't use the old (2,15) (2, 10, 15 are used just as an example here)
					node_to_node[j + k * max_nodes] = node_to_node[j + i * max_nodes] + node_to_node[i + k * max_nodes];
					visited[j + k * max_nodes] = i; // store the visited point
				}
				if (j == k) // dist(1,1) = dist(2,2) = dist(3,3).... = dist(29,29) should be set to 0 (not necessary but looks nicer)
				{
					node_to_node[j + k * max_nodes] = 0; // otherwise we would get d(1,1) = d(1,2) + d(2,1) if "2" is the closest node to "1"
					visited[j + k * max_nodes] = 0; // same thing here; the distance between a visited node and itself should be zero
				}
				k += 1;
			}
			k = 0;
			j += 1;
		}
		k = 0;
		j = 0;
		i += 1;
	}
}

function find_path(l, j)
{
	i = 0;
	while (i < max_nodes) // search from this node for the rest of the nodes (29 more nodes)
	{
		if ((i != j) && (visited[i + max_nodes * j] == 0)) // the current node can "see" these nodes, excepting itself of course (i != j)
		{
			if (node_to_node[l + max_nodes * j] == node_to_node[l + max_nodes * i] + node_to_node[i + max_nodes * j]) 
			// that's a node on the shortest path because the shortest path includes it
			{
				k += 1; // move to the next array element
				path[k] = i; // and store the node number inside the array
				next_node = i; // store the new node on the shortest path because it will loose its value right away
				i = max_nodes - 1; // don't test other values - eliminate other paths that have the same length (that could happen in some levels)
				if (path[k] == l) // end of search, reached the starting point (l = start_node, remember?)
				{
					return; // get out of this function
				}
			}
		}
		i += 1; // increase i if the function continues to run
	}
	j = next_node; // set the next node on the path as target
	find_path(l, j); // recursive function, search for the shortest path again (if it searched (2,10) now search (2,9) and so on)
}

function display_path()
{
	proc_kill(4); // only one instance of this function is running
	while (mouse_left == 1) {wait (1);} // wait for the mouse button to be released
	k = 0;
	while (k < max_nodes)
	{
		path[k] = 0; // reset the array, get rid of the previously stored path
		k += 1;
	}
	k = 0; // start with the first element of path[30]
	path[k] = target_node; // write the first path element
	find_path(start_node, target_node); // find the shortest path between those two nodes
	wait(1); // wait for the path to be computed; we can use wait (1) too because the function needs a single frame to run
	i = k; // k = number of nodes on the shortest path
	while (i >= 0) // decrease i until it goes below zero
	{
		VECTOR temp;
		temp.x = nodex[path[i]]; // get the previously stored coordinates for this node
		temp.y = nodey[path[i]]; // on x and y 
		temp.z = 50; // and then set a decent height above the ground
		ent_create (marker_mdl, temp, dynamic_light); // create an invisible entity that generates light
		i -= 1;
		wait(0.5); // every 0.5 seconds
	}	
}

function dynamic_light()
{
	set(my,PASSABLE | INVISIBLE);
	my.lightrange = 100; // its lightrange = 100
	my.red = 255; // and its color = red
	my.green = 0;
	my.blue = 0;
	wait(3); // use up to 7 dynamic lights (6 * 0.5 seconds + 1)
	ent_remove(me);
}