Finding a nearest entity

[Orion]

Hi, is there a way to search for the nearest entity using find/findradius?

I know that findradius() searches in a specified sphere size, but what if I don't know how far is that entity?


Example:

A bot is running around the map, right? He want to follow the nearest enemy from his position. How can I do that?

I think find/findradius searches entities from a specified order, but I think it isn't from nearer from farther.

Thanks!

[Dr. Shadowborg]

Hi, is there a way to search for the nearest entity using find/findradius?

I know that findradius() searches in a specified sphere size, but what if I don't know how far is that entity?


Example:

A bot is running around the map, right? He want to follow the nearest enemy from his position. How can I do that?

I think find/findradius searches entities from a specified order, but I think it isn't from nearer from farther.

Thanks!

Use something like:

Code: Select all

dist = vlen(self.origin-head.origin);

[Preach]

Kind of tangential question, but does anyone know which of the following is faster to do in qc:

x = vlen( vec );

or

x = vec_x * vec_x + vec_y * vec_y + vec_z * vec_z;

One is a function call which has to calculate a square root, while the other has 3 multiplications and two additions, but all handled in the qc parser. If it's the latter, then there's a optimisation you can use in cases where you have lots of distance comparisons to make each frame.

[Spike]

in qc, the fastest is:
x = vec*vec;

Yes. There is a built in dotproduct instruction.
The resulting distance is squared, but if you don't care about the actual distances (only which one is smallest) then its fine.

[Preach]

Excellent, I should have thought of that one. You can, in lots of cases, use the squared distance in place of a regular distance. For instance, if you want to know if a given vector is of length less than 100, dot the vector with itself, and test if the dot product is less than 10,000(which is 100 squared). This kind of optimisation would probably come in handy in ai routines which are run 10 times a second on every monster, if you care about optimality that is.

[Orion]

Hmm, I see.

But to calculate the distance of the found entity, vlen() should be called inside while(head), but as while() loops, it will be different each loop...

Code: Select all

while (head)
{
...
dist = vlen(head.origin - self.origin); // calc distance
dist = dist*dist; // so I get the current distance squared
...
}

Kinda tricky... What if I do this?
The bot will search for players and then pick a goalentity... He'll calculate his goal's distance, square it, and re-search for the nearest goal, I'm not sure if that works.

Here's an example:

Code: Select all

void() FindPlayer =
{
	local entity plr;

	plr = find(world, classname, "player");
	while (plr)
	{
		if (plr != self)
		if (plr.health > 0)
		{
			self.goalentity = plr;
			self.SQRT_last_goal_dist = vlen(plr.origin - self.origin);
			self.SQRT_last_goal_dist = self.SQRT_last_goal_dist*self.SQRT_last_goal_dist;
		}
	}
};

void() FindNearestPlayer =
{
   local entity plr;

   plr = find(world, classname, "player");
   while (plr)
   {
      if (plr != self)
      if (plr.health > 0)
      {
         if (vlen(self.goalentity.origin - self.origin) < self.SQRT_last_goal_dist)
            self.goalentity = plr;
      }
   }
};

[Sajt]

dist = vlen(head.origin - self.origin); // calc distance
dist = dist*dist; // so I get the current distance squared

This is redundant and slow...

vlen is implemented like this: vlen(v) = sqrt(v dot v)

So you are calling sqrt, then squaring the result. This is a waste as these two operations cancel each other out. All you want is the 'v dot v'.

local vector delta;
delta = head.origin - self.origin;
dist = d*d;

[Orion]

I still can't understand...

Where I put these lines? I think if I put inside the while() it will reset chage every loop... I need a meaningful explanation please.

[Preach]

Since I've got an answer out of this thread and sent it off topic like that, I suppose I should help : -p. You need two distance variables, lowestdist and dist, along with an entity variable called nearestent. These can be variables local to the function. The idea is you store the nearest entity you've found so far in nearestent, and the distance that was found at in lowestdist. Then you calculate dist for the next entity, and compare to see if dist is smaller than lowestdist. If so, then assign the value of dist to lowestdist, and assign the current entity to nearestent. Once the while loop has completed, nearestent will be the entity that had the least distance between it and the player.

The one important snag you have to be careful of is that you need a starting value for lowestdist, otherwise it will default to 0 and nothing can be closer than 0 distance. So when you find the first player, assign that player to nearestent and the distance of that player to lowestdist before the while loop. Another pitfall you're going to have to watch out for in the specific code you've written is what happens if there are no players other than self, or if all of them are dead.

[Spike]

something like:

(warning unreadable version!)

Code: Select all

float(vector fwd, vector org, entity p) playerweight =
{
  local vector dir;

  if (p.health <= 0)
    return 0; //dead, not a viable target
  
  dir = p.origin - org;
  if (fwd != '0 0 0')
  {
    if (fwd*normalize(dir) < 0)
    {
      if (random() < 0.95)
        return 0;  //its behind us, we're blind at the moment
    }
  }
  
  //fixme: traceline from org+eye to p.origin to see if we can see them (do about 8 traces to the different parts of the model)

  return 10000/(tvec*tvec); //invert it, so nearer = bigger number
};

entity(vector fwd, vector org, entity ignore) findnearestplayer =
{
  local entity best. plr;
  local float bestweight, weight;

  while((plr = find(plr, classname, "player")))
  {
    if (plr != ignore)
    {
      weight = playerweight(org, plr);
      if (weight > bestweight)
      {
        bestweight = weight;
        best = plr;
      }
    }
  }
  return best;
};

To try and find a new target:
makevectors(self.angles);
self.goalentity = findnearestplayer(v_forward, self.origin, self);

I think find/findradius searches entities from a specified order, but I think it isn't from nearer from farther.

They do return in an order, but its not a meaningful one. Its actually in vauge creation order, with removed slots being reused. Never rely upon any ordering except that any two entities will be in the same order relative to each other over multiple frames. This is the same order as nextent() gives - order of allocation.

[Orion]

Thanks for the code, but I found out a simpler way to do it before you posted, and I think it worked, because all bots encounter each other (including me) in a specified point.

Here's it:

Code: Select all

void() FindNearestPlayer =
{
	local entity head, near;
	local float dist, low;
	
	if (self.goalentity)
		return;
	
	low = 99999999;	// because nothing in quake can have 0 distance
	
	head = find(world, classname, "player");
	while (head)
	{
		if (head != self)
		if (head.health > 0)
		{
			dist = vlen(head.origin - self.origin);
			if (dist < low)
			{
				low = dist;
				near = head;
			}
		}
		head = find(head, classname, "player");
	}
	
	if (near)
		self.goalentity = near;
};

[Sajt]

Yup, that looks about right. But if you want to use the optimization discussed above (though it won't cause a noticeable framerate improvement ), change this

Code: Select all

dist = vlen(head.origin - self.origin);

to this

Code: Select all

delta = head.origin - self.origin;
dist = delta*delta; // some comment explaining the optimization

With delta declared earlier as a local vector.