# Collision detection with a tilemap- raping the walls

## Recommended Posts

KellerHood    104
I am using Java to make a 2d platformer, and I am having trouble with the enemies. I am using rectangles and the [i]intersects [/i]method to detect collisions. I just want the enemy to run back and forth between two bricks.
Here is my code:
[code] public void checkCollision() {
for (int i = 0; i < map.tiles.size(); i++) { //map.tiles is an ArrayList of the tiles on the map and size() is how many tiles are on the map, we are looping through each tile
Tile temp = map.tiles.get(i); //temp is the handle to the tile we are on (not physically on, but what tile we are on in the loop)
if (map.tiles.get(i).index != 0) { //checking if the tile is not blank, if there is actually a brick or whatever there
if (bounds.intersects(temp.bounds)) { //bounds is the rectangle that encapsulates the object. It is used for detecting intersections.
if (getX()+32>temp.x) //getX(), the x coordinate of the object, temp.x, the x coordinate of the current tile
setX(getX()-1); //push the enemy outside of the block, so he doesn't collide with it again.
if (getX()<temp.x+32)
setX(getX()+1); //same, but in opposing direction if he is going the other way
hspeed = hspeed * -1; //reverse the horizontal speed
}
}
}
}
[/code]

The enemy is suffering from what I call 'rape the wall syndrome', meaning he is just bouncing back and forth, on a single brick like this when he runs into one:
[~] = enemy
[_] = brick
vertical order of frames:
[~] [_]
[~][_]
[~]_]
[~][_]
[~] [_]
[~][_]
[~]_]
[~][_]
[~] [_]
and repeat.

More about the enemy- he is a 32x32 square, and he is raised one pixel above the tiles on the ground so as not to collide with them, and have him reverse his direction in the same spot. In his 'main loop' his X coordinate is updated by his vertical speed like so:
[code]setX(getX()+hspeed)[/code]
I don't know why he is doing this, and I don't know how to solve this. Thanks in advance to whomever can help me find the solution.

##### Share on other sites
coderWalker    127
Man not trying to be harsh but [b]drop the list[/b] totally first.
This will cause LOTS of problems with Logic, Performance and Memory!

Lets say you want to have a level the size of Super Mario Bros 1-1:
[img]http://www.vgmaps.com/Atlas/NES/SuperMarioBros-World1-1.png[/img]

[b]Memory:[/b]
This level contains 5936 blocks!
If thier represented by ID's that would only be 5936 bytes

[b]Performance:[/b]
Meaning for everything on screen that's moving you are going to have loop running that loops with all those statements 5936 times!
Again in the Mario level you would be lucky to get 60fps even with something this simple.

[b]Implementation:[/b]
The best way to do this is to have a [color="#0000FF"]unique id[/color] for each tile.
A great practive for collision would be to have [color="#0000FF"]0 [color="#000000"]for an empty block.[/color][/color]
Then have a [color="#0000FF"]2d Array[/color] [color="#000000"]and stor[/color]e all the id's in the array.

[b]Drawing:[/b]
Basically when drawing have 2 for loops to draw the level, very simple.

[b]Very Fast! Collision Routine:[/b]
(This routine will always take the same amount of time,
while the above routine gets [i]Exponencially slower[/i] when the number of blocks increases)
Then when checking for collision just:
Take the coordinate of the enemy and say for example
[code]
bool collide()
{
if (tile[enemy.x-1,enemy.y] != 0)
{
return true;
}
else if (tile[enemy.x+1,enemy.y] != 0)
{
return true;
}
else
{
return false;
}
}
[/code]

CoderWalker

##### Share on other sites
KellerHood    104
Well, what if he is not moving an entire block over every frame? He is only moving two pixels, and your method suggests that there is a block at each pixel, but there is a block at every 32 pixels. Also, the enemy (and the player) are rectangles, not pixels.

##### Share on other sites
coderWalker    127
Most games use the tiles for [color="#0000FF"]static[/color] objects (ones that dont move).
Sorry I didn't mention this.

Meaning the enemy would not be drawn with the map.
if each tile is 32x32.

The solution is:
tile.x = enemy.x/32;
tile.y = enemy.y/32;

Since this is integer division they will get "Snapped" to 32x32 positions

ex:
1 = 36/32;
0 = 14/32;

then check tile[1][0]

