Welcome, Guest. Please login or register.
Did you miss your activation email?

Login with username, password and session length

 
Advanced search

1384988 Posts in 66307 Topics- by 58780 Members - Latest Member: masendor

November 23, 2020, 08:08:43 PM

Need hosting? Check out Digital Ocean
(more details in this thread)
TIGSource ForumsDeveloperDesignLevel design via perlin noise (Suggestions?)
Pages: [1] 2
Print
Author Topic: Level design via perlin noise (Suggestions?)  (Read 5510 times)
baconman
Level 10
*****


Design Guru


View Profile WWW
« on: August 23, 2011, 04:43:16 AM »

TL/DR summary:

Some game projects I'm doing right now use Perlin Noise to generate level chunks. I'm debating on whether to keep screens lined up, for 15 simple outputs per level, offsetting horizontally or vertically for 63 outputs, or calculating both offsets for 255 of them; as well as considering the level design changes that would come from such offsets.

Which kind of games would you design like that, and what offset/calculation option would you go with?


Actual, lengthy "wall-o-text" post:

Okay... I'm working on a variety of projects right now that this CAN apply to, so I'll try to keep it brief and not too hard to follow. I will likely fail at both. Among the project genres are platforming (both in nonlinear start-to-finish gameplay and Metroidvania-like/exploration), Zelda-like action-adventure, and even shmup/racing/driving. Basically, if it's a kind of game that CAN have levels, this concept can be theoretically applied to it.

The level-design generating algo/idea I'm going with now is similar to Spelunky's in function (via level chunks), but rather than being entirely tile-based, the whole scene/screen is rendered as it's own "object" (although I'm also going for artisitically tile-based looking - but that's an art thing). First, "color screens" are randomly shuffled between 6 "color codes;" and it'll check adjacently for one of two outcomes: If the "colors" match, it will create a sublevel with a real blockade between those two rooms/borders, and if they're polar-opposites, it will create a "fake" blockade between the two instead (by inserting a foreground/fake wall or destructible one, something like that).

The difficulty I'm having here comes in wanting to keep enough variation between these preconcieved level chunks while keeping them functional (and the most important part of that word, "fun"). I'm also debating on whether to keep rooms aligned (and simple-calculated, with + 1/2/4/8 determining the corresponding directions, but that only allowing for 15 outputs (0-14), considering "15" would simple block off everything), or going with a vertically or horizontally offset-by-a-half-screen layout, which would add 16/32 factors in it, and thus a greater variety of room designs (as well as the increased work of pulling that off, btw).

Clearly, certain genres would benefit differently from these different approaches, which is part of what I'm hoping to get in feedback here; as well as maybe ideas of what to do with certain room styles; like especially those only opened up in one direction, or ones opened all over the place. (I'm thinking something like one-shot bonus room minigames, or miniboss traps.)

This approach can also create entirely different level types just by creating a second set of "screen objects" as different frames.

The "What's Perlin Noise?" part (feel free to skip if you know about this).

Let's say all the rooms are lined up, right? Object checks above to see if there's a matching color, if so it +1s. To the left will +2, to the right will +4, and to the bottom will +8. Based on that calculation, this "color room" will change itself into a level chunk, and it will set that calculated total to it's "frame." So basically, the level chunks are like frames of a sprite, except they don't animate.

Okay, now back to the action.

Offsetting the levels would change this a bit two ways. First off, you'll have two screens on top/bottom, or on the sides; and you'll need to do two additional checks (+16/+32). This will basically QUADRUPLE the level design output (64 - 1 screens, rather than 16 - 1). Secondly, the level design itself will have to take this into account. Say it's horizontal-offset, now you'll have two ins/outs on each top, and the level design get more "X" influence... leaving out of one bottom-right will now put you into the other screen's "top left" (instead of a "top right").

