From: chrisp@wimsey.bc.ca (Chris Phillips)
Subject: Re: blocking out walls
Organization: Wimsey Information Services
Date: Mon, 25 Jan 1993 11:22:42 GMT
X-Newsreader: Tin 1.1 PL5

:         To add yet another question about Wolf3d games: Has anyone got a good algoritm for eliminating walls that you couldn't see(wall behind other walls). I have tried having it check the tiles in a line between you and the tile in question and haven't had very much success. It may be because I had some errors in my algorith, but I wanted to see if anyone else had a better idea. Also about those pesky wall sections that you can only see part of, is it easiest just to print ther closer one last or is th
er


	What you need is whats called an Extent list.

	First order of business is to create a list of all walls you want
to draw in order(front to back).

	Next you need an array with 1 bit for every pixel wide your
screen is. So if your screen or view window is 320 you need 320 bits(or bytes
for speed) in your array.
	
	Next go through the list front(closest wall to you) to back (wall
furthest away). For each wall fill in the bits in the array that corespond
to the minimum and maximum x value of the wall. If you set any bits in this
step the wall is visible and must be drawn. When all bits in the array are
filled you can stop looking.

	Here is some code that should give you the idea.

NOTE: This code is completly un-tested. It is provided as an example only
and proably contains many typing and other errors.

char extent_list[VIEWPORT_WIDTH];

void clear_extent_list()
{
int i;
for(i=0;i<VIEWPORT_WIDTH;i++)
	extent_list[i]=0;

}
/*************************************************/
/* This function returns TRUE if the wall is     */
/* visible and must be drawn. This funtion also  */
/* fills in the extent list.                     */
/* Called with: Projected view port coord's for  */
/* the min and max x value of a wall             */
/*************************************************/
char check_wall_against_extent(int x1,int x2)
{
int i;
char flag=0;     /*assume no draw*/
for(i=x1;i<x2;i++)	/*go from left to right*/
	{
	if(extent_list[i]==0)    /*if no wall already here*/ 
		flag=TRUE;		/*set flag to draw wall*/
	extent_list[i]=1;	/*fill in extent list for this wall*/
	}
return(flag);
}
/***********************************************/
/* This funtion will go through a list of      */
/* walls and mark the visible ones as drawable */
/* This function assumes a global array of     */
/* structures as follows                       */
/* 1. wall.x1,wall.y1 .... wall.x4,wall.y4     */
/* the 4 corners of the wall to draw in        */
/* in clock-wise order starting with upper     */
/* left.                                       */
/* 2. wall.draw                                */
/* Flag to set if wall is visible              */
/* NOTE: This array must be sorted so the      */
/* the wall closest to you is element 0        */
/* and the wall furthest from the viewer is    */
/* element number "num_walls_to_render"        */
/***********************************************/*
void check_extent_list()
{
clear_extent_list();
for(i=0;i<num_walls_to_render;i++)
	{
	wall[i].draw=FALSE; /*assume no draw*/
	if(check_wall_against_extent(wall[i].x1,wall[i].x2))
		wall[i].draw=TRUE;   /*mark wall to draw*/
	}
}
/**********************************************/
/* your main will proably look somthing like  */
/* this.				      */
/**********************************************/
void my_main()
{
int i;
num_walls_to_render=build_list_of_all_walls_in_visible_range();
sort_all_walls_front_to_back();
project_and_rotate_points_to_create_polygons_of_walls();
clip_all_walls_to_view_port();
check_extent_list();
for(i=num_walls_to_render;i>=0;i--) /*NOTE: draw walls back to front*/	
	if(wall[i].draw)
		draw_wall(&wall);
}

If anything in this mess isn't clear I'll be happy to answer any questions.

	Good Luck
		Chris
		chrisp@wimsey.bc.ca


		



: 
Xref: sparky rec.games.programmer:5545 rec.games.misc:19410 comp.sys.ibm.pc.games:33459