💾 Archived View for thrig.me › blog › 2024 › 02 › 20 › time-management-system.gmi captured on 2024-08-18 at 18:57:45. Gemini links have been rewritten to link to archived content
⬅️ Previous capture (2024-03-21)
-=-=-=-=-=-=-
No, this isn't about Getting Things Done or anything productive.
Roguelike games may have many actors (usually monsters trying to murderize the hero du jour (the hero can be modeled as a monster, only with keyboard input)) and the desire that actors move or attack or cast spells at different speeds. This yields the problem of scheduling all these things without the code being an unworkable mess.
One method is to assign some small integer cost to each animate or actor or anything that has scheduled behavior (dart turrets, off-board artillery, the weather system, etc) and when that cost zeros, the whatever it is makes a move. Exactly how to integrate this into a game system varies, as there may be global affects that adjust the flow of time, spell affects to apply to certain things, etc. One can also make the number go up until it triggers, but same difference (unless the numbers get so large that they overflow because the game ran for too long).
So the energy system loop might be to create various actors, assign them energy values, find the smallest energy value, subtract that value from all actors, and run any actors who have zero energy. After moving new energy values are be assigned to those actors that have not stepped into lava or who are otherwise now pining for the fjords, with the value depending on the cost of the move the actor made.
(One might instead use a priority queue for this, but I've never seen a priority queue benchmark well against the energy system described above. Maybe my priority queue code sucks, or modern systems are good at doing energy systems, especially if there's a nice array in memory to act on?)
One instead might have an event loop turning over at some rate, say every 10 milliseconds or whatever. Each time the loop triggers (or unsleeps itself) any actor with a zero or negative energy value is run. This avoids finding the actor with the lowest energy value, at the cost of some events maybe happening not exactly when they should. However, events could be scheduled in multiples of the tick so in theory a negative event should not happen. But enough words! How about some code?!
; the stash is if the agent needs to store whatever, or you could add
; more struct or object slots as need be
(defstruct agent
(energy 0 :type fixnum)
(action nil :type function)
(stash nil))
(defmacro trigger (object amount)
"returns true for objects whose energy has fallen to zero"
(let ((prev (gensym)))
`(let ((,prev ,object))
(when (plusp ,prev)
(decf ,object ,amount)
(when (minusp ,object) (setf ,object 0))
(zerop ,object)))))
; One might pass in or have a global time value if an agent needs to do
; different things based on that. The callback should either return nil
; (ignored) or can return new agents.
(defun run-agents (agents amount)
(loop for ent in agents collect
(when (trigger (agent-energy ent) amount)
(funcall (agent-action ent) ent))))
; NOTE this deletes agents with zero energy; to stay alive an agent will
; need to increase its energy value, or spawn new agents. In a game one
; might instead have an "alive?" field and then prune objects that have
; died. Whether or not agents should persist depends on how they are
; being used in the system.
(defmacro doagents (agents amount)
`(let ((new (run-agents ,agents ,amount)))
(setf ,agents (delete-if
(lambda (ent) (zerop (agent-energy ent)))
,agents))
; this compilication is support agents that may return a list of
; new agents. another way would be to register new agents, and not
; to loop over any new agents until the next tick
(loop for obj in new do
(etypecase obj
(agent (push obj ,agents))
(list (loop for lobj in obj do
(when lobj (push lobj ,agents))))
(null)))))
This isn't very much code, and isn't difficult to adapt as need be. And we should also include a bit of code that shows how to use it.
; a test of the agent system mostly devised to show what is going on
(load "agents")
(defparameter *agents* nil)
(defconstant +tick+ 10 "energy cost per iteration of energy system")
(defparameter *time* 0 "world time (if you need that)")
(block nil (setq *random-state* (make-random-state t)) (return))
(defun coinflip? () (zerop (random 2)))
(defun a-few-ticks () (* +tick+ (1+ (random 6))))
(defun dosomething (ent)
(declare (agent ent))
(format t "~&~a RUN ~a~&" *time* (agent-stash ent))
(when (coinflip?)
(let ((value (a-few-ticks)) (id (gensym)))
(format t "~& SPAWN ~a in ~a~&" id value)
(new-agent :energy value :stash id))))
(defun new-agent (&key (energy (a-few-ticks))
(action #'dosomething)
(stash (gensym)))
(make-agent :energy energy :action action :stash stash))
(defun show-agents ()
(format t "~&~a AGENTS ~a~&" *time*
(mapcar (lambda (e)
(list (agent-stash e) (agent-energy e)))
*agents*)))
(loop repeat 4 do (push (new-agent) *agents*))
(loop repeat 10 do
(doagents *agents* +tick+)
(show-agents)
(incf *time* +tick+))
And a Makefile since I insist on wedging everything to fit unix.
.SUFFIXES: .lisp .fasl
agents-test: $@.lisp agents.fasl
sbcl --script $@.lisp
.lisp.fasl:
sbcl --noinform --non-interactive --eval '(compile-file (second *posix-argv*))' {body}lt;
This may result in something like:
$ make agents-test.lisp
sbcl --script agents-test.lisp
0 RUN G94
0 AGENTS ((G96 10) (G95 40) (G93 40))
10 RUN G96
SPAWN G98 in 20
10 AGENTS ((G98 20) (G95 30) (G93 30))
20 AGENTS ((G98 10) (G95 20) (G93 20))
30 RUN G98
SPAWN G99 in 30
30 AGENTS ((G99 30) (G95 10) (G93 10))
40 RUN G95
SPAWN G100 in 10
40 RUN G93
40 AGENTS ((G100 10) (G99 20))
50 RUN G100
50 AGENTS ((G99 10))
60 RUN G99
60 AGENTS NIL
70 AGENTS NIL
80 AGENTS NIL
90 AGENTS NIL
One use is to schedule MIDI events; for example a "note on" event could create a future event that will run "note off" some time later, though this may become problematic if the same note is turned on multiple times, depending on what the software or hardware device does with "note on" events when the note is already turned on. A physical piano for example has difficulty playing a key that is already held down, but a synthesizer or software might simply run the usual code for whatever a "note on" does, as there may not be a lock due to the "key" being "down" unless someone writes code for that.
The agents could be more abstract; perhaps an agent emits one or more MIDI events, then reschedules itself sometime later to play the next note of a melody or rhythm, or generates more agents to do more things (assuming the agents do not get out of control). The agent handling code then runs the events when then need to be run, and the agents do not need to worry (directly) about doing something in some amount of time.
Agents are acted on in some unknown order. Sorting may be necessary so that, say, all the MIDI "note off" events happen prior to any "note on" events. One way to handle this is to collect all the events to be run during a tick instead of simply running them as they trigger. Then, the caller can optionally sort or modify the events before they are run.
The "note off" problem may not arise if you only trigger "note on" events and have a different but similar system that drains the time left and triggers a "note off" when the time runs out. This distinct system could also prevent a note from firing when that note is already playing, or could extend the duration of the note, or throw an error for the user to resolve.