Followers, spoken commands, and quests

I think I've found something that hasn't been done that could add a lot to roguelikes: spoken commands. You type what you want your followers to do and they do it. Instead of having a complex AI that handles the entire english language, you could focus on a few things that could be combined in different ways. If you have many people following these commands then you and your rag-tag team of adventurers could really change the world.

Here's a simple command syntax that I have in mind:

  <target> <verb> [<objects>] [<preposition clauses>]

target is an optional person or group you are talking to: healer, fighters, Bob, Joe, etc.

verb is one of a dozen or so supported verbs: attack, defend, go, pickup, drop, help, etc.

objects are the people, places, or things directly involved with the verb: a sword, goblins, me, the desert, home, etc.

preposition clauses are optional clauses that constrain the verb: in <location>, with <item>, etc.

The prepositions are where the real flexibility and power come from since you can specify where something should happen, what should be used, or whatever else makes sense. The verbs, people, places, things, and prepositions would be whatever is appropriate to the game; resource gathering, squad maneuvers, mixing potions, social intrigue, whatever you can think of.

Turning the spoken words into commands would be three steps:

1. Normalize the sentence, removing fluff words and changing synonyms (protect -> defend)
2. Parse the sentence
3. Correct the prepositions and objects if necessary

As an example, Miners, give the blacksmith ore from the mines would be normalized into

 miners give blacksmith ore from mines which would be parsed into this:

 target = miners

 verb = give

 objects = blacksmith, ore

 prepositions = from mines

The correction phase would be necessary in this example since the "give" verb requires the verb's object to be a thing and requires a "to <person>" prepositional clause. "blacksmith" is a person and "ore" is a thing so "blacksmith" should be the "to" prepositional clause and "ore" should remain as the verb's object. The corrected interpretation is:

 target = miners

 verb = give

 objects = ore

 prepositions = from mines, to blacksmith

or miners give ore from mines to blacksmith

So the miners who hear this would get ore from the mines and give it to the blacksmith.

Some other example commands:

 healer, help the villagers at home

 kill the goblins in the dark forest with spears

 Urist, craft a sword with steel at the master's forge

 guards, escort the prince from the castle to the fort

There seems to be a deep similarity between commands and quests. Even my example Lost Heirloom Quest could be seen as a command: player, give the McUrist family watch from the dark forest to Urist McUrist. Since the NPCs can follow commands, and commands and quests are the same, then they should be able to follow quests. Also; since the player can give commands, the player is also giving quests. Imagine a world with a few hundred NPCs running around trying to fulfill quests and giving quests to others when appropriate.

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.

Procedurally generated puzzles

Just jotting down some informal thoughts on types of puzzles and how to proceduraly generate them. Each puzzle is really a barrier that you must overcome to get to the other side. Place a puzzle when you need a barrier to seperate zones, protect treasure, or just to keep things interesting.


Minigames. Reminds me of the Wii party games where whichever team gets the best overall score after 5 events wins the tournament. Slider puzzles, tower of hanoi, checkers, gambling, etc. It would take time to code each one but it would also break up the monotony. You could also make the real game a metagame of the minigames. Imagine everyone in the game is obsessed with a collectable card game. By finding new cards in the game world you improve your chances of winning the card minigame, which could lead to rewards that improve your chances of the real game. Done right it would be interesting and fun diversion; done wrongly it would be a tedious and required waste of time.

(days later) I just remembered that Star Wars: Knights Of The Old Republic had this with Pazaak! I was thinking more along the lines of a Magic The Gathering type minigame, but a poker-blackjack hybrid is a good idea too. Neat! Proof that my idea works!

