Walking Up Steps

Posted By: Valdsator

Walking Up Steps - 10/10/11 01:37

At the moment I'm trying to make an efficient and flexible movement system that I could use later on in a game. One part that's very important is the ability for the player to walk up steps/stairs. I thought about how I might do this, and came up with this:

Black = The level
Blue = The player
Red = c_trace
Basically, a c_trace acts as the feet of the player. It stops gravity from pulling him down when something is detected, and when something is detected, it checks the hit.z of the c_trace. If it's too close to the player, it moves the player up, making it so that he can walk up steps. The player's collision box stops him from moving if the step is too big. I got this working rather well, but then walking on slopes, while it worked, was very jittery and unnatural. I then tried it with 2 c_traces (one for walking on the ground, one for falling/jumping), which solved the slope problem, but now the player would walk up steps instantly rather than gradually moving up (things got weird otherwise), and overall it's probably very easy to break on complex terrain. Heck, I broke it simply by having a step that touches both the collision box, and the c_trace.

So my question is:
How does a system like this (climbing steps, walking on slopes) work on games like Quake? How might I do this with Lite-C (not exact code, but in general)? I'm simply stuck, and I want to solve this so I can use it for my games, rather than trying to work around it all the time.

Thank you!
Posted By: Redeemer

Re: Walking Up Steps - 10/10/11 03:38

Quake uses Axis Aligned Bounding Boxes (AABBs) to represent game objects in the collision engine. Basically, all objects are treated as cubes that do not rotate with the model, but instead stay oriented with the world axis.

At one point Gamestudio used this same system, but now it uses a combination of different systems depending upon what objects are being tested. When using the c_move() instruction to move an entity, ellipsoids are used to handle collisions between entities and world geometry, and OBBs (oriented bound boxes, which rotate with the model) are used when two entities collide with one another.

More info on this page:
http://www.conitec.net/beta/collision.htm

Needless to say the system is finicky and difficult to manage. Understand that unless you know exactly how to use this collision system to your advantage, you will end up with a sticky mess at the end of it. My advice: write your own robust collision system with the aid of the Gamestudio functions, or find someone willing to do it for you. But whatever you do, don't abuse the stock Gamestudio movement functions, or you will end up with something that is very difficult for you to control as a game designer.
Posted By: Valdsator

Re: Walking Up Steps - 10/10/11 04:04

Originally Posted By: Redeemer
Quake uses Axis Aligned Bounding Boxes (AABBs) to represent game objects in the collision engine. Basically, all objects are treated as cubes that do not rotate with the model, but instead stay oriented with the world axis.
Ah, this explains a lot.

Originally Posted By: Redeemer
My advice: write your own robust collision system with the aid of the Gamestudio functions...
If I were to do this, where would I start? How would I set it up so that a whole game can use it with flexibility?
Posted By: bart_the_13th

Re: Walking Up Steps - 10/10/11 05:57

I believe you can force c_move to use AABB collision.
As for the movement, I usually move the entity up before c_move and move it down afterward.
Something like this
Code:
my.z+=100;
c_move(something);
my.z-=100;

Posted By: painkiller

Re: Walking Up Steps - 10/10/11 09:26

After trying some movement systems, finally I ended using PhysX and PH_RIGID with PH_CAPSULE. You have nice collisions, and thanks to the capsule shape you can walk up steps. You don't even have to create your gravity system, just check when the player is on the ground and then being able to move using addvelcentral. If you want to check it out, my code is on AUM 101
Posted By: Valdsator

Re: Walking Up Steps - 10/10/11 12:25

Originally Posted By: painkiller
After trying some movement systems, finally I ended using PhysX and PH_RIGID with PH_CAPSULE. You have nice collisions, and thanks to the capsule shape you can walk up steps. You don't even have to create your gravity system, just check when the player is on the ground and then being able to move using addvelcentral. If you want to check it out, my code is on AUM 101
Wouldn't this require the player to have an NVIDIA card?
Posted By: painkiller

