BulletManager (performance argument)

[JohnnyC]

My Shmup code is starting to look like spaghetti so I was rewriting my entire bullet module. However I'm not entirely sure what the best way to go by doing this is.

I want to preload a table with like 10,000 bullets with an alive == false value. Then when createBullet() is called instead it just looks for the first index with alive == false and makes it true after changing some values.

Then later I have a removeBullet() function that turns true back into false. My issue is, is it okay to be iterating through such a big table so frequently?

Would sorting it by false/true be faster or slower?
Would it be better to go back to constantly adding/removing tables?
Is there a better 4th option?

no .love file because this is all theorycraft and I don't actually have any code written down yet. Just been searching the archive of threads.

[zorg]

Bullets may theoretically vanish in many ways:
- Go far enough outside the visible area's bounds
- It's time ran out
- It collided
- something else

All of the above probably happens in a loop that goes over bullets and calls its update or whatever function per frame, so you're not using more than one loop, which is good.

You could use two tables, one to hold all bullets (a pool) and one that only holds the active ones (that you iterate over); if an active one vanishes, you don't do anything to it, instead, if you need to start one, go through the elements, and replace the first one that has its alive state set to false.

This may or may not be more performant that just iterating over a gigantic table, that said, most touhou games use at max 2000 bullets, and with only positioning, löve can handle around 44k bullets (on my computer anyway), so your mileage may vary.

[JohnnyC]

44K bullets? I'm curious on your computer lol because I have performance issue at 2.5k bullets which is why I started looking for another way to deal with bullets. That said I started using anim8 and not generating tons of newImage calls (which in hindsight should've been obviously silly), so that most likely was the problem as well. How would you do the two tables? Isn't that essentially inserting to a second table with information from the first?

[zorg]

Yes, and since tables are passed by reference (a pointer -> a number basically), whether one or two references exists, they won't occupy tooo much space.

As i said, 44K was only achievable with me only drawing circles made out of meshes (could probably have textured them), and it only had linear movement logic, so not too many things to calculate. I didn't use animate either, just draw-ed them to the screen.

If/When you have some code, i could take a look at it.

CPU is a core i7 4820K (3.7GHz) with 8 cores, that being irrelevant since my code wasn't threaded.

[JohnnyC]

Here is the code I have so far

in load I populate the bullets to be used.

Code: Select all

function bulletInformation()
	for i=1,20000 do
		bulletTablePopulate()
	end
end

Enemies call testFire and fire when the timer hits 0.

Code: Select all

function enemyTestFire(v)
	if v.timer > 0 then
		v.timer = v.timer - 0.1
	else
		bulletCreate2(v.x,v.y,0,100,0)
		v.timer = 1
	end
end

Before I create the bullet I iterate through the bullets table til I find the first dead bullet and then I break out of the while loop returning the index of the dead bullet.

Code: Select all

function findDeadBullet()
	local k = 0
	local x = false
	while x == false do --search table til you find an index that is true.
		k = k + 1
		if bullets2[k].alive == false then
			break
		end
	end
	i = k 
	return i
end

I then fill the information and set it to alive.

Code: Select all

function bulletCreate2(startX,startY,veloX,veloY,img)
findDeadBullet()
local t = bullets2[i]
t.x = startX
t.y = startY
t.veloX = veloX
t.veloY = veloY
t.graphics = testSprite
t.alive = true
test = i
end

During the update I iterate through the table with ipairs and update the position of the bullet if it is alive.

Code: Select all

for i,b in ipairs(bullets2) do
	if b.alive == true then
		fireTesting(b,dt)
	end
end

Then I draw the bullet only if it is alive.

Code: Select all

for i,b in pairs(bullets2) do
	if b.alive == true then
		love.graphics.draw(b.graphics, b.x, b.y, 0, 1, 1, 0, 0)
	end
end

I don't really have a way to remove bullets yet but it works pretty well.

EDIT: Here is the code firing tons of bullet at once and happily not dipping under 60 fps. Though the bullet logic in this test code has minimal math.
https://love2d.org/imgmirrur/ZukIpbu.png

[drunken_munki]

I do something like this for all of my interactive things, it may give you ideas or not. I've just made this example up (I don't have bullets in my own game):

Code: Select all

local TABL_BULLET = {}
local rollingBulletCount = 0
local minRollingBulletCount = 1

function resetGame()
	TABL_BULLET = {}
	rollingBulletCount = 0
	minRollingBulletCount = 1
end

function updateGame(dt, cameraX, cameraY)
  for i = minRollingBulletCount, rollingBulletCount do
    local o = TABL_BULLET[i]
    if o ~= nil then
      local alive = true
      
      -- Update
      if o.life > 0 then
         o.life = o.life - dt
         if o.life <= 0 then
           alive = false
           removeBullet(i)
         end
      end
        
      if alive == true then
          o.x = o.x + (o.dx * dt)
          o.y = o.y + (o.dy * dt)
          o.drawX = o.x - cameraX
          o.drawY = o.y - cameraY

          -- Check if visible/drawable
          o.draw = visibleInScreen(o.drawX, o.drawY, o.w, o.h) -- Magick function to check against screen bounds (Returns boolean)
      end

    end
  end
end

function drawGame()
  for i = minRollingBulletCount, rollingBulletCount do
    local o = TABL_BULLET[i]
    if o ~= nil and o.draw == true then
      -- Draw
      draw(o.image, o.drawX, o.drawY)
    end
  end