Logic mazes. Reminds me of many games where you have to move like a knight on a giant chess board or slide across the ice in just the right pattern to make it to the other side. For these puzzles you must go from here to there but you must follow a certain way of moving. I think these would be easier to make in reverse. For example, start with an impassible expanse of ice. Start at the end point. Pick a direction and place a block in that neighboring cell. Move the opposite direction a few spaces. Repeat several times, making sure not to place blocks in areas the player will need to later pass through, and you end up with an end point, a start point, and at least one way to move from the start to the end. There are many more examples of logic mazes at http://www.mazelog.com/.

Inventory based. Reminds me of Metroidvania games. You must have a certain item or ability in order to pass. A locked door requires a key, a hall of spikes requires the spike armor, cracked walls require bombs. Basically there's some sort of "lock" and some sort of inventory "key" is required to pass. To place an inventory based puzzle, simply pick something from a preset table of a "lock" and item "key" and place the key somewhere before the lock. Or pick a random item from the world as the key: "The burly guard won't let you pass until you give him A HAM SANDWICH."


Knowledge based. Reminds me of Myst. You must answer a question or enter the correct sequence to pass. A combination lock where the randomized combination is written down elsewhere or a guard who asks you questions that you would only know from reading books in the game or talking to people in the game. Like the inventory puzzles, simply pick something from a preset table of a "lock" and an information "key" and place the randomly generated key somewhere before the lock.


Environment based. Reminds me of many sub puzzles in modern Zelda games. You must change the environment to a certain state before you can pass. Pull the lever to open a door, push all 4 buttons to lower the bridge, set all 6 torches on fire to open the treasure chest, redirect the laser to destroy the statue. This could be a superset of sokoban puzzles which are really just "push the blocks into the marked places". If you look at it a certain way, the requirements or triggers could even involve other people or groups: the king must be dead, the mages guild must be at war with the fighters guild, the price of milk must be low, the senate must be mostly of the Merchant's Alliance, etc.



These puzzles can be combined to form larger and more intricate puzzles:

To get the treasure chest you must push all four buttons

• to push button 1 you just walk over and push it
• to push button 2 you must cross a bottomless pit
• to cross the pit you must purchace Flying Boots or know how to teleport
• to push button 3 you must open the giant door
• to open the door you must find and reassemble the 2 gears to the door machinery
• gear 1 is on the other side of a giant randomized sokoban puzzle
• gear 2 is buried at a random location
• shovels can be purchaced at stores
• the location is on a map you find in the dungeon
• reassembling the gears is a slider puzzle
• to push button 4 you must defeat the guardian with a special sword and a special shield 
• to get the special sword you must help the dying king
• the king will give you the sword if you give him an elixer of life that no one knows how to make
• the recipe is randomly generated but written in a recipie book - or you could just start mixing things and get lucky
• to get the special shield you must play the specific melody on the piano
• the notes of the randomized melody are written on the wall of another room

You could create a puzzle like this at each dungeon or important location or create one giant puzzle that includes all the major locations in the game world.

Ideas like this aren't worth much unless actually implemented though. I'll have to create some proof of concept or even a roguelike that has puzzles like this in it. One of these days.

Problems, solutions, and sandwiches

Let's say you have a screwdriver and you happen upon a loose screw that needs to be tightened. Using the screwdriver to fix the loose screw seems like a pretty good idea - and it probably is.

Now you happen to have a loose nail that needs to be fixed. You know you should use a hammer, but if you're really lazy, don't have enough time to fetch a hammer, or if someone else insists on it, then you could probably bang the nail in with your screwdriver. Yes, it won't work as well as a hammer, you may damage the screwdriver, and you may hurt yourself, but at the end of the day you will have fixed the loose nail. You can then go home with a banged up screwdriver and sore hand and wish you could do it the right way. Not ideal, but it happens from time to time.

Now you happen to have an empty stomach. You really should eat a sandwich but instead you reach for your screwdriver. Why? Maybe everyone keeps talking about using a screwdriver so you go along. Maybe someone doesn't realize that even though sandwich and screwdriver have many letters in common, they're not the same. Or maybe you happen to have the screwdriver in your hand and really think it can help. For whatever reason, you, or someone else, decides that eating your screwdriver is a perfectly acceptable way to fix your empty stomach. Despite your best efforts and after several days or weeks, the best you can hope for is a broken screwdriver and several broken teeth. And you still have an empty stomach.

