[Optimising] Bullet theory (collsion checks)

I reckon it's mainly the rendering that's slowing everything down. Iopred's Particle System could handle this many bullets and collisions without even batting an eyelid. I know this because I'm using it for collision detection with 100 arrows vs 100 soldiers and getting pretty much full framerate. With your amount of bullets against only a single ship, you could definitely get rid of the lag using the Particle System class.

EDIT: Here's a link to it:

http://board.flashkit.com/board/show...1&postcount=33

50000 tests is quite a lot. If you think about realistic game with 250 enemy bullets vs 1 ship the difference between fastest and slowest method is about 3 milliseconds. I still think every collision detection script takes much less time then simply moving the 250 bullets and updating the screen.

Thanks for all the replies guys :) I was only expecting a few.

Anyway, I'm about to start work on a bitmap data version of the bullets to see how it runs so i will let you know how things work out.

Thanks.

Ali

hi,

your "burreto teori" looks great so far. i`m also working on a manic bmp shooter,.

the way i try to reduce hit checks is similar to squize`s way. i just check if bullet, enemy or player are in the same cell, and then hitTest them(allthough i might have to try , if it really is faster with a simple bounding box hitTest, to get the cell they are in,since i do it by coordinates, right now).

either way, its faster, because there is no constant hitTesting and the loops are much smaller.

im pretty amazed by iopreds particle class, damn fast...have to check it out

anyway, if you find a good and speedy alternative, it would be great if you could share it with us.

have fun

Chris

vengeance, that things amazing, im gonna have to figure out how it works some time...im really bad at doing so though

I only spent a few seconds browsing through iopreds code, but I can't quite work out why it runs so quickly. It seems to me he’s just attaching bitmaps to movieclips and then moving them as normal... how is that any different to just attaching a movieclip with a bitmap already in it?

By the way, I should have said this before, but I’m not actually having any speed issues at the moment, this thread was just because I wasn’t sure which of two methods were faster for collision detection. I still want to make it as speedy as possible though, so I’m continuing to look into bitmap collisions.

Ali

The consensus is to use circle testing (without sqrt) for collision, it was proved just a page back to be the fastest by quite a lot, and for round bullets, it seems like the perfect choice.

The Movieclip+BitmapData renders faster than Movieclips with bitmaps in them because normal MC's bitmaps are treated as square vectors with a bitmap fill. BitmapData is cached and is faster to draw.

So use Movieclip + BitmapData for display, and circle testing for collision and you'll be on the right track.

Thanks mate, that what I needed to know :).

Ali

Quote:

---

Originally Posted by iopred

The consensus is to use circle testing (without sqrt) for collision, it was proved just a page back to be the fastest by quite a lot, and for round bullets, it seems like the perfect choice.

The Movieclip+BitmapData renders faster than Movieclips with bitmaps in them because normal MC's bitmaps are treated as square vectors with a bitmap fill. BitmapData is cached and is faster to draw.

So use Movieclip + BitmapData for display, and circle testing for collision and you'll be on the right track.

---

have you experimented at all with bitmap.hitTest method, as another alternative the the other collision methods you tested....and if so, I was interested at your thoughts about it......whether you'd use something like that or not....

paul.

I haven't tested the speed of it, so I'm going purely on assumptions. But theres no way I see, that the bitmap hitTest would be faster than a simple bounding box hitTest. It would be nice if someone implemented it into Webgeeks testing fla however.

Quote:

---

Originally Posted by iopred

I haven't tested the speed of it, so I'm going purely on assumptions. But theres no way I see, that the bitmap hitTest would be faster than a simple bounding box hitTest. It would be nice if someone implemented it into Webgeeks testing fla however.

---

I did that (Flash8):

Bitmapdata.hitTest Test
Iterations: 200
Tests: 250
Total Tests: 50000
Hits: 50000
Misses: 0
Duration (milli): 509-545

