Diablo-look a like possible on A8?

[Heaven/TQA]

i just spend some time on the level generator as my i think this is the key to avoid mistakes later with the mapper...

 

look what i have found:

 

I. A Dungeon is a Maze

First of all, it is helpful to think of any dungeon as simply a maze—a collection of corridors that turn every which way. The first part of generating any dungeon, then, is to create a random maze.

 

Now, there are lots of different ways to generate mazes (for some idea of how many different types of mazes and algorithms there are, check out the Maze Algorithms page at Think Labyrinth). For the dungeon generator, I just picked a straightforward algorithm that I'm pretty familiar with—it's a variation on the "Hunt-and-Kill" algorithm. The algorithm creates a 2D, normal, orthoganol, perfect maze, which simply means that the maze is rectangular, with all passages intersecting at right angles, and that there are no loops or inaccessible areas in the maze.

 

Here's how the algorithm I picked works. Feel free to substitute this one with any other algorithm.

 

Start with a rectangular grid, x units wide and y units tall. Mark each cell in the grid unvisited.

Pick a random cell in the grid and mark it visited. This is the current cell.

From the current cell, pick a random direction (north, south, east, or west). If (1) there is no cell adjacent to the current cell in that direction, or (2) if the adjacent cell in that direction has been visited, then that direction is invalid, and you must pick a different random direction. If all directions are invalid, pick a different random visited cell in the grid and start this step over again.

Let's call the cell in the chosen direction C. Create a corridor between the current cell and C, and then make C the current cell. Mark C visited.

Repeat steps 3 and 4 until all cells in the grid have been visited.

Once that process finishes, you'll have your maze! There are a few variations you can do to make the maze more interesting; for example, my dungeon generator has a parameter called "randomness". This is a percentage value (0–100) that determines how often the direction of a corridor changes. If the value of randomness is 0, the corridors go straight until they run into a wall or another corridor—you wind up with a maze with lots of long, straight halls. If the randomness is 100, you get the algorithm given above—corridors that twist and turn unpredictably from cell to cell.

 

II. Mazes vs. Dungeons

It is important to note that the algorithm given above results in no loops in the maze. It is also important to note that the algorithm results in a dense maze—that is, every cell contains a corridor.

 

This "pure" maze is probably not what you had in mind when you asked for a dungeon. For example, sometimes a dungeon passage intersects with another passage, or with itself, forming a loop. Also, an underground dungeon may cover a lot of territory, but not fill every square meter of rock—it is probably sparse, as opposed to dense.

 

There are two steps I used to convert the maze into something more like a dungeon (though still lacking rooms).

 

The first step involves a parameter I called sparseness. It is an integer value; you may want to experiment with it to arrive at a value (or set of values) that work best for you. It is used as follows:

 

Look at every cell in the maze grid. If the given cell contains a corridor that exits the cell in only one direction (in otherwords, if the cell is the end of a dead-end hallway), "erase" that cell by removing the corridor.

Repeat step #1 sparseness times (ie, if sparseness is 5, repeat step #1 five times).

After sparsifying the maze, you should wind up with large "blank" gaps, where no passages go. The maze, however, is still perfect, meaning that it has no loops, and that no corridor is inaccessible from any other corridor.

 

The next step is to remove dead-ends by adding loops to the maze. The "deadends removed" parameter of my generator is a percentage value that represents the chance a given dead-end in the maze has of being removed. It is used as follows:

 

Look at every cell in the maze grid. If the given cell is a dead-end cell (meaning that a corridor enters but does not exit the cell), it is a candidate for "dead-end removal."

Roll d% (ie, pick a number between 1 and 100, inclusive). If the result is less than or equal to the "deadends removed" parameter, this deadend should be removed. Otherwise, proceed to the next candidate cell.

Remove the dead-end by performing step #3 of the maze generation algorithm, above, except that a cell is not considered invalid if it has been visited. Stop when you intersect an existing corridor.

So, now you have something looking more like a dungeon. All it lacks, now, are rooms…

 

III. Room Generation and Placement

This was perhaps the trickiest step. Looking at my generator, you'll see three parameters: "room count" (Rn), "room width", (Rw), and "room height" (Rh).

 

Generating rooms is actually easy: Rw is just a random number between the minimum and maximum widths. Rh is generated similarly.

 

Placing the rooms was trickier. The idea is to find a place in the maze where the given room overlaps a minimum of corridors and other rooms, but where the room touches a corridor in at least on place. To this end, I implemented a weighting system.

 

The program tries to put the room at every possible place in the dungeon. The algorithm works as follows:

 

Set the "best" score to infinity (or some arbitrarily huge number).

Generate a room such that Wmin <= Rw <= Wmax and Hmin <= Rh <= Hmax.

For each cell C in the dungeon, do the following:

Put the upper-left corner of the room at C. Set the "current" score to 0.

For each cell of the room that is adjacent to a corridor, add 1 to the current score.

For each cell of the room that overlaps a corridor, add 3 to the current score.

For each cell of the room that overlaps a room, add 100 to the current score.

If the current score is less than the best score, set the best score to the current score and note C as the best position seen yet.

Place the room at the best position (where the best score was found).

For every place where the room is adjacent to a corridor or a room, add a door. (If you don't want doors everywhere, add another parameter that determines when a door should be placed, and when an empty doorway [ie, archway, etc.] should be placed).

Repeat steps 2 through 6 until all rooms have been placed.

 

 

now i am trying to implement that without errors...

 

http://www.aarg.net/~minam/dungeon_design.html

[Ghost...]

Hi,

rg dungeon generator ..maybe also interesting:

roque like games..

GHO

[Heaven/TQA]

thanks! indeed: "One thing for sure is that the implementation of a map and a dungeon generation algorithm is one of the first things implemented in any roguelike."

 

thats why we spend so much time on it.

[Heaven/TQA]

Ghost, thats the site which i searched for nearly a month now...

 

great...

[Heaven/TQA]

not bad as well...

 

http://www.fargoal.com/

 

like it more than the nethack versions...

[Cybernoid]

Heaven,

 

Thanks for sharing all the good information!!! These are great tips, dungeon design and game links that you have provided...

 

Thanks!!!

[Cybernoid]

not bad as well...

 

http://www.fargoal.com/

 

like it more than the nethack versions...

 

 

Pretty cool that the source code for the dugeon generator is included in the PC download (map.c)...

[Heaven/TQA]

yup.

[Heaven/TQA]

have you ever played these two ones?

 

one is a-rogue written in atari basic and the other one is a mastertronic tape (no...its not the rogue you already knew) ...

 

all these can be done better...

A_Rogue.zip

Rogue.zip

[Heaven/TQA]

oh and not to forget Dark Chambers by Atari...

 

http://www.atarimania.com/detail_soft.php?...VERSION_ID=1507

[belboz]

Don't forget the game that inspired Gauntlet and was basically redone later as Dark Chambers.

 

Dandy!

 

http://gury.atari8.info/details_games/1008.htm

[Albert]

Don't forget the game that inspired Gauntlet and was basically redone later as Dark Chambers.

 

Dandy!

 

http://gury.atari8.info/details_games/1008.htm

Wow, I was a huge 8-bit fan back in the day and I never heard of this game! I just read all the linked articles from that page--very interesting story about how Dandy came first! I love Gantlet, and remember the 8-bit version being subpar. Wish I had known about Dandy!

 

..Al

[Cybernoid]

Don't forget the game that inspired Gauntlet and was basically redone later as Dark Chambers.

 

Dandy!

 

http://gury.atari8.info/details_games/1008.htm

 

 

Wow! This is very cool!!! And the story behind this is awesome... I did not know that.

 

Wow! This game does play like Gaunlet!!!

[deathtrappomegranate]

There's a nice little author's note on the last page of the original APX manual, too:

 

Dandy by APX - Atarimania

[Cybernoid]

Okay, I implemented a simple random dungeon generator that I might use for my game on the server. It might be useful for yours as well, Heaven. I took a look at the links, this one in particular: http://www.aarg.net/~minam/dungeon_design.html

 

I liked what he did, but I think that it takes too much time. First, he starts with generating a maze, then deleting corridors for sparseness, then adding in the rooms.

 

I took the opposite approach:

(1) generate random room size between certain limits

(2) check if the corners overlap with another room (not exhaustive, but yields good results).

(3) save the center points of each room

(4) pick random direction for room, go in direction of a wall,

(5) if found wall, start working on a hall

(6) place a random hall, if run into anoth hall turn, if run into a room, stop

(7) goto 4 for as many entries into a room (2 is good)

(8 ) goto 4 for each room

 

This way it places large rooms first, then snakes a hall around for the rest of the dungeon. This has some parameters for randomness (actually inverse randomness), room size, number of entries into a room.

 

It is written in perl for now for debug...

 

 

 

 

dungeon.zip

Edited June 23, 2006 by Cybernoid

[Heaven/TQA]

thanks... i am just playing around with my mapper as well...

 

so... to be honest... now i need your maths brain...

 

the tileset PG drew...can i really turn a 2d map (like your asci caves f.e. or my bitmaps) with this tileset into a nice dungeon? if you checked my mapper than you realise how it scans the map... from left to right but something tells me that i need to do it the other way around or maybe in another way?

 

maybe i have to adjust not the mapper but the level generator?

[Cybernoid]

Yes, this is the difficult part to map correctly the wall/room boundaries...

 

Hmmm...

[Heaven/TQA]

in your perl script... your level generator knows the north/south/east/west side of each room...so you can mark them with different chars...a potential mapper could then pick the right one...

 

but think of the iso perspective... how do we scan your map to turn it into a 3d version with PGs tileset... from NW to SE or NE to SW? or doesnt matter?

[gauntman]

So, for "research purposes only" I installed and played Diablo II LOD last night. (I had finally excised this from my machine, after it ate hundreds of hours over the years).

 

A few observations after playing solid for 4 hours and finishing Act 1:

 

1)

Randomized levels are important

- having fixed levels (like Dungeon Siege 1&2, Titan Quest, just about every MMO, etc.), drastically reduces the replayability. It can make for excellent eye-candy, but ask anyone who has played Dungeons and Dragons Online how much fun it is to rerun the same dungeon 15x. In any case, we don't want to have to store all that content if it can be avoided.

 

It is worth considering using different map generation techniques for different levels (see map comments below). See also comments on passage-heavy maps vs room-heavy.

 

2)

A balanced and interesting drop system is a must

!

 

The drop system can make or break the game. Interestingly, I enjoyed Diablo II when it first came out, but it didn't really capture me until the expansion pack. Dungeon Siege and (even Sacred to some extent) were crippled by fairly lame drops. Fate seems to have the opposite problem -- too much uberloot cripples the game.

 

3)

Lots of monsters attacking at once

- I mean lots. I had forgotten how big the fights were - modern 3D games seem to loose this aspect. For a comparison, think of the difference between Doom and Quake. The number of monsters is approaching Robotron intensity. I don't know if that many monsters can be thrown at the player on the A8 on an isometric map

 

Also of note, the number of different monster types in a single area (or dungeon level) is fairly constrained in Diablo - only 2 or 3 types per area. The notion of mini-bosses and minions is also worth considering for retention. (Perhaps the minions are character based only, the mini-bosses can use 1 or 2 players for extra color or effects).

 

Of lesser importance:

4)

A skill tree for customizing your character

- this may not be as important in a single player game (see Fate and Dungeon Siege for examples of a generic character; Gauntlet and Sacred for examples of class-based characters).

 

Either class based or generic, quick advancement over many levels is more fun then slower advancement over a few. Getting special powers as you progress is nice, but can be handled via equipment or spells in addition to class based skills. (See GuildWars for another very interesting way of doing this)

 

