Collision Detection - Need optimization/faster method

[JayWalker]

Hey everyone, ive been working on a small space/rpg type game for the last week or so, and ive come to a pretty big problem. In my game i need to check for collisions between players/projectiles and player/pickups. the problem is there are (at least in the small demonstration version ive made so far) 999 players, 999 projectiles, and 999 pickups which need to be checked. the total number of loops alone in my collision detection sub is 998001 loops, with 2 fairly complex calculations per loop. At its current status, it takes about 2.5 seconds just to go through one loop on an Athlon 64 3700+ 2.2ghz cpu.

I need ideas/examples on a MUCH faster/more efficient way of checking for collisions. I check the distance between the objects in my game and subtract each radius because most of the objects in the game are circular, and those that arent are small enough to be considered so. so distance is an easy enough way of checking for collisions in this game at least.

here is my current sub for collision detection

Public Sub check_for_collisions()
'check for collissions between player/projectile and player/pickup
    Dim i As Integer
    Dim r As Integer
    Dim tempdist1 As Single
    
    For i = 0 To 999
        For r = 0 To 999
            'check player/projectiles
            tempdist1 = distance(player(i).x, player(i).y, projectile(r).x, projectile(r).y) - (player(i).radius + projectile(r).radius)
                If tempdist1 <= 0 Then
                    collision_player_projectile i, r
                End If
            'check player/pickups
            tempdist1 = distance(player(i).x, player(i).y, pickup(r).x, pickup(r).y) - (player(i).radius + pickup(r).radius)
                If tempdist1 <= 0 Then
                    collision_player_pickup i, r
                End If
        Next r
    Next i
End Sub

Im thinking i may just have to cut back to a max of 99 or so entities of each (player, station, projectiles and pickups even tho only projectiles and pickups are used in this sub (as well as players)) but i wanted to make this a very large scale game, with almost so many things to explore you would never be at the same place twice.

So, if anyone could help me that would be more than greatly appreciated.

