### Author Topic: Fast tilemap collisions  (Read 1147 times)

0 Members and 1 Guest are viewing this topic.

#### gameblabla

• Super User
• Join Date: May 2015
• Location:
• Posts: 764
• Post Rating Ratio: +15/-7
• TI-nspire porter
##### 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

#### Snektron

• Lvl 69 Russian Snake
• Super User
• Join Date: Dec 2014
• Location: Netherlands
• Posts: 3165
• Post Rating Ratio: +32/-0
• SSSssssss.....
• Gender:
##### 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 tilechar 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...

#### gameblabla

• Super User
• Join Date: May 2015
• Location:
• Posts: 764
• Post Rating Ratio: +15/-7
• TI-nspire porter
##### 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 tilechar 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

#### gameblabla

• Super User
• Join Date: May 2015
• Location:
• Posts: 764
• Post Rating Ratio: +15/-7
• TI-nspire porter
##### 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 tileunsigned 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

#### Snektron

• Lvl 69 Russian Snake
• Super User
• Join Date: Dec 2014
• Location: Netherlands
• Posts: 3165
• Post Rating Ratio: +32/-0
• SSSssssss.....
• Gender:
##### 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...

#### gameblabla

• Super User
• Join Date: May 2015
• Location:
• Posts: 764
• Post Rating Ratio: +15/-7
• TI-nspire porter
##### 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.