Sign in to follow this  
Sephnroth

calculating visibility

Recommended Posts

Hello, I have been working for a month or so on an rpg-ish like engine using darksdk (i heard some people mention darkbasic before - its like that, but its the db engine in c++ .lib form - allows me to access some stuff using directx manually and the like) - the dungeons for the most part are randomly generated much like in the ps2 game Dark Chronicle (or dark cloud 2 for non-europeon users). Now some of these dungeons are quite big. The FPS used to drop quite considerably with a full sized one until I decided it was about time I wrote something to calculate a visibility table so I could hide objects that wernt there. I am kind of fortunate in that my dungeon maps are 2d array based, much like a 2d tile engine. Well, it basically IS a 2d tile engine but with 3d tiles. Now, the best way to calculate accurate visibility trees that I know of is raycasting and checking for collisions with objects, if it hits one add it to the vis list for that particular tile. But I avoided this completly - because my dungeons are randomly generated I cannot precalculate the visibility tables, this means any vis calculations get added to the loading time for that level. I figured raycasting, though accurate, would be far too slow. The idea that I managed to come up with was to use breshams line drawing alogorithm to draw lines through my 2d array from each tile in the map to each other tile and whenever the line passes over a hard tile in the array it stops drawing and returns that point as the hit and it gets added to the vislist. Its quite good in theory and its certainly fast enough to not be too much of a bother on the loading time.. but it turned out to be far to inaccurate due to the 3d nature of the game. For example most of my wall tiles have a short wall, a small bit of floor and then a high wall. The high wall blocks vision, the low wall does not. But to the vis calculation its all the same thing which caused tiles which were partially visable to be hidden which looks well nasty in game. I have got partially around this by adding a tolerance factor to the line routine making it say pass through 3 solid objects before it counts as a hit. That was an okay bodge job, until now. Im now adding more effects, shaders and stuff to the engine and the fps is begining to get low again. I know its because of this stupid tolerance system i use which means, if you imagine a "." is floor and a "x" is a wall and "p" is player then consider this: x.p.....x....................x...x because of the tolerance at 3 the engine would draw -everything- in that line, all the floors and their attached entities and stuff and in maps with lots of open spaces you really notice it in game. So my question is what would people recommend as a good way of calculating my visibility table? For refrance I will provide the code that i use to generate the vis list and the line of sight routine it uses as I figure the more you guys know the better you can help me (which is why this post is so long, I apologise). The Vistable calculation:
void CalculateVisTable() {

	bool cl, cr, cu, cd, cur, cul, cdr, cdl;
	int NextID = 0;

	register int f;
	register int x;
	register int y;
	register int x2;
	register int y2;

	

	for (f = 0; f < Dungeon[0].NumFloors; f++) {
		for (y = 0; y < DungeonH; y++) {
			for (x = 0; x < DungeonW; x++) {			
				NextID = 0;
				
				if (VisTable[f][y][x].VisList != NULL)
					free(VisTable[f][y][x].VisList);

				VisTable[f][y][x].VisList = (Co2D*)malloc(sizeof(Co2D));

				//Check for valid map co-ordinates in each direction of the current map section
				if (IsValidMC(x - 1)) cl = true; else cl = false;
				if (IsValidMC(x + 1)) cr = true; else cr = false;
				if (IsValidMC(y - 1)) cu = true; else cu = false;
				if (IsValidMC(y + 1)) cd = true; else cd = false;

				if (cl && cu) cul = true; else cul = false;
				if (cr && cu) cur = true; else cur = false;
				if (cl && cd) cdl = true; else cdl = false;
				if (cr && cd) cdr = true; else cdr = false;
				

				//first check all squares visable from this exact location
	
				for (y2 = 0; y2 < 100; y2 ++) {
					for (x2 = 0; x2 < 100; x2 ++) {					

						if (IsFloor(f, x, y)) {
							if (Get3dDistance(x * TileSize, 0, y * TileSize, x2 * TileSize, 0, y * TileSize) < MAX_DRAW_RANGE + TileSize/2) {
								if (GetLOS(f, x, y, x2, y2)) {// || Dungeon[f].Data[y2][x2].id == 2) {
									//If the object is visable, add its object id to the vis list

									VisTable[f][y][x].VisList = (Co2D*)realloc(VisTable[f][y][x].VisList, sizeof(Co2D) * (NextID + 1));
									VisTable[f][y][x].VisList[NextID].x = x2;
									VisTable[f][y][x].VisList[NextID].y = y2;
									VisTable[f][y][x].VisList[0].s = NextID;
									NextID++;
									

									//here I add all the adjencent squares to the one that finally hit, to avoid clipping when
									//looking around part of a corner.. I know, this is NOT good.

									if (cl) {
										if (!VisIdExist(f, x - 1, y, x2, y2)) {
											VisTable[f][y][x].VisList = (Co2D*)realloc(VisTable[f][y][x].VisList, sizeof(Co2D) * (NextID + 1));
											VisTable[f][y][x].VisList[NextID].x = x2 - 1;
											VisTable[f][y][x].VisList[NextID].y = y2;
											VisTable[f][y][x].VisList[0].s = NextID;
											NextID++;
										}
									}
									
									if (cr) {
										if (!VisIdExist(f, x, y, x2 + 1, y2)) {
											VisTable[f][y][x].VisList = (Co2D*)realloc(VisTable[f][y][x].VisList, sizeof(Co2D) * (NextID + 1));
											VisTable[f][y][x].VisList[NextID].x = x2 + 1;
											VisTable[f][y][x].VisList[NextID].y = y2;
											VisTable[f][y][x].VisList[0].s = NextID;
											NextID++;									
										}
									}
									
									if (cu) {
										if (!VisIdExist(f, x, y, x2, y2 - 1)) {
											VisTable[f][y][x].VisList = (Co2D*)realloc(VisTable[f][y][x].VisList, sizeof(Co2D) * (NextID + 1));
											VisTable[f][y][x].VisList[NextID].x = x2;
											VisTable[f][y][x].VisList[NextID].y = y2 - 1;
											VisTable[f][y][x].VisList[0].s = NextID;
											NextID++;
										}
									}
									
									if (cd) {
										if (!VisIdExist(f, x, y, x2, y2 + 1)) {
											VisTable[f][y][x].VisList = (Co2D*)realloc(VisTable[f][y][x].VisList, sizeof(Co2D) * (NextID + 1));
											VisTable[f][y][x].VisList[NextID].x = x2;
											VisTable[f][y][x].VisList[NextID].y = y2 + 1;
											VisTable[f][y][x].VisList[0].s = NextID;
											NextID++;
										}
									}

									if (cul) {
										if (!VisIdExist(f, x, y, x2 - 1, y2 - 1)) {
											VisTable[f][y][x].VisList = (Co2D*)realloc(VisTable[f][y][x].VisList, sizeof(Co2D) * (NextID + 1));
											VisTable[f][y][x].VisList[NextID].x = x2 - 1;
											VisTable[f][y][x].VisList[NextID].y = y2 - 1;
											VisTable[f][y][x].VisList[0].s = NextID;
											NextID++;
										}
									}

									if (cur) {
										if (!VisIdExist(f, x, y, x2 + 1, y2 - 1)) {
											VisTable[f][y][x].VisList = (Co2D*)realloc(VisTable[f][y][x].VisList, sizeof(Co2D) * (NextID + 1));
											VisTable[f][y][x].VisList[NextID].x = x2 + 1;
											VisTable[f][y][x].VisList[NextID].y = y2 - 1;
											VisTable[f][y][x].VisList[0].s = NextID;
											NextID++;
										}
									}

									if (cdl) {
										if (!VisIdExist(f, x, y, x2 - 1, y2 + 1)) {
											VisTable[f][y][x].VisList = (Co2D*)realloc(VisTable[f][y][x].VisList, sizeof(Co2D) * (NextID + 1));
											VisTable[f][y][x].VisList[NextID].x = x2 - 1;
											VisTable[f][y][x].VisList[NextID].y = y2 + 1;
											VisTable[f][y][x].VisList[0].s = NextID;
											NextID++;
										}
									}

									if (cdr) {
										if (!VisIdExist(f, x, y, x2 + 1, y2 + 1)) {
											VisTable[f][y][x].VisList = (Co2D*)realloc(VisTable[f][y][x].VisList, sizeof(Co2D) * (NextID + 1));
											VisTable[f][y][x].VisList[NextID].x = x2 + 1;
											VisTable[f][y][x].VisList[NextID].y = y2 + 1;
											VisTable[f][y][x].VisList[0].s = NextID;
											NextID++;
										}
									}

								} else {
									if (x2 == LosHitX && y2 == LosHitY) {
										
										if (Get3dDistance(x * TileSize, 0, y * TileSize, x2 * TileSize, 0, y * TileSize) < MAX_DRAW_RANGE + TileSize/2) {
											if (!VisIdExist(f, x, y, x2, y2)) {
												VisTable[f][y][x].VisList = (Co2D*)realloc(VisTable[f][y][x].VisList, sizeof(Co2D) * (NextID + 1));
												VisTable[f][y][x].VisList[NextID].x = x2;
												VisTable[f][y][x].VisList[NextID].y = y2;
												VisTable[f][y][x].VisList[0].s = NextID;
												NextID++;
											}
										}
									}
								}//*/
							}
						}


						
			
					}
				}
			}
		}
	}


} 

