collisio.cpp

quake 游戏原代码

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include "sign.h"
#include "ray.h"
#include "fixed.h"
#include "globals.h"
#include "collisio.h"
#include "isect.h"
#include "blockmap.h"
#include "message.h"
#include "abs.h"
#include "ground.h"

#define COLLINEAR         2
#define FIXED_TO_FLOAT(x) (((float)(x))/ONE)
#define FLOAT_TO_FIXED(x) (long)((float)(x)*ONE)
#define FIXED_ONE_QUARTER (16)
#define MAN_SIZE          (64)
#define WALL_PASSABLE 8
static plinedef s_wall = NULL;

#define VECTOR_LEN  15

/*
-- ----------------------------------------------------------------------
-  Function    : LineDistance
-
-  Parameters  :
-
-  Result      :
-
-  Description :
-    Returns the distance between point c, and the line a-b.
-- ----------------------------------------------------------------------
*/
MYFIXED
LineDistance( MYFIXED cx, MYFIXED cy, long ax, long ay, long bx, long by, long line_len )
{
  long delta_x = ax-bx;
  long delta_y = ay-by;
  MYFIXED s;

  /* If s becomes negative we are facing the line clockwise */
  fixedmult64(cy-(by<<SHIFT), delta_x);
  fixedma64((bx<<SHIFT)-cx, delta_y);
  s=fixeddiv64(line_len);


/*
  printf( "R = %f S = %f\n", r, s );
*/

  return s;
}

BOOL
On_Line( MYFIXED cx, MYFIXED cy, long ax, long ay, long bx, long by )
{
  long delta_x = ax-bx;
  long delta_y = ay-by;
  long line_len;
  MYFIXED r;

  /* the lenght of the line in **2 */
  line_len = delta_x*delta_x+delta_y*delta_y;

  fixedmult64((ay<<SHIFT)-cy, delta_y);
  fixedma64((ax<<SHIFT)-cx, delta_x);
  r=fixeddiv64(line_len);

  if ( r < 0 || r > ONE)
	  return FALSE;
  else return TRUE;
}

void
get_vector_xy( MYFIXED *vx, MYFIXED *vy, plinedef wall )
{
  long dx, dy, line_len;

  dx = Vector_List[wall->v[0]].x - Vector_List[wall->v[1]].x;
  dy = Vector_List[wall->v[0]].y - Vector_List[wall->v[1]].y;
		 
  line_len = wall->distance;

  *vx = fixeddiv(dx,line_len);
  *vy = fixeddiv(dy,line_len);

/*
  printf( "line_len %f, dx %f, dy %f\n", 
	 line_len, dx, dy );
*/
}

/*
  Check how it should behave when you sliding agains a wall. 
*/

void
slide_wall( MYFIXED *x, MYFIXED *y, MYFIXED x2, MYFIXED y2,
		  MYFIXED dist_old, MYFIXED dist_new )
{

  MYFIXED vector_x, vector_y;
 

  // get percent moves in x & y per move in unit of distance along line
  get_vector_xy( &vector_x, &vector_y, s_wall );

  // move along perpendicular to line, which to the best of my knowledge _always_ works
  // for sliding

		*x  = x2+fixedmult(dist_old-dist_new,-vector_y);
		*y  = y2+fixedmult(dist_old-dist_new, vector_x);
  
}

void Find_Closest_Line_In_List(MYFIXED x1, MYFIXED y1, plinedef * close_line,
	MYFIXED * cur_min, pline_list search_list) {
if (search_list==NULL)
	return;

plinedef wall;
MYFIXED tmp;
int i; 

for (i = 0; i < search_list->line_count; i++) {
	 wall=search_list->lines[i];
	 /* Check Distance */
	 if (On_Line(x1, y1,
		 (Vector_List[wall->v[0]].x ),
		 (Vector_List[wall->v[0]].y ),
		 (Vector_List[wall->v[1]].x ),
		 (Vector_List[wall->v[1]].y)) ) {
	 tmp = LineDistance( x1, y1, 
		 (Vector_List[wall->v[0]].x ),
		 (Vector_List[wall->v[0]].y ),
		 (Vector_List[wall->v[1]].x ),
		 (Vector_List[wall->v[1]].y),
					  wall->distance);
	 } else {
		 tmp=MAXMYFIXED;
	 }
	 if ( ABS(tmp) < ABS( *(cur_min) ) )
		{
	*(cur_min)      = tmp;
	*(close_line) = wall; 
		}

  }
}

void
checkwalls(pwall_collision_info the_collision)
{
	MYFIXED  side   = 0,
						x   = 0,
						y   = 0;

  plinedef mem_wall;
  MYFIXED  x1, y1, dest, min = MAXMYFIXED;

  // we never want an object with 2*speed of a wall, or it may get through
  long cur_speed=(the_collision->move_obj->type->stats.base_speed*2)<<SHIFT;
  MYFIXED dest_x, dest_y;
  USHORT block_x, block_y;

  x = the_collision->move_obj->x;
  y = the_collision->move_obj->y;
  x1 = x+the_collision->delta_vec->x;
  y1 = y+the_collision->delta_vec->y;

  if ( x1 == x && y1 == y ) {
	 the_collision->found_collision=FALSE;
	 return;
  }

  mem_wall=NULL;
  
  dest_x=x1;
  dest_y=y1;
  block_x=Block_X(dest_x);
  block_y=Block_Y(dest_y);
  
  Find_Closest_Line_In_List(x1, y1, &mem_wall, &min, 
	  Get_Block_Line_List(block_x, block_y));

  // check surrounding blocks
  if (dest_y-Block_Bottom_Line(dest_y)<(cur_speed)) {
	 Find_Closest_Line_In_List(x1,y1,&mem_wall, &min,
		 Get_Block_Line_List(block_x, block_y-1));
	 if (dest_x-Block_Left_Line(dest_x)<(cur_speed)) {
		 Find_Closest_Line_In_List(x1,y1,&mem_wall, &min,
			 Get_Block_Line_List(block_x-1, block_y-1));
	 }
	 if (dest_x-Block_Right_Line(dest_x)>(-cur_speed)) {
		 Find_Closest_Line_In_List(x1,y1,&mem_wall, &min,
			 Get_Block_Line_List(block_x+1, block_y-1));
	 }
  } else if (dest_y-Block_Top_Line(dest_y)>(-cur_speed)) {
	 Find_Closest_Line_In_List(x1,y1,&mem_wall, &min,
		 Get_Block_Line_List(block_x, block_y+1));
	 if (dest_x-Block_Left_Line(dest_x)<(cur_speed)) {
		 Find_Closest_Line_In_List(x1,y1,&mem_wall, &min,
			 Get_Block_Line_List(block_x-1, block_y+1));
	 }
	 if (dest_x-Block_Right_Line(dest_x)>(-cur_speed)) {
		 Find_Closest_Line_In_List(x1,y1,&mem_wall, &min,
			 Get_Block_Line_List(block_x+1, block_y+1));
	 }
  } else if (dest_x-Block_Left_Line(dest_x)<(cur_speed)) {
	  Find_Closest_Line_In_List(x1,y1,&mem_wall, &min,
		  Get_Block_Line_List(block_x-1, block_y));
  } else if (dest_x-Block_Right_Line(dest_x)>(-cur_speed)) {
	  Find_Closest_Line_In_List(x1,y1,&mem_wall, &min,
		  Get_Block_Line_List(block_x+1, block_y));
  }

the_collision->wall=mem_wall;
the_collision->dis_from_line=min;
if ( (mem_wall!=NULL) && (ABS( min ) < cur_speed) ) {
	the_collision->found_collision=TRUE;
} else {
	the_collision->found_collision=FALSE;
}

}

BOOL Intersect_Abs(pvector2 sv1, pvector2 dv1, pvector2 sv2, pvector2 dv2) {
	long sv1d, dv1d, sv2d, dv2d;

	sv1d=(sv2->x-dv2->x)*(sv1->y-dv2->y)-(sv2->y-dv2->y)*(sv1->x-dv2->x);
	dv1d=(sv2->x-dv2->x)*(dv1->y-dv2->y)-(sv2->y-dv2->y)*(dv1->x-dv2->x);
	sv1d=(sv1->x-dv1->x)*(sv2->y-dv1->y)-(sv1->y-dv1->y)*(sv2->x-dv1->x);
	sv1d=(sv1->x-dv1->x)*(dv2->y-dv1->y)-(sv1->y-dv1->y)*(dv2->x-dv1->x);

	if ( (SIGN(sv1d)!=SIGN(dv1d)) && (SIGN(sv2d)!=SIGN(dv2d)) ) {
		return TRUE;
	} else {
		return FALSE;
	}
}

BOOL Passable_Wall(plinedef wall, pobject the_obj, MYFIXED dest_x,
	MYFIXED dest_y, psector sec2) {

if (!(wall->attributes & WALL_PASSABLE)) 
	return FALSE; 
if (the_obj->z+the_obj->type->height>(sec2->ceil_height-
	Ground_Height_XY(dest_x, dest_y, sec2))) 
	return FALSE;
if (Ground_Height(the_obj)+the_obj->type->stepping_height+the_obj->z < 
	Ground_Height_XY(dest_x, dest_y, sec2))
	return FALSE;

return TRUE;
}

ULONG Do_Slide_Wall(pobject the_obj, pwall_collision_info the_collision) {
  psector sec1, sec2;
  plinedef wall;
  MYFIXED min, side, cur_speed, dest;
  MYFIXED source_x, source_y, dest_x, dest_y;

  source_x=the_obj->x;
  source_y=the_obj->y;
  dest_x=source_x+the_collision->delta_vec->x;
  dest_y=source_y+the_collision->delta_vec->y;
  wall=the_collision->wall;
  min=the_collision->dis_from_line;
  cur_speed=(the_obj->type->stats.base_speed*2) <<SHIFT;

  /* is there any point in checking further. */
  side=LineDistance(source_x,source_y,       
		 (Vector_List[wall->v[0]].x ),
		 (Vector_List[wall->v[0]].y ),
		 (Vector_List[wall->v[1]].x ),
		 (Vector_List[wall->v[1]].y),
						wall->distance);

  if (side<0) {
	  sec1=wall->s[1]->sec;
	  sec2=wall->s[0]->sec;
  } else {
	  sec1=wall->s[0]->sec;
	  sec2=wall->s[1]->sec;
  }

ULONG message_res;
BOOL impassible;

/* can we pass the wall */
if (Passable_Wall(wall, the_obj, dest_x, dest_y, sec2))
{
	dest=-SIGN(side)*cur_speed;
	impassible=FALSE;
} else {
	dest=SIGN(side)*cur_speed;
	impassible=TRUE;
}

message_res=Send_Specific_Message(NULL, the_obj, 
	WALL_SLIDE_CONFIRM, (pdata)&impassible); 

if (message_res==STOP_SLIDE) {
	return NORMAL_MESSAGE;
}
if (message_res!=NORMAL_MESSAGE) {
	return message_res;
}

s_wall = wall;
slide_wall( &source_x, &source_y, dest_x, dest_y, dest, min );
the_collision->delta_vec->x   =  source_x-the_obj->x ;
the_collision->delta_vec->y   = source_y-the_obj->y ;

return NORMAL_MESSAGE;
}