Archived

This topic is now archived and is closed to further replies.

Leiarchy9

Collision Detection in a tile system

Recommended Posts

Leiarchy9    100
I''m new to the tile-base system scenary. I recently made a tile class and got it to work. It renders all of the tiles as it appears in my 2D array map. My question is...how the hell could I detect collision between a character(standing on top of the tile layer) and a solid tile(like a wall or a boulder)? -------- "Do you believe in Ghost?"

Share this post


Link to post
Share on other sites
JTippetts    12951
One way to do it is to maintain an array of blocked tiles, where each tile is represented by a single bit. If a character or object covers a certain amount of area, you just need to check all of the blocking bits in that area for one that is set.

If you want movement and collision checks to be done on a level finer than the tile level, then you need to subdivide each tile into a number of subtiles, and store blocking flags for each subtile.

Every time you set a tile to be a wall, or a floor, or water, or whatever, you set the corresponding subtile block flags based on some pre-determined pattern to fit the wall/terrain you are setting.

A quick check for collisions involves finding out the size of a square of subtiles that an object covers, then iterating through the square centered at the object''s location and checking block flags. If a collision is indicated, you can either use that as your final result or perform a finer detail collision check if you desire.

Josh
vertexnormal AT linuxmail DOT org


Check out Golem: Lands of Shadow, an isometrically rendered hack-and-slash inspired equally by Nethack and Diablo.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
how do you make an array to represent stuff by bits? would that be a boolean array?

Share this post


Link to post
Share on other sites
JTippetts    12951
No, boolean types are (usually) represented by an entire byte, which is wasteful for large arrays.

Typically, you would instead use bitwise operations (&, |, ~) for setting bits in a byte, selecting the proper byte from an array.

For instance, say you have a map consisting of 256x256 tiles. Using standard booleans, that's 65536 bytes. Using bitwise operations so that each flag is exactly 1 bit, that reduces it to 8192. Now, in today's world of huge amounts of RAM it might not be so important, but I still like to be efficient and for very large maps the savings can be significant.

Each bit in a byte (unsigned char) can be set or cleared using a corresponding bit mask, which has only the desired bit set to 1. The set of masks for a byte are

{0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80}

By selecting a byte in an array, and further selecting which bit in that array to operate on, you can use the appropriate mask to set, clear or query the bit in question. Typically, I will implement my array of bytes as a 1D array of length equal to the number of tiles in the map:

unsigned char *ByteArray=new unsigned char[ MAP_SIZE_X*MAP_SIZE_Y];

Now, if you have a pair of tile coordinates TX,TY representing a tile in the map you want to check, you can calculate which byte in the array holds the corresponding tile's bit, and which bit in the byte it is:

// Get the right byte in the array
int Which=TY*MAP_SIZE_X+TX; // Index into 1D array
unsigned char *WhichByte=&ByteArray[ Which/8]; // Get ptr. to byte

// Calculate which bit
int Bit=Which % 8;


Once you have the byte you need to use, and the bit to set/clear/query, you can select the appropriate mask either by indexing an array of masks using the calculate Bit:

unsigned char MaskArray[ 8]=
{
0x01,
0x02,
0x04,
0x08,
0x10,
0x20,
0x40,
0x80
};

unsigned char Mask=MaskArray[ Bit];


or by bit-shifting 1 by Bit:

unsigned char Mask = 1 << Bit;


Then, it is a simple matter of performing the appropriate bitwise operation. For setting a flag, you OR the byte and the mask together. For clearing a flag, you AND the byte with the NOT of the mask. For querying the flag, you AND the byte and the mask and check for non-zero:


// Set flag
*WhichByte=*WhichByte | Mask;

// Clear the flag
*WhichByte=*WhichByte & (~Mask);

// Check the flag
if(*WhichByte & Mask)
{
// Blah blah blah
}


I have encapsulated all of this in a class for simplicity in my own projects. It certainly comes in handy.

Josh
vertexnormal AT linuxmail DOT org


Check out Golem: Lands of Shadow, an isometrically rendered hack-and-slash inspired equally by Nethack and Diablo.

[edited by - VertexNormal on January 13, 2004 1:18:03 AM]

Share this post


Link to post
Share on other sites
Zahlman    1682
This is ugly stuff to have to deal with. :/

I assume that your character moves one tile at a time, and since you are able to move the character around freely, you already have something like

// Adjust character''s position.
// return true iff movement was successful.
boolean Character::move (int dx, int dy) {
Tile target = map.getTile(this.tile, dx, dy);
// TODO: make sure the movement is valid!
this.tile = target;
return true;
}


Now what you want to add, where I have the TODO comment, is a check of whether ''target'' is blocked. You can have that precomputed and stored somewhere in a giant bit array, as suggested; or, you can take the approach I''d instinctively suggest, and calculate this on demand. So you add code like:

boolean Tile::isBlocked() {
for (iterator i = myContents.begin(); i != myContents.end(); i++ ) {
if (*i.isBlockage()) return true;
}
return false;
}


where myContents is a vector of the Tile contents, all of some base Contents class. Then you go about all your Contents subclasses, and implement isBlockage() as appropriate (true for walls, false for insects, etc). Finally, you go back to that TODO line and add something like "if (target.isBlocked()) return false;".

I''m making huge assumptions about your design, of course; but you can probably adapt this to work - I hope I at least got the idea across.

Share this post


Link to post
Share on other sites