Archived

This topic is now archived and is closed to further replies.

EnochDagor

Basic AI Functions

Recommended Posts

Ok, imagine having 2000 objects in a given environment. All 2000 objects have the POTENTIAL to fight each other. I need some ideas or even some articles on the FASTEST way to determine when one object is in agro range of another object. For those unsure of what agro range is: Agro range means the distance before an object will engage a hostile object. Agro range is some arbitrary number based on attributes of that object. But for ease and simplicistic reasons, we''ll simply call it radar range. Some things to consider: 1) The radar range is a radius around the object. 2) All objects can move. 3) This is in a 2D coordinate plane 4) For now, assume I have no terrain or outside variables, simply distance from target One last caveat... I need to be able to determine this information EXTREMELY quickly. If you need further clarification, please let me know. Thanks in advance. -Enoch

Share this post


Link to post
Share on other sites
If they were all the same range, you would only need to do one comparison between each pair of objects. If they have different ranges, you need to do it bi-directionally (i.e. A-B & B-A) and you end up with 2000 * 1999 comparisons. With the former situation, the first object would need to be compared to 1999 objects, the next would be compared to 1998, the 1500th object would be compared to 499 objects, etc. It cuts things down significantly. One optimization for the bi-directional comparisons is to do them sequentially so that you only need to calc the distance between A and B once.

One way of dicing things down is to subdivide the map into chunks. Let''s say your map is 100 x 100 tiles and the max radar range is 10. If you were to dice the map into 10x10 grids, you know for a fact that a unit could only possibly detect units in it''s own grid or the 8 grids surrounding it. Therefore, you create a way of calculating and storing what grid each object is in, and for each item, you just pull an active list of the objects that are in the surrounding grids. You only need to create this list once per sector, so it further optimizes the search if you process the items on a per sector basis... that is, all the items in (1,1), then (1,2), etc.

Dave Mark - President and Lead Designer
Intrinsic Algorithm -
"Reducing the world to mathematical equations!"

Share this post


Link to post
Share on other sites
typedef list oblist;

oblist myobs;
oblist tempobs;

// fill in yer oblist

tempobs = myobs;

oblist::iterator T = tempobs.begin();
bool cont = true;
for(oblist::iterator I = myobs.begin(); I != myobs.end(); ++I)
{
while(cont)
{
if((I != T) && ((*I)->coords - (*T)->coords).Magnitude() <= (*T)->QueryAggroRange()) )
{
(*T)->SetAggro(true);
tempobs.pop_front();
T = tempobs.begin();
cont = false;
}
else
{
++T;
}
}
}


What this does is sets up 2 lists to compare... myobs is the list of your objects and tempobs is a list we make that we can modify... the loop will start with the first ob in myobs(I) and then go through comparing that with each ob in tempobs(T). When we find a guy close enough to make T aggro, we set his aggro flag on then remove him from the list. We want him to stay in myobs cuz he can still turn others aggro if he is close enough to him. I don''t know if this is fastest, but will stop from doing redundant checks against people already turned aggro...

Fox''s suggestion will save time, but you can come into weird edge cases when breaking things into sectors like that... 2 guys can be right on the edge of a chunk, one on one side, the other on the other side... their actual distance between could be 0.001 but since they are in different chunks, they won''t be compared... just keep that in mind if you decide to do the division method, cuz you might have to compare a chunk with all chunks around it also...

Share this post


Link to post
Share on other sites
Yes,
I agree with the method where the terrain is splitted into multipule sectors. It is how I have my map setup so that I can do very fast frustrum culling... In your case just make each sector as big as the biggest argo distance... then check all objects in each sector to the other objects in the same sector as long with the oned in the adjecent ones.

This should dramatically reduce the number of comparisons bieng made.

Dwiel

Share this post


Link to post
Share on other sites
I had thought of sectors before... thanks for refreshing my memory on it. I will reevaluate those ideas.

To answer the question, yes, the objects have varying radar ranges.

Other than the sector/grid idea, what other methods are there?

-Enoch

Share this post


