blockmap.cpp

quake 游戏原代码

#include "ray.h"
#include "globals.h"
#include "blockmap.h"
#include "error.h"

pdata N_PTR=NULL;

typedef struct BLOCK_MAP {           
  long x_base, y_base, x_range, y_range;
  short x_count, y_count;
  pline_list * blocks;
  pobject_node ** objects;
  } block_map;

typedef struct LINE_LINK * pline_link;
typedef struct LINE_LINK {
  plinedef data;
  pline_link next;
  } line_link;
  
BOOL block_map_loaded=FALSE;
block_map the_block_map;

plinedef Ll_Get_Data(pline_link node) {
  return node->data;
  }

pline_link Ll_Make_Link(plinedef line_pointed_to) {
  pline_link new_link;
  new_link=(pline_link)NewPtr(sizeof(line_link));
  new_link->data=line_pointed_to;
  new_link->next=NULL;
  return new_link;
  }

void Ll_Push_Link(pline_link & base_link, pline_link push_link) {
  if (push_link==NULL)
    return;
  push_link->next=base_link;
  base_link=push_link;
  }

void Ll_Make_And_Push_Link(pline_link & base_link, plinedef line_pointed_to) {
  pline_link the_link;
  the_link=Ll_Make_Link(line_pointed_to);
  Ll_Push_Link(base_link, the_link);
  }

pline_link Ll_Get_Next_Link(pline_link cur_link) {
  if (cur_link==NULL)
    return NULL;
  return cur_link->next;
  }

BOOL Ll_Empty_Link(pline_link the_link) {
  return ((the_link == NULL) ? TRUE : FALSE); 
}

void Ll_Make_Empty(pline_link & the_link) {
  the_link=NULL;
}

void Ll_Clear_Links(pline_link & base_link)
{
pline_link cur_link, next_link;
cur_link=base_link;
while (!Ll_Empty_Link(cur_link)) {
  next_link=Ll_Get_Next_Link(cur_link);
  DelPtr(cur_link);
  cur_link=next_link;
  }
Ll_Make_Empty(base_link);
}

void Ll_Push_In_Array(pline_link ** & the_array, short x_pos, short y_pos,
   plinedef data) {

if ((x_pos>=0) && (x_pos<the_block_map.x_count) &&
    (y_pos>=0) && (y_pos<the_block_map.y_count)) {
      Ll_Make_And_Push_Link((the_array[x_pos])[y_pos],
        data);
      }

}

line_list * Get_Block_Line_List(USHORT block_x, USHORT block_y) {
if (!block_map_loaded)
  return NULL;
  
// range check
if ((block_x>=0) && (block_x<the_block_map.x_count) &&
    (block_y>=0) && (block_y<the_block_map.y_count) ) {
  line_list * base_list=the_block_map.blocks[block_x];
  return base_list+block_y;
  } else {
  return NULL;
  }
}

pobject_node * Get_Block_Obj_List(USHORT block_x, USHORT block_y) {
if (!block_map_loaded)
  return NULL;
  
// range check
if ((block_x>=0) && (block_x<the_block_map.x_count) &&
    (block_y>=0) && (block_y<the_block_map.y_count) ) {
  pobject_node * base_list=the_block_map.objects[block_x];
  return base_list+block_y;
  } else {
  return (pobject_node *)&N_PTR;
  }
}

line_list * Get_Line_List(long x, long y) {
if (!block_map_loaded)
  return NULL;
long block_x, block_y;
block_x=x-the_block_map.x_base;
block_y=y-the_block_map.y_base;
block_x>>=BLOCK_MAP_X_SHIFT;
block_y>>=BLOCK_MAP_Y_SHIFT;

// range check
if ((block_x>=0) && (block_x<the_block_map.x_count) &&
    (block_y>=0) && (block_y<the_block_map.y_count) ) {
  line_list * base_list=the_block_map.blocks[block_x];
  return base_list+block_y;
  } else {
  return NULL;
  }
}

