Draw direct path from AI to target?

Discuss Artificial Intelligence and Bot programming.
Post Reply
Mexicouger
Posts: 514
Joined: Sat May 01, 2010 10:12 pm
Contact:

Draw direct path from AI to target?

Post by Mexicouger »

I have been racking my brain for several days trying to come up with the BEST method of doing this. So far, I have failed to do a DIRECT path from the waypoint closet to the target, making a path to the AI in a map.

My current code for making a path.

Code: Select all


void(entity l1, entity l2, entity client) Ai_Follow_Link =
{
	bprint("LINKS GOING ON!\n");
	traceline(l1.origin, l2.origin, FALSE, l1);
	trailparticles(l1, particleeffectnum("carbine"), l1.origin, l2.origin);

	client.cur_way_in_path = l2;
	client.enemy = l1;
};

//waypoint touch code
if(other.classname == "AI" && other.touched_way_update < time)
	{
		if(other.stack1 == world)
			return;

		other.touched_way_update = time + 1;
	/*
	//get the closet, visible waypoint from the target\\
	*/
	if(other.cur_way_in_path == world)
	{
		bprint("finding a new cur_way_in_path\n");
		local entity closest_way, best_way;
		local float cur_dist, best_dist;
		closest_way = world;
		best_way = world;
		closest_way = findradius(other.stack1.origin, 1000);
		best_dist = 1000;

		while(closest_way)
		{
			if(closest_way.classname == "ai_waypoint")
			{
				cur_dist = vlen(closest_way.origin - other.stack1.origin);	
				bprint("cur dist: ");
				bprint(ftos(cur_dist));
				bprint("\n");
				bprint("best dist: ");
				bprint(ftos(best_dist));
				bprint("\n");
				if(cur_dist < best_dist)
				{
					traceline (closest_way.origin, other.stack1.origin, FALSE, closest_way);
					//trailparticles(closest_way, particleeffectnum("carbine"), closest_way.origin, other.stack1.origin);
					bprint("trace_ent: ");
					bprint(trace_ent.classname);
					bprint("\n");
	
					bprint("trace_fraction: ");
					bprint(ftos(trace_fraction));
					bprint("\n");	
					if(trace_ent)
					{
						best_way = closest_way;
						best_dist = cur_dist;
						bprint("Hitting an entity\n");
					}
					else if (trace_fraction == 1)
					{
						best_way = closest_way;
						best_dist = cur_dist;
						bprint("Hitting an entity\n");
					}
					else if(trace_fraction != 1 && !trace_ent)
					{
						bprint("Hitting a wall\n");
					}
				}
			}
			closest_way = closest_way.chain;
		}

		//bprint(best_way.classname);
		//bprint("\n");

		other.path_way_num = best_way.way_num;
		other.cur_way_in_path = best_way;
		other.cur_way_in_path.link1 = best_way.link1;
		other.cur_way_in_path.link2 = best_way.link2;
		other.cur_way_in_path.link3 = best_way.link3;
		other.cur_way_in_path.link4 = best_way.link4;
		trailparticles(other.cur_way_in_path, particleeffectnum("carbine"), other.cur_way_in_path.origin, other.stack1.origin);
	}
	//Stupid hack.. FREAKING FIX TEVIN!!
	local float attempts;
	attempts = 10;
	local entity cant_go_back;
	while (other.cur_way_in_path != self)
	{
		if(other.cur_way_in_path == world)
			break;

		//Next
		local float d1, d2, d3, d4, link_used1, link_used2, link_used3, link_used4;
		local float lowest_dist;
		lowest_dist = 0;
	
		d1 = vlen(other.origin-other.cur_way_in_path.link1.origin);
		if(other.cur_way_in_path.link1 == world)
			d1 = 0;
		d2 = vlen(other.origin-other.cur_way_in_path.link2.origin);
		if(other.cur_way_in_path.link2 == world)
			d2 = 0;
		d3 = vlen(other.origin-other.cur_way_in_path.link3.origin);
		if(other.cur_way_in_path.link3 == world)
			d3 = 0;
		d4 = vlen(other.origin-other.cur_way_in_path.link4.origin);
		if(other.cur_way_in_path.link4 == world)
			d4 = 0;

		if(d4 != 0)
		{
			lowest_dist = min4(d1, d2, d3, d4);
			//bprint("4 links\n");
		}
		else if (d4 == 0 && d3 != 0)
		{
			lowest_dist = min3(d1, d2, d3);
			//bprint("3 links\n");
		}
		else if (d4 == 0 && d3 == 0 && d2 != 0)	
		{
			lowest_dist = min(d1, d2);
			//bprint("2 links\n");
		}
		else if (d4 == 0 && d3 == 0 && d2 == 0)
		{
			lowest_dist = d1;
			//bprint("1 links\n");
		}
	
		//What I could do is test every link1, and set a tag on that waypoint, and then go through each
		//waypoint and reset the tag
		//Try making a path to self.
	
		//Sort of hackish. I really need to come up with an alternative..
		//Basically, it switches to getting to its target by waypoint numbers.
		//This isn't efficient because the path will always be the same, and 
		//the AI might have to rerun through the entire map to get to its target

		//ANOTHER HUUGE HACK!
	if(vlen(other.enemy.origin-other.origin) == lowest_dist && other.enemy != self)
		{
			attempts -= 1;
			if (attempts == 0)
				break;
			local float link_wahoo;	//F*** it
			local float closest_way_num;
			local float distance_apart;
			distance_apart = 100;

				if((other.cur_way_in_path.link1.way_num-self.way_num) < distance_apart)
				{
					distance_apart = other.cur_way_in_path.link1.way_num-self.way_num;
					closest_way_num = other.cur_way_in_path.link1.way_num;
				}

				if(((other.cur_way_in_path.link2.way_num-self.way_num) < distance_apart) && other.cur_way_in_path.link2 != world)
				{
					distance_apart = other.cur_way_in_path.link2.way_num-self.way_num;
					closest_way_num = other.cur_way_in_path.link2.way_num;
				}

				if(((other.cur_way_in_path.link3.way_num-self.way_num) < distance_apart) && other.cur_way_in_path.link3 != world)
				{
					distance_apart = other.cur_way_in_path.link3.way_num-self.way_num;
					closest_way_num = other.cur_way_in_path.link3.way_num;
				}

				if(((other.cur_way_in_path.link4.way_num-self.way_num) < distance_apart) && other.cur_way_in_path.link4 != world)
				{
					distance_apart = other.cur_way_in_path.link4.way_num-self.way_num;
					closest_way_num = other.cur_way_in_path.link4.way_num;
				}	

		if(closest_way_num == other.cur_way_in_path.link1.way_num)
			Ai_Follow_Link(other.cur_way_in_path, other.cur_way_in_path.link1, other);
		else if(closest_way_num == other.cur_way_in_path.link2.way_num)
			Ai_Follow_Link(other.cur_way_in_path, other.cur_way_in_path.link2, other);
		else if(closest_way_num == other.cur_way_in_path.link3.way_num)
			Ai_Follow_Link(other.cur_way_in_path, other.cur_way_in_path.link3, other);
		else if(closest_way_num == other.cur_way_in_path.link4.way_num)
			Ai_Follow_Link(other.cur_way_in_path, other.cur_way_in_path.link4, other);
		}

		if(lowest_dist == d1)
		{
			bprint("Link 1 is closer\n");
			Ai_Follow_Link(other.cur_way_in_path, other.cur_way_in_path.link1, other);
		}
		else if(lowest_dist == d2 && d2 != 0)
		{
			bprint("Link 2 is closer\n");
			Ai_Follow_Link(other.cur_way_in_path, other.cur_way_in_path.link2, other);		
		
		}
		else if(lowest_dist == d3 && d3 != 0)
		{
			bprint("Link 3 is closer\n");
			Ai_Follow_Link(other.cur_way_in_path, other.cur_way_in_path.link3, other);
		}
		else if(lowest_dist == d4 && d4 != 0)
		{
			bprint("Link 4 is closer\n");
			Ai_Follow_Link(other.cur_way_in_path, other.cur_way_in_path.link4, other);
		}
	}
               //for testing
		te_customflash(other.enemy.origin, 100, 1, '1 0 0');
		te_customflash(other.cur_way_in_path.origin, 100, 1, '0 0 1');
	}
