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)

Last edited by Redeemer; 10/12/11 13:42.
Eats commas for breakfast.

Play Barony: Cursed Edition!