Skip to content

WIP: New algorithm for Game:tick() and Game:levelTick()

Ryan Yappert requested to merge RootOfAllThings/t-engine4:archery_overhaul into master

The problem

T-Engine's implementation in GameEnergyBased.lua is pretty naïve/inconsistent when it comes to resolving both energy ties and mid-tick shenanigans. For example, game-level entities who are generated mid-tick will never act on that tick (because game.entities gets cloned), but level-level (map-level?) entities who are generated mid-tick might get to act on that tick, if they're sufficiently far up in the level.e_array table. The current algorithm of

  1. Pick an entity.
  2. Give that entity energy.
  3. Check if that entity can act, and let it act if it can.
  4. Move to the next entity.

Also leads to some inconsistencies. Iteration order is undefined because level.e_array isn't sorted in any way, and if two entities gain sufficient energy to act on the same tick, the order in which they act isn't clear either.

The solution (?)

Implement what I've termed "rolling action". The algorithm is the same for both game-level entities (in Game:tick()) and map-level entities (in Game:tickLevel())

  1. Iterate over the relevant entity list and hand out energy to all entities that don't have enough to act (or actBase).
  2. Re-iterate the entity list and collect any entities that are able to act.
  3. Sort this collection of entities in order of descending energy, baseEnergy, UID, and then finally their location in the original list as tiebreakers.
  4. Let the most eligible entity act (or actBase), thus decrementing its energy.
  5. Return to 2 and repeat until no entities are able to act on the current tick.
  6. Proceed to the next tick.

The changes are subtle but should make for a more consistent behavior across ticks and turns. For example, a creature with 1300 energy will always act before one with 1100 energy.

Implementation details

Adds a new function to GameEnergyBased.lua:_M:sortEntities(elist) that expects an unsorted list of tables. Those tables are expected to have elist[i].e as the entity in question and elist[i].index which is a general purpose tiebreaking value and should be unique (here sourced from the iteration in step 2). This function operates on elist (in place) and sorts it according to some criteria. The implementation here is:

  1. Highest energy acts first.
  2. If tied for energy, use baseEnergy.
  3. If tied for baseEnergy, use UID.
  4. If tied for UID, use the index.

Probably scuttles the self.can_pause-self.paused-level.last_iteration machinery in Game:tickLevel. I wasn't sure what exactly this was intended to do, and wasn't able to neatly mesh it with the new algorithm. Please advise.

Probably a fair bit more intensive, computation wise. The iteration is O(N^2) instead of O(N) which means that ticks may take significantly longer to compute with many entities in play. An O(N) version of the sorting algorithm is presented in a5ea06d4 that doesn't support entities being introduced/becoming eligible for action mid-tick.

Merge request reports