Generalize representation of dependencies between goals

[kostmo]

This builds upon #378.

Is your feature request related to a problem? Please describe.

I'd like to be able define "optional" goals (e.g. hidden achievements, or "secondary" or "tertiary" goals) for a scenario, aside from the primary goals.

Describe the solution you'd like
We could use a Tree rather than a list to represent the goals. Conveniently, YAML can already represent trees.

Goals that must be completed in sequence would be represented as a chain of increasing depth, while goals that are independent of each other shall be siblings in the YAML file. A slight drawback is that for each of the existing scenario files, multi-goal sequences will need to be indented into a "terrace" of children.

Perhaps we would define the following enum to label each goal:

data GoalType = Primary | Secondary | Tertiary | Hidden

Primary shall be the "default" goal type when omitted.
The scenario would be considered "complete" once all of the Primary goals are met. The "Keep playing" option will then be useful to pursue the other goals.

[byorgey]

Hmm, I'm not convinced --- that is, I'm not convinced it's worth it to use trees in particular. What about a scenario where you have to complete goal A to unlock goals B and C, and then you can only unlock goal D once you have completed both B and C? Or what about something where you need to complete any two of A, B, or C in order to unlock D? Or where secondary goal B is only available to you if you have already completed a different tutorial scenario? etc.? Switching to trees would be a lot of work and would complicate the code, but there would be lots of potential scenarios we still could not express. Really the only reason to use trees in particular would be that YAML can already represent them. So it would be a lot of added complexity with only a small gain in expressiveness.

If we want to generalize the goal system (and I'm very open to that), I think we should jump straight past trees to something much more general. I'm not sure exactly what, but here are some ideas off the top of my head:

• If we give goals unique identifiers, then each goal could have a list of other goals which are prerequisites
  • This by itself would let us express not just trees but arbitrary directed acyclic graphs
• Or each goal could have some code to define when it should become active/available, just like goals already have arbitrary code to determine when they have been met
• The idea of having "primary" goals that have to be met to complete a scenario makes sense, but I don't think we would need to make up a GoalType enum; each scenario could simply have a list of goals which must be achieved. Or, even simpler, each scenario would be required to list one goal as its primary goal. That goal could then encode whatever logic makes sense, such as completing a list of other goals, or completing two out of three of certain goals, etc.

[xsebek]

I like this proposal in general and either Tree/DAG/active system would be an improvement with many fun possibilities.

Some issues, that I can think of:

• We probably do not want to show all the possible goals descriptions. So there can be a hidden alternative or achievement.
• Some achievements need to be checked in the background, while we run other goal checks.

Overall I think the "active system" is the most general and might even be easiest to implement:

• use unique identifiers
• completing an objective turns on or off other objectives
• we can use two Set Objective which will make the current state easier to understand than encoding DAG in YAML
• EDIT: we also need a starting objective (required object member "start":) and winning objectives (wins: true).

@byorgey we can test backward compatibility for the first time in scenarios and keep supporting the good ol' objective list syntax. The new system does not need a new name - it can simply be a JSON/YAML object instead of a list. Guaranteed identifier uniqueness for free. 😁

---

PS: The active system is still a DAG graph where we can test reachability! Turning objectives off is just an optimization a big change to the graph properties that we can ignore if it is too much trouble. 🙂

[kostmo]

we can use two Set Objective which will make the current state easier to understand than encoding DAG in YAML

Sounds interesting, but can you elaborate on how this would work?

I like the idea of expressing as much of the dependency relationships statically as possible, so that we don't have to execute arbitrary code to, say, visualize the objectives network.

Overall I think the "active system" is the most general

A step beyond the "prerequisites list" implementation of a DAG in the yaml file could be a string that defines a boolean expression of other goals. These expressions would support AND, OR, and NOT. Here's a ready-made parser. This system generalizes the "prerequites list", which would be implemented as: Prereq1 AND Prereq2 AND Prereq3.... This optional boolean expression would finally be AND'ed with whatever code has been defined to evaluate the specific goal.

In fact, with a CNF boolean expression, we could make the ANDs implicit as items in a list, allowing us to piggyback on YAML a bit. (I prefer to leverage the structure of the underlying format when possible, rather than having opaque string blobs.) With this convention, the "prerequisites list" example above would be written exactly:

- Prereq1
- Prereq2
- Prereq3

but we could also do more fancy stuff like:

- Prereq1
- NOT Prereq2
- Prereq3 OR Prereq4

Can you think of any arrangement of objectives that this would be unable to represent?

[xsebek]

Sounds interesting, but can you elaborate on how this would work?

Very simply, you start with your starting objective in the activeObjectives set, and when it finishes you can move it to either the completedObjectives set or discard it and move all the objectives it turns on to the activeObjectives and conversely remove those that it turns off.

The advantage is that adding/removing objectives would be very simple - just add/remove those listed on the finished objective.

I now realize this is different from what @byorgey was pitching and would lead to arbitrary (?) graphs on sets of objectives.

The implementation in code and in YAML is simple and there are almost no restrictions, but the alternatives may be better.

[xsebek]

Boolean expressions look nice - they have the same power as the active/inactive system but would not require hacks when writing scenarios. Regarding the format, I would either go all the way and use the parser and evaluator you linked or use YAML as much as possible:

prerequisite:
  - objective1
  - or:
    - objective2A
    - objective2B
  - not: objective3

If we process the Aeson Value to BooleanExpr ObjectiveID, we could even allow both! 😆 The downside to the premade parser is that it does not allow the - character in identifiers.

Turns out JSON schemas can be recursive^[SO] so we do not need to limit ourselves to CNF. 😅

---

So far I like the "DAG using a list of alternative prerequisites" (@byorgey) and the "boolean expressions using YAML only" (@kostmo, but with Mergify-style not:/or:) the most. 🙂

[byorgey]

I like @kostmo 's boolean expression proposal as well. It's strictly more powerful than a simple list of prerequisites, but still relatively simple, and keeps all the prerequisite logic for a scenario in one place (I think @xsebek 's proposal to have each objective enable/disable others might end up being equivalent in power, but it would be hard to understand under what circumstances a given objective would become active, since that information would be distributed around among other objectives). I don't care too much about the specific syntax we use as long as it's easy for scenario authors. Probably Mergify-style not:/or: makes sense, that way you don't have to learn yet another syntax when writing scenarios.

---

I think we should generalize the goal dialog to show all the currently active/available objectives (kind of like a list of "active quests" in an RPG), perhaps with a narrow column on the left side with a list of objectives that you can scroll through, and a larger area on the right side showing the description of the currently selected objective. It makes sense to me that we would then want an optional hidden attribute for objectives; with hidden: true an objective will never show up in the goal list, even when it is available. It could be used for secret objectives, or just for "helper objectives" that exist only to serve as prerequisites for the "real" objectives.

[kostmo]

If we were to add a prerequisites field to each goal to indicate serial dependence, then we'll have to update every existing scenario that currently has more than one goal. How much work would this be?

~/github/swarm$ find data/scenarios -name "*.yaml" | wc -l
61
~/github/swarm$ find data/scenarios -name "*.yaml" -exec yq '.objectives | length' {} \; | grep "[01]" | wc -l
55

So we only need to update 6 scenarios.

For my own reference, here's how to get a list of the files:

find data/scenarios -name "*.yaml" -printf "%p\t" -exec yq '.objectives | length' {} \; | grep -v '[01]$' | cut -f1