Platformer!

[Disch]

firedraco:

I've had great success with a line-based collision system, rather than a tile based system. Tile based systems were always really hard for me to get working (particularly with slopes).

This is a picture I made forever ago which kind of illustrates how it works:

http://i41.tinypic.com/33csm69.png

The '1' series illustrates the first case of an object (green thing) moving towards a wall (black line). The idea is you project lines starting from each corner of the object and have them move where the object is moving. If any of those lines intersect with the wall, you not only know you have a collision, but by examining the intersection point, you also know how far you can move before you actually hit the wall (so it's easy to stop exactly at it).

The '2' case shows that you also need to do the reverse and extract lines from the corners of the walls and move them backwards and see if they collide with any lines of the object.



Pros:
- objects can be moving any speed and you will never go through any wall, no matter how thin or small.
- Makes handling things like slopes much easier
- "true" diagonal movement is effortless (with tilebased, it's awkward because you usually have to move horizontal, then vertical -- which gets weird at high speeds)

Cons:
- constructing line based maps is less intuitive than constructing tile based ones.

[firedraco]

Actually, that sounds a lot more like what I was trying to do. However, it seemed kinda laggy since I had to do the comparison against every wall. Even with just one point (the center as a test) it seemed to lag a bit, like the controls weren't as responsive and stuff.

There were some other things that seemed kind of annoying too. I wasn't really sure how to deal with "standing" on a platform kind of thing, since obviously if I just try to apply gravity and move left/right then they won't move since the intersection point will be right at where they are standing.

[xander333]

firedraco, make sure to work with a fixed timestep to prevent not detecting collisions.

[Disch]

Actually, that sounds a lot more like what I was trying to do. However, it seemed kinda laggy since I had to do the comparison against every wall

Well like shaktar said, you only want to check against nearby walls. In my attempts I didn't make anything as complicated as a kd tree, I just broke the world into "Sectors" (of say, 128x128 pixels), and each sector had a list of all the walls that were in it. Then objects only had to compare against walls which existed in the sectors they were in or passing through (sectors often only had 3 or 4 walls, any more than 7 or so was very uncommon).

Building the lists for each sector takes some time, but you only have to do it once when the map is loaded. Of course this only works for walls that are motionless -- moving platforms would have to be checked separately.

The method you're using to check line intersection can make a big difference, as well. I posted mine on here before (and can again if you need it). If you're calling any trig functions you're doing it wrong.

There were some other things that seemed kind of annoying too

There are definitely situations that need to be addressed, but that's just the nature of platformers.

I wasn't really sure how to deal with "standing" on a platform kind of thing, since obviously if I just try to apply gravity and move left/right then they won't move since the intersection point will be right at where they are standing.

My objects had a "grounded" boolean which was false if they were in the air and subject to gravity. When grounded, I also kept a unit vector of the ground which they were standing on. When they moved left/right, I simply multiplied their movement by the unit vector and they would walk up/down whatever slope they were standing on.

After movement, you do a mock move a few pixels downward to ensure they're still grounded. If you hit a wall, you know you're still grounded, and you update the unit vector to make sure it reflects the new slope. If there's no ground, you know they just walked off a cliff, are no longer grounded, and you can start applying downward force.


There are other things you have to watch for, but it all can be worked out. The end result is very nice.

I made a small demo a while back:
http://www.filefactory.com/file/q6zr22n9m7h/n/PhysDemo_zip

(Sorry about the lame download site, I still have no personal server space)

Arrows to move, space to jump, Down+Space to "drop-thru" the drop-thru walls.

There are 3 maps I was using to test different things. Rename the one you want to try to 'testmap.lmp'

Source available upon request.

[firedraco]

Well like shaktar said, you only want to check against nearby walls. In my attempts I didn't make anything as complicated as a kd tree, I just broke the world into "Sectors" (of say, 128x128 pixels), and each sector had a list of all the walls that were in it. Then objects only had to compare against walls which existed in the sectors they were in or passing through (sectors often only had 3 or 4 walls, any more than 7 or so was very uncommon).

Building the lists for each sector takes some time, but you only have to do it once when the map is loaded. Of course this only works for walls that are motionless -- moving platforms would have to be checked separately.

I see. So then you'd basically just check each point/movement vector to see if it's inside the "Sector", and then if it is, see what it intersects?

The method you're using to check line intersection can make a big difference, as well. I posted mine on here before (and can again if you need it). If you're calling any trig functions you're doing it wrong.

Fortunately, no.

My objects had a "grounded" boolean which was false if they were in the air and subject to gravity. When grounded, I also kept a unit vector of the ground which they were standing on. When they moved left/right, I simply multiplied their movement by the unit vector and they would walk up/down whatever slope they were standing on.

After movement, you do a mock move a few pixels downward to ensure they're still grounded. If you hit a wall, you know you're still grounded, and you update the unit vector to make sure it reflects the new slope. If there's no ground, you know they just walked off a cliff, are no longer grounded, and you can start applying downward force.

Ah, that's sort of what I was going for, but I think I made it more complicated than it needed to be...I was trying to store a pointer to the wall they were "standing" on and calculating stuff on the fly.

I definitely would like to see the source code, at least for the collision detection part.

[Disch]

firedraco wrote:

I see. So then you'd basically just check each point/movement vector to see if it's inside the "Sector", and then if it is, see what it intersects?

Yes. Of course it's possible to move through several sectors (especially at high speeds) so you'd need to check all of them.

I definitely would like to see the source code, at least for the collision detection part.

Here you go (again, sorry for lame upload site):

http://www.filefactory.com/file/78n6scin8weh/n/GameDemoSrc.zip

In the source I seem to be calling them "Blocks" instead of "Sectors". But the idea is the same. Most of it is pretty clean and decently commented. If you have any questions, feel free to ask.

PhysRect::Update in physrect.cpp is where the overall movement/physics/collision starts.

PhysRect::DoMoveHit in physrect.cpp is where it actually checks collision with walls.


EDIT: also the source uses an old WIP version of SFML2 so you probably won't be able to compile it without tweaks.

[Disch]

xander wrote:

@EssGeEich: Yeah I REALLY couldn't find any fitting music!
So I just slapped some oldskool rap on there :D

Check out Ryoko's Theme from Tenchi Muyo ( http://www.youtube.com/watch?v=gQxsyEIT78c ).

I find that it fits these kinds of games perfectly, and is kind of catchy.

XD

[zwA4jE8b]

nice game xander. way better than mine :P

[LB]

Using the sector system, what if a wall is not crossing into a sector but it is on the very edge? Would you pass through it? Don't secors have to overlap a bit?

[Disch]

that's not really possible.

Say you have sectors that are 128 pixels wide. That would imply that [0..128) is one sector, and [128..256) is the next. So if you have a wall that lies exactly on 128, it would fall into the 2nd sector. Even with floating points there's a clear boundary. 127.99999999 is one sector and 128.00000001 is another.

If you are really concerned about missing an edge case, you can pad object movement so that it will "spill into" other sectors when it's close enough. Say for example an object is moving from 100 to 127. Normally you would only check sector 0, but if you are worried about missing an edge case you could pad it 5 pixels or something (for purposes of determining the sector) which would push it into sector 1.

[LB]

Say you have sectors that are 128 pixels wide. That would imply that [0..128) is one sector, and [128..256) is the next. So if you have a wall that lies exactly on 128, it would fall into the 2nd sector.

And what if the player is in the first sector?

Normally you would only check sector 0, but if you are worried about missing an edge case you could pad it 5 pixels or something (for purposes of determining the sector) which would push it into sector 1.

This is what I am talking about, it effectively has the same effect as making the sectors overlap.

[Disch]

And what if the player is in the first sector?

If the player is in the first sector and remains strictly in the first sector after moving, then they would never collide with the wall in the 2nd sector, even if that sector is right on the border.

Even if they get really close (127.99999) that still is not a collision so you don't have to check that wall.

This is what I am talking about, it effectively has the same effect as making the sectors overlap.

Yes, but really this isn't necessary. It's just something to do if you're paranoid. I don't really think you'd miss any collisions by not doing it. I don't do it in mine and I haven't had any issues with missed collisions.

[LB]

Disch wrote:

If the player is in the first sector and remains strictly in the first sector after moving, then they would never collide with the wall in the 2nd sector, even if that sector is right on the border.

Which means they would go through the wall as though it weren't there, right?

[Disch]

No. They wouldn't even be approaching the wall.

I think we are talking about 2 different things here.

You don't just check the sector that the object is in. You check all the sectors that the object is in and moving through. You can do this by creating a larger bounding box that encloses the object before and after the move. You then check every sector that the bounding box lies in.

[LB]

So, in other (very simplified) words, you have to check nearby sectors as well - having the same effect as overlapping sectors (in my mind). This was what I expected, I guess I was thinking about it in an opposite way from you. Thanks Disch!

[Disch]

So, in other (very simplified) words, you have to check nearby sectors as well - having the same effect as overlapping sectors (in my mind).

Not really, they're not the same.

If you are moving insanely fast and move 1000 pixels in one step, then you will need to check 8 or 9 sectors. That can't be accomplished simply by overlapping them. Checking "nearby" sectors also doesn't work because a sector 9 sectors away is not nearby.

Really it's not that complicated. Just check all the sectors that the object is in and moving through. Before and after the move.

[LB]

If you are moving insanely fast and move 1000 pixels in one step,

Wait, what? I thought the whole point of steps was to move no faster than the size of the character's collision box and move 1000 pixels over many, many steps...why would you move all 1000 pixels in one single step?

[Disch]

Nah, see you don't have to do that with this approach.

Maybe step was the wrong word. Maybe "update" was better. If you are updating your world 60 times per second, and an object is moving 1000 pixels in that update, then it will span over several sectors in a single update.

You do not (and should not) break that update up into smaller steps. It'd be pointless.. it would only slow the game down by making it do more calculations.

One of the beauties of this line-based collision is it works on all movement of any speed. There is zero risk of "tunnelling" through walls by moving too fast.... no matter how small or thin the wall is.

[kidd106]

If your still looking for a plot, you could use something similar to one of the plot lines that are in Wesnoth with Delfador being the character in the game.

[xander333]

I've been playing around with the menu screens, it's a lot harder to make an aesthetically pleasing menu than I though! I have a few sketches:

http://imgur.com/MRb5e&QXlao#1
http://imgur.com/MRb5e&QXlao

The map is going to be Mario-style, if you know what I mean.

What do you think? How can I improve?