Hey. In my next project, I want to create a bullet hell involving hundreds and hundreds of small images on-screen, each with very basic behaviors and point collisions with a few objects.
Are there particular optimizations I can make for this that are exclusive to Lua or Corona? Is Corona the right tool for this? I’ve heard it’s particularly slow with lots of images, which concerns me.
Thanks.
Corona SDK is based on OpenGL which uses the system’s Graphics card pipeline to manage textures on screen. Managing a bunch of items is a task that would CPU bind an computer, but unlike a bitmap graphic solution (not using the graphics card’s features), Corona should be faster than most solutions. But bunches and bunches of times will choke just about anything.
Corona SDK is free, so have a quick try and see what it can do!
Rob
Hey there - I did some tests for my own bulletstorm game. 5000 bullets moving all over the screen, each with their own enterFrame loop: no problem whatsoever running at 60fps on an iPhone 4 and an iPad 2. And that was even using the old graphics engine. So I wouldn’t worry about it.
Thanks for the info. I was a bit worried I’d have to learn another tool, I’m starting to like Corona. Did you do any particular optimizations? I don’t think you can even structure a program for cache hits in Lua; I remember getting only about a 5% hit rate, at the most, and that was while going through a large array. Am I wrong?
No cache hits, that’s right.
I don’t do any particular optimizations, but of course you need to program efficiently. Doing very complex collision checks on hundreds of objects each frame can bog things so being smart is always a plus.
Some pointers:
Think and test your collision checks. See which method works fastest. I’m not sure but I assume simple distance-between-two-points checks will be the fastest method (distance = math.sqrt(deltaX squared + deltaY squared). If you need to test against box shapes then don’t put all your “if”-calls in one big line, but rather phase them.
If your big boss fires bullets in a 360 degrees pattern, you probably know that only those in a certain quarter range of this circle will be near your hero character. That means the other 270 degrees bullets don’t need to be tested for collision and are just decorative.
Etcetera. So yes, optimize. But most of it is being smart and normal clean programming.
p.s. One more thing: test which is fastest: 100 bullets as separate instances each with their own frameLoop, or just one frameLoop for a list containing 100 bullets.
Regarding cache hits…
I’ve got at least a couple applications (a JPEG decoder in one case and 2-D Fast Fourier Transforms in another) where I’m doing a HUGE amount of math while hopping around some large memory regions. Needless to say, these are not even remotely fast for large data sets, even after all the standard Lua optimizations, and I’ve brainstormed several approaches* to try to mitigate that. One of the instances where I figured I could get a big win would be to have a “buffer” object in which I could lump big blocks of data and just do lots of operations at once on the C / C++ side, possibly with vector and / or parallelism support. With the opening up of plugins it’s crossed my mind to actually do it. I hadn’t thought about more interesting uses like this, but they might fall out of it naturally. 
* - Other ideas: trying to use asm.js support in webviews; Coronium for LuaJIT, both for its automatic benefits and to access dedicated libs through the FFI; in the FFT case, via a shader.
What do you mean by phasing them? Does lua not short-circuit groups of and evaluations? To keep it fast, I’m probably going to do only point/distance collisions.
That’s clever. Sounds like I should keep a list of “dangerous” bullets and a list of bullets that are very unlikely to hit the player. I wouldn’t even have to much around with quad trees or any of that nonsense because it’s all player<->bullet collisions. I might have to do something special for playerBullet<->mob collisions.
You mentioned you had five thousand bullets, were those all simple image rects that were moved by an x/yspeed? As far as I know that’s the only way to put images on the screen in corona.
I see. Can these be accessed without the enterprise version?
@ thomas6
Did this play on a phone, or just tablets? If the former, how did it work out? I wondered about that when I saw them in the Android store. Seems like with the hectic pace your fingers would be in the way. 
@ abridgedun
You can actually omit the square root if you’re just checking a distance (more specifically, you would compare against the squared distance). If you find you need to take the motion into account (either of just the bullet or the player as well), you could do a two-stage collision detection, where you first detect potential collisions and then find any actual ones among those. In that case, a distance check would still be viable in the first stage: just grow the radius of the object by its distance traveled the last frame, e.g. fixed speed * elapsed frame time.
This being (I assume) a shmup, presumably the world is “fixed” from the point of view of the player, in which case an underlying grid is probably a reasonable data structure. The bullet could be put in the bucket of the cell it currently occupies, and the player would only check its own cells (it’s probably cheapest to bin the bullet to one bucket, whereas the player, who may straddle multiple cells, would investigate a slightly generous neighborhood). If most bullets will travel along a fixed linear velocity, you could even try to make the bucket placement incremental (if you’re brave, you could try to adapt this ray slopes code).
Also, these aren’t mutually exclusive to any of the other ideas, like forgoing the big swath of angles.
Oh, heh. I brought those other ideas up in a “No, really, I HAVE considered several approaches” way. :) Apart from the plugin idea nothing involves Enterprise, no. Coronium is probably too long of a round-trip for a twitch game, and would depend on a connection as well. I don’t know if asm.js is all that pervasive, but my main thinking there was that the Javascript VM might be more friendly than Lua to data that was known to be all numbers / vectors. That still entails a round trip, though, and possibly an expensive (in danmaku terms) conversion step afterward.
Shaders are in the recent daily builds and there’s a beta going on. This one might actually be viable, though it won’t likely be dead simple code. Most ideas I have in mind involve snapshots, which given their frame delay might not be amenable to such a frenetic genre. Also, you might need to set aside one pixel on the screen… maybe it could be embedded in a noisy HUD.
So, first idea is to maintain some shadow display objects, maybe circles if that will be the collision primitive anyway, in the snapshot. A multi-pass shader is run on the snapshot. The first takes the player position and radius as input; ideally, the vertex shader trims down the area to “shade” to just the player’s vicinity (or rather, the next-power-of-2-sized bounding box), not the full-screen snapshot. Any white pixel within the player’s circle is kept; all other pixels are cleared.
After that, several reduction passes are performed to bring it down to one pixel. Along the way, you take the maximum of all samples; in this way, if there’s a white pixel anywhere in the texture after the first pass, it winds up in our single pixel. Then, you color pick that pixel. If it’s white, collision!
The reduction thing might be expensive. It’s tailored more towards compute shaders.
The other idea is to maintain a bunch of single-pixel rects, again shadowing your bullets, again in a snapshot, at whatever pixel position we’re monitoring. Each frame, you tell each of them where it’s at, where the player’s at, and their respective radii. This is six pieces of information to cram into four floats, so you’ll have to compress some things or hard-wire stuff into the shader (player and bullet radius, or the vertex shader’s output position, freeing up the object’s position) or sneak low-res information in through the fill color. Do some comparisons as in the other shader, outputting white on a collision, black otherwise; use additive blending on the effect. Again, color pick the pixel.
Anyhow, this is all speculative! The idea, though, is to move most of the math into the (typically massively parallelized) graphics pipeline. Color picking isn’t fast, but neither are hundreds of radius checks. 
thomas6 hello!
Can You post your code of bullets enterFrame function and collision detection with enemies from your bulletStorm test, please?
In my test I have 200 moving objects on background without collision checks, 80 enemies with collision checks of bullets, and when I put 3 bullets on stage fps goes down very fast. 3 bullets is almost nothing.
I test it on Nexus 7 and galaxy e5.
Sadly, Corona is much too limited and slow for me to use it for my project. I found that out the hard way. I may be back here when I need to work on some business apps, but Corona’s well hidden gotchas are enough reason for me to just go native.
It’s been a while but let me dive into my archive. Bear in mind that 3 bullets is not much, but you need to calculate 3 bullets times 80 enemies, so the relevant number here is that you need to do 240 collision checks. Can you give me a description of what your game looks like a a basic way, for instance “My hero ship is at the bottom of the screen moving left and right, and fires bullets up a waves of enemies that descend from the top of the screen”? That gives me a better idea of your specific setup and needs.
- “My hero ship is at the bottom of the screen moving left and right, and fires bullets up a waves of enemies that descend from the top of the screen”?
You are right)
Just out of curiosity: do you have 80 enemies on screen at the same time? Or do you only see about 10 or 20 of them on screen at the same time?
80 at the same time.
@ Novgorod59
What does one of your collision checks look like?
I can tell you that mine are super-basic distance between two points or spheres.
Calculate local xDelta, local yDelta, and check wether xDelta * xDelta + yDelta * yDelta is smaller than a certain value.
T
In bullet update function:
function bullet:enemyCollide() local i local j for i=1, #gameData.enemysArr do for j=1, #gameData.enemysArr[1] do if (gameData.enemysArr[i][j] ~= nil) then if (self:hasCollidedCircle(gameData.enemysArr[i][j].enemyContainer, self.bulletMc)) then self:destroy() gameData.enemysArr[i][j]:destroy() end end end end end
function bullet:hasCollidedCircle(obj1, obj2) if ( obj1 == nil ) then return false end if ( obj2 == nil ) then return false end local dx = obj1.x - obj2.x local dy = obj1.y - obj2.y local distance = math.sqrt( dx\*dx + dy\*dy ) local objectSize = (obj2.contentWidth/2) + (obj1.contentWidth/2) if ( distance \< objectSize ) then return true end return false endShould the line
for j=1, #gameData.enemysArr[1] do
be
for j=1, #gameData.enemysArr[i] do
instead? Also, does that contain all the other enemies? Does each pair of enemies have the other in its own list?
You might eke out a little by changing
local distance = math.sqrt( dx\*dx + dy\*dy ) local objectSize = (obj2.contentWidth/2) + (obj1.contentWidth/2) if ( distance \< objectSize ) then
to
local distance = dx\*dx + dy\*dy -- actually, dx^2 + dy^2 is faster, in my experience local objectSize = (obj2.contentWidth/2) + (obj1.contentWidth/2) if ( distance \< objectSize^2 ) then
which is the same under these circumstances.
The contentWidth property might be calling some functions under the hood, so maybe you could cache those if they don’t change.
I might need a little more info, but I suspect the grid structure probably isn’t ideal. LOTS of indirection, too, which adds up. I’m going to go run for a while (and probably get drenched by a thunderstorm…) but later tonight I could post some suggestions.
Okay, some more stuff.
First, what’s the idea behind the two-dimensional array? I guess if one dimension is waves and the other is their enemies, that’s fine. But if it’s some sort of 80 x 80 monster, you’re hosed!
A quick note. This
for j=1, #gameData.enemysArr[1] do if (gameData.enemysArr[i][j] ~= nil) then
is not safe, unless the very first “wave” has no nil members and is some maximum length or something. (That sounds kind of odd, so I’m guessing it’s not the case.) The length operator, #, will not behave well in the presence of nil elements. If you need gaps, false is your friend here.
(Also, you don’t need to declare locals i and j. The loops do it for you.)
Do you actually need the existence checks inside hasCollidedCircle ()? Can your enemy exist but not its container? It seems like you could do the check for the bullet’s Mc once at the beginning and be done with it. For that matter, I assume you could just return after destroying your bullet. Or can it take out multiple enemies?
Actually, you might be able to get some improvement if destroy () doesn’t necessarily remove the display object, but just turns it off, letting it be awoken later for a new enemy. But this might require some work if the enemy types vary a lot.
Also, with stuff like gameData.enemysArr[i][j], you’re doing a bunch of accesses in a tight loop, so you’ll gain a little bit just by stashing the intermediate parts into local variables.
Now, the bigger gains would come from restructuring your data. If you refer to my earlier long post, I’m going to assume those sorts of conditions. So, say, you would have your game screen, and it could be broken up a bit:
(Lovingly crafted in 45 seconds.)
As we all know, something in the upper right is not all that close to stuff in the lower left, and likewise for things on the top versus the bottom, etc. In general, something in one of those “boxes” probably doesn’t care much about a “box” much further away.
Now, we have our bullet zinging around:
And it will overlap one or more boxes. Furthermore, it can reason out which cells it’s covering. Assuming x = 0 on the left and y = 0 at the top, for example, you could visit the bullet’s neighborhood:
local floor = math.floor local max = math.max local min = math.min local Cells = {} for row = 1, CellRows do local line = {} for col = 1, CellColumns do line[col] = {} end Cells[row] = line end -- stuff local CellWidth = display.contentWidth / CellColumns local CellHeight = display.contentHeight / CellRows function VisitCells (object, radius, action) local top = max(1, floor((object.y - radius) / CellHeight) + 1) local bottom = min(CellRows, floor((object.y + radius) / CellHeight) + 1) local left = max(1, floor((object.x - radius) / CellWidth) + 1) local right = min(CellColumns, floor((object.x + radius) / CellWidth) + 1) for row = top, bottom do local line = Cells[row] for col = left, right do local cell = line[col] action(cell, object) end end end
Then, for instance, you could indicate that the bullet is in all those cells:
local function AddBulletToCell (cell, bullet) cell[bullet] = true end -- stuff VisitCells(bullet, bullet.radius, AddBulletToCell)
Or remove it from them (when it’s destroyed, before moving, etc.):
local function RemoveBulletFromCell (cell, bullet) cell[bullet] = nil end -- stuff VisitCells(bullet, bullet.radius, RemoveBulletFromCell )
We also have enemies prowling around! Probably bigger than bullets:
But you could add and remove them from cells the same way.
These cells are generally going to be pretty sparse. The bullets / enemies are all over the place, so there probably will only be a few in a given cell. So a given bullet could actually just enumerate enemies it might touch:
local pairs = pairs -- stuff local function GatherEnemies (cell, bullet) for thing in pairs(cell) do if IsEnemy(thing) then bullet.n = bullet.n + 1 bullet.enemy\_list[bullet.n] = thing end end end function BulletCollide (bullet) bullet.n = 0 -- reset the enemy list VisitCells(bullet, bullet.radius, GatherEnemies) local list = bullet.enemy\_list for i = 1, bullet.n do if bullet:hasCollidedCircle(bullet, list[i]) then bullet:destroy() list[i]:destroy() return end end end
Likewise for the player.
Now, an enemy might sprawl across several cells, so we could encounter it several times during the gather process. We could set a flag the first time we encounter it, and ignore it after that. But then we’d have to clean up all of our flags. In the above code this might be okay (we could clear it during the loop), but it complicates the early return on a collision. Another method is to just keep a “current” ID and see if it’s been assigned that; if so, ignore it. Then the above becomes:
local pairs = pairs -- stuff local function GatherEnemies (cell, bullet) local id = bullet.id for thing in pairs(cell) do if IsEnemy(thing) and thing.id ~= id then bullet.n = bullet.n + 1 bullet.enemy\_list[bullet.n] = thing thing.id = id end end end function BulletCollide (bullet) bullet.id = bullet.id + 1 -- initialize to 0 or whatever on bullet creation bullet.n = 0 -- reset the enemy list VisitCells(bullet, bullet.radius, GatherEnemies) local list = bullet.enemy\_list for i = 1, bullet.n do if bullet:hasCollidedCircle(bullet, list[i]) then bullet:destroy() -- do normal stuff, plus remove from cell, etc. list[i]:destroy() -- ditto return end end end
Anyhow, this is all pseudo-code, but the ideas might be worth a shot. The main idea is that it breaks a big problem down into smaller, more manageable ones. I could elaborate if you have questions.
EDITS : A couple code typos and wonky text bits.
Thank You very much for your reply! I need some time to translate and understand it, because I not good speak English.