and its two helper functions:
//line of sight inside the map array using breshams
bool GetLOS(int f, int x1, int y1, int x2, int y2) {
    int u = 0;
    int dx, dy, c, M, xinc = 1, yinc = 1;
	int hits=0;
    int x = x1;
    int y = y1;
    dx = x2 - x1;
    dy = y2 - y1;

    if (dx < 0) { xinc = -1; dx = -dx; }
    if (dy < 0) { yinc = -1; dy = -dy; }

    if (dy < dx) {
        c = 2 * dx; 
		M = 2 * dy;

        while (x != x2) {
            
			if (d(f, x, y) != 1 && d(f, x, y) != 3) {
				LosHitX = x;
				LosHitY = y;
				hits++;

				if (hits > LOS_TOLERANCE)
					return false;
			}

            x += xinc; 
			u += M;

            if (u > dx) { y += yinc; u -= c; }
        }

    } else {

        c = 2 * dy; 
		M = 2 * dx;

        while(y != y2) {
			if (d(f, x, y) != 1 && d(f, x, y) != 3) {
				LosHitX = x;
				LosHitY = y;
				hits++;

				if (hits > LOS_TOLERANCE)
					return false;
			}

            y += yinc; 
			u += M;

            if(u > dy) { x += xinc; u -= c; }
        }
    }


	return true;
}

