A new direction

Happy Camper Studios is taking a new direction.  We’ve teamed up with Boldly Games and will be operating under their banner from now on.  This does unfortunately mean that work on Star Ship Story will be ceasing, at least for the meantime.  We discussed the possibility of continuing the project under the Boldly Games name, but the product’s trajectory combined with our combined goals don’t quite match up.  We are working on an exciting new project that will be announced fairly soon over at the Boldly Games website so check in there or on the Facebook page.  The good news is that with our powers combined we can tackle some really exciting game possibilities!

2014 development update

Despite all evidence to the contrary, Star Ship Story’s development is alive and well in 2014.  Since the last update much has changed, but the design is now on a very solid footing overall.  Also, as you probably could have guessed, it looks nothing like the previous iteration.

galaxy 2014-02-10Before I get into what exactly has changed I should really go over the big picture structure of Star Ship Story (SSS hereafter) and how these changes fit in.  At the beginning of a game, you will be presented with a ship, its crew, and your current situation as that crew.  Think of this like a one-off pen and paper RPG session.  The GM (in this case the game) has come up with a story for you and has created all the characters for you to play as.  In the case of SSS, the characters are not randomly generated but your ship is chosen from a pool of hand authored ships, any of which can potentially star in, be the antagonist for, or make an appearance in any story.  So out of the big pool of all of the characters in the galaxy, your ship with its crew is selected.  Next you choose who you as an individual want to play as.  This assigns you a role such as Tactical (goes pew pew), Helm (goes whoooosh!), Engineering (gets yelled at by her entire team for not keeping everything repaired all the time), or Science (tells everyone we’re about to die as they’ve just locked on to us with their mega super laser).  Once you’re settled in as a crew, the game will then present to you the details of your objective.  Since you’ve taken on the role of this crew, you’re not out to do just anything, this crew has an agenda.

With that in place, you’re off!  The story generator has decided how your crew will go about trying to accomplish their objective.  Of course a story without any obstacles is rather boring, so at (in)opportune times various kinks in the plan will develop.  Your engines will break down (whether via sabotage, bad luck, or another mysterious force you don’t know), you will receive a distress call, you will be attacked by pirates, well you get the idea.  At these points your crew now can decide how to proceed.  Are you a mighty Imperial vessel charged with policing and protecting the people of this sector?  Probably would be a good idea to answer that distress call.  Are you a tramp freighter 3 days out from the biggest payoff of your life?  Distress calls like that are often used in this sector by pirates.  What’s that?  It’s a ship we know and they’re calling in that favor we owe them?  Hmmmm.

"Programmer art" version of the minigame

“Programmer art” version of the minigame

Whatever happens along the way, at some point it will be necessary to resolve how well you do in the face of your challenge.  This is the point in a tabletop RPG when you will typically roll some dice, consult a character sheet, add some modifiers and then wait for the storyteller to resolve all the action.  This being a video game, we resolve such matters interactively.  Specifically in SSS via a minigame that many of you will recognize as a match-3 style game.  This is not a Bejeweled clone though, the gameplay is much closer to the multiple swaps per turn style of Puzzle and Dragon.  This style doesn’t make the game just a wee bit more tactical and complex, it makes the game a LOT more sophisticated, but without adding any complexity for beginning players.  The bottom line is, if you’re just starting out you can play it just like Bejeweled, and as you get more comfortable with the game you will start to discover lots of cool things you can do to really boost the points that you’re generating.

Speaking of points, there’s no score shown anywhere.  Fighting an opponent and getting 1,273 points while they score 1,342 seems pretty anti-climactic.  Points are all handled behind the scenes and generate the power for your abilities (in the screenshot to the left this would be Pulse Lsr, Heavy Lsr, Evade, and Scan).  Once an ability is charge up as the Pulse Laser is on the left, you can fire it at your opponent by simply dragging from the ability to the part of the enemy ship you want to hit.  In the current build the systems that a ship can have are Hull (every ship has this), Engines, Weapons, and Sensors.  As soon as multiplayer is implemented any individual won’t see all the abilities at once, they’ll only see the ones that pertain to their role.  So the tactical officer would see all the weapon abilities, the helmsman would see Evade and the science officer would see Scan.  There will of course be many more abilities than these few.  If a particular ability is needed RIGHT NOW and doesn’t have the energy to activate, other players can dump some of the energy they’ve charged up on their abilities to the needed system but this comes at a price of 50 – 75% efficiency.  The engineer gets a better ratio on their transfers as well as some abilities to augment their “magical energy fairy” duties.

