[help] hittest VS array checks

[Ray Beez]

Hey, what would be quicker/more optimized:

I have a thingy that the player moves and shoot from. The bullets shoot up and can hit objects in the playfield. The playfield is stored as a grid array.

Now, I can detect objects two ways:

1. Move the bullet as an MC... test for collision with hitTest() ... Then figure out where in the array that object is and remove it.

or

2. Based on the bullet X,Y I can check the grid cell it's overlapping, and see if that grid cell contains an object. If so, then I remove it (hit!).

So which is faster. Doing hittest all the time, then looking up the array, or looking up the array all the time?

:-)

[Incrue]

Array.
Isnt that the reason why they say:You should use tiles you should use tiles
But even this way i would rather to use hitTest, if you have 20, hitTests each frame its still not such a great problem, and i bet you have less them 20 bullets in the screen at the same time

[Ray Beez]

There is only ever 1 bullet.

[ozmic66]

try placing all of the objects in the game in one movieclip (if it's a\not already set up that way)

and then do a hittest of the bullet against that mc only

if there is a hit then do a hittest with every obj in the array
or if you want a speed up, do the grid deal

[tonypa]

If you have the grid why would you need an array? Grid itself is enough to know which object sit where, if you want to check for object in x=2, y=1 then you only need to check if enemy1_2 exists or not. The array is only good when objects can move freely and no grid is used.

[artlink]

The fastest way would probably be not to check all the object but the ones that are close to the bullet

so, using a grid 10x10, 50 pixels for each square width/height, what about:

1) dividing the grid in horizontal strips (50*500)
2) create 10 arrays containing the infos for each strip
3) check only 1 strip/array at the time according to the bullet._y
--> check only 10 out of 100

this can be still subdivide and bla bla bla

Anyone been through that path before?

[Define_Robert]

The fastest way would probably be not to check all the object but the ones that are close to the bullet

so, using a grid 10x10, 50 pixels for each square width/height, what about:

1) dividing the grid in horizontal strips (50*500)
2) create 10 arrays containing the infos for each strip
3) check only 1 strip/array at the time according to the bullet._y
--> check only 10 out of 100

this can be still subdivide and bla bla bla

Anyone been through that path before?

If you shoot exactly between 2 'strips' then you check 20 out of 100 right?

[Squize]

"Anyone been through that path before?"

Yep, done it for quite a few shoot'em ups ( Even for a platform game ).

Give's a huge speed increase, and from knowing exactly what mc's are in one sector you can just use hitTest against them which is nice and quick.

Squize.

[Ray Beez]

If you have the grid why would you need an array? Grid itself is enough to know which object sit where, if you want to check for object in x=2, y=1 then you only need to check if enemy1_2 exists or not. The array is only good when objects can move freely and no grid is used.

I thought a grid and array were the same thing. Are you saying it's faster to create a "simulated" array out of variables instead of a real array?

[tonypa]

I thought a grid and array were the same thing. Are you saying it's faster to create a "simulated" array out of variables instead of a real array?

Array is only needed if you need the objects to be in some kind of order. Each element in the array should be somehow related to its 2 neighbours.

Array could be used for example to keep track of distance to every object from one point, first element in the array would always be closest to point and last element in array furthest. So to check if ANY object is close enough to point you only need to check first element in the array.

When the objects are not in any specific order, then there is no need for array. Bunch of enemies on stage, moving around, totally unrelated to each other, then you can simply put them all into one container (container can be either movie clip or object) and use for..in loop to go through every enemy.

The main improvement compared to array is when you start to add and remove objects. By using simple container you only need to delete or add an object, while for the array every time something is added or removed you re-sort the array to make sure order in the array is kept correct. The sorting happens automatically whenever array changes and it takes time and it gets slower and slower with more objects.

Getting back to grid. Lets suppose enemies are not moving, once they are created they stay in their position and they can only be at certain steps. So, this becomes tile-based system where every enemy has name according to its position. If there is enemy at 0,0 cell then the name of this enemy is "enemy0_0" and to find if there is enemy you only need to check if "enemy0_0" exists. No array, no loops, very fast and simple.

Now if the enemies are moving and can be at any coordinates then you could still use their names to reflect their position. Every time enemy moves, its name is changed to its new x/y coordinates (only you have to make sure 2 enemies never appear at same coordinates or they would get same name and the game is messed up). Anyway, lets say "enemy102_256" which was at _x=256, _y=102 moved one pixel up and is now at _x=256, _y=101, so it will be renamed to "enemy101_256". Now if bullet is moving in the stage you can use coordinates of the bullet and size of enemies to check if any enemy is around the bullet. If for example bullet is point (_y=102, _x=250) and enemies have width of 2 and height of 2 (and enemies are centered) all you have to do to find if any enemy collides with bullet is to check if 9 enemies around the bullet exist: "enemy102_250", "enemy101_250", "enemy103_250", "enemy102_251", "enemy101_251", "enemy103_251", "enemy102_249", "enemy101_249", "enemy103_249". Doesnt matter how many enemies are on stage, you still always check for only 9 enemies. Obviously this gets slow with fewer and larger enemies, but with large number of small enemies this can be very fast.

Next, the grid with moving enemies. Its usually expected that size of enemies is less then size of grid cells. This means each enemy can be in 1, 2 or 4 grid cells. When enemy moves, it delets itself from grid cells it used to be and marks itself being in the grid cells for each of its 4 corners for its new position. Grid cells itself does not have to be array, as I pointed out before they do not keep enemies in any order. All you need to know is if enemy is in the cell or not, so cells can be simple objects. Now for the bullet to check for all enemies it only needs to check 4 cells around it.

[Ray Beez]

Unbelievable! Great "trick" there, naming objects with their XY.
Amazingly that's sort of how I was doing it in Flash 4 for my Cubes game (non-moving objects in a grid). I name the objects with their grid position. But I did not go so far as renaming them when they moved!

I'm just blown away by how simply clever that is... wow.
:-D