Scan for enemy in RTS ?

[Raul]

I need an answer for a local competition in my country. We have to make a RTS game.

There are 2 Teams. The user is team 1 and the AI is team 2. Let's say I have an unit somewhere on the map. My unit has to scan if there is any enemy near it in order to shoot it.

So for every unit that is mine i call this:

Code:

For U2 = 0 To MaxUnits
    If Unit(U2).Team = 2 Then 'this means is enemy
       If GetDistance (Unit(U).Pos, Unit(U2).Pos) < 700 Then
          MyUnit.Enemy = U2 'and after this i have the code for shooting.. etc
       End If
    End If
Next U2

The problem is that I have to loop through all units multiple times because I told you that I call that code for every unit I have. so if I have 50 units and enemy has 100, for every 50 units i have i will loop through 100 enemys... This just simple kill my proc.

Is there another way to do that ?

[ZaPPZion]

maybe you can divide the coordinates in parts. So for example soldier 1 is standing at (100,100,100), which is for example part 21. He then checks every soldier that's in the following parts: 12,11,10,20,21,22,32,31,30. That means he's checking just 9 parts, which will probably have a lot less man.

12 22 32
11 21 31
10 20 30

Another solution might be to give soldiers a squad. Every group of soldiers that is running somewhere, will be grouped into a squad. This means that you just have to check which squad sees what other squad. When there's a lonely soldier, he forms a squad of his own, so if you have 200 lonely soldiers, your processor is going to get killed. Maybe there's a smart solution for this.

A combination of these solutions will probably work better, but it's hard enough just coding one i think. I don't know what your timelimit is, so you'll have to decide;)

[micmanos]

The following is pseudocode that hopefully will help you with faster / optimized distance checking between multiple objects.

The key concept is to only calculate the distance between 2 objects IF at the next frame there is a possibility of them coming in range. This method requires you knowing the distance each object can travel in maximum speed at a time of 1 msec.

If the loop discovers that at the next frame, 2 objects might have a distance that is within your defined weapons range, then a flag goes up and their distance will keep getting checked until they're out of range again.

If the loop discovers that 2 objects cannot come in-range in the next frame, then it calculates the minimum time required for them to come in range and only re-checks their distance after that time has elapsed.

Good luck and i hope this have been helpful ....

Code:

    Public Const MAX_ENEMIES As Integer = 100
    Public Const MAX_FRIENDLIES As Integer = 50

    Public Structure struEnemy
        Dim Enabled As Boolean  'This enemy exists.
        Dim MaxSpeed As Single 'The maximum speed in terms of world units / msec.
        Dim Dist As Single 'Distance from friendly.
        Dim dt As Single 'The time that must elapsed before the distance is checked again.
    End Structure

    Public Structure struFriendly
        Dim Enabled As Boolean 'This friendly exists.
        Dim Enemy(MAX_ENEMIES) As struEnemy
        Dim MaxSpeed As Single 'The maximum speed in terms of world units / msec.
    End Structure
    Dim Friendlies(MAX_FRIENDLIES) As struFriendly

    'The weapon range distance .... in terms of world units.
    'Within this range, the distance calculation will occur.
    Public Const WeaponRange As Single = 1



    Public Sub sLoop()

        t_midterm = TV.accurateTimeElapsed
        Do
            t = TV.accurateTimeElapsed
            t_midterm = (t_midterm + t) / 2
            Dist_threshold =

            For i = 0 To MAX_FRIENDLIES
                'Only check if the friendly exists (or it's not dead).
                If Friendlies(i).Enabled = True Then
                    For j = 0 To MAX_ENEMIES
                        'Only check if the enemy exists (or it's not dead).
                        If Friendlies(i).Enemy(j).Enabled = True Then
                            'Subtract the elapsed time from the timer counter.
                            Friendlies(i).Enemy(j).dt -= t
                            'If the time remainning to check for distance is less than the time required
                            'for those 2 objects (enemy & friendly) to come within range of each other
                            'then calculate the distance between them.
                            If Friendlies(i).Enemy(j).dt < t_midterm Then
                                Friendlies(i).Enemy(j).Dist = .......math........
                                'Calculate the maximum distance that both (enemy & friendly) can cover a (t_midterm) time.
                                Speed_threashold = Friendlies(i).MaxSpeed + Friendlies(i).Enemy(j).MaxSpeed
                                Dist_threashold = Speed_threashold * t_midterm
                                'If the distance is within the (WeaponRange) ...
                                If Friendlies(i).Enemy(j).Dist < Dist_threashold Then
                                    'recheck their distance in the next frame
                                    Friendlies(i).Enemy(j).dt = 0
                                    '
                                    ' PLACE CODE TO SIGNAL THE ENEMY & FRIENDLY THAT THEY'RE WITHIN WEAPONS RANGE.
                                    '
                                Else
                                    'Based on the distance, set a timer to recheck their distance after that time.
                                    Friendlies(i).Enemy(j).dt = Speed_threashold / (Friendlies(i).Enemy(j).Dist - Dist_threashold)
                                    '
                                    ' PLACE CODE TO SIGNAL THE ENEMY & FRIENDLY THAT THEY'RE OUTSIDE WEAPONS RANGE.
                                    '
                                End If
                            End If
                        End If
                    Next
                End If
            Next
        Loop

    End Sub

