Poll

Did you find this article helpful?

Yes
0 (0%)
No
0 (0%)
No, there's a better explanation somewhere else.
0 (0%)
No, its utterly obvious.
0 (0%)
TL;DR
2 (100%)

Total Members Voted: 2

Author Topic: Simple, stable, energy system  (Read 7860 times)

Omnivore

  • Rogueliker
  • ***
  • Posts: 154
  • Karma: +0/-0
    • View Profile
Simple, stable, energy system
« on: January 29, 2016, 11:59:23 AM »
If you are like me and found the need for an energy system to schedule your entity actions, you probably haven't found much clearly stated on the net (or I missed it in my searches).  Implementing an energy system runs into two additional potential problems; multi-move jumps in display state, and possibly an unstable (unsaveable) game state when processing halts due to needing player input.  It sounds like a thorny problem, but after you break it down, it isn't so bad, the following is, I believe, a fairly clean solution.

First, lets deal with the multi-move jumps in display state.  This is where a mob takes two or more actions (typically moves) to the player's one.  If you simply give the display a new state after each player move, you end up with 'teleporting' mobs, jerky actions.  You can, of course, turn to something like a physics engine and do an animated display, interpolating the move over time so it looks good.  However, why not eliminate the problem in the first place?

An energy system works by adding a value based on an entity's speed to the entity's energy state each turn.  In simple systems, an entity with a positive energy level is free to take an action.   The action's energy cost is subtracted from the entity's energy level.

If our display system is typical of today's frame rate driven loops, then instead of doing all the work at once, we can use a divisor to spread the work over multiple frames where each frame (or sequence of n-frames) receives a stable picture of the game state.  The ideal divisor is one that is large enough to ensure that no entity can take two actions in one processing tick.  That is, the fastest speed energy add amount divided by the divisor is smaller than twice the quickest action energy cost.

A nice side effect of using a divisor is that after each processing step we potentially have a stable game state so we can do 'save anytime' save games (useful for debugging at the very least).  Potentially, because there is another wrinkle to the overall problem.  Player entities can normally only act if input from the player is available. 

Part of doing an energy system is ordering actions by entity energy.  This isn't just an afterthought, it is a necessary part of making a consistent acting system.  Typically this is done by sorting or by a priority queue.  Sorting is simpler, and hey, we're doing roguelike, we have cycles to spare (although sorting in this case is probably *faster* than a reprioritizing priority queue).

Now though, we have a dilemma, halfway through our sorted list of entities by positive energy levels (descending), we run into our player entity.  No problem, we say, we'll just grab the next player command out of the input queue and... oops... nothing there.  We're stuck.  We have to bail and return control to the user interface, but we have a half done list, an unstable state.  Sure there are some coroutine hacks that might let us actually yield then resume later, but between the yield and resume we can't save the game state because it is not in a stable state.

There is a simple solution, one that doesn't require saving some sort of quirky interim state.  Before we even start processing the tick, we check to see if A) there is player input in the queue, and if not B) that the player's next energy level won't be above zero.  That is, we check to see if the player's entity is going to run into the stalling scenario above, and simply return from the process game function without doing anything to avoid it.  Maybe that's why my google-fu failed, everyone that has done it considered it too simple to need writing up!

Ok, time for some pseudo code:

GameLoop:
   GetInput => add command to player entity input queue if necessary
   Update => call the engine's Process function
   Render => do what I'm really bad at

Engine Process function:
  if no commands waiting in player entity input queue:
     player_tick_energy = player_speed / tick_divisor
     if player_entity.energy + player_tick_energy > 0 then return "Hey I need input!"
  otherwise // much better than else
 
  pending_list = new list (or clear old one and reuse each tick)
  foreach entity in actor_list:  // actor_list includes anything that can act (mobs/some items/traps/unstable walls/etc)
    add entity.speed / tick_divisior to entity.energy
    if entity.energy > 0 then add to pending list

  pending_list.Sort( on energy descending ) // highest energy levels first
  foreach entity in pending_list:
    do something and adjust entity energy level by subtracting cost of something action
    // this is where we would've run into the stall problem if we hadn't made sure the player entity wouldn't hang

  clean up and return