Link to post
Share on other sites
A way of helping to deal with the different radar ranges is to reparse the field for the different ranges. That is, in my previous example, the range was 10 and the grids were 10. If there are units that have a range of 5, divide the map into grids of 5 and then process THAT type of unit. Obviously, it would be inefficient to do this if you had many different ranges. The other option is to just do the bi-directional comparison that I mentioned earlier and just eat the fact that many of the 5''s will never be able to see a 10 that it is being compared to. The advantage of this is still that you only calc the distance once for each pair.

Dave Mark - President and Lead Designer
Intrinsic Algorithm -
"Reducing the world to mathematical equations!"

Share this post


Link to post
Share on other sites
This problem has been attacked in the statistics/machine learning field (for k-nearest neighbors) using k-d trees. I don''t have any specifics handy, but an online search should be easy enough.

Share this post


Link to post
Share on other sites
before u divide the object into MAP_SIZE/MAX_RANGE u should see if any object is on the central point of the sector,if it is true then, u only have to compare this object with the objects in the same grid instead of compare with other around grids.

:D

_,,,^Ó..ò^,,,_

Share this post


Link to post
Share on other sites
Well, unfortunately, every object I have has a different radar range. There is a max range set by me. But each object contains its own range. Furthermore, they are not cookie-cutter objects... each object is a unique object with its very own range.

So for example''s sake, assume that all ranges are different.

Right now, I am forced to do two loops.

For each object
For each object
Is Object(Y) In range of Object(X)?
Object(X).Aggro
Next
Next

I have to do it this way because I can''t assume that Object(Y) KNOWS that object(X) has aggroed unless Object(X) is in range of Object(Y).

Now I can reduce this further by checking both ranges at once which reduces my distance calculations and simply checking if I''ve checked this pair before (like has been suggested already).

Gridding could work. It reduces the amount of checks I have to make. I can already limit it via sector (the game is divided into zones/sectors) which may fix my problem altogether.

I will look into KD Trees and I will be buying that AI Techniques book to try to jog my memory.

I realize that by having all objects with different ranges, things get real nasty, real quick. Hence why I''m posting here.

-Enoch

Share this post


Link to post
Share on other sites
"...and I will be buying that AI Techniques book to try to jog my memory."

My book doesn''t delve into spatial partitioning algorithms, so don''t buy it looking for answers to this specific problem... you''ll be disappointed!

"I realize that by having all objects with different ranges, things get real nasty, real quick"

It doesn''t make much difference with some of the methods I''ve mentioned

My Website: ai-junkie.com | My Book: AI Techniques for Game Programming

Share this post


Link to post
Share on other sites
i think that the division map theory can func with ur different object ranges,divide the map by the MAX_RANGE.the MAX_RANGE are a variable value that have the value of the range of the object with biggest range.

_,,,^Ó..ò^,,,_

Share this post


Link to post
Share on other sites
Fup: I looked through your book and came to the same conclusion. However, I will be returning to B&N tonight to do some more research. I am also still researching those methods you indicated.

KosmiC_Khaoz: I''m not discounting your thoughts on this issue. However, I am trying to get some other options, as well.


At this point in time, I wanted to put this process on the server of my engine... however, more and more, I am leaning towards putting the process on the client and relaying information to the server. Both has its pros and cons. However, both require that the process is absolutely streamlined.

-Enoch

Share this post


Link to post
Share on other sites
quote:
Original post by Predictor
This problem has been attacked in the statistics/machine learning field (for k-nearest neighbors) using k-d trees. I don't have any specifics handy, but an online search should be easy enough.



I recently implemented a fast k-d tree library for Matlab (written in C++). Unfortunately I cannot share the code with you as it is part of a copyrighted program I've developed for work, however I would be happy to offer any advice for implementing a k-d tree, if you should choose to go in that direction.

To spell out what a k-d tree does...

