Let's talk about Bump and grid optimization, shall we? In a tile based game each tile can be a solid or pass-through block. With a normal hand-crafted collision system you'd simply check the tile's solid entry at runtime. But since I'm using Bump, I guess you'd be expected to have a single box for each solid tile. But on a large level you'd end up with a lot of memory being used. (I tried it. A huge grid with thousands of solid tiles would have Bump creating so much garbage) So I wrote an algorithm to take my grid of solid tiles and optimize it and give me less Bump blocks by combining large groups of like tiles into larger blocks. Less blocks = less memory used by Bump = less garbage.
But for some tile types I need to have each block be a single Bump block. For instance; sand, destructable rock walls. So I create their Bump blocks individually. But then there's some other kinds of tile types that might need a different kind of Bump block created like conveyor belts which are created at level load as separate entities, or spikes that are only created in horizontal strips, or pass-through platforms that are also only created in strips. My optimization algorithm is really only used for normal solid non-destructible walls which normally make up the majority of a level as well as ice.
Here's an image with one of each kind of collision to illustrate:
- Collisions.png (327.84 KiB) Viewed 4006 times
Number of solid normal wall tiles above: ~130
Number of solid normal wall collision blocks: 29
You'll note the grey stone blocks and yellow sand have single blocks for each tile. The spikes have two collisions, one pass-through for harming and another solid one for standing on. The green passthrough platforms don't merge vertically. The ice is separate from the rest and is one entity while the dirt walls are optimized (As well as my algorithm currently does) for as little memory as possible to allow for bigger levels when needed. These collision blocks are created when a level is loaded. They are not stored in the map file. Generation is near-instantaneous. (On a huge level it might take a few seconds. I used this algorithm in, and created it originally for, my RPG map collision detection. On the overworld, which could be 256x256+ tiles in size it would take a second or two to create with a lot of solid chunks of collidable blocks.)
The idea of merging groups of solid blocks is not my own as I got the idea from
another game creation utility that allowed you to make games in HTML5 and had JavaScript Box2D built-in and would perform the same type of algorithm for creating its maps and optimizing the Box2D collision elements. Although I never saw any of their code to do it, I had to come up with the algorithm on my own using my own methods. So it is probably not even the best way to do it. (They even use a performance graph in the same way I do. Of course I modeled mine after Minecraft, not Impact.)
Now I'll share some sort of pseudo but possibly working code you can try and play with and examine. It's really quite simple:
First create a table of tables of possible chunk sizes to check for...
Code: Select all
local boxSizeList = {
{128,24}, {32,128}, {64,12}, {12,64}, {32,12}, {12,32}, {12,12}, {8,8}, {7,7}, {6,6}, {5,5}, {5,4}, {4,4}, {5,3}, {20,2}, {15,2}, {10,2}, {6,2}, {5,2},
{4,5}, {4,2}, {4,3}, {4,2}, {3,10}, {3,4}, {3,3}, {2,4}, {1,32}, {32,1}, {30,1}, {20,1}, {1,20}, {7,1}, {6,1}, {5,1}, {4,1}, {2,3}, {1,4}, {3,1}, {1,3}, {2,2}, {2,1}, {1,2}, {1,1}
}
Of course that could be optimized or changed completely, but this was the easiest way I could do it. I can add more chunk sizes if needed and it wont matter much. Larger ones get created first while smaller ones are last with 1x1 being final.
Then you run through the list one at a time from largest to smallest, check the grid for a chunk of solid blocks all in the same shape, then mark them all (Using a temporary grid table the same size as the map specifically for marking) when the block is successfully created. Of course as you're checking a tile during that grid check, you skip the tile if it's already marked.
Code: Select all
for a = 1, #boxSizeList do
local bw, bh = boxSizeList[a][1], boxSizeList[a][2]
local count = bw * bh
for x = 0, #tempColMap-bw+1 do
for y = 0, #tempColMap[1]-bh+1 do
local _count = 0
for bx = x, x + (bw-1) do
for by = y, y + (bh-1) do
if not markedGrid[bx][by] then
if tempColMap[bx][by] == currentTileType then
_count = _count + 1
end
end
end
end
if _count == count then
local n = "solidWall_" .. x+1 .. "_" .. y+1
local wallType = currentTileType
-- Add the newly created collision box to a table that will later be used to generate the Bump collision blocks
self.level.boxList[n] = { x = x * TILESIZE, y = y * TILESIZE, w = bw * TILESIZE, h = bh * TILESIZE, id = n, solid = true }
for bx = x, x + (bw-1) do
for by = y, y + (bh-1) do
markedGrid[bx][by] = true
end
end
end
end
end
end
And what pops out is a list of collision boxes that make up the solid areas of the map. This algorithm is only for solid walls that will never change or be destroyed.
Now if you want to do the "horizontal mode" method I use for the pass-through platforms and spikes you'd add a little piece of code to the top above the first loop where you create a temporary list of checks that only includes entries that are 1 tile high. For example:
Code: Select all
local altBoxSizeList = {}
for bsl = 1, #boxSizeList do
if boxSizeList[bsl][2] == 1 then
altBoxSizeList[#altBoxSizeList+1] = { boxSizeList[bsl][1], boxSizeList[bsl][2] }
end
end
Then you run through the altBoxSizeList instead of the boxSizeList in that first loop.
For spikes you'd instead create two separate collision boxList entries. Or rather that's what I do. It all depends on how you want your game to actually work. You could just make them solid and have the player get hurt when standing on top of the spikes like in SMB2. I was going more for a Spelunky approach where you can be inside the spikes.
I hope you found this interesting and informative and fun. Maybe next time I'll talk about how I draw my tiles in the right order.