Finally, the third option is to do ALL EIGHT possible checks, which then factors a (+64/+128) into the mix. AND it means that upper/lower routes must be available on the sides, AND left-right routes will factor into the top and bottom; and level designs would then have to take either or both offset potentials into consideration. Plus, although it would clearly provide the most variation, each potential level would need (256 - 1... that's right, count your Rupees, Link) different screen variations. That's not per game - that's PER LEVEL. That's an effing LOT of work to do, there!

I guess here's the feedback I'm going for:

With a system like this at your disposal, what type of game(s) would you create with it?

Which offset-possibility do you think would give that game the most bang-for-buck?


DISCLAIMER: I am aware that "Perlin Noise" and PGC are usually affiliated with the "Technical" sub-forum, but the level design involved is what I'm seeking feedback about on here.
Logged

zovirl
Level 1
*


Mark Ivey


View Profile WWW
« Reply #1 on: August 25, 2011, 08:43:26 PM »

err....I've read this three times and I still have no idea what you are talking about.

Levels? sublevels? scenes? screens? rooms? chunks? colors? Maybe define your terms? Also, maybe a diagram or an example of a level would help explain.


Logged

Alaskan Runway, a side-scrolling flight sim I'm working on.
Forest, a walking meditation game. (behind the scenes)
www.zovirl.com
baconman
Level 10
*****


Design Guru


View Profile WWW
« Reply #2 on: August 26, 2011, 12:21:46 AM »

err....I've read this three times and I still have no idea what you are talking about.

Levels? sublevels? scenes? screens? rooms? chunks? colors? Maybe define your terms? Also, maybe a diagram or an example of a level would help explain.

That's kinda what I was afraid of. Okay...

So this game engine I'm working on is about combining random level generation with actual level design. Sonic-style platformer levels, Zelda-style overhead levels/maps, urban road systems ala older GTAs, etc. To do this, it builds the game one "screen/scene" (IE: the level chunks - half of those terms you listed basically mean the same thing) at a time in ways that can logically flow together.

These screens start off as randomly-assigned, colored screen-size boxes. These can be any of 6 colors, but coloring is irrelevant, it's just a way of assigning a random 0-5 value. What these boxes do, is a check for every other screen that touches them, and adds a variable for each location (1/2/4/8/16/32/64/128 - like binary code). It does 8 of these checks - two against each side, since some of the levels will have offset screens.

Then based on it's total, it will change to a different "chunk" of level design, based on whatever level of whatever game you're playing. Any time two of these blocks are the same color, the level design will create barriers between the chunks, and whenever they're +/- 3, the "opposite color" so to say, it will simply create a fake barrier - something that can be destroyed or walked through.

Now, what I'm hoping to find a way of doing here is grouping the outcomes mathmatically, based on rotational outcomes. So that, instead of having to hardcode 255 different chunks per level (ouch!), that there's a way I can hardcode just 64 of them instead, and then have them flip horizontally and vertically to fit. So that, for example, an upper-left to lower-right passage is simply a lower-left to upper-right passage turned around or upside down.

...


That example makes me think that, while it's possible to vertically and horizontally flip level chunks to fit, it'd probably be a bad idea to attempt both. I may have to stick to one kind of flipping or the other, on second thought. After all, flipping that both ways wouldn't change it's directional outcome. And since different game types have different directional flow, it might just come down to hard-coding all 255 results (manually flipping some? But then, why bother?).

Keeping the screens all lined up, and doing one check each way would be simple, but it would only give you 15 level chunks that matter. That would probably make for some pretty boring levels, huh? I'm trying for an outcome that gives me right around 64 level chunks. A good variety, but managable to work with, too.
Logged

baconman
Level 10
*****


Design Guru


View Profile WWW
« Reply #3 on: August 26, 2011, 05:45:17 AM »

 Shocked !! EUREKA!!

Okay... I think I know how to solve this thing... instead of doing 8 checks, I'll do the basic 4 checks, but in a way that can compensate for the level offsets:

Left side will check in the upper half
Right side will check in the lower half
Top will check to the right half
Bottom will check to the left half

Then all I have to do, is have the internal level design compensate for that. So if things are offset horizontally, for instance, just put bottom exits on the left side (25% of the way), and top exits likewise on the right! As for the variety in level structure, all I have to do then is create a different "chunk set" for each color variable! So 4 of those will give me 60 level chunks, or 6 of them will give me 90! :D

And if I keep the screens lined up, then I can just center the scrolling points. This also makes it easier to give the levels shape, too. Why didn't I think of that before? DON'T ANSWER THAT.
Logged

zovirl
Level 1
*


Mark Ivey


View Profile WWW
« Reply #4 on: August 26, 2011, 07:44:20 PM »

Glad you found a solution! I have a couple suggtions, but I should check to make sure I understand you before I offer them Smiley

You're talking about building a random level out some manually-created, screen-sized building blocks, right? So you would draw a collection of, say, 20 different "rooms" and then randomly attach those 20 rooms to each other to bulid a complete level. Also you have a scheme for creating either premanent or destroyable barriers between rooms based on whether the neighboring rooms are the same or opposite.

Did I get that right?

Ok here are my suggestions:

1. You asked what games I would use something like this in. It sounds useful for a rouge-like where you want to build random dungeons but you want the rooms themselves to have that hand-crafted quality. It also reminds me of Carcassone (random map but beautiful non-procedural artwork on each tile) and Clue (mostly I'm just thinking of a randomly-generated house made by gluing floorplans together)

2. You mentioned symmetry and the tradeoff of hand-creating the various reflections/rotations of each room vs. complicating the level generation to do the rotation/reflection. If it were me, I would split this into 3 steps: First, make a limited number of rooms (so you have a small set of rooms). Then, a post-processing step automatically computes the various reflections/rotations you want (now you have a bigger set of rooms). Finally, generate random levels using the full set of rooms. This would also let you mark some rooms as "able to use all symmetries" and other rooms could be marked "can't be flipped vertically."

3. If I was going to build random levels by gluing together rooms, I wouldn't use the color scheme you proposed but would instead start by picking a random room. Next I'd randomly pick a neighbor for that from the set of all rooms that logically can be placed next to that room. I'd keep attaching rooms like this until the whole level was complete (like a flood-fill). Sorta like Carcassone. But I probably am not appreciating why you are using the color scheme so this advice probably doesn't apply to your situation.
Logged

Alaskan Runway, a side-scrolling flight sim I'm working on.
Forest, a walking meditation game. (behind the scenes)
www.zovirl.com
baconman
Level 10
*****


Design Guru


View Profile WWW
« Reply #5 on: August 27, 2011, 07:20:24 AM »

Oh no, you're right on the money. Smiley Hand Thumbs Up Right

The only difference is that these groups of rooms are all frames of a sprite with independent collision detection; non-animated. It calculates the "frame" by adding together the checks based on the rooms around it. So a frame/room 9 would be created by colliding with a same-valued room in the "+1" and "+8" positions. In 4-directional terms, (U L R D) that would mean the room is left-to-right-only.

Then, the part about hand-crafting the rooms' design is by taking that into account. That level chunk would be a manually mapped left-to-right passageway, and if it detects that a secret passage is needed, it would then create one on the appropriate border. Wink

Finally, it just occured to me that for every different "color/value" that the randomizer picks, I can associate that with a completely different set of level chunks; something I hadn't considered up to that point. Different levels/games can use the same sort of randomizer, but different sets of level chunks; and by offsetting the initial match detection, I could use that same scheme whether I offset the rooms or not. All that offsetting the room chunks would mean, is that I have to factor that relativity into the prefab level design. So a half-screen offset to the side means that I place "upper" gaps to the right, and "lower" gaps to the left, so they always still connect/disconnect right.

Quote
It sounds useful for a rouge-like where you want to build random dungeons but you want the rooms themselves to have that hand-crafted quality.

Therein is the entire point of this concept. You just won the thread. Wink Bro Fist Right Bro Fist Left Smiley
Logged

gimymblert
Level 10
*****


The archivest master, leader of all documents


View Profile
« Reply #6 on: August 28, 2011, 04:13:00 AM »

http://www.squidi.net/mapmaker/index.php remind me loosely the zelda genertion article there
Logged

LiquidAsh
Level 2
**



View Profile WWW
« Reply #7 on: August 28, 2011, 07:24:08 AM »

It sounds like your tile representation of bits would enable pretty simple bitwise operations for rotations: 90 degree rotation = 2 rotate through carry operations.  This might help you search through <256 hand designed tiles for a match.  I can't think of an elegant way to flip these byte representations. 

If this is too slow, another approach would be to hand design the invariant tiles, and then have a pre-build step create all of the flipped and rotated variations.

Logged

If you found this post useful, you might enjoy Rollaway.
baconman
Level 10
*****


Design Guru


View Profile WWW
« Reply #8 on: August 28, 2011, 01:01:31 PM »

That would work for making tiles. But I'm making prefabricated, level-chunk objects here.

And apparently, not as well as I'd expected. Sorry for lack of commentation, btw; it's just a loosely-thrown-together experiment for the time being, with itty-bitty chunks to make a map, rather than the full-sized levels that actual projects will use.

First off, the randomization is down to 3 "colors", because more resulted in far too many wide-open rooms; and the "secret passages" function isn't implemented yet either. Ideally, every room should barricade itself of the same colored neighbors, and connect to every neighboring room that's a different color. Horizontal-offsets connect via the top right and bottom left, and vertical-offsets connect via the upper left and lower right.

The first problem I think I ran into was the "Test Object"/collision detection, so I changed it so the chunks would begin on frame 15 (everything-full), did the calculation, and then +1'ed the frame afterwards to compensate. It's still not quite right; and not just because of the outer perimeter, which tbh, I'm not particularly worried about right now. The mid-level stuff is what I'm testing with this.

"Vertical w/Parity" is identical to Vertical essentially, but with the level chunk design so that the lower left/upper right is always open. The chunks are all that are different, not the method of generation.

Finally, "Both Ways" was originally a mistake I made when changing between the offsets - before I'd realized what I'd done, I had over half a set of level chunks generated that were offset both directions. I was going to scrap it at first, but it turned out to make very good Sonic-like flow, and could basically generate physically bigger levels with fewer objects. So I implemented that option as well, instead.


The actual level-generating framework will do something like this, except that each "color" of rooms can draw totally different sets of chunks, I just lazily copypasted them in this quick experiment; and would actually be screen-sized objects, instead of the little 64 x 48 things they are here.

But what am I doing wrong here?! This should be simple and straightforward. (Effing programming never is, is it? lol)


EDIT:

http://www.squidi.net/mapmaker/index.php remind me loosely the zelda genertion article there

 Mock Anger ...  Corny Laugh ...  Cheesy

That kind of thing is actually one of the exact outcomes I'm actually going for here, in fact! The only difference would be blasting walls/burning trees/pushing rocks would open up spaces between the screens as well, instead of just passageways within them.
« Last Edit: August 28, 2011, 01:22:53 PM by baconman » Logged

Nix
Guest
« Reply #9 on: August 28, 2011, 01:06:45 PM »

If you're using prefabricated chunks (Spelunky-style), I'm not sure how using perlin noise would make much sense or be beneficial.
Logged
baconman
Level 10
*****


Design Guru


View Profile WWW
« Reply #10 on: August 28, 2011, 02:16:54 PM »

If you're using prefabricated chunks (Spelunky-style), I'm not sure how using perlin noise would make much sense or be beneficial.

Because the chunks are in sets that determine which of the neighboring chunks it should connect or disconnect with. Wink Each set right now contains 15 level design-focused chunks, and it picks whichever one corresponds with different level designs that interconnect them appropriately. You wouldn't want an passage on the side of one screen that walks you straight into a wall (in the neighboring screen), would you?

The Perlin Noise isn't for checking tiles, it's for checking the chunk objects themselves. Unfortunately, since Chunker isn't working right yet, that's kind of what's happening. Sad
Logged

Nix
Guest
« Reply #11 on: August 28, 2011, 03:03:00 PM »

No, I understand that certain chunks should only connect to other certain chunks on certain sides, and I certainly understand perlin noise, as I've used it a number of times for obscure graphical effects in my projects. Maybe you're doing something extremely clever that I'm just not understanding, but I don't get how perlin noise would make any of that easier (or how it would work at all).

Enlighten me.
Logged
baconman
Level 10
*****


Design Guru


View Profile WWW
« Reply #12 on: August 28, 2011, 04:14:27 PM »

Okay. Randomizer gives each level chunk a value between 1 and 3 in that GMK above; and then creates a different "level chunk object" that corresponds with that value. (Okay, "0 and 2," but it's still 3 outcomes for now.) The chunks each contain 16 sprite/layouts, corresponding to possible routes within them. Then PN comes into play, as each chunk runs a check against four neighboring chunks.

For each match, the chunks gain a corresponding value in it's image index.

1 = Up
2 = Left
4 = Right
8 = Down

So the value 0 "red" chunks will check for other reds, which should cause both cases to block one another off. If there's a "red chunk" above it, and nowhere else, it'll give a value of 1, which should set it to frame #1, which would be mapped so that the player can traverse any direction except up. Another red chunk to the left will add 2 more, changing the image index to frame 3, which would then make a passageway chunk that links down and to the right instead.

Checking the frames of the "chunk" sprites would give you a good insight to what I'm getting at, there.

The checking points are offset a little bit from center, so that it can also generate levels where the chunks are offset as well. This way, it can also generate maps where for instance, each row is a half-screen apart from the next... and through an alteration in the level design, the level construction can still take place right.

Code:
Chunk Checker:

         +1
   +-----..-+
+2 .........|
   |........|
   |......... +4
   +-..-----+
     +8

The level design consistency is there for each map type. But I think something's off in the calculation step, because for some reason the level chunk outcome is totally off. Undecided

...
Logged

baconman
Level 10
*****


Design Guru


View Profile WWW
« Reply #13 on: August 28, 2011, 04:29:46 PM »



This first one doesn't look too bad as complete randomness, but it's far from the outcome it should be getting. For instance, the red room at 2, 2 (from the upper left) should detect the room on the right, and change to frame 2, which is open to the right, top, and bottom. Instead, it's on frame 0, which is open in all directions (hence why it looks identical to the green room above it - which is actually place correctly, considering).

That green room on the second row with the treasure? Since it's closed off on all sides but the bottom (IE: frame # 7), it should only appear if there's another green room above and to both sides of it, and clearly that's not the case here.



Here is an example of a map utilizing the vertical offset. The "left checks" occur to the upper left, and the "right checks" occur to the lower right.

The second yellow room down in the second column should detect the other yellows to the side, and thus use frame #6, which is one that creates a pathway top to bottom. But instead, it's on #10, which is top-to-right.



Horizontally-offset calculations appear to be even MORE broken, yet; although it *could* be a matter of the randomization, the worse results appear to be more consistent. And the ones that are offset both ways?

They're COMPLETELY broken. They don't even randomize at all...



I'm gonna make sure I placed the right objects in that one. But if the other layouts' calculations are that far off, there's no reason to think it wouldn't there as well.

EDIT: Yup. That was that one's problem.  Facepalm It still calculates wrong, though:



And I see a chunk-design error too, crap.
« Last Edit: August 28, 2011, 04:42:21 PM by baconman » Logged

baconman
Level 10
*****


Design Guru


View Profile WWW
« Reply #14 on: August 30, 2011, 07:35:49 AM »

Modified the Level Chunker to let me manipulate the chunks, essentially +1/-1 frame commands.

Here's how a (broken) randomized level currently generates:



And here is the same level, with it's calculations corrected:



See how the neighboring chunks with the same color are mutually blocked off? And how it comes out to being a fully cohesive level that can be navigated in?

Here's another "before" of the horizontal offset disasterpiece:



...And it's correctly-recalculated layout:



Notice the totally-filled room to the upper right? It's because there's a red block to it's upper right, lower left, and on both sides. That sort of thing is where the Perlin Noise comes into play. Only the room colors are randomized. After that, the level designs are supposed to be calculated to fit together, like this one.
Logged

LiquidAsh
Level 2
**



View Profile WWW
« Reply #15 on: August 30, 2011, 12:00:41 PM »

I don't get how perlin noise would make any of that easier

I don't think perlin noise sounds necessary here either, but it would be one way to pseudorandomly generate values across a multidimensional level.  Here's another simpler way, that I believe will would work equally well in this application (if I understand it correctly):

// seed random number generator with x position
// generate xRand
// seed random number generator with y position
// generate yRand
// seed random number generator with xRand+yRand
// generate randomColor

Really just white noise rather than perlin noise.
Logged

If you found this post useful, you might enjoy Rollaway.
baconman
Level 10
*****


Design Guru


View Profile WWW
« Reply #16 on: August 30, 2011, 12:39:22 PM »

 Huh? That's a whole lot of randomness. I suppose if everything were about random placement, perhaps that would work. But how could I coincide that with genuine level design? Would it still be as cohesive as the corrected output? (The "complete randomness" that the miscalculated outputs are doing is exactly what I'm trying to not do here!)

Quote from: Reference:

Not totally sure I follow you. Seems like it's just:
RNG (seed) * Xgrid * Ygrid? I might as well be shuffling an array, and hoping the sublevels just "connect by magic" or something. o.O

About the only other thing I can think of, along those lines, is the checkerboard approach: make the "black squares" an array of open-in-all-directions designs, and the "red/white squares" a second array of open-in-certain-directions ones, and then overflow those a bit to coincidentally block it's neighbors.

Not sure if that would also work with the level-offsetting, however.

Or are you saying check the grid positions directly, instead of relatively? (But... isn't the whole point to relative checking...?)


Not totally following, I guess.


EDIT: OHH! I think I know what you're getting at, now - it's basically doing the same steps backwards, huh? Randomly coinciding the 0-15 outputs between the rooms first (one neighbor affects the other), and that leading to the 16 output groups of level designs, each open in their appropriate directions? And then randomly chosen from however many there may be... did I get that right?
Logged

baconman
Level 10
*****


Design Guru


View Profile WWW
« Reply #17 on: August 30, 2011, 02:46:55 PM »

Just to get more on the same page, there's three things I'm trying to make this level chunker to create:

1. A randomly-arranged, but systematically-calculated method of creating real, gamelike maps with actual level design involved; so that everywhere a player is supposed to be capable of going, they can. And if they can't, it's blanked out so no other assets are placed there. It's not just random stuff all over the place, where the terrain is completely free-roam. It's also not Rogue, where every "room" pathways to every other neighboring room.

I'm aware that Rogue does have dead-ends, but it's never because pathways aren't there - it's only because the room itself gets blacked out.

2. A way of arranging these level chunks so that you never encounter two of the same kind in a row. Granted, this prototype does a terrible job of making an example of that, since the different colors are all copypasted, but the actual engine will have totally different sets for each "color," that's why "same color" rooms are calculated and designed to close off from one another. Wink (Or perhaps in some certain projects, even effectively merge and conjoin together differently!)

Some of these "exits" from one chunk to another will likely also have action-influencing widgets that affect things that happen in the following chunk. They aren't actually intended to end up being different colors; just different sets.

3. Be flexible enough to work with a variety of gameplay genres and concepts. There's a decent-sized number of PGC "game reimaginings" that I would like to use this as a framework for creating, it's not like it's just one project. In fact, if it goes well, it's actually meant to tie into my bigger long-term, siggy-linked project; basically a "game about gaming as a whole," or as close to that as I can get in 2D. Wink

Some of the various influences I hope to capture in these projects includes Zelda, Demon's Souls, Metroid, Sonic, MegaMan, Sinistar, Pac-Man/Rally X, Castlevania, Duke Nukem, Alien Syndrome, Ikari Warriors, Samurai Warriors (yes, a 2D SamWa!!)... oh, the list could go on forever.

But basically from this point, any cool PGC project is just a little level chunk design, some asset creation, and a bit of polish away. It's a HUGE leap forward, personally. That's why I'm so pumped! (And frustrated, considering how something like this should be so straightforward, and yet... how is it screwed up?! This is what programming-from-scratch does do me, too.)
« Last Edit: August 30, 2011, 02:57:54 PM by baconman » Logged

baconman
Level 10
*****


Design Guru


View Profile WWW
« Reply #18 on: September 03, 2011, 10:05:08 AM »

 Evil IT'S ALIIIIIVE!!! Evil

A couple users at GMC found the two things I was doing wrong - misunderstanding the use of the "Check Object," and making sure the calculation step was definitively after the randomization (before, I had them both under the "Create" event).

Okay, I didn't bother to fix up the double-offset, because it suffered from a couple of design layout errors anyways, and because now I know the experiment is otherwise successful. Check this shit out. :D

EDIT: Now EXE'd. Pics momentarily.
« Last Edit: September 03, 2011, 10:10:14 AM by baconman » Logged

gimymblert
Level 10
*****


The archivest master, leader of all documents


View Profile
« Reply #19 on: September 03, 2011, 10:08:33 AM »

pic or it didn't happen
Logged

Pages: [1] 2
Print
Jump to:  

Theme orange-lt created by panic