To further complicate matters, we wanted to give the player the option to change her paths throughout the story. So instead of just having six mostly-disjoint paths the player can take through the story, we have the following story diagram (still a work in progress).
Which gives our writers nightmares.
Fortunately, we've got a pretty powerful system that makes our dialogue exceptionally flexible and responsive to prior events in the story. Borrowing from a 2012 GDC talk by Valve's Elan Ruskin, it functions by allowing a writer to place any number of criteria on a line. The game then plays the most specific line that has all its criteria met. As an example, a writer might make two lines for entering a town: a default one that reads, "Welcome to Thebes." with the only criterion being the player enters the town; and a more specific line, "Those wounds—someone fetch a healer!" that has the criteria of the player entering the town and being at <50% health.
If the player is at <50% health when entering the town, the second line will always play, since it'll have two criteria to the first line's one. However, if the player is at >50% health, the second line will never play since one of its criteria isn't met.
Branching can even occur mid-conversation, as a writer can enter multiple potential replies to a line, each of which contains its own set of criteria.
The particularly awesome thing about this dialogue system is that it gives us an opportunity to add situational embellishment without building a complicated dialogue tree. Simply, if we want to add lines that specifically reference one or more earlier events, we just add those events as criteria. If the player's experienced those events (which we can't guarantee, given our labyrinthine story tree), then those specific lines will play; otherwise, the encounter’s default lines will play.
This flexibility is key to making our story work, as it allows our writers to easily add the one-off dialogue bits that help tie nodes in our story graph to the various paths that could have taken the player there, helping our story feel cohesive in spite of its crazy branching.