home *** CD-ROM | disk | FTP | other *** search
/ io Programmo 23 / IOPROG_23.ISO / SOFT / RAYCAST.ZIP / BLOCKMAP.CPP < prev    next >
Encoding:
C/C++ Source or Header  |  1995-10-25  |  10.9 KB  |  391 lines
  1. #include "ray.h"
  2. #include "globals.h"
  3. #include "blockmap.h"
  4. #include "error.h"
  5.  
  6. pdata N_PTR=NULL;
  7.  
  8. typedef struct BLOCK_MAP {           
  9.   long x_base, y_base, x_range, y_range;
  10.   short x_count, y_count;
  11.   pline_list * blocks;
  12.   pobject_node ** objects;
  13.   } block_map;
  14.  
  15. typedef struct LINE_LINK * pline_link;
  16. typedef struct LINE_LINK {
  17.   plinedef data;
  18.   pline_link next;
  19.   } line_link;
  20.   
  21. BOOL block_map_loaded=FALSE;
  22. block_map the_block_map;
  23.  
  24. plinedef Ll_Get_Data(pline_link node) {
  25.   return node->data;
  26.   }
  27.  
  28. pline_link Ll_Make_Link(plinedef line_pointed_to) {
  29.   pline_link new_link;
  30.   new_link=(pline_link)NewPtr(sizeof(line_link));
  31.   new_link->data=line_pointed_to;
  32.   new_link->next=NULL;
  33.   return new_link;
  34.   }
  35.  
  36. void Ll_Push_Link(pline_link & base_link, pline_link push_link) {
  37.   if (push_link==NULL)
  38.     return;
  39.   push_link->next=base_link;
  40.   base_link=push_link;
  41.   }
  42.  
  43. void Ll_Make_And_Push_Link(pline_link & base_link, plinedef line_pointed_to) {
  44.   pline_link the_link;
  45.   the_link=Ll_Make_Link(line_pointed_to);
  46.   Ll_Push_Link(base_link, the_link);
  47.   }
  48.  
  49. pline_link Ll_Get_Next_Link(pline_link cur_link) {
  50.   if (cur_link==NULL)
  51.     return NULL;
  52.   return cur_link->next;
  53.   }
  54.  
  55. BOOL Ll_Empty_Link(pline_link the_link) {
  56.   return ((the_link == NULL) ? TRUE : FALSE); 
  57. }
  58.  
  59. void Ll_Make_Empty(pline_link & the_link) {
  60.   the_link=NULL;
  61. }
  62.  
  63. void Ll_Clear_Links(pline_link & base_link)
  64. {
  65. pline_link cur_link, next_link;
  66. cur_link=base_link;
  67. while (!Ll_Empty_Link(cur_link)) {
  68.   next_link=Ll_Get_Next_Link(cur_link);
  69.   DelPtr(cur_link);
  70.   cur_link=next_link;
  71.   }
  72. Ll_Make_Empty(base_link);
  73. }
  74.  
  75. void Ll_Push_In_Array(pline_link ** & the_array, short x_pos, short y_pos,
  76.    plinedef data) {
  77.  
  78. if ((x_pos>=0) && (x_pos<the_block_map.x_count) &&
  79.     (y_pos>=0) && (y_pos<the_block_map.y_count)) {
  80.       Ll_Make_And_Push_Link((the_array[x_pos])[y_pos],
  81.         data);
  82.       }
  83.  
  84. }
  85.  
  86. line_list * Get_Block_Line_List(USHORT block_x, USHORT block_y) {
  87. if (!block_map_loaded)
  88.   return NULL;
  89.   
  90. // range check
  91. if ((block_x>=0) && (block_x<the_block_map.x_count) &&
  92.     (block_y>=0) && (block_y<the_block_map.y_count) ) {
  93.   line_list * base_list=the_block_map.blocks[block_x];
  94.   return base_list+block_y;
  95.   } else {
  96.   return NULL;
  97.   }
  98. }
  99.  
  100. pobject_node * Get_Block_Obj_List(USHORT block_x, USHORT block_y) {
  101. if (!block_map_loaded)
  102.   return NULL;
  103.   
  104. // range check
  105. if ((block_x>=0) && (block_x<the_block_map.x_count) &&
  106.     (block_y>=0) && (block_y<the_block_map.y_count) ) {
  107.   pobject_node * base_list=the_block_map.objects[block_x];
  108.   return base_list+block_y;
  109.   } else {
  110.   return (pobject_node *)&N_PTR;
  111.   }
  112. }
  113.  
  114. line_list * Get_Line_List(long x, long y) {
  115. if (!block_map_loaded)
  116.   return NULL;
  117. long block_x, block_y;
  118. block_x=x-the_block_map.x_base;
  119. block_y=y-the_block_map.y_base;
  120. block_x>>=BLOCK_MAP_X_SHIFT;
  121. block_y>>=BLOCK_MAP_Y_SHIFT;
  122.  
  123. // range check
  124. if ((block_x>=0) && (block_x<the_block_map.x_count) &&
  125.     (block_y>=0) && (block_y<the_block_map.y_count) ) {
  126.   line_list * base_list=the_block_map.blocks[block_x];
  127.   return base_list+block_y;
  128.   } else {
  129.   return NULL;
  130.   }
  131. }
  132.  
  133. void Generate_Block_Map() {
  134.    block_map_loaded = TRUE;
  135.  
  136.    long min_x, min_y, max_x, max_y, range_x, range_y;
  137.    pvector2 cur_vec;
  138.    short counter;
  139.  
  140.    // Get min and max points of world be looping through vectors
  141.  
  142.    min_x=max_x=Vector_List[0].x;
  143.    min_y=max_y=Vector_List[0].y;
  144.  
  145.    for (counter=1; counter < Number_Of_Vectors; counter++) {
  146.       cur_vec=Vector_List+counter;
  147.       if (cur_vec->x < min_x)
  148.          min_x=cur_vec->x;
  149.       if (cur_vec->y < min_y)
  150.          min_y=cur_vec->y;
  151.       if (cur_vec->x > max_x)
  152.          max_x=cur_vec->x;
  153.       if (cur_vec->y > max_y)
  154.          max_y=cur_vec->y;
  155.    }
  156.  
  157.    // Get block range
  158.  
  159.    range_x=max_x-min_x;
  160.    range_y=max_y-min_y;
  161.  
  162.    // Save info on block table
  163.  
  164.    the_block_map.x_base=min_x;
  165.    the_block_map.y_base=min_y;
  166.  
  167.    the_block_map.x_range=range_x;
  168.    the_block_map.y_range=range_y;
  169.  
  170.    the_block_map.x_count=(range_x+(BLOCK_MAP_X_SIZE-1)) >> BLOCK_MAP_X_SHIFT;
  171.    the_block_map.y_count=(range_y+(BLOCK_MAP_Y_SIZE-1)) >> BLOCK_MAP_Y_SHIFT;
  172.  
  173.    pline_link ** block_temps;
  174.    pline_link * cur_block_line;
  175.    short cur_x, cur_y;
  176.  
  177.    block_temps=(pline_link **)NewPtr(the_block_map.x_count * sizeof(pline_link *));
  178.  
  179.    for (cur_x=0; cur_x<the_block_map.x_count; cur_x++) {
  180.       block_temps[cur_x]=(pline_link *)NewPtr(the_block_map.y_count *
  181.         sizeof(pline_link));
  182.       cur_block_line=block_temps[cur_x];
  183.       for (cur_y=0; cur_y<the_block_map.y_count; cur_y++) {
  184.         Ll_Make_Empty(cur_block_line[cur_y]);
  185.       }
  186.    }
  187.  
  188.    plinedef cur_line;
  189.    long x1, y1, x2, y2, x_diff, y_diff, error_term, 
  190.         x_unit, y_unit, cur_abs_x, cur_abs_y;
  191.    short new_x, new_y;
  192.  
  193.    for (USHORT l_index=0; l_index<Number_Of_Linedefs; l_index++) {
  194.       cur_line=Ld_List+l_index;
  195.  
  196.       // Get block map positions of start and end
  197.  
  198.       x1=(Vector_List[cur_line->v[0]].x-the_block_map.x_base);
  199.       y1=(Vector_List[cur_line->v[0]].y-the_block_map.y_base);
  200.       x2=(Vector_List[cur_line->v[1]].x-the_block_map.x_base);
  201.       y2=(Vector_List[cur_line->v[1]].y-the_block_map.y_base);
  202.       
  203.       // setup line for bresnham's algorithym      
  204.       
  205.       cur_abs_x=x1;
  206.       cur_abs_y=y1;
  207.       cur_x=cur_abs_x>>BLOCK_MAP_X_SHIFT;
  208.       cur_y=cur_abs_y>>BLOCK_MAP_Y_SHIFT;
  209.       Ll_Push_In_Array(block_temps, cur_x, cur_y, cur_line);
  210.       error_term=0;
  211.       
  212.       x_diff=x2-x1;
  213.       if (x_diff<0) {
  214.         x_diff=-x_diff;
  215.         x_unit=-1;
  216.       } else x_unit=1;
  217.  
  218.       y_diff=y2-y1;
  219.       if (y_diff<0) {
  220.         y_diff=-y_diff;
  221.         y_unit=-1;
  222.       } else y_unit=1;
  223.  
  224.       if (x_diff>y_diff) {
  225.  
  226.         for (short position=0; position<=x_diff; position++) {
  227.           new_x=cur_abs_x>>BLOCK_MAP_X_SHIFT;
  228.           new_y=cur_abs_y>>BLOCK_MAP_Y_SHIFT;
  229.           if ((new_x!=cur_x)||(new_y!=cur_y)) {
  230.              cur_x=new_x;
  231.              cur_y=new_y;
  232.              Ll_Push_In_Array(block_temps, cur_x, cur_y, cur_line);
  233.              }
  234.           cur_abs_x+=x_unit;
  235.           error_term+=y_diff;
  236.           if (error_term>=x_diff) {
  237.             error_term-=x_diff;
  238.             cur_abs_y+=y_unit;
  239.             }  
  240.           }
  241.  
  242.       } else {
  243.  
  244.         for (short position=0; position<=y_diff; position++) {
  245.           new_x=cur_abs_x>>BLOCK_MAP_X_SHIFT;
  246.           new_y=cur_abs_y>>BLOCK_MAP_Y_SHIFT;
  247.           if ((new_x!=cur_x)||(new_y!=cur_y)) {
  248.              cur_x=new_x;
  249.              cur_y=new_y;
  250.              Ll_Push_In_Array(block_temps, cur_x, cur_y, cur_line);
  251.              }
  252.           cur_abs_y+=y_unit;
  253.           error_term+=x_diff;
  254.           if (error_term>=y_diff) {
  255.             error_term-=y_diff;
  256.             cur_abs_x+=x_unit;
  257.             } /* end if */
  258.           } /* end for */
  259.       } /* end if (x_diff>y_diff) */
  260.    } /* end loop through lines */
  261.       
  262. pline_list cur_list_column;
  263. pline_list cur_line_list;
  264. pline_link cur_link;
  265. short line_count;
  266.  
  267. the_block_map.blocks=(pline_list *)NewPtr(the_block_map.x_count*sizeof(pline_list));
  268. for (cur_x=0; cur_x<the_block_map.x_count; cur_x++) {
  269.   the_block_map.blocks[cur_x]=(pline_list)NewPtr(the_block_map.y_count*sizeof(line_list));
  270.   cur_list_column=the_block_map.blocks[cur_x];
  271.   cur_block_line=block_temps[cur_x];
  272.   for (cur_y=0; cur_y<the_block_map.y_count; cur_y++) {
  273.     cur_link=cur_block_line[cur_y];
  274.     line_count=0;
  275.     while (!Ll_Empty_Link(cur_link)) {
  276.       cur_link=Ll_Get_Next_Link(cur_link);
  277.       line_count++;
  278.       }
  279.     cur_line_list=cur_list_column+cur_y;
  280.     cur_line_list->line_count=line_count;
  281.     if (line_count > 0) {
  282.       cur_line_list->lines=(plinedef *)NewPtr(line_count * sizeof(plinedef));
  283.       cur_link=cur_block_line[cur_y];
  284.       short cur_line=0;
  285.       while (!Ll_Empty_Link(cur_link)) {
  286.         cur_line_list->lines[cur_line]=Ll_Get_Data(cur_link);
  287.         cur_link=Ll_Get_Next_Link(cur_link);
  288.         cur_line++;
  289.         }
  290.     } else {
  291.       cur_line_list->lines=NULL;
  292.     }
  293.     cur_link=cur_block_line[cur_y];
  294.     Ll_Clear_Links(cur_link);
  295.   }
  296.   DelPtr(cur_block_line);
  297. }
  298. DelPtr(block_temps);
  299.  
  300. pobject_node * cur_object_list;
  301. the_block_map.objects=(pobject_node **)NewPtr(the_block_map.x_count * sizeof(pobject_node *));
  302. for (cur_x=0; cur_x<the_block_map.x_count; cur_x++) {
  303.    the_block_map.objects[cur_x]=(pobject_node *)NewPtr(the_block_map.y_count * sizeof(pobject_node));
  304.    cur_object_list=the_block_map.objects[cur_x];
  305.    for (cur_y=0; cur_y<the_block_map.y_count; cur_y++) {
  306.       cur_object_list[cur_y]=NULL;
  307.    }
  308. }
  309.  
  310. }
  311.  
  312. void Clear_Block_Map() {
  313. if (!block_map_loaded)
  314.   return;
  315. short cur_x, cur_y;
  316. pline_list cur_list_column;
  317. for (cur_x=0; cur_x<the_block_map.x_count; cur_x++) {
  318.   cur_list_column=the_block_map.blocks[cur_x]; 
  319.   for (cur_y=0; cur_y<the_block_map.y_count; cur_y++) {
  320.     if (cur_list_column[cur_y].lines!=NULL)
  321.       DelPtr(cur_list_column[cur_y].lines);
  322.     }
  323.   if (the_block_map.objects[cur_x]!=NULL)
  324.     DelPtr(the_block_map.objects[cur_x]);
  325.   DelPtr(cur_list_column);
  326.   }
  327. DelPtr(the_block_map.objects);
  328. DelPtr(the_block_map.blocks);
  329. }
  330.  
  331. short Block_X(long real_x) {
  332.    if (block_map_loaded)
  333.       return ((real_x-(the_block_map.x_base<<SHIFT))>>(SHIFT+BLOCK_MAP_X_SHIFT));
  334.    Error("Invalid call to Block_X");
  335.    return 0;
  336. }
  337.  
  338. short Block_Y(long real_y) {
  339.    if (block_map_loaded)
  340.       return ((real_y-(the_block_map.y_base<<SHIFT))>>(SHIFT+BLOCK_MAP_Y_SHIFT));
  341.    Error("Invalid call to Block_Y");
  342.    return 0;
  343. }
  344.  
  345. long Block_Left_Line(long base_x) {
  346.    if (block_map_loaded) 
  347.       return (((((base_x-(the_block_map.x_base<<SHIFT))>>SHIFT)&BLOCK_MAP_X_AND)
  348.          +the_block_map.x_base)<<SHIFT);
  349.    Error("Invalid call to Block_Left_Line");
  350.    return 0;
  351. }
  352.  
  353. long Block_Right_Line(long base_x) {
  354.    if (block_map_loaded) 
  355.       return (((((base_x-(the_block_map.x_base<<SHIFT))>>SHIFT)&BLOCK_MAP_X_AND)+the_block_map.x_base+
  356.          BLOCK_MAP_X_SIZE)<<SHIFT);
  357.    Error("Invalid call to Block_Right_Line");
  358.    return 0;
  359. }
  360.  
  361. long Block_Bottom_Line(long base_y) {
  362.    if (block_map_loaded) 
  363.       return (((((base_y-(the_block_map.y_base<<SHIFT))>>SHIFT)&BLOCK_MAP_Y_AND)+
  364.         the_block_map.y_base)<<SHIFT);
  365.    Error("Invalid call to Block_Bottom_Line");
  366.    return 0;
  367. }
  368.  
  369. long Block_Top_Line(long base_y) {
  370.    if (block_map_loaded) 
  371.       return (((((base_y-(the_block_map.y_base<<SHIFT))>>SHIFT)&BLOCK_MAP_Y_AND)+the_block_map.y_base+
  372.          BLOCK_MAP_Y_SIZE)<<SHIFT);
  373.    Error("Invalid call to Block_Top_Line");
  374.    return 0;
  375. }
  376.  
  377. BOOL In_Block_X(long real_x, short block_x) {
  378.    if (block_map_loaded)
  379.       return ( (Block_X(real_x)==block_x) ? TRUE : FALSE);
  380.    Error("Invalid call to In_Block_X");
  381.    return FALSE;
  382. }
  383.  
  384. BOOL In_Block_Y(long real_y, short block_y) {
  385.    if (block_map_loaded)
  386.       return ( (Block_Y(real_y)==block_y) ? TRUE : FALSE);
  387.    Error("Invalid call to In_Block_Y");
  388.    return FALSE;
  389. }
  390.  
  391.