Sauerbraten initial development documentation ============================================= This document describes the state of sauerbraten at the moment of its initial open source release. Anyone who wants to program as part of the sauerbraten project should read this document VERY carefully. Sauerbraten History =================== Sauerbraten was started as an effort to take the ideas behind Cube further: both allow significantly more geometrical possibilities while at the same time being simplified compared to Cube's internal structure. Read all about this on the Sauerbraten homepage: http://wouter.fov120.com/sauerbraten/index.html Sauerbraten is based on the cube source code of roughly the november 2002 state, and both code bases have diverged significantly since. The base Cube code was cleaned up a bit, and all code specific to the cube world structure removed or commented out. Some other parts of cube dependent on this were also commented out, but most code is in the sauerbraten base unmodifed. All gamecode, client/ server code, physics (dynamics, not collision), sound, monsters, weapons, console/scripting, entities, menus, md2 / hud / particle rendering is all there pretty much unmodified from cube and either already works, or can be easily be made to work again as sauerbraten progresses. This document assumes some familiarity with the original Cube source code. The major areas that are new have to do with world structure, like rendering, editing etc. A description of each follows: World Structure =============== The new world structure is the ultimate in elegance, if I may say so myself ;) "octa.h" contains the definition: the only data structure is the new struct "cube". a "cube" is the central component of Sauerbraten's octree structure (if you don't know octree's, google them and read some documents about them first). If a "cube" is a leaf, i.e. the smallest element that has been edited as a single cube at that level in the octree, the edges/faces fields define the shape of the cube using the aforementioned "edge spans". A cube has 12 edges, each having 1 edge span occupying 1 byte. The single byte is split in two 4bit quanties each storing a number between 0 and 8, the lower one being the start of the span, and the higher being the end of the span. A maximally exstended cube has all edge spans with value 0x80, by definition. A completely empty cube (space) can be defined in many different ways (all edges of 0x00, 0x11 .. 0x88), but as a convention only the value 0x00 is used to allow for fast testing. All current functions enforce this already. if a "cube" is not a leaf but is 8-fold subdivided, it has a pointer to its 8 children allocated as one chunk. The other fields of a non-leaf cube are meant to hold the LOD version of its children, but this is currently not implemented. note the lack of a "type" field in the "cube" struct: there is only one type of cube (unlike the 7 different types in the Cube engine). This greatly simplifies the code. It may take a while to wrap your head around the idea of edge spans and the way they are stored. Reading the algorithms that handle them should help. "octa.cpp" contains some of the basic functions of dealing with this structure. Particularly study lookupcube(), as it is the central function used by all other code to access the octree and to further subdivide it if needed. "worldio.cpp" works as before but now with the new world structure, "map" and "savemap" work as expected. World Rendering =============== "octarender.cpp" contains all functions that draw the octree & cubes to the screen. It consists of two parts: gencubeverts() and all the code above it takes the octree structure and turns it into a vertex array and index lists ready to be rendered. It currently does this for the entire level at once after a level load or edit, ideally it should be done for small parts of the level at a time (see below). This function cannot be called every frame (as it is in Cube) as it is quite expensive. The actual structure of the code is to take each cube, compute the 8 vertices for it by intersecting the 6 faces defined by the 12 edge spans (the intersection functions are in "geom.c"). It also attempts to cull unneeded faces such as those of equal size and touching eachother. The hashtable at the top is used to not put duplicate vertices in the array. This code is not easy to follow, but does a lot in very little code, so you will just have to read it to understand the details. As with everything in Cube/Sauerbraten :) octarender() and the 2 functions above it render the scene, and as you can see are super simple (after all the work done by gencubeverts()). It renders all quads using any particular texture together, and uses texgen for the texture coordinates (which makes the vertex array very small at just 16 bytes per vertex). World Editing ============= This part I was in the middle of programming when I had to suspend work on it, so contains the most bugs/unfinished parts and crappy code. How editing works is briefly explained in "readme_player_mapper.txt". Play with the editing functionality to get a feel of how it works. cursorupdate() is the main function that gets called every frame in edit mode to update the rectangle, and a dragged selection if there is one. editface() then implements the actual geometry modification with the mousewheel and the different key combinations. Again, not easy to follow code, but not a lot of it considering that it implements pretty much the entire set of editing operations. Thing to be implemented ======================= What follows is a list of items that would probably need to be implemented to make Sauerbraten into a fully usable engine. I have listed the items below roughly in the order which I think would be useful they would happen. Quite a few of the items can be worked on by different people without interfering too much, i.e. one person can work on rendering issues, one on editing, on on collision etc. - make the current editing features work in all situations (they currently work in some of the 6 orientations and not in others). - add texture selection feature (should be easy). Suggested is a "move to front" texture list much like Cube, that is saved with the map. Texture slots and texture loading is already in the engine just like Cube. Maybe later a fancy texture selection window can be added. - once the editing is fully working, remove the redundancy in the various editing related functions - currently only NV_VERTEX_ARRAY_RANGE is used to upload vertex arrays to video memory after the level changes. ATI_VERTEX_BUFFER_OBJECT and ARB_VERTEX_BUFFER_OBJECTS should also be supported. - collision detection. The physics dynamics sort of work from Cube, but there is no proper collision detection (there is an ad-hoc collision detection which treats the player as a "needle"). - currently the entire level is rendered into one big vertex array every time the level is loaded or edited. Not only is this very inefficient for editing, it doesn't allow frustrum culling and occlusion culling. The level should be split up at certain levels in the octree, depending on the number of nodes below it (i.e. a high detail area will result in smaller chunks and more split up than a low detail area). The target amount of cubes in a chunk should be tunable: large enough so that there are enough polys in it such that rendering it at once is efficient, and small enough so that culling algorithms are effective. To make this work with VAR and VBO, a simple memory manager should be implemented on top of the VAR or VBO which allocates parts of its memory for these chunks as needed. Once this works, frustrum culling should be implemented. Occlusion culling is more complicated and can be left for later. - lighting. Currently there is a provision for vertex lighting in the "cube" structure which is being filled with random values at the moment as you can see in the levels. The lighting model is debatable, but for the kind of engine Cube is, doing things like shadow volumes or shadow maps is probably not feasible yet, meaning that again some form of lightmap or subdivided vertex lighting must be used. I would suggest that for surfaces below a certain size only vertex light be used, and for the larger faces the engine accumulates lightdata in a series of lightmap textures as required (subdivision would probably be unwise given the potential scale sauerbraten worlds can have). - fix all those small little issues from the former cube gameplay code which stopped working (should not cost a lot of time). If all the above items are implemented, Sauerbraten should be able to run the old Cube multiplayer and singleplayer game without much problems, in much more impressive worlds! - occlusion culling. Will be quite complicated to do well, should be left as last item to do until all other parts of the engine are matured. Once we get to this point I'd be happy to help brainstorm on possible good algorithms. - many interesting features can be implemented beyond this point. We'll think of them once we get there :) Code style and simplicity ========================= Many people may work on this code, all with their own coding styles and coding philosophies. If everyone just goes their own way things will become a mess, and noone will be happy. Coding style is least problematic. It would be easiest if everyone just followed my style of formatting, identifiers etc. However if everyone agrees that they prefer a different style that would be fine too, as long the style is applied consistently (i.e. all old code is change to reflect the new style). One particular style I will forbid however, and that is the so-called "hungarian notation". Coding philosophy is a harder topic. I am however assuming that people working on sauerbraten do so because they like Cube and its minimalistic engine design, and are excited by the possibilities Sauebraten's new world structure brings. That means that they are people that can agree with Cube's coding philosophy and may enjoy working with it. Even though Cube's source code is not the prettiest (it is downright ugly in places), it overal VERY easy to read, which almost entirely due to its incredibly small size and simple algorithms. Lets face it, if you have to understand a physics system, there's no way you are going to easily find your way around a physics system that stretches 20 .cpp and .h files with several pages of code each (even if its wonderfully designed), compared to Cube's 1 or 2 pages in a single file (even if its ugly). Ever wonder why an engine that is simpler than Doom2 still gets so much attention in 2004? And why nobody appears to do anything with all those hundreds of advanced engine projects out there? its because of this kind of thing. Cube is about doing more with less (a lot less!) and Sauerbraten is no different. Its about elegant tiny algorithms, and using not a single line of code more than needed. I hope the programmers working on Sauerbraten will embrace this, and join in the fun "sport" that is simplicity, even if by their background they prefer to create collosal class hierarchies that include every version of the kitchen sink. A misconception is that Cube's code philosphy is "anti-OO". This is not relevant at all. I'd be happy for people to convert all of sauerbraten into a neat bunch of classes. The _form_ of the code does not matter, as long as its the minimal, simplest, least redundant one. The problem with classes as used by most people is that they require to split up a part of the code between .h and .cpp, and also invite people to get serious with data hiding, introducing the dreaded get/set methods. All of this introduces useless clutter that will bloat up the code size of an engine several fold for no gain other than being "correct". And readability for anyone except the original writer will suffer. If you want to create a class, I suggest you put it in a .h file in its entirety, improving readability immensely by keeping all code together. Really, the design of classes and the .h/.cpp idea don't work well together at all. Don't worry about executable code bloat by the appearent "inline" nature of this, most linkers have gotten very good at filtering this out nowadays. And unless you do the entire engine this way, you are not going to feel the compilations speed difference. And please forget about get/set. A small example is the "vec" class that is still a bunch of macros in the Cube code base. Important to notice is that it is still exactly the same amount of code as in Cube, however just a bit more readable than before. Another think people worry about is the use of global variables in the code, because global variables are certified evil (tm). But think of it: an engine intrinsically has some global data it needs to store. So you put all of this in a class (or classes). But this engine really only uses one instance of this class, so you make it a singleton. Now you need to access this data. You write get() methods, and you litter your code with calls to them. You have just bloated your code, made it less readable, and all for what? for no change in actual structure whatsoever. In cube, a .cpp file is often implicitly a "singleton" already. Don't worry too much about being Politically Correct, worry about the actual structure of the code. Doesn't all this hacking reduce maintainability? On the contrary. By keeping the code the simplest possible and accepting no redundancy, most modifications you want to make are simple because the code that is related to it is easy to isolate. Abstractions can be made when they are first really needed, rather than ahead of time and forgotten. So when you work on Sauerbraten, try taking these steps: - Make it a challenge thinking about the algorithm design before you start coding. What is the simplest thing that could possibly work? How can I make it such it requires less data structures or code, or simpler data structures and code? Don't think in terms of just getting features done. Just because all other engines make a certain feature look complex doesn't mean we have to follow. - Once you got a cool base idea, discuss with other Sauerbraten programmers. There will be a thread on the messageboard for this. Maybe they have further simplification ideas. - Implement using exactly the code needed to implement the algorithm without redundancy. Refrain from implementing any big "systems" or "managers" to help your cause. Make it a sport to be efficient with the amount of code your algorithm needs. - spend as much time refactoring as you can. If things get a bit messy, don't just let it become worse but take some time to restructure things. - Be careful to not implement tons of special purpose features that sound neat. Focus on features that have more universal power and can be used for a multitude of things. Once players/mappers start to use Sauerbraten, they will ask for endless features, most of them not very well thought out. Resist the temptation :) ========== Wouter van Oortmerssen wouter@fov120.com