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

Does the agro range vary from unit to unit or does it remain constant? For example, does Unit A have a different agro range than Unit B?

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!"

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

Ah, fox mentioned also needing to check the grids around it... =) sorry...

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

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

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!"

Do a search for ''spatial partitioning'' and ''proximity query''.

There are numerous algorithms to chose from: cell-space partitioning (the grid idea mentioned by Dave), quad-trees, circle trees, sorted arrays etc.



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

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.