Tile Collision help

[Deux]

Hi all

I am looking for a good method for tile based game collisions, I am familiar with AABB ( Axis Aligned Bounding boxes ) and the usual bounds checking within arrays.

I want the incremental steps of my player to not equal the tile steps, example, if my tiles are 32x32, and my map array plots them in 32 unit increments, I want my player for example to move in 3 unit increments. This is a problem with normal array bound checking as the playerx/32 and playery/32 bounds checking no longer works, unless I specify upper left, upper right, lower left and lower right bounds checking. I am experiencing big problems with this. My solutution is shoddy to say the least

Basically I want to know if there are any other methods I could/should employ.

Thanks guys.

[Nikster]

what you already have should work to find if you're actually on a collision tile, I'm guessing you're having problems with actually making sure you are touching the edges when you cross a boundry, if so this can easily be done by taking your positions and anding with ~31 if you are going up or to the left and add 32, and the same for right, down but subtract 1 from the result. Then again I could have misread what you're wanting to do as always :)

[sparkyboy]

Why do you want to move 3 pixels(if I understand you correctly!!).In my opinion it's always best to have your map cells and movements divisible by 2!
Therefore, you can always check for when a sprite hits the centre of a cell easily!!! ;)

In one of the games I did, the cells were 16 by 16, but the speed of the sprites were 1,2,4 and 8 pixel steps!! :)
Did I miss any cell collisions, NOPE!!!! ;)
I also did a pacman/bomberman clone, and you know when you move left or right, and you move down or up, well if you are not correctly in the cell, you have to tap tap and hope you enter the cell where you change direction CORRECTLY!!!

Well my solution was simply to ensure no matter what direction key you hit, the player would not move in the requested direction UNTIL it was exactly in the centre of the cell.

How was this this possible.......because all my movements and cells were divisible EXACTLY by 2!!! :D

ET VOILA!!!!!!

Edit:
And as nickster says, you check for the tile ahead of your pixel, and if by any chance you go into the tile, you simply adjust your player's sprite position before drawing it!!!I mean, how often do you think a sprite shoots past the edge of a screen????....It's always reset to the edges of the screen plus or minus the 'HANDLE' of the sprite!!!!

All the best

Mark.

[Adrian Cummings]

Hmmm yes that is not good tho if you want to add inertia to your sprite for example where the sprite movement speed in pixels is and odd number really.

You would need to AND the x,y sprite pos values with the width and height of the tile and add then finally add this fine position 'overflow' to the x & y to get the correct tile you are checking against.

Countour tiles (ramps) are a bit harder but similar principle.

Adrian.

[Deux]

aha !

Thanks guys, I think you have helped me :)

Will report back soon :)

EDIT **

Should I post the bmax source code here for all to see ?

EDIT** 2

what you already have should work to find if you're actually on a collision tile, I'm guessing you're having problems with actually making sure you are touching the edges when you cross a boundry, if so this can easily be done by taking your positions and anding with ~31 if you are going up or to the left and add 32, and the same for right, down but subtract 1 from the result. Then again I could have misread what you're wanting to do as always :)

HAHA !!! This works ! Yeah, I need to do bounds checking on 31, not 32

like so


If KeyDown(KEY_LEFT) Then
If px > 0 Then px:-PLAYER_INC
If px < 0 Then
px=0
Else
If Collision(px,py) Then ' upper left
px:+PLAYER_INC
Else If Collision(px,py+31) Then 'lower left
px:+PLAYER_INC
End If
End If
End If


Thanks so much for the help guys, it is greatly appreciated !

[sparkyboy]

Hmmm yes that is not good tho if you want to add inertia to your sprite for example where the sprite movement speed in pixels is and odd number really.

You would need to AND the x,y sprite pos values with the width and height of the tile and add then finally add the fine position 'overflow' to the x & y to get the correct tile you are checking against.

Countour tiles (ramps) are a bit harder but similar principle.

Adrian.

True Adrian, inertia would pose a problem in a CELL based game(unlike a platformer for example ;) )
However I've yet, personally, to see inertia implemented in a cell based game!! :) ALA Pacman, bomberman........Sonic YES!!

Edit:
Even with inertia, that surely would be a seperate variable, so in a cell based game I think it would be possible to disregard the final sprite position+ inertia and use the last recorded sprite position + new position - inertia!! Never tested this, but should work if implemented correctly!
All the best

Mark.

[Adrian Cummings]

Hi,

Well ok but you should'nt really be doing your sprite to tile collision like that.

You should have stored the SpriteXPos and SpriteYPos then you would divide the SpriteXPos and SpriteYPos like this:

TileX=SpriteXPos>>5 // Divide by 32 (Tile width)
TileY=SpriteYPos>>5 // Divide by 32 (Tile Height)

Tile2Check=MapArray[(TileY<<5)+TileX]; // Check tile under this sprite.

