Index | FAQ | Search | Memberlist | Usergroups | Profile | Log in to check your private messages | Log in | Register

Finding a nearest entity

| Inside3d Forums Forum Index -> QuakeC Programming

View previous topic :: View next topic
Author | Message
--- | ---
Orion Joined: 12 Jan 2007 Posts: 414 Location: Brazil |

Posted: Fri Jan 18, 2008 3:43 pm Post subject: Finding a nearest entity |

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 |

Dr. Shadowborg Inside3D Staff Joined: 16 Oct 2004 Posts: 726 |

Posted: Fri Jan 18, 2008 4:24 pm Post subject: Re: Finding a nearest entity |

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 |

Preach Joined: 25 Nov 2004 Posts: 122 |

Posted: Fri Jan 18, 2008 5:31 pm Post subject: Re: Finding a nearest entity |

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 |

Spike Joined: 05 Nov 2004 Posts: 944 Location: UK |

Posted: Fri Jan 18, 2008 6:26 pm Post subject: |

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 |

Preach Joined: 25 Nov 2004 Posts: 122 |

Posted: Fri Jan 18, 2008 10:47 pm Post subject: |

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 |

Orion Joined: 12 Jan 2007 Posts: 414 Location: Brazil |

Posted: Fri Jan 18, 2008 11:21 pm Post subject: |

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 |

Sajt Joined: 16 Oct 2004 Posts: 1026 |

Posted: Sat Jan 19, 2008 1:02 am Post subject: |

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 |

Orion Joined: 12 Jan 2007 Posts: 414 Location: Brazil |

Posted: Tue Jan 22, 2008 4:11 pm Post subject: |

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 |

Preach Joined: 25 Nov 2004 Posts: 122 |

Posted: Tue Jan 22, 2008 5:36 pm Post subject: |

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 |

Spike Joined: 05 Nov 2004 Posts: 944 Location: UK |

Posted: Tue Jan 22, 2008 6:39 pm Post subject: |

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 |

Orion Joined: 12 Jan 2007 Posts: 414 Location: Brazil |

Posted: Tue Jan 22, 2008 10:32 pm Post subject: |

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 |

Sajt Joined: 16 Oct 2004 Posts: 1026 |

Posted: Wed Jan 23, 2008 1:15 am Post subject: |

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

Display posts from previous:

| 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