Note: it did just run bitmapdata.hittest function 50000 times with bitmapdata object in hero and in enemy objects (25x25 px). It did not use the idea I talked about earlier about using 1 screensized bitmapdata object for all enemies.

Quote:

---

Originally Posted by tonypa

Note: it did just run bitmapdata.hittest function 50000 times with bitmapdata object in hero and in enemy objects (25x25 px). It did not use the idea I talked about earlier about using 1 screensized bitmapdata object for all enemies.

---

wow....even still, when compared with similar F8/AS2 tests by webgeek, it's clearly almost twice as fast as any of the other methods....even the simple bounding box hitTest....that's GREAT news!!! :D :) :)

now, if we could only get coordinates returned for the collision with that method...

paul

I got completely contrary results to tonypa.


HT - Shape to Point Test
Iterations: 200
Tests: 250
Total Tests: 50000
Hits: 0
Misses: 50000
Duration (milli): 721

HT - Bounding Box to Point Test
Iterations: 200
Tests: 250
Total Tests: 50000
Hits: 200
Misses: 49800
Duration (milli): 599

HT - Bounding Box to Bounding Box Test
Iterations: 200
Tests: 250
Total Tests: 50000
Hits: 1800
Misses: 48200
Duration (milli): 833

Math - Circle to Circle Test
Iterations: 200
Tests: 250
Total Tests: 50000
Hits: 1600
Misses: 48400
Duration (milli): 599

HT - Bitmap to Point Test
Iterations: 200
Tests: 250
Total Tests: 50000
Hits: 50000
Misses: 0
Duration (milli): 2571

The bitmap hittest was well the slowest, even checking a point, and even when you have 100% misses:

HT - Bitmap to Point Test
Iterations: 200
Tests: 250
Total Tests: 50000
Hits: 0
Misses: 50000
Duration (milli): 2505

i really wish Adobe would do somethinhg about the rendering in flash.

we are living in the age of broadband Adobe, how's about intergrating directX or openGL, i'd download an extra 10mb

bitmapData could be so much better

bastards

Quote:

---

Originally Posted by iopred

I got completely contrary results to tonypa.

---

Which Flash version you used? I noticed that in Flash9 Alpha the bitmapdata hittest results were much slower then in Flash8. Which could be because the code is not AS3 VM compatible. Or something....

Quote:

---

Originally Posted by mr_malee

we are living in the age of broadband Adobe, how's about intergrating directX or openGL, i'd download an extra 10mb

---

Mac version has OpenGL rendering, and it's far slower than the PCs in my school's IT room. No idea why.

Quote:

---

Originally Posted by tonypa

Which Flash version you used? I noticed that in Flash9 Alpha the bitmapdata hittest results were much slower then in Flash8. Which could be because the code is not AS3 VM compatible. Or something....

---

It was Flash 8, but in the Flash 9 player.

Just checking in on the shooter gang. Don't see any news, so I think monday we can have another demo of http://www.deusx.com/xlr

Just gotta decide which 3-4 levels to show.

Don't worry mate, "Project Soon"* is on it's way :)

Be cool to see what everyone else is up to.

Squize.

* Working title

Cool, looking forward to it :)


Just an update on the bitmapData stuff while I'm here. I’ve spent a few hours converting my engine to support bitmapData and things seem to be running ok for now. Progress is very slow at the moment with bullet theory though because I want to make it so perfect that I never seem to spend any time progressing with the game :p. I’ve started to get things rolling now though and I'm confident I will get it finished sooner rather than later.

Ali

Some cool screen shots there Mike. Look'n forward to seein both Alillm and Squizes games.

Still stuck on my project. Having problems getting my enemies to attack and some graphics. but I'm trying to have her done by Christmas.

Awesome, really looking forward to seeing all the shooters that will be coming out. I'm afraid mine wont be done for a couple of months though :( a lot of work to do still...enemies, bosses, backgrounds, GUI, dialog, guns...hopefully it will rock though ;).

Ali

Quote:

---

I'm afraid mine wont be done for a couple of months though

