Author Topic: Loops on dungeon-type levels  (Read 18093 times)

reaver

  • Rogueliker
  • ***
  • Posts: 207
  • Karma: +0/-0
    • View Profile
Re: Loops on dungeon-type levels
« Reply #15 on: October 19, 2014, 12:43:59 PM »
Blindly retrying can be a major source for slowdowns for the generator.
Theoretically. In the worst case at least. But that sounds like premature optimization to me.

Not for me at least -- of course depends on what do you use the randomness for. An example scenario, try to place 100 rectangular rooms (disconnected for now):

rooms_placed = 0
target_room_number = 100
while rooms_placed < target_room_number:
   room_corner = generate_random_point()
   ok = place_room( room_corner )
   if ok:
       rooms_placed += 1
       

Above, when you're nearer the target room level, it will be more likely that the random point will be inside or very near an existing room. On the contrary, if you generate a list of random points based on a better distribution, you would have less failures. How much would that affect performance of course is variable and would have to be measured (indeed if it's not a problem, no need for fancy stuff).

If I had to choose between something that is pretty good at making valid dungeons and easy to retry vs something that is mathematically proven to always be valid, I know which I would choose: the good enough way. I've found that a good enough generation algorithm and a rock-solid validation algorithm are far easier for me to program, far more adaptable, and require far fewer tweaks as new monsters, terrain, puzzles, abilities, etc, are added.

Imho that's the mindset if one wants to actually release something :)

Besides; with most algorithms, I'm guessing at least a hundred or a thousand levels or rooms can be generated per second anyway.

It pays to be fast in the long run though. If you make the basic generator logic fast, then you can scale up either in terms of dungeon level (100x bigger) or you can scale up in terms of running many generators for different aspects ( one for level layout, one for monsters, one for torches, one for chests, one for traps and so on and so forth)

Bear

  • Rogueliker
  • ***
  • Posts: 308
  • Karma: +0/-0
    • View Profile
Re: Loops on dungeon-type levels
« Reply #16 on: October 19, 2014, 03:55:51 PM »
Blindly retrying can be a major source for slowdowns for the generator.
Theoretically. In the worst case at least. But that sounds like premature optimization to me.

This actually became a problem with the Angband level generator IIRC -- it was sometimes trying for a long time to generate a valid level.  So it's definitely something to consider. 

If I had to choose between something that is pretty good at making valid dungeons and easy to retry vs something that is mathematically proven to always be valid, I know which I would choose: the good enough way.

I prefer something that is solidly bounded in compute time - ie, won't do generation more than once.  If it's not provable to be mathematically valid, I use a rock-solid validation algorithm to detect the problems, then use "patchups" (such as moving unconnected open spaces together or making additional tunnels to connect anything that's not connected) to alter the output and force it to become valid. 


Slash

  • Creator of Roguetemple
  • Administrator
  • Rogueliker
  • *****
  • Posts: 1201
  • Karma: +4/-1
    • View Profile
    • Slashie.net
    • Email
Re: Loops on dungeon-type levels
« Reply #17 on: October 20, 2014, 01:56:50 PM »
I just recently adapted the rot.js Rogue style generator into SquidLib and it does what you're looking for:

https://github.com/SquidPony/SquidLib/blob/experimental/src/squidpony/squidgrid/mapping/ClassicRogueMapGenerator.java

Looks interesting, thank you!

Slash

  • Creator of Roguetemple
  • Administrator
  • Rogueliker
  • *****
  • Posts: 1201
  • Karma: +4/-1
    • View Profile
    • Slashie.net
    • Email
Re: Loops on dungeon-type levels
« Reply #18 on: October 20, 2014, 01:57:50 PM »
Anyway, I go through all the rooms, select a random wall tile, and use a pathfinder that can't use diagonals to dig a tunnel to a random wall tile of another room. Then I run through the list of rooms again and make a second tunnel in the same way, so each room will have at least two exits.

Actually, to make it more interesting, the first time I do it, the pathfinder isn't allowed to go through any already-open space. It'll curve around other rooms (and tunnels too, I think. Don't remember if it ignores them or not).
The second time, it's allowed to go wherever it wants, including through other rooms, so some rooms might have multiple exits, and tunnels will intersect other tunnels.
Aha! this looks pretty good! I think I'll give it a shot :)