Maze Game

[anarkavre]

Here is a screenshot of a maze game I am making. I hope to eventually make it into a Diablo style game. Does anyone know a decent way I could do clipping of the map. Right now it isn't the most efficient way that I could probably do it.

Code: [Select]

gluLookAt(playerX + 3.0, 3.0, playerY + 3.0, playerX, 0.0, playerY, 0.0, 1.0, 0.0);

if (playerX - 10.0 >= 0)
sx = (int)(playerX - 10.0);
else
sx = 0;

if (playerY - 10.0 >= 0)
sy = (int)(playerY - 10.0);
else
sy = 0;

if (playerX + 3.0 <= 20)
ex = (int)(playerX + 3.0) + 1;
else
ex = 21;

if (playerY + 3.0 <= 20)
ey = (int)(playerY + 3.0) + 1;
else
ey = 21;

glTranslatef(sx + 0.5, 0.0, sy + 0.5);

for (y = sy; y < ey; y++)
{
glPushMatrix();

for (x = sx; x < ex; x++)
{
if (maze[y * 21 + x])
drawCube(x, y);
glTranslatef(1.0, 0.0, 0.0);
}

glPopMatrix();

glTranslatef(0.0, 0.0, 1.0);
}

It was basically a guess for the values 10.0 and 3.0.

[Bad Sector]

Can you describe with words what you want to do? (also what do you mean with clipping?)

[anarkavre]

Basically my maze is an array and I don't want to loop through the entire thing as this will be a waste for large maps. I basically need a way to only draw what is seen on the screen.

[Hugo]

Well, you can achieve this in a few ways.  First off, we need to determine what exactly you want to do with the camera.  Does it rotate ? or just move it’s position ?
If it only moves position you can work something out as followed :

Code: [Select]

#define camera_max_x_screen (10) // how many tiles can be seen on the x-axe
#define camera_max_z_screen(20) // how many tiles can be seen on the z-axe
for(z = 0; z < camera_max_z_screen; z++)
{
for(x = 0; x < camera_max_x_screen; x++)
{
map[camera.z - (z/2)][camera.x - (x/2)];
}
}

This isn’t the best or most efficient way, because there’s still some overdraw. But at least it’s a lot less then rendering the whole map and it’s also very speed consisted (it doesn’t matter if you render a big map, or a small map).

The best way to handle this, is a bit more complicated. What we basically need to do is cast some rays over the 2D map array.

[Bad Sector]

Or project the camera frustum on the 2D map array and find which cells it touches*. That would tell you exactly what is visible. An easier (and faster for the CPU) method is to project the camera's frustum in the 2D map array, find the bounding rectangle and render its contents in a loop similar to what Hugo said.

Since in today's cards its more important to do few GPU calls which draw more than seen (well not everything, but not exactly what is seen either) than many GPU calls that draw exactly what is seen, instead of rendering each cell separately, you should combine the cells in clusters which are made of -for example- 16x16 cells. These clusters will have the static cell geometry compiled in a display list (sorted by texture if possible). When you figure out the bounding rectangle of the frustum in the 2D array just find the clusters it touches* and call their display lists.

You can also keep a list of the dynamic stuff (monsters, items, etc) in the clusters and when you render the clusters, have the dynamic stuff in them rendered too (just make sure to update the lists when the dynamic stuff moves - keeping a list in each dynamic item with the clusters it touches (an item can be inside more than one cluster if the items move freely and not in the grid) helps)

Thats how i would structure it initially at last. After that, benchmarking with real data would tell me if i'm on the right track or not (too bad NVPerfHud doesn't work with OpenGL... although there is NVPerfSDK which can be used by OpenGL programs to manually query the GPU signals, but i haven't checked it out yet)

(*=with "touch" i mean cells/clusters which are either partially or fully inside)

EDIT: note that the above will work fine as long as the camera looks mostly "down" as in your shot. As the camera "looks up" towards the horizon, its projected frustum will get very large and the bounding rectangle will be big enough to contain a lot of otherwise invisible stuff. In this case instead of using that bounding rectangle, you should project the frustum in the *cluster grid* to find exactly which clusters are visible.

[anarkavre]

Using the frustum was one idea I thought of. I found this website which describes how to extract the frustum.
http://www.crownandcutlass.com/features/technicaldetails/frustum.html
Would I need the planes in normalized form or not for what I want to do?

[Bad Sector]

Having the frustum planes available is always a good thing, so yes normalize them. There isn't a reason to not do so, a few sqrts for each frame aren't going to affect your framerate even if the engine was running in an old Pentium.