Allocation algorithm

TODO: this page needs a lot more detail

The monster allocation algorithm is the heart of Manticore. It is used to generate the lists of encounters presented to the user. This algorithm is found in src/ts/workers/libs/allocate.ts. At it's heart it is simply a recursive combinations algorithm that has been extended with domain rules from the 13th Age encounter building system.

The function allocateMonsters does the majority of the work. It has an internal generator function allocate that calls itself recursively to yield encounters.

allocate depends on the generator repeatMonster for producing one or more monsters for a given allocation based on cost and available points.

allocate should only ever receive immutable (readonly) values as parameters. Note that the allocation function is that partial allocations are threaded in, and then yielded out outward when the budget is expended. This can be seen on the acc parameter of allocate. While the acc (the accumulator) is technically mutable, it is copied (using zero argument Array slice) each time is modified prior to passing to into a recursive call to allocate.

The ForkingBufferCursor<T> class wraps up access to the underlying set of monsters and manage forking it when the algorithm descends into a recursive call.

Finally the stream of generated encounters is run through groupMonsters to collect encounters with the same monsters in different proportions.

Complexity

This algorithm is potentially very expensive. Without thinking about it too much I assume that it is maybe O(2^n). It generates a lot of combinations if theres more than a small number of monsters to combine. If left unbounded it could run for hours and consume a lot of ram if it was feed the whole dataset. As a result there are two implications for the code:

• It runs in a web worker to avoid blocking the main thread of the UI.
• allocateMonsters caps the total encounters generated at 10000, which is probably absurdly high anyway.

Originally the allocation code didn't run on a worker, and as a result was written and rewritten to be about as performant as was reasonable. While I've been migrating away from this to a more maintainable if slower implementation now that it runs in a worker, some vestigial pieces of code still reflect this origin.

Territorial monsters

The notion of territorial monsters comes from 5e Dungeons & Dragons. It was adopted in a very ad hoc fashion into the allocator as a step towards having the allocator produce /interesting/ encounters. The concept is simple: some monsters are territorial and won't appear in an encounter with another territorial monster. Currently this is hardcoded to master vampires ("Vampire" in the 13th Age book) or any dragon (regardless of size or colour).

The territorial code simply skips territorial monsters in the input sequence if allocate is told it has already seen a territorial monster. This is part of the loop around line 113.

Issue #30 is intended to generalise this part of the algorithm.

Repeating monsters

Currently the algorithm explicitly has a skip step for all monsters, with repeatMonsters returning nothing, or allocations of 1 or more of a given monster. This implementation reduces the additional conditionals within the consumption of the repeats. Generalising the territorial and maximum types logic may require these to be unified.