Re: Walking Up Steps - 10/10/11 12:46

Originally Posted By: Valdsator
Originally Posted By: painkiller
After trying some movement systems, finally I ended using PhysX and PH_RIGID with PH_CAPSULE. You have nice collisions, and thanks to the capsule shape you can walk up steps. You don't even have to create your gravity system, just check when the player is on the ground and then being able to move using addvelcentral. If you want to check it out, my code is on AUM 101
Wouldn't this require the player to have an NVIDIA card?


no, PhysX works on all video cards, I have an Ati card for example, the only advantage is that you will have hardware acceleration with an nvidia card
Posted By: Valdsator

Re: Walking Up Steps - 10/11/11 03:00

I think I actually want to write my own, simple collision detection system. But, while I understand the basic concept of it, like what the game should do to fix a collision, what I don't know about is how I would make the bounding boxes, and then check if they're intersecting with any other ones in Lite-C. Can anyone give me a few hints? tongue Thanks.
Posted By: Redeemer

Re: Walking Up Steps - 10/12/11 00:47

I think I might have what you need, but can you give me a bit more info of what you were thinking of? I wrote some collision code some time ago that would allow you to accurately perform 2D collision detection for entity vs. entity interactions and entity vs. square tile map interactions. It was written in Ansi C code so I would have to do a little tinkering to get it working in Gamestudio, but it works perfectly as long as you don't use it for anything other than those two things I mentioned above. tongue
Posted By: Valdsator

Re: Walking Up Steps - 10/12/11 02:24

Well, I want to create 3D AABB collision detection, which I guess means your collision detection wouldn't work, and I think it would be interesting to make my own (but thanks for the offer!). tongue

