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

Login with username, password and session length

 
Advanced search

1057370 Posts in 42956 Topics- by 34890 Members - Latest Member: AgentBlue0

October 25, 2014, 03:33:48 PM
TIGSource ForumsDeveloperTutorialsBraving Procedural Generation
Pages: [1] 2 3 ... 23
Print
Author Topic: Braving Procedural Generation  (Read 159290 times)
ChevyRay
Guest
« on: March 10, 2009, 08:43:01 PM »

I've written yet another article Smiley this one is less technical, and contains an ActionScript source for my previous cave-generation algorithm.

Latest Article



This time, I featured a lot of the source files and images posted here. Keep showing your stuff, guys Smiley this is a great topic so far!



----------



New tutorial/experimentation is up. Smiley

This time it's creating heightmaps and applying mathematical curves to optimize them!





----------



I wrote a very large article today documenting my first experiences with procedurally generated content for games, and thought I'd share it here. While it's not technically a tutorial, I explain a lot of the methods I used and how I went about getting my fingernails dug into this world of game development that I've been sidelining for so long.

http://properundead.com/2009/03/cave-generator.html

Basically, I wrote this to show how procedural programming can be broken down and understood, even by an amateur programmer (aka. me) using GM. I think a lot of indie developers life myself daydream games with these kinds of systems, but get intimidated by worlds like "procedural" and "algorithm", and I wanted to tame the concepts down a bit.

I tried making the articles as rhetoric as they are technical, so they can be understood from both frames of mind Smiley and I think a lot can be learned just from reading into another person's learning experience.

So I'm sharing mine with you.



« Last Edit: August 12, 2011, 12:23:08 PM by ChevyRay » Logged
Lynx
Level 5
*****


Upstart Feline Miscreant


View Profile WWW Email
« Reply #1 on: March 10, 2009, 11:05:06 PM »

Great job!  Fascinating to see how you went about iterating your cave generation system.
Logged

Currently developing dot sneak - a minimalist stealth game
Lynx
Level 5
*****


Upstart Feline Miscreant


View Profile WWW Email
« Reply #2 on: March 10, 2009, 11:27:44 PM »

Some additional thoughts:

* It'd be useful to identify caves somehow as distinct areas.

* Caves that are far from the path might be candidates for 'grand treasures' - treasure chests in the center, with guardian monsters

* Following the A* path, you could place guardian monsters at the ends of those caves

Let's say the entrance is always in 'cave 1'.  Then you expand from there and identify all other squares with at least 3 open squares adjacent as also 'cave 1'.

Squares with only 2 open squares are considered to be tunnels.  Follow and mark them so you don't visit them again, but don't assign them to caves.

Keep a running count of how many cells each cave has.  This lets you decide how many monsters a cave needs to feel 'populated'.  Caves of low size are just swellings within tunnels and can be disregarded.

This algorithm might need some tweaking since it'd count that big area in the example where the red square is as one big cave, but there's a 2-wide tunnel.

Totally untested idea, inspired by your procedural map generation article. Smiley
Logged

Currently developing dot sneak - a minimalist stealth game
Eclipse
Level 10
*****


0xDEADC0DE


View Profile WWW Email
« Reply #3 on: March 11, 2009, 03:21:12 AM »

very nice article Chevy, congrats and tophats to ya  Gentleman
Logged

<Powergloved_Andy> I once fapped to Dora the Explorer
Ataraxia
Level 0
**


View Profile Email
« Reply #4 on: March 11, 2009, 08:01:02 AM »

Awesome! Thanks a lot for this, I've been wondering how to do this kind of thing for a little while!
Logged
george
Level 7
**



View Profile Email
« Reply #5 on: March 11, 2009, 11:19:45 AM »

Great looking caves, and I like this 'rhetorical' style!  Beer!
Logged
William Laub
Level 10
*****


Gold Cray


View Profile WWW Email
« Reply #6 on: March 11, 2009, 11:56:33 AM »

This is very nice. I've spent months working on algorithms with similar ideas but never managed to come up with something so simple nor so effective.

Edit: A quick python implementation of your algorithm made this in a matter of seconds. It's already much closer a decent 2d platformer cave than anything of my algorithms, and it runs hundreds of times more quickly.

« Last Edit: March 11, 2009, 01:24:00 PM by Gold Cray » Logged
ChevyRay
Guest
« Reply #7 on: March 11, 2009, 02:08:27 PM »

Nice, cold cray! :D

Yeah, my favorite thing about the cave algorithm was how fast it was. Even if I add a recursive check to keep it from being too small, it still finds an appropriate size and creates it within a second.
« Last Edit: March 11, 2009, 04:55:03 PM by ChevyRay » Logged
Kneecaps
Level 3
***



View Profile Email
« Reply #8 on: March 11, 2009, 05:36:11 PM »

Awesome!  I've never been able to completely figure out PG, and you made the explanation really simple.  After following the terrain thingy, I duplicated the method in Flash.  Click to generate a new map.  It takes about a second to generate for me due to the size of the map (and because I could probably make some more optimizations).

Thanks for the article!
Logged
ChevyRay
Guest
« Reply #9 on: March 11, 2009, 05:42:17 PM »

Well, procedural generation is something that can be approached in countless different ways, all I did was show a couple particular methods that I used and tried to explain them in a simple way to show people that PG is a fun game to play Smiley

I'm really glad to see people learning and benefiting from this, though!

EDIT: That works very nicely, Kneecaps.
Logged
ஒழுக்கின்மை
Level 10
*****


Also known as रिंकू.

RinkuHero
View Profile WWW Email
« Reply #10 on: March 11, 2009, 11:16:57 PM »

It takes me less than a second, it seems to generate as fast as I can click. Maybe my CPU is just better at it or something. Really nice though. Any chance you could let us see the source code?
Logged

Hayden Scott-Baron
Level 10
*****


also known as 'Dock'


View Profile WWW Email
« Reply #11 on: March 12, 2009, 12:56:19 AM »

Excellent article, thanks for sharing!

'Random caves' are on my shortlist for techniques I'd like to develop. I suspect I'll give them a go at some point after I ship the game I'm working on.
Logged

Mipe
Level 10
*****


Migrating to imagination.


View Profile
« Reply #12 on: March 12, 2009, 01:30:57 AM »

The site seems unresponsive.  Undecided
Logged
ChevyRay
Guest
« Reply #13 on: March 12, 2009, 01:41:14 AM »

Server's down right now Sad sorry guys. I'll post here when it comes back up.
Logged
ChevyRay
Guest
« Reply #14 on: March 12, 2009, 03:47:00 AM »

Okay, the site is working again!
Logged
Kneecaps
Level 3
***



View Profile Email
« Reply #15 on: March 12, 2009, 04:53:18 AM »

It takes me less than a second, it seems to generate as fast as I can click. Maybe my CPU is just better at it or something. Really nice though. Any chance you could let us see the source code?
Sure!  I'll need to make it user-friendly though, which is something I could work on during school today.
Logged
Kneecaps
Level 3
***



View Profile Email
« Reply #16 on: March 12, 2009, 12:18:19 PM »

Yay double post!

Here's my code.  I'm sure there's better ways to organize it and such, but it worked for me, and that's all that matters.