That’s basically where development is today.  Very soon there will be lots of things to interact with on your board resulting from enemy attacks as well as effects from your own abilities.  Of course this is all just “programmer art” and the real art treatment is still coming.  There are also a lot of missing bits like seeing the ships firing at each other (currently you just see the systems change color when damaged), and proper icons for the abilities, etc.

TIGJam and Star. Ship. Story. progress

Last weekend I attended TIGJam 5 in Mountain View, CA. It is 4 day gathering of indie game developers of all sorts, from students to working professionals to big name indie superstars. It was a fantastic mix of people to talk to, go out to eat with and jam alongside. I took this time to implement some rather large changes to SSS that I have been working on the past 2 months.

While working on the story generation side of the game which necessitated the research outlined in my previous posts on PDDL and AI planners, I started to run into some contradictory forces at work in SSS.  I had begun my work on the real time multiplayer combat part of the game.  That part was the most fully formed in my mind, and when I started the project, it was the primary focus.  Only later did the group decision making in the overall context of galavanting around a galaxy begin to become much more important to the overall design.  So it was with much hand wringing that I set aside 5 months of work and some pretty nicely performing network code to take a step back and think about the big picture.  Of course I could have thought about all this ahead of time, but it never seems to actually work out that way, does it?

SSS was always intended to be a game you can play with your non-gamer friends.  When I looked at the system I was creating, it was certainly not CounterStrike or some other punishingly harsh experience, but with a bit of testing on the exact people I was making the game for, it was pretty apparent that even basic dexterity requirements were going to exclude a good chunk of non-gamers.  This is by no means a knock against those people, they simply do not have 20 years of FPS experience or other such fine motor control training with their hands that most “hardcore” gamers do.  It’s pretty humbling to remember that what we take for granted in terms of skill is pretty hard won in an adult who didn’t grow up playing Super Mario Brothers or Street Fighter.  So, I asked myself, can you have a skill based game that is devoid of dexterity challenges?  The answer is of course yes, we see it all over the place in the world of hobby games (if you’re not familiar with hobby gaming, look up Ticket To Ride, Settlers of Catan, Carcassonne, or Ascension which are all fine examples of the type and almost all are also available on iOS).

I have a pretty extensive background in hobby gaming, so I was very comfortable taking the game in this direction.  There are a few snags of course.  In a typical hobby game that is heavy on skill, you are controlling all the pieces.  In a typical co-op game the group wins or loses based on their reaction to die rolls or card draws that simulate the game playing its side against the players.  Since this is a video game we don’t need any of that blind opposition, the game can adapt much more precisely  which also means the players are going to need more precise actions so that they do not feel cheated out of a victory by a bad die roll.  With die rolls for resolution of events effectively off the table (but not the concept of dice in general as you will see below), I started working up some paper prototypes of how the various systems could work.  Because simultaneous resolution of actions was highly desirable to keep the game moving this was surprisingly difficult for stations such as tactical that are heavily affected by other stations such as the helm.  There have been a few board games that attempt to tackle this problem, such at Space Cadets by Geoff Engelstein (of the very excellent Ludology podcast) and the follow up Space Cadets: Dice Duel but nothing I found really felt right.  This is an odd beast, a video game that is trying keep the design considerations of a board game but remove as much of the bookkeeping and cruft that sometimes accumulates around board games, sort of how Hex is trying to be Magic: The Gathering but in digital form and thus with new opportunities.

At TIGJam I finally wanted to jump in and start getting some infrastructure in place.  I managed to build up a basic turn system and started hooking in a bit of user interface.  Here is the current mockup, only the ship movement is functional.  Pictured is the galaxy view, the ship view, and the engineering station’s view.  This is the screen of the pink player which as you can see is located at the engineering station (note the black background of the icon indicating your avatar marker).  Each turn the engineer can choose how many energy dice to draw from the engines, which produces some randomized results depending on if the energy level is green, yellow, or red.  Green die as you might assume give better results, red die have lower numbers and the potential to damage systems.  In the image below, the engineer has 6 die to distribute with each station capable of receiving 2 dice maximum.  For the next turn, the engineer has elected to draw 6 more dice (the maximum) and will get 1 green, 4 yellow, and 1 red.  The engines recharge based on the ship you are piloting, this particular ship recharges 3 per turn.