---

This may or may not be a thinly disguised allegory for certain events that may or may not happen when programming on projects that involve several other people and hard deadlines. This has been one of the most difficult things for me to deal with.

A possible algorithm for Zeldalike overworlds

The 2012 7DRL challenge is one month away!


I've been thinking about how to procedurally create a Zeldalike map for a roguelike. By Zeldalike I mean the important parts that I remember from playing the original Zelda game: it was broken into screen-sized chunks, everywhere was reachable (although sometimes you had to get an item first), there were different themed areas, it wasn't too dense or too sparse - it was interesting, charming, and fun.


Here's an algorithm that should come up with something interesting like Zelda's overworld Hyrule. It creates one array of tiles and one array with details about each screen-sized chunk of the world.

Since the world will be broken into screen sized chunks, we can start by determining how those screens will be connected. Let's start with a 16x5 array of screens that have no connections to any neighbors. This is a high-level view of the world. If you were to print it out, it may look something like this where each screen is represented as a blank space and the walls between them are solid spaces.	################################# # # # # # # # # # # # # # # # # # ################################# # # # # # # # # # # # # # # # # # ################################# # # # # # # # # # # # # # # # # # ################################# # # # # # # # # # # # # # # # # # ################################# # # # # # # # # # # # # # # # # # #################################
With the array of screens, create a simple perfect maze. When printing out how the screens are connected to make a big maze, it would look something like this. We can see that this time, the top left screen has an open path to the screen to the east. After traveling east a few screens, you can go south.	################################# # # # ####### ### ##### ############### # # # # # # # ### # # ######### # ### ### # # # # # # # # # # # ### # # ####### ### # ##### # # # # # # # # # # # # # # ##### # # ############# # # # # # # # # # # # #################################
Remove some of the walls to connect screens. There are now loops and many ways to move around. Now when traveling east from the top left screen you can go south on the second screen or continue to the fourth screen and go south.	################################# # # # ### ### ### ##### # # ########### # # # # # ### # # ######### # ### ### # # # # # # # # # # ### # # ####### ### # ##### # # # # # # # # # # # # # # ##### # # ############# # # # # # # # # # # # #################################
Assign themes to some of the screens. I'm just using 1 through 5 as arbitrary themes. They could be like the original zelda: brown rock, green rock, brown forest, green forest, cemetary, etc or they could be your own themes.	################################# # 1 # 2 3 # ### ### ### ##### # # ########### # 4# 4 # # # ### # # ######### # ### ### # # # # # 1# # # # # ### # # ####### ### # ##### # # # # #5# 3 5# # 2# # # # # # ##### # # ############# # # # # # # # # # # # #################################
Spread the themes to adjacent screens that are connected.	################################# #1 1 1 4#2 2 3 3 # ### ### ### ##### # # ########### # 1 4 4# 2 4 4 # # # ### # # ######### # ### ### # # # # 5 #3 1# # # # # ### # # ####### ### # ##### # # # # #5# 3 3 5# # 2 2# # # # # # ##### # # ############# # # # # # # # # # # # #################################
Continue spreading them until all screens have a theme. This ensures that the themes match the path that the player has to walk through and the user should feel like they spend some time in each theme before entering a different one.	################################# #1 1 1 4#2 2 3 3 3 3 3 3 3 3 3 3# ### ### ### ##### # # ########### #1 1 4 4#2 2 4 4 4 4 4 2 2 2 2 2# # # ### # # ######### # ### ### # #1#1#5 5 5 2 2 2#3 1#4#2 2 2 2#2# # ### # # ####### ### # ##### # # #1#5 5#5#5 3 3 3 3 5#4#2 2 2#2#2# # # # ##### # # ############# # # #1#5#5 5#3 3#3#3 3 3 3 3 3 3#2#2# #################################