Code:
package 
{
import flash.display.*;
import flash.events.MouseEvent;

/**
* ...
* @author Kneecaps
*/
public class Map1 extends Sprite
{
private var map:Array;
private var i:int;
private var j:int;
private var image:Bitmap;
private var imageData:BitmapData;
public function Map1()
{
//Start out with a map displayed
createMap();
stage.addEventListener(MouseEvent.CLICK, onMouseClick);
}
//Generate a new map when the user clicks the mouse
private function onMouseClick(e:MouseEvent):void {
stage.removeChild(image);
createMap();
}
private function createMap():void {
//Create an 8x8 map
map = new Array(8);
for (i = 0; i < 8; i++) {
map[i] = new Array(8);
}
//Randomly fill the map with land (1) and water (0)
//I use j as the y-value and i as the x-value in my code normally
for (j = 0; j < map.length; j++) {
for (i = 0; i < map[0].length; i++) {
if (Math.random() < 0.4) map[j][i] = 1;
else map[j][i] = 0;
}
}
//Make the map bigger until it is bigger than 500 pixels.  Since
//the dimensions double each time the map is refined, the final
//size is 512 pixels.
while(map.length<500){
map = refineMap(map);
}
//Make a bitmap the size of the map
imageData = new BitmapData(map[0].length, map.length);
//Draw the map
for (j = 0; j < map.length; j++) {
for (i = 0; i < map[0].length; i++) {
//If the current cell is land
if (map[j][i]) {
//x and y values for the cells bordering the current cell
var left:int = i - 1;
var right:int = i + 1;
var up:int = j - 1;
var down:int = j + 1;
//Ignore cells out of the map's boundaries
if (left < 0) left = i;
else if (right > map[0].length-1) right = i;
if (up < 0) up = j;
else if (down > map.length - 1) down = j;
//If one of the bordering cells is water, make this cell dark green
if (!map[up][i] || !map[down][i] || !map[j][left] || !map[j][right]) imageData.setPixel(i, j, 0x003300);
//Else, make the cell light green
else imageData.setPixel(i, j, 0x009933);
}
//Make the water blue
else imageData.setPixel(i, j, 0xAEEBFF);
}
}
image = new Bitmap(imageData);
stage.addChild(image);
}
//Doubles the map's size while making it more "complex"
private function refineMap(a:Array):Array {
//Make a new array (na) twice the size of the initial array
var na:Array = new Array(a.length * 2);
for (i = 0; i < na.length; i++) {
na[i] = new Array(a[0].length * 2);
}
/*Copy the values to the new array, but twice as big.
* 01            0011
* 00   becomes  0011
*               0000
*               0000
*/
for (j = 0; j < a.length; j++) {
for (i = 0; i < a[0].length; i++) {
na[j * 2][i * 2] = a[j][i];
na[j * 2 + 1][i * 2] = a[j][i];
na[j * 2 + 1][i * 2 + 1] = a[j][i];
na[j * 2][i * 2 + 1] = a[j][i];
}
}
/* We want two copies of the bigger version.  Cells will be read off
* the first array (a), and the new cell will be written to the new
* array.  Using only one array for reading/writing can lead to problems.
*/
a = na;
for (j = 1; j < na.length-1; j++) {
for (i = 1; i < na[0].length - 1; i++) {
//The number of bordering cells (including the first cell) that are land.
var landSpaces:Number = 0;
//x and y values for the cells bordering the current cell
var left:int = i - 1;
var right:int = i + 1;
var up:int = j - 1;
var down:int = j + 1;
//If values were out of bounds, wrap them around the map to the other side
if (left < 0) left = na[0].length-1;
else if (right > na[0].length) right = 0;
if (up < 0) up = na.length-1;
else if (down > na.length) down = 0;
//Find the total amount of bordering land cells (out of 9)
if (a[up][left]) landSpaces++;
if (a[j][left]) landSpaces++;
if (a[down][left]) landSpaces++;
if (a[up][i]) landSpaces++;
if (a[j][i]) landSpaces++;
if (a[down][i]) landSpaces++;
if (a[up][right]) landSpaces++;
if (a[j][right]) landSpaces++;
if (a[down][right]) landSpaces++;
//Randomly generate a cell based on how many land cells are bordering it.
//A cell with 3 bordering land cells has a 3/9 chance of becoming a land cell.
if (Math.random() < landSpaces / 9) na[j][i] = 1;
else na[j][i] = 0;
}
}
return na;
}
}

}

If my commenting makes no sense, let me know.

FUN EDIT TIME:
So, I tried adding more stuff to my maps, and it hasn't been too friendly to me.  Specifically, rivers.  I can get a river line to generate fine, like so:



However, whenever I try to expand that river (like one would expand a selection in Photoshop), I get this:



Here's my expand function.  It takes in the map that is going to be changed, the value of the cells to search for (water is 2), the number of times to expand, and the chance that any particular cell will turn its neighbors into its value.  With that number at 1, it should theoretically just do a normal "expand" thingy, but that fills the whole screen at one.  The screenshot is when that value is at 0.7.  If you could help me at all with this, I would very much appreciate it.

