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.
The design of the actor classes has been reworked and improved. So far various classes for the different actors existed to test the individual features. These features have now been collapsed into reusable base classes HumanActor and DragonActor. This way adding new features and characters is easier.
This includes also the dragon locomotion system which has been added to the game scripts similar to the one used in the animator editor during development. The locomotion system still has troubles and needs more work but the basic pieces are in place. To handle turning better collision detection has been augmented with some additional code to allow testing for rotation collisions. The code is currently still a hack as the bullet physics is supposed to take over this job later on (still a few problems in the way hence the hack is still in place). What does this mean now for the movement of the player? The main problem with dragon characters is that they are not rotation independent viewn from above. If you do not want to go through narrow places this is not important and a large cylinder can be used. For this game though the dragon actors have to be able to also get through narrower places. For this the rotation has to be taken into consideration. The way it is implemented right now before each motion the actor is checked for hitting geometry using rotation. The rotation is then blocked if a wall is hit. Doing the check like this allows a player to squeeze against walls and getting away from them easily. This system still has room for improvement though. Getting through doors still requires some aiming. That said this is not that bad though as a dragon in a narrow places would have troubles to maneuver in the real world anyways.
Video on ModDB, Video on YouTuve
There exists an idea for doing a different kind of rotation testing which does not require actual rotation testing. Rotation testing is a nuisance and difficult to handle. This idea would require some unusual handling of the dragon character to work but it should be much more stable and less error prone. This will be tested in the time to come to see if it works better. Most important is that it fells well for the player to navigate.
A trigger system has been added which works similar to existing trigger systems in other games. In this game there is triggering and connecting. Certain objects can be linked to others using named targets. Linking objects requires the two objects to know about the type of each other. This is useful for certain cases but not for others. For example this does not work well for generic triggering like switching on and of a light source or triggering generic actions when an entity enters some location. To handle this triggering has been added.
Triggering works rather simple in that a trigger expression can be specified for "trigger*" type object properties. For example a light source has a property "triggerActivate". This defines an expression to be evaluated and the light is activated if the expression evaluates to true or false otherwise. A trigger expression composes of trigger names, modifiers and logic operators. Modifiers can negate (!) a trigger (hence return true if a trigger is not fired) or refer to the current state (@) instead of the global state. Triggers always store two states. The global state indicates if the trigger has ever been fired while the current state indicates if the trigger is currently in the fired state or not. Depending on what kind of trigger action you want to use either of the two can be useful. Logic operators exist two, the and (&) and or (|) operator. Parenthesis can be used to group sub expressions. So for example an trigger expression could look like this:
(@trigPlayerInArea & !trigActionA) | trigActionB
This would fire if either the player is currently in a trigger zone named trigPlayerInArea and trigActionA never fired so far or if trigActionB fired sometime earlier. This system is rather simple and allows to trigger objects which have no idea about the type of each other. Objects can have more than one trigger expression affecting different actions. So for example a door can have "triggerOpen" and "triggerLocked" both with their own trigger expressions. The door would therefore only open if both triggers are true. Granted you could do this like "triggerOpenExpression && triggerLockedExpression" in this particular case too but it can happen that a door turned locked due to scripted means not using a trigger expression. Hence multiple trigger targets are possible allowing to combine the two worlds for a lot more flexibility.
In general the Trigger System is an addition to the Connection System. Combining the two allows for very dynamic game scenarios difficult (or even impossible) to do with other game engines.
The last news post in the big news pack is going to deal with the new map geometry in general and launcher improvements. You've seen already a bit of the geometry in the preceding news posts. This one though is going to show more.
Engine Profile
Engine Profile