Simple.

Hope this helps,
Brian aka Omnivore

PS: There is a slightly more complicated, improved version that handles a number of possible additional cases, as well as ensuring that every action that could be taken before player stall is taken before halting.  In C# it could be done using a custom struct that supports IComparable<T> in place of the raw entity for the pending list.  The custom struct holds the entity.energy + entity_tick_energy in an additional field (that is sorted on).  This allows any entity to abort the current process function without causing an unstable state.

PSPS: Slight error in the divisor calculation, the largest speed add divided by the divisor should be smaller than the lowest cost action.
« Last Edit: January 29, 2016, 03:30:27 PM by Omnivore »

Omnivore

  • Rogueliker
  • ***
  • Posts: 154
  • Karma: +0/-0
    • View Profile
Re: Simple, stable, energy system
« Reply #1 on: January 30, 2016, 03:16:13 AM »
Update: After a few hours sleep, I woke up with an idea for an improvement based on the first simple solution above.  Rather than write another long explanation, the C# snippet below should be self explanatory.

Code: [Select]
        // simpler energy cost system
        public const double EnergyPerTick = 1000.0;
        public readonly double EnergyPerTurn; // this is ticks per turn * EnergyPerTick

        IList<EntityID> actorList; // current actors (mobiles, active items, features, etc)

        // return true if input needed
        bool OnUpdate()
        {
            double playerSpeedFactor = GetSpeedFactor(PlayerId);
            double tickEnergy = EnergyPerTick;
            var playerCmdQueue = command_queues[PlayerId];
            if (playerCmdQueue.Count < 1) {
                var playerEnergyState = GetEnergyState(PlayerId);
                if (playerEnergyState.Energy + tickEnergy * playerSpeedFactor > 0.0) {
                    // We need to prevent partially computed state due to missing player input
                    var maxPlayerEnergyChange = -playerEnergyState.Energy;
                    if (maxPlayerEnergyChange < 0.0001) {
                        // this is probably the second or subsequent call with this state
                        return true;
                    }
                    // We avoid trying to process the player entity by keeping its energy
                    // state below 0.  Adjust tickEnergy to give us a short tick.
                    tickEnergy = maxPlayerEnergyChange / playerSpeedFactor;
                }
            }
            var readyList = new List<EntityEnergyState>();
            foreach( var id in actorList) {
                var sf = GetSpeedFactor(id);
                var es = GetEnergyState(id);
                es.Energy += sf * tickEnergy;
                if (es.Energy > 0.0) {
                    readyList.Add(es);
                }
            }
            foreach( var es in readyList.OrderByDescending(a => a.Energy)) {
                var cmdq = command_queues[es.Id];
                Debug.Assert(null != cmdq);
                var cmd = (cmdq.Count > 0)? cmdq.Dequeue() : waitCommand;
                var cost = DoCommand(es.Id, cmd) * EnergyPerTurn;
                es.Energy -= cost;
            }
            readyList.Clear();
            return Math.Abs(tickEnergy - EnergyPerTick) > 0.0001;
        }

A boolean state variable could be added to make the second and subsequent call to OnUpdate bulletproof as well as cleaning up the final return value.

Hope this helps,
Brian aka Omnivore
« Last Edit: January 30, 2016, 03:19:08 AM by Omnivore »

Omnivore

  • Rogueliker
  • ***
  • Posts: 154
  • Karma: +0/-0
    • View Profile
Re: Simple, stable, energy system
« Reply #2 on: February 28, 2016, 09:26:34 PM »
Found an alternative, and in many cases much improved, solution: https://www.reddit.com/r/roguelikedev/comments/484gb2/turnkeeping_issues_with_energy_and_fatigue_systems/d0h3qmb