switch (Tile2Check)
{
case 1: // Ground.
Do stuph to sprite.
break;
case 2:
Do stuph to sprite. // Wall.
break;
Etc.
}

Something like that anyway :)

Cheers,

Adrian.

[Deux]

Yeah I am doing that :)

my collision func looks like this


Function Collision:Byte(x:Int,y:Int)
Return map[x/32,y/32]
End Function

[sparkyboy]

Sweet ade, like the 'BIT SHIFT', so much faster than multiplication or division......go figure ;) , but as always.........each to his own...AND.....
IF IT AINT BROKE...DON"T FIX IT!!! :D


All the best

Mark.

[Adrian Cummings]

Yes sorry... as long as it works dont fix it I agree! :)

There always a better way to do something but yeah at least do << >> bit shifts rather than divides at least as it will make a difference to run speed if you do lots of even divides in you game like /2 /4 /8 /16 /32 etc.

An oldie but goldie that one!.

Cheers then,

Adrian.

[Deux]

yeah, I will employ that method as I am doing a long of divides and multiplication :)

Thanks again guys for the help, and speedy replies :)

[Adrian Cummings]

Coolness... right I must get back to work now :)

[sparkyboy]

hehe no need for sorry ade, you are well respected in my eyes bud!! :)
There you go guys, use BIT SHIFT in place of multiplication/division!! :D

It may be the difference between blitting your stuff every frame compared to every 1.5 frames!!! ;)

And we all know what that means.............beef 'JERKY'!!! :D


Kudos

Mark.

[sparkyboy]

Another thing guys, remember that arrays and structs are your friends!! ;)

If you change direction and/or speed, store ALL possibilities in a TABLE.....
so instead of..

spritex+=speedx
spritey+=speedy

use:

spritex=speedxtable(speedx)
spritey=speedytable(speedy)

Can't remember exactly, lost nearly all me source from years ago, but basically, why use MATH when you can just look it up in a TABLE!!!!! ;)

Laters

Mark.

[soniCron]

Can't remember exactly, lost nearly all me source from years ago, but basically, why use MATH when you can just look it up in a TABLE!!!!! ;) Well, if the lookup table is too big to fit into the CPU's cache, you're going to get a greater speed hit than if you were to do plain math. (Of course, this depends on how complex the math is, but for trigonometric equations, logarithmic functions, etc, the above holds true.)

[luggage]

I can't tell if you're joking or not with the amount of exclamations and winking things you stick in there.

But just in case someone is reading this who isn't sure. Ignore the post about sticking everything into tables. You're opening yourself up to a whole world of pain by doing it this way for absolutely no benefit.

And I'd also not worry about using bitshifts - if you're using a decent compiler let it optimise the code for you. Better to have the readable code.

[soniCron]

But just in case someone is reading this who isn't sure. Ignore the post about sticking everything into tables. You're opening yourself up to a whole world of pain by doing it this way for absolutely no benefit. It's entirely dependent upon the situation. For this, yes, it's overboard. But for something like realtime DSP, that's another story. (And the "!!!" means he's drunk. ;))

[luggage]

And for someone who is doing realtime DSP do you think they'll need to be told this? People who would read that bit of 'advice' and take it on board aren't likely to be the type of coders who will be doing realtime DSP anytime soon.

[soniCron]

And for someone who is doing realtime DSP do you think they'll need to be told this? People who would read that bit of 'advice' and take it on board aren't likely to be the type of coders who will be doing realtime DSP anytime soon. Pardon. I'll think twice before clarifying your posts in the future.

[Deux]

dont worry I wont be using LUTS for this scenario

the only time I may use LUTS is for sin and cos.

* EDIT

erm, why do a lot of people like fighting on this forum ? :)

I got the answers I was looking for here very quickly, hehe.

[sparkyboy]

I can't tell if you're joking or not with the amount of exclamations and winking things you stick in there.

But just in case someone is reading this who isn't sure. Ignore the post about sticking everything into tables. You're opening yourself up to a whole world of pain by doing it this way for absolutely no benefit.

And I'd also not worry about using bitshifts - if you're using a decent compiler let it optimise the code for you. Better to have the readable code.

Thanks Dan, I am indeed a bit tipsy( ;) ), but Chris I think you are wrong to dismiss my post.Maybe I'm too old school and the need for tables, loop unrolling is no longer necessary, I don't know, I have not done any tests (nor programming for that matter :D ) on the beasts that are available today!

All I know is optimization by hand, was way better than letting some compiler totally screw up your program because you asked it nicely to OPTIMIZE for you.

Structures and Tables do have their place....!

Edit:

I also fail to see what pain is involved in PRE-CALCULATIONS!! ;) It may not seem evident at the moment, but when your rendering starts to stutter those pre-calcs could just about be your saviour.

All the best

Mark.

[luggage]

Better to not optimise until you realise there's a problem. Profile it and look where the time is going.

