So I am making a 2d tilebased puzzle platformer game.
It's convenient to store the basic level geometry as a giant bit array that says whether there's a block at any given location. This is very memory compact and easy to query as well. When looking for collisions, I test each object agaisnt every nearby square and perform collision response calculations against every block individually. The problem is that this is inefficient.
Most of the time, blocks will form much larger surfaces and contiguous rectangles that span multiple blocks. What would be ideal is a way to automatically recognize this and do a collision test against all the blocks as a single larger rectangle. This is not only faster but also leads to slightly more accurate physics.
The problem is that I don't know of any easy and simple way to automatically detect and merge blocks like that.
Automatically merge adjacent tiles for collision?
You could probably use a flooding technique to determine which blocks are joined. For example,
This isn't necessarily the quickest way to go about grouping them but it seems to run pretty quickly when wid=100 hei=100 so that's something. From then on there's still the issue of how to merge the blocks that are in the same collision set. How are you currently storing the blocks? (If it's a 2D array I can easily change the above code over).
What are you using for the collision detection?
#include <iostream>
#include <deque>
using namespace std;
typedef struct Tile
{
bool collidable;
int collisionSet;
} Tile;
void SortGroups(Tile* tiles, int wid, int hei);
int main()
{
int wid = 10;
int hei = 10;
// Create an array of tiles, the system would also work with a 2 dimensional array
Tile* tiles = new Tile[wid * hei];
for (int i = 0; i < wid * hei; i ++)
{
// Default set tiles to non-collidable
tiles.collidable = false;
// Tile doesnt' belong to a collision set
tiles.collisionSet = -1;
// Randomly setting whether a tile is collidable
if (rand() % 3 == 0)
{
tiles.collidable = true;
}
}
// Print out the way the world looks
printf("|");
for (int i = 0; i < wid * hei; i ++)
{
if (tiles.collidable)
printf("#");
else
printf(" ");
if ((i % wid) == wid-1)
printf("|\n|");
}
// Assigns a group to collidable tiles
SortGroups(tiles, wid, hei);
// Prints out the tiles according to their group
printf("\n\n|");
for (int i = 0; i < wid * hei; i ++)
{
if (tiles.collidable)
printf("%c", tiles.collisionSet + 'A');
else
printf(" ");
if ((i % wid) == wid-1)
printf("|\n|");
}
}
void SortGroups(Tile* tiles, int wid, int hei)
{
// A deque is like a vector but allows pop_front as well as pop_back
deque<int> checks;
// The first set id you can use
int currentSet = 0;
int currentCell;
// We'll go through each of the tiles we have
for (int i = 0; i < wid * hei; i ++)
{
// If the tile is collidable but not in a collision set
if (tiles.collidable && (tiles.collisionSet == -1))
{
// Put it in our list of checks
checks.push_back(i);
tiles.collisionSet = currentSet;
// While we have items in our checks keep going
while (checks.size() > 0)
{
// Assign the first item in checks to currentCell then remove that item
// from the list
currentCell = checks[0];
checks.pop_front();
// This checks to see whether we have the left most tile on our map
if ((currentCell % wid) > 0)
{
// If not we check whether we can collide to the tile to the left, and check if it's been assigned
// a collision set
if (tiles[currentCell - 1].collidable && (tiles[currentCell - 1].collisionSet == -1))
{
// If not, we add it to our list of tiles to check and set its collision set
tiles[currentCell-1].collisionSet = currentSet;
checks.push_back(currentCell-1);
}
}/**/
// Do the same for checking to the right
if ((currentCell % wid) < (wid - 1))
{
if (tiles[currentCell + 1].collidable && (tiles[currentCell + 1].collisionSet == -1))
{
// If not, we add it to our list of tiles to check and set its collision set
tiles[currentCell+1].collisionSet = currentSet;
checks.push_back(currentCell+1);
}
}
// Moving upwards
if ((currentCell - wid) > 0)
{
if (tiles[currentCell - wid].collidable && (tiles[currentCell - wid].collisionSet == -1))
{
// If not, we add it to our list of tiles to check and set its collision set
tiles[currentCell-wid].collisionSet = currentSet;
checks.push_back(currentCell - wid);
}
}
// Moving down
if ((currentCell + wid) < (wid * hei))
{
if (tiles[currentCell + wid].collidable && (tiles[currentCell + wid].collisionSet == -1))
{
// If not, we add it to our list of tiles to check and set its collision set
tiles[currentCell + wid].collisionSet = currentSet;
checks.push_back(currentCell + wid);
}
}
}
// It wouldn't be too hard to add in diagonal checks if you wanted to
// Increase the set number
currentSet ++;
}
}
}
This isn't necessarily the quickest way to go about grouping them but it seems to run pretty quickly when wid=100 hei=100 so that's something. From then on there's still the issue of how to merge the blocks that are in the same collision set. How are you currently storing the blocks? (If it's a 2D array I can easily change the above code over).
What are you using for the collision detection?
Author
You could probably use a flooding technique to determine which blocks are joined. For example,
This isn't necessarily the quickest way to go about grouping them but it seems to run pretty quickly when wid=100 hei=100 so that's something. From then on there's still the issue of how to merge the blocks that are in the same collision set. How are you currently storing the blocks? (If it's a 2D array I can easily change the above code over).
What are you using for the collision detection?
That's what I'm trying to decide. I can't decide on anything.
If you're using c/c++ you could probably use box2d (http://www.box2d.org). Then modify my code above so that it doesn't move up and down when creating the groups. Then for the left most cell in each group create a shape to use
Then attach each one to fixture, use it for a body and set the body's position to the centre of the cell group, make sure that they're static objects and it should work nicely
dynamicBox.SetAsBox(tilewidth*tilesInSet, tileheight);
Then attach each one to fixture, use it for a body and set the body's position to the centre of the cell group, make sure that they're static objects and it should work nicely
Author
The problem is that I'm making the game for the GBA.
I keep worrying about what will use the most memory or processor time even though I have no idea how to profile either.
I keep worrying about what will use the most memory or processor time even though I have no idea how to profile either.
Oh you're writing it for GBA, that does make things a lot more difficult (not much I can do to help you with it really). How well does the GBA handle floating point numbers? There's always the option of building in a quick box2d app and testing it out?
After further investigation, the DS only handles fixed-point numbers which means that the GBA probably does the same...
After further investigation, the DS only handles fixed-point numbers which means that the GBA probably does the same...
Author
I'm planning on doing all the physics in fixed point. I already have the contact solving code written and it appears to work pretty well, though I have no real way to test it. And it isn't optimized at all, but until I actually make the game, I'll have no idea whether it is too slow or not.
Anyway, at the moment I'm thinking about getting rid of the bitmap altogether and just representing the level as a list of line segments.
Anyway, at the moment I'm thinking about getting rid of the bitmap altogether and just representing the level as a list of line segments.
You could always represent the world using the bitmap but have the physics calculated using line segments. The trick is just having the physics geometry matching the bitmap
Author
Well I've got the line segment collision code mostly working. There's just one problem - corners. Currently I do a separate calculation for each segment, but this leads to incorrect results when colliding with a corner.
My best guess is to handle one collision first, then check to see if the other is still an issue, if so then handle it... But you're probably doing that already. What sort of incorrect results are you getting?
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
