random level generation

[Guest]

If you were to play a game like diablo would you want 2d isometric or 3d with a birds eye view. I want to do random level generation like in diablo, but think that might be a bit difficult in 3d? any insight?

[pfo]

It's actually unrelated to 3d, look around on the net for algorithms which will generate a complete 2d maze, they're pretty neat. Some let you do things let specify areas as start and finish, and the algorithm will generate a completely random maze from A to B each time. Then what you do is take that finished result maze (which is usually in some type of data structure describing the 2d maze) and turn it into your 3d maze. You can build each 'section' of the level, and then load / position / snap them together to regenerate your maze in 3d.

[jam]

You can build each 'section' of the level, and then load / position / snap them together to regenerate your maze in 3d.

How would you go about doing this?

[pfo]

Well, maybe you'd have a 'room' piece, and maybe a 'hallway' piece, etc... and then you go through your maze data struture, and at each position load the appropriate model to represent the maze, and orient it correctly. Keep doing this for each section of the model and when its finished you should have a maze. You need to be careful that all the pieces can come together right (i.e. place hallways end to end so they don't overlap or have gaps).

[jam]

On paper it sounds easy, but doing it seems to be a different matter

It would be cool if it could be done, you would be the first person to do it, I think no other game has done something like this before.

[pfo]

Code: Select all

On paper it sounds easy, but doing it seems to be a different matter Sad 

Yeah, I guess so The real key is to break it down into steps, first step would be a good algorithm to generate mazes. You could test this by simply exporting the maze data as a text file, or a bitmap or something to check its generating valid mazes. That seems like the only hard part to me. The task of loading and connecting the other pieces seems trivial... However the design considerations of the level pieces and the restrictions that imposes would be something to consider. Imagine though, if you said 'ok, each piece is 10x10x10' then you generate a 100x100 maze, you'd need 100 10x10 pieces to make up the maze. Each piece in each slot corresponds with the maze.

Just to clarify, I am not doing something like this. I don't have any need for random mazes, but I am considering allowing it maybe in the future. I'm working more on a FPS / RPG type game (yes, that is both combined, I think its a cool concept).

[sRc]

this is something I'm going to do with one game I'm working on. im working on a sort of sandbox app to test various things before i start putting together actual games, I'm gonna try and see if I can implement something like this

[jam]

this is something I'm going to do with one game I'm working on. im working on a sort of sandbox app to test various things before i start putting together actual games, I'm gonna try and see if I can implement something like this

That would be awesome if you can get it working.

However the design considerations of the level pieces and the restrictions that imposes would be something to consider. Imagine though, if you said 'ok, each piece is 10x10x10' then you generate a 100x100 maze, you'd need 100 10x10 pieces to make up the maze. Each piece in each slot corresponds with the maze.

That's a good start I think. It kind of reminds me of how Wolfenstein 3D worked.

[grunt]

ok..... this will probably not work because I dont habe the IDE on the station that I am currently working on. These are just the thoughts of mine on how to get this working. Probably full of syntax problems, and logic problems. This would also be very basic with no rooms, and a very 'wierd' maze. But hey its a start to a dungeon. Basically what I am thinking is:

Creating a grid
Flagging all cells in the grid unvisited
Choosing a random cell and flagging it visited
Choosing a random direction from that cell and flagging it visted
Repeating steps 3 and 4 untill all cells have been visited

Code: Select all

‘boolean determining if the cell should be filled
Dim visited as Boolean

‘do a rectangular array of 512 x 512
Dim grid(511, 511) as integer

'set each cell to unvisited
dim intval as integer
for each intval in grid
	visted = false
next

‘choose a random cell in the grid
'we need to do this once for both x and y
Dim randcell as integer

for xy = 0 to 1
	randcell = randomclass.next(0, 511)
next

'pick the random cell and mark it visited
if grid(randcell, randcell) then
	visited = true
end if

'choose a random direction
dim randdir as integer = randomclass.next(1, 4)

if randdir = 1 then
'direction = north
'subtract a random number from 5 to 20 from y

elseif randdir = 2 then
'direction = south
'add a random number from 5 to 20 from y

elseif randdir = 3 then
'direction = east
'add a random number from 5 to 20 from x

elseif randdir = 4 then
'direction = west
'subtract a random number from 5 to 20 from x
end if

'reiterate until all cells are visited....

I would love it if I could work together with someone on this idea.

[pfo]

The only problem with that is: how can you tell where the walls in the grid are? Also, if you visit every cell, you'd end up with a huge room (if you didn't mark where walls are). Plus, for a video game, to make things interesting, you need to generate some rooms every now and then.

For all those interested in this, check out what I dug up on the net http://www.mazeworks.com/mazegen/mazetut/ This is a pretty good start at understanding the first steps of maze generation.

[Guest]

i actually found a smoking gun. Might want to email him first because it looks like it took him a lot of time.

http://www.heroicadventure.com/dev/code/dungen3.vb.txt