This repository has been archived by the owner on Mar 8, 2021. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 140
Procedural Dungeon Generation #3 #47
Labels
Comments
Great to see ya still sharing your insights with us. I first saw the gif on Reddit and was hoping that you would write about it here. I am so glad you did :). I like the physics part remembered me off your Delauney Tut on Gamasutra ;). |
Hey love your work. Would it be possible to see the full code for this. I am a complete noob at coding |
@FlaminThunda the code is linked in the last paragraph of the OP, not far above your post! |
Sign up for free
to subscribe to this conversation on GitHub.
Already have an account?
Sign in.
This post will explain a technique for generating an overmap lightly inspired by the one in Slay the Spire. The general way it works is like this:
Physics Step
The first thing we want to do is generate the nodes that will make up our graph. The way I decided to do this was by spawning a bunch of box2d circles and letting the physics engine separate them as the simulation moves forwards. We create all those circles inside a rectangular boundary for this example and the way it looks is like this:
The code to make this happen is fairly simple. For instance, the function to create a circle looks like this:
This is a pretty standard way of creating a physics circle with box2d and should be the same or similar everywhere. And then we create multiple of those physics circles like this:
Here there's a simple table full of different values
6
,8
and10
which represent the different sizes for all possible circles. This way we can create a graph that already has differently sized circles which will correspond to different types of nodes in the overmap. One of the advantages of using the physics engine here is that we can create objects of different shapes and sizes, as well as play with the shape and size of the bounding object, and everything will still be neatly separated without any extra work.After this we can move the simulation forward until we're happy with it. I choose 500 steps but you may choose a different number:
After the simulation is done we can transform these physics objects into nodes that will make up the graph that represents the overmap:
Additionally we also destroy the physics world we previously created and all the bodies, fixtures and shapes with it. The only data structure we care about now is
graph
, which contains all the nodes as tables withx
,y
andradius
attributes.Pathing Step
In this step we'll take this graph, connect all nodes to their nearest neighbors, and then create the paths in the graph that will represent our final overmap. The first step is the connection of all nodes which looks like this:
And the code to achieve that is this:
Here we're just going through all nodes and for each node we're checking which other nodes are close enough and adding those nodes to a
neighbors
attribute. Now each node is a table withx
,y
,radius
andneighbors
, which is another table containing references to other nodes in thegraph
table.The next two things we'll do is select the nodes that will make up our overmap. This will be divided into vertical and horizontal steps. The vertical step will pick a random at the top of our graph and walk randomly down until it can't do that anymore. We'll repeat this step twice.
The horizontal step will pick a randomly already selected node from one of the vertical steps and then walk randomly either left or right based on how far away the picked node is from left/right edge. If a node is further away from the left edge then we will walk left, otherwise we'll walk right.
All this put together looks like this:
For the purposes of these gifs each vertical step is colored red and green, and the horizontal steps are colored blue. The code to achieve the vertical step looks like this:
This picks a top node until it picks one that isn't selected, and here we also set the
selected
attribute to the number passed in to the function. For the vertical step we'll callcreate_path_from_top_to_bottom(1)
andcreate_path_from_top_to_bottom(2)
, and then when we draw each node we'll use these numbers to tell which step of the algorithm each node belongs to; this is done simply for educational/visual purposes. In reality we'd just setnode.selected = true
instead of a number and the logic would work the same.After we pick a random node we walk down from it until we can't anymore.
get_random_neighbor_down
will go through theneighbors
attribute of a node and return a random one that has a highery
attribute. If there are no neighbors nodes with a highery
attribute then it simply returnsnil
, and based on how we set this while loop up it means it will stop picking more nodes.The same exact logic applies to the horizontal steps, just instead of picking a random top node we pick a random selected node, and we also need some additional logic to decide if we should walk left or right.
Final step
In the final step we'll take the nodes in our graph data structure and create the objects that will make our overmap in the game. The end result looks like this:
I'm not going to focus much on this step since it's the one that's most specific to whatever game, but the most important thing is the mapping from the physics world positions to the positions in the actual game. The way we initially created the boundary was like this:
And so what this means is that the rectangle that defines the boundaries of our nodes have width
80
and height162
, centered atgame_width, game_height
. These numbers were not chosen randomly, because I want the overmap to have a width of400
and a height of810
, as the size of one screen is 480x270 and this means that in terms of width the overmap will cover almost the whole screen (leaving some left over for potentially extra information on one of the sides) and in terms of height it will cover exactly 3 screens. All this means that when translating the positions of our graph nodes to actual world objects we just need to take these measurements into account, and that would look like this:Here the
remap
function changes the first value from its previous range to a new one. So, for instance,remap(5, 0, 10, 5, 0)
returns2.5
. In this simple way we can change the position of our nodes to the position they should be in the world. And finally, now that we have all our nodes in their proper places we can create our game objects from the graph data structure. I won't go over this since it's specific to each game, but you should be able to continue from here by yourself. Good luck!The source code for all this is available here. You can run it by using LÖVE and it's written in Lua. I tried to write it in the simplest way possible and without using anything too specific to Lua, so it should be easy to follow if you use other languages. To stop at each stage of the tutorial, simply remove the call to the next stage from the previous one, for example, remove the call to
pathing_step
if you want to stop at the end ofphysics_step
to see what the circles look like after they're simulated.The text was updated successfully, but these errors were encountered: