hey everyone I'm John Abercrombie and uh
Tommy on this left it's right over there
so I'm gonna start for the first part on
the talk but you know like they just
said you know procedurally generated
worlds and player building are huge
parts of games today and both booked
down I come from a background with more
like very much designer driven
handcrafted content and we both moved
into this this new and interesting phase
of games that have you know randomly
generated worlds in it and so we're you
know our goal I think for both of us has
been trying to take some that richness
that comes from that handcrafted you
know content creator placed pieces of
the game and bring that into a space
that you really don't know much about
when you start the game so I'm working
on a game called fortnight it's in alpha
testing currently you know we're moving
towards bringing it out very soon but
basically the game is about player
building players build forts to save the
world and you have to defend against the
invaders who are coming for your for
your fort basically and for the thing
inside the fort that you're protecting
and then you have a bunch of people that
you're rescuing as well in the game so
while I could talk about it more I'm
just going to show you a little video
and you can kind of get an idea of what
it is but I'll just one more note I just
want to make sure you all know it's a
multiplayer building action survival
game with RPG elements so there's a lot
going on here and you'll see that in
this video
[Music]
all right of course the video was
nonsense of the audio right now so let's
move past that so I came to at the game
Surma rational where I worked on a
Bioshock and infinite for the Elizabeth
but I came to epic to solve you know you
know face new challenges and work on
difficult problems with a bunch of
talented developers and there certainly
have been many to overcome you know
especially come when it comes to the
procedurally generated aspect and the
player generated aspects of fortnight so
I'm going to approach the talk from the
perspective of some of the problems that
we've had in building this game and then
how we solve them so you know these are
examples of techniques that we've used
for the procedurally generated and
player built structures in the game a
fortnight and they're useful techniques
for the game we're making there may not
necessarily be useful to you and I've
tried to you know pick the techniques
that you know will be most applicable
for the general case and and I include
both development techniques as well as
runtime techniques so while all these
techniques may not be useful to you
right now I'm hoping that you have at
least something to take away from this
talk so worlds in fortnight are
procedurally generated and stitched
together at load time using a random
seed so they're comprised of level
designer worlds are comprised of level
designer levels that they've been
handcrafted a little bit and then stream
together put stitch together and then
they have a lot of potential locations
for gameplay so we run the game on a
dedicated server like I said it's a
multiplayer game and we don't have
access to the renderer so the AI logic
exists only on the server so debugging
problems becomes you know pretty
difficult beyond the text output that
you can get from from a server so we
wrote a system to allow the recreation
of the procedurally generated levels in
the editor so that allows running you
know worlds that are normally run in the
client-server situation to be just run
inside of the editor and it's incredibly
more powerful to have access to to have
it in the editor because you can run it
repeatedly over and over again really
quickly and having access to a debugger
versus a log file is like I don't have
to tell you how
better that is it's really a much better
situation in for tonight
you know once we've loaded our randomly
generated world we need to allow the AIS
to be able to navigate in it so you know
then the players load into and then they
start building so how do we deal with
that well like most games these days we
use a you know the standard navigation
math mesh and in fact we're using
recasts so we use what we call nav links
which are also called off mesh
connections and recast and allows AI to
drop off ledges or move through geometry
or move between edges of the nav mesh
and generally improve connectivity and
the nav mesh responds quickly to player
mail structures so we use we build the
nav mesh in a tile form and hopefully
this video works maybe a little bit
better but you'll sort of get the idea
as I play it this is it again standard
warning for today that this is level and
so what you're seeing here is the sea of
blue is to just the navigation mesh and
then the red is where we're one of the
tiles that were rebuilding and these
green areas that you can see and we have
a few other different colors in in here
you can see where we've added cost to
the navigation mesh so the eyes will try
to avoid those where they're doing a
path fun so but there are lots of like
we want to have lots of a eyes and for
tonight and you know and the ant eyes
are traveling long distances so the nav
mesh is great but all those triangle to
traversals can get expensive so and we
could use maybe cached paths or
something like that but that only works
you know if the eyes are all traveling
along the same path and in the past
don't change so that doesn't really help
us very much because the paths are
always changing in for tonight is the
players are building so what we did was
we had to have an alternative
connectivity graph so we call it the
navigation graph and it's based on the
bedrock of the level of the navigation
space at a level and we do have some
allowance for dynamic nodes as well but
most of its based on the bedrock and the
graph nodes they describe the space and
the connectivity to the other nodes so
here you can sort of get an idea for the
what the nav graph looks like
since we're built on the tiled world we
it the the graph nodes are built to the
tile size so all these white boxes are
nodes in the navigation graph and then
you can see it maybe a few blue ones
that are actually dynamic but there are
still lots of nodes in a navigation
graph you know certainly less than a
number of triangles that we're dealing
with in the navmesh but the navigation
graph still isn't fast enough to allow
us to you know have a large number of a
is traveling long distances so while it
describes the connectivity for us in a
much better way it's we can do better
so since since we know where the AI
spawn and then where they're going to
generally we can use the navigation
graph to generate flow fields and then
once we have those flow fields we can
basically create hot reusable paths
along the navigation graph that the AIS
can follow over long distances so for
performance reasons we can generate the
navigation graph in the editor we don't
need to actually do it at runtime
because it's not based on any of the
player billing but the flow fields are
generated as an initialization step to
our encounters and then our paths are
generated from that flow field so
basically use a Dijkstra a flood fill of
the navigation graph and to determine
connectivity and then you know from the
flow fields we extract the past based on
where we will spawn the eyes and so here
if we look at this again you can sort of
see those red lines and that's after
we've done the flood fill so from there
we will pick our spawn points which will
end up being in our view frustum those
clouds and then the inn and now we've
taken and created the paths here and we
have the paths from where the AIS are
spawning to their goal where that beam
of light is hitting the ground right
there
and note that that is the optimized path
there's actually no direct way up so
they have to actually cut around and
come back they can't actually climb up
terrain well yet so in fortnight players
they also can build structures almost
anywhere so we're dealing with it not
only you know the randomly generated
world so we're dealing with players who
can build almost anywhere and they can
you know they build their player built
forts they can build walls floors
ceilings and and more to stop the AI
from sabotaging stop the AI from
navigating to their goal so the way we
used to have the the attack structures
when I first started was to just have
them like sort of bump up against a
piece of geometry and start attacking
once they got there and it was it was
absolute chaos it really looked bad it
didn't have good results and we needed
to solve that problem so the solution
was for us was to add what we call
hotspots and it's basically an offset
position and orientation from a building
structure we make like mixed use of both
baked in editor sets of hotspots as well
as generated on the fly and in the game
to allow the AI to attack structures so
they can be socketed about geometry for
fortnight we choose hotspots based on
direction we're approaching from so we
actually have hotspot sets from each
direction you can approach your building
structure so if you met if you took a
wall right you can approach a wall from
six different directions and for each of
those directions you would have a
different set for the potentially so we
also we have that pre baked data but
we're putting once you put all those
structures together we have to filter
that with runtime tests so that you can
make sure that if I want to go to this
hotspot can I actually path to it so
some hotspots are ignored because we
can't pass them or if they're blocked by
geometry or another building structure
hotspots are also a good way to make you
know the animations line up with
geometry well it's not going to be exact
we're not we're not really trying to be
perfect about that we want it to look
good it works very very well for that
and sorry so you know all that we use
the hotspots for having the attacking
building structures the hotspot
technology isn't limited to that you
could use it for
the guys going up two interacting
machines or something like that
something we're looking into for the
future so here's an example of hot spots
in action this is an automated test
level there are four this is our
automated test level for hot spots and
you can see right there there's a big
tree and the eyes have you know in this
test have been told to destroy the tree
now about the tree there are a bunch of
hot spots and they're actually a bunch
of the eyes in there right now that tree
is very large in the hot spots our belt
the tree that are further away are
actually for range day eyes to attack
the tree so range eyes that have a
capability of destroying building
structures can do so and we also have
some hot spots lots as well for the
larger eyes that we have so like I said
before the players can build structures
pretty much everywhere and we don't know
where anything is going to be in the
editor except for the indestructible
floor surfaces so we have no chance of
pre calculating 100% effective data
ahead of time that's very different from
the projects I worked on before where
we've been able to do a lot of the baked
calculations ahead of time in the editor
and the complexity in the player builds
building situations can be become too
great a problem so you can see here you
have a bunch of AIS with the hot spots
that a eyes are mostly underneath this
structure and they're trying to path
into that pyramid up up above and it's a
complicated situation where the AIS are
trying to navigate into the pyramid and
they're destroying the structure below
and it can get really complicated and
once you you know things get more
complicated when dedicated players start
building they have a lot more time than
I do I guess to create crazy structures
so you can start to see that here and
then this is just massive structure
there so things thinking about really
complicated so as a result in the AI
it's I think it's better to be you know
good and work all the time then perfect
and fail when it you know when it comes
to the characters performance robust
solutions are important players are
novel and we you know we want to allow
them to be creative so one of the things
we do is a daily use of automated tests
as I mentioned that automated test level
we have we had before when we find
issues with the player with the AI is
attacking things for example we will
create a new test based on that pretty
much every nain system AI system in
fortnight has at least one fallback
behavior to deal with the complexities
of navigation behavior goal selection
and during development it's also
important for us to know that like the
AI are actually failing so we actually
have an additional behavior to show that
which is for development purposes
purposes only but at least we can see
when the AI is failing and moving to a
fallback and eventually if the AI fails
repeal that we know there's a really big
problem so the last problem I want to
talk about what if there's there's very
little domain knowledge to make
decisions you know like I just said
previous games like SWAT 4 and Bioshock
and bash like an infinite they use a lot
of designer place points to describe the
main knowledge to the AI and in a
procedurally generated action game this
really isn't as possible positions and
orientations they'll be different from
run to run and then you add in player
build structures and I just got to deal
with it so we make heavy use of you know
real-time spatial feature evaluation in
fortnight so it allows AI to you know
understand the current world
configuration including player built
structures and I think the the line from
Jamie Gries summer and Chris butcher's
talk about halo 1 still rings true which
is that reasoning on a continuous space
requires discrete sampling points to
make decisions about the that points
effectiveness so just to show you how we
do it in a basic way we we generate
points in the world will project those
points to a surface you can do for the
two geometry the navmesh or you can do
it to both and then you can test those
points you know to filter and to score
them you know tests can use external
values to compare distances dot product
whatever you want and we're not really
just limited to points results can come
in many forms single best result
multiple sorta results etc and so we use
real-time evaluation for all sorts of
things we do it for encounter layout so
that we can pick the best direction for
the eyes to approach from so we can pick
a spawn point so that we can put a
patrol about players so that we can
position which is a typical use of
spatial reasoning in in games even
static worlds as well we also do for
goal selection and so what's the most
important thing for the AI to be doing
right now and then you know just doing
some evaluation for the AI director
so fraud spatial reasoning also needs to
be performant we want to run lots of
servers for 490 minimal CPU such times
so we have a spatial reasoning budget
and we are constantly doing performance
analysis to make sure that everything is
going after you know using the correct
amount of resources and then you know in
general the methodology of games of the
team is that we keep the spatial
reasoning test simple but effective so
we're not again using too much
performance so here's just a little bit
more of picture fortnight just sort of
having it all come together and that's
it thank you
[Applause]
okay am I in my life okay so uh hi my
name is Damien and I I also have a
triple a background worked on a number
of games in the past where you shoot
people in the face from a first-person
perspective in fact we work together on
BioShock Infinite for almost a year a
couple years ago but uh in recent times
I've actually moved into the indie space
so I'm gonna be talking to you about a
game called the flame in the flood which
came out about three weeks ago so the
flaming the flood is a is a survival
roguelike game in a procedural world in
this case it's takes the form of a
soulful River journey down sort of this
post societal Mississippi River kind of
a don't starve meets journey or maybe
Huck Finn meets the road or something
like that
tubing meets Oregon Trail is the one
that my co-workers really like I never
played tubing so I don't know that one
but um so you float down this procedural
River and the idea is that you stop at
various sort of recognizable locations
and each time you get off your raft you
have a little a little micro world that
is populated with things like plants to
loot locations to explore AI to combat
or deal with in one way or another so
just to give you an idea I'm going to be
talking about the on foot sections the
what we call explore islands when we
talk about that section if you want to
hear about the river generation part of
it does I'm giving a talk on Thursday in
the main conference about that
so please please come to that if you're
interested but I'll just give you an
idea of what those on foot AI look like
we explore island a I put together a
helpful Survival Guide for everyone
[Music]
[Applause]
[Music]
Isis does it help if I start again
[Music]
this is playing at about half speed for
some reason
[Music]
[Applause]
[Music]
this pin I can we just mute the audio
because the audio doesn't like match at
all what's going on what this should be
showing is just basically sort of the
kinds of interactions that you have with
the AI and AI have with each other okay
well forget this it's getting slower as
we go so part of the idea was actually
inspired by some of the early pitches I
heard for Bioshock where the the talk
was of taking these different kinds of
characters they have their own sort of
internal behaviors their own way of
seeing the world there were only way of
interacting with their environments and
and you just sort of sprinkle them into
the environment together and though they
interact the way they will interact and
the gameplay comes out of the player
coming to learn what the rules of
behavior were and using to learning to
exploit one AI against the other so we
were interested in that we were going to
do something similar with you know
wolves and bears and snakes and that
kind of thing but of course like well
okay if all of the intelligence is
wrapped up in the AI itself and where
does sort of be encounter logic live
because that's typically what the
designer would be authoring and a level
designer would be authoring within a
within an authored environment so for us
the encounter sort of consists of things
like resource spawning certainly AI
spawn locations AI territories and how
they relate to their territories and the
spatial behavior that they eyes exhibit
so here's what an explorer island
consists of it's a very small relatively
small closed arena it's got a single
entrance and it's got a series of what
we call sockets where basically pieces
of geometry particularly functional
geometry so a church or a bus to sleep
in or a water fountain or something like
that can be swapped in and out
and then you know other randomized
geometry sometimes levels have these
environments have like standing water
like puddles and heat sources like
campfires and and so on so here's an
example of sort of one of the larger one
of the larger Explorer islands towards
the the bottom left is where the player
is entering the space and you can just
kind of see that it doesn't it doesn't
change a lot but it changes enough you
know the topology of the space changes
and it's changes enough that the thought
of scripting or having designers put in
hand authored metadata of any kind it
kind of seems like it's not the right
the right thing to do so we're going to
do some amount of spatial analysis to to
figure out how to place and encounter
within that space now a design goal I
mean I actually think back from I used
to work on the Halo games and one of the
design principles for encounters there
was always that the harder you push your
way into an encounter the harder the
encounter should push back and that's
sort of something that I think I've
always taken with me and in the case of
the flame in the flood the way that I
interpreted that was that the farther
into the Explorer island you go the more
dangerous it is but also the greater the
reward so like I said we don't know a
lot not a lot is fixed about these about
these spaces but we do know some stuff
we do know for example because of the
runtime navmesh generation from recast
we know what space is traversable we
know where the single exit is because
that's one of the few places that we can
have a designer mark we know where the
primary location is and and some of
those other features that I mentioned so
our approach is going to be to take that
navigable space and break it up into a
regular square grid probably the the
simplest spatial representation you
could possibly hope for
and using that grid along with the
Dijkstra's algorithm which which John
also uses we're going to create a bunch
of spatial features and the spatial
features usually take the form of
distance Maps so I'm going to create one
map over that space which says distance
to edge
for every cell in that grid how far am i
from the edge of the of the grid of the
navigable space for every cell how far
am i from the exit distance to water
distance the territory etc and so I
think if if I think if we were had been
sort of smarter we would have made the
system the very same system that does
spatial analysis for runtime positioning
for AI be the exact same system that did
spatial analysis for a spawn point
generation and that kind of thing we
didn't we didn't do that we should have
but we didn't do that but many of the
same kinds of that five minutes many of
the same kinds of decisions are made in
that way so here's the example of a you
know of one sort of typical level we'd
take this open space here here's the
discretized grid of it
those blue squares are the ones that are
in water and then you know we here are
the different features that we can
generate there's the distance to edge
there's the distance to exit there's the
distance to the water's edge so both
distance in water from the edge of the
water and distance out of the water to
the edge and and there's a an example of
a generated AI territory along with the
distance map for that so right off the
bat one of the things that I sort of
came to realize was that distance
features are always way more useful than
binary features even though something
like territory feels like a binary
feature like is the cell in the
territory for this AI or is it not it's
so much more useful to rather than just
saying yes or no to actually give a
distance to the territory now one good
reason for that for example is for using
hysteresis for territory so for example
if I have a behavior which says if the
player stands on my territory then
attack and then stop when they leave my
territory it's always better to use sort
of some sort of some level of hysteresis
to say not not just is the player not in
my territory anymore but is the player
outside of safe five meters from my
territory so that the player can't dance
back and forth over the line and turn
that behavior on and off
so here's an example of how we do loot
spawning plants sort of ah it's a sort
of higher-level
authority that decides which plants
should appear on a given island and
designers are able to sort of specify
min Max and average intervals for
appearances of certain things so
saplings if appear on average every
three Owens but never more than six
Islands that kind of thing but more
interesting is like how do we decide
spatially where to put those plants well
certainly we can sort of specify ranges
for the different spatial features so
certain plants like to spawn on the
border of of the navigable space others
like just on an open space the thing
that I think that is a sort of more
interesting that we did was to sort of
connect the rarity of the plant to the
distance from the exit so that as the
player sort of enters this space the
common plants are right around clustered
around the entrance but if they push
their way all the way through the space
and get to the sort of the most
dangerous extents of the space that's
where you're going to get the rare and
powerful plants so if the scheduler had
decided well we're going to spawn
saplings dandelion yuca and Devils
trumpet on this particular Island it
would literally divide up the space in
these four tranches and randomly spawn
within that area and of course that
supports the sort of design goal of the
farther into this space you get the
greater the danger the greater the
reward so are we out of time just
rolling all right
thanks Dave
so for AI spawning we do something
similar one simplification that we do is
that we don't evaluate spawn spawning
criteria on the individual cell level
and said we generate a series of points
basically from a jittered hex grid and
we put those points out and we consider
only those those locations we can of
course get the feature Maps you know all
the feature values for that point either
way so we're just it's just a way to
sort of reduce the number of points that
we're considering and then once we you
know once we have those points each
different kind of AI is of course going
to have its own spawning criteria and
its own sort of territorial behavior
rabbits will spawn in clusters along
with little burrows and every time they
get scared they run back to their burrow
wolves will spawn a around a around the
primary location sort of guarding the
the primary location and then once
alerted we'll just harass you until
you're either dead or you leave the
island Bears are one of my favorites
they spawn in a bear den and they're not
easily Agra but once they are ad word
they literally have to kill something
before they won't go back to their to
their spots so usually you can drag a
bear into a pack of wolves and then sit
back and watch watch the show and bored
spatially or maybe the most interesting
example actually because what they what
we do for them is to spawn is to sort of
generate an explicit territory for them
so here's an example of that we know we
know given the space and given the
distance map what the farthest point
from the exit is and so what we do is we
consider a range from 60% to 80% of that
farthest distance and we pick a point
within it and just draw a line there and
we say okay this anything beyond that is
boy land and offset from that we pick a
spawn point a little bit so that the
boar is always sort of standing around
towards the front of its of its
territory and as you come in it's always
sort of right there to challenge you
and again sort of defining that
territory as a distance map also lets
you do things like create creative
behaviors such that the bore always
tries to this position itself no matter
where you are no matter how far outside
of its own territory it has followed you
to always position itself between you
and its territory so always pushing you
back away from its own territory so
that's the basic idea you know those
specific examples of like how a rabbit
spawns versus a wolf of course are
irrelevant probably to you what's more
interesting is that all of those
criteria are defined in terms of those
spatial those spatial features that's
point number one here and again distance
features whenever I have found myself
saying oh I can get away with a binary
feature I find out three days later that
in fact distance feature is much more
interesting much more rich so again once
you have those features you end up using
them both responding criteria territory
criteria and also runtime positioning
number three Dijkstra is all your friend
is always your friend you know when all
you have is a hammer everything looks
like a nail and and Dykstra has been my
hammer for the past couple of years and
just in general like you know there are
not a lot of tight constraints beyond
what I just described on how things are
placed out in in one of these spaces but
one of the things we do of course is we
we sort of exploit the players tendency
to interpret meaning behind placements
and as long as the space is small enough
and the simulation dense enough it ends
up feeling sort of fun and structured
which is what we've been what we've been
going for so to bring it back to the
grand question of this whole talk how do
we generate encounters how do we how do
we go about generating counters without
designing the encounters well the fact
is we are still designing the encounters
we're simply designing them in terms of
abstract spatial features rather than
concrete spatial features that are
placed by a designer so we didn't go too
much over hopefully but that's where we
are thank you very much