Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[Derakon]

EDIT
Jetblade is now an open-source project! You can check out the code at the project site here. It's written in Python, requiring Python2.5 and PyGame to run. The rest of the post below is pretty hilariously out of date; a lot has happened in the interim.
/EDIT

This is a little project I've been working on for about a week now that I thought you all might be interested in.

(Click for full-size version)


Unlike Toady's procedurally-generated cave systems, I'm just doing two dimensions...but this is a side-on view, not top-down, since they're intended to be used for a platforming game. I've had to solve a lot of pretty interesting problems to get this much; it's been fun! The green lines, for example, are the tree that I've created to provide a starting point for the tunnels; the tunnels themselves, and the rooms, are created by a spacefilling automata. The small platforms are created by a wallwalking algorithm that looks for areas of "local difficulty" (e.g. steep walls or large gaps). The map generator clocks in at 1048 lines of Python (168 of which are whitespace, 174 comments), and it takes about 6-8 seconds on my two-year-old computer to make maps like the above example.

At the moment I'm still hammering out a few details involving accessibility -- I don't think it'd be possible to get out of the lower-right room once you've entered, for example -- but soon I hope to move on to adding little features to some of the rooms for additional flavor -- pools of water or magma, statues, spiked floors, and so on. Someday I may even add a player! Wouldn't that be something.

[Ampersand]

Though it may defeat the purpose of the game, the addition of some sort of rope or grappling hook may resolve the problem.

[EchoP]

Looks amazing...
Are you willing to show the program that did it? As always feel free to say no

[Derakon]

Ampersand: I hope to get the accessibility problem licked to the extent that I can control which areas the player has access to depending on which items they've found. I'd like to add a grappling hook to the game, though graphically and control-wise I'm not certain if I can make it work well. Simply having one from the start would be a bit game-breaking though.

EchoP: since I hope to eventually turn this into a game I can sell, I can't show you the program. However, I'm perfectly willing to outline my algorithm if you like.

[Virex]

Hmm, If you're doing what I think you're doing, this could easely be expanded to a system that can create man-made structures, by adding several constraints to the system. You ought to be looking at the tree especialy if you'd want to do that.

[Derakon]

I'm curious what you think I'm doing.

I can place constraints on the direction and thickness of the tree branches easily enough. At the moment I need to avoid loops in the system, since that can break my accessibility rules; that's the only major problem with the map right now that I haven't yet determined how to solve. Loops make exploration much more interesting.

[woose1]

Will the system be moddable? Ex: Changing the spread of tree lines, thickness of tunnels, frequency of platforms, etc.

[Sowelu]

That looks AWESOME.

[Virex]

If he's using an L-system, then that ought to be possible.

I'm curious what you think I'm doing.

By the looks of it (and because you're calling it a "tree"), you're using a simple L-system to generate the skeleton tree, probably starting in the center and setting out 4 actors. Then from each point generated this way you start a second L-system that fills everything up. The only thing I'm not sure about is how these fillers work. It seems as if you allocate them an amount of tiles based upon their distance from other points, and have them fill the surrounding area in a square-like fashion, putting some restraints on them to prevent areas from spilling over into each other.

Now to improve the accessibility, ideally you'll want to have the construction algorithm work in such a way that you don't need to check the accessibility at all, but that might be difficult. The way I would try it would be by first filling in the platforms and then do the space-filling algorithm. Then you'll just need to put restraints on the filler to make sure that the distance between the floor and the nearest platform is a jump-able distance and you're set. Perhaps you could do a final pass to cut away redundant platforms, but I don't think that'll be necessary.

Also, you can create a feeling of persistence by not giving each level a completely different skeleton tree. Instead you could generate a "stack" of turn angels and distances and use that for the tree of level one. Then you gradually change these values by small but noticeable increments. That way people will see the cave evolve slowly. Your space-filling algorithm and platform placing algorithm should of course differ a nice bit more to keep things interesting.

[Derakon]

Heh. You ascribe more complexity to this system than there really is. I call it a tree because that's what it is -- an acyclic directed graph in which every node has only one path to the root node. It may be an L-system (I'm not familiar with the concept, but a brief look over the Wikipedia article shows certain basic similarities), but I didn't set out specifically to use that theory in the construction of the map. I just said "Okay, make a tree starting in the center. Make certain the branches don't cross each other and that they don't get too close to each other either."