My plan:
Each entity would set it's bounding box (a rectangular prism) via a function I make, or just changing some skills, and then I would make a function for movement. The move function would use the bounding box to check if it's intersecting with another bounding box, or the level (not sure how I would do this, as c_intersect wouldn't work with the level, and c_trace only makes a line).
If it's intersecting, it would try fixing the problem, which could be done several ways (a simple solution would be moving to the previous position). I think I know how I would do gliding, but that's irrelevant at this point. I really just need help creating the bounding box. Is it possible for the engine to check if anything is inside a rectangular prism shaped area? I don't think c_scan would work.
Posted By: lostclimate

Re: Walking Up Steps - 10/12/11 02:59

you could make a bb struct and have a scheduler go through a list of bb dependant on its relativity to any possible collisions. i am far from an expert on physics or collision but thats where i would start if i were doing it.
Posted By: painkiller

Re: Walking Up Steps - 10/12/11 09:58

maybe you can adapt c_intersect function
Posted By: Redeemer

Re: Walking Up Steps - 10/12/11 13:26

Originally Posted By: Valdsator
Each entity would set it's bounding box (a rectangular prism) via a function I make, or just changing some skills, and then I would make a function for movement. The move function would use the bounding box to check if it's intersecting with another bounding box, or the level (not sure how I would do this, as c_intersect wouldn't work with the level, and c_trace only makes a line).
If it's intersecting, it would try fixing the problem, which could be done several ways (a simple solution would be moving to the previous position). I think I know how I would do gliding, but that's irrelevant at this point. I really just need help creating the bounding box. Is it possible for the engine to check if anything is inside a rectangular prism shaped area? I don't think c_scan would work.

That's a fine plan, but it's sort of like planning the construction of a robot when you have no idea how they work. "First, I make the robot's body. Then I program the robot and give it power."

Don't take that the wrong way, I'm just trying to put what you said into perspective for you. laugh To "make" a bounding box for an object, you have to define a new data structure with the information you'll need (or reuse an existing one, like an entity's min/max variables) and then setup some complicated logical and mathematical constructs that can be used to "trace" a volume across your movement distance. Said tracing involves checking the volume's path against the world's raw geometry data, which is simply a list of polygon definitions... and simply put, it's really really hard to check cube volumes against polygons.

Basically, this is a very complicated kind of programming and you're in for a massive headache if you try to begin learning it by writing your own 3D AABB movement system. And trust me when I say there's no easy way to do this right. My own 2D collision code was 350 lines of commented code - and while that may seem like only a little bit, for such a "simple" task of moving a box over a 2D landscape, it's quite a lot of mathematical/logical construction, and none of it's obvious!

Here's my code just so you can get a small idea of what you'd be up against (note that it's long, and (being experimental) a bit messy):
Click to reveal..
Code:
/*-------------------------------------------------------------------------------

	e_CheckCells

	Tests all four cells surrounding the position (tx, ty, tz) and returns
	a 1 if the position intersects with a cell.

-------------------------------------------------------------------------------*/

int e_CheckCells( double tx, double ty, int tz, entity_t* me )
{
	float sx, sy;
	float ffx, ffy;
	long fx, fy;
	long fh, ch;
	entity_t* entity;

	for( sy=-me->sizey; sy<=me->sizey; sy+=me->sizey )
	{
		for( sx=-me->sizex; sx<=me->sizex; sx+=me->sizex )
		{
			fx = floor(tx+sx); fy = floor(ty+sy); // int coordinates
			ffx = tx+sx; ffy = ty+sy; // float coordinates
			
			fh = map.floors[fx+fy*map.width] + (me->sizez*.5) - 1; // get the initial floor/ceiling heights
			ch = map.ceilings[fx+fy*map.width] - (me->sizez*.5) - 1;
			if( firstentity != NULL ) // check against entities
			{
				for( entity=firstentity; entity!=NULL; entity=entity->next )
				{
					if( !(entity->flags&FLAG_PASSABLE) && entity != me ) // if the entity is neither passable nor myself
					{
						if( ffx >= entity->x-entity->sizex && ffx <= entity->x+entity->sizex ) // if this horizontal position intersects with the entity
						{
							if( ffy >= entity->y-entity->sizey && ffy <= entity->y+entity->sizey ) // if this vertical position intersects with the entity
							{
								if( me->z+me->sizez > entity->z+entity->sizez && fh < entity->z+entity->sizez )
									fh=entity->z+entity->sizez; // adjust the floor height to include me!
								if( me->z-me->sizez < entity->z-entity->sizez && ch > entity->z-entity->sizez )
									ch=entity->z-entity->sizez; // adjust the ceiling height to include me!
								else if( me->z == entity->z )
									return(1); // you're level with the entity. stop that ship!
							}
						}
					}
				}
			}
			
			if( fh >= ch ) return(1); // the floor is in the ceiling
			if( (fh-tz) > STEPHEI ) return(1); // this floor is too high
			else if( fh+1 >= tz ) me->onground=1; // I fell to the floor
			if( (tz-ch) > STEPHEI ) return(1); // the ceiling is too low
			
			gfh = max(fh+1,gfh); // remember the highest position of the floor for this collision pass
			gch = min(ch+1,gch); // remember the lowest position of the ceiling for this collision pass
		}
	}
	return(0);
}

/*-------------------------------------------------------------------------------

	e_ClipVelocity

	Takes a velocity (vx, vy, vz) and clips it against the cells
	surrounding the position (*x, *y, *z)

-------------------------------------------------------------------------------*/

int e_ClipVelocity( double *x, double *y, int *z, double vx, double vy, double vz, entity_t* me )
{
	double tx, ty; int tz;
	long fx, fy;
	//long fh, ch;
	int exitcode = 1;

	if( *x+vx < .36 ) vx -= *x+vx-.36;
	if( *y+vy < .36 ) vy -= *y+vy-.36;
	if( *x+vx > map.width-.36 ) vx -= *x+vx-map.width+.36;
	if( *y+vy > map.height-.36 ) vy -= *y+vy-map.height+.36;
	
	fx=floor(*x); fy=floor(*y);
	gfh = map.floors[fx+fy*map.width] + (me->sizez*.5);
	gch = map.ceilings[fx+fy*map.width] - (me->sizez*.5);

	if(me->onground == 0) me->onground2 = 0;
	else me->onground = 0;
	tx=*x+vx;
	ty=*y+vy;
	tz=*z;
	if( !e_CheckCells(tx,ty,tz,me) )
	{
		*x=tx;
		*y=ty;
		exitcode=0;
	}
	else
	{
		tx=*x+vx;
		ty=*y;
		tz=*z;
		if( !e_CheckCells(tx,ty,tz,me) )
		{
			*x=tx;
			*y=ty;
		}
		else
		{
			tx=*x;
			ty=*y+vy;
			tz=*z;
			if( !e_CheckCells(tx,ty,tz,me) )
			{
				*x=tx;
				*y=ty;
			}
		}
	}

	tx=*x; ty=*y; tz=*z;
	/*fx=floor(tx); fy=floor(ty);

	fh = map.floors[fx+fy*map.width] + PLAYER_EYES;
	ch = map.ceilings[fx+fy*map.width] - (PLAYER_HEIGHT-PLAYER_EYES);*/

	*z=min(max((tz+vz),gfh-me->sizez),gch);
	if(*z <= gfh)
	{
		if( !me->onground2 ) // landing from a fall?
		{
			*z=gfh;
			me->onground2=1;
		}
		else if(*z < gfh) // climbing a step?
		{
			*z+=timesync*.3;
			if(*z>gfh) *z=gfh;
		}
	}

	return(exitcode);
}

/*-------------------------------------------------------------------------------

	e_MoveTrace

	Traces from *x1, *y1, *z1 to x2, y2, z2 performing collision detection along the
	way. If an impassable obstacle or the destination is reached, set the
	given pointers *x1, *y1, and *z1 to end position.

-------------------------------------------------------------------------------*/

void e_MoveTrace( double *x1, double *y1, int *z1, double x2, double y2, int z2, entity_t* me )
{
	double tracex, tracey, tracex2, tracey2;
	int tracez, tracez2;
	double dx, dy, dxabs, dyabs, x, y;
	int sdx, sdy, i;

	dx=x2-*x1;		// the horizontal distance of the line
	dy=y2-*y1;		// the vertical distance of the line
	dxabs=abs(dx);
	dyabs=abs(dy);
	sdx=sgn(dx);
	sdy=sgn(dy);
	x=dyabs*.5;
	y=dxabs*.5;
	tracex=*x1;
	tracey=*y1;
	tracez=*z1;
	tracex2=x2;
	tracey2=y2;
	tracez2=z2-tracez;

	if( sdx >= 0 && sdy >= 0 )
	{
		if( e_ClipVelocity(&tracex,&tracey,&tracez,min(1,tracex2-tracex),min(1,tracey2-tracey),tracez2,me) )
		{
			*x1 = tracex;
			*y1 = tracey;
			*z1 = tracez;
			return;
		}
	}
	else if( sdx < 0 && sdy >= 0 )
	{
		if( e_ClipVelocity(&tracex,&tracey,&tracez,min(1,tracex2-tracex),min(1,tracey2-tracey),tracez2,me) )
		{
			*x1 = tracex;
			*y1 = tracey;
			*z1 = tracez;
			return;
		}
	}
	else if( sdx >= 0 && sdy < 0 )
	{
		if( e_ClipVelocity(&tracex,&tracey,&tracez,min(1,tracex2-tracex),min(1,tracey2-tracey),tracez2,me) )
		{
			*x1 = tracex;
			*y1 = tracey;
			*z1 = tracez;
			return;
		}
	}
	else if( sdx < 0 && sdy < 0 )
	{
		if( e_ClipVelocity(&tracex,&tracey,&tracez,min(1,tracex2-tracex),min(1,tracey2-tracey),tracez2,me) )
		{
			*x1 = tracex;
			*y1 = tracey;
			*z1 = tracez;
			return;
		}
	}
	if( dxabs >= dyabs ) // the line is more horizontal than vertical
	{
		for( i=0; i<dxabs; i++ )
		{
			y+=dyabs;
			if( y >= dxabs )
			{
				y -= dxabs;
				tracey += sdy;
			}
			tracex += sdx;

			if( sdx >= 0 && sdy >= 0 )
			{
				if( e_ClipVelocity(&tracex,&tracey,&tracez,min(1,tracex2-tracex),min(1,tracey2-tracey),tracez2,me) )
				{
					*x1 = tracex;
					*y1 = tracey;
					*z1 = tracez;
					return;
				}
			}
			else if( sdx < 0 && sdy >= 0 )
			{
				if( e_ClipVelocity(&tracex,&tracey,&tracez,min(1,tracex2-tracex),min(1,tracey2-tracey),tracez2,me) )
				{
					*x1 = tracex;
					*y1 = tracey;
					*z1 = tracez;
					return;
				}
			}
			else if( sdx >= 0 && sdy < 0 )
			{
				if( e_ClipVelocity(&tracex,&tracey,&tracez,min(1,tracex2-tracex),min(1,tracey2-tracey),tracez2,me) )
				{
					*x1 = tracex;
					*y1 = tracey;
					*z1 = tracez;
					return;
				}
			}
			else if( sdx < 0 && sdy < 0 )
			{
				if( e_ClipVelocity(&tracex,&tracey,&tracez,min(1,tracex2-tracex),min(1,tracey2-tracey),tracez2,me) )
				{
					*x1 = tracex;
					*y1 = tracey;
					*z1 = tracez;
					return;
				}
			}
		}
	}
	else // the line is more vertical than horizontal
	{
		for( i=0; i<dyabs; i++ )
		{
			x += dxabs;
			if( x >= dyabs )
			{
				x -= dyabs;
				tracex += sdx;
			}
			tracey += sdy;

			if( sdx >= 0 && sdy >= 0 )
			{
				if( e_ClipVelocity(&tracex,&tracey,&tracez,min(1,tracex2-tracex),min(1,tracey2-tracey),tracez2,me) )
				{
					*x1 = tracex;
					*y1 = tracey;
					*z1 = tracez;
					return;
				}
			}
			else if( sdx < 0 && sdy >= 0 )
			{
				if( e_ClipVelocity(&tracex,&tracey,&tracez,min(1,tracex2-tracex),min(1,tracey2-tracey),tracez2,me) )
				{
					*x1 = tracex;
					*y1 = tracey;
					*z1 = tracez;
					return;
				}
			}
			else if( sdx >= 0 && sdy < 0 )
			{
				if( e_ClipVelocity(&tracex,&tracey,&tracez,min(1,tracex2-tracex),min(1,tracey2-tracey),tracez2,me) )
				{
					*x1 = tracex;
					*y1 = tracey;
					*z1 = tracez;
					return;
				}
			}
			else if( sdx < 0 && sdy < 0 )
			{
				if( e_ClipVelocity(&tracex,&tracey,&tracez,min(1,tracex2-tracex),min(1,tracey2-tracey),tracez2,me) )
				{
					*x1 = tracex;
					*y1 = tracey;
					*z1 = tracez;
					return;
				}
			}
		}
	}
	*x1 = tracex;
	*y1 = tracey;
	*z1 = tracez;
}

I execute this movement system by calling e_MoveTrace and passing an entity's information. e_MoveTrace in turn calls e_CheckVelocity multiple times while it traces a path through the level, which in turn calls e_CheckCells multiple times to check whether or not the volume has hit an obstacle so far.
(note that in my code I'm also moving z variables around... that's because technically this is collision code for a doom-like engine)
Posted By: Valdsator

Re: Walking Up Steps - 10/12/11 21:16

Originally Posted By: Redeemer
That's a fine plan, but it's sort of like planning the construction of a robot when you have no idea how they work. "First, I make the robot's body. Then I program the robot and give it power."
Haha, that's exactly how I feel.

Originally Posted By: Redeemer
Basically, this is a very complicated kind of programming and you're in for a massive headache if you try to begin learning it by writing your own 3D AABB movement system. And trust me when I say there's no easy way to do this right. My own 2D collision code was 350 lines of commented code - and while that may seem like only a little bit, for such a "simple" task of moving a box over a 2D landscape, it's quite a lot of mathematical/logical construction, and none of it's obvious!
Heh, I knew it wasn't quite as simple as I thought. Since I'm really interested in this, I'll search around the internet for more information, and do some experiments. Thanks for the code, I'll definitely have a look at that, and thanks for explaining the basics as well. laugh
Posted By: bart_the_13th

Re: Walking Up Steps - 10/13/11 04:13

Maybe you can check jiglib's collision for start. I guess the best way to check collision actually is during the vertex computing/processing, at least when you actually have access to the process.
Posted By: 3run

Re: Walking Up Steps - 10/13/11 12:16

Bart, where can I find those jiglib's collusions?
Posted By: Valdsator

Re: Walking Up Steps - 10/15/11 15:46

Alright, I've begun experimenting on some collision detection stuff, but obviously it's going to take a while to make anything that would be flexible and usable in a game. I guess I'll have to just deal with the 3DGS collision detection for now, but one thing that would really help is the ability for the bounding box to be... well an actual box. It's an ellipsoid when it's colliding against the level, and it would be great if it was just a rectangular prism. Surely there's a way to do this? :|
Posted By: 3run

Re: Walking Up Steps - 10/15/11 17:45

No mate, there is no way to change ellipsoid shape for collusions... But sure, there are some ways to workaround problems which you faced, but without changing bbox's shape. A lot of users on this community requested different shapes for bbox, but noone really cares...
Posted By: Superku

Re: Walking Up Steps - 10/15/11 18:31

I'm currently working on a simple AABB implementation (blocks/ entities):
http://www.opserver.de/ubb7/ubbthreads.php?ubb=showflat&Number=385150#Post385150
I will continue to work on it after I've written my last exam on the 21st and publish the source code (if I get it done).
Posted By: Valdsator

Re: Walking Up Steps - 10/15/11 21:37

Nice! Good luck with that. I don't like using other people's code, so I'd probably just look at it to see how it's done. tongue

Anyway, good news. I finally got the walking up steps thingy to work properly, while not screwing up the slopes. First I set move_min_z to 0.1, because the default 3dgs collision detection is going to take care of sliding down slopes. Next, I made a c_trace that goes from the bottom of the bounding box of the player, to a bit lower (5 unit) than his model's feet. Then it checks if there was a hit, and if the normal.z is more than 0.9.

It instantly sets the entity's z to hit.z + 60 (standing on the ground) if normal.z is less than 1. So if the player is walking on a slope, he will stick to the ground. Then it checks if my.z is lower than hit.z + 60 (the feet of the player is 60 units below the origin), and if normal.z = 1. If so, it increases z_move to 10 (a variable c_move uses). This allows for the player to walk up steps.

If the player is now perfectly standing on the ground, z_move is set to 0. Finally, if the c_trace does not hit, or if the player walks on to a slope too steep, gravity pulls the player down.

Code:
move_min_z = 0.1;

[irrelevant code]

c_trace(vector(my.x,my.y,my.z + my.min_z),vector(my.x,my.y,(my.z - 65)),IGNORE_ME|IGNORE_PASSABLE);
	if(trace_hit && normal.z > 0.9){
		if(normal.z < 1){my.z = hit.z + 60;} //if on slope
		if(my.z < hit.z + 60){ //if too low
			if(normal.z == 1){z_move = 10;} //and if on flat ground
		}else{ //if standing perfectly on ground
			z_move = 0;
		}
	}else{ //if not on ground
		z_move -= grav * time_step;
	}
c_move(me,nullvector,vector(0,0,z_move * time_step),GLIDE|IGNORE_PASSABLE);
Woot.
© 2024 lite-C Forums