Jump to content
  • Advertisement


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


Collision Detection in a tile system

This topic is 5299 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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
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.

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
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
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]=

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.

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
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

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!