Finding nearest Image in a certain range

[Imp Midna]

I have a bleeding-system set up in which bleeding units leave blood trails (images) while bleeding. Specific units (blood hounds) should be able to find and follow these trails once they get into a certain range.

Now, for this, i need a way to determine the nearest blood image to each blood hound patrouling around. Since many units can bleed at the same time, and many blood hounds can be roaming around, i would prefer not to use a O(n*m) algorithm for this, but im not sure how to do that.

Once way would probably be a quadtree, but i fear that it would degenerate quickly since most images will be very close to each other (its a blood trail after all).

Another way might be to put a dummy unit on every image and let natives (such as pick every unit in x range or the units gets in range event) do the job of finding the nearest image in a certain range. Then again, warcraft 3 doesnt typically behave too well with many units on the field.

What would be the better option? Or are there any other methods i have missed?

 

[Ardenian]

Make/Use a very simple model, like a square, then use the blood image as a skin and use a unit instead of an image.

For the trails, maybe you could index them, so units coming in range of a certain blood trail are ordered to follow the following ones via index.

Using hahstables you could define the trails for every specific unit due to the unique Id each unit has.

 

[DeadZero]

You could use a point variable array and/or a hashtable like Adrenian suggested to store the points of the blood trail spots,
Then Pick Every Unit in (Bloodhounds) and do For Each point in the array check the distance between that point and Picked Unit
If the distance is less than a certain amount (how far they can smell), then save it as (closest_point)
If a closer point is found, save that as (closest_point)

You could also use this to store the second closest point. Always being ordered to the second closest point would make the bloodhounds 'follow' the trail

 

[Zwiebelchen]

Guys, he asked for a solution that isn't O(n²)...

Yes, a quad-tree would work, but it is probably overkill for what you are trying to achieve. Your JASS overhead will probably kill all performance gains that your quad-tree will provide. Remember that normal unit enumerations internally already use binary trees!


@TO:
Here's how I would do it:

- create linked lists called "blood trail" (a blood trail, in fact, is a prime example of a linked list in real life)
- the "blood trail" members are basicly the "blood" splats
--> this allows easy "following" of blood trails just by using .next() or .prev() on the linked list structure at O(1) once a hound is "locked on"
- Divide your map into squares of known size (ideally matching the range of your bloodhound scouting) - store all "blood" objects indexed by the square they are in in a table
- perform distance checks only for the squares the bloodhounds are in and all 8 adjacent squares (to avoid corner cases)

Now, technically, this method is still O(n²), (number of bloodhounds * number of blood splats) however, as you basicly only loop through the square each bloodhound is in (and all adjacent squares) you exclude huge parts of your map from the calculation, effectively reducing this to O(n) (assuming an infinitely sized map).


So what this approach does is it hashes all blood images to avoid pointless enumerations. Oh, and definitely don't use units for the blood.


Now, remember: I assumed in my concept that there are way more blood trails than blood hounds. The solution will be completely different if at average the number of blood hounds exceeds the number of blood trails. In this case it would be easier to just loop through the trails and enumerate the dogs in range.

 

[DeadZero]

Ah yes, simply splitting the map into a grid where 1 = The bloodhound's smell range is a good solution,

Guys, he asked for a solution that isn't O(n²)...

Though there was no good reason to dismiss brainstorming of which some is required in certain parts of the trigger anyway

perform distance checks only for the squares the bloodhounds are in and all 8 adjacent squares

 

[Imp Midna]

Now, remember: I assumed in my concept that there are way more blood trails than blood hounds.

Indeed.

Oh, and definitely don't use units for the blood.

Mind elaborating on this? Being able to use the enum functions seems like a good way to get around this problem (so much so that you recommended it in case where we have more bloodhounds). Maybe items or destructibles could help if units come with too much overhead? (though i would like to avoid destructibles in fear of hitting the limit)

Apart from that, sounds like a good idea (and much easier to implement ).