Carving out the tunnels based on the tree branches is done using a simple spacefilling cellular automaton. The trees lay down cells that have a desired number of replication cycles; on each cycle, the cells grow, and if they run into cells "owned" by a different tree branch, a wall forms between them. I'm handwaving a lot of tweaking and details here, but that's basically how they work. The rooms at the end, currently, are simply cells with a much higher number of replication cycles. Thus the spacefilling has no conception of "floor", "wall", or "ceiling".

It's actually desirable for me to have tunnels that are inaccessible at the start, since part of the game is meant to be figuring out where you can go, finding powerups, and then figuring out what those powerups let you reach. The big problem is simply making certain that I know which areas are accessible and which are not, so that I can place powerups accordingly.

Woose1: the settings for the map are configurable, but I doubt that I'll be exposing all of the configuration details to players since it's very easy to make impossible maps which break the generator and/or let the player get stuck. Most likely the player will only have control over the overall size of the map and maybe a "complexity" slider.

[Virex]

Heh. You ascribe more complexity to this system than there really is. I call it a tree because that's what it is -- an acyclic directed graph in which every node has only one path to the root node. It may be an L-system (I'm not familiar with the concept, but a brief look over the Wikipedia article shows certain basic similarities), but I didn't set out specifically to use that theory in the construction of the map. I just said "Okay, make a tree starting in the center. Make certain the branches don't cross each other and that they don't get too close to each other either."

You did use it, since it's the most logical aproach

Carving out the tunnels based on the tree branches is done using a simple spacefilling cellular automaton. The trees lay down cells that have a desired number of replication cycles; on each cycle, the cells grow, and if they run into cells "owned" by a different tree branch, a wall forms between them. I'm handwaving a lot of tweaking and details here, but that's basically how they work. The rooms at the end, currently, are simply cells with a much higher number of replication cycles. Thus the spacefilling has no conception of "floor", "wall", or "ceiling".

Well, a start would be to give it a concept of floors. This can be done rather easely by checking which floors have an empty space above it. Then you can start accesability (or actualy the ability to get out again) by working upward from the floors and checking the distance to the next floor or platform.

It's actually desirable for me to have tunnels that are inaccessible at the start, since part of the game is meant to be figuring out where you can go, finding powerups, and then figuring out what those powerups let you reach. The big problem is simply making certain that I know which areas are accessible and which are not, so that I can place powerups accordingly.

What you could do is adjust your cell aglorythm. Once it has reached a certain size, it'll set a platform that is within reach of another platform (you can fiddle with the reach to make areas that are only accesible at later stages. Just be sure to have them above things that are always accesible). Then you start a daughter cell from the new platform. This daughter cell will not interfere with any other daughter cells of the same parrent or that parrent, but it will create a wall with cells of another family. That way you are sure that cells of a certain family are always accesible for someone with certain upgrades and place bonuses accordingly. Just be sure to build upward so people can always get out if they're stuck at the bottom.

[Sowelu]

I'd disagree that an L-system is appropriate here, since they have no concept of loops at all, and they don't seem particularly suited for stochastic models...Most of those examples are context-free grammars, and that really isn't useful at all when you have to deal with a concept of space...They generally don't terminate in any useful way (except possibly becoming stable after N iterations) and, being iterative, have no sense of how the whole system fits together...  I'd say that's really the wrong tree to bark up.

Hmm.  I think this would look even more awesome-neat if the walls started out a little thicker, and then another pass was applied to touch them up a bit with scenic stuff, so you had more room to work with when shaving debris off the floor or something.  Then again, they look REALLY cool now.