#####################&&&&&&&********* # ## ## #& &* ** # 1 ## 1 ## 1 #& 4 &* 2 ** # ## ## #& &* ** #####################&&&&&&&********* ##############&&&&&&&&&&&&&&********* # ## #& && &* ** # 1 ## 1 #& 4 && 4 &* 2 ** # ## #& && &* ** ##############&&&&&&&&&&&&&&********* ##############%%%%%%%%%%%%%%%%%%%%%%% # ## #% %% %% %% # 1 ## 1 #% 5 %% 5 %% 5 %% # ## #% %% %% %% ##############%%%%%%%%%%%%%%%%%%%%%%% #######%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% # #% %% %% %% %%	Now we can build the real world map based on the array of screens created in the earlier part. For each cell in the array of screens, plop down a screen sized chunk in the world array. For this example I'll make each screen 7x5 tiles large and just show the top left few screens but a real game would have much larger screens. I will also put the theme number and use different border tiles for each theme.
#####################&&&&&&&********* # ## ## #& &* ** # 1 1 1 4 &* 2 # ## ## #& &* ** ########## ##########&&& &&&********* ########## ###&&&&&&&&&& &&&********* # ## #& && &* ** # 1 1 4 4 &* 2 # ## #& && &* ** ### ###### ###&&&&&&&&&& &&&*** ***** ### ###### ###%%%%%%%%%% %%%%%% %%%%% # ## #% %% %% %% # 1 ## 1 #% 5 5 5 # ## #% %% %% %% ### ##########%%% %%%%%% %%%%%% %%%%% ### ###%%%%%%%%%% %%%%%% %%%%%% %%%%% # #% %% %% %% %%	Then remove the walls for screens that should be connected. It would be easiest to always remove the one or two center blocks from a wall that separates connected screens but you could also make a wider path, a path at a different spot, or multiple paths between two screens. That would add variety but the screens are too small to do that here. After this, we have a themed maze to walk around in based on the array of screens.
#####################&&&&&&&********* # ## ### ##& & & &* $ $ ** # $ # # &* # ## ### ##& & & &* $ $ ** ########## ##########&&& &&&********* ########## ###&&&&&&&&&& &&&********* ######## #& &&# #&* ** ### &&& ? &* ### #### #& &&# #&* ** ### ###### ###&&&&&&&&&& &&&*** ***** ### ###### ###%%%%%%%%%% %%%%%% %%%%% ## #### ##%% %%% %% %% # # ### ##% *** ! ## ####!$!##%% %%% %% %% ### ##########%%% %%%%%% %%%%%% %%%%% ### ###%%%%%%%%%% %%%%%% %%%%%% %%%%% #% %#%%%%%%%% %% %% %%	Randomly select different things to fill the screens with based on its theme: a center lake, small blocks of rock, rows of tree's, bordering trees, statues, etc. You could also have special things that only appear at dead ends: temples, towns, caves, treasure, bosses, puzzles, etc. Putting things at the dead ends makes it worth the time spent getting there - a good idea since most players hate dead ends and mazes in general. Secret areas and bad guys could also be placed now.
#####################&&&&&&&********* # ## ### ##& & & &* $ $ ** # $ # # &* # ## ### ##& & ~~~~~~ $ ** ########## ##########&&& ~~~~~~****** ########## ###&&&&&&&&&& ~~~~~~****** ######## #& &&# ~~~~~~ ** ~~# &&& ? &* ~~# #### #& &&# #&* ** ~~# ###### ###&&&&&&&&&& &&&*** ***** ~~# ###### ###%%%%%%%%%% %%%%%% %%%%% ~~ #### ##%% %%% %% %% ~~ # ### ##% *** ! ~~ ####!$!##%% %%% %% %% ~~# ##########%%% %%%%%% %%%%%% %%%%% ~~# ###%%%%%%%%%% %%%%%% %%%%%% %%%%% ~~ %#%%%%%%%% %% %% %%	Hyrule had shore lines along some the edges and small lakes at the corner of four screens. You can add those too.
#####################&&&&&&&********* # ## ### ##& & & &* $ $ ** # $ # # &* # ## ### ##& & ~~~~~~ $ ** ########## ##########&&& ~~~~~~****** ########## ###&&&&&&&&&& ~~~~~~****** ######## #& &&# ~~~~~~ ** ~~# &&& ? ~&* ~~# #### #& &&# ~&* ** ~~# ###### ###&&&&&&&&&& &~&*** ***** ~~# ###### ###%%%%%%%%%% %~%%%% %%%%% ~~~=~~~~~~=~~~~~~~~~~~~~=~~%% %% ~~ ### ##% * * ! ~~ ####!$!##%% %%% %% %% ~~# ##########%%% %%%%%% %%%%%% %%%%% ~~# ###%%%%%%%%%% %%%%%% %%%%%% %%%%% ~~ %#%%%%%%%% %% %% %%	Rivers could connect some of the lakes to the edges. It would be necessary to place bridges if the river is cutting off a path that used to be passable. A final step could involve looking at each screen or tile in the world and placing more treasure, creatures, or structures at interesting points.