void Generate_Block_Map() {
   block_map_loaded = TRUE;

   long min_x, min_y, max_x, max_y, range_x, range_y;
   pvector2 cur_vec;
   short counter;

   // Get min and max points of world be looping through vectors

   min_x=max_x=Vector_List[0].x;
   min_y=max_y=Vector_List[0].y;

   for (counter=1; counter < Number_Of_Vectors; counter++) {
      cur_vec=Vector_List+counter;
      if (cur_vec->x < min_x)
         min_x=cur_vec->x;
      if (cur_vec->y < min_y)
         min_y=cur_vec->y;
      if (cur_vec->x > max_x)
         max_x=cur_vec->x;
      if (cur_vec->y > max_y)
         max_y=cur_vec->y;
   }

   // Get block range

   range_x=max_x-min_x;
   range_y=max_y-min_y;

   // Save info on block table

   the_block_map.x_base=min_x;
   the_block_map.y_base=min_y;

   the_block_map.x_range=range_x;
   the_block_map.y_range=range_y;

   the_block_map.x_count=(range_x+(BLOCK_MAP_X_SIZE-1)) >> BLOCK_MAP_X_SHIFT;
   the_block_map.y_count=(range_y+(BLOCK_MAP_Y_SIZE-1)) >> BLOCK_MAP_Y_SHIFT;

   pline_link ** block_temps;
   pline_link * cur_block_line;
   short cur_x, cur_y;

   block_temps=(pline_link **)NewPtr(the_block_map.x_count * sizeof(pline_link *));

   for (cur_x=0; cur_x<the_block_map.x_count; cur_x++) {
      block_temps[cur_x]=(pline_link *)NewPtr(the_block_map.y_count *
        sizeof(pline_link));
      cur_block_line=block_temps[cur_x];
      for (cur_y=0; cur_y<the_block_map.y_count; cur_y++) {
        Ll_Make_Empty(cur_block_line[cur_y]);
      }
   }

   plinedef cur_line;
   long x1, y1, x2, y2, x_diff, y_diff, error_term, 
        x_unit, y_unit, cur_abs_x, cur_abs_y;
   short new_x, new_y;

   for (USHORT l_index=0; l_index<Number_Of_Linedefs; l_index++) {
      cur_line=Ld_List+l_index;

      // Get block map positions of start and end

      x1=(Vector_List[cur_line->v[0]].x-the_block_map.x_base);
      y1=(Vector_List[cur_line->v[0]].y-the_block_map.y_base);
      x2=(Vector_List[cur_line->v[1]].x-the_block_map.x_base);
      y2=(Vector_List[cur_line->v[1]].y-the_block_map.y_base);
      
      // setup line for bresnham's algorithym      
      
      cur_abs_x=x1;
      cur_abs_y=y1;
      cur_x=cur_abs_x>>BLOCK_MAP_X_SHIFT;
      cur_y=cur_abs_y>>BLOCK_MAP_Y_SHIFT;
      Ll_Push_In_Array(block_temps, cur_x, cur_y, cur_line);
      error_term=0;
      
      x_diff=x2-x1;
      if (x_diff<0) {
        x_diff=-x_diff;
        x_unit=-1;
      } else x_unit=1;

      y_diff=y2-y1;
      if (y_diff<0) {
        y_diff=-y_diff;
        y_unit=-1;
      } else y_unit=1;

      if (x_diff>y_diff) {

        for (short position=0; position<=x_diff; position++) {
          new_x=cur_abs_x>>BLOCK_MAP_X_SHIFT;
          new_y=cur_abs_y>>BLOCK_MAP_Y_SHIFT;
          if ((new_x!=cur_x)||(new_y!=cur_y)) {
             cur_x=new_x;
             cur_y=new_y;
             Ll_Push_In_Array(block_temps, cur_x, cur_y, cur_line);
             }
          cur_abs_x+=x_unit;
          error_term+=y_diff;
          if (error_term>=x_diff) {
            error_term-=x_diff;
            cur_abs_y+=y_unit;
            }  
          }

      } else {

        for (short position=0; position<=y_diff; position++) {
          new_x=cur_abs_x>>BLOCK_MAP_X_SHIFT;
          new_y=cur_abs_y>>BLOCK_MAP_Y_SHIFT;
          if ((new_x!=cur_x)||(new_y!=cur_y)) {
             cur_x=new_x;
             cur_y=new_y;
             Ll_Push_In_Array(block_temps, cur_x, cur_y, cur_line);
             }
          cur_abs_y+=y_unit;
          error_term+=x_diff;
          if (error_term>=y_diff) {
            error_term-=y_diff;
            cur_abs_x+=x_unit;
            } /* end if */
          } /* end for */
      } /* end if (x_diff>y_diff) */
   } /* end loop through lines */
      
pline_list cur_list_column;
pline_list cur_line_list;
pline_link cur_link;
short line_count;

the_block_map.blocks=(pline_list *)NewPtr(the_block_map.x_count*sizeof(pline_list));
for (cur_x=0; cur_x<the_block_map.x_count; cur_x++) {
  the_block_map.blocks[cur_x]=(pline_list)NewPtr(the_block_map.y_count*sizeof(line_list));
  cur_list_column=the_block_map.blocks[cur_x];
  cur_block_line=block_temps[cur_x];
  for (cur_y=0; cur_y<the_block_map.y_count; cur_y++) {
    cur_link=cur_block_line[cur_y];
    line_count=0;
    while (!Ll_Empty_Link(cur_link)) {
      cur_link=Ll_Get_Next_Link(cur_link);
      line_count++;
      }
    cur_line_list=cur_list_column+cur_y;
    cur_line_list->line_count=line_count;
    if (line_count > 0) {
      cur_line_list->lines=(plinedef *)NewPtr(line_count * sizeof(plinedef));
      cur_link=cur_block_line[cur_y];
      short cur_line=0;
      while (!Ll_Empty_Link(cur_link)) {
        cur_line_list->lines[cur_line]=Ll_Get_Data(cur_link);
        cur_link=Ll_Get_Next_Link(cur_link);
        cur_line++;
        }
    } else {
      cur_line_list->lines=NULL;
    }
    cur_link=cur_block_line[cur_y];
    Ll_Clear_Links(cur_link);
  }
  DelPtr(cur_block_line);
}
DelPtr(block_temps);

pobject_node * cur_object_list;
the_block_map.objects=(pobject_node **)NewPtr(the_block_map.x_count * sizeof(pobject_node *));
for (cur_x=0; cur_x<the_block_map.x_count; cur_x++) {
   the_block_map.objects[cur_x]=(pobject_node *)NewPtr(the_block_map.y_count * sizeof(pobject_node));
   cur_object_list=the_block_map.objects[cur_x];
   for (cur_y=0; cur_y<the_block_map.y_count; cur_y++) {
      cur_object_list[cur_y]=NULL;
   }
}

}