It's very uncommented and messy. This code is called when an AI touches a waypoint. What it does right now, is it finds the closet waypoint to the Ai's target, and follows links of waypoints based on how close they are to the AI. That's very inefficient because it could try to draw a path to A waypoint thats can't even reach the AI's waypoint. So in that case, I added a huge hack. The Ai will use waypoint numbers and follow each waypoint based on which is the closest to the waypoint number that the Ai is on. That means the AI might have to go through the entire map the way the player waypointed it just in order to get to the target it wants.

You may also see I added the attempts float. That's another hack to get it out of the loop because it doesn't always get to the AI's current waypoint due to some maps structure.

This code works on some maps, and not on others. I basically just want to code it so that a complete direct path is made from the Ai's target, straight to the waypoint the AI is currently touching. If anyone has any suggestions or ideas i'd appreciate it!

Some notes: My waypoint system uses 4 links per waypoint. (.link1, .link2, .link3, .link4). The AI can hold up to 4 entities in its stack (Waypoints excluded. Waypoints use .enemy for the most part unless stack1 is seen and in range of the Ai.) (.stack1, .stack2, .stack3, .stack4)
Spike
Posts: 2914
Joined: Fri Nov 05, 2004 3:12 am
Location: UK
Contact:

Re: Draw direct path from AI to target?

Post by Spike »

what are you trying to do? routing?

most people use A* for that.
dijkstra's algorithm may be easier to understand.

both are explained well enough on wikipedia.
Mexicouger
Posts: 514
Joined: Sat May 01, 2010 10:12 pm
Contact:

Re: Draw direct path from AI to target?

Post by Mexicouger »

Thanks Spike! I was looking at Routing haha.
I had a very rough idea of Dijkstras algorithm in my head, but it wasn't as useful.
Post Reply