Code:
private function expandTerrain(a:Array, v:int, n:int, chance:Number=1):Array {
var na:Array = a;
for (k = 0; k < n;k++){
for (i = 0; i < a[0].length; i++) {
for (j = 0; j < a.length; j++) {
if (a[j][i] == v&&Math.random()<chance) {
if (j - 1 > 0) na[j - 1][i] = v;
if (j + 1 < 127) na[j + 1][i] = v;
if (i - 1 > 0) na[j][i - 1] = v;
if (i + 1 < 127) na[j][i + 1] = v;
}
}
}
}
return na;
}
« Last Edit: March 13, 2009, 12:52:53 PM by Kneecaps » Logged
ChevyRay
Guest
« Reply #17 on: March 13, 2009, 02:02:39 PM »

I usually do mountain generation before rivers, and then create glacier-points on top of those mountains. After that, I just run rivers down from the mountains, moving in the general direction of the ocean, and ending them when they reach it.
Logged
Kneecaps
Level 3
***



View Profile Email
« Reply #18 on: March 13, 2009, 02:17:33 PM »

I usually do mountain generation before rivers, and then create glacier-points on top of those mountains. After that, I just run rivers down from the mountains, moving in the general direction of the ocean, and ending them when they reach it.
I'm not too concerned about making the rivers flow realistically just yet; I'm more concerned about  making the river 3 pixels wide.  Also, for what I have in mind with the generation, I won't be needing mountains (yet).

So one again, if someone has a function that can do this:
Code:
00000        00000
00000        00110
00110  --->  01111
00100        01110
00000        00100
I would be so happy.  And I would give you sexual favors.
Logged
Cthulhu32
Level 6
*


Brawp


View Profile WWW Email
« Reply #19 on: March 13, 2009, 03:01:57 PM »

Seemed like a pretty swanky tutorial so I decided to give it a go in Pygame :D Took me about an hour with getting the algorithm small. I also started with using 8 corner neighbors + self when determining whether to become a land or island, but quickly learned that 4 corners (up, down, left, right) + self is a much better alternative.

If you want to play around with the source, try modifying LAND_COUNT (1-15), LAND_RATIO, and SEA_RATIO. LAND_COUNT is the initial how many land blocks will we generate off of, and it randomly chooses to be a sea or land based on neighbors.



And of course full source Smiley
Code:
import pygame, random
from pygame.locals import *

SCREEN_WIDTH = 512 # For now this must be 512, 1024, 1536, or 2048
SCREEN_HEIGHT = 512 # For now this must be 512, 1024, 1536, or 2048
LAND_COUNT = 5 # how many initial islands can we spawn off of?
LAND_RATIO = 9  # 8/5 chance of having land vs. sea
SEA_RATIO = 5   #   we can change this to any ratio
LAND1_RGBA = (132,176,138,255)
LAND2_RGBA = (119,168,126,255)
SEA1_RGBA = (75,162,255,255)
SEA2_RGBA = (62,142,255,255)
BORDER_RGBA = (80,124,87,255)

class PLand:
def __init__(self, landLayer):
self.landLayer = landLayer
self.largeGrid = []
self.mediumGrid = []
self.smallGrid = []
self.tinyGrid = []
for i in xrange(16): # 4*4
self.largeGrid.append(0)
for i in xrange(256): # 16*16
self.mediumGrid.append(0)
for i in xrange(4096): # 64*64
self.smallGrid.append(0)
for i in xrange(65536): # 256*256
self.tinyGrid.append(0)
self.state = 'largeGrid' # always start at large grid for this implementation
self.tileIdx = 0 # which tile idx are we at?
self.neighbors = [(0,-1),(-1,0),(0,0),(1,0),(0,1)] # check 4 neighbors (up,down,left,right) + self

