Player movement on uneven terrain / in polygonal environment

Game Play & Game Design
#1

This is in my head for the last couple of days now:
Imagine a world (2D, sideview), where everything is made out of polygons. One of that polygons is the player character (human). Now I want to move the player. I’m thinking in 2D here, but the problem must be quite common in 3D worlds. How do modern games do the movement of the player in such an environment? Does anyone know?
Googling unfortunately didn’t help…

My current approach is:

  1. move the player according to key input
  2. do collision detection
  3. if a collision occured, shift the player up, until no collision is detected anymore
  4. if the player was shifted about max-length and there still is a collision, there seems to be a real collision with a wall or something, reset player position

There are problems comming with that, one of them is:
The player polygon is a box. Standing on a line going up 45 degrees or something like that, it looks like one of the players feet is floating in the air. I could just move the player a bit down so that both feet are on the ground, but then I’d have to handle the collisions coming with that.

Am I doing something terrible wrong? Is there a “standard” approach for moving in polygonal environments? Any hints and thoughts are highly appreciated :slight_smile:

#2

If your player is side-on you could use two boxes for him (full-height, side by side) which see-saw up and down as his feet move, so if his front foot is raised the front box is raised also. Then follow your approach as before.

#3

Such collision detectioin is known as intersection of 2 Shape’s . e.g. 2 Rectangle’s are instancied on the bottom-side and top-side and the Player bounds Rectangle is always intersected with the both Rectangle instances, if the resulting Rectangle of the intersect isn’t empty, then a collision event must be thrown to an extra function that pushes back the Player model to not-intersecting bounds. :smiley:

#4

That sounds interesting, but this comes with the problem to find out which foot actually must be raised. Seems not that easy to me, any ideas?

Sorry, I don’t get it: what do you mean by “the resulting Rectangle”?

#5

Surely it is trivial to know which box should be associated with which foot?
Having said that, an interesting side-note… JKA (Jedi Knight Academy aka Jedi Knight 3) got this the wrong way around, and never fixed it!
When hanging your left foot off a drop, your right foot would be the one dropping down - into the floor =)

#6

With platformers I find that the obvious approach of moving a bounding box/shape and detecting collisions isn’t a good idea. It works ok for collisions with walls and other obstacles, but for actual surface walking and movement it’s not sufficient. Remember that for a platformer the surface movement is key to having a playable and enjoyable game, so it’s not really unusual to want something more customised and suitable.

An approach I find works well is to store what geometry you’re currently on, and an offset within it (so if you’re doing a platformer, that would be a 2d line segment and a distance along it). Movement then involves increasing or decreasing the distance along the surface, and if you go off one of the edges either finding another edge to walk onto or starting to fall under gravity.

Actually displaying the character with their feet on the ground is tricky, but it’s only really a graphical problem - it shouldn’t affect your gameplay. For 2d I’d just move the sprite down a tad so both feet are within the surface, and possibly have different running animations for two different ground angles if you can afford that and pick the closest. If you want a more technical solution then you can try rotating the sprite to align with the surface normal, but for people on steep surfaces this can look weird (would be ok for small changes in angle though).

It’s worth noting that for 2d this is mostly overkill - even commercial 3d games rarely change the animation and foot position for characters going up and down slopes,

#7

(attachements don’t work at the moment, so here we go: http://img408.imageshack.us/img408/4666/examplesqd5.png)

I attached an example. Look at number 1: it’s obvious that the right foot must be raised, but how to recognize that in the program?

That also sounds like a nice approach. But it seems like it brings further difficulties, like in example 2: the player walks on the ground (one polygon) and before him there is a small stone (another polygon). Any ideas about that?

By the way, thanks for the interesting posts guys :slight_smile:

#8

I’d be inclined to avoid the situation in the first place. Either by making the stone non-steppable (and being ignored for collision) or by making the collision surface one continuous surface (possibly a separate, invisible surface rather than using the actual visible geometry). If you really want to do it that way then you could probably convert the separate polys into a single continous surface in a preprocessing step. That would also have the nice side effect of making collision checks quicker since you could remove a whole bunch of redundant edges (like the bottom surface of the rock).

#9

see if you can imagine a field of table-tennis is compound of 1 rectangle, top-side viewed. Then getting the coordonates of the table-tennis small white ball, use the !Rectangle.intersect(field.getBounds(), ball.getBounds()).isEmpty() to find where the ball hit !
The resulting (aka returned instance of the previous function) Rectangle is got to be non-empty to find an valid Rectangle surface. the Rectangle is compound of 4 coordinates in Java2, those are : x, y, width and height. using getBounds() we can recover a rectangle with all the surface or shape (3-Dimensional polygon) intersecting the field and the ball.
From a Rectangle instance, getX() getY() getHeight() getWidth() recover all the data we need. 8)

#10

Be careful with this. I did a similar approach and it has its fair share of problems. One is that the steeper the hill, the “faster” the player is going to move. This is because as the slope increases (the y change becomes greater and greater than the x change), the same tiny x change will produce a drastic y change. On a flat ground where you are trying to move x 5 pixels, you will move a total of 5 pixels. On a 45 degree slope, you will move the x 5 pixels, then you will get pushed up to the top of the hill and move y 5 pixels. That means that a 45 degree hill produces double the speed of flat ground. 45 degrees is probably close the the steepest hill you want to allow, but steeper ones will have even worse speed differences.

And broumbroum, that approach won’t be very desirable. If he used only hitbox collision, then any polygonal or spheroid object will have completely the wrong collision. Instead, Noya, you should check out Java’s java.awt.geom.Area class. It works wonders for 2D side scrollers. You can create an Area using any Shape, then you can find precise intersection, get the slope of the intersection, add or remove pieces from the Area, and more.

I was just working on a project using this approach, but I was also trying to implement realistic Physics, and I kept coming up with collision issues, so I gave up and now I am using Phys2D. You could try that as well – it is tiny in terms of disk space and works well. It will handle every single collision and physics issue you have – all you will need to do is apply force in the correct places and from the right button presses. (if you do use this approach, let me know if you want to use my AnimatedBody subclass, which renders a sprite at the proper scale and rotation to match its bounds).