Best practice for destroying enemies in array

[vreahli]

Heya! First few days with Love2d here - I was wondering what the 'right' way to remove an object from a table is. I'd like to destroy it at the "destroy here..." point.

Also any ideas about best practices or what to read up on for larger love2d oriented games, I'd love to hear.

Thanks in advance!

Code: Select all

-- Bubbles
io.stdout:setvbuf("no")

local bubbles_spritesheet
local tileSize = 16
local currentSprite = 1
local bubbles = {}

local bubbles = {}

local Bubble = {}

function Bubble.new(x, y)
	local self = self or {} -- If I don't exist yet, make yourself
	self.animations = {
		floating = {
			frames = {
				getRect(0, 0)
			}
		},
		bursting = {
			frames = {
				getRect(0, 1), getRect(0, 2), getRect(0, 3)
			},
			endAction = "destroy"
		}
	}

	self.animation = {}
	self.animation.name = "floating"
	self.animation.frame = 1
	self.dt30 = 0
	self.x = x
	self.y = y
	self.age = 0;

	self.update = function(dt)
		self.dt30 = self.dt30 + dt * 30;
		if self.dt30 > 1 then
			self.dt30 = self.dt30 - 1 -- assumption that we shouldn't get more than a second out of whack
			self.advanceFrame()
		end

		self.y = self.y - dt * 30 - (math.random() -.2) * 3
		self.x = self.x + (math.random() -.2) * dt * 100

		self.age = self.age + dt;

		if(self.age > 3) then
			self.animation.name = "bursting"
		end

	end

	self.advanceFrame = function()
		local anim = self.animations[self.animation.name]
		local length = table.getn(anim.frames)
		if self.animation.frame < length then
			self.animation.frame = self.animation.frame + 1
		else
			if anim.endAction then
				print("destroy here...")
			end
			self.animation.frame = 1
		end
	end

	self.draw = function()
		local anim = self.animations[self.animation.name]

		local q = anim.frames[self.animation.frame]
		love.graphics.draw(bubbles_spritesheet, q, self.x, self.y, 0, 2, 2)
	end

	return self
end



function love.load()
	love.graphics.setDefaultFilter("nearest", "nearest", 1)
	bubbles_spritesheet = love.graphics.newImage("bubbles_16.png")
	aBubble = Bubble.new(200, 200)

	for i = 0, 200 do
		local b = Bubble.new(0 + math.random() * 700, 500 )
		table.insert(bubbles, b)
	end
end

function love.update(dt)
	for k, b in pairs(bubbles) do
		b.update(dt)
	end
end

function love.draw()
	for k, b in pairs(bubbles) do
		b.draw()
	end
end

function getRect(sx, sy)
	local left = sx * tileSize
	local top = sy * tileSize
	local quad = false;
	quad = love.graphics.newQuad(left, top, tileSize, tileSize, bubbles_spritesheet:getDimensions())
	return quad
end

[AnRu]

To remove element from lua table use table.remove function. It takes table and position of the element and return deleted element.
But from here, lua autors reccomended to use assigning to nil last element to remove it.

The Lua authors recommend using this method for removing from the end of a table nowadays:

Code: Select all

