Procedural quests for a dynamic world

Interesting and procedurally generated quests are something of a holy grail for many roguelike developers. I've also given it some thought and here's a simple idea I came up with.

Basically, if you have a catalogue of possible quests and you have an event based architecture, then each quest type would have it's own saga. That saga would listen to domain events and when the preconditions were right, it would add the quest to a quest giver. By talking to a quest giver the player, or any other actor, could accept the quest. When the saga receives the right domain event, the quest is over and everyone undertaking the event is rewarded or notified as appropriate.

Here's a concrete example I'll call a Lost Heirloom quest.

1. A LostHeirloomSaga subscribes to certain events like PersonMoved (while fleeing or confused) or ItemStolenFromPerson. As a response to those events, it may create a LoseItem command with a reference to the person and item.
2. Some command handler causes the target of the LoseItem command to drop the item (if it wasn't already stolen) and create an ItemLost event with references to the person, the location, the time, the item, and the reason why.
3. The LostHeirloomSaga listens to ItemLost events and when it handles the event, the person who dropped the item is given a LostHeirloomQuest and can ask others to accept it.
4. When the player talks to that person they can accept that quest. The details from the LostItem event can be used to create the quest specific rewards and text. Imagine talking to URIST McURIST the WOODCUTTER when he says "TWO WEEKS ago I was CUTTING WOOD in the DARK FOREST and was attacked by a GIANT BEETLE. While fleeing for my life, I dropped my McURIST FAMLIY WATCH. If you find it and return it, I'll give you my spare WOODCUTTER'S AXE and a PASS TO THE WOODCUTTER'S GUILD."
5. The LostHeirloomSaga also listens to ItemGiven events. When the item that was given matches a lost item and the person it was given to matches the person who lost it, the associated quest is completed and the person who gave the item is rewarded.
6. If a CreatureDied event for the quest giver happened, an ItemDestroyed event for the lost item, or some other quest-canceling event happens, then the LostHeirloomSaga cancels that creature's quest and everything else is cleaned up appropriately.
7. For extra awesomeness, when the saga notices other events related to the item (like ItemSold or ItemPickedUp), it could somehow add details to the world about it. Maybe the town's gossipmonger would tell you rumors about how the local blacksmith found a family watch in the dark forest. You could then talk to the blacksmith to find out what happened to it or you could sneak through his stuff when he's not looking.

Implementing this quest means adding a few classes: a LoseItem command, a method to handle that command, a ItemLost event, a LostHeirloomQuest, and a LostHeirloomSaga. The neat thing is that no existing classes need to be updated except for making sure the quest saga subscribes to the right events - all the logic is contained in the command handler and LostHeirloomSaga. The LostHeirloomSaga can use details of the quest giver to create dynamic and relevant details about what was lost, how it was lost, and when and where it was lost as well as a reward appropriate for the quest giver and the location and value of the lost item.

The real emergent behavior comes from quests that play off of events generated by other quests. If each quest can be ended two or three different ways, each quest directly or indirectly involves affecting the world, and there are multiple actors giving or accepting quests, then a complex chain of events could cause gathering firewood to lead to the downfall of a civilization.

• Perhaps LostHeirloomQuestCompleted events please the god of compassion who may give the quest completer a Help The Townfolk quest.
• Perhaps when a Rescue Princess quest is ended by the princess dying, her family creates a Kill Person quest targeting the killer and a Revenge quest against every group the killer was a member of. When a Rescue Princess quest is ended by the princess returning home, her family rewards whoever escorted her and every group the escort is a member of.
• Perhaps 10 Expand Influence quests must be completed before a size 3 town can become size 4. Whenever an Expand Influence quest is completed, nearby paranoid town mayors become nervous and may create an Attack Town quest or Assassinate Ruler quest targeting their rival neighbors. When an Attack Town quest is completed, the targeted town's mayor can give Strengthen Defenses and retaliatory Attack Town quests. Undertaking either requires buying resources from the market and if a market trader's goods are running low then he could create Gather Resource quests. Of course gathering resources in your neighbor's territory will cause them to hand out quests to get you to stop; by bribery, trade, or sword and shield.

This, right now, is just idle speculation but I think this could be done. By relying on domain events and sagas, new quests can be implemented without muddying up the existing code since it doesn't even need to be touched. By relying on specific details of the people and places creating the events, compelling and believable quests can be generated. And by relying on quests that build on domain events raised as part of attempting other quests, an interdependent and dynamic history following simple laws of cause and effect can be created. I'll have to create a proof of concept some time.

Java multimethods for a simple command handler

I came up with a simple way to have an event handler easily handle multiple types. It's basically a way to say a class implements Handle<DomainEvent1>, Handle<DomainEvent2>, which works fine in C# but doesn't work in java due to type erasure. My solution: reflection based multiple dispatch. I'm sure others have done this before so it's nothing new.

public abstract class Handler {

 public void handle(Object message) {
  multipleDispatch(message);
 }

 private void multipleDispatch(Object message) {
  try {
   this.getClass().getMethod("handle", message.getClass()).invoke(this, message);
  } catch (IllegalArgumentException e) {
   e.printStackTrace();
  } catch (SecurityException e) {
   e.printStackTrace();
  } catch (IllegalAccessException e) {
   e.printStackTrace();
  } catch (InvocationTargetException e) {
   e.printStackTrace();
  } catch (NoSuchMethodException e) {
   ;
  }
 }
}

Not a good idea for high-performance applications and possibly not a good idea for any app. When you send a message to a class that extends Handler then the correct method will get called if it is capable of handling it. If you use a specific type then the specific method is called like normal, otherwise this multiple dispatcher tries to call the correct method.

My summary of CQRS and DDD

Recent epiphany: sagas are just ways to turn domain events into commands.

Here's my as-of-now summary of the concepts I see in many EventSourcing, CQRS, and DDD videos and blog posts.

Command: A simple message that represents a user's request to make something happen. Just data with no behavior and often named in the imperative tense.

class CloseAccount implements Command
{
  public AccountId accountId;
  public String reason;
 
  public CloseAccount(AccountId accountId, String reason){
    this.accountId = accountId;
    this.reason = reason;
  }
}

CommandHandler: A domain service that turns a command into events by calling methods on an aggregate root, publishes the resulting events, and handles transactions and persistence. Stateless with just behavior; just a task based method and sort of procedural.

class AccountCommandHandler extends CommandHandler
{
  private AccountRepository _repository;
  private MessageBus _messageBus;
 
  public AccountCommandHandler(AccountRepository repository, MessageBus messageBus){
    this._repository = repository;
    this._messageBus = messageBus;
  }
 
  public void handle(CloseAccount command){
    Account account = _repository.get(command.accountId);

    account.close(command.reason);
  
    persistAndPublishEvents(account);
  }
}

Aggregate Root: A persistent domain object that turns method calls into domain events. May contain references to other domain objects as part of a parent/child relationship. Stateful and behaviorful and guaranteed to be internally consistent.

class Account extends Aggregate
{
  private AccountId id;

  public Account(AccountId id){
    this.id = id;
    super.storeEvent(new AccountCreated(this.id));
  }

  public void Close(CloseReason reason){
    super.storeEvent(new AccountClosed(this.id, reason));
  }
}

Domain Event: A simple message that represents a change to the state of an aggregate. Just data with no behavior and often named in the past tense.

class AccountClosed implements DomainEvent
{
  public AccountId accountId;
  public CloseReason reason;
 
  public AccountClosed(AccountId id, CloseReason reason){
    this.accountId = id;
    this.reason = reason;
  }
}

MessageBus: A mechanism for publishing commands and events and subscribing handlers to commands and events. May be a separate EventBus and CommandBus. The only behavior is publishing events and subscribing event and command handlers to events; the only state is what's required to track which services have subscribed to which events.

public class SimplestEventBus implements EventBus
{
  private List<Handler> handlers = new ArrayList<Handler>();
  
  public void subscribe(Handler handler)
  {
    handlers.add(handler);
  }
  
  public void publish(DomainEvent event)
  {
    for (Handler handler : handlers)
      handler.handle(event);
  }
}

Saga: A persistent object that turns domain events into commands. Stateful and behaviorful. The only state is what's required for knowing when to create the commands.

// Send a notice to the account's owner once the account is
// both paid off and closed. (ignore thread safety since this is a simple example)
class OwnerNotificationSaga implements Saga
{
  private AccountRepository _repository;
  private MessageBus _messageBus;
 
  private List<Account> closedAccounts = new ArrayList<Account>();
  private List<Account> paidOffAccounts = new ArrayList<Account>();
 
  public OwnerNotificationSaga(AccountRepository repository, MessageBus messageBus){
    this._repository = repository;
    this._messageBus = messageBus;
  }
 
  public void handle(AccountClosed event){
    Account account = _repository.get(event.accountId);
  
    if (closedAccounts.contains(account))
      return;
  
    if (paidOffAccounts.contains(account)){
      sendNotice(account);
      paidOffAccounts.remove(account);
    } else {
      closedAccounts.add(account);
    }
  }
 
  public void handle(AccountPaidOff event){
    Account account = _repository.get(event.accountId);
  
    if (paidOffAccounts.contains(account))
      return;
  
    if (closedAccounts.contains(account)){
      sendNotice(account);
      closedAccounts.remove(account);
    } else {
      paidOffAccounts.add(account);
    }
  }
 
  private void sendNotice(Account account){
    _messageBus.publish(new NotifyOwner(account.ownerId));
  }
}

So, for many of the examples I've seen, a user creates Commands that are handed to a MessageBus that dispatches it to a subscribed CommandHandler. The CommandHandler loads the relevant Aggregate and calls methods on it. The resulting events are gathered, persisted (if doing Event Sourcing), and passed to the MessageBus. The subscribers to that event will often update some read model (effectively turning domain events into updates on report tables) but they may be Sagas that track events and create related commands when necessary.

None of that is the essence of DDD or the essence of CQRS, but it's so common to the discussions and examples that this little glossary helps me to keep things straight.

The simplest typesafe EventBus

I'm a big fan of typesafety so while exploring messaging and events, I've also tried my own typesafe EventBus:

public static class EventBus
{
  private static Dictionary<Type, List<Action<object>>> handlers 
      = new Dictionary<Type, List<Action<object>>>();
  
  public static void Subscribe<T>(Action<T> handler){
    if (!handlers.ContainsKey(typeof(T)))
      handlers.Add(typeof(T), new List<Action<object>>());
   
    handlers[typeof(T)].Add(e => handler((T)e));
  }
  
  public static void Publish<T>(T e){
    var eventType = typeof(T);
   
    foreach (Type handlerType in handlers.Keys)
      TryPublishForType(handlerType, eventType, e);
  }
  
  private static void TryPublishForType(Type handlerType, Type eventType, object e){
    if (handlerType.IsAssignableFrom(eventType))
      handlers[handlerType].ForEach(handler => handler(e));
  }
}

It's very similar to the simplest event bus. I'm sure there are other ways of tracking what subscribers can handle each event but the Dictionary<Type, List<Action<object>>> works well enough. If you're not used to Haskell or C# type trickery then it may seem too complex either way but I think much of that is caused by how verbose C# tends to be.

One neat thing about typesafe event busses is that, if designed for it like this one is, they can respect the inheritance tree. That means if an Action<object> is subscribed, then it will get everything that get's published since all events are assignable to object. This also means that it is backwards compatible with the simplest EventBus. A few subscribers may need to explicitly state the event type they are interested in but if they use object as the type parameter when subscribing, then the behavior should be the same.

The simplest EventBus

I've been playing a lot with event buses, domain events, messaging, or whatever you want to call it. I've seen some open source event buses but they looked pretty complicated and often had a lot of extra baggage that clouded what I was interested in: exploring different ways to decouple collaborating classes. I had enough of that and set out to find the simplest thing that would get the job done and here's what I came up with:

public static class EventBus
{
  private static List<Action<object>> handlers = new List<Action<object>>();
  
  public static void Subscribe(Action<object> handler)
  {
    handlers.Add(handler);
  }
  
  public static void Publish(object e)
  {
    handlers.ForEach(handler => handler(e));
  }
}

That's it. No unsubscribing, multithreading, xml configuration, flexible dispatching strategies, subscription tokens, base classes, interfaces, or attributes. You don't have to use any specific interfaces to subscribe or publish. You don't even have to instantiate it - it's always ready. Anything can subscribe, anything can publish, from anywhere in your project. Anything can be published and every subscriber will get it. Want to publish an AccountClosed domain event? Go for it. Want to publish a naked string or int? Go ahead. How about publishing your entire Windows Form? I'm not sure why you would, but this won't stop you.

Just one line to wire-up a subscription (often called from Main):

public static void AddSubscriptions(ILogger logger, PopulationReport pop, MainApp app)
{
  EventBus.Subscribe(e => logger.Log(e.GetType().Name + ":" + e.ToString()));

  EventBus.Subscribe(app.HandleEvent);

  EventBus.Subscribe(e => {
    if (e is CreatureCreated)
      pop.CreatureCreated(((CreatureCreated)e).Creature);
    else if (e is CreatureDied)
      pop.CreatureDied(((CreatureCreated)e).Creature);
  });
}

And one line to publish (often called from domain objects):

public void Die()
{
  this.health = 0;
  EventBus.Publish(new CreatureDied(this));
}

It can be a bit on the slutty side since it's globally accessible and subscribers will get everything that's published, but that comes with benefits too. This is a good starting point and I haven't had any problems with it: the type checking is minimal for subscribers, I've never tried to subscribe a null, and I don't mind having my domain objects explicitly depend on it. You could add a ClearSubscribers method or a SetInstance method for unit testing, but I just use a single subscriber that dumps all events into a list when a unit test needs to ensure that specific events were created. In the last few at home projects I've worked on this has been the only static class I've used since this is one of the very few times that I'm in favor of a static class with behavior and state.

I find it much easier to learn about something when it's striped of all the unnecessary fluff. Event busses, domain events, messaging, whatever you want to call it is, in my mind at least, really just easy, ubiquitous, and loosely coupled communication.

From collaborator hell to dependency-free bliss

Let's say you're a developer on a C# app and just got a batch of new requirements. Let's also say that it has a fairly simple requirement: when a user closes his or her account, the account status should be set to closed. You, as a good Test Driven Developer, write your unit test, watch it fail, then add the following code to the Account class and watch your test pass:

public void Close() {
  this.Status = AccountStatus.Closed;
}

Easy-peasy.

Many weeks later you come across a requirement that says when a user closes his or her account, the account owner's IsSpecial flag should be set. To make your latest unit test pass, you do the simplest thing that could possibly work.

public void Close() {
  this.Status = Status.Closed;
  this.Owner.IsSpecial = true;
}

Your test went from Red to Green and now it's time to Refactor. Having your Account mutate some value on another object breaks encapsulation so you Control+R & E to Extract Method then Control+R & M to Move your method to the Owner class and give it a clear name.

public void Close() {
  this.Status = Status.Closed;
  this.Owner.ClosedAccount(this);
}

That's a little better. In stead of just setting some property you're now telling the other object that something happened. It's free to handle that how it wants and the Account needn't know about it - a textbook case of encapsulation and The Hollywood Principle.

You've worked in this domain long enough to know that all kinds of things are going to happen when an account is closed. Maybe the other things should be moved to a different method? Not entirely YAGNI, but modifying the account and telling others about it are two different things so you could make the argument that they should be two separate methods.

public void Close() {
  this.Status = Status.Closed;
  this.OnClosed();
}

private void OnClosed(){
  this.Owner.ClosedAccount(this);
}

It's a judgment call but this does clearly separate things. There's one method where the account modifies itself and another where all the other objects get to react to the account being updated. You know that if you have requirements that start with when an account is closed, then the code that deals with the account should go in the Close method and code that deals with other classes goes in the OnClosed method. But wait a second - doesn't this sound familiar? There's even something built into the C# language for just this scenario: events and delegates.

public delegate void ClosedEventHandler(object sender, AccountClosedEventArgs e);

public class Account {
  public event ClosedEventHandler Closed;

  public void Close() {
    this.Status = Status.Closed;

    if (this.Closed != null)
      this.Closed(this, new AccountClosedEventArgs(this));
  }
}

Now the owner can register a callback with the account's Closed event and the account can just tell whoever's listening when it has closed. The Account class no longer needs to reference the Owner class and we can rejoice.

But something about this still doesn't quite seem right. Now instead of the Account telling the Owner, the Owner has to listen to the Account. You still have one class directly referencing and depending on another - you just switched the dependency direction. A day or two later you remember you once read something about Messaging and Domain Events so you look it up and get that started.

public void Close() {
  this.Status = Status.Closed;
  EventBus.Publish(new AccountClosed(this));
}


/* ... elsewhere ... */
public class AccountClosed{
  public Account Account { get; set; }

  public AccountClosed(Account account){
    this.account = account;
  }
}


/* ... elsewhere ... */
class AccountEventsHandler {

  private IRepository repository;

  public AccountEventsHandler(IRepository repository){
    this.repository = repository;
  }

  public void Handle(AccountClosed e){
    this.repository.GetOwner(e.Account).IsSpecial = true;
  }
}


/* ... elsewhere ... */
public void WireEverythingTogether(IRepository repository){
  var accountHandler = new AccountEventsHandler(repository);
  EventBus.Subscribe<AccountClosed>(accountHandler.Handle);
}

Much nicer. Not only is the dependency completely removed from the Account and Owner classes, but each class no longer exposes methods that are just used for reacting to each other. The Account only modifies itself and creates events and the Owner only modifies itself and creates events. Now you have the Account depend on the EventBus and somewhere else you subscribe other classes to the appropriate events. You have a simple AccountEventsHandler that deals with coordinating other objects when the account changes so the domain objects themselves don't need to. It can be little bit more work, but it does reduce coupling and allow much cleaner domain objects. But the Account is still referencing the EventBus directly. You could use a service locator:

public void Close() {
  this.Status = Status.Closed;
  Services.Get<IEventBus>().Publish(new AccountClosed(this));
}

But the service locator can cause problems - like if an IEventBus wasn't registered - and is considered an anti-pattern by some people. You could use constructor injection to pass in the dependency instead.

public Account(IEventBus bus){
  this.eventBus = bus;
}

public void Close() {
  this.Status = Status.Closed;
  this.eventBus.Publish(new AccountClosed(this));
}

That's clean and a good use of the Dependency Inversion Principle, but maybe overkill since the EventBus is so simple and ubiquitous. Maybe hard coding a such a simple dependency is ok. In my limited experience this is an acceptable time for bending the rules and relying on a statefull static class. You will probably never hear me say that again since I hate working with static classes and singletons that have state or complex behavior. On the other hand, constructor injection is a great first step to using a Dependency Injection Container to wire up the EventBus and other dependencies.

Maybe months from now you can switch to actual full-scale event sourcing and CQRS. With command handlers, the Domain Objects create events and store them locally. Then the command handler would fetch all the events from the domain objects and pass them to the event bus; your domain objects don't even need to know about the event bus anymore since the command handler deals with that.

---

This series of slightly different ways of dealing with different objects involved in the same action is something that I've had a lot of problems with. It's all the same basic result but the important difference is in how to deal with coordinating different objects when something happens. These different designs have very different benefits and costs. The earlier examples are easy for anyone to do, easy to see exactly what happens when debugging or looking at the code, and you know exactly where to make the change: right in the method itself. The downside is that it becomes collaborator hell and all your classes quickly become so bloated that most of the class's code is actually about other classes. The classes become so interdependent that you can't change one thing without having to change everything else. Having lots of dependencies like this can also make build times suffer too. The latter examples only rely on the Event Bus, Service Locator, or Inversion Of Control Container so they are as non-dependent as possible but I can't really tell what's going to happen when the program runs. If everything is wired together with configuration in xml files or sql tables then it can also become exceedingly tedious and error prone to change. This kind of configuration becomes especially difficult if the developer's environment, qa environments, and production environments can all be configured differently. Not everyone will be familiar with or even like the event-based designs either. The whole thing is made even more confusing if different sections of the project have different ways of doing things and people mostly just do whatever they copied and pasted from - not that I've ever done that of course....