I rewrote my dungeon generator!

Поділитися
Вставка
  • Опубліковано 23 гру 2024
  • ⁍ Play: mythfall.com
    ⁍ Discord: / discord
    ⁍ Patreon: / unitoftime
    ⁍ Github: github.com/spo...
    ⁍ Twitter: / unitoftime
    // References
    ⁍ Boris the Brave: www.boristhebr...
    ⁍ Planarity: www.jasondavie...
    ⁍ Force Directed Graph Drawing: en.wikipedia.o...
    // Description
    This week I worked rewrote my dungeon generation algorithm to support multiple room sizes and a more natural layout.

КОМЕНТАРІ • 154

  • @kevwano
    @kevwano 8 місяців тому +712

    the graph generating would make a sick loading screen

    • @vandanramakrishnan5782
      @vandanramakrishnan5782 7 місяців тому +8

      imagine venom's tendrils doing this durng loading screens

    • @user-v4v5c
      @user-v4v5c 7 місяців тому +3

      They still have those?

    • @CentreMetre
      @CentreMetre 7 місяців тому +6

      True, tho 'loading screen takes as much if not more CPU than actually loading the game' sounds funny

    • @koibubbles3302
      @koibubbles3302 7 місяців тому +2

      @@CentreMetreyou can record it and just use the recording in the loading screen

    • @CentreMetre
      @CentreMetre 7 місяців тому +2

      @@koibubbles3302 you could, but then you'd only have a set amount, and it'd take more storage space. I guess you could pre make some and record the movements and then play the movements back, so it'd take less space, but again limited amount.

  • @Kio_Kurashi
    @Kio_Kurashi 8 місяців тому +237

    I like the fact that they're no longer in a grid. This is the thing that's been bothering me with every other dungeon generation I've tried. It just never felt right.

  • @ZM-dm3jg
    @ZM-dm3jg Рік тому +208

    This is the same algorithm that the knowledge-base note-taking application I use (Obsidian) uses for graph view of how all your notes relate to each other.

    • @UnitOfTimeYT
      @UnitOfTimeYT  Рік тому +28

      Ah yeah obsidian is great. I use it to store all my game ideas. A lot of graph-viewer type applications use that force based approach, I think for those it ends up usually looking pretty nice.

    • @jdarokhajiit9153
      @jdarokhajiit9153 Рік тому +2

      I love obsidian notes! I use it for almost everything and even look for things to use it for. Kudos

    • @jerseyse410
      @jerseyse410 8 місяців тому +5

      @@UnitOfTimeYT I also just came across Obsidian and it's interesting how I'm finding more and more uses for Data Structures and Algorithms in GameDev than I ever have as a SWE/DE

    • @clwnwrld
      @clwnwrld 8 місяців тому

      Thanks for the heads up on this! I recently was looking for EXACTLY that but I couldn't find it so I settled on OneNote

    • @warlockpaladin2261
      @warlockpaladin2261 7 місяців тому +1

      Is Obsidian free and open source?

  • @mycroft16
    @mycroft16 7 місяців тому +54

    Just enough un-grid looking that the dungeons doesn't feel like city blocks and cubes. Feels more organic. Especially with the varying room sizes. Slick solution to just collapse everything inward without allowing them to violate the basic constraints.

  • @HelloThere-xs8ss
    @HelloThere-xs8ss Рік тому +49

    I like how you can see the algorithm signature in its final form.

    • @UnitOfTimeYT
      @UnitOfTimeYT  Рік тому +10

      Yeah I like how the visualizations turned out for this one too :)

  • @kevnar
    @kevnar 7 місяців тому +18

    Alternatively, you could create random rectangles with various dimensions, placed all over the map, and then do the crunching together process with collision detection. Then connect them all with a minimum-spanning tree. This would work in 3D, too, for a multi-leveled dungeon.

  • @UnitOfTimeYT
    @UnitOfTimeYT  Рік тому +25

    Huge thank you to all of the supporters that made this video possible:
    Kenta Dracula Andrew Brudnak gugaskhan Dave
    Jomy10 SamieZaurus Jonas Uliana Mqix CD

    • @mattshu
      @mattshu Рік тому

      ok didn't know i needed monospace comments and now i need more

    • @UnitOfTimeYT
      @UnitOfTimeYT  Рік тому

      haha in retrospect I should have thought of that as I separated everyone's names. I don't even have a monospace font. What was I even thinking lol.

    • @prophetzarquon
      @prophetzarquon 6 місяців тому

      I feel like the only reason all fonts aren't monospaced is because we're drawing our glyphs wrong.

  • @BlackMatt2k
    @BlackMatt2k 7 місяців тому +2

    0:29 "because grid, rooms must be the same size" If the minimap only needed to be accurate from the perspective of your current room, and you didn't care whether people can count paces to map the whole thing out, the actual room size could be arbitrary. You could just graft and cull the exit rooms as you cross the threshold, and have doorway colliders that transform raycasts through the "portal". In a fast-paced game, I doubt anyone would notice the floor plan doesn't add up, and it might even add to the pressure/confusion.

  • @timmygilbert4102
    @timmygilbert4102 10 місяців тому +9

    Or start with a fully connected temokate graph (ie a grid) then random walk free node only (visited nodes goes to close list, neighbors of last visited goes to open list, randomly chose within the open list at each step) after it's done randomly drop (or use designed heuristic) links between nodes not in the generation path, up to a set number, to get some cycles, bonus round, generate long distance link between nodes that aren't neighbors.

    • @MensoJero
      @MensoJero 2 місяці тому

      what if you just tag each room as it's generated and then pick a room that spawned at least a set distance away from the spawn room and spawn the boss room there?

  • @littleowlgaming-unity-tutorial
    @littleowlgaming-unity-tutorial 7 місяців тому +1

    for the first issue, i like the multiple lines solution. you have a dungeon generate rooms connected. going in a random direction. for a iteration account. storing each room, then once iteration is done, start either back at the spawn, or in a random room along the first iteration, and iterate again, making a "second path" place something at the end room, boss, treasure, dungeon key, etc. then redo that algorithm from the start, and making something else at the end of another path, this makes sure the boss room, isn't connected right next to spawn, that there is always a path to the boss, and to treasures and such.

  • @jomy10-games
    @jomy10-games Рік тому +23

    I need a 10 hour version of the intro

  • @tylerbakeman
    @tylerbakeman 6 місяців тому

    1:30,
    For both 2D-Arrays and Connected-Graphs, you are able to control all of those things:
    1) How far from the start should the boss room be? That could be a random value between some min and max, call that value D for depth. When creating the dungeon, only a node with the value D can be the boss room - this can be done during the dynamic procedural construction of the dungeon, or you can assign the ideal bossroom after the dungeon layout is generated - both are fine.
    2) Room sizes can be different for both. With Generalized graphs, it is easier to have accidental overlap - you can control this during the generating steps: create some kind of BitMap or Rasterization that keeps track of which pixels contain a room - if a new room would overlap those pixels, don’t create it altogether. If the rooms have a predictable geometry (ie. The rooms are rectangles or polygons, then you can check for overlapping easier).
    An alternative approach to this problem is to use some kind of generating function that builds off of randomness:
    - Wave Function Collapse (this is probably what you should be using)
    - Noise generating dungeons (perlin noise is better for heightmap generation) Whorley noise creates cell-like areas, that you can use for things like cave generation - there are probably better noise algorithms for caves, but this one is pretty good. Ie, Voronoi diagrams are pretty interesting.
    - Maze generation can be turned into dungeon generation, to my understanding- but I don’t know the name of the algorithm.
    If you have irregular shapes, if you use some kind of noise, then you’re likely going to have some added difficulty navigating through the dungeon. Add some extra checks for the players size (ie, having a player width and height that collide with walls),
    use the “A* pathfinding algorithm” to make sure it is possible to get from the Start to the End of the dungeon.

  • @david3710
    @david3710 Рік тому +5

    Very cool and elegant! Nice job, man, and wish you good luck on your game-dev journey.

  • @atursams5501
    @atursams5501 7 місяців тому +42

    I solved this problem in the past with Voronoi diagrams (they don't have to use manhattan or l2 distance). Merging nearby cells randomly, allowing for any room size/shape and eliminating any potential for crossing edges.
    It seems like a very roundabout way to do something, friend.

    • @nicksrub
      @nicksrub 7 місяців тому +2

      Could you make a video on it or link to examples or source?

    • @doomsday7699
      @doomsday7699 6 місяців тому +1

      Does that mean that there is a minimum size and the other sizes of the merged room is in a multiple of that minimum size? Or random sizes to begin with but with a maximum size constraint, and during merging that constraint is removed?

  • @ramsey2155
    @ramsey2155 8 місяців тому +6

    You should have assigned the room properties when generating, with this approach you can even have more advanced properties like constraining the the boss room to be 3 rooms away from the spawn instead of doing it based on distance

  • @aiacfrosti1772
    @aiacfrosti1772 7 місяців тому +18

    I liked the part where he said "it's dungeoning time" and then dungeoned all over the place

  • @TheMasonX23
    @TheMasonX23 7 місяців тому +1

    Ooh, I love how you solved the crossing constraint by mixing both algorithms! The second one was neat, but required too much tuning and still couldn't enforce the constraints. Graphs are definitely the way to go, but I like the simplicity of using a random walk combined with some collision based constraints.

  • @kiveynen
    @kiveynen 8 місяців тому +1

    I tackled that problem last during my first years of programming. Very interesting - never came across a physics based approach in a post processing.

  • @KagrithKriege
    @KagrithKriege 7 місяців тому +6

    Id peep at the comment below this one, as i had an epiphany while writing it.
    If you havent yet, you could have a look at A* and Dykstra's algorithms. Then compare against binary tree algorithms. You can then use your gap to prune shortest paths from spawn to boss, until minimum separation is achieved.
    Graph theory studying could also be helpful.
    Quantum wave function collapse might be most helpful to you.
    Worth having a look at. (Start with this actually)

    • @KagrithKriege
      @KagrithKriege 7 місяців тому +2

      ua-cam.com/video/20KHNA9jTsE/v-deo.htmlsi=nk6JITQyLTgTM1IA
      This video has been the best explainer ive seen on using the algorithms in games.
      For your purposes, a biome is a room type, and the ability to designate what kind of rooms can share adhacency should be very helpful.
      Will also let you retain grid power, and you can even designate dead-end and hallway rooms. You can also dictate the connection count of rooms, their min or max radius from spawn, or any other room.
      For instance, maybe item rooms are like "islands" and must have four "water" type tiles between them.
      Much can be done! Could make for maximal replayability with different and new tilesets. Excited to see what you come up with!

  • @fokeyjo
    @fokeyjo 23 дні тому

    Excellent approach and use of algorithms!

  • @ozancanacar8237
    @ozancanacar8237 9 місяців тому +2

    Very Nice! Thanks for sharing your process ❤

    • @UnitOfTimeYT
      @UnitOfTimeYT  9 місяців тому +1

      Thanks! Glad you liked it!

  • @Eaglefield_
    @Eaglefield_ 7 місяців тому +3

    Would love the generation to be available on a website for generating dungeons for TTRPG nerds like myself. Love the generator!

  • @denouement231
    @denouement231 11 місяців тому +4

    I've been thinking about this approach forever. I want to see more of what you've done since this video. I also wanted to work on a 3d force graph dungeon.

    • @UnitOfTimeYT
      @UnitOfTimeYT  11 місяців тому +1

      For dungeon generation, I haven't changed much about my approach, other than experimenting with splicing "bonus" rooms into my dungeon DAG (Treasure rooms, miniboss rooms, etc). But for my overall game I've made a lot of new changes, I'm working on a new video about that as we speak!

  • @titastotas1416
    @titastotas1416 7 місяців тому +2

    Great video, I have a few ideas that may be useful when improving the force based graph drawing algorithm. If you added the repelling force to the edges too it would greatly improve the algorithms ability to produce graphs with no crossings. had you frozen the positions of some nodes and edges as soon as they met some condition it would help prevent forces from tangling them up, as an example: a node acquires 4 neighbours and the edges towards the neighbours have no crossings, in such case a node is considered to have a good placing and is frozen in place with its neighbours.

    • @UnitOfTimeYT
      @UnitOfTimeYT  7 місяців тому

      Thanks for the suggestions. I think they are good ideas! Ill have to try them out!

  • @renobrecords
    @renobrecords Рік тому +4

    This is really cool. I'm just getting into game dev and want to learn how to build proc gen dungeons. Subbed!

  • @Solanaar
    @Solanaar 7 місяців тому +1

    I have zero idea of this, but I have a degree in watching informative youtube videos and I kept thinking about wave function collapse and how it could help with defining room types. Is this, like, an option?

    • @UnitOfTimeYT
      @UnitOfTimeYT  7 місяців тому

      Yeah. I'm not super familiar with WFC, but it might be helpful if my dungeon needed to bridge multiple rooms together. right now the dungeons are designed to have several rooms connected via hallways, so the hallways are kindof the joining point. Maybe I'll use WFC for future dungeons though.

  • @lauram5905
    @lauram5905 7 місяців тому +1

    I've always wondered how someone could recreate a dungeon system like this, very smart! I wonder if it could be extended to place rooms in 3D space, or non rectangular rooms... Thanks for sharing!

    • @UnitOfTimeYT
      @UnitOfTimeYT  7 місяців тому

      Yeah. For 3D it might be a little tricky to route hallways because you need things like stairs. But for 2D I actually use prefabricated rooms (that can be any shape or size, and have custom objects), then I just use the rectangle as a bounding box to make sure the rooms don't overlap.

    • @lauram5905
      @lauram5905 7 місяців тому +1

      @@UnitOfTimeYT I got suggested a video by Vazgriz right after watching this that goes into a similar method in 3D, using the 3D A* algorithm to map out grid-aligned hallways and stairwells

  • @pik910
    @pik910 11 місяців тому +2

    Very well done and communicated , concise and useful, ty!

  • @paulgalvinauthor
    @paulgalvinauthor 7 місяців тому

    Fantastic explanation and the visuals were terrific!

  • @BlackJar72
    @BlackJar72 6 місяців тому

    Its definitely different from the how I laid out the rooms for Doomlike Dungeons and Caverns of Evil, though both use a kind of random walk -- I placed node rooms, all destined to become important, at random locations, usually far apart, and used a random walk to have them grow towards each other by placing a series of rooms in meander paths from each start until the two paths met.

  • @sebaitor
    @sebaitor 7 місяців тому

    The very first approach you showed was sufficient. All you need to do to ensure enough distance from spawn to boss room is to perform any pathfinding algorithm that returns the distance between nodes and if that distance is less than your defined accepted threshold, move the boss room and repeat this process until satisfaction of the condition.

  • @litlclutch
    @litlclutch 7 місяців тому +1

    the larger dungeons make me think of Daggerfall... those dungeons could be MASSIVE and often were. is there a way to have rooms that colide during the shift merger into a single larger room? could be neat but could also be pointless as the are just representations of where they are right? They could still be whatever shape that you want/need?

    • @UnitOfTimeYT
      @UnitOfTimeYT  7 місяців тому

      Ah yeah that's an interesting idea. I can definitely merge rooms. but rooms (at least how I have them now) are kinda "prefabricated". Like they might have boxes in a corner, things like that. So if i'd have to ensure the entities inside the room dont end up causing a weird situation.

  • @bryak4548
    @bryak4548 7 місяців тому +1

    I bsicaly made first version of tile generator you showed. In mine when rooms collide the just connect with each other and it done with a simple line trace chech. I think the graph searching algorithms can be used for solving the problems with speciall rooms placement i implemented basic BFS algorithm in my scince i use linked list. Video is cool

  • @thedude4063
    @thedude4063 5 місяців тому

    I am still trying to find a tutorial or dungeon generation script similar to Gungeon but supporting 3D rooms because I love its premade rooms with grid-like hallways. I continue the search!

  • @rionhunter
    @rionhunter 7 місяців тому

    This is incredible. I feel it would be really easy for you to add dynamically sized rooms as well. For spawn>boss routes, for rpgs with open worlds, it is not that you want them far apart, but just the approach to the boss room being long. Exiting the boss room to somewhere near spawn via a one way avenue (door/height, etc) is often a nicer experience. If you made one vein that somehow looped around or a secret passage hallway, maybe with the rewards? :o
    Obviously depends on what overall game/playloop is

    • @UnitOfTimeYT
      @UnitOfTimeYT  7 місяців тому

      Yeah there's a lot of cool dag preprocessing stuff that I think I can do!

  • @omg33ky
    @omg33ky Рік тому +3

    That's a very clever idea!

  • @PandaJerk007
    @PandaJerk007 7 місяців тому

    Very cool to see your process :)

  • @Voronza
    @Voronza 7 місяців тому

    Interesting! How about Voronoi diagram algorythm with some edges removal?
    I wrote something similar recently. But instead of gravitating towards the start room - I generated all rooms one by one and slided them to the top left corner. Which is simplier, but the result is not that natural.

    • @UnitOfTimeYT
      @UnitOfTimeYT  7 місяців тому +1

      Cool! Yeah I didn't start with Voronoi diagrams because originally I wanted to generate a dungeon based on the abstract DAG representation of a dungeon.
      Gravitating towards a corner sounds interesting, I hadn't even thought about doing something like that.

  • @Dimencia
    @Dimencia 7 місяців тому

    The only time I did something like this, I also ended up with a physics based approach relying on gravity to pack rooms together, then just sorta cut holes in the rooms where they connected to make 'hallways'. Funny that the physics stuff is kinda the best solution, and as a bonus it really does make a cool loading screen

    • @UnitOfTimeYT
      @UnitOfTimeYT  7 місяців тому

      Oh that's interesting. Haha yeah the loading screen made it worth it for sure lol

  • @ifcoltransg2
    @ifcoltransg2 Рік тому +2

    You could also randomly generate some points in space and do a Delaunay triangulation on them, which gives you a planar embedding for free. I'm pretty sure Unexplored uses this kind of approach for its level generation.
    Edit: They don't, but I think they used to.

    • @UnitOfTimeYT
      @UnitOfTimeYT  Рік тому

      Cool. Thanks for the suggestion!

    • @Eruntano314
      @Eruntano314 7 місяців тому

      I use a hand base estimate to make cities... It seems to work pretty well

  • @rohan751
    @rohan751 11 місяців тому +1

    Intresting approach

  • @jansustar4565
    @jansustar4565 Рік тому +3

    Dungeon generation is hard. The end result looks really good. I dabbled with it myself a bit, but with no good results. Due to a deadline, i just ended up using a maze generator and a few extra steps. Anyway, great video and presentation.
    Could you elaborate on the post processing you did? Did you use Maximum Shortest Distance to place spawn and boss rooms? And maybe add a constraint what is considered good enough?

    • @UnitOfTimeYT
      @UnitOfTimeYT  Рік тому

      Thanks! Yeah, I'm slowly learning how difficult procedural generation is in general lol. When I generate the planar graph version of the dungeon, I simultaneously generate a DAG which holds every room and all of the connections between rooms. So for postprocessing I just need to decide "which room goes at which node in the DAG". My game is pretty simple so far, (I only have "spawn rooms", "normal rooms", and "boss rooms"), So for now I just take a topological sort of the DAG and choose the first node as the "spawn room", and choose the last node as the "boss room". I think in future, I might do some extra steps to regulate a few things: room difficulties, monsters selected per room (to prevent neighbored duplicates), potentially adding special encounter style rooms in interesting locations, stuff like that.

  • @syzore2
    @syzore2 7 місяців тому

    What's the problem with edge crossing? I mean, what could be a hallway and the other is a small tunnel under it.. right?

    • @UnitOfTimeYT
      @UnitOfTimeYT  7 місяців тому +1

      I didn't really explain in the video but my game is 2d. So when the hallways overlap they end up making the dungeon more connected then I wanted

  • @Shammikaze
    @Shammikaze 6 місяців тому

    Any chance of an educational video or tutorial demonstrating how to create the logic for such a thing? Not necessarily looking for exact steps in any given game engine, but a precise overview of the math and logical steps used would be incredible.

    • @UnitOfTimeYT
      @UnitOfTimeYT  6 місяців тому +1

      Sry I don't have time rn to make a tutorial. But somewhere in the comments I replied to someone with a link to the code on my GitHub. Your welcome to look at the code!

  • @darkenblade986
    @darkenblade986 7 місяців тому

    checkout wave function collapse.
    u give constraints to the different types of rooms and then it procedurally generates a map.

  • @demian_csomic_winters9484
    @demian_csomic_winters9484 6 місяців тому

    I wonder what happens if you were to build a city with this type of system this way you can have very large metropolises without doing every building, roads and various infrastructure. What would it build and would it give its own design philosophy following set rules of algorithm generation

    • @demian_csomic_winters9484
      @demian_csomic_winters9484 6 місяців тому

      Been thinking since last night about how to start learning blender as I want to learn character design that can be used by NPCs and players alike yet I need to start somewhere. Then I remembered this video I commented on, starting by building the world they will be in my own style and thoughts how the city will be built. Even the idea of building backrooms like location under the map where I can store assets with foes Incase anyone manages to glitch under allowed areas of the maps such as my version of soul reapers or something to hunt them down.
      Potentially start learning how to do little programming for semi procedurally generated maps where map is made of blocks each block has predetermined path to generate fully or partially what on each block and how to full or partially degenerate stuff in each block.
      Thank you for your help.

  • @titansoundsmusic
    @titansoundsmusic 4 місяці тому

    Any links to a guide for graph based 3d procedural generation?

    • @UnitOfTimeYT
      @UnitOfTimeYT  4 місяці тому

      Sorry nothing for 3d procgen. My game is 2d unfortunately :/

  • @bethrains3105
    @bethrains3105 6 місяців тому

    Could watch the graph redraw for hours.

  • @nickgennady
    @nickgennady Рік тому +2

    You could use graph grammars to make the graph procedural

    • @UnitOfTimeYT
      @UnitOfTimeYT  Рік тому

      Oh cool I actually hadn't heard of graph grammers before. Thanks for sharing!

  • @FlippinFunFlips
    @FlippinFunFlips 8 місяців тому +1

    That's pretty neato!

  • @n.roussis
    @n.roussis Рік тому +1

    i zoned out after a bit and was not hearing what you were saying but liked the video anyways because you use kde

  • @runekutchinsky8745
    @runekutchinsky8745 6 місяців тому

    Classic physics issue: you meed to check for the boundary consitions (your design constraints) all the time

  • @lordfresh
    @lordfresh 10 місяців тому +1

    How do you visualize this? Im starting to learn game dev now

    • @UnitOfTimeYT
      @UnitOfTimeYT  10 місяців тому

      I made these visualizations with a rendering library that I wrote on top of opengl. If you're just starting gamedev, I'd highly recommend an engine (unity, godot, unreal, etc). Best of luck!

    • @lordfresh
      @lordfresh 10 місяців тому

      ​@@UnitOfTimeYTCool. Im gonna start using Unity. Started yesterday actually. I see a lot of these visualisations in tutorials though without completely understanding. Is this part of the game project? Like a renderer in the map generator for example? Do you run it by running the game or can you run a separate renderer to just render stuff like that you are curious about?

    • @UnitOfTimeYT
      @UnitOfTimeYT  10 місяців тому

      Yeah for this particular case I just render rectangles in a special project and its separate from my main game project. Though it is possible to set things up so that you can show debug rectangles and things like that@@lordfresh

  • @arc7498
    @arc7498 7 місяців тому

    Hello, could you tell me how you created your video animations?

    • @UnitOfTimeYT
      @UnitOfTimeYT  7 місяців тому +1

      Hey for these ones I just rendered them using opengl and recorded them. But there's some nice anim libraries out there like: manim and motioncanvas which I've heard are pretty good too.

    • @arc7498
      @arc7498 7 місяців тому

      @@UnitOfTimeYT Thank you :)

  • @alphaberzrkr
    @alphaberzrkr 7 місяців тому +1

    how did this journey start im interested in stuff like this are you self taught or school...curious good job though this is very cool

    • @UnitOfTimeYT
      @UnitOfTimeYT  7 місяців тому +1

      Thanks! I went to school for Electrical Engineering, but transitioned after college to software engineering. If you want to learn. I'd recommend taking some *free* intro programming courses (like how to code basic things). then as you get more advanced you can take more advanced college-level courses that "MIT open courseware" offers. They have a YT channel where you can basically go and learn data structures and algorithms and all about how computers function under the hood. Best of luck!

  • @larkohiya
    @larkohiya 7 місяців тому +7

    But what are you going ro "DO" with the rooms and layout. Why so you need these layouts at all? Why these many rooms? Why these sizes? Why square?

    • @canjiica
      @canjiica 2 місяці тому

      How do you expect someone to answer all these questions without experimenting things first? Looks like you are expecting that he builds a game in a cascade approach. You could spend days thinking about these questions, coming up with answers and finding they were all wrong. Experimenting first lead to a more engaging and productive process, not only because you find answers but because you find the questions that you didn't know you needed to ask

  • @antha-earth
    @antha-earth 7 місяців тому

    Nice! I feel inspired

  • @adiaphoros6842
    @adiaphoros6842 7 місяців тому

    Why not have the edge crossings mean the corridors are in different "elevations."

    • @UnitOfTimeYT
      @UnitOfTimeYT  7 місяців тому

      Yeah you could do that if you wanted. I am making a 2d game and didn't want elevation levels

  • @anzhel3268
    @anzhel3268 5 місяців тому

    cool visuals

  • @deadlyembrace8326
    @deadlyembrace8326 6 місяців тому

    Very cool!

  • @moxvallix
    @moxvallix Рік тому +1

    Hang on, I recognise that cursor. KDE Plasma?

  • @pepdawg18
    @pepdawg18 7 місяців тому

    Is the code for this posted anywhere??

    • @UnitOfTimeYT
      @UnitOfTimeYT  7 місяців тому +1

      Yeah some of the dungeon generation code can be found here: github.com/unitoftime/flow/blob/master/pgen/dungeon.go
      And the original example which generated and rendered the dungeon is here: github.com/unitoftime/flow/blob/master/pgen/example/main.go

  • @Alienboi2005vidsandstuff
    @Alienboi2005vidsandstuff Рік тому +1

    What engine do you use?

    • @UnitOfTimeYT
      @UnitOfTimeYT  Рік тому

      Hey! I don't use an engine. My game is basically from scratch on top of opengl and webgl

  • @ShahabSheikhzadeh
    @ShahabSheikhzadeh 6 місяців тому

    This presentation makes me feel dumb, but this also makes me wonder how large world/map design works, like Helldivers 2 and their levels.

    • @UnitOfTimeYT
      @UnitOfTimeYT  6 місяців тому

      Haha. yeah it was a struggle figuring all this out, and I'm not really sure my solution is all that great. but it does work for my game at least. But yeah I'm not really sure how large 3d games do level gen. Mine is a 2d game which is probably much simpler.

  • @argigra3909
    @argigra3909 10 місяців тому

    where can we find this algorithm?

    • @UnitOfTimeYT
      @UnitOfTimeYT  10 місяців тому +1

      Ah I probably put links in the description to various sources that I used during my research. I don't think its like an official algorithm though. Hope that helps!

  • @captaincael1308
    @captaincael1308 2 місяці тому

    remind me alot of how the map looks like in eve online

  • @EMB3D
    @EMB3D Рік тому

    where rendered dungeon?

    • @UnitOfTimeYT
      @UnitOfTimeYT  Рік тому

      I guess I never showed a picture of it You can go here to play and run to one of the dungeon portals (NorthWest or South) if you want to see what the dungeons look like : mythfall.com
      Or if you check out this video it has some gameplay as well: ua-cam.com/video/rp0KWg2Z9G8/v-deo.html

  • @BboyKeny
    @BboyKeny Рік тому

    So each node has a room type which contains the dimensions of the room which is then used for collision detection for the rooms?
    Looks very awesome!

    • @UnitOfTimeYT
      @UnitOfTimeYT  Рік тому +2

      Thanks! Yeah, exactly. I maintain a pool of different rooms based on the "RoomType". Right now I just have 3 rooms: Spawn Rooms, Normal Rooms, and Boss Rooms. Then right before I do the initial grid layout of all of my room rectangles, I first need to decide which room will go into which grid location. So I randomly select a room out of the room pool, based on which RoomType is is at that grid location. Once I've selected the room, I will know the bounding rectangle of that room, so for the "gravity compression" stage, I just do collision detection based on that room rectangle. Hope that makes sense!

    • @BboyKeny
      @BboyKeny Рік тому

      @@UnitOfTimeYT incredibly clear explanation, thank you very much 😄

  • @igrb
    @igrb 7 місяців тому

    big W

  • @NightmareCourtPictures
    @NightmareCourtPictures 7 місяців тому

    hypergraphs son

  • @nichan008
    @nichan008 6 місяців тому

    Bro took a feature and thought it was a bug. 🤦‍♂️
    But more seriously, rather than a flat wide random assortment of squares, I'd rather see people generate layouts that include verticality and usage factors.
    Maybe where edges cross could have been an indicator for verticality or a 4 way hallway.
    Give rooms usages beyond boss, normal, and treasure. Where's the bathroom? The kitchen? They're going to need to get water either from the entrance or maybe an internal source. Where do they store the wine? Give each of these things weight for how close they should be together.
    But otherwise, cool. I acknowledge that you put in a lot of effort to stick random squares next to each other. 👍

  • @Toksyuryel
    @Toksyuryel 10 місяців тому

    You might appreciate looking at how Path of Exile solved this problem too

  • @lucbloom
    @lucbloom 7 місяців тому

    Fake solutions to simulate systems are more fun solutions. Applies to a lot of things; kart handling physics, physical health, and yes, also 2D topology.

  • @pichers5528
    @pichers5528 7 місяців тому

    Couldn't you just add stairs when there were overlaps of rooms? Over simplifying here, but it's a genuine question

    • @UnitOfTimeYT
      @UnitOfTimeYT  7 місяців тому +1

      Yeah you could definitely do multileveled dungeons. In my case, I'm making a 2D game. and I wanted the connectivity of the dungeon to match the initial DAG that I used so that I could do some preprocessing steps more easily. But yeah, there's lots of ways to go about procedural dungeon generation, depending on the type of game and feel you are going for. Thanks for watching!

  • @lethiagames9208
    @lethiagames9208 7 місяців тому

    "gungeon generator"

  • @42beebop
    @42beebop 7 місяців тому

    Phew, is there some kind of competition who can narrate the most words within 5 minutes? That's exhausting to listen to.

  • @randomancy
    @randomancy Місяць тому

    Ugh, I want this in Unreal Engine haha I also dislike the grid systems out there

  • @brice.rhodes
    @brice.rhodes 7 місяців тому

    Looks like you found a solution, I just wanted to point out that I think wave function collapse sounds like very good solution for what you were looking for. Its very customizable beyond its basic rules. A pretty popular game that uses this algorithm is Bad North (ua-cam.com/video/0bcZb-SsnrA/v-deo.html)

  • @86Corvus
    @86Corvus 20 днів тому

    Thats a tunnel generator, not a dungeon generator...

  • @jamesalewis
    @jamesalewis 7 місяців тому

    Just wait until you realize you really want it to be 3D 😬

    • @UnitOfTimeYT
      @UnitOfTimeYT  7 місяців тому +1

      Haha. hopefully I'll never have to go down that road :P

    • @jamesalewis
      @jamesalewis 7 місяців тому

      @@UnitOfTimeYT Literally the next video in my feed: ua-cam.com/video/rBY2Dzej03A/v-deo.html ("Procedurally Generated 3D Dungeons" by Vazgriz)

    • @jamesalewis
      @jamesalewis 7 місяців тому

      @@UnitOfTimeYT It would be a trick, but crosses in the graph would actually become easier to handle, since you can simply make them different levels within the dungeon, and the hallways with elevation changes would become stairwells. You'd need some checks to be sure elevation changes don't happen too quickly, but it still may make some things actually easier.

  • @PoPuppy-i1l
    @PoPuppy-i1l Рік тому +1

    Why would you do this it seems like a lot of work when there are better less expensive solutions

    • @UnitOfTimeYT
      @UnitOfTimeYT  Рік тому +4

      I'm always open to learn about other dungeon generation algorithms, this was the best I could come up with for my requirements in the couple of days I spent working on it

  • @Discipol
    @Discipol 7 місяців тому +2

    the end results in this video are kinda underwhelming

  • @Yoloman147
    @Yoloman147 7 місяців тому

    Have a like for putting the music source into the description.

    • @UnitOfTimeYT
      @UnitOfTimeYT  7 місяців тому +1

      Haha thanks. I'm pretty sure YT automatically adds it even if I don't. Lol