Mockup Ship UI

This is programmer prototype art and should not be taken as representative of the look of the game

Over the coming weeks I hope to continue updating screen shots as more functionality comes online.  You can fully expect all of this to change multiple times over as all the various elements that have to align get pushed, pulled, and prodded into place.

More on AI planners, metrics and plan refinement

The plan outlined in the previous post on ai planners talked about getting a basic plan that was solvable. If our concept of “optimal” lines up with the fewest possible steps, then we’re all good to go. Often though a shortest plan does not really embody what you really want the planner to value in a solution. Perhaps you want to minimize a different cost, or perhaps you want to maximize something (like a score), and a short plan, while valid, is not perhaps ideal. PDDL has a mechanism for expressing this, metrics.  A metric is simply a numeric variable (called fluents in PDDL) that can be manipulated by the various operations in your domain and then referenced to see if you’re getting closer or further away from your goal.  This can be though of somewhat as a heuristic to guide the planner, similar to your distance calculation used in A* to help pick the shortest path.

I’ve extended the domain from the previous post to include both the actions mentioned at the end (steal-ring and lose-ring). So now Sam has 2 possible ways to get the ring. To use our metric, which we will call total-cost for now, we simply need to add a “function” to the domain.  Now this isn’t a function in the “has input and output” ala most programming contexts.  I’m not actually sure why it’s called a function, but it’s how you define a fluent which is in actuality a variable, in this case a numeric variable. Once we have our total-cost fluent we can now manipulate it. We’ll modify 3 key actions, the lose-ring, find-ring, and steal-ring actions to each modify total-cost. I’m using total-cost here as a sort of “trouble” for the agents as a whole which is why losing the ring increases the value and finding the ring decreases the value. Notice the increase or decrease at the end of each action’s effect, they are otherwise unaltered.

(:functions 
	(total-cost) - number
)

(:action steal-ring
	:parameters (?thief - person ?victim - person ?location - location)
	:precondition (and (at ?thief ?location) (at ?victim ?location) (not (has-ring ?thief)) (has-ring ?victim))
	:effect (and (not (has-ring ?victim)) (has-ring ?thief) (increase (total-cost) 5))
)

(:action lose-ring
	:parameters (?loser-of-ring - person ?ring - ring ?location - location)
	:precondition (and (has-ring ?loser-of-ring) (at ?loser-of-ring ?location) (not (at ?ring ?location)))
	:effect (and (not (has-ring ?loser-of-ring)) (at ?ring ?location) (increase (total-cost) 5))
)

(:action find-ring
	:parameters (?finder-of-ring - person ?ring - ring ?location - location)
	:precondition (and (not (has-ring ?finder-of-ring)) (at ?finder-of-ring ?location) (at ?ring ?location))
	:effect (and (has-ring ?finder-of-ring) (not (at ?ring ?location)) (decrease (total-cost) 5))
)

So now the domain supports the concept of a total-cost and manipulates it via our various actions. In the problem file we must now set total-cost as the metric by which the planner will determine a “best” path. We need to set the initial value of total-cost in the init section, and then add a new section for the metric. The plan looks like this now.

(define (problem pb1)
    (:domain proposal)
	(:requirements :typing :strips :equality :constraints :fluents :quantified-preconditions :disjunctive-preconditions :derived-predicates :negative-preconditions :tlplan)
  	(:objects 
		engagement-ring - ring
		joe sam sally - person
		a b c - location
	)
	(:init 
		(loves sally sam)
		(loves sally joe)
		(has-ring joe)
		(at joe a)
		(at sam b)
		(at sally c)
		(= (total-cost) 0)
	)
	(:goal (married sam sally))
	(:metric minimize (total-cost)))
)

Running this gives us the following result

Operators:
0:(move joe a b)
1:(lose-ring joe engagement-ring b)
2:(find-ring sam engagement-ring b)
3:(move sam b c)
4:(propose sam sally c)

Order:
0:(move joe a b) -> 1:(lose-ring joe engagement-ring b)
1:(lose-ring joe engagement-ring b) -> 2:(find-ring sam engagement-ring b)
2:(find-ring sam engagement-ring b) -> 3:(move sam b c)
3:(move sam b c) -> 4:(propose sam sally c)