//This code returns wether or not an id has already been added to the vislist so I dont add duplicates
//its written in asm because I was interested in learning it so it was an exercise.  It uses a hashing technique.

bool VisIdExist(int f, int x, int y, int x2, int y2) {

	bool r;	
	int *addr = (int *)&VisTable[f][y][x].VisList[0];
	
	int ThisSize = VisTable[f][y][x].VisList[0].s;
	__asm {

		mov eax, 0						;set eax to 0 (array index)
		mov ebx, [addr] 				;array data
		mov ecx, 0						;holder for second half of array calcs (hashing)
		mov edx, 0						;holder for first half
		mov esi, 0						;im sure i shouldnt be using this register but what the hell. its eax * 2

		lp:
			mov edx, [eax * 4 + ebx]	;store the value of the current index of the array in edx
			cmp edx, [x2]				;compare edx (array value) to the value we are looking for
			je checkY					;jump to "rt" if the values match
	
			mov esi, eax				;second half of the array
			add esi, [ThisSize]
			mov ecx, [esi * 4 + ebx]
			cmp ecx, [x2]
			je checkY2

			cmp edx, [-1]
			je rt2

			cont:
			inc eax						;increase eax
			cmp eax, [ThisSize]			;compare eax against max size of the array
			jge rt2						;jump to "rt2" lable if eax was greater than or equal to maxsize

		jmp lp							;jump back to "lp"


		checkY:
			mov edx, [eax * 4 + 4 + ebx]
			cmp edx, [y2]
			je rt

			jmp cont

		checkY2:
			mov ecx, [esi * 4 + 4 + ebx]
			cmp ecx, [y2]
			je rt

			jmp cont

		rt:
			mov [r], 1			;set return result to 1 (true)
			jmp end

		rt2:
			mov [r], 0			;value wasnt found.

		end:
	};
	

	return r;
}

Well, thats all my code for what good it is. There has -got- to be a better and more accurate way of doing things than this, but i'm all out of ideas :/

Share this post


Link to post
Share on other sites
Look up "occlusion culling".

In the meantime, how about this: each tile has max_height and occluder_height. max_height is of course the highest visible point of a tile and occluder_height is the height below which nothing can be seen beyond it. As you cast your ray, you compare the max_height of a tile to the highest occluder_height so far. Something like this:
    occlusion_tangent = 0;
while ( ... )
{
...
occluded_height = occlusion_tangent * ray_distance;

if ( tile->max_height > occluded_height )
{
tile->draw();

if ( tile->occluder_height > occluded_height )
{
occlusion_tangent = tile->occluder_height / ray_distance;
}
}
...
}

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this