void Clear_Block_Map() {
if (!block_map_loaded)
  return;
short cur_x, cur_y;
pline_list cur_list_column;
for (cur_x=0; cur_x<the_block_map.x_count; cur_x++) {
  cur_list_column=the_block_map.blocks[cur_x]; 
  for (cur_y=0; cur_y<the_block_map.y_count; cur_y++) {
    if (cur_list_column[cur_y].lines!=NULL)
      DelPtr(cur_list_column[cur_y].lines);
    }
  if (the_block_map.objects[cur_x]!=NULL)
    DelPtr(the_block_map.objects[cur_x]);
  DelPtr(cur_list_column);
  }
DelPtr(the_block_map.objects);
DelPtr(the_block_map.blocks);
}

short Block_X(long real_x) {
   if (block_map_loaded)
      return ((real_x-(the_block_map.x_base<<SHIFT))>>(SHIFT+BLOCK_MAP_X_SHIFT));
   Error("Invalid call to Block_X");
   return 0;
}

short Block_Y(long real_y) {
   if (block_map_loaded)
      return ((real_y-(the_block_map.y_base<<SHIFT))>>(SHIFT+BLOCK_MAP_Y_SHIFT));
   Error("Invalid call to Block_Y");
   return 0;
}

long Block_Left_Line(long base_x) {
   if (block_map_loaded) 
      return (((((base_x-(the_block_map.x_base<<SHIFT))>>SHIFT)&BLOCK_MAP_X_AND)
         +the_block_map.x_base)<<SHIFT);
   Error("Invalid call to Block_Left_Line");
   return 0;
}

long Block_Right_Line(long base_x) {
   if (block_map_loaded) 
      return (((((base_x-(the_block_map.x_base<<SHIFT))>>SHIFT)&BLOCK_MAP_X_AND)+the_block_map.x_base+
         BLOCK_MAP_X_SIZE)<<SHIFT);
   Error("Invalid call to Block_Right_Line");
   return 0;
}

long Block_Bottom_Line(long base_y) {
   if (block_map_loaded) 
      return (((((base_y-(the_block_map.y_base<<SHIFT))>>SHIFT)&BLOCK_MAP_Y_AND)+
        the_block_map.y_base)<<SHIFT);
   Error("Invalid call to Block_Bottom_Line");
   return 0;
}

long Block_Top_Line(long base_y) {
   if (block_map_loaded) 
      return (((((base_y-(the_block_map.y_base<<SHIFT))>>SHIFT)&BLOCK_MAP_Y_AND)+the_block_map.y_base+
         BLOCK_MAP_Y_SIZE)<<SHIFT);
   Error("Invalid call to Block_Top_Line");
   return 0;
}

BOOL In_Block_X(long real_x, short block_x) {
   if (block_map_loaded)
      return ( (Block_X(real_x)==block_x) ? TRUE : FALSE);
   Error("Invalid call to In_Block_X");
   return FALSE;
}

BOOL In_Block_Y(long real_y, short block_y) {
   if (block_map_loaded)
      return ( (Block_Y(real_y)==block_y) ? TRUE : FALSE);
   Error("Invalid call to In_Block_Y");
   return FALSE;
}