A k-d tree is a binary tree implemented in k dimensions, such that at any given node in the tree, the left and right subtrees below that node represent the left and right partitions of a given dimension (variable). The dimension to be partitioned at any given level is chosen according to some measure (usually the dimension with the largest variance in the data values of all items to be sorted in the tree). The partition value (key) can be anything you like, although typically it is the median value of the data in that dimension at that level. Unlike the quad-tree, or the oct-tree, splitting doesn't rotate through dimensions. The splitting order of dimensions depends on the variability in the data as described above.

Once you've created the k-d tree, you can use it to efficiently perform a nearest neighbour search, whereby you can recall from the tree the m nearest neighbours of a query item. For your problem, you would probably want it to return all neighbours within a given radius, which is a trivial modification of the nearest neighbours algorithm.

Personally though, unless you need to partition your space for some other reason (like frustrum culling, object collision, etc) then I wouldn't utilise a k-d tree. The reason being that you will need to rebuild your tree whenever the objects move.

A more efficient method is to store an n-dimensional array (intialised to zeros), where n is the spatial dimension of the domain. There are as many rows as columns and as many columns as there are things in the world that you want to sort. When you initialise the world, sort the dimensional data for the locations of the things. Now, taking the first dimension of the matrix (rows for example) assign each thing to a row of the matrix based on the sort order. Then take the second dimension and assign things to columns based on the sort order of that dimension. Continue for each dimension until each thing occupies a single cell. Put a 1 in that cell. Now every thing in your domain is sorted on each of its spatial dimensions. For each thing that you want to find the neighbours of, find its location in the matrix. Then start checking neighbouring cells for other things and check whether they are 'in range' or not. Do this for each cell that has a 1 in it. Stop checking when the range to the neighbour in each dimension exceeds the distance criteria for your check.

When objects move, you don't need to do a complete resort of the arrays. You just need to check whether an item has moved past one of its neighbours in the sense of the dimensional sort. If it has, then swap the two things in that dimension only. How much swapping goes on depends on how fast things move with respect to the time step in your engine.

Given a large number of objects, this sort array can be quite large. In which case, you can get smart and implement a sparse array class that will save you heaps of memory (pun intended)!

Cheers

Timkin

[edited by - Timkin on July 28, 2003 10:38:54 PM]

Share this post


Link to post
Share on other sites
quote:
Original post by EnochDagor
All 2000 objects have the POTENTIAL to fight each other.
2) All objects can move.
I need to be able to determine this information EXTREMELY quickly.



Maybe i''m just all slow bus and safety helmet on this one, but what exactly does fast mean? Right now, with the way computers are, you can do some really inefficient stuff super quickly. As examples, i wrote a brute force weighted k-nearest neighbor search that appears instantaneous (not too surprising) and a text file trigram analyzer that does file i/o, denoising, porter stemming and the like, does bigram and trigram counts and sorts, was written in java and was in no way optimized and four years ago it was also near instantaneous. So i guess the question is, are you really having performance problems right now?

i''m also a bit surprised no one mentioned the really obvious (at least to me) solution. While i''d certainly use cell partitioning (i like hierarchies of grids), you get more speed from (hmm, let me think of a fancy dime word way of saying this) time interval delta processing. Yeah, that''s pretty good!

Pulling once again from my psychology books on how humans deal with issues like this, the human mind is hard wired with a little rule that says objects move in a direction at a given speed and do not just randomly teleport around. Further, give that speed, you know just how far they can move when you''re not paying attention to them. That''s what controls how frequently you check your rear view mirror and how long you feel safe staring at the radio

So let''s say you have some expensive 2,000 way computation at the begining. Each object now knows who is close, who could be close next time step if they ran at max speed towards you and who won''t be an issue for quite a while

On the time step where someone moves, only compute calculations for those people who move. Bot 1,698 moves 2 meters north. Bot 1698 knows who was definitely in range, who was definitely out of range and those 2 groups of people who hover on the edge (people currently in range but could leave and those out of range who could enter). So when Bot 1698 moves, he only checks those bots straddling the border. Only process those people who have moved and ignore everyone else. Selective attention