Plan:
0.000000 : (move joe a b) [1.000000]
1.000000 : (lose-ring joe engagement-ring b) [1.000000]
2.000000 : (find-ring sam engagement-ring b) [1.000000]
3.000000 : (move sam b c) [1.000000]
4.000000 : (propose sam sally c) [1.000000]
Plan cost: 0.000000

The two lose-ring and find-ring actions both add and remove 5 from the total-cost so the overall cost is 0. If the planner had chosen the steal-ring, we would have just a +5 to our cost which is obviously higher. One thing to note, since we’re going for smallest total-cost, and finding the ring reduces the total-cost it’s very important that finding the ring does not decrease total-cost by more than the amount lose-ring increases it by. In that situation, the correct way to minimize the total-cost is to infinitely lose and find the ring. While a clever exploit of our intended setup, this is not very useful as a plan for our characters, so we make the value even (for now). Since we’re using a custom metric, the number of steps in the plan don’t matter anymore, but we can create a hybrid solution.

(:metric minimize (+ (total-cost) (* 2 (total-time))))

total-time is equal to the number of steps in the plan. We could use this to weight plan length relative to the inconvenience of our agents.

So what does this have to do with Star. Ship. Story.? As I began to dig into the source of TLPlan I realized to my chagrin that its forward chaining nature makes it rather difficult to adapt the CPOCL algorithm I was intending to use. The core concept in the CPOCL algorithm is that the threatened causal links are indicative of conflicting goals for agents, but I don’t have any causal links to be threatened in a forward chaining system. Hrm I thought, what am I to do now? I began to wonder if there was a way to use multiple individually generated plans by multiple actors, each seeking their own personal goal, and somehow merge them. I worked through several possible scenarios that all went bust, but I believe I now have a way to use the plans generated for each agent to inform a master plan that does in fact allow for the story to contain a sufficient amount of conflict. The best part is, if it works, this technique would work with any planner without any modification, so it would be very nice if say you already had a planner for your navigation or overall goal setting. I’ll try to get back and write up a post on what my work produces in the next week or so, I plan to have enough info to know if this is going to work by then.

A brief layman’s introduction to AI planners

You may be familiar with “Game AI”, that is the special branch of Artificial Intelligence that deals specifically with real-time application inside a game environment.  This is the domain dominated by state machines, behavior trees, and the occasional genetic algorithm or neural network.  We deal with things such as implementing A* to traverse a navmesh or building convincing steering behaviors but perhaps you’ve always wondered what was part of that “normal AI” side of things.  This is especially true when you start to deal with long term planning for agents across a large number of potential actions.

This was the situation I found myself in, trying to figure out how I’m going to generate the story plan with all the various actors moving about with the tools that I know from game ai. I was thus delighted to run into a paper on narrative generation with conflict planning.  I dug in, read the paper, realized it’s based on another system outlined by this paper which itself builds upon (at the time, 23 years of research) another system named STRIPS which gave birth to a whole branch of AI known as planners.  Well, I can’t actually say with authority that STRIPS gave birth to that branch, but it certainly seems to be the great granddaddy of most systems these days.  Of course in 40+ years of research there have been lots of ideas floated around and I don’t want to sound like this is all there is, but certainly I had stumbled upon a big area of active research that has a lot of history and culture behind it.

I had basically no idea what these people were talking about.

So, 3+ papers read and digested later, I was starting to get a handle on this whole idea.  You see, STRIPS style systems are all about taking a starting state, a set of operations or (actions if you prefer) that can transform that state, and finally a goal to work towards.  These planners then magically figure out the most efficient plan that transforms the start state to the end state.  Ok, so it’s not really magic, in fact it’s not really super complex at an algorithm level.  Each operation has a list of preconditions that must be met, and effects which then are applied to the world.  So you might have an action named drop-item which has the precondition of having the item and the effect of not having the item, and the item being at your current location (presumably on the ground).