---

Hey, ours was "done" 2 years ago, just never got to the point where the final 2% was added to really make it complete. And it still isn't in some ways. Too busy with other things. So, yeah, it just drags on and on sometimes.

Cool, the shooter I worked on will be out soon. Though you'll have to register on the gaming portal to play it. I would really appreciate it if you guys do register on that site and give your valuable reviews. Will be much much appreciated :thumbsup:

I havn't read all of the posts, but I don't think I saw this idea. You can do the entire bullet array with one shape hitTest call, and you could even get it to work visually collide with the edges of the ship and not the center. (not one for each bullet, one hitTest that checks the MC that contains all the bullets)

If all of you bullets are spawned in their own MC, you only have to hitTest that MC against the players origin. I ran some tests that did 10000 hitTests per frame at 60fps, and the complexity of the shape being HitTested (IE your billion bullets) had no impact on the performance of the hitTest.

I think that is the obvious answer to do a quick check as long as all you need to know is if a bullet has hit your ship.

you can do the whole hitTest with one line of code and no loops.

if(EnemyBulletMC.hitTest(player._x,player._y,true) ){
oneOfTheBullet****TheShip=true;
}

of Course if you have the ship somewhere other than the main timeline you'll need to do a localToGlobal, but that will still be much faster than any method that checks all the bullets individually.

I you want to make the bullets collide with the edges of your ship, make the bullets have an invisible radius boosting movieclip that is about width of your ship, that way if the visual element of the clip hits your ships edge, the center point of your ship will be hitting the invisible circle surrounding one of your bullets.

If you do it that way, the HitTesting will certainly be the least of your worries in terms of performance.

What you are describing is simply "culling" the problem domain. This was mentioned previously at several points. There are many techniques to do this. In commercial games, it's generally something like a quad tree. The various collision testing techniques can all be used in conjunction with a "culled" data set.

I somewhat briefly skimmed through this thread because A. it interests me because I'm wokring on a Top-Down Shootem up for my final in my intro to game programming course (although I'm finding I'm slightly more advanced than the class, or my ability to pick up programming languages is very good), and B. because I'm working on accurate Shape dynamic hit testing for this game.

Unfortuanetly I'm limited to MX2004 but this is all besides the point, I believe I noticed that no one mentioned my title for collision testing, Recursive Dimensional Clustering (RDC from here on out.

RDC is a dynamic 'algorithm' so to speak, that figures out if objects bounds on screen intersect with other objects bounds along their x, THEN y, axis'. It doesn't sound very good, but in the simple level of my shmup its definetly improved the run speed.

The end results is minimal actual hit detection tests. which allows you to use more advanced hit detection methods for more accurate detection (finer detail, so that when an edge touches an edge, rather than a general area)

I'm not going to go into detail because I can't really explain it as well as it deserves, but here is a link to the article that enlightened me to RDC.
Recursive Dimensional Clustering

it took me some time to actually think of how I could implement this, because while the concept is very clear, the implementation can be somewhat tricky if your can't grasp it right off. if you consider using this, but are having trouble understanding his coding technique (as I did, since I have trouble thinking in classes, rather than functions) just drop me a reply, and I'll get back to you

Quote:

---

Originally Posted by Twiner

it took me some time to actually think of how I could implement this, because while the concept is very clear, the implementation can be somewhat tricky if your can't grasp it right off. if you consider using this, but are having trouble understanding his coding technique (as I did, since I have trouble thinking in classes, rather than functions) just drop me a reply, and I'll get back to you

---

yeah, I am the same way w/ classes......I'd like to see your implementation if you don't mind...


thanks,

paul.

Code:

---

function KillTest(b:MovieClip)
{
// First Define Two Arrays, one for Each Axis you need to test (three if you're
// working in a three dimensional enviroment.)

    var GroupX:Array = new Array();
    var GroupY:Array = new Array();

// Okay First, Background info, In this example we have two emptyMovieClips
// the first is eClip, which contains all enemy MovieClip's
// the second is bClip, which contains all the bullet MovieClip's

// Ok, after we define our Arrays, we will populate one OR more
// !!! we will not necessarily fill both arrays!! RDC is designed to reduce the
// amount of collisions test we will need to run in the end.

// okay, so we iterate through eClip, and test to see if any of the
// Enemy MovieClips Bounds (Min or Max) overlap any of the bullet MovieClips
// Bounds (min or Max) on their X axis
// you may chose to start on the y axis depending on your application

    for (e in eClip) {

    if (
      (bClip[b]._x + (bClip[b]._width / 2) >= eClip[e]._x - (eClip[e]._width / 2)
        &&
      (bClip[b]._x - (bClip[b]._width / 2) <= eClip[e]._x + (eClip[e]._width / 2)
        )
          {

// if any enemy movieclips intersect with a bullet clip on their bouds via the X
// axis, we add them into the local array GroupX
// in this specific case I'm using strings so I can evaluate them later with []

              GroupX.push(String(e));
          }
    }


// okay so here is where some of the power starts, if we don't Find any
// bound overlaps, we obviously don't want to waste processing
// so if nothing overlapes, nothing ever gets pushed into the GroupX array.
// but if we do have elements in the GroupX array, we iterate through
// it and run y Axis's tests against the elements in it (I had to use
// reference strings to pass to evaluaters to get this to work for me.

    if (GroupX.length != 0) {
          for (e in GroupX) {
              if ((bClip[b]._y + bClip[b]._height / 2) >= (eClip[GroupX[e]]._y - eClip[GroupX[e]]._height / 2)
              &&
              (bClip[b]._y - bClip[b]._height / 2) <= (eClip[GroupX[e]]._y + eClip[GroupX[e]]._height / 2))
              {
// Same deal here as before with the GroupX.push
                    GroupY.push(GroupX[e]);
              }
          }
    }

// now once again we are going to make sure there were some true
// statements along the Y axis, so that we don't waste processing power.

    if (GroupY.length != 0) {
          for (e in GroupY) {

          // and this is where you would put you're hit test code
          // remember, this design in itself isn't a hit test, its designed to
          // reduce the amount of hit tests to a minimum
          // I definetly recommend checking out the article I learned this
          // from, especially if you don't really understand what this is
          // doing. on the article site, there are flash and graphic
          // representations. go see the site linked in my previous post.

          }
      }
}

---

and heres the code without the comments if you want to just rip it, you can replace eClip and bClip with any empty movie clip that contains a set of movieclips (I've done it in this fashion partially do to the fact that all the content in my game is dynamicly generated

Code:

---

function KillTest(b:MovieClip)
{
    var GroupX:Array = new Array();
    var GroupY:Array = new Array();
for (e in eClip) {

    if (
      (bClip[b]._x + (bClip[b]._width / 2) >= eClip[e]._x - (eClip[e]._width / 2)
        &&
      (bClip[b]._x - (bClip[b]._width / 2) <= eClip[e]._x + (eClip[e]._width / 2)
        )
          {
              GroupX.push(String(e));
          }
    }
    if (GroupX.length != 0) {
          for (e in GroupX) {
              if ((bClip[b]._y + bClip[b]._height / 2) >= (eClip[GroupX[e]]._y - eClip[GroupX[e]]._height / 2)
              &&
              (bClip[b]._y - bClip[b]._height / 2) <= (eClip[GroupX[e]]._y + eClip[GroupX[e]]._height / 2))
              {

                    GroupY.push(GroupX[e]);
              }
          }
    }
 if (GroupY.length != 0) {
          for (e in GroupY) {
          }
      }
}

---

Just a note, this is a very specific implementation of RDC, it only checks an object against a set of objects.

In order to use this in a more advanced function, (more than a 1 to 1 collision break down) you'de need to modify this function.

Unfortuanetly, I can't really explain how to do that.

Additionally, if you're just using basic hit tests this may actually use up a lot of extra processing power, unnecessarily, this is more usefull when doing advanced mathematical collision testing, true shape, or maybe bitmapData (I don't know since I'm not currently using Flash 8).

I saw a recent thread that was discussing irregular shapes and normals using BitmapData to generate a "pong"-esque physics engine. I think one aspect of that experiment could be put to use here.

Near as I can understand, the player's ship would occupy one BitmapData and all of the enemy bullets would occupy another BitmapData. All you would need to do is check to see if any opaque portion of the enemy bullets layer overlaps with the opaque area of the player's ship layer. If this happens, retrieve the bounding box of that collision, then find the bullet closest to those coordinates and perform actions on it as needed.

This may work well (hypothetically) for only one collision at a time, but would have to be reworked to accomodate multiple impacts.

That's pretty much how I did it in Polarity.

Squize.

Quote:

---

Originally Posted by Q__Hybrid

Near as I can understand, the player's ship would occupy one BitmapData and all of the enemy bullets would occupy another BitmapData. All you would need to do is check to see if any opaque portion of the enemy bullets layer overlaps with the opaque area of the player's ship layer. If this happens, retrieve the bounding box of that collision, then find the bullet closest to those coordinates and perform actions on it as needed.

---

yeah, that's a similar system that I'm working on......are you talking about finding if the two layers (bitmapdatas) overlap by using bitmapdata.hitTest method??.....if so, the problem I run into w/ that is that it doesn't return coordinates for where the hitTest has occured.......but I supposed if there is a hitTest between the bitmaps, one can figure out where the ship is at as a obj, and run through the bullet objects to find the closest one to the ship, if that's what you're refering to.........

@ squize:.....am I interpreting that right, as far as your collision method used in polarity?


thanks,

paul.

performing getColorBoundsRect i'vw found can greatly reduce performace because of the drawing of two movieclips, applying color transformations and positions. Even if your running the method on two bitmaps using copyPixels its still slow.

maybe you could run a hitTest then perform getColorBoundsRect to get the exact position.

Quote:

---

Originally Posted by mr_malee

performing getColorBoundsRect i'vw found can greatly reduce performace because of the drawing of two movieclips, applying color transformations and positions. Even if your running the method on two bitmaps using copyPixels its still slow.

maybe you could run a hitTest then perform getColorBoundsRect to get the exact position.

---

no, I wouldn't use the getColorBoundsRect method for collision detection.... I think the bitmap hitTest method is faster and much easier to use ....that's what I was refering to above.....

paul.

My little brick on the wall of this interesting topic.

As you know the speed of the bullet to test and the maximum speed of the player ship, you can know how many frame you must wait before a possible collision you can wait. Then you can add a paraemter for each bullet "To be testes on frame number X". Bullet that are far away from the player, will be tested maybe 10 to 30 frames later. I didn't test this but I'm pretty sure you can improve a lot your tests with this.


Of course should use this in addition to the screen partitioning method in several areas.

I agree with TonyPa that collision test is very often a minor issue comparing to rendering. However, it can become significant if you manage several players ships with a lot of bullets to test.

I used this code ( Slightly condensed here ) in Polarity,

colourTransform=new ColorTransform(1,1,1,1,255,255,255,255);
var mat:Matrix=new Matrix();
mat.tx = sprite._x;
mat.ty = sprite._y;
collisionBitmap.draw(sprite,mat,colourTransform,"d ifference",new Rectangle(0,2,512,448));

var intersection:Rectangle = collisionBitmap.getColorBoundsRect(0xFFFFFFFF,0xFF 00FFFF);
if(intersection.x==0){
return;
} else {
//collision

So I plot the player sprite / bullets into the collisionBitmap as simple rectangles and then each baddie tests against that bitmap to see if it's hit anything, and from there it works out what.
Not the quickest approach, but really accurate ( And what the client wanted, I wasn't allowed to just do a tile based level of accuracy ).

Squize.