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

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

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

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

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.

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

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

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]

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

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

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

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