I haven't implemented this yet so I'm not sure if this will really work or not. I'm also not sure how difficult this will be or how fun the results will be. It's something I haven't seen in any roguelike or non-Zelda game and if each screen has something interesting then it should avoid having long spans of time where all you do is walk around. I will probably use this for my entry into the 2012 7DRL challenge.

2011 7DRL re-retrospective

I'm really looking forward to the 2012 7DRL next month and I've got a lot of ideas I want to try out. I rechecked the scores I got for my entry last year to see when I should focus this time. I'm quite happy with the scores for my 2011 entry but I think I can do better this time.

Here's what my 2011 entry Twelve Hours got:

Completeness: Bug free, polished game with no features that feel like they are missing.
2.67 - My highest score. I've got a much better idea of what I want this time, some ways of reducing memory and CPU usage, and some time set aside to add polish so I expect to get a 2.67 or 3.00 this time.

Aesthetics: Good looking, excellent controls and UI.
2.33 - A pretty good score; probably from the clean UI, few commands, and standard ASCII visuals. Less garish colors and a few small animations should help improve the aesthetics.

Fun: If you try any 7DRLs, try this one.
2.33 - One reviewer said: "Would be nice to have better control over your companions."Yup. I want to avoid having total control but I agree that more influence and interaction with others could add much more fun. Adding some humor and a more heroic feel won't hurt either. A 3.00 would be nearly impossible but I hope I could get a 2.67.

Innovation: Brings something fundamentally new to roguelikes.
2.00 - Reviewer: "Survive timer, goal other than finding the powerful artifact, inventory-less." My lowest score. I don't know about "fundamentally new" but I've got a few new ideas up my sleeve this year....

Scope: Beyond what you think could have been done in seven days.
2.33 - Fair enough. I was unfocused for the first few days so it was less than 7 days of useful work. I've got a long list of ideas in my head this time so I hope to have much more in the game this year.

Roguelike: 3 means Roguelike, 2 means Roguelike-like, 1 means Not Roguelike.
2.67 - "misses some points for tactical polish." Agreed. I've got some ideas and expect a 3.00 this time.

Average

2.39 - Not a bad score - not bad at all. I did better than I thought I would but this year I'd like at least a 2.50. By looking at last year's entries, this seems to be a very difficult and rare thing. On the other hand, if one reviewer had given me one more point my average would have been 2.59 so I think 2.50 is reasonable for 2012.

I think most of my posts for February and March will be about roguelikes. Ideas, implementations, and random musings and rants.

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.