Visualizing Design

The Turn Manager, maybe one of the most insidious systems, is essentially done. After a bit of refactoring it is actually quite compact (about 230 lines of code) but the thoughts and logic behind it not so much, so I thought it would be nice to write a bit about it as a learning experience.

2016-03-06_hourglass

First let’s set up some requirements for our Turn Manager:

  1. It implements two queues, for Real-time actions and to manage Turn-based gameplay.
  2. Both queues can grow indefinitely without blocking the game flow.
  3. Actions from the Turn-based queue that change the status of the world must be resolved in the Real-time queue.
  4. The execution order of the Real-time queue is known/fixed at the beginning of the update.
  5. The execution order of the Turn-based queue is NOT known/fixed at any time (depends on initiative and actions done during an Actor turn, or lack of actions).
  6. The execution of time of the whole Turn-based queue between Player Actor turns must be constrained.
    1. The constraint may not be deterministic, but should be within a reasonable time, e.g. 500 milliseconds.
    2. Interrupt scenes (like dialogues) can override this rule.
  7. Lazy optimization:
    1. It is single threaded (more on this later).
    2. “Good enough” is good enough.

Said that let’s move to implementation.

I am mostly a visual guy. I understand things trough graphics, diagrams, flowcharts and so on (then tables, then bullet lists…). At work two of my most appreciated tools are Microsoft Visio (because my company uses that, there a number of alternatives, some free like draw.io that I am using for Wizards of Unica) and a white board. Let’s see how the requirements above translate into a flow chart.

The Update function of the Turn Manager

The Update function of the Turn Manager (click to enlarge)

There are at least a couple of quirks that I have pointed out in bubbles.

The first one (right) is that as soon as I finish with the Real-time queue I exit the loop. This one is useful to ensure that the Real-time queue contains only actions from a single round (albeit it is possible, expected actually, that several actors have pushed something inside the queue). Actions return a Time To Live, so if an action needs to wait we exit the loop and wait for a new cycle, to avoid getting stuck in waiting. We also ensure that no other actors will interfere with the queue until it is their turn.

The second one (left) is a bit tricky. We don’t want to use a for-each loop for several reasons, but on the other hand we don’t want to run a single actor for each update, even if the game would work just fine (it IS turn-based after all).

The for-each is out of question because the queue is dynamic: in theory an Actor may be added or removed at any time (hint: not if all the logic is managed by the Real-time queue) and after each Actor is executed its initiative is updated and the queue should be sorted again (we need to perform the sort immediately, otherwise an Actor may skip a turn if it is very fast an acts on more than a single turn). If you are not a programmer you may not know how much of a hassle iterating over a dynamic list may be…

Running one Actor per loop is also out of question because of timing constraints (see requirement 6 above). For example, if every iteration takes 10 milliseconds, it means that to run 100 Actors it takes a full second, and since Actors usually perform their turn in 0.5 it means that everyone (and especially the player) has to artificially wait half a second before being able to act again.

Now, most modern game engine solve these kind of problems with multi-threading (in short, parallel execution of a number of entity updates per cycle), but this opens a whole new world of problems that, from my perspective and limited to a “simple” game like Wizards of Unica, simply don’t give enough return for their cost.

The rest should be pretty straightforward and was actually not so difficult to implement. It will be important to define very well the behavior of actions, but this is something outside of the scope of the Turn Manager (see requirements 3 and 6 above).

If you are like me, I strongly suggest to put your algorithms on paper before the actual implementation. Most of the time pseudocode will do, but for me seeing the steps drawn is a huge improvement.

Do you have any suggestions on how to improve the loop?

Thanks for reading.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s