t [#t] = nil  -- remove last entry

Note that for other keys (eg. strings) you simply assign nil to the element to remove it. For example:

Code: Select all

t = {}
t.foo = "bar"  -- add item
t.foo = nil    -- remove item

[Plu]

Note that if you want to remove items in a loop, you have to loop backwards, because table.remove will update the indexes and mess everything up.

A common example of removing entities is to flag entities that need to be cleaned/removed from whatever code you have, and then run over all entities in the update function and remove them from the table if needed. Something like this:

Code: Select all

entities = { entity1, entity2, entity3 }

love.update = function(dt)
  entity2.flagClean = true -- this will mark entity3 from cleanup

  for i = #entities, 1, -1 do
    if entities[i].flagClean then
      table.remove( entities, i )
    end
  end

end

[4aiman]

Since the topic is "best practice" I'd like to suggest this as an answer. Note the comments on table.remove there.

[kikito]

Does it have to be an array? I find adding and removing faster and easier to do when the enemies are the keys of the table instead of its values (that is a hash or a dictionary instead of an array):

Code: Select all

local enemies = {}

...

enemies[enemy1] = true -- add 1
enemies[enemy2] = true -- add 2

...

-- Draw all enemies 
for enemy,_ in pairs(enemies) do
  drawEnemy(enemy)
end

...

enemies[enemy1]  = nil -- remove 1

[zorg]

Otherwise, if you need order, but want speed too, then you can sacrifice space instead; have both an ordered array and a hash "map", and use whichever when it's best suited for a specific job. At least in theory, it could work.

[MadByte]

Does it have to be an array? I find adding and removing faster and easier to do when the enemies are the keys of the table instead of its values (that is a hash or a dictionary instead of an array):

Code: Select all

local enemies = {}

...

enemies[enemy1] = true -- add 1
enemies[enemy2] = true -- add 2

...

-- Draw all enemies 
for enemy,_ in pairs(enemies) do
  drawEnemy(enemy)
end

...

enemies[enemy1]  = nil -- remove 1

I can't believe I didn't knew that this is possible... *mind blown*

[airstruck]

I can't believe I didn't knew that this is possible... *mind blown*

Be aware that pairs is really slow compared to ipairs, and it won't JIT, so it can even make other code around it slower. If you don't care about the order the enemies are in, but you need to iterate them, and you don't actually need a hash map, you're better off going with an array and removing elements by copying the last element into the index you want to remove and then setting the last element to nil (a method slime suggested once, I believe).

Otherwise, if you need order, but want speed too, then you can sacrifice space instead; have both an ordered array and a hash "map", and use whichever when it's best suited for a specific job. At least in theory, it could work.

That can work well for fast iteration and fast lookup; here's an example of how it can look. It's not going to help with fast removal, though. In fact if the values in the hash part are the numeric table indices, it'll slow down removal since you need to update them all. If the values are something like true it won't slow down removal, but won't speed it up any either; you'll still need to remove the item from the array part.

Since the topic is "best practice" I'd like to suggest this as an answer. Note the comments on table.remove there.

A simpler variation of this that can be faster than the usual "reverse-iterate and table.remove" approach in many cases is simply creating a new array with only the stuff you want to keep. You'd have to check whether this is actually faster in your particular scenario, but I've found it to be pretty efficient when removing more than one or two things from a relatively small list. This can have other benefits as well, for example it can be combined with memoization.

[vreahli]

Thanks for all the help guys! @_@ This helped a ton, I didn't expect such a huge response. You guys rock!

So, here's the solution I settled on (for now, at least!)

First off, I flagged old bubbles as deletable...

Code: Select all

	-- Inside bubble
	self.advanceFrame = function()
		local anim = self.animations[self.animation.name]
		local length = table.getn(anim.frames)
		if self.animation.frame < length then
			self.animation.frame = self.animation.frame + 1
		else
			if anim.endAction then
				self.deletable = true
			end
			self.animation.frame = 1
		end
	end

As well as moved it in to a function in case I need to do any logic.

Code: Select all

	-- Inside bubble
	self.isDeletable = function()
		return self.deletable
	end

Also, in the draw and update, I had it check the delete flag to prevent it from rendering or updating dead objects.

Code: Select all

	self.draw = function()
		if self.isDeletable() then
			return false
		end

In the main loop, I set up a check to see if a certain amount of time had passed to do cleanup.

Code: Select all

	globalTime = globalTime + dt

	if globalTime > cleanupWait then
		bubbleCleanup()
		globalTime = 0
	end

The cleanup method iterates through the number of bubbles backwards (thanks! That would've driven me nuts) and removes them.

Code: Select all

function bubbleCleanup()
	print("bubbles before cleanup: " .. #bubbles)
	for i = #bubbles, 1, -1 do
		if bubbles[i].isDeletable() then
		    table.remove( bubbles, i )
		end
	end
	print("bubbles after cleanup: " .. #bubbles)
end

Here's the complete code for anyone curious about it all working together that swings by this thread at a later date. I'm really looking forward to playing with this more and building some full games. I'm having a blast.

Code: Select all

-- Bubbles
io.stdout:setvbuf("no")

local bubbles_spritesheet
local tileSize = 16
local currentSprite = 1
local bubbles = {}
local globalTime = 0
local cleanupWait = 2

local bubbles = {}

local Bubble = {}

function Bubble.new(x, y)
	local self = self or {} -- If I don't exist yet, make yourself
	self.animations = {
		floating = {
			frames = {
				getRect(0, 0)
			}
		},
		bursting = {
			frames = {
				getRect(0, 1), getRect(0, 2), getRect(0, 3)
			},
			endAction = "destroy"
		}
	}

	self.animation = {}
	self.animation.name = "floating"
	self.animation.frame = 1
	self.dt30 = 0
	self.x = x
	self.y = y
	self.age = 0;
	self.deletable = false;

	self.update = function(dt)
		if self.isDeletable() then
			return false
		end

		self.dt30 = self.dt30 + dt * 30;
		if self.dt30 > 1 then
			self.dt30 = self.dt30 - 1 -- assumption that we shouldn't get more than a second out of whack
			self.advanceFrame()
		end

		self.y = self.y - dt * 30 - (math.random() -.2) * 3
		self.x = self.x + (math.random() -.2) * dt * 100

		self.age = self.age + dt;

		if(self.age > 3) then
			local doBurst = math.random()
			if doBurst > 0.95 then
				self.animation.name = "bursting"
			end
		end

	end

	self.advanceFrame = function()
		local anim = self.animations[self.animation.name]
		local length = table.getn(anim.frames)
		if self.animation.frame < length then
			self.animation.frame = self.animation.frame + 1
		else
			if anim.endAction then
				self.deletable = true
			end
			self.animation.frame = 1
		end
	end

	self.draw = function()
		if self.isDeletable() then
			return false
		end

		local anim = self.animations[self.animation.name]

		local q = anim.frames[self.animation.frame]
		love.graphics.draw(bubbles_spritesheet, q, self.x, self.y, 0, 2, 2)
	end

	self.isDeletable = function()
		return self.deletable
	end

	return self
end

function bubbleCleanup()
	print("bubbles before cleanup: " .. #bubbles)
	for i = #bubbles, 1, -1 do
		if bubbles[i].isDeletable() then
		    table.remove( bubbles, i )
		end
	end
	print("bubbles after cleanup: " .. #bubbles)
end

function love.load()
	love.graphics.setDefaultFilter("nearest", "nearest", 1)
	bubbles_spritesheet = love.graphics.newImage("bubbles_16.png")

	makeBubbles()
end

function makeBubbles()
	bubbles = {}
	for i = 0, 500 do
		local b = Bubble.new(0 + math.random() * 700, 600 )
		table.insert(bubbles, b)
	end
end

function love.update(dt)
	for k, b in pairs(bubbles) do
		b.update(dt)
	end

	globalTime = globalTime + dt

	if globalTime > cleanupWait then
		bubbleCleanup()
		globalTime = 0
	end

	if #bubbles == 0 then
		makeBubbles()
	end
end

function love.draw()
	for k, b in pairs(bubbles) do
		b.draw()
	end
end

function getRect(sx, sy)
	local left = sx * tileSize
	local top = sy * tileSize
	local quad = false;
	quad = love.graphics.newQuad(left, top, tileSize, tileSize, bubbles_spritesheet:getDimensions())
	return quad
end

[MadByte]

Here is another way I usually use if the game I'm working on allows it.

RemoveObjects.love

(1.54 KiB) Downloaded 212 times

Basically I'm creating a "World" which manages all objects. It also updates all of them and checks if the object has been removed.

Code: Select all

function Object:destroy()
  self.removed = true
  -- Remove collision object (i.e when using bump) or do other stuff when destroying the object
end

Code: Select all

function World:update(dt)
  for i=#self.objects, 1, -1 do
    local object = self.objects[i]
    if not object.removed then
      if object.update then object:update(dt) end
    else
      table.remove(self.objects, i)
    end
  end
end