Now, this all ignores the question i have in my mind which is, when would this ever happen? If this were gladiators in a collesium, their line of sight would be limited as would the number of objects they could track. So each agent would keep a list of those objects it pays attention to and on each movement you could either gain an object, lose an object or have one object replace another. After, say, 9 objects, you just stop tracking, get overwhelmed and become "hypervigilant" where you just focus on the 2-3 closest ones

In the animal world, a cheetah attacking a herd of 2,000 zebras picks one and then focuses solely on it, never noticing any one else, never transfering targets. Cognitively, it''s easier

Anyway, that''s my two cents

-baylor, who is practicing his big words today

Share this post


Link to post
Share on other sites
To follow up on Baylor, here... the width of the "border" area would have to be determined by the maximum closing speed of the primary object and the fastest unit in the game. That is, if I can travel 2 meters but there is a unit out there that can travel 10, my "border" area needs to be 12. However, if all units move 2 meters, my border only needs to be 4. Of course, the tricky part, which really only delays the initial problem, is determining who is in your "border" area from turn to turn. In the end, you still end up having to check many units.

Dave Mark - President and Lead Designer
Intrinsic Algorithm -
"Reducing the world to mathematical equations!"

Share this post


Link to post
Share on other sites
At this point...

in pseudo-code...

for each object in zone
if object.bMoved
DetermineAggro(object)
next

DetermineAggro(theobject)
{
for each object in zone
if distance from theobject to object <= theobject.range then
theobject.SetAggro(object)
if distance from theobject to object <= object.range then
object.SetAggro(theobject)
next
}


That''s what I have at the moment. I feel it is not nearly as optimized as it could be. Dividing the zone further may help but I''m not sure it will at this point. Also realize that the application maintains several zones (probably maxed out at about 256).

Each zone can have moving objects, etc...

Anyway, I like some of the options offered here as my pathing engine will be coming up soon and I may need to refer to some of these suggestions for that.

Finally, if you have optimized code examples that you can show me, please post them as anything may joggle my thoughts to the right direction.

Thanks,

-Enoch

Share this post


Link to post
Share on other sites
I can''t offer any new and ground breaking algorithms for you to try, but I would like to point out the difference between a quick mathmatical algorithm and a quick code algorithm. There are some really nice mathmatical designs out there, but if they take more clock cycles to complete than a less elegant approach, then they''re only quicker on paper.

I believe the best approach in this instance (if you have the time) is to plug in 3-4 different algorithms and profile them - see which does the job with most time to spare.

Remember - optimisation in this case is going to be about minimising the number of objects you check within reason, not necessarily doing the very bare minimum possible. Depending on how important accuracy is you could save a lot of time using probability rather than exact measurements -

e.g.
Why do trig lookups for calculating distance? Just a waste of clock cycles. For really coarse checking using a square agro range; for more fine tuning use the fact that if dx and dy are very close and both greater than (aggroRange/sqrt(2)) then the object is outside aggro range (probably ) That effectively gives you an aggro octagon (ish)

I''m presuming here that each objects aggro range - whilst different from other objects - is fixed. You can store this approximation alongside the actual aggro range, and if it does change, well it''s only one fdiv operation and a save back to memory.

As for minimising the objects you test - I would section the playfield into MX_AGGRO_RANGE grids and do as someone else advised.

Avoiding bi-directional checking? Pick two objects, choose the object with the *smallest* aggro range. If it aggros against B, then B can automatically aggro against A. If not, you have another test to do, but ypu were gonna do that anyway.

Hmm - sorry for the length. I waffle......

Share this post


Link to post
Share on other sites
"To follow up on Baylor, here... the width of the "border" area would have to be determined by the maximum closing speed of the primary object and the fastest unit in the game. That is, if I can travel 2 meters but there is a unit out there that can travel 10, my "border" area needs to be 12. However, if all units move 2 meters, my border only needs to be 4. Of course, the tricky part, which really only delays the initial problem, is determining who is in your "border" area from turn to turn. In the end, you still end up having to check many units"

You also have to add in each object''s bounding radius...

My Website: ai-junkie.com | My Book: AI Techniques for Game Programming

Share this post


Link to post
Share on other sites