There are some other solutions discussed in that thread but Kodiologist's approach as used in Rogue TV seems to be the best.  If anyone is interested in a Python adaption of the idea or wants an explanation of how to adapt an energy system to an abstract timed system, post a reply and I'll do my best to help.

Hope this helps,
Brian aka Omnivore

Tilded

  • Newcomer
  • Posts: 49
  • Karma: +0/-0
    • View Profile
Re: Simple, stable, energy system
« Reply #3 on: February 29, 2016, 12:50:43 AM »
I'm using DeltaClock. Entities are stored in an ordered list along with the time between the previous entity's move and theirs. So:
Code: [Select]
Kodiologist's system:
A 100, B 150, C 225,  ...
DeltaClock:
A 100, B 50, C 75, ...
There's the unecessary optimization that, each turn, you only have to update the times for one entity instead of all of them.
This means that you have a list of who is going to act next, and entities can go in the list more than once.
If you want to solve the jerky actions problem, you could do something like this: If the fastest entity takes 50 units of time between actions, add a dummy entity to the list that takes 50 units of time between moves. This entity would not represent anything in game, but when it 'moves,' render the game and wait a few frames.

Quendus

  • Rogueliker
  • ***
  • Posts: 447
  • Karma: +0/-0
  • $@ \in \{1,W\} \times \{1,H\}$
    • View Profile
    • Klein Roguelikes
Re: Simple, stable, energy system
« Reply #4 on: February 29, 2016, 01:39:56 PM »
For games which have fewer than a thousand actors in play at the same time (or for which profiling doesn't identify turn scheduling as a bottleneck), I think there are more important considerations for a turn-scheduling system than how many times per tick or per turn each actor is processed.
For instance, how actor deaths are processed, when time-limited effects are cancelled, and how often damage-over-time is applied. RLs with fine-grained time systems often have ways for an actor's speed to change outside of its turn, such as a hostile actor casting a slowing spell, or an environmental hazard destroying an equipped speed item. Ideally these kinds of mechanics should be implementable without awkward hacks or replacement of the turn scheduler.
For systems where each actor is only processed during its turn, there are at three ways to deal with damage over time:
  • Actors with different speeds experience different amounts of damage in the same length of time
  • Damage over time is given the elapsed time as a multiplicative parameter
  • Damage over time is implemented as a separate entity with standardised speed
Some of those options aren't too bad. DeltaClock, however, has some big problems.
First, the schedule() method uses a linear search to find the appropriate place to insert a new event, so that its worst-case performance is equivalent to iterating over every actor every time an actor takes a turn.
Whenever an actor dies or has its speed altered outside its own turn, it needs to be unscheduled. When an event is unscheduled, the preceding event's link and the following event's delta both need to be updated, and the unschedule() implementation given on roguebasin doesn't do either of those tasks.
Code: [Select]
dc = DeltaClock()
dc.schedule('a',25)
dc.schedule('b',100)
print(dc.nodes['b'].delta)
dc.unschedule('a')
print(dc.nodes['b'].delta)
Even if unschedule() was correctly implemented, correctly updating the delta for an actor whose speed changed would be difficult. You would have to work out what energy level it reached in the time since its previous turn, based on its previous speed and the sum of time deltas stored in the DeltaClock, and then how many ticks are required to reach the full energy at the new speed.

TL;DR fancy time systems put unnecessary roadblocks in the way of common mechanics, giving monsters energy every tick is much easier.

Zireael

  • Rogueliker
  • ***
  • Posts: 604
  • Karma: +0/-0
    • View Profile
Re: Simple, stable, energy system
« Reply #5 on: February 29, 2016, 01:43:28 PM »
Found an alternative, and in many cases much improved, solution: https://www.reddit.com/r/roguelikedev/comments/484gb2/turnkeeping_issues_with_energy_and_fatigue_systems/d0h3qmb

There are some other solutions discussed in that thread but Kodiologist's approach as used in Rogue TV seems to be the best.  If anyone is interested in a Python adaption of the idea or wants an explanation of how to adapt an energy system to an abstract timed system, post a reply and I'll do my best to help.

Hope this helps,
Brian aka Omnivore

I can't recall what programming language Kodiologist uses. I like that approach, it's really good and I think I'll try my hand at a Lua adaptation.

Tzan

  • Rogueliker
  • ***
  • Posts: 193
  • Karma: +0/-0
    • View Profile
Re: Simple, stable, energy system
« Reply #6 on: February 29, 2016, 10:07:25 PM »
Whats being described by Kodiologist is exactly what I am planning to do.
Friends of mine "invented" that in the 1970's to replace the D&D move system.

In D&D a guy could run away several spaces then a chaser could run up behind and hit him, move+action= 1 turn.
So the guy just running could never get away. Mike really hated that, because he was always running away  :)

