next »

[st33d]

I always run the checks one tile inwards from the edge.

That, and I always, always, always do a bounding box check whenever there is a bounding box. The clue is in the name, "bounding box."

[Trevor Dunbar]

Nevermind, I was having problems because java's modulus operation is not a true mod operation (hint: its truncated  ).

One of my favorite parts of procedural generation is you can share your maps/worlds simply by sharing the map's beginning seed, as long as the seed isn't changed later to something that doesn't have anything to do with the first seed.

[JasonPickering]

alright so I am working on some procedural level generation, but a little different.

so basically what I am doing is making a Submarine game with a procedurally created ocean. its from the side and room based. (each 16x16 dark blue block below being a room and the brighter blue being the ground) so here are 4 maps that were made and a room example.



alright so basically do you guys think that this is giving me interesting maps? what I am doing now is filling the world with rock and then randomly drilling down each column. do you guys see anyways I could improve this for more dynamic maps. also I plan on adding smaller offshoots for you to explore with a diver outside of the sub.
 

[Daniel Seabra]

I've done some work with lake generation. Here is the map in 3x:


And the program itself + code: http://www.danielseabra.net/prodGen/LakeGen.html
(It's an applet, runs on the browser)


Basically what it does is it creates a map with land which has depth 0 (or less, I suppose, but that's just odd) and then it creates a single dot with depth 32 (this would be 32 UNDER land). That dot then spreads out by checking neighbors and seeing whether they have differences in land similar to it. If they don't, it makes it similar (for example, something next to the 32 would turn into 31 or 30). I changed the array like that until no more changes were made (I checked with a boolean). Once this happened, I drew it. You can see depth differences in shading.

I also experimented a bit with mean value terrain generation, but it just doesn't look very good.



EDIT:
I shamelessly stole ChevyRay's fractal algorithm which divides itself. This is what I got:



Java code and applet here: http://www.danielseabra.net/prodGen/MapGen.html

[TheLastBanana]

I've been working on a procedurally-generated game, and I've got a little article up that describes the generator I'm using:
http://mildlydisconcerting.com/drillboid/2011/01/20/procedural-generation/
It uses the method that ChevyRay showed off in his first article, and then it applies some semi-premade rooms to each "cell" afterwards, a bit like Spelunky's level generator. There's Game Maker source code for the cell generator in there, although the actual rooms are only in the Unity game itself.
The cell generator produces some interesting results:


And, although it has very few premade rooms at the moment, the actual levels are interesting to walk through, too:


Thanks for the article, Chevy - this is the first time I've done any sort of procedurally-generated content, so the article was a great starting point.

[schipman]

This has been a really informative thread for me! Thanks guys!

Here's what I've been working on:
http://dl.dropbox.com/u/1394227/procedural/2_8/WebPlayer/WebPlayer.html

Currently using cellular automata to generate the world

[aDFP]

Great thread! I've only just started reading through it, looks like an insane amount of information here. You guys are incredible.

I wish I'd seen this months ago, before I started working on the city generator for my game Cold Metal http://forums.tigsource.com/index.php?topic=17841.0. I was originally using something along the lines of a roguelike dungeon generator to make the streets, but now I've decided to go with a full-blown 3D procedural system. Probably way too ambitious, but I'll see how it goes. Pics soon...

Edit: If anyone's curious, this is the roguelike-style first-person city generator http://dl.dropbox.com/u/21084866/ColdMetalFPSTest.rar

[Leukbaars]

ooh aDFP, that's really cool =).

I'm working on something similar, trying to create a level generator that generates doom-style levels

It actually generates a logical layout, and I'm adding in colored keycards and doors soon. I really need to optimise it though, right now it takes about 10 seconds to generate because there's a lot of error checking going on :s.





try it out!:

http://www.brameulaers.com/code/fps_setup_06.html

let me know if you find any bugs, it's definitely not foolproof yet

This thread is really awesome by the way, a lot of really helpful stuff!

[Will Vale]

That looks really impressive! Doing 3D levels seems like it would be a lot more difficult than 2D, although I guess Doom-style means 2.5D, so at least you aren't worrying about over/under situations?

10 seconds to generate doesn't sound too terrible compared to typical loading times - you could stream the assets in a separate thread while you were generating to get the compute time for free.

Will

[superflat]

Leukbaars, lovely texture work there - is it your own art?

[aDFP]

Leukbaars, thanks. Yours is looking really nice too, I'll be interested to see how you progress.

[Leukbaars]

That looks really impressive! Doing 3D levels seems like it would be a lot more difficult than 2D, although I guess Doom-style means 2.5D, so at least you aren't worrying about over/under situations?

10 seconds to generate doesn't sound too terrible compared to typical loading times - you could stream the assets in a separate thread while you were generating to get the compute time for free.

Will

Yeah exactly, the layout it generates is essentially just a bunch of rooms and hallways connected on a 2d grid. Maybe later on I'll have it also do room-over-room layouts. It shouldn't be too hard to do but it will add more complexity to the system, which I don't really like :p.

Leukbaars, lovely texture work there - is it your own art?

Thanks! Yeah it is, except for the gun which I stole from a doom alpha . I'll have my own weapons in it soon though

[shrimp]

try it out!:

http://www.brameulaers.com/code/fps_setup_06.html

I really like some of the "composition"* here, like the looming towers and the holes in the roofs with the strong shadows. That's something that is lacking in many PG systems.
(* In the musical sense, perhaps? Sorry, I don't really know how to describe this)

After a brief run around the level, I did find I got a bit disoriented. Maybe once there are doom-style battles and persistent dead enemies, that would help create natural landmarks? Anyway great job!

[davidp]

ooh aDFP, that's really cool =).

I'm working on something similar, trying to create a level generator that generates doom-style levels

It actually generates a logical layout, and I'm adding in colored keycards and doors soon. I really need to optimise it though, right now it takes about 10 seconds to generate because there's a lot of error checking going on :s.

SWEEEEEEET IMAGES

try it out!:

http://www.brameulaers.com/code/fps_setup_06.html

let me know if you find any bugs, it's definitely not foolproof yet

This thread is really awesome by the way, a lot of really helpful stuff!

OMG awesome

[increpare]

ghost diagrams
this could be a neat basis for maze generation... (you can click on the texts to the right to see them)

Leukbaars, those levels have a cool solid feel to them.  Good work so far   Have you looked at any existing doom level generators?

[Nugsy]

Made a little tutorial for something i came up with earlier, hope it helps someone!


Generating ruins/corridors using modified cellular automata.
In semi-pseudo code.


First we randomly decide whether a cell is a wall or not.

Code:

For y = 0 To mapHeight
    For x = 0 To mapWidth
        wallChance = Random(0,100)
        If wallChance > 60
            The current cell becomes a wall
        EndIf
    Next
Next

This gives us:



Next, we use some slightly modified cellular automata to determine the corridors.

Code:

For i = 0 To A random number
   For y = 0 To mapHeight
      For x = 0 To mapWidth

         If the current cell IS NOT a wall
            If this cell is surrounded by 3 or more walls
               The current cell is a wall
            EndIf
         EndIf

         If the current cell IS a wall
            If this cell is surrounded by 4 or more walls
               This cell is not a wall
            EndIf
         EndIf

      Next
   Next
Next     

The amount of times you iterate this is up to you. This is why i have written For i = 0 To A random number.

We now have this:


If you look closely, you can see that there are some corridors that will be inaccessible to a player, as they are blocked by walls.

To solve this we iterate through the map again with a low chance of knocking down a wall.

Code:

For y = 0 To mapHeight
   For x = 0 To mapHeight
      breakChance = Random(0,100)
      If breakChance >= 90
         This cell is no longer a wall
      EndIf
   Next
Next

We now have:


Now almost every area is reachable. It is very rare that an area will not be accessible to the player.


So there we have it! Procedurally generated dungeons using slightly modified cellular automata.
Try it, then tell someone what you've done. They'll think you are super clever.

Seriously though, i thought this was pretty neat. I hope it helps someone out there to make some cool dungeons. I know this isn't groundbreaking - but if you use this tutorial to help you with your game, credit would be nice!

Thanks for reading!

[Leukbaars]

Leukbaars, those levels have a cool solid feel to them.  Good work so far   Have you looked at any existing doom level generators?

I didn't even know there were any! I checked out Oblige, and it's very impressive . It seems to work similar to mine, creating connected rooms with their own themes, so I know I'm on the right path at least :p

[Hayden Scott-Baron]

Nugsy, this is awesome! I love seeing tricks like this. It always strikes me that the best game coders have a host of these things up their sleeves.

[Fifth]

Heh, awesome.
I actually just had a bit of success generating maps using some very specific cellular automation myself, so it's good to see more ways you can use the technique.

[DeadPixel]

A technique that I've had some luck with in the past is working with perfect mazes (meaning there is always a valid path from start to finish) and modifying them.  I got the idea from a web site I stumbled upon some time ago while researching this stuff.  Sadly I no longer have the link or the author's name.

For instance, if we start a basic DFS style maze:

Code:

Initialize an array of empty cells
Keep a stack of visited cells for backtracking
Track how many cells we've visited in total
Pick a random cell to start and mark as visited

do
{
    find all neighbors of the current cell that have not yet been visited (no exits)
    if we have neighbors
    {
        pick a random one to move into
        knock down the wall between the cells
        mark the current cell as a corridor, non-wall, etc
        add the current cell to our stack
        set current cell to the next cell
        iterate visited count
    }
    else
    {
        get the last cell on our stack
        set as current cell
    }
} while(cells visited < total cells)

Then we proceed to shrink the maze a bit by finding all of the dead ends (that is, cells with only one exit) and removing them N number of times.

Code:

for n = 0 to iterations
{
    loop through all cells and add the ones with a single exit to a list
    for each cell in the list
    {
        remove the exits from this cell and the cell it leads to
        remove the cell by setting it to 'empty'
    }
}

Next we extend the remaining dead ends until they collide with an existing corridor/cell.  This will create loops and remove all dead ends.  This part is pretty much the same as the maze generation, but with a different termination clause.

Code:

loop through all cells and add the ones with a single exit to a list
keep a stack of cells we have visited
for each cell in the list
{
    do
    {
        find all neighbors of the current cell that are not in our visited stack
        if we have neighbors
        {
            pick a random one to move into
            knock down the wall between the cells
            mark the current cell as a corridor, non-wall, etc
            add the current cell to our stack
            set current cell to the next cell
        }
        else
        {
            get the last cell on our stack
            set as current cell
        }
    } while(the current cell has only one exit (ie, is still a dead end))    
}

From here you have the basic layout of a dungeon done.  You have a fully navigable set of corridors and only need to add the 'rooms'.  Probably the easiest way is to simply take the leftover empty space and designate those as rooms.  Add a door along a random wall that touches a corridor, and you're done!



Another method that works well for room placement, especially if you'd like to have pre-designed room chunks, is to do the following:

Code:

for r = 0 to roomsToPlace
{
    choose a random room from a preset list
    give the room a default large score (max int, for instance)
    for y = 0 to mapHeight, y += roomHeight
    {
        for x = 0 to mapWidth, x += roomWidth
        {
            'place' the room's top-left corner at x, y
            keep a temp score for this location
            for each cell along the room's walls
            {
                for each outer neighbor of the wall cell
                {
                    if mapCell == corridor
                        tempScore += 1;
                    if mapCell == room
                        tempScore += 100;
                    if mapCell overlaps the room cell
                        tempScore *= 3;
                }
            }
            if tempScore < score and tempScore > 0
            {
                score = tempScore
                set the room's real position to x and y
            }
        }
    }
}

This will let you generate dungeons with your pre-frab rooms while maintaining some randomness in terms of placement while also ensuring that the rooms will always be attached to corridors.  Changing the weights around will give drastically different results so there's room for customization, as well as adding weights above and beyond the basic ones listed there.

EDIT:  Fixed bad room chunk placement code.