Removing an object from a table question

Solar2D General Questions/Discussion
#1

Quick note:

In my game I have a lot of enemy waves attacking by moving along a path.

I create enemies and also store a ref to the enemies in a table, so I can do the collision detection with a for loop cycling through the ref table.

Because of performance issues I now want to remove destroyed enemies not only but also from the ref table. With more than 1000 enemies created the performance drops.

My question:

Is there a way to store the new created enemies in a ref tabe and “safely” remove them from this array fast! So this array can be used to do a collision check with a circle circle collision detection (not physics)?

Right now I just store every enemy in the array (means a reference) which get’s too much with a LOT of enemies. I should remove the destroyed enemies from this ref table also, but how can I do this in a fast way and still use the table to do the collision check?

I also don’t know how to get the correct index for an enemy to remove from the ref table.

When creating an enemy and giving it an index with enemy.index=x removing this enemy from the ref table with table.remove (reftable,enemy.index) will only work ONCE and the stored indexes get messed up.

How can I still remove enemies from the ref table with the correct index?

And is there a faster way to do this without using the table.remove?

#2

I saw a post from RoamingGamer the other day which mentioned he would use the object itself as the key in the table. Then you can just remove it by doing myTable[myObject] = nil, and use in pairs to iterate over the table instead of a for loop.

#3

Don’t remove the destroyed enemy but replace it with the last enemy within your array.

I.e.

[lua]

local numEnemies = #myEnemies

myEnemies[deleteIdx] = myEnemies[numEnemies]

myEnemies[deleteIdx].index = deleteIdx – update the index to the new slot

myEnemies[numEnemies] = nil

[/lua]

This way, the removal is a constant time operation, all entities but the one moved into the free slot keep their index and the moved one gets the new index.

#4

Nice!

#5

Thats a bit too generalized info which can result in many different scenarios, which I doubt anyone will sit down and type out.

A more specific problem situation and code sample is likely to let people give a more short and targetted response.

Unless you get RG on it, he’s probably gona write you an essay on the subject  :slight_smile:

#6

Thanks for you help!

@Michael This looks like a very easy to implement solution, but I have some bullets moving around which will have a ref to the enemy they are aiming at which makes this a little bit hard to implement with the existing code.

@nick_sherman I will look into this!

#7

so what do I have to do to get the length for this table then?

Example: when doing this… #Enemy I always get 0 now!

How can I get the length of this new table using the objects itself?

#8

That’s as simple, just add a list of bullets to update to each enemy. The update/handling of the array is basically the same.

Whenever a bullet selects an enemy, add it to the list, and remove it when you destroy the bullet (or it follows another target).

On destruction of the enemy, update each bullet in the list and on destruction of a bullet, update the list in the enemy.

#9

You don’t need to know the length of the table, you just iterate over it using k,v in pairs.

#10

so doing

for k,v in pairs (Enemy) do ... end

should do the job, right? But how can I now get the correct Enemy from the table to do the collision detection?

Is it via

for ...      Enemy[v] end

is this giving me the Enemy I want to check with?

Or is it Enemy[k] or something else?

And how do I delete later?

?

#11

In this instance both k and v will represent the enemy - the key is the enemy, the value is also the enemy.

#12

I’m late to the party, but I suggest not using numeric indices unless order of calculations matters.

i.e. do this:

local enemies = {} local function makeEnemy( ... ) -- args up to you local enemy display.new ... code to make enemy enemies[enemy] = enemy -- Index by enemy not a number function enemy.finalize(self) enemies[self] = nil end; enemy:addEventListener("finalize") return enemy end ... later local anEnemy = makeEnemy() -- Now it is in the enemies table display.remove( anEnemy ) -- Now it is not. Automatically.
#13

Tip:  For small tables (those with around a few thousand entries or less) there is a negligible speed difference between numerically indexed and object indexed tables.

For games, I never choose an indexing system based on speed.  I choose it based upon how it affects my game mechanics and on whether it makes coding hard or easy.

By the time you have enough object references in your table where speed of iteration is a problem, you’ll be out of memory from creating all those objects.

#14

I don’t think table iterations should have anything to do with your speed, although I do think a numerically indexed table is the wrong way to go.

More likely to be affecting your speed are these things (in order of likelihood):

  • The rendering
  • The calculated collision test you mentioned.
  • The transitions

Question:   How are you doing your (within radius) collision detection calculation.

Please tell me you’re using squared lengths. i.e I hope you are not using math.sqrt() in this test.

In fact, please show you’re algorithm.

#15

Here is an example that shows:

  1. How to efficiently do a within radius calculation minus the square root calc one might normally use.

  2. How rendering display objects dominates over the choice of loop indexing and iteration

  3. Re-inforces #2 with the use of ‘fake’ objects to show how a large table of tables is fast to iterate over.

https://github.com/roaminggamer/RG_FreeStuff/raw/master/AskEd/2018/10/efficiencyTest.zip

To test this, first run the demo with ‘useRealObjects’ set to ‘true’.  Tap right side of screen to increase max objects, left to decrease.

Slowly increase till your FPS dips and stays below 60.  Note the ‘target’ number of the left bottom.

Repeat with  ‘useRealObjects’ set to ‘false’ (this uses tables so it looks boring).  Notice how at the same target number your FPS is still fine?

https://www.youtube.com/watch?v=439lAISwYko&feature=youtu.be

#16

Wow thanks!

My collision code I am using is optimized and not the problem. no math functions… just a position check based on distances of objects to each others.

But I’m doing this check inside a for loop which is going to all the enemies.

Now with using the pairs version for the ref table the game is faster in higher levels a lot! BUT: I get lags when enemies are spawned.

Is there a way to use some faster alternate version to something like this without the slow pairs?

for k,v in pairs (Enemyreflist) do ... end
#17

How many objects are you iterating over per frame?  Try to give an exact maximum count or at least a pretty-sure count.

I’m asking because in my experience pairs() is plenty fast so I have to wonder if there is some other issue going on.

#18

For 99.9% of uses pairs() is fast enough.

I had a situation once where an inner in-pairs loop over a small number (6) of known keys, but done many thousands of times (up to 50 matches, 18 times per match x 11 players x 18 attributes) was a bottleneck.

By storing the key names in a separate numerically indexed table and iterating over this in a for loop to access the keys directly, I shaved fractions of a millisecond per operation and halved overall processing time.

#19

One question:

for what is the following part in the code:

function enemy.finalize(self) enemies[self] = nil end; enemy:addEventListener("finalize")

?

#20

the real question is why are there “more than 1000 enemies” - that seems like an unrealistically large number on screen

suspect that’s the “entire population” for the “entire wave”, with some perhaps far offscreen, yet still participating in the collision test, likely with doubly nested loops over the entire population (so 1000*1000 tests - now THERE’s enough to notice a performance hit)

if instead you kept (and managed) a separate list of enemies “within the viewport” then life would be much simpler

and if you happened to have them in an indexed list than you could reduce the inner collision loop to a triangular array

in short:  you could optimize the list storage/retrieval all you want, but to no real practical effect if the problem is at a “higher level” (ie, if you can’t fix what i suspect is an O(n2) problem in the collision loops, then worrying about the performance of pairs() is moot)

[EDIT]  nah, it’s probably not quite that bad, as you don’t actually say you’re colliding enemy-vs-enemy.  so ignore the O(n2) and triangular array bits, but if you’re still colliding something like 100 bullets vs 1000 enemies, where maybe half or more of those enemies are offscreen, then the rest still applies – the fastest way to do something is to not do it.