[Derakon]

Virex: the main difficulty with the approach you're suggesting is that it requires analysis of the local area of the map. Keep in mind that a cell "expands" by making copies of itself in adjacent squares in the grid, not by literally expanding. Thus it can't know, after N expansions, if it's gotten huge, or if it's been absorbed by other cells. This gets especially tricky at the places where the tree branches; I've had more than a few different algorithms completely choke the branchpoints with platforms.

What I'm using right now is a wallwalker algorithm that runs after the tunnels have been carved out. It proceeds along the walls, ceilings, and floors, and measures the local steepness, then uses that to determine if it's worth adding a platform in. This is basically similar to what you said with "...checking which floors have an empty space above it. Then you can start accesability (or actualy the ability to get out again) by working upward from the floors and checking the distance to the next floor or platform."

Sowelu: I'll be adding tilesets with actual graphics at some point, naturally, but that has to take a back seat to getting the map functional. I did just go in and make the walls a bit thicker; it's not really noticeable close-in except when you have a tree branch split into two new branches with only minor differences in their angles, but it is an improvement. Thanks for the idea! I'm not certain what you mean about "shaving debris off the floor", though.

[Sowelu]

What I meant by that idea is:  Let's say you want the floor in a given branch to be smooth, for some reason.  Like, you want it to look previously inhabited, or maybe you want to carve stairs out of a slope.  Decent as a post-processing step, but needs to have enough 'wall' to work with, that way when you remove material to flatten out a floor, you don't cut into the ceiling below.

[Virex]

I'd disagree that an L-system is appropriate here, since they have no concept of loops at all, and they don't seem particularly suited for stochastic models...Most of those examples are context-free grammars, and that really isn't useful at all when you have to deal with a concept of space...They generally don't terminate in any useful way (except possibly becoming stable after N iterations) and, being iterative, have no sense of how the whole system fits together...  I'd say that's really the wrong tree to bark up.

Those L-systems given by Wikipedia arn't stochastic, but hack in a random number generator at some points and things become different
Also, they have the aditional bonus of being interconected, which is quite important for caves. Perlin noise will usualy generate isolated area's, which means you have to backtrack and open up some passages. You could use Voronoi diagrams, but they tend to generate larger angels then the ones you see on the example. Also, voronoi diagrams are completely looped, there are no dead ends. That only leaves something similar to an L-system, or a celular automaton, though I would be interested to see if you've got another idea.

Also, it's quite easely to give an L-system or a celular automnaton some sense of space, since it's working on a finit and usualy small amount of points. For each of those points you can check the surrounding area and make rules based upon that. Perlins and Voronois don't quite have that luxery, thouhg you could hack in a small amount of sense into a voronoi.

In this case, a celular automaton wouldn't be too great for generating the skeleton I'd assume, since it'd be unable to easely generate twisting arms and things like that. Also, you'd need to check way more points if you're going to base descions upon the surroundings.

Virex: the main difficulty with the approach you're suggesting is that it requires analysis of the local area of the map. Keep in mind that a cell "expands" by making copies of itself in adjacent squares in the grid, not by literally expanding. Thus it can't know, after N expansions, if it's gotten huge, or if it's been absorbed by other cells. This gets especially tricky at the places where the tree branches; I've had more than a few different algorithms completely choke the branchpoints with platforms.

Hmm, that's not easy to solve. Have you considered my previous idea of placing the platforms first and then generating the cave? For that you practicaly coppy the aglorithm you're using for the tree. I think it'll be quite possible to get the platforms to spawn upon a set distance, based upon the dificulty level for the area, that is jumpable/climbable/traversable in another way if you've got a certain set of upgrades.

Generating the floor on a jumpable distance could be done by capping the max amount of replications your celular automaton can do. If you'd like a slightly more comlicated system you could even only cap it in the down direction