ChevyRay
Guest
|
|
« on: March 10, 2009, 08:43:01 PM » |
|
I've written yet another article 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 this is a great topic so far! ---------- New tutorial/experimentation is up. 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.htmlBasically, 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 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
|
|
« 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
|
|
« 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.
|
|
|
Logged
|
Currently developing dot sneak - a minimalist stealth game
|
|
|
Eclipse
|
|
« Reply #3 on: March 11, 2009, 03:21:12 AM » |
|
very nice article Chevy, congrats and tophats to ya
|
|
|
Logged
|
<Powergloved_Andy> I once fapped to Dora the Explorer
|
|
|
Ataraxia
|
|
« 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
|
|
« Reply #5 on: March 11, 2009, 11:19:45 AM » |
|
Great looking caves, and I like this 'rhetorical' style!
|
|
|
Logged
|
|
|
|
Gold Cray
|
|
« 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
|
|
« 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 I'm really glad to see people learning and benefiting from this, though! EDIT: That works very nicely, Kneecaps.
|
|
|
Logged
|
|
|
|
ஒழுக்கின்மை (Paul Eres)
|
|
« 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
|
|
« 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
|
|
« Reply #12 on: March 12, 2009, 01:30:57 AM » |
|
The site seems unresponsive.
|
|
|
Logged
|
|
|
|
ChevyRay
Guest
|
|
« Reply #13 on: March 12, 2009, 01:41:14 AM » |
|
Server's down right now 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
|
|
« 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
|
|
« 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. 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. 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
|
|
« 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: 00000 00000 00000 00110 00110 ---> 01111 00100 01110 00000 00100
I would be so happy. And I would give you sexual favors.
|
|
|
Logged
|
|
|
|
Cthulhu32
|
|
« 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 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
|
|
|
|
|