A very long time passed since the last news. One reason had been me moving to a new place which took longer than expect. Then there had been lots of work too correlated to show by its own. And finaly but not least there had been some nasty incidents at ModDB where somebody with site moderator power (as it seems) vandalizing the profile of my project which I restored. Due to this incidents though I put a news ban on ModDB which had been in effect since somewhere the beginning of this year. In the mean time though a couple of people asked me to lift the ban. When I found a way to protect my work by reworking the Wiki to host the articles I decided to lift the ban as on my wiki my work is safe. I don't want to warm up this story more than I just did. Important now is only that ban is lifted. For me this incident is now a matter of the past and shall stay there. Let's move on to what is really important.
The Drag[en]gine Wiki has been completely overhauled. To help prepare for a future release of the game engine this wiki is turned into the SDK and first source of information. Hence it is made for the developers wishing to work with the game engine. Especially in light of the incidents that happened the wiki has been modified to hold also all the articles from now on. I'll now only make short bullet lists of what has happened linking to the wiki pages. No articles will be posted anymore on ModDB (on my wiki they can't be vandelized). The articles contain in depth details. It's really worth reading them if you want to know all over the Drag[en]gine.
Here the list of what happened during all these month. Click on the links for detailed articles about the topic:
It's time now for an overdue all important addition to the shader system to allow for even more power and versatility that I need to get that performance punch to crank up frame rates. My Radeon 4870 HD is not the youngest and most powerful graphic card anymore but I have the will to get the most punch out of it with my engine. Besides this I want to get the first mission into a playable state with first investigation work going on. A lot of the required engine work is done already. And that is the most time consuming part so far. Furthermore more articles will be moved one by one to the safety of the Wiki.
A bunch of other projects (especially in real life) got in the way of development so things slowed down a bit. Nevertheless another entry on the list of remaining tasks to do for the first engine release could be complete. Now I can head over to the rest of the entries on the list and these should hopefully not be that work intensive.
The particle system received a bunch of updates which I had on my list since some time. As a new trend I talked about recently I'm not going to write much here but instead show you over to the Particle Emitter Wiki Page containing detailed information. So here just a short list of what changed. See the Wiki page for explanation on what each of the changes does.
With this task gone the list of remaining tasks to release the engine is one less. Next step is adding the nodes support to animators and skins to add another layer of control for these cases where you want to do the really crazy and complex stuff. So stay tuned.
The last couple of weeks has been spent in the name of navigation. Many know this as Path Finding but correctly path finding is just one (albeit important) ingredient of the navigation problem. As always the Drag[en]gine takes a general approach in dealing with the navigation problem to allow all kinds of games to use it efficiently and painlessly.
I try to keep the technical details as short as possible here. Due to demand from watchers I'll try to add a more in depth documentation to the Wiki of the Drag[en]gine over time (maybe this summer if I get the time). This way you can see better how awesome this engine is (which is not so visible from summary type news posts).
As with other technical parts of the engine for anything related to AI an own module exists, the AI module. This module provides services required typically by AI routines like navigation support. Thus the player can choose the AI module on his own allowing to improve for example navigation easily. At the base the navigation system composes of two main components, the navigation mesh and the navigator.
To implement path finding various way exist but the typical ones are the navigation grid and the navigation mesh. Navigation Grids are often also used waypoint systems but covers many other scenarios like hexagonal fields on an RTS type game map and so forth. This can be imagined as a collection of Nodes connected with edges. Each node is a field or location an actor can be located at and each edge defies a valid transition from one location to another. Giving cost functions to edges the choice of path can is improved a lot. Cost functions define how costly it is to move along an edge. This way AI can be kept on fast traveling routes unless it is more favorable to treat through rough terrain. Combined with A* (the most common path finding algorithm) this yields a solid base but gets in troubles with complex scenarios or large open plains. For this reason Navigation Meshes have been invented. A navigation mesh augments the navigation grid in that they add a new dimension to it. The nodes are now faces while the valid transitions still are edges but this time between neighboring faces. This allows to cover the walkable space more precisely with less faces/nodes than using navigation grids. In contrary to navigation grids though the notion of cost functions for the edge is more difficult now. The Drag[en]gine solves though all of this for you.
In the Drag[en]gine all these navigation spaces are folded into one single object, the Navigation Mesh, as they are all similar to each other just with differing properties. Thus the navigation mesh object can hold at your wish navigation grids, navigation meshes or even navigation volumes. Navigation volumes are an extension on the navigation mesh in that they take it another dimension higher so now you have rooms as nodes which are connected by faces. Navigation volumes are currently not yet implemented. Cost functions are provided using a type value for node connections (for example faces). This can then be linked later on. Navigation meshes can be created any number and added/removed to the game world at any time. The AI module takes care of the rest for you. This allows to have for example navigation meshes for individual buildings and/or terrain segments which you can edit individually. This improves work flow and allows for reusable content (for example modular assets). Furthermore every navigation mesh has a layer value. All navigation meshes with the same layer value belong to the same search space. Hence you can have various navigation meshes for different types of AI in your game each using its own layer value.
While Navigation Meshes define the search space the Navigator objects define the search function. Every AI in the world typically maintains a personal navigator. As with navigation meshes the navigator has a layer value and thus only takes navigation meshes with the same layer value into account. You simply define the start and goal position and you get your path out as a list of path points. The neat trick on using navigators is that you can define cost functions per navigator (thus per AI if required). Remember the type numbers of navigation meshes? In a navigator you define a table of cost functions which is a mapping of type value to cost function. AIs can thus have individual navigation behavior (also dynamic at run-time). Cost functions consist of two values: fix cost and cost-per-meter. Simply put the final costs are:
costs = fixCost + costPerMeter * distance
Thus costs are a simple MAD and generic. For navigation grids fixCost would be non-0 while in navigation meshes costPerMeter is non-0. Distance is the length of the path segment traveled inside a face. This yields a good cost function for navigation meshes which usually lack a useful cost function in other engines.
The current AI module uses for path finding the A* algorithm using the outlined cost functions. While A* is works well the resulting path would not be very good as it runs along the center of the faces. To deal with this the String-Pulling is used. String-pulling is the name for a technique where the A* path is pulled at the ends to make it fit tightly around scene geometry. Various solutions exist for this too but a well known one is the Funnel Algorithm. http://www.navpower.com/gdc2006_miles_david_pathplanning.ppt contains an explanation of the algorithm (look for the next corner point slide). This results in a tight path as shown here: http://dragengine.rptd.ch/articles/navigation/navmesh_pathfind_1.png. Unfortunately the funnel algorithm fails in various situations as it is lacking as you can see here (left image base funnel algorithm, right image how it should be): http://dragengine.rptd.ch/articles/navigation/navmesh_pathfind_3.png. Some projects like Recast tip-toe around the problem by introducing ray-casting (can be slow) and thus is not suitable for a generic solution. I've done now some modifications to the algorithm to catch the problems while retaining the speed advantages of the funnel algorithm. The result is now a properly working and fast calculated path.
On the game side a bunch of additional classes have been implemented namely the ActorAI class. This works similar to the PlayerActions class but for AI purpose. Implemented there a basic Move-To type AI to show how the navigation works. Hence you can just say where you want to go and the code does the rest for you. To finish this news post here a test-run where I send the actor down to the back entrance and from there back up again.
ModDB: Video "Navigation Test"
More details hopefully in the Wiki later on.
More work on the game script side of AI handling especially adding real collision avoidance as well as improving on objects dynamically blocking things (blocker memory and so forth).
This news post gives amongst others some insights into the art of efficient culling and how the Drag[en]gine deals with this situations.
You can not build a high class game engine rendering wise without having to deal with culling in one way or the other. Although the computers of today are powerful they are still unable to render complex scenes at acceptable frame rate and will not be able to do so for quite some time. The limitations are actually much lower than one might expect. To cope with this problem Culling is used. In a nutshell culling values the old Graphic programmer wisdom "the fastest objects to render are those you don't render at all". As simple as it sounds this is one of the most tricky challenges in graphics programming. While for a human it is rather simply to judge if something is visible from his point of view it is an expensive operation to do so for a computer.
Different commercial engines developed different solutions for handling culling. Each technique though works mostly for either indoor scenes or outdoor scenes but no method works well for both. In the past game developers cheated around this problem by limiting their games to either outdoor or indoor and using various game mechanic hacks to hide the transition like for example entering a house or cave in Oblivion. Another problem are static and dynamic environments. Many methods only work on static environments but with games getting more dynamic new solutions are required.
In the course of the last couple of weeks I spend quite some time transporting over the old culling system from the Terrain system to the pure Component system and at the same time added quite some improvements. So here a little insight in the culling in the Drag[en]gine Game Engine which.
It is astonishing how many small projects forget the very basic idea of frustum culling. Yet it's one of the most important steps. What many don't know is that objects outside the view do reduce render speed a lot. Although the graphic card does prevent rendering them outside the view it has to do a lot of calculations to figure out that all faces of an object are actually invisible. So the first step is to build a view frustum and to test objects against it. A View Frustum is a pyramid representing the view of the camera with the camera at the tip of the pyramid looking down at the base of it. Rejecting objects by testing them against the frustum is nice but there is a catch. This test by itself is CPU hungry especially for triangles. The game engine therefore rejects entire objects by testing their boundary instead of each triangle. Even then though it is not fast if you have a complex scene. Another step is required. (frustum culling has been in the game engine since the very beginning).
To the rescue comes octrees. An Octree is a rather interesting spatial data structure. An octree encloses a box shaped piece of space. This space is split up into 8 octants which each can be a smaller octree totally filling this space. As you can imagine this box-in-box structure grows like a tree splitting up your game world into nested boxes of various size. Objects are then inserted into the smallest box which entirely holds the object. An octree exposes two interesting properties. First if an octree box is invisible all objects in this box are invisible. The inverse is though not always true but that's not so important. The second property is that since every sub-octree is fully contained inside an octree octant if such an octree octant is invisible the entire octree below it is invisible. As you can imagine you can skip large chunks of your game world by testing the octree from the top down to the leaves. Actually determining the rough visibility using an octree is the most used solution and works fast and provides a good culling. (octree culling has been in the engine since the very beginning). Now is this the solution? Unfortunately not. Octrees can only help to figure out what is potentially in your view of view but it fails to figure out if objects are for example hidden behind a wall. But exactly these missed culling opportunities cost a large amount of speed. More solutions are required to get an acceptable speed.
In early games Portal Systems have been invented. The basic idea is simple. You take your game world and you split it into convex rooms connected by walls and portals. Later on you can test your view frustum against this portal system to figure out which rooms you see. All objects in invisible rooms are then for sure invisible. Back then this technique worked well since game worlds had not many triangles. This had been the case because portal systems had been generated by a program (qvis for example). The walls of the game world are used to split the world into rooms. Obviously the more complex the world gets the higher the pre-processing time is going to be as well as the amount of data produced skyrockets. Conventional portal systems quickly hit their limits turning them unusable for a game with todays standards unless a world is artificially limited in complexity of developers forced to place manual portals. Another problem is that due to the convex nature of portals they only work well for indoor scenes. For outdoor scenes they are hell. Since the Drag[en]gine though is supposed to allow seamless transition between outdoor and indoor conventional portal systems had not been an option... "conventional" ones that is. Some might remember an old news-post where I talked about a portal system. I stepped the system up a bit.
So how can a portal system be actually turned usable for todays games? The solution is to get away from generated portal systems as well as using one portal system per game world. No matter how well your portal system generator is they can never produce optimal solutions since they lack an understanding of the map geometry the mapper does have. Let's take the ISG HQ building from the game. This building composes of 4 floors with two wings each one hosting 15+ rooms as well as a stairs area in the center where you can look down and up between all floors. This is a challenge for a portal system since the shape is highly irregular and holes provide problems with the convex nature of generators. To overcome these problems I went ahead and implemented a manual portal system object. What happens is that the mapper can now create alongside his building a portal system mesh in Blender.
I can hear now a lot scream "Help, this is complicate and time consuming!". You are right if you try to make a portal system as the ones generated by a generator application. The trick is though something else. If you look at the room above you'll notice that the portal system mesh is utterly crude. A room is more or less just a box. But exactly this crudeness is the clue. It doesn't matter if you have for example a room or hallway with tons of pillars or objects inside. All this does not change the basic visibility. Everything inside the room is in general visible. Also everything outside the rooms is in general invisible. For a mapper it is quite clear how the "logic visibility" of your map looks like as you tend to design rooms. All you have to do is placing a portal system wall in the middle of a wall segment no matter how this wall actually looks like. A crude approximation of the visibility is more than enough to fulfill the culling requirements. Another problem is the convex nature of portal system rooms. In the existing systems rooms have to be convex. This is tricky to handle manually and produces a large number of rooms and portals. To counter this problem portal system rooms in the Drag[en]gine are allowed to be concave. Using some clever math this relaxation of existing portal systems can be used to reduce the required complexity of portal system. Creating such a mesh takes no time for most cases. In this example the ISG HQ mesh contains over 40k triangles not counting door and various other props. The portal system mesh for the entire building as shown above ranges in at less than 3k faces. In most cases this mesh is even much simpler. A complex underground lab with more than 100k triangles can easily be befitted with a portal mesh of less than 2k faces. It takes therefore very little time to create this additional mesh but the speed gain is tremendous.
Here an example view of the ISG HQ. I am standing here in the hallway of the left wing (right on the image) on the first floor looking towards the stairs area and the right wing. The culling has been disabled so no portal system magic is done. As you can see the amount of objects in my view is tremendous. Lots of wasted work and slow frame rate.
The same situation as above but now the portal system culling is enabled. The amount of visible object dwindled a lot down to a number that can be easily rendered. The good thing here is that this kind of visibility detection works also for light shadow calculation reducing shadow rendering costs a lot. There is also another nice property of the portal system in the Drag[en]gine. You can use as many portal systems as you want in your maps. Typically though you use one for each major building. The engine is able to use multiple portal systems to produce a proper result. This allows the mapper to create the portal system and to change the mesh later on without having to worry about updating the portal system unless the visibility changes significantly. As a result the implemented portal system here runs at top speed without any pre-processing time required while being simply to produce by hand. But there is more possible.
Objects outside portal systems are always visible. To deal with them occluders can be used. The idea of Occluders is rather old. In general this is a rectangular shape which blocks the view. They have been used in early games on landscapes to block the view of the player for example through mountains. In the Drag[en]gine occluders are available as an additional trick to cull objects. The mapper can place these shapes manually in the map if he wants to give a hint about visibility. The Drag[en]gine simply tests objects against these occluders. This is the last test which happens on the CPU side and can remove objects on landscapes for example behind a mountain or cliffs. The Drag[en]gine knows occluders since a couple of month. There is though a last trick that can be played out.
In the recent years a new technique arrived in the mass market of graphic cards, the "Occlusion Query". This is an OpenGL extension that allows to test how many pixels an object drawn on the screen affects. In short this counts the amount of object pixels that are in front of whatever is rendered already. This extension can be used to render a box (without actually rendering to the screen) around an object checking if any pixels would be visible. If invisible the query would return 0 as no pixel is in front of any existing pixel. While this might sound like the solution for culling it has a performance problem. It requires reading informations "from" the graphic card and this is slow to state it friendly. Using them though in moderate numbers and interleaving them smart with the rest of rendering they can be of benefit. While the CPU culling methods potentially miss these opportunities the Occlusion Query is able to detect them. Due to the CPU culling methods only a small number of objects has to be tested using a GPU Occlusion Query. In the Drag[en]gine these are lights and complex objects. They are costly enough to justify using an extra test as skipping them helps a lot.
All these methods are used now in the Drag[en]gine to provide efficient culling for both objects in your view as well as objects casting shadows for lights. Paired with the double-shadow approach of light sources as mentioned in an earlier news post the render speed has now been improved significantly. It is now possible to render a complex building lit by a sky light with 4-texture shadows as well as 10+ static and dynamic shadow casting lights in between 30-60 fps on a Radeon HD 4870 class hardware (fully running game). There is though still room for more optimizations. But that's to be left for another news post.
Besides these rendering optimizations a bit of time had been left for other things too. One of them is the first implementation of the new texture property "reflectivity". This property defines how much a surface reflects the environment. These two screen shots give an example of how this looks like on the ISG HQ viewn by day and night. As you can see the reflection is dynamic and properly reflects the current sky configuration. The engine takes care of all so just adding this texture property to your skins is enough to get the effect.
Getting these optimizations working like they do now had been on my agenda for quite some time. There's room for improvement but the results are promising. So stay tuned for the next time.
What use would a good game engine be without a good front-end? Not that funny to use for common gamers. This update sheds some first light on the front-end part.
Most work went this time into the GUI launcher for the games. This included especially a long overdue redesign of the compilation process on Windows. Due to a bug in windows (infamous 32k command limit on CreateProcess) compilation using SCons and MinGW resulted in problems. Various hacks and improvements on the build scripts allow now the entire game engine, the IGDE and the launchers to build also properly on Windows 32bit and 64bit (Linux 32bit and 64bit always worked).
So what does the GUI launcher provide? Another Desura or Steam? Not exactly. The GUI launcher provides a one-spot solution to install, run and tune games build for this engine. This is the main difference between the Drag[en]gine GUI Launcher and Desura or Steam. It is designed to handle games build on this engine and nothing else. This is required since applications like Desura do not want to deal with the complexity involved handling this game engine. This is where the Launcher comes into play.
Currently the launcher supports running games as well as some basic fine tuning support. Games are not required to be installed using the Launcher as long as they install their Game File into the proper directory. This directory is global for all launchers. Using this principle you can use whatever launcher you want for your Drag[en]gine based games. Once installed the games can be run from the launcher like you know it from applications like Desura or Steam so just double click and get going.
The interesting part though is the fine tuning part. The common player does not worry about those and can just run the games on his machine. For power gamers though the tuning system allows to get the most out of your games if you are willing to turn some skrews. For this the launcher supports Game Profiles. Game profiles can be created globally for all games as well as individually for each game. You can define which profile a game uses by default so once you got a nice tuning starting a game uses this profile. You can though run a game any time by selecting explicitely a different profile. This can be useful for testing while creating a game or using alternate profiles like a "no sound" profile or a "window mode" profile or maybe a "capture video" profile and so forth. The most important choice you can make for each profile is which Engine Modules you want to use for running a game. A simple example would be to have one profile with OpenAL as sound module while another use NullAudio. Obviously the later one would provide a silent game which can be useful for certain games or if your boss is not supposed to know you are gaming instead of working :D . Furthermore every module in the engine provides a list of Module Properties. For each profile you can define which property values to set. All property values you do not set in a profile use the default values. In the screenshot below two sample screens are included giving an idea on how this looks like. Using this system you can tune your games the way you see fit. For the lazy ones the launcher provides a default profile which includes the best matching modules for your machine. Specifying no profile uses this default profile.
The entire engine as well as running games is handled in separate processes so no matter if the game fails for some reason (either due to scripting errors while modding or due to a crash in an experimental engine module) the launcher stays alive all time. You can also kill a running game if you managed to get it stuck for some reason. Something which is useful that other game frontends often lack. Each game can be run only once. Support for running more than one instance of a game in parallel can be added later on if this is desires. For most games though more than one instance does not make much sense.
The GUI Launcher is not finished and requires more work. Installing games as well as uninstalling games is not yet implemented. Also the module rating and optimal profile generation is not yet implemented. This requires some additional engine stuff to work first. Updating is also not yet included. This will later on be included when the engine turned into a releasable state. Last but not least the GUI is currently made to be functional but not yet esthetic. A nice look will be added later on. Important at the time being is the functionality.
One of the larger construction sides remaining had been the logging part. So far everything from the engine over modules to launchers used printf for logging and that's ugly to work with in the long run. The other half of the work this time went into building a proper logging system which is not only simple to use but also versatile and efficient to use. For this a bunch of logger classes have been created. These are organized in a hierarchy so you can use any combination of color-console logging, file logging and custom logging depending on your needs. For games running through the launcher log files will be written using a file logger to a separate log file for each game. All other log messages are written using a file and a GUI logger. This way the important logging informations about the launcher can be viewn in a separate window. Overall logging is now proper and works similar on all supported platforms.
File Hierarchy Clean-Up
This may sound now not like news worthy but it actually good news for Windows 7 users. Windows 7 has rather restrictive ideas about which files are allowed to be stored where getting in the way with a complex engine system as the Drag[en]gine is using. The IGDE and the Launcher have now been modified to conform also with the restrictive file hierarchy requirements of Windows 7.
With this work out of the way the next steps can be taken care of including Environment Mapping which works already but more about that later.