Internals

Internals

Engine

Consider the task of simulating a particle which at random times receives an outside impulse changing it's direction and an certain times hits a wall, reflecting from it. The exact time when the particle hits the wall is difficult to predict - because it might change it's direction randomly. What we can compute, is the hitting time of the wall conditional on the particle not changing direction. If we do so, we need to recompute the hitting time of the walls every time the particle changes direction.

ZigZagBoomerang provides an engine for this task. It simulates the movement of a particle (or abstract state) in time and space, keeping track of possible collisions and other events.

Basis are concurrently running clocks/alarms i in 1:d which show the next event time of a certain type if nothing else happens. Whatever clock rings first, an appropriate action is taken (a modification of the state). This action invalidates precomputed hitting times, so each action is responsible of triggering updates to relevant timers: an action triggering a direction change in a coordinate needs to update all timers which depend on the velocity in this coordinate.

This is handled with a priority queue: Tick times/event times t of each clock i of events e are fed into a priority queue Q.

On next tick in the queue, say of clock i at time t′, the state u gets updated with action action![e], where action! is a table of available actions. The action modifies the state u, and informs the engine which times get invalidated by returning a vector of invalidated clock indices. The engine calls for each clock a function computing the next event time and queues them in the queue.

In each step, it iterates over the following

Step 1: Fetch next event and associated action

        i, t′ = peek(Q) # fetch time of next tick of next timer and action `e` belonging to `i` 
        e = next_action[i]

Step 2: Perform action

        state_change, invalidated_clocks = action![e](i, t′, u, args...)

Step 3: Update invalidated clocks and feed into queue

        for j in invalidated_clocks
            pairs_of_actions_and_times = [next_action[e](j, i, t′, u, args...) for e in available_actions(...)]
            e_new, time_new = findnextaction(pairs_of_actions_and_times)
            Q[j] = time_new
            next_action[j] = e_new
        end

In Julia, calling a function from a struct action![e] and next_action[e] is inherently type unstable, but this is solved through generated functions/unrolling the loop or decision tree.