We used a sheet of graph paper and blank 1/2 inch counters from Avalon Hill wargames to make a time chart.
Fast actors at the top, slow and npc creatures at the bottom, all aligned in the far left column to start.
Swing a sword now, move the counter 3 spaces to the right etc...
Walk 1 space, move counter 1 space.
Run 2 spaces, move counter 1 space.

You could increase a skill to swing swords faster, even to get 2 swings per time count.

Our time was 1 count per 1 second of simulated time.
Milliseconds seems excessive for paper and pencil play, but no big deal for a computer.


Tilded

  • Newcomer
  • Posts: 49
  • Karma: +0/-0
    • View Profile
Re: Simple, stable, energy system
« Reply #7 on: February 29, 2016, 10:22:26 PM »
Yes, DeltaClock has limitaitions, and it is not intrisically better than any other system. I don't use it for it's efficiency, I use it because it is simple and doesn't require a global time (Javascript has no heaps/queues, and I'm too lazy to implement them).
RLs with fine-grained time systems often have ways for an actor's speed to change outside of its turn
Yep, DeltaClock is unsuited for that. It models everything as a fixed cost. I try to avoid fine changes in speed because, in a turn based game, it's hard to measure their effects as the player. After all, if you are going to split your game into turns, double moves at seemingly arbitrary moments kind of takes away from the point of using turns.
For actor deaths, I just have them stop rescheduling themselves if they are dead (I have a remove function that works, but I don't use it).
My implementation in javascript, if you're curious.
Code: [Select]
/**
 * Implementation of DeltaClock
 * DeltaClock is a scheduling system created by Jeff Lund.
 * It is a linked list that stores actors and the time difference between them.
 * @return a new schedule object
 */
rlt.Schedule = function() {
    'use strict';
    return {
        /**
         * Add an actor to the schedule
         * @param actor - actor to be added
         * @param delta - the time before actor will act
         * @return the schedule
         */
        add: function(actor, delta) {
            var prev = this;
            var next = this.next;
            while (next && next.delta <= delta) {
                delta -= next.delta;
                prev = next;
                next = next.next;
            }
            if (next) {
                next.delta -= delta;
            }
            prev.next = {
                actor: actor,
                delta: delta,
                next: next
            };
            return this;
        },
        /**
         * Advance to the next actor
         * @return the actor that was at the head of the list
         */
        advance: function() {
            if (!this.next) {
                return undefined;
            }
            var actor = this.next.actor;
            this.next = this.next.next;
            return actor;
        },
        /**
         * Remove all instances of an actor
         * @param actor - the actor to be removed
         * @return the schedule
         */
         remove: function(actor) {
             var prev = this;
             var next = this.next;
             while (next) {
                 if (next.actor === actor) {
                     prev.next = next.next;
                     if (prev.next) {
                         prev.next.delta += next.delta;
                     }
                 } else {
                     prev = prev.next;
                 }
                 next = prev.next;
             }
             return this;
         },
         /** The head of the list */
         next: undefined
    };
};

Omnivore

  • Rogueliker
  • ***
  • Posts: 154
  • Karma: +0/-0
    • View Profile
Re: Simple, stable, energy system
« Reply #8 on: March 01, 2016, 12:18:29 AM »
@ Zireael: Kodiologist uses Hy which is... Lisp on Python.

@ Quendus: Good points!  I prefer to implement DoT and similar effects as independent entities.

After some thought and review, I realized that the major difference between an energy system and an abstract time system is that conceptually the 'traditional' energy system is just an inverted abstract time system with a fixed 'current time' of zero.  I revisited my earlier ideas and implementations, and came up with a very simple new system in Python which, I believe, addresses all of the concerns and has a low overhead should processing time be a concern.  It also is, I believe, more compatible with ECS (all code in systems) approaches.

See https://gist.github.com/Brian61/2702669ba9f42802815d#file-scheduler-py for Python source.

If N is the number of Actors, and M is the number of Actors ready for processing, then the scheduler.py algorithm is of O(N + M*log(M))*.  For comparison, a priority queue based approach is O(M*log(N)).   However, for rescheduling, the algorithm in scheduler.py is O(1) while a priority queue based approach is O(N*log(N))**. 

Hope this helps,
Brian aka Omnivore

*depends on the ratio of N and M, for low M:N the N term predominates, for high M:N the M*log(M) term.
**the textbook figure here seems too high, it should really be O(log(N)) in most use cases.
« Last Edit: March 01, 2016, 12:43:13 AM by Omnivore »

Quendus

  • Rogueliker
  • ***
  • Posts: 447
  • Karma: +0/-0
  • $@ \in \{1,W\} \times \{1,H\}$
    • View Profile
    • Klein Roguelikes
Re: Simple, stable, energy system
« Reply #9 on: March 01, 2016, 11:32:33 AM »
That looks like a sensible approach to the problem. If I adapted it for use in my own projects I'd probably use 1 rather than 0.001 as the smallest unit of time (or make it a parameter when initialising the object), and make the modifier in modify_time() additive (or overwriting) rather than multiplicative.

Omnivore

  • Rogueliker
  • ***
  • Posts: 154
  • Karma: +0/-0
    • View Profile
Re: Simple, stable, energy system
« Reply #10 on: March 01, 2016, 01:10:11 PM »
That looks like a sensible approach to the problem. If I adapted it for use in my own projects I'd probably use 1 rather than 0.001 as the smallest unit of time (or make it a parameter when initialising the object), and make the modifier in modify_time() additive (or overwriting) rather than multiplicative.

Thanks.  I used 0.001 as an 'epsilon' value to avoid problems with floating point equality.  In a static typed language I'd probably just use integers for abstract time values.   

It is a bit hard to see in the code but the list elements returned by current_actors() are tuples of three parts: the time of the action, the id of the actor, and a reference to the actor data.  Normal actions apply an additive value calculated by the time of the action + a suitably modified action cost of the next action directly to the actor data action_time field as the actor is processed.  I didn't add a method for this because there are too many external factors involved and it doesn't require accessing the actor mapping.

The modify_time is multiplicative because it is for use when one actor applies a 'slow' or 'fast' effect to another actor.  Really this could be done externally in a similar manner to the primary route detailed above for normal actions, the modify_time method is just a helper.

In actual code, since I use a 'pure data component/virtual entity/all game logic in systems' ECS model, I'm extracting the current_actors method out as a stand-alone method (or perhaps as a member of a model class) renamed to schedule.  It just seemed to be more widely applicable to demonstrate it as a class.

Thanks again,
Brian aka Omnivore

Quendus

  • Rogueliker
  • ***
  • Posts: 447
  • Karma: +0/-0
  • $@ \in \{1,W\} \times \{1,H\}$
    • View Profile
    • Klein Roguelikes
Re: Simple, stable, energy system
« Reply #11 on: March 01, 2016, 02:16:09 PM »
I could see the intent in making modify_time multiplicative; I think making it additive would allow it to work in applications where time and energy are integral (and certain speed changes would have non-integer ratios), and where effects like stunning can delay an actor's turn by a fixed period of time.