[Raul]

my problem is when i calculate the distance. i have 100 friendly units and 100 enemys. if i just make the loop. every friendly unit go through every enemy unit i have 60 FPS, but when i calculate the distance... 11 FPS

i do not have enough time to implement micmanos code, because i have to remake my unit structure.

@ZaPPZion: in order to do what you said i have to know who's near my units and is almost like calculating the distance for every enemy, because i cannot know how many of them are near my units... 

I am wondering if there is another solution for this issue??

[micmanos]

if i just make the loop. every friendly unit go through every enemy unit i have 60 FPS, but when i calculate the distance... 11 FPS  

First, let me ask, what formula are u using to calculate the distance?
Second, the code i've given you is designed to eliminate distance calculations that have no meaning ...... 

i do not have enough time to implement micmanos code, because i have to remake my unit structure.

I think that the code seems much more confusing than it really is and it's really the best that i can think of right now .... maybe another member has some other pointers?

[Raul]

i used Maths.GetDistance2D to calculate the distance.

[Dragoon]

I've got 2 suggestions

First, split your your units array into 2 arrays 'Enemies', and 'Friends' (and for every 'Enemy', calc distance for that enemy with every "friend")

Second, try (pseudo code)
(fpos.x - epos.x) * (fpos.x - epos.x) + (fpos.y  - epos.y) * (fpos.y - epos.y) + (fpos.z - epos.z) * (fpos.z - epos.z) < 490000

instead of:
GetDistance (fpos, epos)
(fpos = friend position, epos = enemy position)

notice that 490000 == 700 * 700
this eliminates the need of the sqrt function (which I think GetDistance uses )

btw, another idea just popped up, which might work (never tested it though)

calc the distance for every unit to a certain point in you level (I think one of the corners of your level is your best choice)

then, when 'checking' enemies against friends, substract eachothers distances to that point, and if that results in a value < 490000, calculate the actual distance between the two, and check again.

you can optimize this further by taking into account the angle between that 'certain point in your level' and the unit's position...

but I've never tried that idea/'theory' before, and I don't know how much time you want to spend on this issue, so it might not help at all.

I'm going to make a proof of concept when I've got some more time on my hands though... just to satisfy my curiosity... at least... I hope I so :p


edit:
if you whant the distance between 2 units in 2D, use (fpos.x - epos.x) * (fpos.x - epos.x) + (fpos.z - epos.z) * (fpos.z - epos.z) < 490000 (leave out the y part)

