Tell me if I'm making any bad ideas here.
Solid block collision should be done in this order:
- move object horizontally
- perform horizontal collision
- move object vertically
- perform vertical collision
In order to do this it should implement object motion within the collision routine, and everything to be moved by velocity regs, without any object being moved "manually."
Collision should only be checked if the edge of an object has moved over a tile from the previous frame, and in the direction it is moving.
So basically, for an object, you could have two registers that count to the width and height of the tile. When the number in the registers is the same as the width or height, you check to see if you bumped into anything and you also set the number in the register back to 0. Off course, if you have 16x16 tiles and one of the registers is at 14 and you want to add 4, you want to make it 2 instead of 18 or 0.
Sorry for this unrelated question, but how do you go to different parts of code that correspond with what action is supposed to be happening, like if you are on the ground or in the air? Do you use jump tables? I had originally used beq and bne, but that is only really useful for if there are only two different things the object can do.
It's an interesting idea and it certainly seams like a simple solution to the
which direction did I collide in problem.
Assuming that objects are rectangular, for a 16x24 pixel character and an 8x8 grid you only need to check 3 tiles horizontally and 4 tiles vertically, which is also a plus.
I played around with some graph paper and noticed an issue. Allow me to demonstrate:
Imaging you have a block and an object such as:
Code:
BBB
BBB
OOOBBB
OOO
OOO
And the object is moving down/right at -30 degrees (xVel = 1, yVecl = 2)
Then following your algorithm (move horizontal, notice collision, move object out of collision
[assumed functionality], move vertically, no collision) then the location of the object would be:
Code:
BBB
BBB
BBB
OOO
OOO
OOO
Where as if you calculated X and Y positions together, then checked for a collision, the object should be at:
Code:
BBB
BBB
BBB
OOO
OOO
OOO
Maybe your players will not notice, but if your horizontal collision routine removes the objects xVecl then I think they will.
If you do implement this algorithm, I recommend preforming the vertical calculations/checks first. It still has the same issue, but rotated 90 degrees. This case would result with the player standing on the edge of a ledge.
I had some issues with moving both X and Y first, and then doing collision. If I'm walking on pass-through-bottom tiles, it works fine, but when I'm walking on solid tiles I get stuck where the cracks are.
I'm really not sure what's going on with velocity and things. Like I said, I figured that if blocks are 16x16 pixels large, then you only check collision every 16 pixels because there isn't going to be a block halfway in the tile map. You could also still use the x and y collision check, and maybe if both are or over 16, then you could check them both at the same time to make sure there aren't any problems.
Am I even making any sense?
Moving both axis at the same time creates all kinds of trouble. Yes, characters get to go through some corners they woldn't otherwise, but IMO, the worst problem is ejection. Think about it: if you update the two axis at once, and when validating that movement you detect that the object didn't hit a wall, but there was a vertical collision, you'll have to eject the object vertically, and that could invalidate the horizontal motion that you have already considered safe, and the object could get stuck inside a wall.
It's much safer to move and test each axis individually, but there is no universally good order to perform the tests. If you really care about objects being able to land on or jump onto ledges in all extreme cases,
you might have to change the order in which you test the axis depending on the direction of the movement.
Espozo wrote:
Am I even making any sense?
Not to me. You're talking about pixels and counters while all you need is to scan all blocks that could be touching one edge (top, right, bottom or left) of the character. To test blocks at the right, for example, you'd have to check all blocks between (ObjectRight, ObjectTop) and (O jectRight, ObjectBottom), converting all coordinates from pixel space into block space (i.e. divide pixel coordinates by the size of the block - usually 16). Just get the object coordinates, divide by 16 and use them to look up blocks the level map. You don't ever need to think in terms of pixels unless you have slopes.
Have you had a chance to look over
Four-corner collision detection?
tokumaru wrote:
Moving both axis at the same time creates all kinds of trouble. Yes, characters get to go through some corners they woldn't otherwise, but IMO, the worst problem is ejection. Think about it: if you update the two axis at once, and when validating that movement you detect that the object didn't hit a wall, but there was a vertical collision, you'll have to eject the object vertically, and that could invalidate the horizontal motion that you have already considered safe, and the object could get stuck inside a wall.
Here's an attempt to illustrate this problem:
Attachment:
fail.png [ 825 Bytes | Viewed 2277 times ]
So, you move both horizontally and vertically at the same time, then test for a horizontal collision and there are none. Then you check for a vertical collision, and you see the object went past the ceiling. To fix this, you eject the object down, effectively sinking it into the floor. To handle the ejection properly here you'd probably have to check the horizontal axis again, and then the logic starts to get weird IMO.
Quote:
you might have to change the order in which you test the axis depending on the direction of the movement.
Yeah, turns out I was wrong about this. Look:
Attachment:
ledges.png [ 1.19 KiB | Viewed 2277 times ]
The object is moving in the same direction, but in order to land on ledge A, you'd have to check for vertical collisions first, but to land on ledge B you'd have to check for horizontal collisions first. I can't think of a good solution for this right now, so I'd love to see someone else coming up with something.
tepples wrote:
Have you had a chance to look over
Four-corner collision detection?
I'll take a look at it now.
EDIT: Looked at your solution. It's pretty interesting, but like you said in the beginning, the object can't be larger than a block, and that's a huge limitation. How would you expand the technique to work with larger objects?
Espozo wrote:
I'm really not sure what's going on with velocity and things.
The point about velocity is that if the collision routine knows the direction where the object is travelling, the collision check can be done more efficiently (if the object is travelling right, we know that only its right edge can collide, working from the assumption that the object was free from collisions before movement). Compare that to a situation where you only know the new position of the object, not where it came from. "Velocity" might not be the best word for it though in the context of collisions, it feels too... physichy. "Displacement" might be better.
Figure I might as well add my experience on this, I spent a lot of time on my own collision detection. I started off using the method from Sonic 1 as a base, having two vertical sensor lines on either side and one horizontal one, using this as a reference:
http://info.sonicretro.org/SPG:Solid_TilesProblem was my character is about half the height of Sonic, so without some really restrictive velocity caps I couldn't check for both upward and downward collisions using their method. So what I did is I split the routine into some different cases for flying up, flying with low Y-velocity, and flying down, with the Horizontal sensor line positioned at the bottom, middle and top respectively. This allows the space to check for upward and downward collisions without triggering the H-sensor. It also works nicely in that if you're pressing against a wall while flying, you won't start to pass through until you're clear of it in either direction. I guess this probably isn't helpful to you if you're trying to build something much bigger than usual, I wouldn't know... But aside from a few cosmetic problems (See the "Bugs Using This Method" section in that link I linked), it seems a very stable system.
Later when trying to do small-projectile collisions I took a slightly different approach. Instead of the earlier method of sensor bars of fixed length, I checked from its new centre backward along each axis only as far as the velocity, starting with Horizontal. They'd keep getting stuck inside a corner as they flew past - clear on the horizontal check but detecting the vertical collision after and sucking it back into the wall.
I ended up building my projectile collision routine to check horizontal first, then vertical, then check horizontal again from the corrected position IFF you had a vertical collision but NOT A horizontal one. Then if the last collision hit was horizontal (ie/ first H pass hit and no vertical hit, or both vertical hit and second H pass hit), it's a horizontal collision, otherwise treat it as a vertical one.
It is not perfectly accurate as projectiles will tend to catch and bounce off a corner they might have just barely scraped past following a real trajectory, but it's the best I could come up with and it looks pretty realistic in practise provided the speed is reasonable. My code also doesn't seem terribly processor-taxing, but it IS almost totally illegible. Writing that was hell for me.
Definitely curious if anyone knows of any fatal flaws with my concepts. It seems to work for me, I haven't had anything skip out of bounds lately.
tokumaru wrote:
tepples wrote:
Have you had a chance to look over
Four-corner collision detection?
How would you expand the technique to work with larger objects?
Probably by scanning along the leading edge of the sprite. For example, a solid block at center right would be considered solid in top right and bottom right.
Another thing to be careful with is to make sure the bottom of the object is ejected one pixel above the tile instead of the top pixel of the tile, or else it will check horizontal collision within the floor.
So much complexity and we didn't even get to the slopes yet.
tokumaru wrote:
So much complexity and we didn't even get to the slopes yet.
I should mention just in case it wasn't obvious that the method I use DOES handle smooth slopes.
What's ironic is that I paid so much attention to getting pass-through-bottom slopes to work properly, I forgot to check if solid blocks worked properly.
Here is some code that should work once I write the subroutines.
Code:
move_and_collide:
lda {x_position}
sta {old_x}
lda {x_velocity}
bpl +
dec {x_position_hi}
+;
clc
adc {x_position_lo}
sta {x_position_lo}
bcc +
inc {x_position_hi}
+;
lda {x_velocity}
bpl +
jsr left_collision
bra ++
+;
jsr right_collision
+;
lda {y_position}
sta {old_y}
lda {y_velocity}
bpl +
dec {y_position_hi}
+;
clc
adc {y_position_lo}
sta {y_position_lo}
bcc +
inc {y_position_hi}
+;
lda {y_velocity}
bpl +
jsr top_collision
bra ++
+;
jsr bottom_collision
+;
rts
I just realized it is better to do vertical collision first, because vertically hitting a sloped platform does not effect horizontal movement, but moving horizontally along a sloped platform does effect vertical movement.
But then you'd have to compensate for getting kicked upwards before you're pushed back out of a wall, for one thing. I did horizontal first and basically just patched around normal collision on the frame that you land to preserve your speed and such. Seems like a substantial workaround either way.
Though it would probably help at higher speeds to do vertical first, when you have a problem with the horizontal sensor hitting the slope. I guess it depends heavily on the application. I dunno.
If floors and walls are the same thing then you'll have the issue either way, the only difference is which axis… although I never had to compensate in the first place. I think it has to do with the fact that only one axis has moved by the time the first check happens. This means that against a wall, when the vertical check happens you still aren't inside the wall (so no pushing back), and when the horizontal check happens you're already in the final vertical position.
Had another idea. Since a lot of code is spent fetching the tile number from the level map, and using it to look up the collision data, it would be easier and more efficient to have a scrolling collision map, and fetch collision data from there.
I doubt it honestly since most of the code will go in calculating the offset anyway. You could make it simpler by using a look-up table pointing to every row though (then you just fetch the row from there and add the offset within the row, avoiding shifts/multiplication in the first place). The scrolling collision map may still help to allow the map to be stored compressed in ROM though (you decompress the surrounding area in RAM and work on that, assuming the entire level itself wouldn't just fit completely for starters).
EDIT: also before I forget, doing the vertical check first isn't enough for slopes. Depending where you are, you could still not be pushed high enough to be moved into the above row, but then move horizontally far enough to move into the next column, and you'll end up hitting a wall there, causing you to stop. Whoops. The only quick workaround is to do the move/collision step for every pixel. Not as bad as it sounds since it's unlikely you'll be moving many pixels (e.g. in a platformer usually you won't be going faster than 2-3 pixels horizontally, and not that much faster vertically either, and the player would be the only object moving that fast that also requires accurate physics).
I would be able to access the collision data for every surrounding tile, without changing the X index register. I would need to double the collision data map, so it can wrap around.
Sik wrote:
the player would be the only object moving that fast that also requires accurate physics.
In a platformer, sure. Bullets in a shooter are another case. (Of course, then you don't have to deal with ejection.)
Myask wrote:
Sik wrote:
the player would be the only object moving that fast that also requires accurate physics.
In a platformer, sure. Bullets in a shooter are another case. (Of course, then you don't have to deal with ejection.)
Not necessarily. If a bullet collides with a wall in most shooters, the animation for the bullet "exploding" I guess, is usually displayed right outside the wall.
Yeah that's the thing, bullets don't need anywhere as accurate collision detection and response. In fact, the response is always the hardest part since it messes with the physics of the object in question - an object that doesn't need any proper response (such as a bullet, which would just instantaneously stop there) is much easier to program and also generally can have more sloppy detection in the first place.
There's also the fact that when a bullet collides you don't care if it's a handful of pixels too deep. A player or an enemy, on the other hand, need to be pixel-perfect, and even in this case there's some leeway (e.g. enemies usually ignore solid objects and they may treat slopes as surfaces they can't go through, much like a wall, as long as they fulfill their basic purpose).
You're telling me that some games actually have 2 collision routines?
I surely wouldn't waste time calculating bounding boxes for bullets, so I'd most likely treat them as points. I guess that would require a separate collision routine.
Even something as simplistic as Missile Command probably has several collision routines: missiles with the ground, missiles with explosions, and bomber planes or kill sats with explosions.
There are basically three classes of collision routine in my platform game:
1. Test a point against the tile grid and all movable objects (represented as a set of bounding boxes).
2. Test a point, and return a distance to eject in one direction. (There's four of these.)
3. Test two bounding boxes for overlap.
1 is useful for testing things irrelevant to motion. Is the player on the ground? Has a bullet or particle hit a wall?
2 is useful for motion. When you move something to the right, test a point for collision with the world, then return how many pixels you need to move to the left to eject from the thing you collided with. This interacts with other movable objects well, since if you're colliding with both a tile and a bounding box, you can simply return the maximum ejection distance. For most objects you need to test two or three points on the leading edge of the object (corners + however many interior points you need for coverage), and take the maximum ejection distance found.
3 is used for interaction between objects. When to hurt the player. When to trigger a response. This is the most common one, I think. Only some creatures in my game need to respond to walls like with 2, but they all need to respond to touching the player, pretty much.
I knew that tile collision was different than object collision, but I didn't know anyone programmed it 2 different algorithms for the same type of collision.
psycopathicteen wrote:
I didn't know anyone programmed it 2 different algorithms for the same type of collision.
It's obviously not mandatory, but when you have limited processing power, it might be interesting to write more specialized functions for the simpler cases, instead of using the more complex routine for everything. This is true for everything, not only collision detection. Physics, for example, is usually more complex for the main character, while other objects use simpler logic.
Which is easier to program? 1-point slope collision or 2-point slope collision? At first I tried 2-point collision because it makes slightly more physical sense, but I'm having trouble making the back point snap to downward sloping platforms. 1-point slope collision makes platform snapping easier, but the rules of standing at the edge of a tile changes depending if there is a sloped tile there or not.
psycopathicteen wrote:
Which is easier to program? 1-point slope collision or 2-point slope collision?
I prefer to do 1-point, but revert to 2-point when that 1-point goes off the ground.
I know how to make this easy. Give the tiles underneath slopes, matching slope data, so they can eject objects into the slope above it.