Anything that is [color="#0000FF"]Dynamic [/color](not snapped to the map) should:
Draw itself
Have Actual Pixel coordinates instead of tile coordinates

What I talked about above was implemented in many games Mario, Zelda, Donkey Kong.

Evidence:

Attached to map?
--------------------------
Soldier - No
Weapon - No
Grass - Yes
Dirt - Yes
Fence - Yes
Plant - Yes

##### Share on other sites
owl    376
Codewalker's advice is good. I'd take it.

[size="1"]@codewalker: Asking for members to rate you up is like asking a girl to get in your pants. The chances of it working (for free) are negligible. Removing any suggestion to it from your post will increase your chances.[/size]

##### Share on other sites
Trienco    2555
[quote name='keelx' timestamp='1306100348' post='4814356']
[code]
if (getX()+32>temp.x) //getX(), the x coordinate of the object, temp.x, the x coordinate of the current tile
setX(getX()-1); //push the enemy outside of the block, so he doesn't collide with it again.
if (getX()<temp.x+32)
setX(getX()+1); //same, but in opposing direction if he is going the other way
[/code]
[/quote]

Are you sure +/- 1 is going to be enough to not still be stuck and just causing collisions (or rather intersections) every single frame? You could also consider the amount of movement and how much of that was used to get to the block and how much is left and should be used to move away from the block (at least pretend the world doesn't stand still between frames).

Since I have no idea if your getX returns the left side or the center, I'll take a guess that X is left and 32 is the size of the object AND block (consider using a named const instead of magic numbers).

So,

insideX = getX() + 32 - temp.x

is how far inside the block you ended up. Now either your new position should be

setX(temp.x - insideX)

(since you should bounce off when you HIT the block, not when you've already moved halfway into it)
or at the very least

setX(temp.x) (-1 if you want to be on the safe side).

##### Share on other sites
KellerHood    104
Very nice! Now I don't have to rewrite my entire game code. But now he bounces one direction but goes straight through blocks in the other direction.

##### Share on other sites
Trienco    2555
[quote name='keelx' timestamp='1306214311' post='4814884']
Very nice! Now I don't have to rewrite my entire game code. But now he bounces one direction but goes straight through blocks in the other direction.
[/quote]

How did you adjust the lines for the other direction? The code above only handles collision to the right.

##### Share on other sites
Sirisian    2263
[url="http://assaultwars.com/javascript/miner.html"]Oddly enough I was bored yesterday and made this.[/url] Right click view source and look at the update code to see how to handle tile collision and response between an entity. It might help you to see what your problem is. In regards to an enemy moving left until he hits the edge and reversing you just do Math.floor(entity.Position / tileSize) or in C++:
int tileX = static_cast<int>(entity.x / tileSize);
int tileY = static_cast<int>(entity.y / tileSize);
if (!map[tileX - 1][tileY + 1].Collidable)
{
// Set internal minimum move left to tileX * tilesize which is the far left of the current tile the entity is on.
}
For moving right:
if (!map[tileX + 1][tileY + 1].Collidable)
{
// Set internal minimum move left to tileX * tilesize + tileSize which is the far left of the current tile the entity is on.
}

Also if your enemy collides with a tile and the minimum translation distance for x is > 0 then just set direction to right and if it's < 0 set it to left.

##### Share on other sites
KellerHood    104
Okay. Solved. Although I think the best way would have been the 2d array of tiles, and the separation of object-space and tile-space, however as to avoid a complete rewrite, my new working code is as follows:
[code]
public void checkCollision() {
for (int i = 0; i < map.tiles.size(); i++) {
Tile temp = map.tiles.get(i);
float insideX;
if (map.tiles.get(i).index != 0) {
if (bounds.intersects(temp.bounds)) {
if (hspeed > 0 && !collided) {
insideX = (getX() + 32) - temp.x;
setX(temp.x - insideX - 32);
hspeed = -1;
collided = true;
break;
}
if (hspeed < 0 && !collided) {
insideX = getX() - temp.x + 32;
setX(temp.x + insideX - 24);
hspeed = 1;
collided = true;
break;
}
collided = false;
}
}
}
}
[/code]

##### Share on other sites
Trienco    2555
[quote name='Sirisian' timestamp='1306262975' post='4815243']
int tileX = static_cast<int>(entity.x / tileSize);
int tileY = static_cast<int>(entity.y / tileSize);
[/quote]

I see trouble unless you limit it to positive numbers. -1 should always be in tile -1 but ends up 0 unless you add special handling for negative coordinates.

Shouldn't the left side be:
insideX = (temp.x + 32) - getX(); (the right block edge minus the objects left edge
setX(temp.x + insideX); (the right block edge plus the amount you have to bounce back)

The numbers in your code confuse me. Where did 24 come from? Why the additional -32 after colliding to the right?

Wait, I noticed one bug in my code. You need to
setX(temp.x - 2*insideX)
(once to move "out" of the block, twice to where you should be after bouncing back)

So the fixed collision to the left would be:
setX(temp.x + 2*insideX)

And to exploit the neatness of math

[code]
if (hspeed > 0)
insideX = (getX() + 32) - temp.x;
else
insideX = getX() - (temp.x + 32);

//or more compact and confusing: insideX = getX() - temp.x + (hSpeed * 32);

setX(getX() - 2*insideX);
[/code]

edit: damn non-descriptive names. getX, not temp.x

##### Share on other sites
KellerHood    104
Yes, that was what I had done originally (with the exception of multiplying the insideX by 2), but for some reason the enemy would then start flickering left and right, without moving, when he touched a wall. After much trial and error, this is what I got. Not entirely sure why it works, but it does. And as for subtracting 32, it made for smoother looking animation. Same for adding 24, but if I added 32 on that side it would end up on the other opposite of the block.

##### Share on other sites
Sirisian    2263
[quote name='Trienco' timestamp='1306300188' post='4815448']
[quote name='Sirisian' timestamp='1306262975' post='4815243']
int tileX = static_cast<int>(entity.x / tileSize);
int tileY = static_cast<int>(entity.y / tileSize);
[/quote]

I see trouble unless you limit it to positive numbers. -1 should always be in tile -1 but ends up 0 unless you add special handling for negative coordinates.
[/quote]
Indexes into an array are normally restricted to positive numbers. You see in a tile based game the tile map is normally represented by a multidimensional array either indexed with y * width + x or using jagged arrays so the restriction of only positive numbers is there.

##### Share on other sites
Trienco    2555
[quote name='Sirisian' timestamp='1306340859' post='4815644']
Indexes into an array are normally restricted to positive numbers.[/quote]

Yes, but entity positions aren't tile indices and you add implicit limitations to one level of abstraction (object positions) based on a much lower level (layout in memory). I'll not bring up languages where negative indices are perfectly normal and common, since we're talking Java here. Still, you should point out that your code requires positions to be limited to values >tileSize and <worldsize - tileSize not only to prevent "falling into the void", but because any position on or beyond the first or last tile will cause access violations.

[quote]Yes, that was what I had done originally (with the exception of multiplying the insideX by 2), but for some reason the enemy would then start flickering left and right, without moving, when he touched a wall. After much trial and error, this is what I got.[/quote]

You should avoid the "trial and error shortcut", it will only result in stuff that looks like a working solution, but blows up every 100th time (which is the most annoying kind of bug to find). What if your randomly chosen value of 24 only works for 75% of cases, because for the remaining situations it should have been 25 or 29? What if in two weeks you suddenly see objects flickering twice and then pop out on the wrong side of a wall?

Programming means analyse and understand the problem, create an informed plan to solve it and then implement that plan. Seriously, you are currently dealing with the most trivial kind of collision you will ever get. It's only 1 dimensions and you're not even checking for actual collision, but for intersection (which can easily fail with fast moving objects and/or variable time steps). If you decide you can't be bothered to wrap your head around the problem while it's simple, how do you expect to get anything done when you add a second dimensions or want objects that move more than 32 pixels per frame or add thinner blocks as walls?

Look at how you calculate insideX for collisions to the left and right: Notice something? It's the exact same thing. You add 32 and subtract temp.x. The whole point is to determine how much you overlap the block and how much to bounce back. While you _could_ still exploit the fact that apparently everything is 32 wide, but that's not going to make the code any easier to understand.

You can of course ignore the idea of "how close was the object to the block before colliding and how much of it's movement should have already happened in the other direction", in that case you don't need any calculation except for placing the object to the left (temp.x - 32) or to the right (temp.x + 32) and change the direction (hspeed *= -1). Just make sure to use a method you actually understand and could explain (nothing more embarassing than answering "that's cool, how does it work" with "uhm... no idea, I just randomly put some stuff there until it kind of worked most of the time").