Id rather not give the whole source to the game, but attached is a compiled version of what i have so far without collision detection enabled (so its actually playable XD). All that happens right now in the version attached is 999 of each type of entity is spawned, and fly in random directions (except for AI player (pirates, traders, police), they just have a simple AI which makes them follow you (or try to) around.

PS. In order to make it run, you need to put PBGL.dll in your c:\windows\system32 folder and then in start>run or command prompt type "regsvr32 c:\windows\system32\pbgl.dll". PBGL.dll is a "Picture Box Graphics Library" that i wrote to make it easier to do things with picture boxes like using transparent bitblt and other pretty simple drawing operations. Oh, and as i mention that i think it should be stated that all things in the game are rendered with bitblt.

PSS: when running the game please tell me the framerate you get (in the lower right hand corner of the window) and your pc specs (processor at least). I need to make sure my code to control the framerate is working right. It should be a constant 32, if it goes below 32 dont worry, its pretty demanding (yes, i need to work on it a bit more) but if it goes over 32 let me know because that would be another bug to fix...

[si_the_geek]

First off, anyone who runs the compiled files does so at their own risk. I will certainly not be trying it.


It's not 998001 as your loops go from 0 to 999 (1000 values!).

Do you always have 1000 players, 1000 projectiles, and 1000 pickups? If not, you should not be checking them all. You may need to split the inner loop into two (one for projectiles, and one for pickups), but the speed should improve.

For a start, dont have Distance as a separate sub; instead put the code directly into the loop. It takes time to call a sub, and you are currently calling it 2 million times! Based on my experience, this change alone should make it about 5 times faster.

The are also likely to be dramatic ways of improving the code that is currently in the Distance sub, but we obviously cannot tell yet.

[Fedhax]

First off, anyone who runs the compiled files does so at their own risk. I will certainly not be trying it.

Agree whole-heartedly!

The are also likely to be dramatic ways of improving the code that is currently in the Distance sub, but we obviously cannot tell yet.

From my limited experience with RPGs, the world--another way of wording "place where the character can hit/interact with stuff"--is usually broken down into zones or areas. If you play the latest Final Fantasy game, you'll notice that there are different areas, and in these areas, they are broken down into zones. If your game is a single player game--like Final Fantasy--then you are only doing collision detection for that player in a particular area with the objects showing up in the area. (Side Note: The RPG engines I've used usually store a picture (Map), a secondary layer on the picture (map area collision), and code to handle the player's location and how it interacts with the map (code/scripting) for each area, and this information is loaded only when the character enters those areas).

You could have multiple arrays--a single player() and multiple map/zone()--which would cut down on the crunching in the For loop. You could also add a Zone and/or Area ID value to your player UDT and object UDTs so your If() is checking to see if they are in the same zone, then it would handle your distance code--which others can review and help. If you do handle my zone/area idea, you would want to be able to sort the array by these values and maybe even include some zone/area pointers so you know where you can start in the loop and where to end.

Finally, you could also track which players have moved and only check those positions--"polling" if it was an online text-based MUD. If they haven't moved, at the least they can't have interacted with your stationary objects and would only have to check for the moving objects.

[JayWalker]

Ok, well no there are not/will not allways be 1000 objects spawned, so i have modified the sub as so, so it will only do the math for players/pickups/projectiles that are enabled (spawned)

Public Sub check_for_collisions()
'check for collissions between player/projectile and player/pickup
    Dim i As Integer
    Dim r As Integer
    Dim tempdist1 As Single
    
    For i = 0 To 999
        For r = 0 To 999
            'check player/projectiles
            If player(i).benabled = True And projectile(r).benabled = True Then
                tempdist1 = distance(player(i).x, player(i).y, projectile(r).x, projectile(r).y) - (player(i).radius + projectile(r).radius)
                    If tempdist1 <= 0 Then
                        collision_player_projectile i, r
                    End If
            End If
            'check player/pickups
            If player(i).benabled = True And pickup(r).benabled = True Then
                tempdist1 = distance(player(i).x, player(i).y, pickup(r).x, pickup(r).y) - (player(i).radius + pickup(r).radius)
                    If tempdist1 <= 0 Then
                        collision_player_pickup i, r
                    End If
            End If
        Next r
    Next i
End Sub

But it seems to have slowed it down more than help... even though i would think that would improve the speed at least slightly.

Also, here is the code in my distance function:

Public Function distance(x1 As Single, y1 As Single, x2 As Single, y2 As Single) As Single
distance = Sqr((((x2 - x1) ^ 2) + ((y2 - y1) ^ 2)))
End Function

I dont think there is much that can be changed there as that is the simplest way i know to do the distance formula. If it can be improved, please do share

PS: i have code in the game that lets me run certain subs only once every few frames, and when i have it running at half speed (collision detection sub at 16 fps, all the rest at 32) it still doesnt go over 0 fps. and when i have it set at 8 times a second (with the rest at 32) it will run fine for 8 frames, pause for a second (while it does all this math) and then continue to the next 8 frames where it pauses again... etc etc.

So i need some kind of algorithm that either can run 32 times a second on a fairly decent machine, because not everybody has a crazy fast $2000 machine to run an incredibly demanding 2d game on... or i need to be told to scale my world down a bit >.<

PSS: Fedhax, i read your post right after i got done typing this XD. The zoning idea sounds like it would definitelty help a lot, but I think i would probly have a good bit of trouble implementing it into my current engine without slowing it down even more, because my first though on this idea would be to only check collisions between objects that are a certain distance/area away from/around the main player (you) but that would just require me using distance a bunch more and slowing it down once again.

[Fedhax]

So i need some kind of algorithm that either can run 32 times a second on a fairly decent machine, because not everybody has a crazy fast $2000 machine to run an incredibly demanding 2d game on... or i need to be told to scale my world down a bit >.<

Big O Notation Time: Your implementation is N^2. As it is written, it will always be N^2 (Very bad if you aren't familar with concept of Big O Notation). If you want your world to have 999 players--NPCs? People?--and see if they are interacting with 999 objects and 999 "pickups", it can't be fixed. I've roughly outlined ways you can cut down your N from 999 to something more manageable (50? 100?), but if you don't want to look into those approaches, you are just going to have to throw brute force--aka CPU time--at the problem or downsize your world--which isn't all that unreasonable depending on your game and your desired results.

[Update]
Again, using Final Fantasy XII as an example: My character goes into the Giza Plains. The plains are broken down into 5-7 zones. In each zone, I will have at most/on average:

• 3 Friendlies
• 5-15 chests
• 5-10 mobs/NPCs (some of them may drop loot)

Using that scenario with your loop, the outer loop runs 3 times. The inner loop runs 10-25 times (max). If the people who spend 100 million USD (equivalent) on a game would do it that way, it says something about a possible solution to your problem.

[si_the_geek]

Good point

If you want to go with the current method tho, here are some tips of improving what you have:


Ideally you should have a 'gap' at the end of the arrays, where all the inactive (benabled = True) items are moved to, and store the "last used" position to a variable. You can then use this on the For lines instead of the 999's.

If you dont do that, you should at least move the "If player(i).benabled = True " to outside the inner loop - as none of the checks will be actually be done anyway. Running those unnecessary If's takes time.

The code in Distance can be improved dramatically - as there is no need for the Sqr function (which will be slow). This is because you are only comparing against 0, not a particular value. edit: misread that part of the code in a rush, you should remove the SQR and square the radius differences (eg: PlayerR + projectile(r).radius ^ 2) when you subtract - or better still, compare against that instead of subtracting and comparing against 0.

As it is only 1 line long, there is absolutely no reason to avoid putting it in-line (replacing the call to Distance with the actual code).

I can also see you are using bad data types - instead of Single you should be using Long, as it is much faster. Whether this is an easy change or not depends on the rest of the program.

Oh, and there is no reason for the = True in the If statements, as you are just checking if True = True, or (the answer is True - which is what the If or And use), or False = True, or (the answer is False - which is what the If or And use). eg: If player(i).benabled And projectile(r).benabled Then


Another speed improvement is using variables for the player properties (eg: player(i).y), and setting them just before the inner loop - then using the variables inside the inner loop. Variables are quicker that properties, so 2000 runs (2 checks for each loop iteration) will make a noticable difference.

[JayWalker]

Ok well, If i get rid of the N^2 and instead use

Public Function distance(x1 As Single, y1 As Single, x2 As Single, y2 As Single) As Single
distance = ((((x2 - x1)*(x2 - x1)) + ((y2 - y1)*(y2 - y1))))
End Function

would i get much of a performance increase? and the same answer? (im not too great at math so forgive me if i make some mathematical mistakes)

Also for my collision detection sub... si_the_geek were you thinking of something like this?: (also i believe this goes along with the distance modification above (removal of SQR))

Public Sub check_for_collisions()
'check for collissions between player/projectile and player/pickup
    Dim i As Integer
    Dim r As Integer
    
    For i = 0 To 999
        If player(i).benabled Then
            For r = 0 To 999
                'check player/projectiles
                If projectile(r).benabled then
                        If (player(i).radius + projectile(r).radius) ^ 2 >= distance(player(i).x, player(i).y, projectile(r).x, projectile(r).y) Then
                            collision_player_projectile i, r
                        End If
                End If
                'check player/pickups
                If pickup(r).benabled then
                        If (player(i).radius + pickup(r).radius) ^ 2 >= distance(player(i).x, player(i).y, pickup(r).x, pickup(r).y)  Then
                            collision_player_pickup i, r
                        End If
                End If
            Next r
        End If
    Next i
End Sub

I hope i didnt make any mistakes up there ^^

Also, i might put the formula there on the line with the whole sub as you said rather than go to it, but im trying to keep my code as clean as possible so i dont get confused but if i need to i will.

And I cannot use Longs in my game, as they round ie:

99.999 = 100 in long

99.999 = 99.999 in single

this is crucial to the movement/physics being accurate and things not moving WAY too fast.

and as far as assigning the variables in-loop rather than using propertys, i will probably do that, i just havent yet.

[si_the_geek]

I think you completely misunderstood Fedhax - you need to put the ^2 back in to Distance (it will give the wrong answer). He wasn't talking about specific code, he was talking about the "order of magnitude" of how long the code will take. For more info, see: http://en.wikipedia.org/wiki/Big_O_notation
If you want the code to be really fast, you need to change your program design completely.

The tips I am giving you will make this particular piece of code noticably faster (possibly 10 to 100 times faster), whereas Fedhax's will make the entire program (or at least significant parts) thousands of times faster - his example cut this sub down from 2 million checks, to about 75.


Your current version of Distance will give the wrong answer (you should only have removed SQR). The rest of the code is fine tho.

Also, i might put the formula there on the line with the whole sub as you said rather than go to it, but im trying to keep my code as clean as possible so i dont get confused but if i need to i will.

Do you want it to be quick? If so (as I have already said twice), this is very important. It will suddenly be several times faster, and the code will only be slightly more complex.

Try it out for yourself - like with the other things (such as using variables for "last used array element") it is fairly simple to see the time the sub takes, so you can see how much improvement each change makes.

And I cannot use Longs in my game... this is crucial to the movement/physics being accurate and things not moving WAY too fast.

Then change the other code.

If you care about speed, only ever use Long's (instead of your Integer variables too!), and change your methods to suit the data type.

Instead of having values of 99.999 etc, why not just multiply by 1000? (so you have 99999 etc).

[triggernum5]

This might have already been mentioned, but you don't really need to do any looping at all.. Create a 2D or 3D boolean array with one element for each possible location in your game/level/whatever.. Use the array to keep track of whether or not that coordinate space is currently "occupied" by anything.. If that area is not occupied then you can skip the checks..
You can also track what is on the area with another array that stores more data in the same array indices as your occupied matrix..
There are many ways to set up the arrays.. You could have separate ones for objects and ppl if you need.. You can use Collections or user-defined types to cut down on the number of arrays, and you may need to store a small array in each element to support more than one occupant.. In anycase this way you tax the memory more than the processor..

[JayWalker]

Ok, so now ive put the distance formula on the same line, and its noticeably faster, but still not near fast enough (it still takes about 2 seconds).

here is my current collision detection sub:

Public Sub check_for_collisions()
'check for collissions between player/projectile and player/pickup
    Dim i As Integer
    Dim r As Integer
    
    For i = 0 To 999
        If player(i).benabled Then
            For r = 0 To 999
                'check player/projectiles
                If projectile(r).benabled Then
                        If (player(i).radius + projectile(r).radius) ^ 2 >= ((projectile(r).x - player(i).y) ^ 2) + ((projectile(r).y - player(i).y) ^ 2) Then
                            collision_player_projectile i, r
                        End If
                End If
                'check player/pickups
                If pickup(r).benabled Then
                        If (player(i).radius + pickup(r).radius) ^ 2 >= ((pickup(r).x - player(i).y) ^ 2) + ((pickup(r).y - player(i).y) ^ 2) Then
                            collision_player_pickup i, r
                        End If
                End If
            Next r
        End If
    Next i
End Sub

And i tested it both ways, my current distance formula and the old one (both without sqr) and they give the exact same answer:

Public Function distance(x1 As Single, y1 As Single, x2 As Single, y2 As Single) As Single
distance = ((x2 - x1) ^ 2) + ((y2 - y1) ^ 2)
End Function
 
'is the same as 
 
Public Function distance(x1 As Single, y1 As Single, x2 As Single, y2 As Single) As Single
distance = ((x2 - x1) * (x2 - x1)) + ((y2 - y1) * (x2 - x1))
End Function

But which is faster?

PS: thinking about the while scheme once more, i could just combine the pickup type with the projectile type and simple have "ispickup as boolean" to determine what to do once collided... that would undoubtedly speed things up a bit.

[Fedhax]

Public Function distance(x1 As Single, y1 As Single, x2 As Single, y2 As Single) As Single
distance = ((x2 - x1) ^ 2) + ((y2 - y1) ^ 2)
End Function
 
'is the same as 
 
Public Function distance(x1 As Single, y1 As Single, x2 As Single, y2 As Single) As Single
distance = ((x2 - x1) * (x2 - x1)) + ((y2 - y1) * (x2 - x1))
End Function

But which is faster?

In this case, the first one will be faster because it is doing 2 less calculations.

I'm sorry if I was confusing about the Big O Notation comment. Big O Notation is programmer short-hand to talk about the worse case scenario--time-wise--for a function--or piece of code--to complete itself. In your existing code, it will always require going through 2 For loops--hence the N^2 (squared) notation.

There was another post that talked about speed issues in VB, and for the life of me, I can't remember what search phrase I used to find it.

Finally, why is your worse case scenario 999 characters w/ (999 * 999) objects? I can't think of any games less than MMOs that would have that kind of collision detection needs. Not Doom 3, Oblivion, Final Fantasy XII, or anything else that comes to mind. What are you really trying to do? What is your game really suppose to do/handle?

[triggernum5]

Actually, oddly enough a NEGLIGIBLE speed increase can be gained by splitting math equations into the smallest possible components over several lines.. Reason being the way the cpu itself actually handles arithmetic.. If somebody cares I'll see if I can find the article I read..

[Fedhax]

Actually, oddly enough a NEGLIGIBLE speed increase can be gained by splitting math equations into the smallest possible components over several lines.. Reason being the way the cpu itself actually handles arithmetic.. If somebody cares I'll see if I can find the article I read..

So taking this example:
distance = ((x2 - x1) ^ 2) + ((y2 - y1) ^ 2)

Would be faster to do:
Result = x2 - x1
Result = Result ^ 2
Result2 = y2 - y1
Result2 = Result2 ^ 2

TotalResult = Result + Result2

??

[triggernum5]

distance = ((x2 - x1) ^ 2) + ((y2 - y1) ^ 2)

Would be faster to do:
Result = x2 - x1
Result = Result * Result
Result2 = y2 - y1
Result2 = Result2 * Result2

TotalResult = Result + Result2
More this, but yea, thats what they said.. I saw some benchmark tests on a site dedicated to vb efficiency to an anal extent.. For instance did you know its SLIGHTLY (nanoseconds) faster to omit the Call Operator and brackets in a sub call?

http://www.persistentrealities.com/v...egory=2&item=0

[chemicalNova]

From what I can tell, you're still looping through 0-999. Why? if your projectiles aren't always on the screen, why bother?

Personally, I would use a collection. Then you can remove any projectiles not on the screen and your loop won't have to loop that many times. Also, you would only have to loop the visible ones like so:

For i = 1 To Collection.Count
Next i

If theres 2 projectiles on the screen, your code will loop twice, not the pointless 999 times.

chem

[triggernum5]

Give us some expected average numbers.. chemicalNova's idea or my idea are bound to be about 1000x faster.. I realize my idea seems whack since this isn't a square based game like zelda, but still If you calculate the largest possible span a player's radius/weapon can have then you can simply loop though every possible reachable location to see if a collision occurs.. Sparse arrays can reduce memory cost if needed..
Consider this stupid analogy.. You're paranoid that there might be a tack on your floor that you don't want to step on.. Are you going to confirm that each and every tack in your home is in a location other than where you are about to step? Or do you simply check the area where you are about to step in order to confirm that there is no tack there?

[Fedhax]

Consider this stupid analogy.. You're paranoid that there might be a tack on your floor that you don't want to step on.. Are you going to confirm that each and every tack in your home is in a location other than where you are about to step? Or do you simply check the area where you are about to step in order to confirm that there is no tack there?

I think that his desired result is to accomplish exactly what ChemicalNova and you are suggesting. Unfortunately, it sounds like--using your analogy--his footstep is the size of his entire lot including the house, the swimming pool, and the pool house. Being a programmer, I know that it hard to be told to rewrite something because that includes a lot of mundane "Been there; Done that" kind of work and nothing that anyone else will be able to notice. However, as si_the_geek said, there are some serious fundimental problems with this design if he is determined to check collisions for 999---much less 999^3--objects/NPCs.

[triggernum5]

Agreed, I know I've painted myself into corners while programming.. I kind of see it the opposite way for step size however..
With radius is a factor, looping would still be necessary, but it would be looping through space, not looping through items/players..
Say my biggest player's/item's radius is 10, and his sword increases his reach by another 10.. I only need to search the array in the area of (reach+radius) for population.. eg, loop from x-(weaponreach+biggestpossibleplayerradius) to x+(weaponreach+biggestpossibleplayerradius)
I guess thats 1600 iterations with my example, but since all you're doing is checking an array value it will fly in comparison to your loop.. Obviously more deeper calculations will be needed if you get a hit..
Another possibility is to use my original suggestion with a sectoring system built into the population array.. eg analogizing to a residential area, are they in this block? No.. Then stop checking.. But if yes then loop through each house then room.. It kind of works like binary division quick searches.. (Which is what the smarter Price IS Right - Beat the Clock contestants employ without even realizing it)

Edit: Or you could do the looping during the moves and toggle population on all the points each player/item can affect.. I'd personally do it like that I think, but I'd use 2 sparse arrays.. One for the actual population, and one for the attackability range.. BTW, a sparse array is a memory saver for huge matrices that only keeps data allocated for the elements it needs while still allowing the addressing/editing of any index valid in its original scope.. I have a class somewhere if interested..

[Fedhax]

eg analogizing to a residential area, are they in this block? No.. Then stop checking.. But if yes then loop through each house then room.. It kind of works like binary division quick searches..

As it stands now, he has one big block, and the block has the population density of Manhattan (The island part of New York City for non-Americans here) during a building/renovation boom. The array/matrix/grouping needs to be divided up. How he wants to do it is his call, but with the posted implementation, it will just take time/CPU power to do it. If he takes my approach, your approach, or ChemicalNova's approach, he will start to get the kind of performance increase he is wanting. However, all of that said...

What kind of game are we debugging, and who is its intended audience? 1 player? 100 online players? Maybe having a better idea of the desired outcome would help figure out possible solutions.

[triggernum5]

Yea I know.. There are so many ways.. New ideas are constantly popping up.. Needless to say, the sooner he breaks and picks a feasible method whatever it may be the better

Here is a page/file containing various classes/examples for advanced arrays.. Good luck..

http://vb-helper.com/tut2.htm

[si_the_geek]

And i tested it both ways, my current distance formula and the old one (both without sqr) and they give the exact same answer:

Indeed they will - I misread your amended version before.

PS: thinking about the while scheme once more, i could just combine the pickup type with the projectile type and simple have "ispickup as boolean" to determine what to do once collided... that would undoubtedly speed things up a bit.

It wont really make a difference - as you will still be doing the same amount of checking for enabled/distance as before.

To improve your current method any further you will need to move "not enabled" items to the end of the arrays, and use a variable for the "highest used index" as I mentioned above. Using this method on my computer (with your latest code, and simulated data!) the time taken went from 2.9s to 0.7s.

chemicalNova's suggestion for a Collection is similar to this method, but in my experience tends to be slower.


To have a really serious speed improvement tho, you are likely to need to re-design the way the program works - and we can help with that if you want. If you do, I'd recommend answering the questions at the end of Fedhax's last post.

[JayWalker]

Ok, well, I have made few changes:

combined pickup type with projectile type so i only need to do 1 distance calculation per loop - speed increase slightly noticeable

using x*x instead of x^2 - this improved speed by a TON

distance formula is on line with collision detection sub, and not using sqr (when using sqr its only slower by about 1fps, but every little bit helps)

so here is my current collision detection sub:

Public Sub check_for_collisions()
'check for collissions between player/projectile and player/pickup
    Dim i As Integer
    Dim r As Integer
    
    For i = 0 To 999
        If player(i).benabled Then
            For r = 0 To 999
                'check player/projectiles
                If projectile(r).benabled Then
                        If ((player(i).radius + projectile(r).radius) * (player(i).radius + projectile(r).radius)) >= ((projectile(r).x - player(i).y) * (projectile(r).x - player(i).y)) + ((projectile(r).y - player(i).y) * (projectile(r).y - player(i).y)) Then
                            collision_player_projectile i, r
                        End If
                End If
            Next r
        End If
    Next i
End Sub

just one question about my distance formula though, when using my current method (without sqr, and squaring what its comparing against) will i get the same difference in the answers as if i was doing it my old way?

So, as of right now, Im getting about 13-14 fps (compiled) when still going through 999 players/projectiles (minus the extra calculations for pickups of course)


Answer To Fedhax:

My ideas for this game are to be a fairly simple, but fully real time space rpg (when saying real time about this i mean anything in the universe can be going on at once, IE: while the player is off trading at some station there could be 100 AI players engaging in battle ten million units away, which could in some way shape or form affect what the player can do later, or if the player was close he could just be wandering along, see this big battle going on, and join in)

In a nutshell:

The players objective is to fly around the universe from station to station, buying/selling items in attempts to make money. The player will be able to attack pirates for gold (the pirates will also attack the player, because they are pirates ) or trade with a passing trader ship (or be pirate like, and attack it ). Pickups carrying various items will be floating through space at any given time, which if the player comes across one could pick it up. Pickups would also be dropped from pirates/traders when they are killed, and the pickup contains whatever that pirate/trader had.

Pretty much going to be a single player game for those who like small games like this. I may eventually make it multiplayer but not at the moment.

I have my current source code attached, but i didnt want to release it because this is pretty much my first major (even tho its nothing amazing) game project. But since im in need of help, i suppose its necessary.

PS: you will need to install pbgl.dll in order to run the game/source. How to do this is explained in post #1.

What happens in the current test/demo version of the engine (no real "game" code in yet, as far as trading, shooting, or things like that goes) is pretty much, every possible thing that can be spawned, is, and the AI players just attempt to follow you around.

PSS: si_the_geek, what you said about

To improve your current method any further you will need to move "not enabled" items to the end of the arrays, and use a variable for the "highest used index" as I mentioned above. Using this method on my computer (with your latest code, and simulated data!) the time taken went from 2.9s to 0.7s.

sounds feasable, and undoubtedly would help, but im not sure how i would go about doing that. Because if one of the objects mid array became non-enabled, wouldnt i have to move all values in the array down so there are no "gaps"? this would take a lot of time if what im thinking is right.

PSSS: You might notice the "calccenters" sub in the physics module. I just realized that someone might see that and wonder why its there, so basically it will be used in the distance formula in the collision detection loop so its comparing radiuses from the center of each object, instead of upper left corner. So it will be object.centerx instead of object.x, if i made any sense out of that. I just havent changed the code yet to that.

[si_the_geek]

I haven't looked at the code yet, but it sounds like you would get a huge benefit from the "zones" idea.. especially for your AI code.

...sounds feasable, and undoubtedly would help, but im not sure how i would go about doing that. Because if one of the objects mid array became non-enabled, wouldnt i have to move all values in the array down so there are no "gaps"? this would take a lot of time if what im thinking is right.

Well there's a nice little trick... you don't need to move them all, only copy one of them.

If you have 100 'enabled' items, and want to remove the 3rd one, simply overwrite item number 3 with the data from item number 100, and then reduce the counter, eg:

'Assuming your counter variable is NumPeople
player(3) = player(NumPeople)
NumPeople = NumPeople - 1

[JayWalker]

So i would be able to do a loop just like this, and instead of going to 999 goto numplayers/numprojectiles on all my loops?

Public Sub optimize_arrays()
    Dim i As Integer
        For i = 0 To numplayers
            If Not player(i).benabled Then
                player(i) = player(numplayers)
                numplayers = numplayers - 1
            End If
        Next i
    Dim r
        For r = 0 To numprojectiles
            If Not projectile(i).benabled Then
                projectile(i) = projectile(numprojectiles)
                numprojectiles = numprojectiles - 1
            End If
        Next r
End Sub

and its simple as that?

[Fedhax]

I'm tackling this post strictly using stream-of-consciousness thinking. Hopefully, you'll be able to follow it. If not, feel free to ask questions.

sounds feasable, and undoubtedly would help, but im not sure how i would go about doing that. Because if one of the objects mid array became non-enabled, wouldnt i have to move all values in the array down so there are no "gaps"? this would take a lot of time if what im thinking is right.

If you design your game loop right, you will update the UDT's status(es) during execution and sort the arrays at the end of the game loop. In this manner, you will not have any objects left dangling in the middle of the array. There are FAQs for a tight/high-performance game loop--haven't read your code yet --and others like ChemicalNova (Shameless plug), si_the_geek, or myself can help you handle it properly. Same thing with the sorting algorithms.

using x*x instead of x^2 - this improved speed by a TON

Score one for triggernum5

My ideas for this game are to be a fairly simple, but fully real time space rpg (when saying real time about this i mean anything in the universe can be going on at once, IE: while the player is off trading at some station there could be 100 AI players engaging in battle ten million units away, which could in some way shape or form affect what the player can do later, or if the player was close he could just be wandering along, see this big battle going on, and join in)

Here is the rub of your dilemma and where other people may be able to help more so than I. You may need to differentiate between "thinking" AIs and "acting" AIs. Maybe a better way to word it would be to say "instances" v. "permanents". If you take the "zone" approach, the "instances" don't have to be persistent as your player jumps between systems. ( Side note: "Warp gates" are in-story use of areas/zones that don't break the suspension of belief while someone is playing your game. Thus, it makes your job as game programmer much easier. )

Now, these instances can be created and destroyed on your whim as game coder which means you could create them when a player travels into that part of a system. When the player shows up, he--or she--doesn't know they didn't exist when he jumped into the system. They just appear to be at each others' throats. However, underneath the hood, your game didn't account for them because it was unnecessary processing time from your perspective. If you have 100 AI ships fighting each other, they don't really need a background, history, persona per ship that spans the entire length of game play. You can randomize or have predetermined values for them to see how they should act under predetermined conditions (Fighting, Fleeing, Resting, Traveling).

"Permanents" will be harder and more complicated to implement--maybe make them a phase two addition to your project if you get the instances out of the way. Permanents will require more programming, predetermined thought & design, and be more CPU intensive. You may want to limit the number of these guys to 2 - 4 ships 'til you get the hang of 'em. They can be rivals to your space-faring player but definitely not 999 of 'em in memory during the entire game playing time. Again, the professionals haven't gotten that far, and I'm not sure if any of us here have gotten there either.

[Fedhax]

So i would be able to do a loop just like this, and instead of going to 999 goto numplayers/numprojectiles on all my loops?

...snip...

and its simple as that?

Not exactly. I think what si_the_geek was aiming for something along the lines that you could sort the array as you move through it. The approach that he posted was varied form of a bubble sort, and it could work.

Public Sub optimize_arrays()
    Dim li       As Integer
    Dim li2      As Integer
    Dim liMove   As Integer
    Dim liMove2  As Integer
 
    li = 0
    li2 = 0
    liMove = numplayers   ' numplayers:  your variable defined elsewhere?
    liMove2 = numprojectiles   ' numprojectiles:  your variable?
 
    ' While li is less than liMove, keep going.  If li is greater than liMove,
    ' you are moving into empty array territory.  Same as the 2nd While loop
    While li < liMove
       If Not player(li).bEnabled Then
          player(li) = player(liMove)
          ' You need to clear/reset the values in player(liMove) here
 
          liMove = liMove - 1
       End If
 
       While li2 < liMove2
          If Not projectile(li2).bEnabled Then
             projectile(li) = projectile(liMove2)
             ' You need to clear/reset the values in projectile(liMove2) here
 
             liMove2 = liMove2 - 1
          End If
 
           ' Check your collisions now/here
           li2 = li2 + 1
       Wend
 
       li = li + 1
    Wend
End Sub

[si_the_geek]

Nope, I really did mean it as simply as I posted - that was the entire code!

This is assuming that the position of items in the array doesn't matter, and that items are not re-enabled (which would only take a couple of extra lines).

and its simple as that?

Even simpler - you dont need the optimize_arrays sub at all.

Start the values of numplayers/etc. at 0, and only increment when you add a new player/etc. ..and when you remove one, use the 2 line code I posted above!


Having this means that your collision code can now be like this:

Dim i As Long  'Long is faster than Integer (because it is the same size as the CPU uses)
    Dim r As Long
    
    For i = 0 To numplayers
        For r = 0 To numprojectiles
            'check player/projectiles
          If ((player(i).radius + projectile(r).radius) * (player(i).radius + projectile(r).radius)) >= ((projectile(r).x - player(i).[u]x[/u]) * (projectile(r).x - player(i).[u]x[/u])) + ((projectile(r).y - player(i).y) * (projectile(r).y - player(i).y)) Then
              collision_player_projectile i, r
          End If
        Next r
    Next i

EDIT: you didn't have X for the player!

EDIT 2: A potential speed improvement:

Dim i As Long  'Long is faster than Integer (its the same size as the CPU uses)
Dim r As Long
 
Dim PX As Single, PY As Single, PR As Single
 
    For i = 0 To numplayers
        With player(i)   'until the "end with", anything starting with . is treated as if it starts with player(i). 
          PX = .x
          PY = .y
          PR = .radius
        End With
        For r = 0 To numprojectiles
            'check player/projectiles
          With projectile(r)
            If ((PR + .radius) * (PR + .radius)) >= ((.x - PX) * (.x - PX)) + ((.y - PY) * (.y - PY)) Then
                collision_player_projectile i, r
            End If
          End With
        Next r
    Next i

[JayWalker]

Awesome. Well, i may have gotten to the point where current optimizations will do from here on out (unless someone can throw even more good ideas at me).

I have the code implemented for numplayers, numprojectiles, and numstations on all loops, and si_the_geek im using your "potential speed improvement code" as it is about 2x faster than my original code.

Currently i am getting about 29 fps (uncompiled) and 32 fps (compiled) with 660 (total) objects spawned, so im thinking from here on out i might either have to scale down my world a tiny bit (depending on how it runs on my old K6-2, which i havent tested yet), or a better idea i can just spawn players around the player depending on preset likeleyhoods of encountering an enemy in any part of the universe, which would be more than fast enough for even old machines because there would only be MAX 1-10 players spawned at all times.

Thanks a ton guys, you have all helped me to an extent i wouldnt have been able to get to alone, i never would have thought of most of these things

So ill be sure to continue using these ideas throughout the rest of any loops i need to do in the game.

Also, where (if anywhere) would be the most appropriate place to post a finished game/program to get opinions/feedback on it?

edit: tested it on my old 500mhz K6-2, and under the same conditions that i ran it under on my pc, it was getting 8-9 fps (compiled) which i think is very good considereing on my original code (before i even started collision detection) it was only getting 13-15 fps. now just a slightly scaled down world and some frame skipping turned on should make it run well on pretty much any machine.

[chemicalNova]

Can I ask how theres going to be this amount of anything on the screen in the first place? Isn't this completely GDI based? If so, its quite doubtful you're going to have the game be fullscreen. If you plan on having 999^3 objects on the screen, they're probably going to be 1 pixel wide each. You should cull the amount of objects/NPC's, etc, considerably. Theres no way you'll ever get 999^3 objects on the screen using pure API's, and running a good framerate.

If however, you're using DX/OpenGL, then the above methods should be more than sufficient. But, again, I'm a little doubtful 999^3 objects could be on screen, even with these graphics libraries.

chem

[NoituloverRevolution]

Yeah... i can do even better then all of you on computing the distance. it shocks me
that none of could do any better here is my code:

Distance = Abs(x2 - x1) + Abs(y2 - y1)

ive known this since i was 8, seriously guys get with the program here.


EDIT: Oh. and i could not agree more with chemicalNova but that's OK, i was a kid once to.

[JayWalker]

Yeah... i can do even better then all of you on computing the distance. it shocks me
that none of could do any better here is my code:

Distance = Abs(x2 - x1) + Abs(y2 - y1)

ive known this since i was 8, seriously guys get with the program here.

um, im not trying to be an ass, but for 1 that wil not return the correct answer because the differences need to be squared (i tested it and it returned a distance of 16, when in fact the correct distance was 10 (measured and compared by pixels) and the "correct" distance formula (that which is found on google and taught by my teachers) returns a totally different answer), and 2, the distance formula (when used properly) will always return a positive answer, so having Abs() in front of it, will only slow it down.

ChemicalNova: i was in no way shape or form planning on having 999^3 objects on screen at once. An absolute MAXIMUM might be 20-30 once the game is done. Also, i have changed the code so now there are only 999^2 objects being controlled, and unless that many are spawned, its far less.

[NoituloverRevolution]

ohhh you did not want a positive answer?

[JayWalker]

ohhh you did not want a positive answer?

no, i NEED a positive answer... and when the distance formula is used correctly will always return a positive answer, so having Abs() in front of it just slows it down...

[NoituloverRevolution]

yeah but i tested it and it runs 20% faster. i use it like this:

X1=0:Y1=0
X2=1:Y2=-1
Distance = Abs(x2 - x1) + Abs(y2 - y1)

so it returns 2 is it not supposed to.
oh... and before i was joking.

[chemicalNova]

ChemicalNova: i was in no way shape or form planning on having 999^3 objects on screen at once. An absolute MAXIMUM might be 20-30 once the game is done. Also, i have changed the code so now there are only 999^2 objects being controlled, and unless that many are spawned, its far less.

I'm also not trying to be an ass, but if the maximum is 20-30, how does this work:

there are only 999^2 objects being controlled, and unless that many are spawned, its far less.

? If theres a maximum why do you still need to loop 999^2 times? :/

chem

[JayWalker]

can you make your own thread and not hijack mine...

chem: i dont need to loop 999^2 all the time. It only loops to the number of players/projectiles i have spawned. Lets say i only have 10 players spawned, and 50 projectiles, thats 10 * 50 = 500 loops, based upon the way the loop works.

[si_the_geek]

True, you just need to be careful about how many items get added - because each one you add will slow it down exponentially (11 * 50 = 550 iterations).

yeah but i tested it and it runs 20% faster. i use it like this:

X1=0:Y1=0
X2=1:Y2=-1
Distance = Abs(x2 - x1) + Abs(y2 - y1)

so it returns 2 is it not supposed to.

Try using some different values, my first test (X1=0, Y1=0 / X2=2, Y2=2) returned the wrong answer (4, when it should be 2.8).

I have moved your separate question to here, we don't want to get things confused!

Also, where (if anywhere) would be the most appropriate place to post a finished game/program to get opinions/feedback on it?

We have a Game Demos forum for that.

[triggernum5]

Umm, I don't know why I'm pointing this out.. I don't even know if this was a serious post, but your 'distance' (teehee formula would be faster if you did the abs() manually with IF statements.. You really should speed that up as much as possible since if a player actually moved like that they'd be wasting alot of time.. Lemme guess, you're the kind of guy who walks 2 miles around a 1sq mile field right?

[NoituloverRevolution]

didn't JayWalker post this code saying something about it being what he'd done
and their not being much to be improved?:
Distance = Sqr((X2 - X1) ^ 2) + Sqr((Y2 - Y1) ^ 2)

i based my distance formula on this code.

but this here, is the only correct formula on here:
Distance = Sqr((((X2 - X1) ^ 2) + ((Y2 - Y1) ^ 2)))

[si_the_geek]

didn't JayWalker post this code saying something about it being what he'd done
and their not being much to be improved?:
Distance = Sqr((X2 - X1) ^ 2) + Sqr((Y2 - Y1) ^ 2)

Nope.

What was posted was this:

distance = ((((x2 - x1)*(x2 - x1)) + ((y2 - y1)*(y2 - y1))))
'which is effectively the same as:
'Distance = ((X2 - X1) ^ 2) + ((Y2 - Y1) ^ 2)

..this is actually distance squared (intentionally), to go along with the squared value to compare it to (so the result of the boolean comparison will be the same). The reason for doing this is that calling functions (such as Sqr) is relatively slow.