Hello everyone. This is my first post here, and it's a long one, but I promise it will have pretty looking screenshots at the end!
Ok... I doubt that'll entice anyone to read fifty-seven pages of text. I'll try to be as concise as I can. ^_^;
I've been a fan of Ken Silverman's work for quite some time now. Heck, I still play the Lab3D-SDL port every now and then using a dual-analog control scheme with one of my joypads. Yesterday I decided to take another look-see through Ken's website to check out anything I never did before, one such program being his Cubes5 engine. Since I've actually been contemplating making a First-Person, OpenGL-accelerated game with cubical levels, Cubes5 served as an excellent practical level design test.
The results were actually very surprising! :O
Firstly, the editor isn't on as shaky-go-crashy ground as the accompanying readme suggests. It seems to only crash/hang if you try to add or delete cubes when there's a ton of non-optimized empties already on the screen. Just gotta learn to hit Alt+S a lot. Once I had a completed, super-complex level, I was able to texture the entire thing without a single crash.
16x16x16 cubes goes an extremely long way if you use your space correctly. I managed to fit a grand total of about 13 good-sized rooms in my map, not counting the many hallways and "elevator shafts" running between them all.
As a result of my test, I've determined that for practical considerations, a cubical map alone would be insufficient, but would serve perfectly well as a static base to work off of. In order to truly make a cubical system work there would also need to be additional 3D objects in the level, serving as doors, trapdoors, elevators, stairs, moving platforms, see-through walls and all those fun things. But, for the prospects of my game idea, all of that is practical.
The map I made in Cubes5 took roughly 4 hours to make, start to finish, and I really squeezed every last ounce of space out of it. For practical considerations, it makes more sense to allow the levels to take any dimensions desired, as 16x16x16 forces you to do a lot of work vertically. I'd also probably make the cubes bigger. IMO, for practicality, one cube should be big enough to fit a standing character. (Like in most retro first person shooters.)
As promised at the start, here's some screenshots. Click on them to see them full-sized!
And also, here's a download link to the map file itself for use with Cubes5. I didn't use any custom textures, as I wasn't about to go fiddling around with ART files for the sake of a level design test. :P (GEMTEST.CUB)
And yes, in the rare chance anyone notices or cares, I am the one responsible for the PixelShips series of games. ;)
Anywhoo... My reasons for posting all this is mostly just to gather some feedback regarding the idea of cube based levels. Before anyone says, "Why don't you just use the Build Engine or Doom Engine or something more advanced?" my primary reason is because of the style I'm aiming for, but also because I want to make my own engine for the game and because I want to have a built-in level editor, so simplicity is extremely important.
Thanks to everyone who's able to provide their insight, and to Ken Silverman for making something which, while really old, has given me a solid source of inspiration for an idea that's been brewing in my head for ages! :D
Awesoken at
Re: Practical Work with Cubes5
That's a nice map - you have managed to fit a lot of variety and detail into the limits of CUBES5. I imagine you'll want to increase the resolution for your engine. I'm curious to know if you plan to use hidden surface removal, and if so what method. In the old days, hidden surface removal was essential to getting any kind of frame rate. Nowadays, you can get away without it - at least with small to medium sized maps.
Jinroh at
Yes very nice map! ;) I played around with Ken's Cube Engine before and well, I'm not exactly a mapper so my results were terrible. :D
I too am curious are you going to be using some kind of simple Octree or something to cull all of those cubes?
Gemini at
Actually, to be perfectly honest, I haven't really come up with a good way of ignoring occluded cubes yet. My best thought so far is something like a BSP Tree, but dynamic and able to be updated on-the-fly, transparently to the user. The idea being that, like a BSP Tree, the level is divided into sections, and being in one section determines what other sections are visible. However, instead of being a tree, each section keeps a list of what other sections it's visibly linked to. A section can be as big as the entire map, or as small as a single cube. Sections can also have flags set so that they may or may not allow other connecting sections to become visible based on the status of doors or such.
Perhaps there's a name for that approach, I dunno what it is though.
There would also be basic visibility culling so that cubes outside of your field of view would not be rendered.
One other optimization that came to mind is surface welding. For example, let's say you have a straight hallway that is 3 cubes tall, 2 cubes wide and 12 cubes long. To render the interior of that hallway you'd normally have to send 120 surfaces down the video pipeline. If each wall, floor and ceiling has identical textures though, you could simply draw 4 large surfaces instead with repeating textures.
One last optimization I can think of is that, since all the cubes are identical in shape and don't spin or anything, you can ignore surfaces to render simply based on the camera's viewing angle and field of view. I haven't the vaguest idea how to calculate that, but I know it can be done.
At present though, I'm working on a non-accelerated 2D project, and the last time I dabbled in 3D I was working on stuff that didn't require level design, so I'm still pretty new to the concept from a programming standpoint. ^_^;
0xC0DE at
The method (to find occluded cubes) you describe sounds to me like portals. you might want to look into that :)
Gemini at
I knew there was a term for what I was thinking of! :)
Funny thing I forgot that since one of my favourite games (Descent 3) uses that technique.
With cube-based maps it also becomes ridiculously simple to figure out where the portals go. Any cube containing a door that has a solid wall on all sides except the entry and exit would be a portal. Any cube with only two open walls and four solid walls connected to a cube with at least three open walls or more would also be considered a portal. A paint-can/fill style algorithm would then be used to find the bounds of each sector on either end of a portal. To top it all off, with the cubes being static, sectors can instead create a list of optimized surfaces to render instead of scanning every cube every frame and rendering them.
...that would actually work REALLY well... indoors...
In the first of my eight screenshots of the map I made, we see a building outside. (Yeah, the blue tiles are supposed to be the sky.) The bounding volume of such an algorithm would encompass that entire space. Worse, there’s a hole that goes all the way to the bottom. The bounding volume there would virtually be the ENTIRE map.
I’d have to come up with a system that can split huge sectors like that into several... that’s gonna take some thinking...
---------------
EDIT:(removed because it was an embarrassingly wrong approach that I thought worked perfectly)
---------------
2nd EDIT: I made an update to my post here but deleted it because it was a complete embarrassment when I realized that it seemed practical at first, but the more I thought about it the more ridiculous it was. x_x;
So here's a BETTER update with an algorithm for generating sectors and portals on a 2D map of squares:
The way this one works in 2D is to first scan the map for large, perfectly rectangular sections, starting with the largest and working its way down in size until it gets as small as 2x2. Each sector's open edges become portal edges. Once no more rectangular sections at least 2x2 can be turned into sectors, the system starts scanning for nx1 rectangles, from largest to smallest.
In the image above is a visibility demonstration for two viewers. Each light-blue sector should be rendered for its encompassing viewer because their field of view touches that sector.
I'm not sure what a good method would be yet for determining visible portals. My first thought was to ray-cast towards the vertices for each portal, until I realized that it was possible to have a line of sight through a portal that doesn't touch one of its vertices.
Also, is it just my imagination, or is something like what I've come up with here happening in Cubes5?
Edited by Gemini at
Awesoken at
CUBES5.C splits the world into boxes, similar to your image at right. In CUBES5.C, study the makeboxbsp() function. (It is poorly named, as it has nothing to do with a BSP.) Anyway, this is the routine that groups the little cubes into larger boxes. I used a pretty simple method: 1. Select a random x,y,z location that is air. 2. Grow the box in each direction until it can't grow any more. 3. Add the sector are mark the cells as done. 4. Repeat until all cells are marked. I have found it to work quite well. I'm not sure it's worth your time to devise a more elegant method. BTW, you can view the regions as they draw in CUBES5 by holding ` (the key above Tab) and pressing Backspace repeatedly. You can also press KeyPad Enter a few times until you get to the wireframe mode. If you fly around the map, you'll see some areas with white lines floating in the air. These are region boundaries.
Gemini at
That may explain why it sometimes hangs when adding or deleting new cubes...
I noticed you’re using your own custom-made random number generator in Cubes5. It’s definitely a lot simpler than the one I made for myself, but something about it set off a warning light in my head, so I decided to put your Cubes5 random number generator to the test to see just how random it is and... it’s not random at all. x_x;
Basically, it is incapable of generating the same number twice in a row because in order to generate a particular number a second time it must generate 65,535 other numbers first. In fact, it follows a pattern that covers all 65,536 results equally and never deviates from that pattern.
...and you used it to optimize the board...
I think that’s why it ends up hanging. It may end up entering an infinite loop as a result of always following the same number pattern.
...though I suspect you probably knew all that, and if not... well... now you do! ;)
But yeah, when I saw the extra lines for the first time in Cubes5's wireframe mode, I at first didn’t get why they were there. Then, after figuring out how to split the board into sectors last night, it started to dawn on me that’s probably the same method you were using, and those extra lines were sector edges.
Heh... making a hardware accelerated game engine using cubes is really starting to seem plausible. I just need to figure out how to detect which sector portals are visible and which aren’t and the rest should be easy! ;D
Awesoken at
I agree that my random number generator is not very good, but that does not explain the crash. You seem to have overlooked a little trick in my makeboxbsp() routine. I use an array called 'tempshort' to hold a list of all air blocks that have not yet been assigned to sectors. So when I throw a new dart, it is guaranteed to be an air block - there is no need to retry the dart.
Portal rendering would be easy if there was widespread support for an "occlusion query". Basically, you would send a polygon (i.e. your portal) to the rendering engine, and without actually drawing it, the engine would determine whether any of its pixels would have been visible, givin the current state of the Z-buffer. I know this method works well, but I have only tested it in a CPU-based rendering engine. I don't know whether there's enough video driver support to make it useful - I haven't done hardware accelerator programming in a while. If this is not the case, then you're stuck with less elegant / more difficult options.
Gemini at
I took another look at the Cubes5 source and yeah, I see now what that “a” variable is doing, and what the tempshort[] array is up to.
...then I noticed there’s no boundary checking. :o
There’s nothing limiting the variables which create the sector boundaries, which means if the user delete cubes from the edges of the map, the sector boundaries can actually wrap around. For the Z and Y axises, this isn’t too dangerous because the array position within cubesect[] will still be valid. BUT, if the X axis wraps around, the position within the cubesect array will either underflow or overflow the array boundaries. Now, normally this isn’t that bad, because all that’s happening is reading from the array position, but if the value read just happens to be -2, it’ll get written to once the sector scan is done, and who knows what value in memory just got overwritten! o_o;
As per the portals, I just perused the OpenGL reference material and found a command pair known as glBeginQuery() and glEndQuery() which seem to scan if something to render passes the depth test... but I haven’t been able to find out yet if these commands actually render anything or not. If they do, I suppose it doesn’t matter for the sake of portals because you could just turn Z-Buffer writing off during the render, then turn it back on and render the sector that’s actually supposed to be there.
So yeah, that would make things simpler for sure... Provided I don’t decide to go for a different idea after my current project, this is definitely looking a lot more promising than before! :)
Plagman at
Yeah, BeginQuery()/EndQuery() are for the occlusion queries Ken described. They do not affect the actual rendering pipeline, though. You'll have to use ColorMask()/DepthMask() if you don't want your portals to show up. Occlusion queries were promoted to core OpenGL 1.5, so relying on them should be pretty safe if you're targeting hardware from the past ~7 years. Keep in mind querying the result of an occlusion query will force OpenGL to flush the command buffer and wait until the GPU is done rendering your portal, effectively emptying a _very_ long and wide hardware pipeline. If you can help it, throw your queries long before figuring if you need to render what relies on them and query for completion status instead of forcing a result query. This alone makes occlusion queries pretty suboptimal for efficient GPU-based serialized portal rendering. I suspect you don't really care for something as simple as rendering simple scenes like that. If you ever become GPU-limited because of heavy shading, an alternative might be to submit all your portals and sector geometry in a first depth-only pass without shading using NV_conditional_render, and then do a second pass after getting the results of the queries to only draw what's really on screen with all the fancy shading enabled. FYI, my custom GPU-based BUILD renderer currently relies on these same OpenGL occlusion queries but I'm actively researching alternatives because of this issue.
Gemini at
Hmm... having glFlush() called after each portal check certainly wouldn’t be nice to the framerate...
However, after scouring the net for awhile I came across a website (http://billbaxter.com/projects/occlusion.html) that suggests that using the OpenGL histogram features in conjunction with depth testing would provide a means of occlusion culling.
One benefit here is that with clever colouring of the portal surfaces during the histogram-enabled rendering, it would be possible to check several portals in a sector at once.
One drawback is that not all hardware is going to support it... though I would imagine most should. In order for the histogram features to work, “ARB_imaging “ must be returned by glGetString(GL_EXTENSIONS). The histogram functions are pretty old, with the earliest optional implementations dating back to OpenGL 1.2, so I would imagine most respectable OpenGL-capable hardware made in the past 7 or 8 years should support them. That’s a wild guess though.
My outdated GeForce FX 5200 card does. :)
Awesoken at
I made bounds checking the responsibility of the editor. I looked through my code, and could not find any place where it could write a negative number to one of the 6 edges of the board[] array. The crash is most likely due to one or more of my statically allocated arrays overflowing while rendering a complex scene. I was reluctant to use dynamic memory allocation back then.. how silly of me : P
Gemini at
The board[] array is fine. It's the cubesect[] array that can go out-of-bounds in either direction during the makeboxbsp() function. If a sector being processed ends up with an X boundary of 0 or 15 at any moment, then the scanning algorithm ends up scanning an X coordinate of -1 or 16 which ends up outside of the cubesect[] array bounds.
I think one way to test this would be to make a board that's really complex, but doesn't have any cubes with x y or z coordinates of 0 or 15. It's kinda late now though where I am... I'll try it tomorrow.
I suppose it doesn't really matter since the program is over a decade old, but I'm usually really good at debugging so I always like the challenge of trying to figure out why something doesn't work perfectly. ^_^;
----------------
EDIT: Waaaaaaaaitaminute... I just noticed that my huge, complex map is only 14x14x14 in size... So you've actually got a 1-cube-wide forced boundary encircling the entire board, meaning the overflow conditions I described can't actually happen because you can't modify the cubes on the edges! :O
Tricky...
So yeah... something else IS going on...
Edited by Gemini at
jeffz at
Gemini said at
Anywhoo... My reasons for posting all this is mostly just to gather some feedback regarding the idea of cube based levels. Before anyone says, "Why don't you just use the Build Engine or Doom Engine or something more advanced?" my primary reason is because of the style I'm aiming for, but also because I want to make my own engine for the game and because I want to have a built-in level editor, so simplicity is extremely important.
have you seen the Cube/Sauerbraten engine?
http://cubeengine.com/cube.php4
0xC0DE at
jeffz said at
Gemini said at
Anywhoo... My reasons for posting all this is mostly just to gather some feedback regarding the idea of cube based levels. Before anyone says, "Why don't you just use the Build Engine or Doom Engine or something more advanced?" my primary reason is because of the style I'm aiming for, but also because I want to make my own engine for the game and because I want to have a built-in level editor, so simplicity is extremely important.
have you seen the Cube/Sauerbraten engine?
http://cubeengine.com/cube.php4
Other then the name it bares little resemblens to ken's cube engine, or the stuff Gemini is talking about. The Sauerbraten engine can render all sorts of 3D models and objects and they aren't bound to a 3d (cube) grid.
jeffz at
Hugo Smits said at
jeffz said at
Gemini said at
Anywhoo... My reasons for posting all this is mostly just to gather some feedback regarding the idea of cube based levels. Before anyone says, "Why don't you just use the Build Engine or Doom Engine or something more advanced?" my primary reason is because of the style I'm aiming for, but also because I want to make my own engine for the game and because I want to have a built-in level editor, so simplicity is extremely important.
have you seen the Cube/Sauerbraten engine?
http://cubeengine.com/cube.php4
Other then the name it bares little resemblens to ken's cube engine, or the stuff Gemini is talking about. The Sauerbraten engine can render all sorts of 3D models and objects and they aren't bound to a 3d (cube) grid.
Ignoring the models it can load, the basic premise of Cube and Sauerbraten is that everything is made from cubes.
0xC0DE at
jeffz said at
Hugo Smits said at
jeffz said at
Gemini said at
Anywhoo... My reasons for posting all this is mostly just to gather some feedback regarding the idea of cube based levels. Before anyone says, "Why don't you just use the Build Engine or Doom Engine or something more advanced?" my primary reason is because of the style I'm aiming for, but also because I want to make my own engine for the game and because I want to have a built-in level editor, so simplicity is extremely important.
have you seen the Cube/Sauerbraten engine?
http://cubeengine.com/cube.php4
Other then the name it bares little resemblens to ken's cube engine, or the stuff Gemini is talking about. The Sauerbraten engine can render all sorts of 3D models and objects and they aren't bound to a 3d (cube) grid.
Ignoring the models it can load, the basic premise of Cube and Sauerbraten is that everything is made from cubes.
Except that it's not. There's not a single screenshot on that page that consist entirly out of cubes on a 3d (cube) grid.
Gemini at
Yes, I have worked with that engine before.
I don't like it.
The main reason I don't like it is because it's very complicated to do anything with. The squares are very small, so in order to change height values and such you have to select a group of them on the floor or ceiling and then alter their height, change ramping, etc.
And yeah, it's not truly cubes but floors and ceilings that are square shaped. Like the original System Shock, but much smaller squares. The fact that they call it a cube engine is misleading.
I've been going over my game idea that I would make with a cubical engine and I really do need to make it myself. A couple of the features I've thought of would be very difficult to pull off with any of the existing engines I've seen, most notably having a built-in level editor. Besides, I know enough about OpenGL to go for it from scratch when the time comes. ;)
EDIT: Then again, it seems the newer version does allow for multiple floors and ceilings in one cube column. Considering how difficult the editor was to use before I can't imagine it being any easier with a feature like that. x_x;
Edited by Gemini at
jeffz at
Gemini said at
Yes, I have worked with that engine before.
I don't like it.
The main reason I don't like it is because it's very complicated to do anything with. The squares are very small, so in order to change height values and such you have to select a group of them on the floor or ceiling and then alter their height, change ramping, etc.
And yeah, it's not truly cubes but floors and ceilings that are square shaped. Like the original System Shock, but much smaller squares. The fact that they call it a cube engine is misleading.
I've been going over my game idea that I would make with a cubical engine and I really do need to make it myself. A couple of the features I've thought of would be very difficult to pull off with any of the existing engines I've seen, most notably having a built-in level editor. Besides, I know enough about OpenGL to go for it from scratch when the time comes. ;)
EDIT: Then again, it seems the newer version does allow for multiple floors and ceilings in one cube column. Considering how difficult the editor was to use before I can't imagine it being any easier with a feature like that. x_x;
The new ingame editor for sauerbraten is much much easier than the old one, the new maps are a testament to that. The cube size that you manipulate can be adjusted from either very small up to very large. The only negative thing for me is that it's written in C++.
Gemini at
Well, I still think I'd prefer to make my own engine. Mostly for the challenge. ;)
jeffz at
Hugo Smits said at
Except that it's not. There's not a single screenshot on that page that consist entirly out of cubes on a 3d (cube) grid.
All made by manipulating cubes, despite what you think you see.