Thread: Diablo's random level generation

  1. #1
    Registered User
    Join Date
    May 2006
    Posts
    169

    Diablo's random level generation

    I liked the way Blizzard let you play it a bit differently every time by providing randomly generated maps. But I wonder how does it work?

    In Diablo 2 online, it would have been insane to send all the randomly generated level data to the many players playing it. I'd imagine the server will only send a random number - sort of like a seed for the level generation algorithms, and basically let the players generate the level accordingly themselves.

    Will love to hear any experience you've had playing with random level generation and your takes on the subject.

  2. #2
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Ireland
    Posts
    8,446
    That pretty much how Diablo does it. On single-Player the seed is generated every time you start a new game, when changing difficulty levels, and when moving to a new Act.

    You can find much data on random generated dungeons if you google for it. Some of the more interesting readings are the algorithms used for rogue-like games (nethack, adom, etc...) which provide all you need to learn the techniques and open your imagination to your own devised algorithms.

    Speaking of Diablo, it borrows many concepts from MUD games like fetching your body and random treasure generation. This last one is also an excellent one-time feature I would love for some games to imitate since it's definitely one of the reasons Diablo II is still so much played today even in SP mode. There's also somewhere a few good articles on how to develop and appraise the quality of your treasure generation algorithms, including treasure-class and chest-like algorithms and others.

    In the end you can also pack that with monster generation algorithms, name generation algorithms and something-generation algorithms - all also available searchable on google - and build your own graphical or text based rogue.
    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  3. #3
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    There are known algorithms you can find on the web that will allow you to effectively place treasures, monsters, doors, and the keys to the doors in the right places so as to make the entire journey balanced. The keys to the door must not be behind the door and the strength of the creatures guarding the treasure ought to be in line with how much the treasure is worth. High price treasures equals more difficult creatures, etc. etc.

    I have a friend who has this system in his game and it works well. I'll ask him where he found these algos.

  4. #4
    Registered User
    Join Date
    May 2006
    Posts
    169
    Thank you, I felt an urge to try something out.
    http://img56.imageshack.us/img56/8860/mazefe9.png
    This maze generator I made takes a 2d map and generates it differently every time it is run.
    The hole inside illustrates how you can insert maps of different shapes and have the generator generate a maze accordingly.
    When I come to think of this, Diablo's dungeons were also as simple as 2d arrays of rooms, with up to 4 exists, they just added cherries on top.

  5. #5
    Registered User guesst's Avatar
    Join Date
    Feb 2008
    Location
    Lehi, UT
    Posts
    179
    You wanna look up roguelike programming.

    The thing about roguelikes (of which diabalo is possibly the most successful one) is that their mazes can be somewhat open, unlike your maze generation where you try to fill the space.

    I played one, I think it was called "Castle of the Wind" for windows 3.1, that even had hidden doors you had to search for. On earlier levels you could get by without searching, it checked to make sure you could find the exit, but by the last level you pretty much had to search or you'd never find the hidden sections where the exit was.

    The point is the topic has been pretty explored and can be robust, you just need to get yourself a resource. (This looks promising.)
    Type-ins are back! Visit Cymon's Games at http://www.cymonsgames.com for a new game every week!

  6. #6
    Registered User
    Join Date
    May 2006
    Posts
    169
    Thanks, I'm actually a regular visitor at Rogue Basin and look into Rogue programming in general.
    Though, what do you mean by open mazes and filling the space?

  7. #7
    Registered User guesst's Avatar
    Join Date
    Feb 2008
    Location
    Lehi, UT
    Posts
    179
    Aren't you the one who pointed me to Think Labyrinth? An open maze is one that leaves area on the grid it's occupying unused. Filling the space means the maze covers the whole area, easy to do if you just start a dead end in an unoccupied space and walk it around until you hit a wall, repeat until there is no unused space.

    Most rogue likes don't worry about filling the space. They just put as much stuff in as the want to and stop.
    Type-ins are back! Visit Cymon's Games at http://www.cymonsgames.com for a new game every week!

  8. #8
    Registered User
    Join Date
    May 2006
    Posts
    169
    Oh of course, the rectangular hole inside the maze is actually intentionally placed there. I was referring to Diablo's random maps, where you would occasionally see unpassable areas.
    It's a matter of marking the cells blocked, that the algorithm ignores them.
    Here's another illustration:

    As a side note, on perfect mazes, there is only one path between two points. So it really doesn't matter where you place the start and exit cells.
    Last edited by glo; 07-19-2008 at 03:21 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. rapid random number generation problem
    By Newton in forum C Programming
    Replies: 17
    Last Post: 09-19-2008, 02:08 PM
  2. non repeating random number generation?
    By gencor45 in forum C# Programming
    Replies: 1
    Last Post: 02-08-2005, 05:23 PM
  3. Another brain block... Random Numbers
    By DanFraser in forum C# Programming
    Replies: 2
    Last Post: 01-23-2005, 05:51 PM
  4. biased random numb generation
    By estranged in forum C Programming
    Replies: 4
    Last Post: 12-13-2003, 06:00 AM
  5. fast random number generation
    By Heraclitus in forum C Programming
    Replies: 4
    Last Post: 02-09-2003, 07:48 PM