[resolved] collision detection (2d array, sprite)

[McCain]

I'm writing a game but I can't get the collision detection to work quite right...

I have a map of tiles, each tile is 20x20 pixels and I have the map stored in a 2d array iMap[20][20] so my whole map is 400x400 pixels on the screen.

If I move my sprite 20 pixels at a time the collision detection works because then I can just go: sprite.x/20 to find out where in the array the player is and then chek to see if the next spot in the array is walkable or not.

The problem is that I want to move my sprite 5 pixels at a time so the method mentioned above won't work. I can partually move through walls and that is not the way I want it.

How can I get the collision detection to work even if I move 5 pixels at a time?

[Arawn]

First off, let me say I'm not qualified to answer this so I'm probably a little off on this. But couldn't you just check if sprite.x+5/20 is walkable?

[McCain]

No, that wouldn't work...
I'll give you some code and try to explain why it doesn't work...

if(key == "right")
{
if(iMap[player.x/20 + 1][player.y/20] == '0')
player.x += 20;
}

The above code will work but the sprite moves 20 pixels at a time and that is too much, I want it to move 5 pixels every time.

if(key == "right")
{
if(iMap[player.x/20 + 1][player.y/20] == '0')
player.x += 5;
}

This code will only work when player.x is 0, 20, 40, 60, 80, 100 and so on...
Let's say that player.x == 25 then it would be iMap[25/20+1][player.y/20] and that is not a valid coordinate in the iMap array...

[kedaman]

you'd have to go with the traditional collision detection method, test each object that you can collide with. If you have a large amount of objects that can collide with each other and you're worried about peformance you can use a quadtree to narrow down the object count to test.

[jim mcnamara]

You have two choices:
1. use an array[80][80], ie., 5 pixel tiles- which is probably a terrible idea, since your sprites would occupy more territiry than that.
2. round .x and .y (up or down) to the nearest value of 20, put in temp variables then test collision.

You cannot have two granularities and expect them to compare directly without compensating.... somehow

[Zaei]

Originally posted by McCain

Let's say that player.x == 25 then it would be iMap[25/20+1][player.y/20] and that is not a valid coordinate in the iMap array...
Yes, it is a valid coordinate. 25/20 is 1 (integer division), plus 1 is 2. However, you get an incorrect result, because you are checking the next cell in the map, but you arent actually to that cell yet (youd be halfway across the current cell, after the move). What you want to do is add 5 BEFORE the division to get the correct cell.

Z.

[McCain]

Actually I might not be halfway to the next cell as I have to move 4 times to get to a new cell (I only move 5 pixels at a time and each tile (cell) is 20 pixels x 20 pixels)

Let's say player.x == 45 then I'm only 1/4 in the next cell and if I add 5 I'm halfway... So sometimes I'd have to add 5, sometimes 10 and sometime 15, how do I know when to add what?

[CornedBee]

What about this: check for each of the 4 corners of the sprite in what tile they would be in after the move. Then test each of these tiles for passability.

[Zaei]

Originally posted by McCain
Actually I might not be halfway to the next cell as I have to move 4 times to get to a new cell (I only move 5 pixels at a time and each tile (cell) is 20 pixels x 20 pixels)

Let's say player.x == 45 then I'm only 1/4 in the next cell and if I add 5 I'm halfway... So sometimes I'd have to add 5, sometimes 10 and sometime 15, how do I know when to add what?
If moving 5 pixels, add 5 to the .x position before divding by 20. If 10, add 10, 15, add 15.

CB's suggestion is a better solution, however, sicne it allows any granularity in movement.

Z.

[McCain]

2. round .x and .y (up or down) to the nearest value of 20, put in temp variables then test collision.
How would I do that? How do I know how much I need to add or subtract to get to a number that is dividible by 20

What about this: check for each of the 4 corners of the sprite in what tile they would be in after the move. Then test each of these tiles for passability.
If I'm given any x-coordinate or y-coordinate, how can I know what cell that coord is in? will it work if I just integer devide it by 20?

[CornedBee]

Yes.

And to find the nearest integer divisible by 20:

inline int findNearestDivisible(int divisor, int number)
{
int diff = number % divisor;
return (diff < divisor/2) ?
(number - diff) : (number + (divisor-diff));
}

[McCain]

Thank you guys for all your help!
The collision detection now works perfect.

Here is the code if you're interested:

if(g_pacInfo.x % 20 == 0)
g_pacInfo.arrayx = g_pacInfo.x / 20;
if(g_pacInfo.y % 20 == 0)
g_pacInfo.arrayy = g_pacInfo.y / 20;

//Left
if(GetAsyncKeyState(VK_LEFT)<0)
{
if(g_pacInfo.x % 20 == 0)
{
if(iMap[g_pacInfo.arrayx - 1][g_pacInfo.y / 20] == '0')
{
if(iMap[g_pacInfo.arrayx - 1][(g_pacInfo.y + 19) / 20] == '0')
{
g_pacInfo.x -= 5;
}
}
}
else
{
g_pacInfo.x -= 5;
}
}

//Right
if(GetAsyncKeyState(VK_RIGHT)<0)
{
if(g_pacInfo.x % 20 == 0)
{
if(iMap[g_pacInfo.arrayx + 1][g_pacInfo.y / 20] == '0')
{
if(iMap[g_pacInfo.arrayx + 1][(g_pacInfo.y + 19) / 20] == '0')
{
g_pacInfo.x += 5;
}
}
}
else
{
g_pacInfo.x += 5;
}
}

//Up
if(GetAsyncKeyState(VK_UP)<0)
{
if(g_pacInfo.y % 20 == 0)
{
if(iMap[g_pacInfo.x / 20][g_pacInfo.arrayy - 1] == '0')
{
if(iMap[(g_pacInfo.x + 19) / 20][g_pacInfo.arrayy - 1] == '0')
g_pacInfo.y -= 5;
}
}
else
{
g_pacInfo.y -= 5;
}
}

//down
if(GetAsyncKeyState(VK_DOWN)<0)
{
if(g_pacInfo.y % 20 == 0)
{
if(iMap[g_pacInfo.x / 20][g_pacInfo.arrayy + 1] == '0')
{
if(iMap[(g_pacInfo.x + 19) / 20][g_pacInfo.arrayy + 1] == '0')
g_pacInfo.y += 5;
}
}
else
{
g_pacInfo.y += 5;
}
}