* WalrusIRC

You need to have 5 posts and not be part of restricted usergroups in order to use the WalrusIRC embedded shoutbox. However, you can also access our IRC channel called #CodeWalrus via EFnet.

Author Topic: Fast tilemap collisions  (Read 263 times)

0 Members and 1 Guest are viewing this topic.

Offline gameblabla

  • Super User
  • Join Date: May 2015
  • Location:
  • Posts: 578
  • Post Rating Ratio: +9/-5
  • TI-nspire porter
    • View Profile
Fast tilemap collisions
« 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 :
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 ?


  • Calculators owned: TI Nspire CX, TI-89

Offline Snektron

  • Lvl 69 Russian Snake
  • CodeWalrus Staff
  • Super User
  • Topic Management
  • Join Date: Dec 2014
  • Location: Netherlands
  • Posts: 3139
  • Post Rating Ratio: +31/-0
  • SSSssssss.....
    • RobinDeWalvis
    • Kzyrox
    • RobinDeWalvis
    • View Profile
    • quantuminfinity
  • Gender: Male
Re: Fast tilemap collisions
« Reply #1 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.

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 »
  • Calculators owned: TI-84+
Legends say if you spam more than DJ Omnimaga, you will become a walrus...


Offline gameblabla

  • Super User
  • Join Date: May 2015
  • Location:
  • Posts: 578
  • Post Rating Ratio: +9/-5
  • TI-nspire porter
    • View Profile
Re: Fast tilemap collisions
« Reply #2 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 :
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 »
  • Calculators owned: TI Nspire CX, TI-89

Offline gameblabla

  • Super User
  • Join Date: May 2015
  • Location:
  • Posts: 578
  • Post Rating Ratio: +9/-5
  • TI-nspire porter
    • View Profile
Re: Fast tilemap collisions
« Reply #3 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 :
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 »
  • Calculators owned: TI Nspire CX, TI-89

Offline Snektron

  • Lvl 69 Russian Snake
  • CodeWalrus Staff
  • Super User
  • Topic Management
  • Join Date: Dec 2014
  • Location: Netherlands
  • Posts: 3139
  • Post Rating Ratio: +31/-0
  • SSSssssss.....
    • RobinDeWalvis
    • Kzyrox
    • RobinDeWalvis
    • View Profile
    • quantuminfinity
  • Gender: Male
Re: Fast tilemap collisions
« Reply #4 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:

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];
}
  • Calculators owned: TI-84+
Legends say if you spam more than DJ Omnimaga, you will become a walrus...


Offline gameblabla

  • Super User
  • Join Date: May 2015
  • Location:
  • Posts: 578
  • Post Rating Ratio: +9/-5
  • TI-nspire porter
    • View Profile
Re: Fast tilemap collisions
« Reply #5 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 :
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 >:(
(Seriously, type "tilemap collisions C" and you stumble upon nothingness)
« Last Edit: February 04, 2017, 12:15:33 am by gameblabla »
  • Calculators owned: TI Nspire CX, TI-89

 


You can also use the following HTML or bulletin board code to share it on your page or forum signature!


Also do not forget to check our affiliates below.
Planet Casio TI-Planet Calc.news BroniesQC BosaikNet Velocity Games