def update(self):
while self.state != 'done':
if self.state == 'largeGrid':
print 'Creating Large Grid'
randGrid = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
width = SCREEN_WIDTH/4
height = SCREEN_HEIGHT/4
for i in xrange(LAND_COUNT): # fill in with defined land count
r = random.randint(0, len(randGrid)-1)
idx = randGrid.pop(r)
self.largeGrid[idx] = 1
for i in xrange(len(randGrid)): # fill the other half with water
idx = randGrid.pop(0)
self.largeGrid[idx] = 2
print 'Moving to Medium Grid'
self.state = 'mediumGrid'
elif self.state == 'mediumGrid':
if self.updateGrid(256, 16, 4, self.mediumGrid, self.largeGrid) == True:
print 'Moving to Small Grid'
self.state = 'smallGrid'
elif self.state == 'smallGrid':
if self.updateGrid(4096, 64, 16, self.smallGrid, self.mediumGrid) == True:
print 'Moving to Tiny Grid'
self.state = 'tinyGrid'
elif self.state == 'tinyGrid':
if self.updateGrid(65536, 256, 64, self.tinyGrid, self.smallGrid) == True:
print 'Drawing Grid'
self.state = 'drawGrid'
elif self.state == 'drawGrid':
width = SCREEN_WIDTH/256
height = SCREEN_HEIGHT/256
for idx in xrange(65536):
x = idx % 256
y = idx / 256
if self.tinyGrid[idx] == 1: # Is it land?
isBorder = False
for nx,ny in self.neighbors:
nx += int(x) # our current difference in grids (64/16 = 4, 16/4 = 4)
ny += int(y)
if nx >= 0 and ny >= 0 and nx < 256 and ny < 256:
if self.tinyGrid[ny*256+nx] == 2: # draw this as darker and break
pygame.draw.rect(self.landLayer, BORDER_RGBA, Rect(x*width,y*height,width,height))
isBorder = True
break
if isBorder == False:
if ( random.randint(0,1) == 1 ): #50% chance of coloring different
pygame.draw.rect(self.landLayer, LAND1_RGBA, Rect(x*width,y*height,width,height))
else:
pygame.draw.rect(self.landLayer, LAND2_RGBA, Rect(x*width,y*height,width,height))
else: # is it sea?
if ( random.randint(0,1) == 1 ): #50% chance of coloring different
pygame.draw.rect(self.landLayer, SEA1_RGBA, Rect(x*width,y*height,width,height))
else:
pygame.draw.rect(self.landLayer, SEA2_RGBA, Rect(x*width,y*height,width,height))
print 'Done!'
self.state = 'done'

def updateGrid(self, maxSize, tileSize, oldSize, newGrid, oldGrid):
if self.tileIdx < maxSize:
x = self.tileIdx % tileSize
y = self.tileIdx / tileSize
neighborList = [] # Check our neighbors
for nx,ny in self.neighbors:
nx += int(x/4) # our current difference in grids (256/4 = 64, 64/4 = 16, 16/4 = 4)
ny += int(y/4)
if nx >= 0 and ny >= 0 and nx < oldSize and ny < oldSize:
neighborList.append(oldGrid[ny*oldSize+nx])
waterChance = 0
landChance = 0
for neighbor in neighborList:
if neighbor == 1: # land!
landChance += LAND_RATIO
elif neighbor == 2: # water!
waterChance += SEA_RATIO
r = random.randint(0, landChance+waterChance-1)
width = SCREEN_WIDTH/tileSize
height = SCREEN_HEIGHT/tileSize
if r < landChance:
newGrid[self.tileIdx] = 1 # land
else:
newGrid[self.tileIdx] = 2 # water
self.tileIdx += 1
return False
else:
self.tileIdx = 0
return True

def draw(self,screen):
screen.blit(self.landLayer, (0,0))

def main():
"""Procedural Generation - Luke Arntson '09
"""
pygame.init()
screen = pygame.display.set_mode((SCREEN_WIDTH, SCREEN_HEIGHT))
pygame.display.set_caption('Land Generation')
pygame.mouse.set_visible(0)
background = pygame.Surface(screen.get_size())
background = background.convert()
background.fill((0, 0, 0))
landLayer = pygame.Surface(screen.get_size())
landLayer = landLayer.convert_alpha()
landLayer.fill((0, 0, 0, 0))
mLand = PLand(landLayer)
screen.blit(background, (0, 0))
pygame.display.flip()
print '-- Creating Map(%i,%i) with %i Land Initializer(s), and a Water-to-Sea average of %i/%i --\n'%(SCREEN_WIDTH,SCREEN_HEIGHT,LAND_COUNT,LAND_RATIO,SEA_RATIO)
clock = pygame.time.Clock()
while 1:
clock.tick(60)
for event in pygame.event.get():
if event.type == QUIT:
return
elif event.type == KEYDOWN and event.key == K_ESCAPE:
return
mLand.update()
screen.blit(background, (0, 0))
mLand.draw(screen)
pygame.display.flip()

if __name__ == '__main__': main()
Logged

Pages: [1] 2 3 ... 23
Print
Jump to:  

Theme orange-lt created by panic