[Raul]

@Dragoon: i will try both methods. hope that using that formula code will be faster than GetDistance.

[petroz]

Dragoon is right.

To reduce the overhead for distance calculations involving many objects:

Try to eliminate the square root where ever possible. finding the nearest object should invlove no square roots.

Another thing to think about is how important response times are. Does it matter if the reaction times are delayed by 100ms? probably not. Putting in some kind of limiter so that you don't iterate over the all friendlies and all enemies every frame might free resources to do more important things.

That 'formula code' is faster than GetDistance.

The second idea probably wont work too well...

Code:

Counter-example:
referencePoint = ( 0, 0)
objectPosition = (10, 0)     ->   distance to reference point = 10;
testPosition   = ( 0,10)     ->   distance to reference point = 10;

10 - 10 = 0 [that means they're near each other?]

...but it's good to explore new ideas.

[Raul]

I resolved this problem. I used the formula and I make the calculations every 30 frames
Thanks to all.

[ZaPPZion]

hmm that's a good option i think
you could do it a bit different as well. The first 50 soldiers you make are group1, and they are doing calculations every 30th frame (1, 31, 61). The second group of soldiers do it at every 30+10th frame (11,41,71). The third do it at (21, 51,81).
That would steady the framerate a bit i think. If your checking it every 30 frames, and someone would have a framerate of like 15, then it would check every 2 seconds in your method, but in mine, it's calculation 3 times per 2 seconds, but it's calculating less, so it would seem to be calculating nonstop.

[Jstinnell]

I was looking for a similar solution but neva got to the point on finishing it.
The problem I had is where I create a bunch of chatacters and then have triggers and events all over my level and assign them to a specefic character within my editor.

For ex:
if
[oject{character1}] [triggertype{inarea}] [areaname]
then
[object{character2}] [eventtype{followpath}] [pathname]

For each character on a level to check whether and wich trigger it triggered and then doing the event was a mess and droped the frames drastically.I hope I will get it right now

[Dragoon]

The second idea probably wont work too well...

Code:

Counter-example:
referencePoint = ( 0, 0)
objectPosition = (10, 0)     ->   distance to reference point = 10;
testPosition   = ( 0,10)     ->   distance to reference point = 10;

10 - 10 = 0 [that means they're near each other?]

you're right, but the botomline of my 'method' is to reduce the amount of actual distance calculations (x*x + ... ) by trying to 'guess' the distance between the objects.


so, in the case you pointed out, they 'could be' near eachother, you should calc the distance between the two objects to determine if they really are near each other.

in other cases like (stealing your format here )

Code:

referencePoint = ( 0, 0)
objectPosition = (10, 0)         ->   distance to reference point = 10;
testPosition   = ( 0,300000)     ->   distance to reference point = 300000;

10 - 300000 = -299990 [clearly not close to each other, if it's out of the 'shooting' range, you shouldn't ceck the distance between the two]

so, in some cases it creates a (lot?) of overhead, and in some cases, it could saves you from doing some distance calculations.

however, the question remains, if the overhead isn't actually worse than to just 'get over it, and do the dang distance calculations'

but again, untested, never implemented, etc. etc. :p

...but it's good to explore new ideas.

Amen

[GD]

I'd perform a sphere based collision in space partitioned map. RTSs are great to implement grid space partioning. You can check out my implementation of kd-tree collision detection TVSM.

[Lordtek]

if your talking about a small amount of players say 200 - 400 i might have your answer.
1. create a struct / type list that can contains
     a. a double var for the distance for your 2d or 3d coords
     b. a byte var that designates enemy friend neutral or whatever
     c. a var for the number
     d. a var for the index.
2. do a quicksort of the distance
3. using the index you can go up and/or down to find the closest people within say weapons or visual range.

[Raul]

well.. right now my game is almost finished. i will not make any other modification. after the competition will be finished i will put here all the source code.