Tweening... Again... Just shoot me now.

Blitz3D Forums/Blitz3D Programming/Tweening... Again... Just shoot me now.

Adam Novagen(Posted 2011) [#1]
Hi all,

So, I've run into trouble YET AGAIN with tweening in Blitz 3D. A reminder for those who may need to be brought up to speed on my project: the game is, in essence, a 2D shooter rendered in 3D, using tile-based level maps. This means that there will sometimes be a metric LOT OF ENEMIES about - quite possibly in excess of 100 at once - all colliding with each other AND the map by use of Collisions().

This means, of course, that there is every chance for the LOGIC to take more than 16 milliseconds, and of course anything over 16 2/3 ms is too long for a game to render at 60 FPS. Mark Sibly's tweening code works purely on the RENDERING; if a frame takes two frame's worth of time to render, the game performs the logic TWICE on the next loop to make up for it. Render goes too long, logic increases to catch up.

This presents a problem, however. If the logic takes, say, 10ms for a single frame, then it's run twice to catch up with a long render, the result is 20ms, meaning the logic has ALREADY taken too long, before the render has even started. This eventually results in cumulative errors that take longer to catch up the longer the frame delays persist.

So, bottom line is this. I need my game to be able to update 100+ enemies, all colliding with each other AND the map, along with rendering about 500~2000 non-colliding frags and bullets, in as few milliseconds as possible, without needing the power of an MIT supercomputer behind it. What should I do? Should I try a different tweening method? Is it unrealistic to hope for 200+ entity collisions, which indeed seem to be Blitz3D's most CPU-intensive process, and should I rethink said collisions? I'm at my wit's end with this; shooters are all about impressive masses of frags, bullets and enemies, yet it seems like I'm just overreaching things somehow.

All help is appreciated, and "dumb" ideas won't be flamed. Thanks. :p


Matty(Posted 2011) [#2]
In games where I have lots of enemies/units that can collide I don't use the blitz collision command usually.

Instead I have a bank (or an array will do) which represents a grid of locations in the game world, at each index is a handle to another bank which contains a list of units within that grid cell. Then, when a unit moves it simply needs to update its grid cell position and check the current grid cell and neighbouring ones iterating through the units in those grid cells to perform distance checks for purpose of collisions.

Pseudo code:

if unit moves
check if still in current grid cell
if in current grid cell check collisions with other units in current grid cell and neigbouring ones.

if moved to different grid cell, remove from current grid cell (adjust bank's accordingly), add to new grid cell bank and check collisions as for above.

This is extremely fast as when a unit (bullet/enemy etc) moves it only needs to check against its nearest neighbours..rather than iterating through an entire list.

Use of the handle/object commands is of great benefit here too.

Hope this helps, from matt.


Adam Novagen(Posted 2011) [#3]
That WOULD work, except I neglected to mention that although the MAPS are tile-based, the movement within the maps is completely free-range.

Anyway, first tip of the day in less than an hour, thanks Matt! :D


Matty(Posted 2011) [#4]
Even so - it would still work for unit to unit collisions, the grid overlaid does not have to be the same size as the tiles/maps.


Adam Novagen(Posted 2011) [#5]
Except that the entities use sphere-to-sphere collisions, and since the maps are 100x100 with tiles of 64x64px, we're looking at a 6400x6400 grid is subdivided... Bruteforcing that would be even slower than intercollisions.


Warner(Posted 2011) [#6]
The grid would solely function as a way to cut down the number of collisions. You should look at them as "area's", rather than tiles. Limiting collisionchecks to only those entities that are in the same area will cut down the number of checks quite a bit.
This example just shows/hides entities. Imagine there is an object where the mouse is at. The visible entities are then the ones that should be involved in collisions. The invisible ones should not be checked.



Adam Novagen(Posted 2011) [#7]
Well I've done some research online, apparently the term I've been looking for all this time is "Delta Time." I also learned about the "spiral of death," which I had thought was an inadequacy in my + Sibly's tweening code but apparently is just an inherent problem in programs experiencing extreme load for prolonged periods of time. So, bottom line is I just have to tear through my code and mercilessly strip and trim things to lessen the logic time as much as possible.

I'll do things like hiding or at least de-colliding enemies when more than a certain distance offscreen, replacing EntityDistance() with my 2-dimensional Distance() function (remember, this is all arranged in 2D), etc. Looks like there's nothing else for it. This has also taught me a lesson, namely the reason why large-scale commercial companies like Valve don't use higher-end languages like B3D; there's really more overhead than first meets the eye. Well, at least I know where I'm going now; after Midnight Hacker, I guess it's time to finally learn C++. ;D

Last edited 2011


SLotman(Posted 2011) [#8]
C++ won't improve your rendering speed, you know?

Again: divide enemies by areas. If your hole map is 6400x6400 then divide it in 4 chunks (each 3200x3200) and only test coliisions on the area the player is. You'll probably have to divide it further, but that's the idea.

If still slow, just do rect-rect collisions on bullets/enemies, can't get any faster than that. Even EntityDistance may have an "Sqr" hidden in there, so it will be much slower then a simple position+width and height comparison.

Make sure your problems are really from the code area. Maybe your models have too much polygons for your video card, and it's slowing it down having too many of them on screen at once - try disabling collisions at all and see if the speed improves drastically, or remains the same.

How are you creating thos 100s ships? I hope you're using copyentity...

Also, avoid using sprites. They slows down things a lot. Create QUADs facing the camera, and update them manually if needed.

Last edited 2011


Matty(Posted 2011) [#9]
Sorry Adam I don't think you understood what either I or Warner are suggesting.

You don't have to have a grid of size 1 pixel per grid square. You simply allocate 'zones' or 'areas' - perhaps if your map is 6400 pixels by 6400 pixels then split into areas of size say 200x200 giving you an array size of 32x32 - and store the units that are within each 'area' in their own bank and do collision checks between those within their own and neighbouring cells.

Trust me, it works well and is extremely fast - blitz is more than capable of having a game with hundreds (or even thousands) of units moving around..


Adam Novagen(Posted 2011) [#10]
Now that I properly understand the zone concept, that's actually what I said I'd do in the end:

de-colliding enemies when more than a certain distance offscreen

Only difference here is that it's just one zone that moves with the player rather than dividing the map into static ones.

As far as C++, I know it won't improve render time; that's why I kept stating LOGIC time. Blitz3D's rendering goes as fast as any DX7 renderer, of this I'm aware, however its logic just has too much overhead, being such a high-end language; hell, it can't even power through a 75KB peek/poke bank without taking at least 11ms.

For Distance() versus EntityDistance, yes they both use Sqr(), but theoretically EntityDistance needs extras to accommodate the third dimension. I might end up cutting my losses and using simple rect collision on smaller, less complex enemies.

As far as quads versus sprites, I was unaware of that distinction; I've had little trouble with sprites in excess of 2,500, but if quads can be even faster then hell I'll rip it out and change it anyway; thanks for the tip.

Collisions, yes I am sure about those; I've done tests that confirm for me the fact that while 400 sprites can move and update quite easily for me, 400 sprites with sphere-to-sphere intercollision cannot; they quickly instigate the spiral of death, as the LOGIC (!=rendering) takes too long. My computers are a pretty good example of mid-market machines, which is more or less my target audience, so if the program doesn't run on my machines it needs work. I should probably test sphere-to-box collisions, however, those would theoretically be much faster; with 400 enemies on sphere-to-sphere there's bound to be 160,000 MULTIPLE calls of Sqr(), whereas with sphere-to-box it should theoretically only be 400 calls of Sqr(). I'll see what I can do there.

Oh, one final thing, the ships are being created from scratch with CreateSprite() - which will be replaced with CreateQuad(), using CreateMesh() - but they're all being textured from a single source. I'm not loading 100 sprites with their own individual yet identical textures, if that's what you're worrying. ;D


SLotman(Posted 2011) [#11]
You shouldn't use CreateSprite() for each ship! This creates a brush for every and each one of them, instead of using the same brush for all.

Create juse 1 sprite, then use copyentity to create the others. Just that should give you a speed boost.


Warner(Posted 2011) [#12]
I would disadvise using sprites. They're seem to be somewhat unreliable due to compatibility issues.


jfk EO-11110(Posted 2011) [#13]
Some of my users reported problems with my game engine as well, until I replaced the sprites by quads (see archives). Tho, I have to say I probalby cloned the sprites by accident, I used copyentity for some lamps, but then added a sprite while there was already one due to copyentity. Such clones at the same position will however couse extreme slowdowns.

So you say you're using sphere to sphere collision? If you don't need the collision response then you could also use EntityDistance instead. And as you said, 2D-Distance can be calculated using Pytagoras:

dist2d#=sqr((xdist#*xdist#)+(ydist#*ydist#))
then simply ask is dist2fd is smaller than radius of sprite*2.

Tweening. I am not a fan of it. It really doesn't make sense to call Updateworld() twice only because a frame took longer than 16.667ms. As you already suggested, I would also use Delta here. Just use

delta#=(frametime#/16.667)
Now you can use it as a multiplication factor for any movement. And best of all, if you for some reason have animated meshes in your game, use Updateworld(delta#) and the animation will be adjusted to the framerate.


Adam Novagen(Posted 2011) [#14]
Yeah, delta time definitely avoids the whole spiral-of-death problem. My only two quibbles with it are that it can't poll additional user inputs, and Blitz floats aren't exactly accurate, but I think in the end I'll just use it. Blitz' tweening capability is a great idea, but in execution it just doesn't always work out too well. :p


jfk EO-11110(Posted 2011) [#15]
I didn't get the thing about the two quibbles. Why would you want to poll additional user input, is the framerate that low so a user could write some text between two frames? AFAIS usually controls are "pressed or not", kind of "walk pressed*delta". In my Opinion a framerate of 20+ is high enough for most controls (no?), although for the eyes there should be 60. The other thing, floats are not accurate. That's true for some situations. But for delta timing it never seemed to be a problem to me. There is the system timer with its millisecsonds resolution. This may be considered inaccurate. And with delta there is also this paradoxon: you measured the last frametime for delta and then use it for the current frame, this is also a source for inaccuracy.

If you need additional input polling, just add some additional keys and button handlers in you gameloop. You could also read the keys at many points in your code, and add the pressed Char to a string, then examine the string at a dedicated, single input handler. (btw. isn't inkey$ doing that automaticly? )


K(Posted 2011) [#16]
Which is faster?

sqr(X)
or
(X)^.5

Just a thought.I agree on sprites, theyr'e painful and outdated and I've been wanting to replace them for a long time, still haven't finished.


jfk EO-11110(Posted 2011) [#17]
If you use the code I've posted in the archives then it's rather painless. It will override the original commands. (Maybe still needs a final cut, codewise, but the idea is there)

(BTW: There is A limitation: when you "FreeEntity" a Sprite, you will also have to "ReleaseSprite" it. Usually it's simple to find all places in your code where Sprites are freed, and add the command there. And such a quadbased Sprite will also be of EntityClass$ "Mesh" and not "Sprite", this may cause further problems. Well, just read the comments in the archive entry.

BTW2:

b=16
Delay 500

t=MilliSecs()
For i=0 To 1000000
 a=b^0.5
Next
Print MilliSecs()-t

t=MilliSecs()
For i=0 To 1000000
 a=Sqr(b)
Next
Print MilliSecs()-t



WaitKey()
End




result:

887
55

Last edited 2011


Axel Wheeler(Posted 2011) [#18]
If you put your two quibbles in a warm box and feed them lemons and sweetmeats they should be fine.

Here's a thought that avoids the hassle of creating a zone-based collision system, and should speed things up a bit.

Instead of running square roots on every permutation of objects, why not start with a recursive culling of the clearly-out-of-range objects:

If abs(Thing1\x-thing2\x) > 10 ; Or whatever your minimum collision distance would be
   If abs(Thing1\y-thing2\y)> 10
      ;Run your distance check here
   EndIf
EndIf


I know it looks like it's repeating itself, but only for those few objects that are actually close enough to bother with. For the great majority of objects the first If statement culls them quickly.

I've never done this, so I don't know, but it seems like it should work.

Come to think of it, for the collisions that don't include the player, the initial checks may be good enough; you could skip the square roots altogether.


Axel Wheeler(Posted 2011) [#19]
Ok, here's the proof. I got a speed increase using my method of nearly a factor of 10. Three methods are compared on collosions of 1000 objects (1,000,000 permutations):

1. Pythagoras on every one (takes ~490 ms)

2. First cull on x, then on y, then Pythagoras on those left over (takes ~86 ms)

3. Cull on x, cull on y, then we're done (settle for a rectangular collusion area) (takes ~62 ms)

Methods 1 and 2 produce idential results, but 2 is much faster. Method 3 is just a bit faster but less accurate. I'd go with method 2.

Of course, varying the size of the overall area relative to the collision area will change the results, but probably not the fact that method 2 is more effiecient than method 1.




SLotman(Posted 2011) [#20]
That's why I suggested first doing RECT collisions:

function Collision%(x1%,y1%,w1%,h1%,x2%,y2%,w2%,h2%)       
  if (x1<x2+w2) and (x1+w1>x2) and (y1<y2+h2) and (y1+h1>y2) then return true
  return false
end function


This is fast as it can be - then you check for sphere collisions, or even use the built-in collisions commands. The function can be optimized a little more if using something like this:

if (x1<x2+w2) then if (x1+w1>x2) then ...


So if any condition isn't met, it won't test all the other options.

Even on an old 486, I could test lots of objects with this code, without any slowdown.

Last edited 2011


Gabriel(Posted 2011) [#21]
It really doesn't make sense to call Updateworld() twice only because a frame took longer than 16.667ms.

It's actually essential, and the fact that delta-timing lets you do it just shows you how many mistakes delta-timing lets you get away with ;)

You're setting the target frame rate, so if your game doesn't reach it, whose fault is that? Either lower the target frame rate or speed up your game logic. It's pretty rare that a game needs to run its logic at 60 frames per second. It's usually a setting which ends up being left over when people convert from delta time because you can't get smooth updates with less than 60 fps with delta timing. Virtually all games could manage very nicely at 30 update cycles per second and you'd be amazed how many games could actually run perfectly well at just ten. If you can't optimize (or can't be bothered to try) your game logic then you can buy yourself so much more time be decreasing the target frame rate.


jfk EO-11110(Posted 2011) [#22]
From my old Atari days I've learnt to use the Vsync, so the frame update will not interfere with the physical sync. That's what I still do. This way the target rate is the rate the user has set for his VSync, usually 60 Hz in Fullscreen. Users may turn off VSync and run the game with as many fps as they can, but basicly 60 is the desired rate. But on many older machines it won't reach 60. So it wil run (still vsynched) with 30, 20, 15, 12 or 10. Some users probably even play it with 2 fps or so. With delta I get the exact time factor, I don't understand why you say "because you can't get smooth updates with less than 60 fps with delta timing", Gabriel. Why not?


Axel Wheeler(Posted 2011) [#23]

That's why I suggested first doing RECT collisions:




If still slow, just do rect-rect collisions on bullets/enemies



Oh, I get it. I thought by rect-rect you meant something like RectsOverlap(). So that means I basically fleshed out the method you mentioned and provided the evidence for Adam. It should basically solve his collisions problem with minimum fuss.

Out of curiousity I ran a test on RectsOverlap() and it was about the same speed as method 3 and usually slightly faster, although I couldn't get the counts to match for some reason. It should be a 20x20 square against a 0x0 point, which produces far more collisions than method 3. Even a 5x5 against 0x0 produces slightly more. Anyway, here it is.

;Method 4

Print ("Method 4 - RectsOverLap")
start=MilliSecs()
For t.thing=Each thing
	For o.thing=Each thing
		If t.thing<>o.thing
			If RectsOverlap(t\x-2.5,t\y-2.5,5,5,o\x,o\y,0,0)
				count=count+1 ;Skip Pythagoras; we're done
			EndIf
		EndIf
	Next
Next
Write("Collisions detected=")
Print(count)
Write("Time taken=")
Print (MilliSecs()-start)



Gabriel(Posted 2011) [#24]
With delta I get the exact time factor, I don't understand why you say "because you can't get smooth updates with less than 60 fps with delta timing", Gabriel. Why not?

It's a rather complex issue, and not really the discussion I was trying to make. One big reason would be that there is no VSync in Windowed mode. So while you *might* get good results in a window, you also might not. It's entirely dependant upon what the OS wants to do.


Adam Novagen(Posted 2011) [#25]
Hey, sorry to revive this thread after a couple of days' inactivity, but I only just remembered to check it again and I didn't want you all to think I was just ignoring you, after all the help you've given out.

So, for the time being I've actually REMOVED enemy intercollisions altogether, not as a copout so much as a design choice. When I started thinking about the various shmups I've played - Touhou, Geometry Wars and so forth - I honestly couldn't think of a single one where the enemies collided with each other, or needed to for that matter. All they really need to collide with, as I see it right now, are the map walls, and so far it's working out great.

I'm in the MASSIVE process of replacing every occurrence of sprites in my code with my quads, and have been surprised to see a distinct increase in rendering efficiency. This interests me, what exactly is it about the nature of B3D sprites that makes them more expensive to render than a quad?

By the by, K & jfk, where exactly do exponents enter into this? I'm a bit confused as to why they'd be used instead of Sqr() in the first place. >.>


Foppy(Posted 2011) [#26]
Only difference here is that it's just one zone that moves with the player rather than dividing the map into static ones.
Well, the difference is that if you do a distance check to all enemies and bullets, that means you are still computing 500 distances every fraction of a second if you have 500 enemies and bullets. The same is true by the way for collisions between your bullets and enemies. So if you have 100 bullets on screen, and 100 enemies, you would have 10.000 distance checks...

Using a grid-system where enemies and bullets are in separate linked-lists of objects for separate grid zones, you can have direct access to only those objects that are in grid areas adjacent to the area the player or one of his bullets is in, which in general means massive savings.

That being said if the game runs fine without a grid I guess it runs fine. :)


K(Posted 2011) [#27]
For X^Y=Z :

If Y is a whole number (ie 2) Z is a Y to the power of X.
If Y is a float/fraction, Z is the X root of Y{EDIT: DENOMINATOR OF Y}
If Y is negative, Z is the reciprical of X^(abs(Y))

But as JFK pointed out, sqr() would be WAY faster for hypotenous distance checks. BTW JFK, thanks for testing that, my whole next project was gonnna rest on pythagoreas, never bothered to test it, figured they'd be about the same.

On sprites, as was said, using copyentity() instead of Create is always better. But, good man to eliminate sprites, their compatibility is attrocious and having more than ~250 in one locale pushines your FPS down by maybe half.

Last edited 2011

Last edited 2011


Axel Wheeler(Posted 2011) [#28]

I'm in the MASSIVE process of replacing every occurrence of sprites in my code with my quads,



Of course, you should use CopyEntity() with your quads too whenever possible. It should boost efficiency a lot; at least it does for other meshes, and quads are just meshes.


Foppy(Posted 2011) [#29]
Another thing, pointed out to me by GfK once if I am not mistaken, is that if you check for collisions or something else between 4 objects, you don't always need 4*4 checks because that would mean checks between the same objects are done twice.

For object1.OBJECT = each OBJECT
   For object2.OBJECT = each OBJECT
      ; ...
   Next
Next

would result in 16 checks:
a: a,b,c,d
b: a,b,c,d
c: a,b,c,d
d: a,b,c,d


A is checked against B, but later on B is checked against A. You can avoid that by not looking at all objects in the inner loop, but only at those following object1:
For object1.OBJECT = each OBJECT
   object2.OBJECT = After object1
   While object2 <> null
      ; ...
      object2 = After object2
   Wend
Next

would result in 6 checks:
a: b,c,d
b: c,d
c: d
d:


Last edited 2011


K(Posted 2011) [#30]
Why not make custom functions named Createsprite(), etc. that would override Blitz Native Functions, as opposed to replacing "every occurence"?