1/13/2024 0 Comments Random dungeon generation tinykeepHaving to check the entire previous path on each step is expensive. There are too many special cases just to handle staircases. The algorithm isn’t exactly A* at this point. Later iterations will just work around existing staircases like before. There are still multiple pathfinding calls to generate all the hallways. The above behavior is only for multiple potential paths within one call to the pathfinding function. The pathfinder could create another path that passes through the staircase, since the second path wouldn’t know about the staircase. The hallway at the end of the staircase would contain all of the cells occupied by the staircase, the node at the start of the staircase, and all nodes in the path before that, all the way to the start. Then when a neighbor node is being evaluated, it will be rejected if it falls on the path of the current node. The solution was for each node to keep track of all previous nodes in it’s path. But I can’t leave them out, because then the pathfinder would be able to move through a staircase it just created, creating those unwanted situations pictured above. I can’t add them to the closed set of A*, since that would prevent a different path from going through those cells from a different direction. The hard part is that I need to somehow make the pathfinder work around staircases that it creates. To make staircases, I would need to “jump over” the four cells of the staircase. The A* algorithm is designed to move from one node to an adjacent node every step. This means it must move 3 units horizontally and 1 unit up or down. The pathfinder must move from the starting location to the end location in one step. This new version is in Scripts3D/Delauna圓D.cs, in case anyone else was looking for an MIT licensed, easy to understand version.Ī staircase starting at the solid blue square and moving up one floor Since it’s mostly 4×4 matrix operations I just used Unit圓D’s Matrix4x4 type to do the heavy lifting. I still don’t really understand why circumcircles are so important, but I was at least able to write it using circumspheres instead, using this page from Wolfram MathWorld. In the end, I had to learn how the Bowyer-Watson algorithm actually worked so I could change it myself. The other was that the code was so heavily templated and inscrutable, that I didn’t actually find where they implemented the algorithm. One was that this module was only available under the GPL ?. The closest was CGAL’s implementation of 3D triangulation, but there were two problems with it. Searching for either ” 3D Delaunay triangulation” or ” Delaunay tetrahedralization” returned a lot of research papers but no actual source code that I could find. Next, find the 3D Delaunay triangulation of the rooms, or rather the Delaunay tetrahedralization. Note that rooms can be multiple floors tall.Ģ. I’ve also added a 1 unit wide buffer on each side (to ensure that rooms aren’t touching), but this is not required for the algorithm to work. It doesn’t matter that much how they are arranged, so for this example, I’ve just placed and sized them randomly. Place rooms arbitrarily such that they don’t overlap with each other. In a full game, 1 unit may correspond to 5 meters, for example. I assume that 1 unit is wide enough to represent a hallway. The world is divided into a rectangular grid. The code for this is in the Scripts2D folder. It works mostly the same as the TinyKeep algorithm, but has been simplified in some ways (especially room generation) and is more complex in others. Two Dimensionsįirst, I had to write the algorithm to work in two dimensions. I’m using Unit圓D for this demonstration, but these concepts are, of course, usable in any game engine. The code for this example is available in this Github repo. I extended the algorithm to work in 3D, to create dungeons with multiple floors. There are a lot of different ways to approach this problem, but I eventually decided to base mine off of TinyKeep’s algorithm, described here. I’ve been playing some roguelikes recently, so I wanted to try writing my own procedural dungeon generator.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |