The shoutbox is currently out of service. Join us on Discord instead.
You can help CodeWalrus stay online by donating here.

Fast tilemap collisions

Started by gameblabla, February 03, 2017, 05:58:24 pm

Previous topic - Next topic

0 Members and 1 Guest are viewing this topic.

gameblabla

Hello guys,
as you may know, i have released a new game called Evil Australians.
However, the collisions routines for checking collisions against the map is slow !
Here it is :
unsigned char Collisions_MAP(short col_x, short col_y, unsigned short width_player, unsigned short height_player, short scroll_x, unsigned short size_map, unsigned short tile_width_map)
{
unsigned short i, a = 0, y = 0;
signed short temp_x = 0, temp_y = 0;

for (i=0;i<size_map;i++)
{
a++;
if (a > (tile_width_map-1))
{
y++;
a = 0;
}

if (collision_map[a+(y*tile_width_map)] == 1)
{
temp_x = (a * SIZE_TILE)-scroll_x;
temp_y = y * SIZE_TILE;
if ( (col_x + width_player > temp_x) && (col_x < temp_x + SIZE_TILE) )
{
if ( (col_y + height_player > temp_y ) && (col_y < temp_y + SIZE_TILE) )
{
return 1;
}
}
}
}
return 0;
}


And here's what a map looks like (width is 40 tiles, height is 15 tiles)
const char map [600] =
{
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,
1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,
1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,
1,1,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,
1,1,1,1,1,1,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,
1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,
1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,
1,0,0,0,0,0,0,1,1,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,1,1,1,0,0,1,1,1,1,1,1,
1,0,0,0,0,0,1,1,1,1,0,0,1,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1
};


As you can see, it's slow because it checks for all posibilites.
I tried to speed it up like so :
unsigned char Collisions_MAP(short col_x, short col_y, unsigned short width_player, unsigned short height_player, short scroll_x, unsigned short size_map, unsigned short tile_width_map)
{
unsigned short i, a, y;
signed short temp_x = 0, temp_y = 0;
y = (col_y/15)-1;
a = 0;

for (i=y;i<size_map;i++)
{
a++;
if (a > (tile_width_map-1))
{
y++;
a = 0;
}

if (collision_map[a+(y*tile_width_map)] == 1)
{
temp_x = (a * SIZE_TILE)-scroll_x;
temp_y = y * SIZE_TILE;
if ( (col_x + width_player > temp_x) && (col_x < temp_x + SIZE_TILE) )
{
if ( (col_y + height_player > temp_y ) && (col_y < temp_y + SIZE_TILE) )
{
return 1;
}
}
}
}
return 0;
}


However, it now involves a division so it might run slower on ARM cpus, like the 3DO...
Perhaps my way of doing things is wrong though.
How i can improve this routine ?
How do you do your tilemap collisions ?

Snektron

February 03, 2017, 06:26:21 pm #1 Last Edit: February 03, 2017, 11:20:33 pm by Snektron
The idea is to only traverse the tiles which are currently inside the rectangle you want to check.


#define MAP_WIDTH 40
#define MAP_HEIGHT 15
#define TILE_SIZE 16

// we can convert a pixel-coordinate to map-coordinates by
// dividing by the tile's size in pixels.
// because the tiles are square we can use the same function for x and y coordinates.
#define PIX_TO_MAP(x) ((x) / TILE_SIZE)

// this converts a map-coordinate to an index of the map array.
#define MAP_TO_INDEX(x, y) ((y) * MAP_WIDTH + (x))

// check wether a rectangle defined by a position and a size collides with a tile
char map_collision_check(int x, int y, int w, int h)
{
int start_x = PIX_TO_MAP(x); // which tile does the hit rectangle start at?
int end_x = PIX_TO_MAP(x + w); // which tile does it end at?
int start_y = PIX_TO_MAP(y);
int end_y = PIX_TO_MAP(y + h);

for (int i = start_x; i <= end_x; i++)
{
for (int j = start_y; j <= end_y; j++)
{
int tile = MAP_TO_INDEX(i, j);
if (map[tile]) // this actually checks whether a tile collides.
return 1;
}
}

return 0;
}


edit: please note that this function is un tested and does not check map bounds. If you want to do that you should limit
start_x and start_y to be >= 0, limit end_x to be < MAP_WIDTH and end_y to be < MAP_HEIGHT.

edit 2: altered to fix small mistakes gameblabla noticed
Legends say if you spam more than DJ Omnimaga, you will become a walrus...


gameblabla

February 03, 2017, 06:27:24 pm #2 Last Edit: February 03, 2017, 06:43:59 pm by gameblabla
Thanks !
I will give it a try right now and let you know about it !

I think you did some mistakes, i think it should look like this :
#define MAP_WIDTH 40
#define MAP_HEIGHT 15
#define TILE_SIZE 16