end

function spawnBullet(x, y, bulletImage, dx, dy, life)
  minRollingBulletCount = minRollingBulletCount + 1
  TABL_BULLET[minRollingBulletCount] = {  
                                          image   = bulletImage, -- <- whatever a quad or other global/local 
                                          x    = x, 
                                          y    = y,
                                          w = 1,
                                          h = 1,
                                          dx   = dx, 
                                          dy   = dy,
                                          life = life or -1 -- Life -1 would not be removed by timer
                                        }
end

function removeBullet(index)
  TABL_BULLET[index] = nil
  if index == minRollingBulletCount then
    minRollingBulletCount = index + 1 -- Change the start index for efficiency
  end
end

Now, I've done it this way to avoid using ipairs() which is incredibly slow. I try to change the start index when a bullet is removed by the life field or it could be called manually upon a collision. The problem here is if a bullet, say 2, was deleted before bullet 1; then my indexing thing won't pick this up and won't be as efficient. I'm trying to solve this but maybe someone has an idea.

I suppose an occasional sweep of the table could work, and reset the start index to the first bullet? Either way this is still way faster then using a loop with ipairs. Or in the update loop I could just assign the first valid index as the minRollingBulletCount; done.

[JohnnyC]

Never thought about giving objects a lifetime til expiration. Seems a bit redundant with collision detection though? Looks good, I'll try and recreate that code and see how it works out.

If anything one thing I'm absolutely going to steal is the, "do not draw if outside of visible screen" even if alive. I have my playarea collision decently large so I can have bullets go off screen slightly but come back or if they're fired before the enemies enter from the top. My solution was just deal with it and draw them even if they're off screen.

[drunken_munki]

Never thought about giving objects a lifetime til expiration. Seems a bit redundant with collision detection though?

Possibly! I mainly use this type of thing for particle effects emmiters or Area Effect damage containers, that might last say 1 second (for an explosion). It could be removed from the example! or used in conjunctin with a collision that calls removeBullet() on a hit.

I just saw your post a few minutes before mine, I'll have a read in a tick.

If anything one thing I'm absolutely going to steal is the, "do not draw if outside of visible screen" even if alive

I think it's worth it, in my example I made a poor description. I think you should also pass the width/height and include that in the screen calculation to make sure things don't 'pop off' before they full exit the screen. I think I use an efficient but not pretty box collision function the object bounds as (x1, y1, w1, h1) and screen (0, 0, W, H) as (x2, y2, w2, h2):

Code: Select all

function boxCollision(x1, y1, w1, h1, x2, y2, w2, h2)
  if x1 > x2+w2 then
    do return false end
  end
  if y1 > y2+h2 then
    do return false end
  end
  if x2 > x1+w1 then
    do return false end
  end
  if y2 > y1+h1 then
    do return false end
  end
  return true -- True implies a collision (object x1, y1, w1, h1 is partially or wholly inside x2, y2, w2, h2)
end

Though it might be redundent passing 0, 0 screen w, screen height each time! I think I store these values as a local inside the top of the module like this:

Code: Select all

local screenX, screenY, screenW, screenH = 0, 0, 800, 600

function boxCollision(x1, y1, w1, h1)
  if x1 > screenX+screenW then
    do return false end
  end
  if y1 > screenY+screenH then
    do return false end
  end
  if screenX > x1+w1 then
    do return false end
  end
  if screenY > y1+h1 then
    do return false end
  end
  return true
end

[zorg]

Now, I've done it this way to avoid using ipairs() which is incredibly slow.

I believe that the luaJIT löve already uses does compile ipairs, so it should not be slow(er than for loops, by any measurable time).
That said, for loops are still betterthe only way if you only want to iterate over a range.

I try to change the start index when a bullet is removed by the life field or it could be called manually upon a collision. The problem here is if a bullet, say 2, was deleted before bullet 1; then my indexing thing won't pick this up and won't be as efficient. I'm trying to solve this but maybe someone has an idea.

Well, i won't say that i understood your code a 100%, but i can't help but feel that since you can't really predict the "life expectancy" of any bullet, you also can't predict their order of death.

I suppose an occasional sweep of the table could work, and reset the start index to the first bullet? Either way this is still way faster then using a loop with ipairs. Or in the update loop I could just assign the first valid index as the minRollingBulletCount; done.

In any case, lua numbers being able to go up to 2^52 or 2^53 means that this shouldn't have any issues with indexing, but again, i wonder what is gained by not "overwriting" already existing indices that have been set as dead anyway. And again, did you benchmark ipairs and for against each other? Just curious, since me and some others have talked about ipairs being compiled with luaJIT before... maybe i'm confused and it's not in the version löve uses...

Never thought about giving objects a lifetime til expiration. Seems a bit redundant with collision detection though?

Depends on how the game should work. Most touhou games i've played had parts where you couldn't harm the boss, and you had to survive; bullets may or may not have went out of the screen in one direction, and appeared on the other. If you didn't lose a life, those bullets only vanished if the timer has elapsed.

My solution was just deal with it and draw them even if they're off screen.

You can detect the play area with offsets, so you can say that if it left the area by more than some amount of pixels, then delete them.

[pgimeno]

Now, I've done it this way to avoid using ipairs() which is incredibly slow.

I believe that the luaJIT löve already uses does compile ipairs, so it should not be slow(er than for loops, by any measurable time).

My measurements indicate that drunken_munki is right, ipairs is noticeably slower.