There are two big approaches to this “find a valid plan” problem, ones that start at the start state and search towards the goal (forward chaining) and ones that start from the goal and work backwards (partial order). The UCPOP algorithm described in the 1994 paper by Weld is a partial order planner and it works like this:

  1. Make a list of all the preconditions of the goal state.  If your goal is to be driving down the highway in a sports car, then the preconditions might be that you have a sports car, you know how to drive a car, and that your sports car has gas.  This list is what needs to be satisfied, once there are no more unsatisfied preconditions you have a plan.
  2. Pick one of the preconditions that is not yet satisfied and either select an existing operation or pick a new operation not yet part of the plan that has an effect that satisfies the precondition.  This might be obtain-driver-license or fill-car-with-gas or buy-car.  Of course, each of those actions will have their own preconditions, so those need to be added to the list of unsatisfied preconditions.
    1. Part of adding a new operation or re-using an existing one is to make sure that you don’t screw up the bits you’ve already figured out.  For example, what if you add the operation of fill-car-with-gas to your plan that already contains buy-car and collect-paycheck.  What if filling your car with gas uses up enough money that the precondition of having X dollars is no longer met by collect-paycheck?  This is known as a threatened causal link and to resolve this issue we have a list of orderings we maintain that says fill-car-with-gas has to happen before collect-paycheck or after buy-car.  In this way it cannot interfere with the  effect of collect-paycheck satisfying the precondition of buy-car.
  3. Do #2 again with your now updated list of preconditions, stopping once that list is empty.

Of course the actual details are all much more complex than this but this gives the flavor of what’s happening.  You’re pluggin the holes (sometimes called flaws) in your plan one by one until either you can’t find an operation to satisfy the precondition, in which case the plan does not exist, or you run out of preconditions and you are done.

Enough with the wall of text, how about some examples presented as… er, well more text. Most planners these days read in a format called PDDL.  PDDL is a Lisp-like syntax developed so that the AI community could have competitions where the source input was standardized and didn’t need to be converted into each and every planner’s own format.  Lisp has been a very popular language for AI research over the years so it makes a lot of sense that using a familiar syntax would be the path of leasat resistance. For the non S-Expression bit of the programming community, reading these statements can be somewhat intimidating at first. But hey I’m a lowly C# / Ruby programmer and it’s not really all that bad.

; Everything in Lisp is a list. To call a function, you create a list
; that has the function as the first element followed by all the params
(function param1 param2)

; Things that are normally "operators" in most languages are just 
; more functions, so + is a function and its params are 2 ints
(+ 4 5)

; You can of course nest lists
; In an ALGOL like language, this would be (4 + 5) * (3 - 4)
( * (+ 4 5) (- 3 4) )

Alright, now that you’re confused and probably a bit grumpy from being forced to look at Lisp syntax and contort your brain into somehow balancing out all those parentheses, let’s move on. PDDL files come in two varieties, the domain which is all the operations that the planner can choose from, and the problem file which gives the start state and goal.  This is done so that one domain can be used to solve lots of different problems without having to re-define it each time.  Apparently AI researchers hate code duplication as much as software engineers.  Here’s our example domain, a situation in which people can move, find rings that happen to by lying on the ground, and of course propose using said ring.  We define the stuff of our world, locations, persons, rings, and then embed concepts (which are really just tags or attributes) such as at, loves, has-ring or married.  Some of these attributes involve only one object such as has-ring, others are a pairing such as loves or at.

(define (domain proposal)
	(:requirements :strips :equality :constraints :quantified-preconditions :disjunctive-preconditions :derived-predicates :negative-preconditions :tlplan)
	(:predicates
		(location ?l)
		(person ?p)
		(ring ?r)
		(loves ?p ?p2)
		(has-ring ?s)
		(married ?s ?m)
		(at ?o ?l)
	)

	(:action propose
		:parameters (?suitor ?maiden ?location)
		:precondition (and  (at ?suitor ?location) (at ?maiden ?location) (has-ring ?suitor) (loves ?maiden ?suitor) (not (married ?suitor ?maiden)))
		:effect (and (married ?suitor ?maiden) (not (has-ring ?suitor)) (has-ring ?maiden))
	)
	
	(:action move
		:parameters (?person ?from ?to)
		:precondition (and (at ?person ?from) (not (at ?person ?to)))
		:effect (and (at ?person ?to) (not (at ?person ?from)))
	)

	(:action find-ring
		:parameters (?finder-of-ring ?ring ?location)
		:precondition (and (not (has-ring ?finder-of-ring)) (at ?finder-of-ring ?location)(at ?ring ?location))
		:effect (and (has-ring ?finder-of-ring) (not (at ?ring ?location)))
	)
)

Given that domain, let’s run some actors through it. Here are Sam and Joe who both want to end up married to Sally. We set a goal of Sam marrying Sally and place a ring at location a.

