Introduction

In a previous post I talked about my game loop and mentioned that the Update method was where a lot of the calculations for the engine are done. I've highlighted the method in this picture of the UML diagram:



I extracted most of the calculations from the RunEngine loop for a few reasons.

• The RunEngine loop was getting rather long and hard to follow.
  
• Now I can add the engine to another engine to process updates.
  
• If the game needs to for some reason to update the engine it now has access to this method externally.
  

Those are just a few reasons I broke the main game loop into sections. So here is most of the update code for today's discussion:[code=auto:358]void GameEngine::Update(){ std::queue tranObjects; // Get start position of entity array unsigned int pos = eFront; while(pos != eBack) { // Check if the entity fell asleep if(entityArray[pos].IsAsleep()) { // Add entity to the transfer queue tranEntity.push(entityArray[pos]); entityArray[pos] = new NullEntity(); }else { // Process update method of entity entityArray[pos]->Update(); } pos = (pos + 1) % MAX_ENTITIES; } // Transfer sleeping entities while(tranEntity.size() > 0) { // Get front entity we are sleeping IEntity* enty = tranEntity.front(); tranEntity.pop(); sleepArray[sBack] = enty; sBack = (sBack + 1) % MAX_ENTITIES; enty->GoingToSleep(); }}

Discussion

The first thing to notice in the update method is there are three main loops. This would put this algorithm at Big O(n) * 2 or Big(2n) depending on how you like your math. In the first loop we go through all game entities and check weather they are asleep. If they are then we add them to a standard queue for later processing. If their still awake then we run their update method

Sleeping Entities

The idea behind having two stacks is that a game entity may no longer need to do calculations but we still need to draw it to the game field. So in this example when the entity feels it has fallen asleep then we no longer worry about running its update. Currently the down side in my design is once an entity goes to sleep it will be there until the engine gets a clear all call. I do plan on though adding in to the engine a way to wake up the sleeping object and put it back in the mainstream entity updates.

Once an object has been put to sleep I do call a special entity method GoingToSleep() this is to allow the entity itself to do any last frame maintenance before it is dormant for ever. Well kind of for ever, they still get drawn so there is potential to do something there. The one thing to note in my PlayerEntity class the IsAsleep() method when called will always return false. Which means if your playing my game you can't fall asleep I won't let you...

The other advantage here is that if I have game field objects that are not moving and want to add more active objects we are not limited to the max entity game limit. Currently this is set to 16 but there is no reason it couldn't be bigger. Is this to small of a number? for a different game that could potentially have more moving parts yes this would not work. but for my simple ASCII RPG type game where there is usually only one palyer and one monster it maybe over kill. But potentially we could setup the random monster generator to not just create one monster but add a pack of monster for you to deal with. Yes this is planned in the game.

Data Structures

You maybe wondering why did I decided on using an Array instead of something like a linked list or any other awesome and amazing data structure out there? This is actually a good question and one of my original engine designed did use a custom double linked list because I liked the ability to adhoc put objects into the game and not worry about any limits. This was fairly naive of me in thinking this would be a good performer. If you know how a processor will read memory and cache hits and cache misses then you might understand the round trip to the memory banks actually slowing down your algorithms. The idea is if we can keep all our data together then we have a higher chance in getting a processor cache hit when it is working on our calculations. Using a linked list leads to memory fragmentation.

This subject could use some hard number and tests performed to prove how much more efficient either data structure can be. For now I will leave this for another discussion so I can take the time and perform these test and provide solid results.

The other thing to note on the game array is that I keep a record of the start and end of the active items in the array. This is so we don't have to loop through say 16 items every time the update loop is ran. It also allows me to remove items from either the front or back of the array and then update the pointer. Another cool trick you can do with arrays which is fun to exploit.

Conclusion

It is worth mentioning that in the actual engine code there is another loop that runs which is primarily for items in the engine that just need to perform updates and not do any rendering. This kind of makes the update run in Big O(3n) time. Overall though this update method provides decent abstraction and power to the core engine. Because of this design it made it quite easy to fix my render flaw when the frame draw got skipped.