CodeWalrus

General => General Help & Troubleshooting => Topic started by: gameblabla on February 03, 2017, 05:58:24 pm

Title: Fast tilemap collisions
Post by: gameblabla on February 03, 2017, 05:58:24 pm
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 ?
Title: Re: Fast tilemap collisions
Post by: Snektron on February 03, 2017, 06:26:21 pm
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
Title: Re: Fast tilemap collisions
Post by: gameblabla on February 03, 2017, 06:27:24 pm
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;
}
Title: Re: Fast tilemap collisions
Post by: gameblabla on February 03, 2017, 07:40:33 pm
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.
Title: Re: Fast tilemap collisions
Post by: Snektron on February 03, 2017, 11:04:49 pm
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];
}
Title: Re: Fast tilemap collisions
Post by: gameblabla on February 04, 2017, 12:03:47 am
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)