(define (problem pb1)
    (:domain proposal)
    (:requirements :strips :equality :constraints :quantified-preconditions :disjunctive-preconditions :derived-predicates :negative-preconditions :tlplan)
  	(:objects engagement-ring joe sam sally a b c)
	(:init 
		(location a)
		(location b)
		(location c)
		(person joe)
		(person sam)
		(person sally)
		(ring engagement-ring)
		(loves sally sam)
		(loves sally joe)
		(at engagement-ring a)
		(at joe a)
		(at sam b)
		(at sally c)
	)
	(:goal (married sam sally)))

Here is the plan the planner produces.

Operators:
0:(move engagement-ring a b)
1:(move sally c b)
2:(find-ring sam engagement-ring b)
3:(propose sam sally b)

Order:
0:(move engagement-ring a b) -> 1:(move sally c b)
1:(move sally c b) -> 2:(find-ring sam engagement-ring b)
2:(find-ring sam engagement-ring b) -> 3:(propose sam sally b)

Plan:
0.000000 : (move engagement-ring a b) [1.000000]
1.000000 : (move sally c b) [1.000000]
2.000000 : (find-ring sam engagement-ring b) [1.000000]
3.000000 : (propose sam sally b) [1.000000]

Hrm, not exactly what I was looking for. Rings don’t typically get up and move on their own.  Clearly we need to restrict which objects move is allowed to be selected for. PDDL provides a mechanism for specifying types for objects and then restricting the parameters to operators based on those types. PDDL uses a hyphen followed by the type, for example sally – person says sally is a person. We add a new section to define our types, in this case 4 things, object, location, person, ring. The reason we need object (of which both person and ring are members of) is so that either one can use the “at” operator but only objects of type person can use the move operator and only rings can be found via find-ring.

(define (domain proposal)
	(:requirements :typing :strips :equality :constraints :quantified-preconditions :disjunctive-preconditions :derived-predicates :negative-preconditions :tlplan)
	(:types 
		location
	 	person - object
		ring - object
	)
	(:predicates
		(loves ?p ?p2 - person)
		(has-ring ?s - person)
		(married ?s ?m - person)
		(at ?o - object ?l - location)
	)

	(:action propose
		:parameters (?suitor - person ?maiden - person ?location - location)
		:precondition (and  (at ?suitor ?location) (at ?maiden ?location) (has-ring ?suitor) (loves ?maiden ?suitor) (not (married ?suitor ?maiden)))
		:effect (and (married ?suitor ?maiden) (not (has-ring ?suitor)) (has-ring ?maiden))
	)
		
	(:action move
		:parameters (?person - person ?from - location ?to - location)
		:precondition (and (at ?person ?from) (not (at ?person ?to)))
		:effect (and (at ?person ?to) (not (at ?person ?from)))
	)

	(:action find-ring
		:parameters (?finder-of-ring - person ?ring - ring ?location - location)
		:precondition (and (not (has-ring ?finder-of-ring)) (at ?finder-of-ring ?location) (at ?ring ?location))
		:effect (and (has-ring ?finder-of-ring) (not (at ?ring ?location)))
	)
)

We now define the objects in the scene with their types in an objects block and simply leave all the “tag / attribute” style data for the init block.

(define (problem pb1)
    (:domain proposal)
    (:requirements :strips :equality :constraints :quantified-preconditions :disjunctive-preconditions :derived-predicates :negative-preconditions :tlplan)
  	(:objects 
		engagement-ring - ring
		joe sam sally - person
		a b c - location
	)
	(:init 
		(loves sally sam)
		(loves sally joe)
		(at engagement-ring a)
		(at joe a)
		(at sam b)
		(at sally c)
	)
	(:goal (married sam sally)))

Given this new input, the planner now produces the plan

Operators:
0:(move sam b a)
1:(move sally c a)
2:(find-ring sam engagement-ring a)
3:(propose sam sally a)

Order:
0:(move sam b a) -> 1:(move sally c a)
1:(move sally c a) -> 2:(find-ring sam engagement-ring a)
2:(find-ring sam engagement-ring a) -> 3:(propose sam sally a)

Plan:
0.000000 : (move sam b a) [1.000000]
1.000000 : (move sally c a) [1.000000]
2.000000 : (find-ring sam engagement-ring a) [1.000000]
3.000000 : (propose sam sally a) [1.000000]

Ah, much better! We can of course make things more interesting. Instead of a ring lying on the ground we could have one person lose the ring to be found by the other, or perhaps one person could steal the ring from the other.

