[Script Info]
Title: 
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:00.89,0:00:04.58,Default,,0000,0000,0000,,Noah: Our next speaker is\NHerbert Wolverson.
Dialogue: 0,0:00:04.58,0:00:10.11,Default,,0000,0000,0000,,Herbert is a hobby game developer,\Nand he has been since the 1990s.
Dialogue: 0,0:00:10.11,0:00:14.71,Default,,0000,0000,0000,,He developed Nox Futura, \NOne Night in the Dungeon,
Dialogue: 0,0:00:14.71,0:00:18.95,Default,,0000,0000,0000,,and a bunch of 7DRLs.\NHe also wrote a book
Dialogue: 0,0:00:18.95,0:00:26.88,Default,,0000,0000,0000,,about Rust roguelike game development,\Nand he's currently writing another book
Dialogue: 0,0:00:26.88,0:00:29.75,Default,,0000,0000,0000,,about learning Rust through making games.
Dialogue: 0,0:00:29.75,0:00:32.73,Default,,0000,0000,0000,,This talk is called \NProcedural Map Generation Techniques,
Dialogue: 0,0:00:32.73,0:00:36.17,Default,,0000,0000,0000,,and this is acctually something I'm\Nsuper excited about, as I've always
Dialogue: 0,0:00:36.17,0:00:38.70,Default,,0000,0000,0000,,wanted someone to give a talk\Nabout this topic.
Dialogue: 0,0:00:38.70,0:00:41.02,Default,,0000,0000,0000,,So without further ado, here's Herbert.
Dialogue: 0,0:00:41.100,0:00:45.03,Default,,0000,0000,0000,,Herbert: Hi. Welcome to \NProcedural Map Generation.
Dialogue: 0,0:00:45.03,0:00:47.63,Default,,0000,0000,0000,,I'm Herbert Wolverson of\NBracket Productions,
Dialogue: 0,0:00:47.63,0:00:50.83,Default,,0000,0000,0000,,which is really just my consulting company.
Dialogue: 0,0:00:50.83,0:00:53.65,Default,,0000,0000,0000,,I'm gonna be talking to you about\Nusing algorithms to generate
Dialogue: 0,0:00:53.65,0:00:57.01,Default,,0000,0000,0000,,maps, and then using more\Nalgorithms to fix the maps you
Dialogue: 0,0:00:57.01,0:00:59.54,Default,,0000,0000,0000,,just created and find out if they're\Neven usable.
Dialogue: 0,0:01:00.40,0:01:03.08,Default,,0000,0000,0000,,There's a lot of content to cover,\Nso I'm gonna be going on
Dialogue: 0,0:01:03.08,0:01:05.41,Default,,0000,0000,0000,,at quite a rate of knots.
Dialogue: 0,0:01:05.41,0:01:08.28,Default,,0000,0000,0000,,So, who am I?\NAs Noah just said, I'm the author
Dialogue: 0,0:01:08.28,0:01:11.52,Default,,0000,0000,0000,,of the Rust Roguelike Tutorial,\Non the address on the screen there.
Dialogue: 0,0:01:11.52,0:01:15.33,Default,,0000,0000,0000,,I talk way too much on Twitter\N@herberticus. If you ever want to
Dialogue: 0,0:01:15.33,0:01:19.14,Default,,0000,0000,0000,,get in touch with me, /u/thebracket\Non Reddit is the best way to find me.
Dialogue: 0,0:01:19.14,0:01:23.11,Default,,0000,0000,0000,,I love hanging out on the roguelike\Ndev forums, answering short answer
Dialogue: 0,0:01:23.11,0:01:28.55,Default,,0000,0000,0000,,questions with SAS. I do have a book\Ncoming out very soon, Hands-on Rust:
Dialogue: 0,0:01:28.55,0:01:31.90,Default,,0000,0000,0000,,Effective Learning through 2D\NGame Development and Play,
Dialogue: 0,0:01:31.90,0:01:35.08,Default,,0000,0000,0000,,which will be out on PragProg.com.
Dialogue: 0,0:01:35.08,0:01:38.63,Default,,0000,0000,0000,,I promise I won't keep promoting that,\Nbut I really wanted to mention it,
Dialogue: 0,0:01:38.63,0:01:41.35,Default,,0000,0000,0000,,and all the sourcecode that goes with\Nthis talk can be found on GitHub
Dialogue: 0,0:01:41.35,0:01:45.48,Default,,0000,0000,0000,,at that address. That'll be repeated\Non the final slide of this presentation.
Dialogue: 0,0:01:48.28,0:01:52.00,Default,,0000,0000,0000,,So we're gonna give a quick\Nshoutout to Rogue, from 1980,
Dialogue: 0,0:01:52.00,0:01:55.57,Default,,0000,0000,0000,,because we really wouldn't be here\Nwithout it. It's one of the
Dialogue: 0,0:01:55.57,0:01:59.75,Default,,0000,0000,0000,,seminal and first uses of procedural\Ngeneration that really defined
Dialogue: 0,0:01:59.75,0:02:03.93,Default,,0000,0000,0000,,the genre. It splats out up to nine rooms,\Nconnected randomly.
Dialogue: 0,0:02:03.93,0:02:07.63,Default,,0000,0000,0000,,It's been said that they did that\Nbecause they needed to keep
Dialogue: 0,0:02:07.63,0:02:10.88,Default,,0000,0000,0000,,the game small and really couldn't\Nfit in 50 beautifully hand-designed
Dialogue: 0,0:02:10.88,0:02:14.31,Default,,0000,0000,0000,,levels, but really that created one\Nof the strengths of the genre
Dialogue: 0,0:02:14.31,0:02:18.15,Default,,0000,0000,0000,,in the first place. When you start\Na new game, you have a different
Dialogue: 0,0:02:18.15,0:02:22.94,Default,,0000,0000,0000,,map every time. So every time you\Nplay, instead of memorizing that
Dialogue: 0,0:02:22.94,0:02:26.86,Default,,0000,0000,0000,,I need to go up, up, up, right,\Nyou're learning instead that
Dialogue: 0,0:02:26.86,0:02:29.58,Default,,0000,0000,0000,,I should interact this way with\Ndifferent monsters, and interact
Dialogue: 0,0:02:29.58,0:02:32.95,Default,,0000,0000,0000,,this way with rooms, navigate like\Nthis, learning the system rather
Dialogue: 0,0:02:32.95,0:02:36.85,Default,,0000,0000,0000,,than learning the game itself,\Ngiving you effectively infinite replay.
Dialogue: 0,0:02:37.76,0:02:40.85,Default,,0000,0000,0000,,Also, any talk on procgen really\Nhas to mention Dwarf Fortress,
Dialogue: 0,0:02:40.85,0:02:43.63,Default,,0000,0000,0000,,because no other procgen game \Nhas ever managed to cram this
Dialogue: 0,0:02:43.63,0:02:46.93,Default,,0000,0000,0000,,much procedural generation into\None binary.
Dialogue: 0,0:02:46.93,0:02:50.30,Default,,0000,0000,0000,,If you haven't played it,\Ngo out and do so.
Dialogue: 0,0:02:50.30,0:02:54.47,Default,,0000,0000,0000,,Support them on Steam, and\Ntell them how awesome they are.
Dialogue: 0,0:02:54.47,0:02:58.45,Default,,0000,0000,0000,,They generate everything from \Na massive overworld with
Dialogue: 0,0:02:58.45,0:03:01.49,Default,,0000,0000,0000,,sweeping mountain ranges,\Ndense forests, volcanoes,
Dialogue: 0,0:03:01.49,0:03:05.59,Default,,0000,0000,0000,,demon-infested fortresses,\Nfill it up with procedurally-generated
Dialogue: 0,0:03:05.59,0:03:08.71,Default,,0000,0000,0000,,civilizations who either like\Nor hate each other, and then
Dialogue: 0,0:03:08.71,0:03:11.77,Default,,0000,0000,0000,,you can drill all the way down\Nto Urist and find out which
Dialogue: 0,0:03:11.77,0:03:15.36,Default,,0000,0000,0000,,proedurally-generated deity\Nhe worships, which procedurally-generated
Dialogue: 0,0:03:15.36,0:03:19.07,Default,,0000,0000,0000,,tavern he drinks in, and learn all\Nabout his quest to cross the land
Dialogue: 0,0:03:19.07,0:03:21.12,Default,,0000,0000,0000,,and find the perfect sock.
Dialogue: 0,0:03:22.18,0:03:25.77,Default,,0000,0000,0000,,At the mid-scale, you can zoom in\Nto any particular land block on the map,
Dialogue: 0,0:03:25.77,0:03:30.15,Default,,0000,0000,0000,,find out that it is beautifully rendered,\Nstill matches the overall shape
Dialogue: 0,0:03:30.15,0:03:34.65,Default,,0000,0000,0000,,of the overall world above it,\Nthe trees gain foliage, lose foliage,
Dialogue: 0,0:03:34.65,0:03:38.28,Default,,0000,0000,0000,,depending on their type and the \Ntype spawns appropriate to the biome.
Dialogue: 0,0:03:38.28,0:03:41.13,Default,,0000,0000,0000,,In other words, there is pretty much\Nevery procgen technique that you
Dialogue: 0,0:03:41.13,0:03:44.50,Default,,0000,0000,0000,,can think of in this game.\NHang out in the Bay 12 forums
Dialogue: 0,0:03:44.50,0:03:46.77,Default,,0000,0000,0000,,and that is a great place to\Nlearn about them.
Dialogue: 0,0:03:47.61,0:03:50.03,Default,,0000,0000,0000,,So one thing that's clear from\Nboth of these games is that,
Dialogue: 0,0:03:50.03,0:03:53.18,Default,,0000,0000,0000,,while they're random, their randomness\Ndoesn't define the game.
Dialogue: 0,0:03:53.18,0:03:56.59,Default,,0000,0000,0000,,The randomness is fed into an\Nalgorithm that generates something
Dialogue: 0,0:03:56.59,0:03:59.93,Default,,0000,0000,0000,,that approximates what you want \Nto get, but ensures that it is different
Dialogue: 0,0:03:59.93,0:04:03.08,Default,,0000,0000,0000,,every time. So, we're gonna\Nstart looking at some algorithms
Dialogue: 0,0:04:03.08,0:04:05.23,Default,,0000,0000,0000,,for doing that.
Dialogue: 0,0:04:05.23,0:04:07.18,Default,,0000,0000,0000,,A simple room placement.\NIf you've done any of the
Dialogue: 0,0:04:07.18,0:04:10.08,Default,,0000,0000,0000,,roguelike development tutorials,\Nthen you've seen this one.
Dialogue: 0,0:04:10.08,0:04:14.53,Default,,0000,0000,0000,,You start with a solid map. You \Npick a random rectangle.
Dialogue: 0,0:04:14.53,0:04:18.65,Default,,0000,0000,0000,,If there isn't a room already there,\Nyou fill in the rectangle.
Dialogue: 0,0:04:18.65,0:04:22.03,Default,,0000,0000,0000,,You keep adding rooms until you\Nmeet whatever criteria you've
Dialogue: 0,0:04:22.03,0:04:24.72,Default,,0000,0000,0000,,come up with for enough,\Nand then you join the rooms
Dialogue: 0,0:04:24.72,0:04:27.36,Default,,0000,0000,0000,,together with corridors.\NLet's watch this in action.
Dialogue: 0,0:04:28.76,0:04:32.03,Default,,0000,0000,0000,,As you can see, it's placing rooms\Nrandomly. When you see the
Dialogue: 0,0:04:32.03,0:04:35.33,Default,,0000,0000,0000,,red rectangles with the exclamation\Nmarks, they tried to generate one
Dialogue: 0,0:04:35.33,0:04:38.27,Default,,0000,0000,0000,,that overlaps, so you have to discard\Nit and try again.
Dialogue: 0,0:04:38.27,0:04:41.49,Default,,0000,0000,0000,,And then it joins them together with \Ncorridors. In this case, they went
Dialogue: 0,0:04:41.49,0:04:44.82,Default,,0000,0000,0000,,with a simple dog leg algorithm,\Nthat randomly switches between
Dialogue: 0,0:04:44.82,0:04:47.56,Default,,0000,0000,0000,,being either vertical first or \Nhorizontal first.
Dialogue: 0,0:04:47.56,0:04:50.59,Default,,0000,0000,0000,,That's pretty much exactly the\Nalgorithm from the Python
Dialogue: 0,0:04:50.59,0:04:57.12,Default,,0000,0000,0000,,roguelike dev tutorial that the\Nroguelike dev subreddit recommends
Dialogue: 0,0:04:57.12,0:04:59.16,Default,,0000,0000,0000,,that you start with.
Dialogue: 0,0:04:59.16,0:05:04.10,Default,,0000,0000,0000,,So a good refinement of that is\NBinary Space Partition rooms, or BSP.
Dialogue: 0,0:05:04.10,0:05:08.85,Default,,0000,0000,0000,,Binary Space Partition is fancy\Ndeveloper talk for chopping in half.
Dialogue: 0,0:05:08.85,0:05:12.36,Default,,0000,0000,0000,,It gives a similar result to\Nrandom room placement,
Dialogue: 0,0:05:12.36,0:05:15.44,Default,,0000,0000,0000,,but it pretty much guarantees\Nthat everything is better spaced out.
Dialogue: 0,0:05:15.44,0:05:18.42,Default,,0000,0000,0000,,You'll find that it's used in Nethack,\Namongst other games.
Dialogue: 0,0:05:18.84,0:05:23.19,Default,,0000,0000,0000,,So to do BSP, you divide your map\Nin half, and you randomly decide
Dialogue: 0,0:05:23.19,0:05:28.60,Default,,0000,0000,0000,,whether you want to divide vertically or\Nhorizontally, and divide that half in half.
Dialogue: 0,0:05:28.60,0:05:31.86,Default,,0000,0000,0000,,Then you keep dividing your halves\Nall the way down until you have
Dialogue: 0,0:05:31.86,0:05:35.34,Default,,0000,0000,0000,,a space that's roughly the right size\Nyou want to use for a room.
Dialogue: 0,0:05:35.34,0:05:38.65,Default,,0000,0000,0000,,And I personally like to then\Nadd a gutter of one tile around it,
Dialogue: 0,0:05:38.65,0:05:41.18,Default,,0000,0000,0000,,to ensure that you don't get rooms\Njoining together, unless that's
Dialogue: 0,0:05:41.18,0:05:43.97,Default,,0000,0000,0000,,what you want. So watching that\Nin action,
Dialogue: 0,0:05:43.97,0:05:47.73,Default,,0000,0000,0000,,you see that there's absolutely no\Nrejections, the rooms are nicely
Dialogue: 0,0:05:47.73,0:05:51.83,Default,,0000,0000,0000,,spaced out, and you wind up with\Na pretty usable map.
Dialogue: 0,0:05:51.83,0:05:56.70,Default,,0000,0000,0000,,So complete change of gear,\NCellular Automata.
Dialogue: 0,0:05:56.70,0:06:00.100,Default,,0000,0000,0000,,I personally love this one, because\Nit involves an ordered-looking
Dialogue: 0,0:06:00.100,0:06:04.90,Default,,0000,0000,0000,,natural map from complete chaos.\NYou know, I said you don't always
Dialogue: 0,0:06:04.90,0:06:07.85,Default,,0000,0000,0000,,start with complete random?\NWell, this one, you do.
Dialogue: 0,0:06:07.85,0:06:12.28,Default,,0000,0000,0000,,You can literally make half your\Nmap walls half your map floors,
Dialogue: 0,0:06:12.28,0:06:15.83,Default,,0000,0000,0000,,randomly picked, no chance of\Ngetting through it,
Dialogue: 0,0:06:15.83,0:06:18.42,Default,,0000,0000,0000,,and you'll end up with something\Nyou can use.
Dialogue: 0,0:06:18.42,0:06:22.48,Default,,0000,0000,0000,,If you played Conway's Game of Life\Nor seen articles about it,
Dialogue: 0,0:06:22.48,0:06:26.65,Default,,0000,0000,0000,,it's the same principle here.\NSo once you've got your map,
Dialogue: 0,0:06:26.65,0:06:30.05,Default,,0000,0000,0000,,you make a copy of it,\Nyou iterate every tile that isn't
Dialogue: 0,0:06:30.05,0:06:33.80,Default,,0000,0000,0000,,on the edge, and you count the number\Nof neighbors, including diagonals.
Dialogue: 0,0:06:33.80,0:06:40.23,Default,,0000,0000,0000,,If there are no neighbors, then it\Nbecomes a wall. If there's one to
Dialogue: 0,0:06:40.23,0:06:43.63,Default,,0000,0000,0000,,four neighbors, it becomes empty.\NFive or more neighbors, it becomes
Dialogue: 0,0:06:43.63,0:06:48.58,Default,,0000,0000,0000,,a wall. Now, you can and should\Ntweak these rules to suit your game.
Dialogue: 0,0:06:48.58,0:06:52.65,Default,,0000,0000,0000,,Let's watch this in action. Completely\Nrandom soup quickly turns into a
Dialogue: 0,0:06:52.65,0:06:58.21,Default,,0000,0000,0000,,far more natural looking structure that\Ncan actually be turned into a
Dialogue: 0,0:06:58.21,0:07:03.76,Default,,0000,0000,0000,,pretty useful map. And it's a really\Nsimple algorithm, really fast,
Dialogue: 0,0:07:03.76,0:07:06.84,Default,,0000,0000,0000,,and given the same seed, you get the\Nsame result every time.
Dialogue: 0,0:07:07.68,0:07:11.91,Default,,0000,0000,0000,,Next one to talk about is Drunkard's Walk.\NThis is another popular one for beginners.
Dialogue: 0,0:07:11.91,0:07:17.19,Default,,0000,0000,0000,,So the basic principle of Drunkard's Walk\Nis that you start with a solid map, find one
Dialogue: 0,0:07:17.19,0:07:21.26,Default,,0000,0000,0000,,Umber Hulk, and ply it with beer until\Nhe's staggering randomly.
Dialogue: 0,0:07:21.26,0:07:24.54,Default,,0000,0000,0000,,Place him somewhere on the map.\NAs he staggers, he randomly smashes
Dialogue: 0,0:07:24.54,0:07:28.94,Default,,0000,0000,0000,,through walls, and carving out a map.\NDon't bother worrying about whether
Dialogue: 0,0:07:28.94,0:07:34.17,Default,,0000,0000,0000,,he backtracks. Let him stagger wherever\Nhe wants. Pick a maximum distance for him
Dialogue: 0,0:07:34.17,0:07:38.75,Default,,0000,0000,0000,,to travel, or her. I'm really not sure how\NUmber Hulk's gender works.
Dialogue: 0,0:07:38.75,0:07:42.63,Default,,0000,0000,0000,,If they travel too far, they pass out,\Nand you can pick another
Dialogue: 0,0:07:42.63,0:07:47.76,Default,,0000,0000,0000,,Umber Hulk, spawn them somewhere\Nwithin the open map, and let them smash.
Dialogue: 0,0:07:47.76,0:07:51.16,Default,,0000,0000,0000,,Then you stop spawning Hulks when\Nenough of your map is open.
Dialogue: 0,0:07:51.16,0:07:53.66,Default,,0000,0000,0000,,In this case, I've used one-third of the map.
Dialogue: 0,0:07:53.66,0:07:57.18,Default,,0000,0000,0000,,So watching this in action, you can see\Nthat each Hulk is staggering
Dialogue: 0,0:07:57.18,0:08:00.88,Default,,0000,0000,0000,,completely randomly, carving out\Nmore and more of the map.
Dialogue: 0,0:08:00.88,0:08:04.34,Default,,0000,0000,0000,,One big advantage of this is that you\Ncan guarantee that your map will
Dialogue: 0,0:08:04.34,0:08:08.22,Default,,0000,0000,0000,,be contiguous. It won't generate\Nany areas that your player
Dialogue: 0,0:08:08.22,0:08:11.81,Default,,0000,0000,0000,,can't reach. It tends to give you\Nmaps that looks like it was
Dialogue: 0,0:08:11.81,0:08:17.09,Default,,0000,0000,0000,,carved out by water, ideal for\Ncreating limestone caverns and similar.
Dialogue: 0,0:08:17.34,0:08:20.48,Default,,0000,0000,0000,,Another algorithm, Diffusion Limited Aggregation.
Dialogue: 0,0:08:20.48,0:08:23.62,Default,,0000,0000,0000,,I highly recommend the RogueBasin\Narticle on this one.
Dialogue: 0,0:08:23.62,0:08:26.66,Default,,0000,0000,0000,,So for the simple version of this,\Nyou start by digging out a small
Dialogue: 0,0:08:26.66,0:08:31.32,Default,,0000,0000,0000,,target seed, and then you pick a random\Npoint anywhere on the map, a random
Dialogue: 0,0:08:31.32,0:08:34.94,Default,,0000,0000,0000,,direction, and shoot a particle.\NIf you're really lucky, the particle
Dialogue: 0,0:08:34.94,0:08:38.74,Default,,0000,0000,0000,,will hit one of the already open areas.\NIf it doesn't, you keep shooting until it
Dialogue: 0,0:08:38.74,0:08:43.72,Default,,0000,0000,0000,,hits something. Something I've\Nheard from a lot of military friends.
Dialogue: 0,0:08:43.72,0:08:48.22,Default,,0000,0000,0000,,In the event that you do hit a target\Narea, then you carve out the last solid
Dialogue: 0,0:08:48.22,0:08:52.21,Default,,0000,0000,0000,,area that you passed through. This\Ntends to give you a very winding,
Dialogue: 0,0:08:52.21,0:08:56.07,Default,,0000,0000,0000,,open map. Again, it's guaranteed\Nto be contiguous.
Dialogue: 0,0:08:56.86,0:08:59.64,Default,,0000,0000,0000,,And there's a lot of ways that you can\Ntweak the algorithm to make something
Dialogue: 0,0:08:59.64,0:09:01.25,Default,,0000,0000,0000,,more interesting.
Dialogue: 0,0:09:01.25,0:09:05.05,Default,,0000,0000,0000,,So the Central Attractor is much\Nmore likely to always hit the target.
Dialogue: 0,0:09:05.05,0:09:09.02,Default,,0000,0000,0000,,You randomly spawn your starting point\Nand then shoot the particle directly
Dialogue: 0,0:09:09.02,0:09:12.20,Default,,0000,0000,0000,,at the middle of the map.\NThis pretty much ensures that you
Dialogue: 0,0:09:12.20,0:09:15.17,Default,,0000,0000,0000,,get an open space in the middle,\Nideal, for example, for you to put
Dialogue: 0,0:09:15.17,0:09:19.30,Default,,0000,0000,0000,,a dragon with his hoard, and then\Na more interesting pattern forming
Dialogue: 0,0:09:19.30,0:09:23.35,Default,,0000,0000,0000,,around the edges, which could be where\Nthe hobbit would lurk while he
Dialogue: 0,0:09:23.35,0:09:28.37,Default,,0000,0000,0000,,torments the poor dragon. On the\Nright, you can see what happens if we
Dialogue: 0,0:09:28.37,0:09:31.46,Default,,0000,0000,0000,,use the same Central Attractor \Nalgorithm, but simply apply
Dialogue: 0,0:09:31.46,0:09:35.31,Default,,0000,0000,0000,,a symmetry down the vertical.\NYou start to get maps that look
Dialogue: 0,0:09:35.31,0:09:38.68,Default,,0000,0000,0000,,a lot like they either want to eat\Nyou, or maybe it's a butterfly,
Dialogue: 0,0:09:38.68,0:09:43.01,Default,,0000,0000,0000,,maybe it's a Space Invaders character.
Dialogue: 0,0:09:43.01,0:09:47.61,Default,,0000,0000,0000,,I recommend using this one sparingly,\Nbut a bit of symmetry like that can be
Dialogue: 0,0:09:47.61,0:09:50.48,Default,,0000,0000,0000,,applied to any algorithm when you \Nwant to produce something
Dialogue: 0,0:09:50.48,0:09:54.04,Default,,0000,0000,0000,,that looks a lot less random.
Dialogue: 0,0:09:54.04,0:09:59.56,Default,,0000,0000,0000,,Another algorithm that everyone should\Nhave in their toolkit is the
Dialogue: 0,0:09:59.56,0:10:01.62,Default,,0000,0000,0000,,Voronoi Diagram.
Dialogue: 0,0:10:01.62,0:10:05.66,Default,,0000,0000,0000,,So to make one of these, I do\Nrecommend Googling it.
Dialogue: 0,0:10:05.66,0:10:09.46,Default,,0000,0000,0000,,You randomly or deliberately place\Nseeds all over your map.
Dialogue: 0,0:10:09.46,0:10:14.41,Default,,0000,0000,0000,,You randomly place them if you \Njust want to produce something random.
Dialogue: 0,0:10:14.41,0:10:17.55,Default,,0000,0000,0000,,If you place them very deliberately -\Nfor example, you can equally space
Dialogue: 0,0:10:17.55,0:10:20.59,Default,,0000,0000,0000,,them all over the map - you can \Nproduce something that looks
Dialogue: 0,0:10:20.59,0:10:24.95,Default,,0000,0000,0000,,very, very much like a beehive.
Dialogue: 0,0:10:24.95,0:10:29.37,Default,,0000,0000,0000,,And then you iterate every point\Non the map, and it joins the
Dialogue: 0,0:10:29.37,0:10:35.72,Default,,0000,0000,0000,,area belonging to the closest seed.\NThere are various fancy algorithms,
Dialogue: 0,0:10:35.72,0:10:39.73,Default,,0000,0000,0000,,like Delaunay triangulations, to do this\Nquickly. In the source code I've
Dialogue: 0,0:10:39.73,0:10:43.52,Default,,0000,0000,0000,,provided, I just brute forced it\Nand did it the hard way.
Dialogue: 0,0:10:43.52,0:10:48.50,Default,,0000,0000,0000,,Now, one neat trick for customizing\Nwhat you get is that you can
Dialogue: 0,0:10:48.50,0:10:53.55,Default,,0000,0000,0000,,use a different distance algorithm\Nto determine which group
Dialogue: 0,0:10:53.55,0:10:58.30,Default,,0000,0000,0000,,every tile joins. So on the left, I've\Nused Pythagoras, and it gives you
Dialogue: 0,0:10:58.30,0:11:05.73,Default,,0000,0000,0000,,relatively smooth edges. Using Manhattan\Ndistance, which is the same distance
Dialogue: 0,0:11:05.73,0:11:10.25,Default,,0000,0000,0000,,that you get if you ask a New York\Ntaxi driver how far it is to get to
Dialogue: 0,0:11:10.25,0:11:13.99,Default,,0000,0000,0000,,somewhere, a number of blocks north\Nplus number of blocks east,
Dialogue: 0,0:11:13.99,0:11:19.86,Default,,0000,0000,0000,,it gives you a much more manmade-looking,\Nsharp-edged structure. And Chebychev
Dialogue: 0,0:11:19.86,0:11:23.86,Default,,0000,0000,0000,,is a similar distance algorithm, and\Ntends to give you somewhere in between
Dialogue: 0,0:11:23.86,0:11:29.06,Default,,0000,0000,0000,,the two. So what do you do with \NVoronoi diagrams? Well,
Dialogue: 0,0:11:29.06,0:11:35.13,Default,,0000,0000,0000,,the first thing you can do with them is\Nfind the edges, place walls there,
Dialogue: 0,0:11:35.13,0:11:41.09,Default,,0000,0000,0000,,and wind up with an alien cell structure.\NAnother good thing to do is
Dialogue: 0,0:11:41.09,0:11:45.42,Default,,0000,0000,0000,,decide that when you're spawning monsters,\Nyou'll spawn the monsters together
Dialogue: 0,0:11:45.42,0:11:47.64,Default,,0000,0000,0000,,within a Voronoi cell.
Dialogue: 0,0:11:47.64,0:11:51.31,Default,,0000,0000,0000,,So, for example, you've decided that the\Norc king should always be
Dialogue: 0,0:11:51.31,0:11:54.69,Default,,0000,0000,0000,,seated with his retinue. Then,\Nyou should probably spawn them
Dialogue: 0,0:11:54.69,0:11:58.69,Default,,0000,0000,0000,,in the same cell together, if possible.\NLikewise, if you decided that orcs
Dialogue: 0,0:11:58.69,0:12:02.62,Default,,0000,0000,0000,,must never, in fact, be near dark elves,\Nmake sure that you spawn them in
Dialogue: 0,0:12:02.62,0:12:07.71,Default,,0000,0000,0000,,far away cells. You can also use this\Nfor very effective city generation.
Dialogue: 0,0:12:07.71,0:12:14.57,Default,,0000,0000,0000,,In my PROCJAM game, Apocalypse Taxi,\NI used the edges of Voronoi cells to
Dialogue: 0,0:12:14.57,0:12:19.19,Default,,0000,0000,0000,,determine where the roads went, and then\Nrandomly populated the content of each
Dialogue: 0,0:12:19.19,0:12:25.79,Default,,0000,0000,0000,,cell with something like heavy industrial city,\Nlight industrial, and it worked pretty well.
Dialogue: 0,0:12:25.79,0:12:29.35,Default,,0000,0000,0000,,Combined with other techniques, this can\Nbe extremely useful.
Dialogue: 0,0:12:29.35,0:12:34.65,Default,,0000,0000,0000,,The next one up is Perlin/Simplex Noise,\Nwhich is used all over the place,
Dialogue: 0,0:12:34.65,0:12:37.52,Default,,0000,0000,0000,,more than you might think.
Dialogue: 0,0:12:37.52,0:12:42.58,Default,,0000,0000,0000,,So Perlin/Simplex Noise are basically\Na bunch of gradients combined together
Dialogue: 0,0:12:42.58,0:12:46.45,Default,,0000,0000,0000,,with a few variables we'll talk about \Nin a moment.
Dialogue: 0,0:12:46.45,0:12:51.88,Default,,0000,0000,0000,,You can generate it in either two or three\Ndimensions. If you look in X/Y value,
Dialogue: 0,0:12:51.88,0:12:56.23,Default,,0000,0000,0000,,it gives you a number between -1 and 1.
Dialogue: 0,0:12:56.23,0:13:00.68,Default,,0000,0000,0000,,And the nice thing is, if you look at\Nan adjacent one, it will be smoothly
Dialogue: 0,0:13:00.68,0:13:06.10,Default,,0000,0000,0000,,moving either up or down, \Nrelative to the neighboring squares.
Dialogue: 0,0:13:06.10,0:13:12.95,Default,,0000,0000,0000,,It's also continuous, so if you decide\Nto look from X 1 through 2,
Dialogue: 0,0:13:12.95,0:13:16.30,Default,,0000,0000,0000,,and then decide to zoom in to \N1.5 through 2, you'll actually get
Dialogue: 0,0:13:16.30,0:13:20.18,Default,,0000,0000,0000,,exactly the same shape as you saw\Non the right-hand side in the first one.
Dialogue: 0,0:13:20.18,0:13:23.18,Default,,0000,0000,0000,,So what do the variables mean?\NNow, the number of octaves
Dialogue: 0,0:13:23.18,0:13:27.98,Default,,0000,0000,0000,,give how many different gradients it's \Nmixing in. Gain is how long the various
Dialogue: 0,0:13:27.98,0:13:34.28,Default,,0000,0000,0000,,gradients last. Lacunarity adds in\Nrandomness, and as you can see,
Dialogue: 0,0:13:34.28,0:13:40.77,Default,,0000,0000,0000,,from the picture on the right-hand side,\Nwhich I guess is my left, this starts
Dialogue: 0,0:13:40.77,0:13:43.98,Default,,0000,0000,0000,,to feather it in and make it look a lot\Nmore random.
Dialogue: 0,0:13:43.98,0:13:47.09,Default,,0000,0000,0000,,Now, frequency is how frequently\Neach of the various octaves
Dialogue: 0,0:13:47.09,0:13:53.34,Default,,0000,0000,0000,,peaks. So, what I recommend you do\Nis find a Perlin/Simplex Noise tool
Dialogue: 0,0:13:53.34,0:13:56.69,Default,,0000,0000,0000,,and simply play with these values until\Nyou get something that you like.
Dialogue: 0,0:13:56.69,0:13:59.92,Default,,0000,0000,0000,,So what can you do with them?\NThe answer is actually quite a lot.
Dialogue: 0,0:13:59.92,0:14:05.31,Default,,0000,0000,0000,,The most common use is to make \Nan overworld. Because Perlin
Dialogue: 0,0:14:05.31,0:14:09.19,Default,,0000,0000,0000,,is deterministic by random seed,\Nevery time you use the same seed,
Dialogue: 0,0:14:09.19,0:14:12.47,Default,,0000,0000,0000,,you get the same map.\NNow, what I've done here is
Dialogue: 0,0:14:12.47,0:14:19.14,Default,,0000,0000,0000,,altitudes from -1 to 0 blued out\Nas water, altitudes from 0 to .75
Dialogue: 0,0:14:19.14,0:14:23.79,Default,,0000,0000,0000,,are in green, shaded as terrain,\Naltitudes above that are marked
Dialogue: 0,0:14:23.79,0:14:28.39,Default,,0000,0000,0000,,as mountains. And this is very common.\NYou'll find this used in a lot of games.
Dialogue: 0,0:14:28.39,0:14:32.15,Default,,0000,0000,0000,,And as I mentioned, you can zoom in.\NSo as you zoom in, you start to see more
Dialogue: 0,0:14:32.15,0:14:36.02,Default,,0000,0000,0000,,of the gradient. The problem is\Nthat the gradients are actually
Dialogue: 0,0:14:36.02,0:14:38.10,Default,,0000,0000,0000,,kind of dull.
Dialogue: 0,0:14:38.10,0:14:41.72,Default,,0000,0000,0000,,Now, you can fix that. The best way\Nto fix that is to make a second layer
Dialogue: 0,0:14:41.72,0:14:45.75,Default,,0000,0000,0000,,of noise. So in this case, we've got a\Nsecond layer of noise that is much more
Dialogue: 0,0:14:45.75,0:14:49.58,Default,,0000,0000,0000,,bumpy, has much more fine-grained\Ndetail, but looks terrible as
Dialogue: 0,0:14:49.58,0:14:53.83,Default,,0000,0000,0000,,a continent as a whole.\NAnd then as you zoom in,
Dialogue: 0,0:14:53.83,0:14:56.45,Default,,0000,0000,0000,,you change the percentage of each\Nof the two gradients that you're
Dialogue: 0,0:14:56.45,0:15:01.02,Default,,0000,0000,0000,,mixing together. So when you're zoomed\Nall the way out like that, you're seeing
Dialogue: 0,0:15:01.02,0:15:04.73,Default,,0000,0000,0000,,the relatively coherent overworld.\NAs you start to zoom in, you see
Dialogue: 0,0:15:04.73,0:15:08.56,Default,,0000,0000,0000,,bays, peaks, valleys, troughs.\NAnd the great thing is, this is
Dialogue: 0,0:15:08.56,0:15:11.85,Default,,0000,0000,0000,,actually really easy to implement.\NThere's a lot of really good
Dialogue: 0,0:15:11.85,0:15:16.81,Default,,0000,0000,0000,,Perlin/Simplex libraries out there.\NI highly recommend it.
Dialogue: 0,0:15:16.81,0:15:20.03,Default,,0000,0000,0000,,You can use it for anything from making\Na pirate game with cool seas
Dialogue: 0,0:15:20.03,0:15:23.56,Default,,0000,0000,0000,,to sail around, or just building the\Noverworld for your map.
Dialogue: 0,0:15:23.56,0:15:29.79,Default,,0000,0000,0000,,You can also use it if you want\Nto generate realistic-looking
Dialogue: 0,0:15:29.79,0:15:34.08,Default,,0000,0000,0000,,clouds, particles. You can even make\Nwood grain with it, with the right values.
Dialogue: 0,0:15:34.90,0:15:38.53,Default,,0000,0000,0000,,And that brings me to one point\Nthat I can't emphasize enough.
Dialogue: 0,0:15:38.53,0:15:44.34,Default,,0000,0000,0000,,You very rarely need to use just\None technique on a map.
Dialogue: 0,0:15:44.34,0:15:49.59,Default,,0000,0000,0000,,So here, on the top left, we've used\NWSP technique to produce a
Dialogue: 0,0:15:49.59,0:15:54.24,Default,,0000,0000,0000,,pretty linear-looking dwarven fortress.\NOn the right, Cellular Automata
Dialogue: 0,0:15:54.24,0:15:59.22,Default,,0000,0000,0000,,has made a really open-looking\Nsort of cavern system. It might
Dialogue: 0,0:15:59.22,0:16:02.54,Default,,0000,0000,0000,,be a dangerous underworld. \NSo running with that theme,
Dialogue: 0,0:16:02.54,0:16:06.82,Default,,0000,0000,0000,,I simply took the left half of the\Ndwarven fortress and the right half
Dialogue: 0,0:16:06.82,0:16:11.62,Default,,0000,0000,0000,,of the Cellular Automata, and you\Nhave what looks like a fortress
Dialogue: 0,0:16:11.62,0:16:16.77,Default,,0000,0000,0000,,that suddenly breaks out into a nasty\Nunderworld. Well, I thought,
Dialogue: 0,0:16:16.77,0:16:20.62,Default,,0000,0000,0000,,a better theme for that might be that\Nthe dwarves were digging, they
Dialogue: 0,0:16:20.62,0:16:23.32,Default,,0000,0000,0000,,came to the underworld, and they\Nneeded to protect themselves.
Dialogue: 0,0:16:23.32,0:16:28.00,Default,,0000,0000,0000,,So I added a prefab, a predesigned\Nsection in the middle, adding fortifications.
Dialogue: 0,0:16:28.00,0:16:31.85,Default,,0000,0000,0000,,And so, with two very simple techniques,\Nyou've produced a map that actually
Dialogue: 0,0:16:31.85,0:16:36.09,Default,,0000,0000,0000,,tells a story, rather than just\Nbeing a bunch of random rooms.
Dialogue: 0,0:16:36.09,0:16:40.32,Default,,0000,0000,0000,,Another popular combination is\Ntake a map and then use DLA
Dialogue: 0,0:16:40.32,0:16:43.70,Default,,0000,0000,0000,,to fire particles at it, and blast\Nparts of the map away.
Dialogue: 0,0:16:43.70,0:16:46.93,Default,,0000,0000,0000,,This starts to look like dwarves failed\Nto pay their maintenance bill,
Dialogue: 0,0:16:46.93,0:16:52.37,Default,,0000,0000,0000,,or had a serious water problem,\Nas the map becomes more and more
Dialogue: 0,0:16:52.37,0:16:55.94,Default,,0000,0000,0000,,organic-looking while keeping its\Nbasic structure.
Dialogue: 0,0:16:55.94,0:17:00.62,Default,,0000,0000,0000,,I mentioned prefabs before.\NPrefabs are a great idea.
Dialogue: 0,0:17:00.62,0:17:05.02,Default,,0000,0000,0000,,So you can make a massively\Nrandom map, but if you start injecting
Dialogue: 0,0:17:05.02,0:17:08.31,Default,,0000,0000,0000,,human design elements into it, then you\Nget the chance to really make the game
Dialogue: 0,0:17:08.31,0:17:09.91,Default,,0000,0000,0000,,your own.
Dialogue: 0,0:17:09.91,0:17:13.23,Default,,0000,0000,0000,,So I've got a prefab here that is\Ndefinitely not a trap. It's death
Dialogue: 0,0:17:13.23,0:17:17.08,Default,,0000,0000,0000,,traps surrounding a treasure chest.\NYou've probably seen that in a lot
Dialogue: 0,0:17:17.08,0:17:20.51,Default,,0000,0000,0000,,of console RPGs. You enter a\Nroom, you see a chest,
Dialogue: 0,0:17:20.51,0:17:22.91,Default,,0000,0000,0000,,with nothing guarding it.\NYou can be pretty sure that
Dialogue: 0,0:17:22.91,0:17:25.43,Default,,0000,0000,0000,,something bad's about to happen to you.
Dialogue: 0,0:17:25.43,0:17:30.26,Default,,0000,0000,0000,,So the room structure makes it relatively\Neasy to place a prefab. You can go
Dialogue: 0,0:17:30.26,0:17:34.22,Default,,0000,0000,0000,,through the room list, find a room that's\Nbigger than the prefab, and you know
Dialogue: 0,0:17:34.22,0:17:36.09,Default,,0000,0000,0000,,the prefab fits there.
Dialogue: 0,0:17:36.09,0:17:39.29,Default,,0000,0000,0000,,On a map that doesn't have rooms,\Nit can be a little more tricky.
Dialogue: 0,0:17:39.29,0:17:42.99,Default,,0000,0000,0000,,What I usually do is I pick random\Nlocations, look and see if the prefab
Dialogue: 0,0:17:42.99,0:17:47.66,Default,,0000,0000,0000,,will fit, and place them. If it won't,\Nthen I don't place it there.
Dialogue: 0,0:17:47.66,0:17:52.71,Default,,0000,0000,0000,,If I've got a nice, big list of prefabs,\Nthen I'll keep going until I've added
Dialogue: 0,0:17:52.71,0:17:56.02,Default,,0000,0000,0000,,a few of them and been careful not to\Nadd all of them, so the game is
Dialogue: 0,0:17:56.02,0:17:58.31,Default,,0000,0000,0000,,different next time I play.
Dialogue: 0,0:17:58.31,0:18:01.61,Default,,0000,0000,0000,,Very quick change of gears,\Nbecause the next set of algorithms
Dialogue: 0,0:18:01.61,0:18:05.64,Default,,0000,0000,0000,,all are going to rely on this one,\Nthe Dijkstra maps.
Dialogue: 0,0:18:05.64,0:18:08.69,Default,,0000,0000,0000,,I highly recommend that you go to\NRogueBasin and read
Dialogue: 0,0:18:08.69,0:18:13.82,Default,,0000,0000,0000,,The Incredible Power of Dijkstra Maps\Non there. It is an excellent article.
Dialogue: 0,0:18:13.82,0:18:18.82,Default,,0000,0000,0000,,And Dijkstra maps are a very powerful\Ntool if you're into making roguelikes.
Dialogue: 0,0:18:18.82,0:18:21.34,Default,,0000,0000,0000,,I recommend that you learn about them.
Dialogue: 0,0:18:21.34,0:18:25.23,Default,,0000,0000,0000,,To make them, you start with one\Nor more starting points.
Dialogue: 0,0:18:25.23,0:18:29.77,Default,,0000,0000,0000,,In this case, the blue knight. The rest\Nof the map gets marked to a sentinel
Dialogue: 0,0:18:29.77,0:18:33.100,Default,,0000,0000,0000,,value, meaning you can't go there.\NAnd then you look at all the tiles
Dialogue: 0,0:18:33.100,0:18:37.35,Default,,0000,0000,0000,,adjacent to your starting point.\NIf you can walk into them, you put
Dialogue: 0,0:18:37.35,0:18:42.07,Default,,0000,0000,0000,,a 1 on them. You can get there\Nin one step away from the starting point.
Dialogue: 0,0:18:42.07,0:18:46.53,Default,,0000,0000,0000,,Then you keep going. So every\Nwalkable tile that's next to a 1
Dialogue: 0,0:18:46.53,0:18:49.55,Default,,0000,0000,0000,,gets a 2, and a 3, and a 4, and a 5.
Dialogue: 0,0:18:49.55,0:18:54.46,Default,,0000,0000,0000,,Eventually, you have a complete\Nmap that tells you, first of all,
Dialogue: 0,0:18:54.46,0:19:06.16,Default,,0000,0000,0000,,the sentinel value means that you\Ncan't go there. So now, you've got
Dialogue: 0,0:19:06.16,0:19:11.100,Default,,0000,0000,0000,,a list of all the cells you can't use.\NLikewise, the numbered tiles tell
Dialogue: 0,0:19:11.100,0:19:16.56,Default,,0000,0000,0000,,you how far away you are from \Na starting point.
Dialogue: 0,0:19:16.56,0:19:20.14,Default,,0000,0000,0000,,So the first big use for this is when\Nyou've generated something like
Dialogue: 0,0:19:20.14,0:19:23.96,Default,,0000,0000,0000,,Cellular Automata, that can give you\Nchunks of a map that you can't get to.
Dialogue: 0,0:19:23.96,0:19:27.68,Default,,0000,0000,0000,,Pick a central point, find one\Nthat's open, generate a
Dialogue: 0,0:19:27.68,0:19:32.34,Default,,0000,0000,0000,,Dijkstra map, and then all of the\Ntiles that are open that have the
Dialogue: 0,0:19:32.34,0:19:36.01,Default,,0000,0000,0000,,sentinel value on your Dijkstra map\Ncan't be reached, and I've highlighted
Dialogue: 0,0:19:36.01,0:19:39.15,Default,,0000,0000,0000,,those in red on the map.\NYou can delete those, because
Dialogue: 0,0:19:39.25,0:19:42.90,Default,,0000,0000,0000,,nobody can get there. Or,\Nif you've got a game system
Dialogue: 0,0:19:42.90,0:19:46.52,Default,,0000,0000,0000,,that encourages tunneling, then go\Nahead and hide the stuff that needs
Dialogue: 0,0:19:46.52,0:19:50.43,Default,,0000,0000,0000,,to be reached with tunneling\Nin those areas.
Dialogue: 0,0:19:50.43,0:19:53.75,Default,,0000,0000,0000,,This can also help you with placing\Na starting point on your map.
Dialogue: 0,0:19:53.75,0:19:59.02,Default,,0000,0000,0000,,Making sure that you cull the\Nunreachable areas before
Dialogue: 0,0:19:59.02,0:20:03.25,Default,,0000,0000,0000,,you pick a starting point ensures\Nthat you won't place the player
Dialogue: 0,0:20:03.25,0:20:06.18,Default,,0000,0000,0000,,somewhere that they can't \Nget out of, and it avoids the
Dialogue: 0,0:20:06.18,0:20:09.95,Default,,0000,0000,0000,,always embarassing case of the\Nmap that's only got two tiles
Dialogue: 0,0:20:09.95,0:20:12.70,Default,,0000,0000,0000,,that you can actually walk on.
Dialogue: 0,0:20:12.70,0:20:14.85,Default,,0000,0000,0000,,That has happened to me.
Dialogue: 0,0:20:14.85,0:20:18.04,Default,,0000,0000,0000,,So typically, to place a starting point,\Nif I know that I want to be on the
Dialogue: 0,0:20:18.04,0:20:21.95,Default,,0000,0000,0000,,left, I'll place somewhere in the \Nmiddle on the left, and then I'll
Dialogue: 0,0:20:21.95,0:20:26.01,Default,,0000,0000,0000,,simply look around for a neighboring\Ntile that is open and hasn't been culled
Dialogue: 0,0:20:26.01,0:20:28.10,Default,,0000,0000,0000,,by the Dijkstra map.
Dialogue: 0,0:20:28.10,0:20:30.58,Default,,0000,0000,0000,,To find an endpoint, you can\Nuse the same thing, if you want
Dialogue: 0,0:20:30.58,0:20:35.18,Default,,0000,0000,0000,,to go left to right. A lot of\Ngames prefer to have more of a
Dialogue: 0,0:20:35.18,0:20:39.58,Default,,0000,0000,0000,,structured progression.\NOnce you've culled the map,
Dialogue: 0,0:20:39.58,0:20:44.63,Default,,0000,0000,0000,,you know that anywhere on the map\Ncan be - that is still open after you've
Dialogue: 0,0:20:44.63,0:20:48.03,Default,,0000,0000,0000,,removed the areas you can't get to,\Nit's safe to place an exit.
Dialogue: 0,0:20:48.03,0:20:54.36,Default,,0000,0000,0000,,So you find the rough area you want\Nto put the exit and you place on a nearby
Dialogue: 0,0:20:54.36,0:20:59.64,Default,,0000,0000,0000,,open tile. I've gone ahead and marked \Nthe optimal route through that map.
Dialogue: 0,0:21:00.59,0:21:04.18,Default,,0000,0000,0000,,You can also, if you really dislike\Nyour player, use Dijkstra to find
Dialogue: 0,0:21:04.18,0:21:07.49,Default,,0000,0000,0000,,the least accessible part of the \Nmap and put the exit there.
Dialogue: 0,0:21:07.49,0:21:10.43,Default,,0000,0000,0000,,If they're starting in the middle,\Nthis is a really bad idea,
Dialogue: 0,0:21:10.43,0:21:16.16,Default,,0000,0000,0000,,because three-quarters of the map\Nis basically irrelevant.
Dialogue: 0,0:21:16.16,0:21:19.70,Default,,0000,0000,0000,,However, if you want to hide something,\Nthis is a great way to do it.
Dialogue: 0,0:21:19.70,0:21:22.24,Default,,0000,0000,0000,,Find the starting point, then find\Nthe least accessible point on
Dialogue: 0,0:21:22.24,0:21:25.84,Default,,0000,0000,0000,,the map, hide something there, and\Nyou force the player to go on a
Dialogue: 0,0:21:25.84,0:21:29.07,Default,,0000,0000,0000,,treasure hunt, if they're gonna get\Nthe bonus item.
Dialogue: 0,0:21:29.62,0:21:32.76,Default,,0000,0000,0000,,That leads to one of my favorite\Ntechniques for refining a map,
Dialogue: 0,0:21:32.76,0:21:35.37,Default,,0000,0000,0000,,once you've generated it. \NI call it the "Hot Path."
Dialogue: 0,0:21:35.37,0:21:38.52,Default,,0000,0000,0000,,Once you've got your start point\Nand your end point, you generate
Dialogue: 0,0:21:38.52,0:21:41.74,Default,,0000,0000,0000,,the path between the two.\NI use ASTAR. In this case,
Dialogue: 0,0:21:41.74,0:21:47.62,Default,,0000,0000,0000,,I think I used a Dijkstra map and just\Nwalked the distance between the two.
Dialogue: 0,0:21:47.62,0:21:52.06,Default,,0000,0000,0000,,Then you make another Dijkstra map,\Nusing all the points on the path as
Dialogue: 0,0:21:52.06,0:21:57.61,Default,,0000,0000,0000,,your hot path. Then, on that Dijkstra map,\Neverything with a tile value of under,
Dialogue: 0,0:21:57.61,0:22:03.15,Default,,0000,0000,0000,,say ten, is the hot path and is\Nclose, but not necessarily directly
Dialogue: 0,0:22:03.15,0:22:06.65,Default,,0000,0000,0000,,on the best path through the dungeon.
Dialogue: 0,0:22:06.65,0:22:10.78,Default,,0000,0000,0000,,So what can you do with this?\NWell, if you prefer a less-branchy game,
Dialogue: 0,0:22:10.78,0:22:14.40,Default,,0000,0000,0000,,you can use it to remove the parts of\Nthe map that are completely irrelevant.
Dialogue: 0,0:22:14.40,0:22:20.53,Default,,0000,0000,0000,,If your game involves a great deal of\Nprogression from, say, left to right,
Dialogue: 0,0:22:20.53,0:22:24.78,Default,,0000,0000,0000,,this is a good way to do it, and a\Ngood way to not force the player
Dialogue: 0,0:22:24.78,0:22:29.86,Default,,0000,0000,0000,,to explore huge, winding labyrinths\Nwith no real purpose to them.
Dialogue: 0,0:22:29.86,0:22:34.26,Default,,0000,0000,0000,,If you're using a room-based generation,\Nthen this can be even more useful.
Dialogue: 0,0:22:34.26,0:22:37.31,Default,,0000,0000,0000,,I've marked in yellow the rooms that are\Non the hot path that go directly
Dialogue: 0,0:22:37.31,0:22:40.66,Default,,0000,0000,0000,,from point A to point B.\NAlso, that means the grey
Dialogue: 0,0:22:40.66,0:22:43.99,Default,,0000,0000,0000,,rooms aren't really necessary.\NOr are they?
Dialogue: 0,0:22:43.99,0:22:48.92,Default,,0000,0000,0000,,Maybe the grey rooms could be culled,\Nif you just want to have a go to room,
Dialogue: 0,0:22:48.92,0:22:52.54,Default,,0000,0000,0000,,go to room, go to room type of game.\NOr, the grey rooms could be where
Dialogue: 0,0:22:52.54,0:22:56.59,Default,,0000,0000,0000,,you hide bonus things. You might have\Nthe yellow rooms mark some breadcrumbs
Dialogue: 0,0:22:56.59,0:23:00.85,Default,,0000,0000,0000,,to give the player a clue as to where\Nto go, and teach them by putting
Dialogue: 0,0:23:00.85,0:23:04.01,Default,,0000,0000,0000,,really scary things in the grey area\Nthat are off the beaten path
Dialogue: 0,0:23:04.01,0:23:07.84,Default,,0000,0000,0000,,and only to be done once you're\Na little more experienced.
Dialogue: 0,0:23:08.87,0:23:14.90,Default,,0000,0000,0000,,You can also use this knowledge\Nto order the progression of the story.
Dialogue: 0,0:23:14.90,0:23:18.35,Default,,0000,0000,0000,,So you know that if the player's gonna\Ngo through this dungeon, they're
Dialogue: 0,0:23:18.35,0:23:22.22,Default,,0000,0000,0000,,probably gonna go through one to nine.
Dialogue: 0,0:23:22.22,0:23:27.45,Default,,0000,0000,0000,,And that's okay. If you're telling\Na story, let's say your grandfather
Dialogue: 0,0:23:27.45,0:23:32.63,Default,,0000,0000,0000,,tells you that it is your destiny to go out\Nand save the world, he's probably
Dialogue: 0,0:23:32.63,0:23:36.02,Default,,0000,0000,0000,,going to want to tell you that somewhere\Naround room one, so you can't avoid
Dialogue: 0,0:23:36.02,0:23:39.100,Default,,0000,0000,0000,,the old windbag. Somewhere around\Ntwo, somebody should show up and
Dialogue: 0,0:23:39.100,0:23:43.68,Default,,0000,0000,0000,,tell you that your destiny is futile,\Nyou should abandon it,
Dialogue: 0,0:23:43.68,0:23:49.00,Default,,0000,0000,0000,,give up, and the whole adventuring\Nthing isn't for you, and so on.
Dialogue: 0,0:23:49.60,0:23:52.80,Default,,0000,0000,0000,,Alternatively, you might have decided\Nthat you wanted to do the old
Dialogue: 0,0:23:52.80,0:23:56.20,Default,,0000,0000,0000,,saw of the locked door that has a\Nkey somewhere on the map.
Dialogue: 0,0:23:56.20,0:24:01.01,Default,,0000,0000,0000,,Supposing that you've decided that room\Nfive is gonna be where the locked
Dialogue: 0,0:24:01.01,0:24:05.13,Default,,0000,0000,0000,,door shall be, it would be a good choice\Nbecause you can do a flood-fill and
Dialogue: 0,0:24:05.13,0:24:09.23,Default,,0000,0000,0000,,discover that there's nowhere else,\Nthere's no alternates to going through
Dialogue: 0,0:24:09.23,0:24:11.76,Default,,0000,0000,0000,,the exit from room five.
Dialogue: 0,0:24:11.76,0:24:15.85,Default,,0000,0000,0000,,So you place a locked door there, and\Nnow you absolutely know that the key
Dialogue: 0,0:24:15.85,0:24:19.06,Default,,0000,0000,0000,,has to be somewhere between rooms\None and four, for this to be a
Dialogue: 0,0:24:19.06,0:24:22.91,Default,,0000,0000,0000,,solvable puzzle. It would really suck\Nif you decided to spawn the key
Dialogue: 0,0:24:22.91,0:24:27.51,Default,,0000,0000,0000,,in room six, and leave yourself with \Na map that cannot be solved
Dialogue: 0,0:24:27.51,0:24:30.43,Default,,0000,0000,0000,,without finding some other way to\Nopen the door. You know, unless
Dialogue: 0,0:24:30.43,0:24:35.09,Default,,0000,0000,0000,,of course that's your point.\NAnd really, that is the point
Dialogue: 0,0:24:35.09,0:24:38.56,Default,,0000,0000,0000,,of what I've been trying to say,\Nis guide your randomness
Dialogue: 0,0:24:38.56,0:24:41.68,Default,,0000,0000,0000,,and then use algorithms to check\Nyour randomness, to make sure that
Dialogue: 0,0:24:41.68,0:24:44.56,Default,,0000,0000,0000,,it matches what you want.
Dialogue: 0,0:24:44.56,0:24:46.82,Default,,0000,0000,0000,,I've written quite a bit about\Nother algorithms on my
Dialogue: 0,0:24:46.82,0:24:51.11,Default,,0000,0000,0000,,roguelike tutorial, tried really hard to\Nbe language-agnostic, even though
Dialogue: 0,0:24:51.11,0:24:55.24,Default,,0000,0000,0000,,all the examples are in Rust.\NSo, I do recommend checking there
Dialogue: 0,0:24:55.24,0:24:58.69,Default,,0000,0000,0000,,for a few more. I wanted to talk about\NWave Form Collapse, and realized
Dialogue: 0,0:24:58.69,0:25:01.02,Default,,0000,0000,0000,,that I needed another 30 minutes.
Dialogue: 0,0:25:01.82,0:25:06.90,Default,,0000,0000,0000,,Alright, so like I said before, the source\Ncode for this talk is all up on my GitHub.
Dialogue: 0,0:25:06.90,0:25:10.30,Default,,0000,0000,0000,,That repost should have gone public\Na few minutes ago.
Dialogue: 0,0:25:10.30,0:25:14.72,Default,,0000,0000,0000,,And just to be a terrible shill one more\Ntime, my book
Dialogue: 0,0:25:14.72,0:25:18.30,Default,,0000,0000,0000,,Hands-on Rust: Effective Learning through\N2D Game Development and Play
Dialogue: 0,0:25:18.30,0:25:23.84,Default,,0000,0000,0000,,will be in beta on PragProg relatively\Nsoon, next few weeks, as long as
Dialogue: 0,0:25:23.84,0:25:27.67,Default,,0000,0000,0000,,I get off my butt and finish editing it,\Nand in your favorite bookstore
Dialogue: 0,0:25:27.67,0:25:31.27,Default,,0000,0000,0000,,pretty soon. If there's any questions,\NI'd be happy to take them.
Dialogue: 0,0:25:33.17,0:25:35.38,Default,,0000,0000,0000,,Noah: Wonderful. Thank you so\Nmuch for that talk.
Dialogue: 0,0:25:35.38,0:25:39.92,Default,,0000,0000,0000,,Herbert: Thanks for having me.\NNoah: Yeah. We have a few questions.
Dialogue: 0,0:25:40.56,0:25:44.25,Default,,0000,0000,0000,,The first one is from Darren Gray,\Nwho asks, "How do you make
Dialogue: 0,0:25:44.25,0:25:48.45,Default,,0000,0000,0000,,generated maps not look very \Nsamey?" For example, he says that
Dialogue: 0,0:25:48.45,0:25:52.62,Default,,0000,0000,0000,,he can always notice when an\Noverworld is generated with
Dialogue: 0,0:25:52.62,0:25:55.18,Default,,0000,0000,0000,,Perlin noise.
Dialogue: 0,0:25:55.18,0:25:58.100,Default,,0000,0000,0000,,Herbert: Yeah, that's actually a fun one,\Nand I play spot the Perlin.
Dialogue: 0,0:25:58.100,0:26:03.18,Default,,0000,0000,0000,,One of the best things to do is\Nto generate multiple noise maps
Dialogue: 0,0:26:03.18,0:26:07.73,Default,,0000,0000,0000,,and mix them together. So if you've\Ndecided that this region is mountains,
Dialogue: 0,0:26:07.73,0:26:17.06,Default,,0000,0000,0000,,start mixing in height values from another\Nmore mountainous-looking height map.
Dialogue: 0,0:26:17.06,0:26:20.14,Default,,0000,0000,0000,,That gets you something that is,\Nas well as just going up,
Dialogue: 0,0:26:20.14,0:26:22.99,Default,,0000,0000,0000,,actually goes up and down, up and \Ndown, and starts to look more like
Dialogue: 0,0:26:22.99,0:26:25.71,Default,,0000,0000,0000,,mountains and less like a boring\Nlittle gradient.
Dialogue: 0,0:26:25.71,0:26:29.16,Default,,0000,0000,0000,,You can also have a lot of fun\Ngenerating your Perlin, and then
Dialogue: 0,0:26:29.16,0:26:32.63,Default,,0000,0000,0000,,run something like a Russian\Non it. Running a simpler
Dialogue: 0,0:26:32.63,0:26:36.11,Default,,0000,0000,0000,,Russian simluator, especially if you\Ndecide that some rocks are
Dialogue: 0,0:26:36.11,0:26:38.92,Default,,0000,0000,0000,,harder than others, gives you\Na beautiful map in no time.
Dialogue: 0,0:26:38.92,0:26:41.39,Default,,0000,0000,0000,,I think that's how World Machine works.
Dialogue: 0,0:26:42.34,0:26:46.94,Default,,0000,0000,0000,,Noah: Cool. Our next question is\Ndo you know any techniques for
Dialogue: 0,0:26:46.94,0:26:51.61,Default,,0000,0000,0000,,generating vertical structures,\Nor Z levels in map generation?
Dialogue: 0,0:26:52.32,0:26:55.31,Default,,0000,0000,0000,,Herbert: That is something I am\Nhonestly terrible at.
Dialogue: 0,0:26:55.31,0:26:58.56,Default,,0000,0000,0000,,I've seen Wave Form Collapse\Nused to make some absolutely
Dialogue: 0,0:26:58.56,0:27:03.02,Default,,0000,0000,0000,,amazing Voxel-based cities. I can't\Nhonestly pretend that I know how
Dialogue: 0,0:27:03.02,0:27:05.45,Default,,0000,0000,0000,,to do that.
Dialogue: 0,0:27:06.35,0:27:09.79,Default,,0000,0000,0000,,Noah: Cool. That looks like all \Nof the questions that people have
Dialogue: 0,0:27:09.79,0:27:12.38,Default,,0000,0000,0000,,put in.
Dialogue: 0,0:27:12.38,0:27:15.62,Default,,0000,0000,0000,,But thank you so much, and\Nthen I'm sure if you hang out
Dialogue: 0,0:27:15.62,0:27:19.39,Default,,0000,0000,0000,,somewhere in the social space, people \Nwill come and ask you more questions.
Dialogue: 0,0:27:19.39,0:27:22.35,Default,,0000,0000,0000,,Herbert: Yes, I should be around\Nthere and on the Discord tonight.
Dialogue: 0,0:27:22.35,0:27:26.40,Default,,0000,0000,0000,,I'll be editing my book and alternating\Nbetween the two. Thank you.
Dialogue: 0,0:27:26.40,0:27:28.16,Default,,0000,0000,0000,,Noah: Cool, thanks so much.