5)

Showing equipment on your character

- this may not be as important to show at the same level as modern games -- however, some basic color changes or primary weapon sets might be nice. Alternatively, if there are epic weapon drops (special 1-of-a-kind weapons) - perhaps only these have a visual impact.

 

A few thoughts on maps:

When I was working on my dungeon game long ago, I implemented the maze + room system as described above. (I prototyped in C, and saved the .bin out - later this was to be ported to assembly); I discovered that while skinny passages are nice for Rogue and Adom, they are a pain and not all that fun in action RPGs. (Perhaps this is due to having to line up exactly to go down a hall when pixel level movement is possible, instead of moving in character or tile based steps).

 

Looking at the dungeon-like levels in Diablo (the Crypt, Mausoleuam, Dark Tower, Jail, and Cloister levels) most of the maps are simply connected rooms - passages are very rare. In this sense, the maps look more like Gateway to Apshai (the cartridge, not the original Temple of Apshai) then Adom or other rogue-likes. I suspect that this level generation may be easier and more fun to play.

 

The second observation is that changing map generators as the player descends is probably a good idea. Interspersing cave levels as described early on in the thread with more traditional dungeon levels (some room dominate, some passage dominate) makes for a tastier mix.

[gauntman]

in your perl script... your level generator knows the north/south/east/west side of each room...so you can mark them with different chars...a potential mapper could then pick the right one...

 

but think of the iso perspective... how do we scan your map to turn it into a 3d version with PGs tileset... from NW to SE or NE to SW? or doesnt matter?

 

I was playing with some algorithms on paper the other night. If you intend to use MWP as a display technique (almost a requirement if you want to scroll and have a chance at a 5200 port) - then it must be possible to draw vertical and horizontal stripes in screen space.

 

Drawing a vertical stripe requires walking a 2D map from the NE corner to the SW corner ('/'); Drawing a horizontal stripe requires walking the map from the NW corner to the SE corner ('\');

 

I was considering a drawing routine based on the cavern like maps (no walls) earlier in the thread - I will be travelling this weekend, but I might have time to write this up next week.

Edited June 23, 2006 by gauntman

[Heaven/TQA]

thanks for your comments, very usefull...

dont play D2:LOD... otherwise you get lost...

 

the whole project and researches keep my free time and last 3 weeks i havent returned to World of Warcraft... i am just playing and coding my own WoW...

 

i even bought & read AD&D stuff just to capture where all came from...

[Goochman]

I hate to be selfish here but I would suggest ditching a 5200 port and try to make as good a 65XE/130XE verison as you can - the baseline of this already looks great and Id hate to sacrifice something for NTSC only 5200 owners.

[Heaven/TQA]

and... i've rerun 20 times deadmines of WoW...so i know what you mean...

 

i think that we are now on the right track with the "connected rooms" approach...

 

i have to give my level generator more AI as he is setting the map so he must know what he is doing like where are walls etc. when a map is finished and it took not too much time maye a 2nd pass can correct all other stuff. f.e. connecting lava holes to a lava sea etc...

[Heaven/TQA]

btw. the interesting thing is when really digging into this kind of RPG and all rogue likes and D&G paper RPG... plus WOW plus Tolkien etc... you get a real big picture how everything envolved... and where the inspiration was...

 

imho Blizzards work was not the action RPG but to balance everything right and to keep the player addicted to the game... that's all for Diablo... (the story...well...forget it... )

[Cybernoid]

I think maybe the mapping can be done by looking at 3 cells at a time. If you walk through the map from top to bottom and from left to right, and look at the cell below and to the right, you have the following 8 cases:

 

(Legend)
# = wall
% = floor


(1)
%%  = floor
%

(2)
%# = SE wall
%

(3)
%% = SW Wall
#

(4)
## = NE Wall
%

(5)
#% = NW Wall
# 

(6)
%# = S corner
#

(7)
#% = N Corner
%

(8)
## = solid wall
#

 

I think this might work...