(:action lose-ring
	:parameters (?loser-of-ring - person ?ring - ring ?location - location)
	:precondition (and (has-ring ?loser-of-ring) (at ?loser-of-ring ?location) (not (at ?ring ?location)))
	:effect (and (not (has-ring ?loser-of-ring)) (at ?ring ?location))
)

(:action steal-ring
	:parameters (?thief - person ?victim - person ?location - location)
	:precondition (and (at ?thief ?location) (at ?victim ?location) (not (has-ring ?thief)) (has-ring ?victim))
	:effect (and (not (has-ring ?victim)) (has-ring ?thief))
)

So this is pretty neat. Given a big pile of operators and actors the planner will figure out how to get from start to goal (assuming such a plan exists). However, this doesn’t really make for the greatest story. The core of most stories is conflict and planners have no concept of this, everything in the system is effectively working together to solve the problem. This brings us all the way back to the original paper that got me started on this whole crazy journey. The CPOCL algorithm preserves some information that is generally discarded in the planning process, namely those threatened causal links from my description of the UCPOP algorithm. When one action threatens to undermine the connection between two other actions, that is (in story terms) conflict! So we need to modify our algorithm to retain some of those threats and although we won’t actually let them mess up our plan, we can force some of them to still happen in a way that leads up to a point where theoretically they *could* have happened. This to me is the key super awesome special magical moment in all of this. When I think of story generation it’s usually like pick an actor, pick an action, pick a location, yada yada 20 attributes later… now put this actor somewhere that they are in the way of the player. But how did this actor get here? Why are they opposing the player? These sorts of obstacles are usually MacGuffins that materialize out of nowhere and then cease to have any consequence on the world when off screen. If the plot is the result of an actual plan, where actors are only at a location because it furthers their goals and they took all the steps needed to arrive at that location, well, that is a real actor behaving (more) believably.

Of course, a set plan falls apart if players have any agency over the world. For examples of this sort of thing, reference… hrm… let’s see, oh yeah. EVERY GAME WITH A PLOT, EVER. Perhaps that is a bit harsh… maybe. There certainly have been some pretty interesting attempts in this direction, the recently released Sorcery I felt did a pretty good job here but your typical fare is GAME -> STORY -> GAME -> STORY -> well you get the idea. You’re either in game mode, or you’re in story mode and never the twain shall meet. If you can actually generate a cohesive plot while taking into account the player’s actions, well then you may actually have something.

So how does this fit in with Star. Ship. Story.? The current plan (no pun intended) is to regenerate the story plan after each encounter taking into account the actions of the player as the new start state. It’s unclear now if the system is fast enough to do this with a sufficiently large number of possible actions, but I’m feeling pretty good about my tests so far. We’ve managed to find a good planner to use as a base for implementing the CPOCL algorithm, named TLPlan and there’s conveniently a C# implementation by Simon Chamberland which he has graciously made available for our use. The work now is to add the CPOCL bits and start tuning the planner to produce the kinds of tension we need. There are further layers then to investigate such as this paper which outlines ways of building suspense by witholding information from the observer. All said, even with all the work it took to get to this point, I’m still pretty stoked about the potential this sort of system has for application within games. Planners in general seem pretty ripe for application as some games have already figured out but I feel the specific application with narrative generation holds huge potential for the kinds of experiences we are capable of building.

Star. Ship. Story.

In the tradition of many fine game development studios who have gone before us, we’re happy to talk about our game that you won’t be able to play for a long time.  No, not Half-Life 3 long, or even Spy Party long, just a year or so until an alpha/beta type phase will emerge from its protective chrysalis and you will have the chance to crush all our hopes and dreams with the brutality and honesty of  your feedback.

Star. Ship. Story. Logo

What is Star. Ship. Story. you ask?  My that’s a clever question, we can’t slip anything by you.  In short, Star. Ship. Story. (S.S.S. from now on) is a co-op space adventure with a custom generated story and persistant world effects.  Let’s examine this a bit further using this handy chart.

Things S.S.S. is Things S.S.S. is not
  • A pure co-op game
  • Skill based
  • Designed for a wide range of gaming ability
  • A procedurally generated story system
  • A short form game experience
  • Influenced by the decisions from previous sessions
  • Still unproven for certain systems
  • A game with RPG elements or XP
  • An excuse to sell in-app purchases
  • A MMO
  • A power fantasy for teenage boys
  • A game that you’re guaranteed to win
  • Complete right now