// we can convert a pixel-coordinate to map-coordinates by
// dividing by the tile's size in pixels.
// because the tiles are square we can use the same function for x and y coordinates.
#define PIX_TO_MAP(x) ((x) / TILE_SIZE)

// this converts a map-coordinate to an index of the map array.
#define MAP_TO_INDEX(x, y) ((y) * MAP_WIDTH + (x))

// check wether a rectangle defined by a position and a size collides with a tile
char map_collision_check(int x, int y, int w, int h)
{
int start_x = PIX_TO_MAP(x); // which tile does the hit rectangle start at?
int end_x = PIX_TO_MAP(x + w); // which tile does it end at?
int start_y = PIX_TO_MAP(y);
int end_y = PIX_TO_MAP(y + h);

for (int i = start_x; i <= end_x; i++)
{
for (int j = start_y; j <= end_y; j++)
{
int tile = MAP_TO_INDEX(i, j);
if (map[tile]) // this actually checks whether a tile collides.
return 1;
}
}

return 0;
}

gameblabla

February 03, 2017, 07:40:33 pm #3 Last Edit: February 03, 2017, 11:06:33 pm by gameblabla
Just want to say that your routine works perfectly !
Here's the "version" i'm using for the game :
// we can convert a pixel-coordinate to map-coordinates by
// dividing by the tile's size in pixels.
// because the tiles are square we can use the same function for x and y coordinates.
#define PIX_TO_MAP(x) ((x) / 16)
// This converts a map-coordinate to an index of the map array.
#define MAP_TO_INDEX(x, y, a) ((y) * a + x)

unsigned char Collisions_MAP(short col_x, short col_y, unsigned short w, unsigned short h, short scroll_x, unsigned short size_map, unsigned short tile_width_map)
{
unsigned short x = col_x + scroll_x;
unsigned short y = col_y;
unsigned short start_x = PIX_TO_MAP(x); // which tile does the hit rectangle start at?
unsigned short end_x = PIX_TO_MAP(x + w); // which tile does it end at?
unsigned short start_y = PIX_TO_MAP(y);
unsigned short end_y = PIX_TO_MAP(y + h);
unsigned char i, j;
unsigned short tile;

for (i = start_x; i <= end_x; i++)
{
if (end_x > tile_width_map) end_x = tile_width_map;

for (j = start_y; j <= end_y; j++)
{
if (end_y > 15) end_y = 15;
tile = MAP_TO_INDEX(i, j, tile_width_map);
if (collision_map[tile]) // this actually checks whether a tile collides.
return 1;
}
}
return 0;
}


However, this new function still bottlenecking the 3DO, despite the new functions helping to streamline my code a bit...
I saw some games doing bit-shifting for tile collisions like this Master System game :
unsigned char maptilemap_bin[1536];
// Obtiene una tile
unsigned char gettilexyb(unsigned char x, unsigned char y)
{
return maptilemap_bin[((x>>3)+((y>>3)<<5))<<1];
}
unsigned char insideblock(unsigned char x,unsigned char y)
{
unsigned char c;
c=gettilexyb(x,y);
if(c<4)return 1; else return 0;
}

However that game checks the color of the tile so in our case, this is out of question as we can have up to 16 millions of colors...
Any suggestions ?

Maybe we can do it without a loop.

Snektron

The difference is that check checks only a singular point. But my routine checks every tile (until one is found)  within the square.
If you only want to check a singular point you can use this:


char map_collision_point(int x, int y)
{
    int map_x = PIX_TO_MAP(x);
    int map_y = PIX_TO_MAP(y);
    int tile = MAP_TO_INDEX(map_x, map_y);
    return !!map[tile];
}
Legends say if you spam more than DJ Omnimaga, you will become a walrus...


gameblabla

February 04, 2017, 12:03:47 am #5 Last Edit: February 04, 2017, 12:15:33 am by gameblabla
Well, much thanks Snektron !
I had to tweak it a bit for my game but it works !
I can't believe my crappy code was simplified into this :
#define PIX_TO_MAP(x) ((x) / 16)
//#define PIX_TO_MAP(x) ((x)>>4)
#define MAP_TO_INDEX(x, y, a) ((y) * a + x)
unsigned char Collisions_MAP(short col_x, short col_y, unsigned short w, unsigned short h)
{
unsigned short map_x = PIX_TO_MAP(col_x+scroll_x);
unsigned short map_y = PIX_TO_MAP(col_y+h);
unsigned short tile = MAP_TO_INDEX(map_x, map_y, map_width);
return !!collision_map[tile];
}


The game runs a little faster on the 3DO than before so it turns collisions were not the bottleneck... lol
If you want to make a 2D game, i would recommend it.
It's the first time Google was unhelpful to me >:(
(Seriously, type "tilemap collisions C" and you stumble upon nothingness)

Powered by EzPortal