Temple of The Roguelike Forums
Development => Programming => Topic started by: UltimaRatioRegum on November 17, 2011, 12:08:23 AM
-
So, I've spent the past little while working on world generation (http://www.ultimaratioregum.co.uk/game/2011/11/15/cartography-in-the-land-of-ultima-ratio-regum/). I thought I'd just throw in a quick screenshot of what the world map looks like at the moment (cross-posted on the Doryen forum, but I know a lot of people are on here!)
(http://www.ultimaratioregum.co.uk/game/files/2011/11/World-map-300x300.png)
The full version can be seen at http://www.ultimaratioregum.co.uk/game/files/2011/11/World-map.png (http://www.ultimaratioregum.co.uk/game/files/2011/11/World-map.png)
Each square on the world map is 200x200 squares of the actual map the player walks around on. The world map first creatures two or three continents, then randomises their borders a little bit, which sometimes results in the continents joining back up. Then it spreads out climates and biomes according to how high or low on the map it is. After that, forests are added in a density according to the climate; there are few 'forest' squares in deserts (ie oases) but a huge number in tropical areas. Volcanic islands are then thrown in, followed by valleys, mountain ranges, and rivers flowing out of the mountain ranges to the ocean, lakes, or valleys. What does everyone think? Now I just need to get cities, territories, and things like dungeons/caves/forts etc spawning...
-
This is extremely cool! I'll echo the "complaint" in the comments that the biomes are a bit too "horizontal," but it still looks great.
Just a general question since I haven't heard of this project before: How do you like developing with Python? Anything in particular you've run into that would make you want to switch to another language?
-
Looks gorgeous.
Random train of thought: model the sea floor? :)
Would be cool as hell to have ancient underwater civilizations hidden far deep beneath the surface.
Maybe they can be visited by using a submarine vehicle.
-
This is extremely cool! I'll echo the "complaint" in the comments that the biomes are a bit too "horizontal," but it still looks great.
Just a general question since I haven't heard of this project before: How do you like developing with Python? Anything in particular you've run into that would make you want to switch to another language?
Thanks a ton! Yeah, I think I'm going to try and change that a little bit. Shouldn't take too long, actually.
I'm really enjoying using Python. Having never programmed before, it's hugely intuitive, and seems to have the facility for pretty much everything I need. Memory issues did come up, but I think I've sorted with them all now. There's no way I'd switch and learn another language now! :)
Looks gorgeous.
Random train of thought: model the sea floor? :)
Would be cool as hell to have ancient underwater civilizations hidden far deep beneath the surface.
Maybe they can be visited by using a submarine vehicle.
Wow, cheers!
That IS an interesting idea. I'm not yet sure how I'm going to handle underwater, if at all. I love the idea of underwater civilizations, though. I might have water-breathing as an option, but it would be for lone adventuring. Ruins might be able to spawn on the coast soon, though, which I think could look quite nice.
-
You mentioned the size is 200x200.
Is this the ideal size for an over-world map? At what threshold would the player begin to feel that the map is too large?
-
You mentioned the size is 200x200.
Is this the ideal size for an over-world map? At what threshold would the player begin to feel that the map is too large?
Yeah - each square of the 200x200 world map is 200x200 of map the player can walk around on, so it's 40,000 x 40,000 in total. I don't think there's any way to pick a size that applies to all roguelikes - mine has an emphasis on empires, strategy, and armies, and therefore it needs to be large. I don't think a roguelike where you don't pick up any allies, or can change alliances, territory, etc, would need to be anywhere near that large :). As for too large... I don't know. I think people would always want bigger maps with more in them, but I can only speak for myself.
-
Nice man. Nice. I have nothing really to add but compliments.
EDIT: Turns out I do have something to add. I have checked out your site and see you are going for your PhD. I have a doctorate and I have this piece of advice to give to all students of all levels. It's a grind. It's a marathon. NOT A SPRINT. Just like developing a roguelike. It's a haul. You might not have shit to show for yourself after years of work. And in the end you might create something that only a few nerds care about. Just like developing a roguelike. And in the end your work might not transfer into professional success. But in the end the achievement cannot be taken from you. You can look in the mirror and say, "I did something." Just like developing a roguelike. :-)
-
Cheers!
Also, thanks a ton for the advice. I'm trying to gather differing views on pursuing a doctorate and 'keeping going' through the entire process. URR is definitely going to make me longer than the thesis, actually. I wholly expect to be working on it in three years time once I'm searching for postdocs and things like that. However, in terms of both thesis and roguelike, I know I'm creating something only a few nerds care about! :)
-
It's only worth it if you have an internal drive to do it. You'll likely get very little monetary compensation or adulation. That's been my experience. I'd be further ahead professionally if I'd just gotten a job at Wal-Mart and worked my way up. But I wouldn't have felt right inside.
-
Yeah - each square of the 200x200 world map is 200x200 of map the player can walk around on, so it's 40,000 x 40,000 in total. I don't think there's any way to pick a size that applies to all roguelikes - mine has an emphasis on empires, strategy, and armies, and therefore it needs to be large.
Then again, if you look at it another way, taking the individual squares that people walk around on as (say) 1x1 meter, what you've got there are not "continents" -- they're a few islands on a map whose breadth is 40 kilometers. There are a lot of things you can do with 40 by 40 kilometers, but keep a sense of scale about the distances between villages, etc.
-
Yeah - each square of the 200x200 world map is 200x200 of map the player can walk around on, so it's 40,000 x 40,000 in total. I don't think there's any way to pick a size that applies to all roguelikes - mine has an emphasis on empires, strategy, and armies, and therefore it needs to be large.
Then again, if you look at it another way, taking the individual squares that people walk around on as (say) 1x1 meter, what you've got there are not "continents" -- they're a few islands on a map whose breadth is 40 kilometers. There are a lot of things you can do with 40 by 40 kilometers, but keep a sense of scale about the distances between villages, etc.
At 1x1 meter, that's true, but as with most roguelikes, the 'size' of a square is variable. One square holds a wolf or a Titan (or, to use something 'wider', a mammoth or behemoth) without any difficulty. So that's very true, but by another definition of a square it could be 400 kilometres! You're totally right about keeping track of the scale, nevertheless, but I think it's practically above 40km. Also, I may end up enlarging the world map a little, as that'll have minimal effect on game speed or anything else, but we'll see...
-
You might not have shit to show for yourself after years of work. And in the end you might create something that only a few nerds care about. Just like developing a roguelike.
When I started developing my roguelike, I went in with the mindset that I was developing it for one person: Myself. I wanted a game I could play, and if by chance other people liked it then cool :)
Great advice overall!
-
When I started developing my roguelike, I went in with the mindset that I was developing it for one person: Myself. I wanted a game I could play, and if by chance other people liked it then cool :)
Great advice overall!
That's pretty much my initial mindset :). I've got a ton of things I've always wanted in a game, and I plan to make those. It's just an added (and remarkable) benefit that others seem interested!
-
I like the custom ASCII-esque tiles you're using. As a fellow Python RL developer, I'm curious to know what library you're using to display both standard ASCII characters and custom characters side-by-side.
-
I like the custom ASCII-esque tiles you're using. As a fellow Python RL developer, I'm curious to know what library you're using to display both standard ASCII characters and custom characters side-by-side.
Mmh, I think it's libtcod. ;D
-
I like the custom ASCII-esque tiles you're using. As a fellow Python RL developer, I'm curious to know what library you're using to display both standard ASCII characters and custom characters side-by-side.
Mmh, I think it's libtcod. ;D
I made all of the custom tiles myself, and also actually changed quite a bit of the default fonts, but I am indeed using libtcod :)
-
Would you be willing to share more details of how you're doing the world map generation?
I've been working on procedurally (rather than randomly) generating worlds, given a seed value, so that I can zoom in and generate the areas needed as the player enters them, instead of having to spend a bunch of time at the beginning generating a world randomly.
I'm generating the base terrain using fractional browning motion running on top of a procedural perlin noise function that feeds a seed and a set of coordinates through a fast murmur hash function to generate values. Once I've drilled down to the resolution I want, I pull out a square of terrain, plus some buffer area on the edges, and run a hydraulic erosion loop on it for a while. It seems to work pretty well, but....
Rivers are troublesome. I can get them to form if I run many many iterations that evaporate and deposit small amounts of water, but that takes quite a long time. Pleasant but fast results are achieved if I dump a whole bunch of water in relatively few iterations, but rivers don't form that way....
I haven't even begun to think about biomes yet.......
How are you running your rivers? What methods are you using to form your biomes? Would any of these methods be usable with as-needed procedural generation rather than pre-generated random worlds?
-
This is great, I love procedural/random map generation, but it's so darn difficult! Is there a place for best practices having to do with such things? I know of the procedural content generation WIKI, but that's about algorithms and not code. Perhaps it's time to start a page on roguebasin...
EDIT:
This represents my solution to making level generation algorithms that can be used flexibly. I'm interested in peoples opinions, and I'd really love to start some kind of library project, although that might be a little ambitious.
http://roguebasin.roguelikedevelopment.org/index.php/Designing_Flexible,_Reusable_Algorithms (http://roguebasin.roguelikedevelopment.org/index.php/Designing_Flexible,_Reusable_Algorithms)
-
I've thought about starting a blog to post code snippets and screenies as I work on stuff...
Some of the code is too long to be spamming up these forums with. <_<
Here's a great article on polygonal map generation: http://www-cs-students.stanford.edu/~amitp/game-programming/polygon-map-generation/
I don't know why I didn't think of using a table like that to figure out biomes myself, lol....
-
Here's a pretty good paper on river generation. Probably wouldn't work for a truly procedural world though...
http://www.cs.sjsu.edu/~teoh/research/papers/CGVR08_terrain.pdf
-
Would you be willing to share more details of how you're doing the world map generation?
I've been working on procedurally (rather than randomly) generating worlds, given a seed value, so that I can zoom in and generate the areas needed as the player enters them, instead of having to spend a bunch of time at the beginning generating a world randomly.
I'm generating the base terrain using fractional browning motion running on top of a procedural perlin noise function that feeds a seed and a set of coordinates through a fast murmur hash function to generate values. Once I've drilled down to the resolution I want, I pull out a square of terrain, plus some buffer area on the edges, and run a hydraulic erosion loop on it for a while. It seems to work pretty well, but....
Rivers are troublesome. I can get them to form if I run many many iterations that evaporate and deposit small amounts of water, but that takes quite a long time. Pleasant but fast results are achieved if I dump a whole bunch of water in relatively few iterations, but rivers don't form that way....
I haven't even begun to think about biomes yet.......
How are you running your rivers? What methods are you using to form your biomes? Would any of these methods be usable with as-needed procedural generation rather than pre-generated random worlds?
Certainly :).
Ah, that's a nice idea. I've been considering using a seed value, but I've decided not to go that route for now. I'm the same in a way, though, since parts of the 'local' map - ie the scale the player walks around on - aren't generated until you first step foot in them.
I also found rivers by far the toughest part. If I split my workgen into various parts - land, terrain, height, mountains, forests, gorges, volcanoes, and rivers, rivers take more time than all the others combined, and it's about as efficient as I can find a way to make it at the moment.
Biomes are currently based primarily upon latitude, with a small height component, though I plan to make this slightly more complex in the future.
As for rivers, my latest devblog entry is on just them!
http://www.ultimaratioregum.co.uk/game/2011/12/19/the-case-of-the-penrose-river-2/
Here's how rivers look at the moment (without any current or indicator of flow shown, currently):
(http://www.ultimaratioregum.co.uk/game/files/2011/12/River.png)
Let me know what you think, or if the explanation I give there isn't clear enough : )
This is great, I love procedural/random map generation, but it's so darn difficult! Is there a place for best practices having to do with such things? I know of the procedural content generation WIKI, but that's about algorithms and not code. Perhaps it's time to start a page on roguebasin...
EDIT:
This represents my solution to making level generation algorithms that can be used flexibly. I'm interested in peoples opinions, and I'd really love to start some kind of library project, although that might be a little ambitious.
http://roguebasin.roguelikedevelopment.org/index.php/Designing_Flexible,_Reusable_Algorithms (http://roguebasin.roguelikedevelopment.org/index.php/Designing_Flexible,_Reusable_Algorithms)
I know what you mean - starting a library project seems like a huge undertaking! I'm trying to get a flexible generation system that can be used for dungeons, but since the focus of URR is on large-scale army combat, dungeons aren't actually that common. So while it's important, getting the outside world looking good is significantly more vital. Really interesting article, though, and has given me a few ideas...
I've thought about starting a blog to post code snippets and screenies as I work on stuff...
Some of the code is too long to be spamming up these forums with. <_<
Here's a great article on polygonal map generation: http://www-cs-students.stanford.edu/~amitp/game-programming/polygon-map-generation/
I don't know why I didn't think of using a table like that to figure out biomes myself, lol....
I've come across that article before - it's fascinating, and gave me quite a few ideas for my system. In the end, though, I think how the map looks is more crucial than how it's constructed; which is to say, if you use a simpler method but the end result is no different, I think one should err on the side of the simpler method. My system is not quite as complex, but I think (at the moment) the map is sufficiently complex : )
Here's a pretty good paper on river generation. Probably wouldn't work for a truly procedural world though...
http://www.cs.sjsu.edu/~teoh/research/papers/CGVR08_terrain.pdf
Wow - that's much more detailed than anything I'm going after. As you say, though, I think that could only be used in certain areas, and I'm not sure I have the skills to program that in myself anyway!
-
I've gone back a bit and added a heightmap in, properly, to the world map. This is enabling hills, more interesting coastlines, and all kinds of other funky stuff.
For instance, a comparison of the same area on the minimap looks like this:
(http://www.ultimaratioregum.co.uk/game/files/2011/08/11.png)
I've uploaded a load of new screenshots and looks at the world in today's devblog entry @ http://www.ultimaratioregum.co.uk/game/2011/12/26/winter-screenshot-update/ - how does everyone think it's looking? :)
-
The rightmost lake (3 down, 6 right) from X looks quite steep. Height 4 on western and height 0 on eastern coast.
-
- how does everyone think it's looking? :)
I think it's looking pretty awesome. The "lakefall" Z mentions could theoretically just be a lake adjacent to towering cliffs.
-
The rightmost lake (3 down, 6 right) from X looks quite steep. Height 4 on western and height 0 on eastern coast.
Yep; but I decided to allow that. Cliffs don't form (both because in the real world, they are actually pretty rare, and they don't stick with the wide-scale 'open' combat theme of the game) so it's a very, very steep incline instead.
I think it's looking pretty awesome. The "lakefall" Z mentions could theoretically just be a lake adjacent to towering cliffs.
Cheers! It is largely thus, though as I say, more of a very steep slope. Lakes often have different heights on different sides from that, whereas normal terrain is (generally) a lot smoother :). That screenshot is actually fractionally out of date; in actual fact, on land, squares can only go up or down by 1 in adjacent squares. Again, stops cliffs, keeps things a lot smoother for large battles, and also (I confess) makes the whole thing easier to draw on the human scale!
-
I would assume the level of the lake is the same as the level of the lowest land adjacent to the lake. Or the lake would just sort of run out. Right? :-)
Cliffs are fun to throw evil off of. And to jump down to escape the cowardly mooks that dare not follow you. You are probably wanting to make a realistic world with fewer cliffs. But in heroic fiction there is always plenty around.
-
http://swordofahkranox.blogspot.com/2011/12/new-year-comes-with-new-features.html
A bit tangential perhaps to the goings on afoot here directly, but these folks are definitely figuring some stuff out bit by bit at a good clip as far as these sorts of things go.
-
I have written a terrain/river generation program a long time ago, and the algorithm was simply something like "start river in a random point; while river has not reached the ocean, find the lowest pixel next to the river, and add it to the river". This algorithm did not generate meanders or deltas, but it did generate nice lakes (if the river falls into a local minimum, it fills all the land around it, until it breaks the wall). I am not an expert on rivers, but I have a feeling that flat lakes and rivers going strictly downwards are more natural (don't rivers carving through hills, subterranean rivers, canyons, and lakes with towering cliffs form simply because there is a kind of rock (limestone) which is very poor at blocking the water, effectively making the river generation algorithm treat it like air?). Anyway this was intended as just a fun simulation, not a game.
-
I would assume the level of the lake is the same as the level of the lowest land adjacent to the lake. Or the lake would just sort of run out. Right? :-)
Cliffs are fun to throw evil off of. And to jump down to escape the cowardly mooks that dare not follow you. You are probably wanting to make a realistic world with fewer cliffs. But in heroic fiction there is always plenty around.
Correcto; lowest level (almost always sea level) is the level for lakes. And there are some steep areas, but still no absolute cliffs; though you will be able to knock creatures off towers, bridges, ramparts, and similar areas instead!
http://swordofahkranox.blogspot.com/2011/12/new-year-comes-with-new-features.html
A bit tangential perhaps to the goings on afoot here directly, but these folks are definitely figuring some stuff out bit by bit at a good clip as far as these sorts of things go.
Most interesting - an infinite world? I'll be keeping an eye on that project...
I have written a terrain/river generation program a long time ago, and the algorithm was simply something like "start river in a random point; while river has not reached the ocean, find the lowest pixel next to the river, and add it to the river". This algorithm did not generate meanders or deltas, but it did generate nice lakes (if the river falls into a local minimum, it fills all the land around it, until it breaks the wall). I am not an expert on rivers, but I have a feeling that flat lakes and rivers going strictly downwards are more natural (don't rivers carving through hills, subterranean rivers, canyons, and lakes with towering cliffs form simply because there is a kind of rock (limestone) which is very poor at blocking the water, effectively making the river generation algorithm treat it like air?). Anyway this was intended as just a fun simulation, not a game.
That description is very, very close to how rivers form in URR. They can carve valleys, but not that often, and they obviously head down-hill by default. Lakes form when a river cannot find an exit into a gorge, or an ocean square, and their depth is determined by a bunch of factors. Though, since swimming will hardly be a focus of the alpha, their depth and other factors will come much more into play later.
-
I'll revive this old thread. I've played around with height map generation, namely this algorithm: http://en.wikipedia.org/wiki/Diamond-square_algorithm (http://en.wikipedia.org/wiki/Diamond-square_algorithm). The terrain it makes is very unnatural though, as there are no valleys. Normally every point on the map should have a path to the ocean that's only going down. This will allow nice looking rivers. I was thinking of enforcing this as a second step (kind of "erosion"), but it would be computationally costly, and not necessarily give nice looking results. An algorithm that generates realistic mountains in one step would be much better. Ideas?
-
World generation won't happen very often, so as long as it doesn't take long and as long as there's some kind of indication of progress, that's not a problem. Perlin and Simplex noise are more popular choices for heightmap generation at the moment, but they suffer from the same problem of geological implausibility. Libtcod has a very efficient erosion algorithm
If you want to do crazy-efficient erosion in real time (on a graphics card), you can take a look at Florian Boesch's craftscape demo: http://codeflow.org/entries/2011/nov/10/webgl-gpu-landscaping-and-erosion/
-
I'll have a look at libtcod. Is their algorithm documented anywhere? It doesn't have to incredibly efficient, but I'm trying to keep start up time below ~5 seconds. The terrain size is in the range of 1000x1000, so something linear would be great. I'm also afraid that the algorithm would do implausible things, like digging out straight lines to the nearest lower point. What's your experience?
Ideally I'd implement something that generates mountains in one step, surely there must be an algorithm.
-
I've been following your work for some time now, since the time your project was still about medieval fantasy. Yeah I did fight some trolls back then! Though I feel sad you discarded the fantasy setting, I'm still looking forward to play it!
Regarding the your map generating algorithm. It is the most beautiful, easy to ready and believable pseudo-ASCII map generator I've seen so far. Really, I got pretty amazing with it. Your clean overall design of the whole game is without a doubt the best experience I had so far in the rogue-like world.
EXCELLENT WORK!
-
I had a look at libtcod's height map generation. It looks like the main elements are placing a hill, which is a part of a spheroid and rain erosion, which simulates rain drops that roll down and take soil with them. What to do with it is left to the user. I'm not sure if this is enough to generate really good terrain, does any one have any experience?
By the way, I'm specifically looking for an algorithm that generates terrain without local minima, just like (mostly) in reality. This will let me generate a nice river system almost for free.
-
Libtcod's heightmap generation is a lot more flexible than that. The "hmtool" included with the library lets you add r multiply by FBM noise, add hills, divide into a voronoi diagram, smooth the landscape, simulate rain erosion, and normalise the result. Once you find a sequence of operations that generates a suitable map, you can use that algorithm with different seeds to get similar-but-different maps.
-
Do you know what the Voronoi diagram thing does? (I know what a Voronoi diagram is, just don't know how it can be used for terrain generation)
-
Why not see for yourself? Load the hmtool executable from the libtcod download and click on the voronoi button.
-
Here is a pretty cool article about Voronoi diagrams and such: http://www-cs-students.stanford.edu/~amitp/game-programming/polygon-map-generation/
As always,
Minotauros
-
Yup, I've read it a few days ago. It's the first algorithm that I've found that guarantees a "no-local-minima" level. It gave me the idea to start generation with a river system, and then generate a height map, such that the farther away from water, the higher. I'll try it out soon.
-
That might not make a very realistic river system - real rivers don't tend to form loops.
-
Dunno if relevant, but I have been imagining an overworld where the x axis corresponds to wetness and the y axis corresponds to heat. With mountains and rivers flowing through.
So the very bottom right is the hottest and wettest, so it's basically tropical ocean. The top right is iceberg ocean. The top left is coldest and driest, so tundra. The bottom left is hottest and driest, so it's mostly desert.
That was how I was going to create my often attempted and often failed Zelda Opus roguelike.