The idea for SSS grew out of my own gaming group’s desire to  find a game that met the following criteria:

  • Enjoyable for both hardcore and casual gamers
  • Supports a wide range of players, from 2 – 10
  • Can be played in discreet time periods, 30 – 40 minutes being pretty close to ideal

After trying just about every game I could find, I finally decided that the only way this was going to happen was if I write the game myself.  So based on some ideas from an old game contest entry, I started to put together a prototype over Christmas vacation.  About a month later I was testing some very rudimentary network code with my gaming group.  It wasn’t pretty and it didn’t work very well, but we were flying around in a ship shooting at stuff.  Development continued which leads us to today:

Of course all this is placeholder art (quite a lot of it programmer art in fact) at this point.  It was, however, enough to convince us that there was something worth pursuing here, and so work continued.  Eventually we felt that enough details were nailed down that we could at least start to talk about the project publicly.

The setting of S.S.S. is a uniquely generated star system inhabited by a selection of characters selected from a large pool.  This story is not just a mad-lib style fill-in-the-blanks solution, it’s not a poorly branching linear-but-with-one-sorta-kinda-actual-decision, no it’s actually a real story.  Ok, story is probably a slight stretch, it’s more like a story outline.  If you’re interested in all the gory details, you can read up on some of the research we’re basing the story generation system on here and here and here.  This is not all 100% worked out yet, and is the single greatest risk factor the project has left to tackle, so that’s what we’re currently working on.

So what good is a bunch of planets and a story to a game?  I mean if you want a story you’ll just go read a book.  S.S.S. is definitely being designed with gameplay first and foremost.  Ship to ship combat is accomplished via each crew member manning a different station (helm, weapons, shields, engineering).  On smaller ships, there are less stations, a 2 crew ship for example would only have helm and weapons.  Each station operates differently and there are variations from ship to ship as well.  The stations were designed to appeal to different play styles as much as possible within the confines of a real-time action game.  These ship combat moments though are meaningless and fall pretty flat when devoid of any context, which is where that story comes back into the picture.  You won’t be fighting constantly, and when you do, we really want it to feel like a big deal, I mean, your life is on the line! S.S.S. is designed to be pretty hard, so that your decisions actually matter and working as a team is significant.  So when a pirate ship lures you into their trap with a false distress beacon, you may think twice before just opening fire.  Also, your role in the world is dependent upon the story that is generated, so that will vary from game to game.

When you’re not fighting off pirates, arresting dangerous criminals or one of the other various roles you can be given, you’ll have decisions to make about where to go to accomplish the overarching mission you are working towards.  These missions are varied and can include such diverse tasks as repelling an alien invasion, tracking down a corporate saboteur, recovering a missing military prototype, escaping the goons of the local underworld boss you owe money to, and many more.  The crew will have the opportunity to make many decisions together in how to proceed in completing this mission.  Along the way, along with ship combat, there will be opportunities to visit locations as an away mission.  These away missions allow your characters to move around in a new environment (planet surface, spaceport, another ship, etc.), and use your skills in a new context.

While there is no experience gain or levels in-game, there are currently plans to have unlockable skills that you can swap out for your initial skills.  These are not power upgrades, you’ll never see a strictly better version of a skill you start with, only variations that come with their own drawbacks.  This allows you to play with different builds of skills to take on certain challenges you can configure for yourself.  Speaking of configuration, each game is set up by you to have a certain duration, which determines the story that is generated.  This allows you to tailor your gameplay experience to be around the time you need it to be.  Have a few friends who will be getting on in the next 30 minutes?  Start a game with a ship big enough for them, play with bots and as they arrive they can jump in and take over those crew positions.  Once everyone has arrived you can quit the game and start over, or more likely, just complete the game you are almost done with before starting another with everyone there from the beginning.

Finally, what good are your decisions and intrepid adventures without some sort of permanence?  Since the stories are procedurally generated, we can factor in your past actions.  Expect to meet up with crews you formerly played as, now taking on roles as characters in the world that can be friendly, indifferent, or outright hostile to your new characters.

Multiplayer is probably something people will think of, and we’re thinking about it too.  In fact we’re using a multiplayer mode to design and balance all the ship combat.  This will be a distinct mode from the co-op game and will be finalized last.

Phew.  Well hopefully that gives you a sense of what this crazy thing is that we’re building.  You can expect lots more updates as we make progress that’s showable over the next few months.

In the meantime, you can sign up for updates on our progress here.