Jump to content

[TOPIC: topicViewTemplate]
[GLOBAL: userSmallPhoto]
Photo

Removing an object from a table question
Started by d.mach Oct 10 2018 02:52 AM

- - - - -
23 replies to this topic
table remove object
[TOPIC CONTROLS]
[/TOPIC CONTROLS]
[modOptionsDropdown]
[/modOptionsDropdown]
[reputationFilter]
[TOPIC: post.html]
#1

d.mach

[GLOBAL: userInfoPane.html]
d.mach
  • Contributor

  • 784 posts
  • Corona SDK

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?



[TOPIC: post.html]
#2

nick_sherman

[GLOBAL: userInfoPane.html]
nick_sherman
  • Corona Geek

  • 1,686 posts
  • Corona SDK

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.



[TOPIC: post.html]
#3

Michael Flad

[GLOBAL: userInfoPane.html]
Michael Flad
  • Contributor

  • 210 posts
  • Corona SDK

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

 

I.e.

local numEnemies = #myEnemies
myEnemies[deleteIdx] = myEnemies[numEnemies]
myEnemies[deleteIdx].index = deleteIdx -- update the index to the new slot
myEnemies[numEnemies] = nil

 

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.


  • agramonte likes this

[TOPIC: post.html]
#4

nick_sherman

[GLOBAL: userInfoPane.html]
nick_sherman
  • Corona Geek

  • 1,686 posts
  • Corona SDK

Nice!



[TOPIC: post.html]
#5

anaqim

[GLOBAL: userInfoPane.html]
anaqim
  • Contributor

  • 726 posts
  • Corona SDK

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  :)



[TOPIC: post.html]
#6

d.mach

[GLOBAL: userInfoPane.html]
d.mach
  • Contributor

  • 784 posts
  • Corona SDK

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!



[TOPIC: post.html]
#7

d.mach

[GLOBAL: userInfoPane.html]
d.mach
  • Contributor

  • 784 posts
  • Corona SDK

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.

 

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?



[TOPIC: post.html]
#8

Michael Flad

[GLOBAL: userInfoPane.html]
Michael Flad
  • Contributor

  • 210 posts
  • Corona SDK

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.

 

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.



[TOPIC: post.html]
#9

nick_sherman

[GLOBAL: userInfoPane.html]
nick_sherman
  • Corona Geek

  • 1,686 posts
  • Corona SDK

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?

 

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



[TOPIC: post.html]
#10

d.mach

[GLOBAL: userInfoPane.html]
d.mach
  • Contributor

  • 784 posts
  • Corona SDK

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?

 

?



[TOPIC: post.html]
#11

nick_sherman

[GLOBAL: userInfoPane.html]
nick_sherman
  • Corona Geek

  • 1,686 posts
  • Corona SDK

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



[TOPIC: post.html]
#12

roaminggamer

[GLOBAL: userInfoPane.html]
roaminggamer
  • Corona Geek

  • 7,484 posts
  • Corona SDK

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.

  • Michael Flad and agramonte like this

[TOPIC: post.html]
#13

roaminggamer

[GLOBAL: userInfoPane.html]
roaminggamer
  • Corona Geek

  • 7,484 posts
  • Corona SDK

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.



[TOPIC: post.html]
#14

roaminggamer

[GLOBAL: userInfoPane.html]
roaminggamer
  • Corona Geek

  • 7,484 posts
  • Corona SDK

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.


  • agramonte likes this

[TOPIC: post.html]
#15

roaminggamer

[GLOBAL: userInfoPane.html]
roaminggamer
  • Corona Geek

  • 7,484 posts
  • Corona SDK

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?



[TOPIC: post.html]
#16

d.mach

[GLOBAL: userInfoPane.html]
d.mach
  • Contributor

  • 784 posts
  • Corona SDK

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


[TOPIC: post.html]
#17

roaminggamer

[GLOBAL: userInfoPane.html]
roaminggamer
  • Corona Geek

  • 7,484 posts
  • Corona SDK

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.



[TOPIC: post.html]
#18

nick_sherman

[GLOBAL: userInfoPane.html]
nick_sherman
  • Corona Geek

  • 1,686 posts
  • Corona SDK

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.



[TOPIC: post.html]
#19

d.mach

[GLOBAL: userInfoPane.html]
d.mach
  • Contributor

  • 784 posts
  • Corona SDK

 

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.

 

One question:

for what is the following part in the code:

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

?



[TOPIC: post.html]
#20

davebollinger

[GLOBAL: userInfoPane.html]
davebollinger
  • Corona Geek

  • 1,296 posts
  • Enterprise

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.



[TOPIC: post.html]
#21

d.mach

[GLOBAL: userInfoPane.html]
d.mach
  • Contributor

  • 784 posts
  • Corona SDK

Got it! Thanks for all your help!

I somewhere had a reference to objects, so they didn't get cleared the right way, when being removed. I now have implemented the code RoamingGamer suggested (Thanks a LOT for this!) and will make the changes to the complete game in the next days. It now works fine regarding the memory and the system memory is now steady because when an enemy is getting destroyed or removed the memory clears.



[TOPIC: post.html]
#22

roaminggamer

[GLOBAL: userInfoPane.html]
roaminggamer
  • Corona Geek

  • 7,484 posts
  • Corona SDK

The answer to your question is on the API page:

 

 

This event is delivered to a display object when ...  removed ... This is useful if you have cleanup ...

 
 
In the code above, all enemies have a finalize listener attached, so when they are deleted it executes and they remove their reference from the enemies table.
 
 
Open up a blank project and put this in main.lua to help you understand.
 
local obj = display.newCircle( 100, 100, 10 )

function obj.finalize( self )
  print (" Deleting object ", self, " @ ", system.getTimer() )
end
obj:addEventListener("finalize")

print("Created and set up object ", obj, " @ ", system.getTimer() )
display.remove(obj) 

 
 


[TOPIC: post.html]
#23

d.mach

[GLOBAL: userInfoPane.html]
d.mach
  • Contributor

  • 784 posts
  • Corona SDK

Thank you!



[TOPIC: post.html]
#24

hhharper8

[GLOBAL: userInfoPane.html]
hhharper8
  • Observer

  • 2 posts
  • Corona SDK

Thanks!!!











-------------------------

compare and contrast essay sample




[topic_controls]
[/topic_controls]

Also tagged with one or more of these keywords: table, remove, object