Inside3D!
     

Finding a nearest entity

 
Post new topic   Reply to topic    Inside3d Forums Forum Index -> QuakeC Programming
View previous topic :: View next topic  
Author Message
Orion



Joined: 12 Jan 2007
Posts: 414
Location: Brazil

PostPosted: Fri Jan 18, 2008 3:43 pm    Post subject: Finding a nearest entity Reply with quote

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!
_________________
There's no signature here. Stop looking for one.
Back to top
View user's profile Send private message
Dr. Shadowborg
Inside3D Staff


Joined: 16 Oct 2004
Posts: 726

PostPosted: Fri Jan 18, 2008 4:24 pm    Post subject: Re: Finding a nearest entity Reply with quote

Orion wrote:
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:

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

_________________
"Roboto suggests Plasma Bazooka."
Back to top
View user's profile Send private message
Preach



Joined: 25 Nov 2004
Posts: 122

PostPosted: Fri Jan 18, 2008 5:31 pm    Post subject: Re: Finding a nearest entity Reply with quote

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.
Back to top
View user's profile Send private message
Spike



Joined: 05 Nov 2004
Posts: 944
Location: UK

PostPosted: Fri Jan 18, 2008 6:26 pm    Post subject: Reply with quote

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.
_________________
What's a signature?
Back to top
View user's profile Send private message Visit poster's website
Preach



Joined: 25 Nov 2004
Posts: 122

PostPosted: Fri Jan 18, 2008 10:47 pm    Post subject: Reply with quote

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.
Back to top
View user's profile Send private message
Orion



Joined: 12 Jan 2007
Posts: 414
Location: Brazil

PostPosted: Fri Jan 18, 2008 11:21 pm    Post subject: Reply with quote

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:

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:

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;
      }
   }
};

_________________
There's no signature here. Stop looking for one.
Back to top
View user's profile Send private message
Sajt



Joined: 16 Oct 2004
Posts: 1026

PostPosted: Sat Jan 19, 2008 1:02 am    Post subject: Reply with quote

Quote:
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;
_________________
F. A. Špork, an enlightened nobleman and a great patron of art, had a stately Baroque spa complex built on the banks of the River Labe.
Back to top
View user's profile Send private message
Orion



Joined: 12 Jan 2007
Posts: 414
Location: Brazil

PostPosted: Tue Jan 22, 2008 4:11 pm    Post subject: Reply with quote

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.
_________________
There's no signature here. Stop looking for one.
Back to top
View user's profile Send private message
Preach



Joined: 25 Nov 2004
Posts: 122

PostPosted: Tue Jan 22, 2008 5:36 pm    Post subject: Reply with quote

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.
Back to top
View user's profile Send private message
Spike



Joined: 05 Nov 2004
Posts: 944
Location: UK

PostPosted: Tue Jan 22, 2008 6:39 pm    Post subject: Reply with quote

something like:

(warning unreadable version!)

Code:

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);

Quote:

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.
_________________
What's a signature?
Back to top
View user's profile Send private message Visit poster's website
Orion



Joined: 12 Jan 2007
Posts: 414
Location: Brazil

PostPosted: Tue Jan 22, 2008 10:32 pm    Post subject: Reply with quote

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:

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;
};

_________________
There's no signature here. Stop looking for one.
Back to top
View user's profile Send private message
Sajt



Joined: 16 Oct 2004
Posts: 1026

PostPosted: Wed Jan 23, 2008 1:15 am    Post subject: Reply with quote

Yup, that looks about right. But if you want to use the optimization discussed above (though it won't cause a noticeable framerate improvement Razz), change this
Code:
dist = vlen(head.origin - self.origin);

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

With delta declared earlier as a local vector.
_________________
F. A. Špork, an enlightened nobleman and a great patron of art, had a stately Baroque spa complex built on the banks of the River Labe.
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Inside3d Forums Forum Index -> QuakeC Programming All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2004 phpBB Group