Sunday, 10 August 2008

A few Quest-ions

I'm working through implementing quests in Unangband at the moment. The core of the idea has been hanging around in the code for a while, but there's no time like the present to get them up and running.

I've gone with a data-centric as opposed to a script-centric design for quests. This may initially appear an unusual choice, because quests are implemented using scripts in so many games, but the data centric approach is common for Angband variants, and a natural fit for the way I design systems in Unangband - by building examples of the data I'm trying to model, then build a data structure, and then wrap code around it.

A quest consists of a number of stages which the player must pass through, and an event for each stage - which is a record of in-game actions required to complete the quest stage. An event is a subtle concept because it could be 'killed 7 goblins', but forms a natural accumulator as well, in that this could equally consist of 7 events of 'killed 1 goblin'. There are actually two ways that events accumulate:

a) if the game object is removed as a part of the event, we add 1 to the number of game objects counted in a separate stage which monitors the player actions contributing towards completing the quest. If this equals or exceeds the number of objects whose state we are required to modify, we complete the event for this stage.

b) if the game object is not removed, but instead has a state modified, we count the total number of objects in the game with this state modification. If this equals or exceeds the number of objects whose state we are required to modify, we complete the event for this stage.

This second type of accumulator is intended for quests where we have to 'terrify 7 goblins' instead of 'kill 7 goblins'. I can also combine the two, to allow the player to 'kill or terrify 7 goblins' by subtracting the number of type a accumulated from the number of type b required.

There are a number of problems with this approach. In particular, I have to make sure that if I've terrified a goblin, it never stops being terrified, otherwise the player will have to terrify it again. I could use this to form a natural timer for the quest, by making this a player requirement that they have to have all monsters terrified simultaneously, but it'll probably be easier just to prevent quest monsters from exiting the state required for the quest. Doing it this way ensures that the player knows which quest monsters they've already terrified, because the Afraid state is shown in the monster name and in its in-game behaviour. The alternative is to have a separate 'you've terrified this monster before' flag, which is a much harder UI problem.

But the real problem is I'm starting to recognise a particular code pattern, which I've implemented previously and has caused no end of debugging problems.

The pattern is one where I have to fire off a series of actions after modifying a variable, in every instance where that variable is modified. In this example, it's every time that a monster gets scared - I've got to check whether or not the player terrified it, and whether there's an active quest that needs to be updated as a result.

This is, of course, a classic problem of encapsulation. Instead of directly referring the variable, I should have been using an function to update the variable indirectly, which I can then use to also to check the player quest status. In order to correct this, I'll have to refactor the code to add the function in.

But even if I had anticipated this requirement in advance, I'd still face this refactorisation process. This is because I could not have correctly anticipated what information is important when updating the variable - in this instance, the fact that the player was responsible for what ever action caused the monster to be afraid. I could equally specify circumstances that are completely independent of the player and the monster: such as the fact that the Oracle might have to be at Delphi, in order for the monster terrify action to count as a quest action being completed.

The previous instance where this has caused me no end of problems is the player learning about the effects of equipment that they use, and inferring information from that. This allows for example, the player to get poisoned by a spider, put on an unknown ring, and then not get poisoned by the spider, to determine that the ring supplies poison resistance. The variable I needed to encapsulate in this instance was whether the player resists poison.

In the poisoning example, this is actually a case of premature optimisation causing me problems. In Angband, to avoid the overhead of having to test whether a player resists poison every time, we check whether the player equipment changes, and if so, update the state of 'resisting poison'. I'd still have to check whether the player equipment changes, even without this optimisation because I'd also need to update the state of 'the player knowing about what equipment they are using'.

What I really want is a generic way of specifying variable dependencies: that is, information I also have to update if a specific variable changes. I can't think of any specific programming paradigm that conveys this idea well. It's not a particularly functional or object oriented idea: because in the examples I've given, you'd have to pass the entire global environment into the function or object in order to not have to go through a refactorisation process if you needed additional information.

Does anyone have a good example of a programming language that conveys this concept well?


wtanksley said...

You're looking at a publish/subscribe situation. Smalltalk handles this well, C# has a dedicated mechanism, and JavaFX is the newest entry in the field to handle it. JavaFX uses an interesting method... It uses functions defined with a subset of the syntax in which loops are impossible to express, and the language evaluates them every time one of the watched variables changes.

VRBones said...

Observer patterns

VRBones said...

gah, beaten to the punch :P

Mikolaj said...

I agree you need to make (part of) the state of the game a black box, accessible only through an interface of a set of functions. I also agree you'll have to change the internals of the black box often and sometimes even its interface.

This way you may sometimes have to touch a lot more code than in the current global variables model. However, most the debugging problems will be gone --- the compiler itself we'll warn you about the lack of where_is_Oracle parameter, whether it's actually used at that particular place, or not.

However, as long as everything is globally visible (accessor for _every_ variable), even though encapsulated, you won't need to change the interface often or perhaps at all, I think.

Andrew Doull said...

wtanksley: Ideally I'd like something where loops are not only possible, but resolved cleanly, much as the same way as Excel resolves its dependencies.