If you're spending 99% of your time in the renderer then sticking your movement into a table isn't a good optimisation. Easier to save 1% of 99% than 99% of 1%.

Better to spend time worrying about writing a good game than wondering if you should generate huge tables or use shifts.

[Deux]

Just another question

how would one employ slopes in tile games ? How would one handle collision and response from that ?

[luggage]

One of the easiest ways would be to define your slope as a bit of maths.

For a 45 degree slope like '/' that maths is 'y = x'...

Work out the offset into a tile you're currently at (worldX % 32). Say you're 3 pixels into said tile.

Now your height would be the bottom of the tile + the xoffset you've just worked out. So just add 3 onto your height. As you move across the tile your height would rise.

For a tile the other way '/' you height would be tileWidth-xoffset.

Another way, and this is where lookups are useful...

run through each tile graphic. Start at the x=0, y=0. Keep incrementing y until you hit some solid tile. Store this value. Now move onto the next X and do the same. Say your tile is 32 pixels wide you'd end up with a table for each tile like yOffset[32].

Now work out the xoffset into the tile (worldX % 32). Look at the table you made so and do worldY = worldY + yOffset[ xOffset ];

[sparkyboy]

Point taken Chris and assimilated.I wasn't disregarding what you say, after all you're a PRO developer I am NOT!!!

I'm just speaking from personal experience, as regards 2D blitting,NO 3D here...no sir!!
In all my tests, pre-calculations produced faster iterations if you will (with albeit a bit of assembly thrown in for good measure) :D

But that was all in DOS mode 13h, 320 by 200, so may not be relevant in todays market!
However I never dismiss offhand...always get a second opinion so to speak! :)


Kudos

Mark

P.S.
Deux you had to ASK didn't ya eh!! :D ;)

[Deux]

ahh i see, that should work just about fine ! :)

say, do you mean modulus ? (World % 32) or divide (world / 32) in your example ?

I can never understand mod :(

[sparkyboy]

Mod is the remainder of a division!!

So 32 mod 10 would give you 2!! :)


Sleepy

Mark.

[luggage]

If you use (worldX / 32) that will give you what tile you're on in your world array.

If you use (worldX % 32) that will give you what pixel you're on in that tile. As Sparky said - it's the remainder.

tileX = worldX / 32;
tileY = worldY / 32;

offsetX = worldX % 32;
offsetY = worldY % 32;

tile = myWorld[ tileX ][ tileY ];

worldY = worldY + tile.heightOffset[ offsetX ];

[Deux]

yeah, but how would it work in the above example ?

if my world pos is 10 and div by 32 that is 0.31, but 10 mod 32 is 10
:confused:


EDIT* oh ok, thanks luggage !

[Savant]

All I know is optimization by hand, was way better than letting some compiler totally screw up your program because you asked it nicely to OPTIMIZE for you.
Yes, was.

I can count on one hand the number of times a compiler has given me a problem optimizing code in the last 5 years.

[Adrian Cummings]

Oh well I'm just to old skool for some of you guys I guess - we never had C or java niceness in my day it was all low level asm :o

Regards the contour slope tiles you could do this once you have worked out what 32x32 tile and pixel in x in the tile you are on.

SpriteYPos=SpriteYPos|31; // Force 'OR' to bottom of tile.

SpriteYPos-=Contour0[XOffset]; // Combine y-offset contour.

Contour0[32]={4,4,4,4,4,4,4,4,3,3,3,3,3,3,3,3,2,2,2,2,2,2,2,2, 1,1,1,1,1,1,1,1}; // Right 22-degree slope tile 1.

This is the best way to add in the y offset to the sprite so it can walk up a ramp for example then you can add inertia and gravity to make a ball say roll up and down 2d slope.

I'm going now as this might turn into my balls are bigger than yours contest and my balls are quite big enough thanks :)

Adrian.

[sparkyboy]

Oh well I'm just to old skool for some of you guys I guess - we never had C or java niceness in my day it was all low level asm :o

Regards the contour slope tiles you could do this once you have worked out what 32x32 tile and pixel in x in the tile you are on.

SpriteYPos=SpriteYPos|31; // Force 'OR' to bottom of tile.

SpriteYPos-=Contour0[XOffset]; // Combine y-offset contour.

Contour0[32]={4,4,4,4,4,4,4,4,3,3,3,3,3,3,3,3,2,2,2,2,2,2,2,2, 1,1,1,1,1,1,1,1}; // Right 22-degree slope tile 1.

This is the best way to add in the y offset to the sprite so it can walk up a ramp for example then you can add inertia and gravity to make a ball say roll up and down 2d slope.

I'm going now as this might turn into my balls are bigger than yours contest and my balls are quite big enough thanks :)

Adrian.
Not for me you aint Ade!! :cool: There you go a sweet example of using pre-calculated arrays!!

Going to bed soon

mark.

[Adrian Cummings]

Happy kipping dewd :)