Jump to content
  • Advertisement
  • 04/10/14 09:11 PM
    Sign in to follow this  
    Followers 0

    Hacking the monolithic entity system

    General and Gameplay Programming
    wildbunny

    By Paul Firth

    Hi and welcome back! This time I'm going to talk about a trick I used on the old PS2 game '24 The Game' to save over 30% of a frame by hacking the game's monolithic entity system.

    The monolithic entity system

    You've probably all seen this design before:
    1. Entity manager, stores a list of all entities
    2. Each entity implements an Update() function
    3. Every frame, the manager loops through all entities and calls Update() on each one
    The primary problem with this design is it's polling nature; each entity is polled to do work, even when that entity may not have any work to do. This doesn't start out being a problem at the beginning of the development of a game when there are only a handful of entities, but it sure is when the game is full of 1000s of them! In '24 The Game', entities were any object which you could interact with, which included: doors, characters, cars, guns, pick-ups, boxes and any other physics objects. They soon started stacking up in numbers, especially when you consider the game's draw distance.
    24_Snipe_4_3.jpg

    Event driven

    In an ideal world, the system wouldn't have been designed like this in the first place. Something event driven would have been more appropriate for the majority of entities - so entities just sleep until they are acted upon by an incoming event, such as being shot, or collided with. While asleep an entity would have done no work and therefore taken no CPU time. However, this was not to be since the game was in beta and rewriting the entire entity system seemed like a bad idea(!)

    Hacking the monolithic entity system

    So a more achievable method was needed, one which could be plugged right into the existing system without breaking everything. The solution was discovered after making a key observation about the nature of the variable time-step we were already using in game. In a game where the time-step varies from frame to frame (like nearly every game in the world), entities must adjust their behaviour to cope with a differing frame rate - for example, animations move forward a differing number of frames, characters move across the ground differing amounts per frame and so on. This being the case, calling Update() on 'unimportant' entities every 2nd or 4th frame wouldn't break anything and would save a bunch of CPU time.

    Unimportant entities

    So, what is an unimportant entity? From the point of view of this system, an unimportant entity is one which is not currently interacting with the player, or is very small on screen, or completely off-screen.

    Mitigating edge cases

    Unimportant entities could temporarily have their importance increased after receiving an event, such as being shot, or collided with. This mitigated the problem of 'dumb entities' which would take a long time to react to events in this new system. Screen-space size should be used rather than just plain distance when calculating importance, otherwise zooming in on a far away moving character would reveal jerky animation, as the animation controller only got updated every other frame. Importance overrides will always be needed in some cases, like if you have a bunch of AI companion team-mates who are following behind the player. Very unimportant entities could volunteer themselves to be excluded from Update() completely if they did no work there, such as most physics objects.

    Results

    In the end this system saved 30% of a frame in general across all levels, sometimes a lot more which was a definite result. However, if possible don't design a monolithic system in the first place! That's all folks Thanks for reading, hope this post gives you some ideas! For more ideas check out my blog at http://www.wildbunny.co.uk/blog/.

    Article Update Log

    10 Aprl 2014: Initial release
    0

      Report Article
    Sign in to follow this  
    Followers 0
    Go to articles General and Gameplay Programming

    User Feedback


    swiftcoder

    So I'd like to see some discussion in the article about *how* to accomplish this type of scheduling.

     

    Let's say I have 10,000 entities in my world. do I need to maintain an external list of potentially 10,000 items that desire updates? Do I give every entity a needsUpdate() function, and call it on every entity every frame? Do I give every entity a updateFrequency() function, which is read at entity creation, and used to partition a sorted list of entities?

    Share this comment

    Link to comment
    Share on other sites
    slicer4ever

    arn't you still doing work on each entity to determine if you need to actually work on it?

     

    I mean, it saves work for some examples you gave(such as a far off unit animating), but woudn't most interactive objects already be doing little to no work?(such as doors/items)

     

    or as swift asked, are you sorting the objects into different lists for work loads?

    Share this comment

    Link to comment
    Share on other sites
    Michael Tanczos

    I suppose the trick of this all is how you partition the entity list such that you know which entities are in the immediate location of the player.   You'd have to have entities that can still appropriately function with infrequent update calls (probably those entities offscreen with little interactivity with the surrounding world). 

    Share this comment

    Link to comment
    Share on other sites
    djee

    As far as I understand it, this time slicing is the same idea already used in Valve's Source engine for entity thinking. If you have a look at the free SDK, each entity has a Think() function, and a flag indicating whether it should think this frame or not. Inside Think(), each entity can inform the engine of the next time it needs to think (e.g. 1 second later) via a SetNextThink() function, and the Think() function will not be called until then. Internally the engine maintains a priority queue based on the next time of thinking.

    I also read about the idea of a LOD-based (spatial or other) priority list recently, probably on entity-systems-wiki.t-machine.org, although I do not know of any actual implementation. But it seems promising indeed.

    Share this comment

    Link to comment
    Share on other sites
    MHGameWork

    Yup, thats how i do it. Have your entities return a 'time until next think'. Note that this is actually Very similar to an Actor Model (http://en.wikipedia.org/wiki/Actor_model). You can implement a scheduler in your engine which schedules these 'think' calls Jerome mentions. Using the actor model way of thinking you could even make this updating multithreaded with some additional restrictions on your think methods.

    Share this comment

    Link to comment
    Share on other sites


    Create an account or sign in to comment

    You need to be a member in order to leave a comment

    Create an account

    Sign up for a new account in our community. It's easy!

    Register a new account

    Sign in

    Already have an account? Sign in here.

    Sign In Now

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

  I accept

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!