Fast tilemap collisions

b/General Help publicado por u/gameblabla February 03, 2017, 05:58:24 PM

Fast tilemap collisions

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 :

Code Select

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)

Code Select

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 :

Code Select

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 ?

Inicia sesión o crea una cuenta para dejar un comentario

u/Snektron 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.

Code Select


#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

Last Edit: February 03, 2017, 11:20:33 PM by Snektron

u/gameblabla 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 :

Code Select

#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;
}

Last Edit: February 03, 2017, 06:43:59 PM by gameblabla

u/gameblabla 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 :

Code Select

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

Code Select

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.

Last Edit: February 03, 2017, 11:06:33 PM by gameblabla

u/Snektron 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:

Code Select


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];
}

u/gameblabla 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 :

Code Select

#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