Hi I'm Tommy Thompson and this is AI and Games: a series on research and applications of artificial
intelligence in video games. In this video I'm going to be a little bit selfish and talk
about a game that I made for a change and how AI and procedural generation can build
scalable and flexible level generation systems: welcome to the world of Computra and my first
ever commercially released video game: Sure Footing!
Sure Footing is an infinite running platforming game developed by my company Table Flip Games.
Over the years I've made a bunch of small games for research purposes, but never with
the intent for humans to play them and enjoy them enough to given their money! As such,
this is my first ever published game - which is quite exciting. Sure Footing takes the
infinite running template seen in flash and mobile games and expands upon it with a dynamic,
scaling and reactive procedural generation system that not only changes the game world
as you play, but makes decisions to change its own internal decision making and tweak
parameters based on player performance. The goal of Sure Footing is to allow for players
to find a play style and pace that suits them as they race through the generated worlds:
not just with the variety of characters, costumes and power-ups but also the difficulty of the
level generation system itself - allowing players to treat it as a mild-paced platformer
all the way to an intense twitch runner.
In this video I'm going to talk about how it all started, the academic research that
inspired it, the AI that controls the bad guys and most importantly the procedural generation
engine that powers the entire game. The engine manages not just how segments of the world
are created, but how we modulate the scale of generation over time, how difficulty is
encoded and makes changes at runtime to try and keep players engaged as best as possible.
If you're not familiar infinite runner are a sub-genre of platforming games where the
player is constantly running forwards and navigating a variety of platforms and obstacles
that get in their way. It's largely popularised in western markets by flash and mobile games
such as Canabalt, Temple Run, Subway Surfers and Jetpack Joyride. Infinite runners are
largely reliant upon procedural generation or at minimum some basic pseudo random methods
in order to continually construct new segments of environment for players to run through
the longer they survive. This is why I chose it as a testbed for a research project I started
back in 2014 exploring how to manage the expressive power of a level generator. Procedural generators
can build anything they want within the scope that they are constructed, but how do you
model that in a framework that is open to user needs and designer influence? By controlling
or at minimum constraining these aspects, we could effectively manipulate the scale
of content and - provided the generated content is linked to gameplay challenge - potentially
influence the perceived difficulty of the game. Infinite runners typically handle their
difficulty curve with small design-driven tweaks of parameters such as running speed,
the probability specific obstacles appear, as well as activating new effects that players
won't see early on. But how do we maintain that whilst also ensuring a sense of variety
and novelty over hours of gameplay? There isn't a huge amount of evidence in industry
of how this is done through frameworks, pipelines and good practice, so I decided to try it
myself.
While Sure Footing is an infinite runner, the design of its level generation system
is derived largely from classic platformers such as Super Mario Bros., Sonic the Hedhgehog
and Rayman. However some of the smaller design choices are influenced by two infinite running
games: Adam Saltsman's Canabalt and Jetpack Joyride by Halfbrick Studios for the orientation,
shifting locales and city skylines.
One of the reasons I focussed on classic Mario style platforming is that there is already
a lot of research in this area. I coverd some of the earliest work in this field a couple
years back with the Mario AI competition, but has since been nurtured even more over
time - a topic that I hope we can dedicate another video too in the near future!
One of the major influences behind the system was the LaunchPad project: a procedural generation
system that developed Mario-style levels using a grammar system - developed by Gillian Smith
who at the time of this video is an assistant professor at Worcester Polytechnic Institute
- and Mike Traenor who is currently an assistant professor at American University. LaunchPad
is built on the idea of rhythm and beats, where the system procedurally generates levels
based on actions the system wants players to do and constraints that dictate how they
can be glued together.
Meanwhile inspiration also came from work by Steve Dahlskog, a lecturer at the University
of Malmo in Sweden who has looked at how encoding platforming level designs as patterns and
how Super Mario Bros. in particular is reliant on specific patterns occurring frequently
and at varying levels of challenge or difficulty. Steve has also experimented with letting machine
learning algorithms create their own Mario levels using this pattern encoding. If you're
interested in this work, be sure to check out my Legacy of Super Mario Bros. video already
on AI and Games.
Sure Footing marries these two principles together: we use the base idea of beats in
a rhythm from LaunchPad, the constraint modelling process and encode the pattern formula at
both the individual gameplay beats as well in the construction of overall levels. This
is actually done on two levels of generation: action, followed by geometry, which I'll cover
in a minute.
Sure Footing has so many generators built into it I sometimes forget they're even in
there. While the framework that places platforms is the primary system, we also use generators
to - generate the opening market street
- place the background geometry - customise the census data players see on
the welcome signs - decorate the streets with NPCs and market
stalls - even the piles of crates you see in the
streets are generated by their own procedural system.
The game is actually rather barren before any of the code starts executing. Sure Footing
is built in the Unity game engine and while in-game you'll see the market, the starting
streets and all the game run quite seemlessly, as you can see here in my editor view, only
the empty start street and junction exist before the game starts. I build the rest of
the game at runtime through a series of volume triggers and time-sliced routines that run
the PCG in the background and place new content. What's critical to us is that the game does
all of this without compromising framerate and mitigating just how much players see in
advance. We actively try and ensure that players can't tell when the PCG systems are active
as it not only generates new content in front of you, but also removes segments of play
behind you.
Sure Footing breaks up the level generation process into what we call 'sprints', these
are the segments full of platforms in between each street area that we refer to as 'rest
pieces'. The procedural generation engine is responsible for building a sprint, ensuring
it is positioned correctly, generate a new rest piece, populate the rest piece with content,
managing the increase in scale for the next sprint and then ensuring that the backgrounds
all align correctly as well as activate or remove mutators that change the game to make
it more challenging.
In order for the sprint generation to ramp up and provide an interesting difficulty curve,
we apply a number of constraints within a system on start up. These constraints are
gradually relaxed during play, allowing it to generate more difficult sprints, but also
inject some variety as it swaps out modes of generation and uses new tools at its disposal.
I'm going to deep dive into two specific systems, the sprint generator and the sector generator
- which is responsible for selecting the locales we visit while running and how the two interact
with one another.
The sprint generator is responsible for looking at the current state of the game and building
the next segment of platforming content. In order to do that, the sprint generator is
broken down into two main subsystems I mentioned earlier: the action generator and the geometry
generator.
The action generator figures out what we want the player to experience in a more abstract
sense during the next sprint. What are the sequences we'd like to glue together. Does
the next sprint adhere to a particular theme such as running up a gradual incline, running
down hill, continually forks into multiple paths or is a nice chill route with a lot
of flat runs. To do this the action generator adopts the
principle of procedural grammars from LaunchPad: in this instance we encode actions we expect
the player to complete, such as climbing a set of stairs, falling down a drop, bouncing
upward on a spring or even just running a flat sprint. These terms or symbols can then
be added to the lexicon of a unique grammar, with associated rules or costs attributed
to them. The lexicon of a grammar, combined with the rules of construction sequences in
that grammar, give us control over what decisions that generator makes. It allows us to decide
what actions are valid for a given sprint, and even distinct contexts within a sprint:
such as ensuring you don't have the same thing twice, or that we don't follow action X with
action Y. The system then drafts a sprint by running a search through the grammar whilst
respecting the constraints that have been imposed, resulting in a finite sequence of
specific actions it wants players to complete for that sprint.
Meanwhile the geometry generator takes that encoding of the sprint and turns it into a
sequence of platforms. This is achieved by having pre-built chunks of gameplay, much
akin to the Dahlskog pattern model that represent the specific symbols used in the action generator
grammar. As the designer that means I have to sit and make a stack of different variations
of the same pattern: such as hopscotches, two and three-prong paths, stair wells, drops,
spring sequences and more. The system then selects a corresponding pre-built chunk or
prefab for each of the sprints generated actions.
In order to gradually scale the challenge of the sprints, each subsystem is built on
the principle of a 'budget' a cost value attributed to decisions made by the level generator systems
constrains the size and intensity of levels, alongside the geometry that actually appears.
In the action generator, the budget gives us control over not only how many actions
are encoded within a given sprint, but also how soon certain actions can start to appear.
Each action generator decides the cost or value of a given symbol in each grammar, meaning
that in some instances a pattern such as a staircase will be more or less expensive in
different action generators. Meanwhile in geometry generator, each variation of a given
pattern is given its own cost. Hence I can sit and make different versions of the that
staircase sequence and through the cost value can establish a continuum of the easier to
harder versions of this segment. All of these budget values and the like are hand tweaked
at design level, allowing for me to better balance parts of the game having playtested
it in the wild.
In addition to all of this, there are multiple versions of each generator, with three geometry
generators and 17 action generators at the time of this video. Geometry generators are
used for specific circumstances in game. Meanwhile the action generators are swapped out at runtime
by the level generator itself, with it dictating how frequently it changes mood and sometimes
reacts to what the player has done in-game.
So with the sprints in place, we wanted to add another layer to the game that helps players
understand how far they're progressing. To do this we use sectors: fictional locations
that change the aesthetic of the game, as well as potentially add a new layer of difficulty.
At launch we have 10 unique locations in the world, with the player always starting in
Cacheville in survival mode. The sector generation process is responsible for generating the
backdrop art assets, activating mutators that change the world as well as triggering the
behaviours in the sprint generation framework.
Upon entering a sector, we check whether any new mutators are going to be added to the
game, this includes visual occlusion, changing the camera orientation and adding elements
such as fog. The sector generator places the background
art assets for that sector - building the cityscapes, the trench and back wall in such
a way that they click together. The skyline of each sector is always generated to ensure
it lines up with the rest area at the end of the current sprint.
Each sector is a certain number of sprints in length, once the threshold is reached,
the generator will pick the next locale to visit. It
then triggers two behaviours in the sprint generation system:
- First up, the sprint and sector generator will build a custom sprint that we call a
tunnel: this is a forced transition to a specific action and geometry generator that creates
a slightly more difficulty run than usual. It's used to signify that a sector transition
is about to occur: using a special tunnel background and audio occlusion to help identify
the change.
- Secondly, we queue up the removal of any and all mutators to occur at the same time
mutators for the next sectors will be activated. Meaning a seamless transition between sectors.
Next up, let's talk some NPC AI as well as game difficulty.
First up, we have two villains in our game, Deletion Dave who chases you throughout the
game, as well as Ramrafstar, who acts as more of a boss battle and flies in to start destroying
the platforms as you run across them. Each of them are actually fairly simple and operate
in a simple finite state machine.
Dave is almost always chasing you, with him gradually increasing in speed the longer you
survive and can be made to slow down by having him hit active blue crates. But he does have
some simple attack patterns and delays between attacks. Dave also has a state within which
he will actually stop chasing you, but that's down to two things: Ramrafstar and difficulty
settings.
Ramrafstar has three states of behaviour, inactive, waiting and attacking: by default
he won't start attacking until the level generator permits him to do it. Every sprint Ramrafstar
checks whether the level generator will permit him to interrupt and attack the player. Once
the level generator permits this - a decision driven by both difficulty settings as well
as some other secrets about player behaviour - Ramrafstar will appear on a rest piece street.
Upon passing him as he sits on the street, he'll come to life and attack for a predetermined
period of time. In addition, based on the current difficulty, Deletion Dave may be asked
to fall back into his inactive state. Though in higher difficulties, there's a good chance
he won't!
Speaking of difficulty, this has been a big part of the ongoing development of the generation
framework: tweaking the system so it is more flexible for players. At the time of this
video, the game provides custom configurations of the level generator that provide specific
difficulty settings as well as the ability to create a custom loadout where players customise
the difficult for individual components of the core design. This is all in an effort
to improve the games accessibility.
Accessibility has proven a really important issue during the games development, largely
given how broad the demographic of players we've seen enjoying it. We've seen hardcore
gamers, grandparents, toddlers, casual players have fun at many of the events we've showcased
in the last couple years. Plus we've had really useful feedback when seeing how players with
disabilities engage with the game and learning about how aspects of its design pose barriers
that prevent them from enjoying it as much as they could!
With over 30 unique parameters in the PCG, enemy AI and more that influence the overall
state of play, we can look to customise them in ways that change the overall experience.
So with that in mind we built running paces: these are essentially difficulty levels, but
I don't like using that kind of terminology, given it can prove alienating to players if
they are physically incapable of playing on the supposed 'normal' difficulty. Each running
pace customises the movement speed of the player, the starting budget values of each
generator system and the amount they increase by, constrains what types of obstacles can
be spawned in by the generator, which action generators are enabled, whether sector tunnels
can be used, what specific actions the action generator cannot do at the start of the game
and whether those rules can relax over time and the levels of aggression of Dave and Ramrafstar,
to the point that on their lowest settings they are completely disabled.
What makes this even more useful is that for some players the gap between one running pace
and another might be too extreme and they need to get used to it. So the custom running
pace system allows players to pick and mix the setting for player movement, level generation,
Deletion Dave and Ramrafstar. So if you like playing super fast speed, with easy geometry
and Dave right on your tail? You can do that. Or if you want to play on the lowest speed
and movement and way to try on slightly harder geometry, you can do that too.
For me it's all about giving players choice and allowing for players of all ages and abilities
to play the game in a manner that suits them. Otherwise, what's the point in building this
whole level generation system if it is still implicitly biased against certain types of
players. I'm still working on some new research into building an adaptive system for the custom
difficulty, whereby it begins to tweak parameters at runtime based on performance, so as to
push players a little harder the more they play and gradually train them up from one
running pace tier to another. But only time will tell how well that works out.
Sure Footing is out now Steam and Itch.io for PC and we're continuing to tweak, update
the game over the next year. Meanwhile I'm porting the game to Mac, mobile platforms
and bringing it to the Nintendo Switch and Xbox One in 2019.
There is still more work to be done, given there are a lot of prototype ideas and experimental
systems locked away in my development builds: some might make it into the final build, some
might not. But for now, there's plenty to keep me busy and hopefully you too. So yeah,
I should stop talking and maybe get back to working on the game, gotta keep running right?
Thanks for watching this video! It's a pretty special one for me as it's the first case
study based on my own work, which is admittedly kinda weird. This channel turned four years
old in 2018 and only now am I talking about my own work. It's pretty scary and exciting
to be able to share this with you. I hope you find it insightful, I'll leave some links
to papers, talks and other stuff I've delivered on this game during its development in the
description below and if you want a a follow-up on the additions we're making or even tutorials
on some of this stuff let me know in the comments. Plus a shout out to the Sure Footing dev team
Matt, Molly, Holly, Eli, Charlotte and Helen who helped build the game you see here today!
While this particular video based on my own work, AI and Games is dedicated to providing
insight into AI practices for games in both academia and the games industry. As such,
if you want to know more then click that subscribe button and check out my more recent videos
on DOTA2, StarCraft and Total War.
In addition, AI and Games is a crowdfunded show and it's thanks to these good people
on screen now who support me on patreon, as well as lovely folks who pass on small donations
via Paypal and Ko-Fi. To find out more about how you can get early access to new content
as well as updates on ongoing work, head on over to my patreon page listed in the description.
Alright, that's enough about me, we'll be back to our regular programming in the next
video!