Thanks everyone for the suggestions.

wtanksley said...

When you say "loops", do you mean "circular dependencies"? As far as I know, that's what Excel supports. If you mean "for loops", you can allow them if you want, but you leave the potential for EXTREMELY slow updates.

Anyhow, it occurs to me that Tom O'Breton, whose email I've long since lost, was working on a roguelike system which included this capability. I have _no_ idea whether he ever produced any implementation of this particular part, though.

Snut said...

I don't profess to know much about it, but it seems this would be a good case for aspect-oriented programming, were there any remotely sensible implementations of it.

I'm pretty sure there's a functional approach for this that works too, in that I'd guess a functional implementation would involve a type action -> world -> world which could be augmented to track player-caused state transitions. Actions in this sense could also be modelled with objects, and would make good candidates for observation.

But without a complete re-write in some arcane functional language (pretty much all of them IMO :P) one thing that might be worth considering is dropping a strict requirement on the player causing a certain change. For one thing without a bit of infrastructure it's hard to track 'ownership' of an event propagating through the world, and for another it may not even be possible to express certain methods of completing the quest. As an example, given the task of scaring some goblins an adventurer might take the risky but efficient path of finding a load of undead, taunting them, and then dragging them through the goblin camp. I can't think of a good way to always correctly ascribe the results of such events to the player.

So, um, I wouldn't even try. If something happens within the area of the world the player has unambiguous feedback about, it might as well count towards the quest counter. At worst this casts some questions on the scruples of the adventurer: coming upon the poor abused goblin camp, she finds a random werewolf eating the chieftain and the rest of the tribe scattering in terror, and promptly sits down with some popcorn and calls the job done.

Being lazy in this way makes the task of observing and tracking questy things a lot more tractable. I think.

VRBones said...

> So, um, I wouldn't even try. If something happens within the area of the world the player has unambiguous feedback about, it might as well count towards the quest counter.

I guess it would come down to intent of the quest. If the quest is a request from one party to get something done (they just want the goblins scared, maybe for payback, or they want batwings for potions, etc) then attribution may not matter. However if the intent is the purposeful completion of the task (such as training), or where there are competing parties (such as a bountyhunt) then attribution is vital.

I was playing FuryBand a month ago when I had to abort a game because I broke a princess quest by killing one of the guardians with poison from a pet. No stairs. Game over. So yes, attribution sucks.

In real world terms, attribution is handled by gathering proof for the quest giver. It is not enough to complete the task, but just as important to gather proof that you were the one that completed it. This may be via delivery note, possesion of items from the victim, witnesses, etc. Scaring goblins may be an instruction on how to use the spell, but may only be carried out in the sight of the instructor to count.

The absence of any way of prooving you did something may preclude some types of quests, but handing over money or items without proof isn't believable from the perspective of the quest giver.
"You scared the goblins already? You haven't even moved?"
"yeh, I have alternate dimension powers"
"O rly?"

Snut said...

However if the intent is the purposeful completion of the task (such as training), or where there are competing parties (such as a bountyhunt) then attribution is vital.

Good examples, I wasn't thinking of those other classes of quest at all..

Still, I think you nailed the quests into a few groups and the first two don't really complicate the issue:

1. Quest giver can confirm whether or not the character completed the quest by examination of the world after the fact (sending scouts to the goblin camp). In this case I think it's safe to just examine the local world state for quest triggers whilst the player goes about his/her business, without caring if they are really the player's doing or just incidental as long as the character is aware of them.

2. Confirmation by object. This is possibly the easiest type of quest to track and implement, which is I guess why every RPG ever has used it. Added bonus is that it doesn't necessarily matter where or when the item was really sourced; if you poison the bounty hunter's beer and steal his bag of bandit heads and orc tusks, you can go claim the reward. Ambush the messenger and claim the delivery note. Slaughter the goblins and take their ears on your way into town before being aware of the bounty. And so on. Doesn't need any examination of the global world state, just the character inventory.

3. Confirmation by witness. Kind of hard, and made a lot more complex if you have a watchful pantheon and you consider paladins or virtuous priests to be always under inspection by either a deity or their own conscience. Quests that might draw the attention of one or more gods may also be 'witnessed', I suppose. I suspect that only simple events or chains of events that can be attributed unambiguously can ever work in such cases, with the added requirement that all events involved must be within sensory range of the witness. I might consider special-casing for training courses etc, and otherwise ignoring this category :)

I'm sure there must be some others, but all of the quests I recall from other games fall into the first couple of categories...

wtanksley said...

I second the point about Aspect Orientation... Thanks for bringing that up; this is pretty much by definition the purpose of AOP.

Robert said...

Could you do it this way?

Whenever a player is poisoned, every piece of equipment with possibly unknown properties gains the property known-not-to-confer-poison-resistance.

When the player resists poison, each piece of equipment with possibly unknown properties, except those already known not to confer poison resistance, gains the property may-confer-poison-resistance. If there is only one, we give it the property known-to-confer-poison-resistance.