The other day, someone had asked me how long it took to recompile the entire Elpis solution. As far as I could remember, this was around 1 minute, but when was the last time I did a full recompile and watched it? My habit is to do something online or to get some food when something will take a while, so it is likely that my assumption was wrong.
So, I enabled build timings in VS, started a full recompile and got myself a snack. Upon returning a few minutes later, I was disgusted to see that it was still compiling! After it was done, I recompiled a few more times and averaged the recompile time to around 4 minutes.
Problems
The first problem was caused by languidness towards header structure and inclusion. One of Elpis' main header files was being included by a large majority of the headers and source files across all projects. This header happened to include the entirety of the DXUT framework, several major boost headers and quite a few other things. Convenient, but dirty.
The second problem had to do with class' being fully defined within their header, rather than within the source file.
Solutions
The first and second problems could easily have been corrected during development, but I was foolish and allowed it to accrue into the devastating creature it had become.
The solution to the first was to divide the mega-all-encompassing header into several categorized headers and to be careful that the heavy headers were only included when needed (a basic rule I've been ignoring for too long).
The solution to the second problem was to simply move definitions to the appropriate source files where possible.
Worth it?
After all of this, compile time had improved to approximately 1 minute. A last optimization was done to some of the large projects that get updated frequently, and that was to use precompiled headers. A feature I've never taken advantage of. This reduced full recompile time to ~40 seconds for the entire solution. Pre-compiled headers will be a big bonus in the long run, since the solution compile time is a tiny fraction of the original time.
There are plenty of other opportunities to improve the compile time in Elpis, but full recompiles have been rare. Each project now takes, on average, 5 seconds to fully recompile. Until I fully adopt TDD, or full recompiles become the norm, I'll be more than happy with my improved compile times.
Friday, April 29, 2011
Thursday, March 24, 2011
Script-in-waiting
In my previous post, I mentioned a flaw with the interaction between Elpis and it's Lua scripts. The issue consisted of an application 'stall' while using sleep/wait functions in Lua. Looking at how Lua scripts are being called from the C++ side of things, it becomes obvious why this was happening.
If a script used a wait function, the screen would not update until it was over, because scene drawing was waiting for the script to end.
The quick work-around I had used in "Oh BeeHive!" was to tell Elpis to run a line of script in x amount time and let Elpis take care of the delays each frame. A global script function had to be made available to call from Elpis. A rather poor excuse for a wait function if you ask me.
A Modified Design
A good implementation of sleep or wait might be used something like this:
My first idea was to have all scripts running in an individual thread, but reading around the Lua manuals, another method was introduced to me.
If a script could be paused mid execution, it would be possible to start a script, let it pause if it wants, and resume it on the next frame update. This would allow the above script to pause the script until 1000 milliseconds has elapsed without freezing the game. Of course, this will not be a high-performance timer, since it relies on frame rate, but this should do fine for the games I will be developing. A plus side to this way over a script thread at this point, is that Elpis' architecture doesn't need many changes. Being a lone dev with few hours to spare... a plus indeed!
Enter Lua Coroutines! These little guys let you pause scripts and resume them later, as described earlier. Here is the method I use now to execute a function with coroutines:
When a script function is called from Elpis, a new coroutine is created, arguments are pushed onto it's new stack and the function is called using 'lua_resume'. If the Cfunction yield is called from the script, the coroutine is paused and stored in a list to be resumed on the next frame update. Once a function is completed, the return values are collected to the stack and a callback is executed to inform the caller that the function is complete. This callback event carries the return values with it.
The CFunction LuaYield looks like this:
In lua, the wait function might look something like this:
Issues Encountered
While testing out this new design, lua_newthread crashed intermittently. After a small bout of investigation, I discovered that the issue was being caused by a stack overload. New threads are pushed onto the stack, and in many cases this would be handled by the Lua Garbage Collector (GC), though this did not seem to be sufficient in this implementation. To solve this, I used luaL_ref and luaL_unref at key moments during the thread's life.
luaL_ref pops the top item off the stack (getting rid of it before it gets buried) and returns a unique integer reference key (so we can get rid of it later). Having a reference to the thread keeps the garbage collector from mistakenly destroying it before it's time. I store both the lua_State* and the reference key until it's time to kill the coroutine. At which point, luaL_unref is called to let the GC know it's safe to be rid of this thread.
 |
| Figure - 0 |
The quick work-around I had used in "Oh BeeHive!" was to tell Elpis to run a line of script in x amount time and let Elpis take care of the delays each frame. A global script function had to be made available to call from Elpis. A rather poor excuse for a wait function if you ask me.
A Modified Design
A good implementation of sleep or wait might be used something like this:
function Character:Attack(target) ... while(target:IsAlive()) do self:FireAt(target); wait(1000) -- 1 second reload time end ... end
My first idea was to have all scripts running in an individual thread, but reading around the Lua manuals, another method was introduced to me.
If a script could be paused mid execution, it would be possible to start a script, let it pause if it wants, and resume it on the next frame update. This would allow the above script to pause the script until 1000 milliseconds has elapsed without freezing the game. Of course, this will not be a high-performance timer, since it relies on frame rate, but this should do fine for the games I will be developing. A plus side to this way over a script thread at this point, is that Elpis' architecture doesn't need many changes. Being a lone dev with few hours to spare... a plus indeed!
Enter Lua Coroutines! These little guys let you pause scripts and resume them later, as described earlier. Here is the method I use now to execute a function with coroutines:
void ExecuteFunction(std::string const& _func, script_argList const& _args)
{
//Create a new thread and pop store a reference to it
lua_State* pState = lua_newthread(m_lua.get_state());
int refKey = luaL_ref(m_lua.get_state(), LUA_REGISTRYINDEX);
//Get the function (pushing it onto the stack)
lua_getglobal(pState, _func.c_str());
PushArgsToState(pState, _args);
//Start/Resume the funciton call
int res = lua_resume(pState, _args.size());
if(res == LUA_YIELD)
{
// Save the coroutine info for the next frame update
AddYieldingCoroutine(pState, refKey, _func, _args);
// Pop the function from the stack
lua_pop(pState, 1);
}
else if(res)
{
Log(m_lua.GetLatestError(pState));
}
else
{
// Function complete, get returned values
script_argList returnResults;
GetReturnResults(pState, returnResults);
EventSystem.FunctionExecutionCompleted.invoke(_func, returnResults);
// Unreference the thread, allowing the GC to get rid of it at it's leisure
luaL_unref(m_lua.get_state(), LUA_REGISTRYINDEX, refKey);
}
}
When a script function is called from Elpis, a new coroutine is created, arguments are pushed onto it's new stack and the function is called using 'lua_resume'. If the Cfunction yield is called from the script, the coroutine is paused and stored in a list to be resumed on the next frame update. Once a function is completed, the return values are collected to the stack and a callback is executed to inform the caller that the function is complete. This callback event carries the return values with it.
The CFunction LuaYield looks like this:
int LuaYield(lua_State* L)
{
return lua_yield(L, 1);
}
In lua, the wait function might look something like this:
function wait(duration)
local totalElapsed = 0;
local elapsedTime = GetFrameElapsedTime();
if(elapsedTime ~= nil) then
while(totalElapsed <= duration) do
elapsedTime = GetFrameElapsedTime();
totalElapsed = totalElapsed + elapsedTime;
LuaYield(); --Call CFunction LuaYield
end
end
end
Issues Encountered
While testing out this new design, lua_newthread crashed intermittently. After a small bout of investigation, I discovered that the issue was being caused by a stack overload. New threads are pushed onto the stack, and in many cases this would be handled by the Lua Garbage Collector (GC), though this did not seem to be sufficient in this implementation. To solve this, I used luaL_ref and luaL_unref at key moments during the thread's life.
lua_State* pState = lua_newthread(m_lua.get_state()); int refKey = luaL_ref(m_lua.get_state(), LUA_REGISTRYINDEX);
luaL_ref pops the top item off the stack (getting rid of it before it gets buried) and returns a unique integer reference key (so we can get rid of it later). Having a reference to the thread keeps the garbage collector from mistakenly destroying it before it's time. I store both the lua_State* and the reference key until it's time to kill the coroutine. At which point, luaL_unref is called to let the GC know it's safe to be rid of this thread.
luaL_unref(m_lua.get_state(), LUA_REGISTRYINDEX, refKey);
Tuesday, March 8, 2011
Oh BeHive!
During my adventures adding features to Elpis, I sidetracked and made a small game...a themed Connect 4 clone. This is a work in progress, and the graphics are all programmer art. A download link is provided at the bottom of this post.
The idea was to make a small game and hopefully discover some of the flaws in the design of the engine... Success! I have discovered flaws! For instance, using 'sleep' in the script will freeze the game until the wait is over. For now, I am using an ugly recursive 'delay' that is just too terrible to describe (if you're curious though, the lua code can be viewed in the download. Oh, and to protect my pride: I want those who will look at the code to know that it is prototypical, so much of it is untammed)
The Game
A strange mutation in honey bees has surfaced. These bees create an anti-honey, poisonous to the honeybees we know and ... love?
The mutant bee queen, unable to accept her mutation, intends to destroy that which serves as a reminder of her disability. She will stop at nothing to destroy the honeybees.
The honeybees have but one defense: Pure honey. Putrid to the mutants, the honeybees can amass large quantities of honey to defend their hives.
Controls:
The idea was to make a small game and hopefully discover some of the flaws in the design of the engine... Success! I have discovered flaws! For instance, using 'sleep' in the script will freeze the game until the wait is over. For now, I am using an ugly recursive 'delay' that is just too terrible to describe (if you're curious though, the lua code can be viewed in the download. Oh, and to protect my pride: I want those who will look at the code to know that it is prototypical, so much of it is untammed)
The Game
A strange mutation in honey bees has surfaced. These bees create an anti-honey, poisonous to the honeybees we know and ... love?
The mutant bee queen, unable to accept her mutation, intends to destroy that which serves as a reminder of her disability. She will stop at nothing to destroy the honeybees.
The honeybees have but one defense: Pure honey. Putrid to the mutants, the honeybees can amass large quantities of honey to defend their hives.
Controls:
- Left/Right - Move the new honey tile
- Space - Drop the honey tile
- Connect 4 of your honey tiles or anti-honey tiles to dominate the hive (vertically, horizontally or diagonally)
- Winning a round grants you a point and removes a point from the other player (the hive bar at the top represents the power struggle)
- If a player reaches 8 points, he is declared the winner
Download
Sunday, February 27, 2011
The Predecessor
This is a project I had started while I was in college. It's a level editor for my first "game engine" (before I knew what an engine should look like).
It had begun as a personal project during the summer, and some of my peers had joined in to use it as a group project. After the project had been submitted and graded, I continued to add features to it.
In the video, you'll see me load a terrain from a heightmap and set it's textures, set up some simple lighting, add a few objects (some with key frame animations) and move them around, and play a bit with some water settings.
Friday, February 11, 2011
The Hills Are Alive! (Outdoor Terrain)
This week, I thought I'd talk about the terrain in Elpis. I like terrain! Terrain is nice!
Also, an afore warning: this post is likely to transform into a musical featuring Julie Andrews...
Implementation of Choice
The terrain implementation in Elpis can be found in an article in Game Programming Gems 6, titled "GPU Terrain Rendering" by Harald Vistnes (Chapter 5.5). Seeing as the article in the book articulates the technique far better than I could, I will not be describing the method in detail. I will, however, skim over the implementation and record any modifications I plan to make and eventually how I intend to make them.
The general idea behind this algorithm is to provide a high detailed terrain while keeping memory and CPU requirements low, and pre-load time to a minimum. To do this, a small regular grid vertex buffer is repeatedly scaled according to the LoD (Level of Detail), morphed on the GPU according to the heightmap, positioned, and drawn.
The single vertex buffer used contains a 17x17 patch of vertices. As seen in figure 0, each patch of the terrain is divided into four more patches, which have been scaled to half the width and height. The division is essentially a quadtree.
The denser areas in figure 0 are one level of detail higher than the patch of lower density.
Also, an afore warning: this post is likely to transform into a musical featuring Julie Andrews...
Implementation of Choice
The terrain implementation in Elpis can be found in an article in Game Programming Gems 6, titled "GPU Terrain Rendering" by Harald Vistnes (Chapter 5.5). Seeing as the article in the book articulates the technique far better than I could, I will not be describing the method in detail. I will, however, skim over the implementation and record any modifications I plan to make and eventually how I intend to make them.
The general idea behind this algorithm is to provide a high detailed terrain while keeping memory and CPU requirements low, and pre-load time to a minimum. To do this, a small regular grid vertex buffer is repeatedly scaled according to the LoD (Level of Detail), morphed on the GPU according to the heightmap, positioned, and drawn.
 |
| Figure 0 - 17x7 LoD/Quadtree |
The denser areas in figure 0 are one level of detail higher than the patch of lower density.
|
|
The heightmap and normal map used for the terrain in figure 1 and 2 were borrowed from Game Programming Gems 6's CD-ROM.
Figure 1 shows the terrain in solid render mode and figure 2 is rendered in wireframe mode. In figure 2 we can see that it is a regular grid terrain implementation and there is a clear separation between terrain patches. Along the edges of each patch, skirts are generated to cheaply and effectively eliminate cracks that occur when mixing LoDs.
Feature Lust
It is a very good terrain rendering algorithm, but the article was kept intentionally simple and featureless for ease of comprehension. For instance: it is rendered in a single (kind of ugly) colour; lighting is static; culling is minimal; and other lacking features that I can't think of right now, or that I'll describe later.
Figure 1 shows the terrain in solid render mode and figure 2 is rendered in wireframe mode. In figure 2 we can see that it is a regular grid terrain implementation and there is a clear separation between terrain patches. Along the edges of each patch, skirts are generated to cheaply and effectively eliminate cracks that occur when mixing LoDs.
Feature Lust
It is a very good terrain rendering algorithm, but the article was kept intentionally simple and featureless for ease of comprehension. For instance: it is rendered in a single (kind of ugly) colour; lighting is static; culling is minimal; and other lacking features that I can't think of right now, or that I'll describe later.
Ah yes, here's another! In figure 3, the bounding boxes for a single LoD are displayed. It's plain to see that the bounding volumes were calculated using the minimum and maximum height of the entire terrain (since they are all identical in size and align at the top), rather than that of the patch's height. In fact, the implementation uses the minimum (0) and maximum ALLOWED height (1 * MAX_HEIGHT). The bounding box is currently used for frustum culling, but can later be used for other things like collision detection.
The point of frustum culling is to cut out unseen data as early as possible, to avoid unnecessary GPU work. The tighter the fit of the bounding volumes, the more accurate the incision will be, the fewer useless draw calls are made.
Summary of feature lust: I want sweet colours and textures, fancy dynamic lighting and shading, tighter bounding volumes for frustum culling, and maybe some occlusion culling if necessary. It would also be nice to use displacement maps for terrain morphing, but I haven't a use for this yet.
Exit
You can expect posts regarding the features mentioned above to pop up every now and again. My next post will be of a more immediate feature that I have made reference to in my first post: Large world support.
Here's a small clip of the terrain in wireframe mode to show the changes in LoD:
 |
| Figure 3 - Bounding Boxes |
Ah yes, here's another! In figure 3, the bounding boxes for a single LoD are displayed. It's plain to see that the bounding volumes were calculated using the minimum and maximum height of the entire terrain (since they are all identical in size and align at the top), rather than that of the patch's height. In fact, the implementation uses the minimum (0) and maximum ALLOWED height (1 * MAX_HEIGHT). The bounding box is currently used for frustum culling, but can later be used for other things like collision detection.
The point of frustum culling is to cut out unseen data as early as possible, to avoid unnecessary GPU work. The tighter the fit of the bounding volumes, the more accurate the incision will be, the fewer useless draw calls are made.
Summary of feature lust: I want sweet colours and textures, fancy dynamic lighting and shading, tighter bounding volumes for frustum culling, and maybe some occlusion culling if necessary. It would also be nice to use displacement maps for terrain morphing, but I haven't a use for this yet.
Exit
You can expect posts regarding the features mentioned above to pop up every now and again. My next post will be of a more immediate feature that I have made reference to in my first post: Large world support.
Here's a small clip of the terrain in wireframe mode to show the changes in LoD:
Friday, February 4, 2011
First thing I gotta do is ... Oooo, a distraction! ... Where was I?
Having a full time job and a 2 hour commute eats at your time and soul, but with the little time and energy you have left, you'd really like to build a game from scratch (for learning purposes as much as pride). A huge task by anyone's standards. So to get the most out of your time and to keep you from being reminded that there's a world outside, you'll need to do away with all them distractions and get some clairvoyance spells... or something. But enough about you, let's talk about me!
First thing's first: If this kinda-too-large-for-one-person project is going to succeed, I need to be the project manager, designer, director and hero (coder). Oh, and I need to cut the reddit feed from my iGoogle page before I hurt myself. [+3 productivity].
To keep me from hating life, I like to squeeze in some gaming and reading into my week [+4 happy].
I can read novels during my bus ride commute to work (and thanks to ebook readers, I can read any sloppy romance novel I please without the judging glares of those who sit near me!).
Since I must, I've allocated a small portion of time to the habits that make me go 'huh? where did the time go?!' (ie. Facebook, Reddit/Digg/etc...), but one of my eyes is fixated on the clock at all times.
Break it down! (-stop, Hammer time) [+4 focus]:
Happiness + 7
Productivity + 7
First thing's first: If this kinda-too-large-for-one-person project is going to succeed, I need to be the project manager, designer, director and hero (coder). Oh, and I need to cut the reddit feed from my iGoogle page before I hurt myself. [+3 productivity].
To keep me from hating life, I like to squeeze in some gaming and reading into my week [+4 happy].
I can read novels during my bus ride commute to work (and thanks to ebook readers, I can read any sloppy romance novel I please without the judging glares of those who sit near me!).
Since I must, I've allocated a small portion of time to the habits that make me go 'huh? where did the time go?!' (ie. Facebook, Reddit/Digg/etc...), but one of my eyes is fixated on the clock at all times.
Break it down! (-stop, Hammer time) [+4 focus]:
- Identify the high level idea of your final product (game story, game type, game play, blah blah). Completing this game is the long-term goal.
- Break it down some to get the features you'd like to have in the game.
- Break the features down and gather all the components you think you'll need to make this work.
- Select the most important components/systems for your game (I deem this Phase 1 of the project).
Ok, so I know what I want from my game, now all I have to do is skip sleep and finish it before the sun comes back up! Wait, I have a better idea...
Gonna' manage ma time! [+3 focus, +4 productivity] :
- Set milestones for each broken down (reasonably sized) iteration or phase. I try to split up the tasks into 2 month iterations, but that is just my preference.
- Using a ticket tracking system (I've been using Trac), I've placed a bunch of "feature request" tickets under the current milestone target for each major feature I'd like complete. The goal is to complete all of these feature requests before the 2 month period is over. This is the mid-term-ish goal.
- Using a project management application (Example: OpenProj or Microsoft Project), I've estimated the amount of time to complete each feature. I've over estimated each by approximately 2.25x, in order to give me time for any hiccups. Ideally, these features should add up to the 2 month period milestone (I add more features to the list if I don't anticipate many complications, but I could instead set the milestone date to the estimated end of features date). This is the short-term goal.
- Each day, I list the small portion of the current feature to cram into my daily TO-DO list to accomplish the short-term goal, which will accomplish the mid-term-ish goal and hopefully, eventually the long-term goal. This is the immediate goal.
Summary (tl;dr): To keep me focused and motivated I start from the end goal and then break it down into smaller chunks until my puny mind can comprehend the task at hand, and eventually my long-term goal will be realized.
Final Self Improvements:
Happiness + 7
Productivity + 7
Focus + 7
Sunday, December 12, 2010
Birthing Pains of Video Game Development
Gentle readers, come along and endure the birthing pains of video game development. This blog will chronicle the lessons learned while building my (currently) personal 3d video game engine I've titled "The Elpis Engine", as well as any video games that will arise as I move forward.
Now, I've been developing Elpis for a little while in my spare time, so my posts won't exactly be a pure start-to-finish operation. Although, it is early enough in the development stages that I could simply list what it can do and everyone would be caught up.
The engine itself revolves around a combination of a component-based entity system and a type of subsystem architecture. Essentially, everything in the game is a generic 'entity' or 'object' with swappable features and the subsystems manage these features. For example, the player character is an entity and it has a 3d model 'feature' or 'component' and the Renderer subsystem loads and draws this feature for our entity.
The system depends on the Havok physics engine, which has been implemented to some minimal extent and I plan to explore this here when I get around to implementing more physics. The engine is written in C++, Lua and uses the DirectX 9 api for rendering. Shaders are in HLSL.
The current capabilities of Elpis:
So, Elpis has some features and a framework to build upon. Surely that isn't enough to build a game, right?
Probably right! But before I list all the features I want to implement, I'll mention that I do have a game planned for this engine (Yay! Project scope!). I shan't cross the borders of the requirements for this game... at least, not at first.
AND THUS, I shall implement the following features next (likely in this order):
Now, I've been developing Elpis for a little while in my spare time, so my posts won't exactly be a pure start-to-finish operation. Although, it is early enough in the development stages that I could simply list what it can do and everyone would be caught up.
The engine itself revolves around a combination of a component-based entity system and a type of subsystem architecture. Essentially, everything in the game is a generic 'entity' or 'object' with swappable features and the subsystems manage these features. For example, the player character is an entity and it has a 3d model 'feature' or 'component' and the Renderer subsystem loads and draws this feature for our entity.
The system depends on the Havok physics engine, which has been implemented to some minimal extent and I plan to explore this here when I get around to implementing more physics. The engine is written in C++, Lua and uses the DirectX 9 api for rendering. Shaders are in HLSL.
The current capabilities of Elpis:
- Loading a DirectX model file (.x file)
- Loading Havok rigid bodies and associating them to the loaded model
- Applying basic physics to rigid bodies (gravity, collision, velocity, friction)
- Handle user input and translate to events that the system recognizes and listens for
- Binding systems and entities between C++ and Lua, thus it has scripting capabilities
- Simple Rendering for the loaded x files, currently on the fixed function pipeline
- Loading, configuring and rendering complex, customizable, animate-able and skin-able GUI elements
- Loads from XML into Lua where it is configured with event handlers and properties, C++ handles the drawing and event passing.
- Seemingly powerful design, though only a rotatable ship helm and animated treasure chest buttons have been developed at this point. (Pirate themed testing... problem?)
- Explore the scene using a quaternion based fly camera
- Generating and rendering terrain from a heightmap, on the programmable pipeline
So, Elpis has some features and a framework to build upon. Surely that isn't enough to build a game, right?
Probably right! But before I list all the features I want to implement, I'll mention that I do have a game planned for this engine (Yay! Project scope!). I shan't cross the borders of the requirements for this game... at least, not at first.
AND THUS, I shall implement the following features next (likely in this order):
- Support for a large world (currently aiming for 40km2 lands, without loading points)
- Shifting co-ordinate space periodically to avoid floating point errors
- Massive, divided terrain
- Entity streaming
- Terrain Physics (well...heightfield collision anyway)
Of course, there will be more features and posts detailing the parts that are interesting. My next post, however, will be of a non-technical topic that I feel is important to talk about: TIME MANAGEMENT! WHOOO! Who's pumped?!
Subscribe to:
Comments (Atom)