Bay 12 Games Forum

Please login or register.

Login with username, password and session length
Advanced search  

Author Topic: Random Hex Map Generation  (Read 3403 times)

Gatleos

  • Bay Watcher
  • Mournhold... City of Light... City of MAGIC!
    • View Profile
    • Someone Sig This
Random Hex Map Generation
« on: July 19, 2015, 01:54:45 am »

So I've been working on a hex map engine for quite a while now, whenever I felt like it. It's probably the most ambitious thing I've ever coded at this point, and it's gotten to the point where I thought you guys might find it interesting. In addition to basic hex grid operations like hex<->pixel conversion and axial<->offset coordinate conversion, I've implemented pathfinding, sprite animation, panning and zooming, and a pretty detailed map generation procedure.

If you ever visit the coding thread in GD, you might have seen some screenshots of this map generation that I posted in the past. Here's some more:
Spoiler (click to show/hide)

It doesn't have a whole lot of interesting things going on right now, but it's got the framework for a lot of really cool things I'm planning to do with it. All of the under-the-hood stuff is pulling together, and soon I'll be ready to make more interesting things happen. If you wanna check my current progress out, here's a download link:
Download v0.1.6
That's a pre-compiled windows executable. If you're on another platform, here's the source and makefile.

As for this thread, I guess I'll post any interesting updates on my project here. Yeah, it's probably going to end up being a game.
Logged
Think of it like Sim City, except with rival mayors that seek to destroy your citizens by arming legions of homeless people and sending them to attack you.
Quote from: Moonshadow101
it would be funny to see babies spontaneously combust
Gat HQ (Sigtext)
++U+U++ // ,.,.@UUUUUUUU

HavingPhun

  • Bay Watcher
    • View Profile
Re: Random Hex Map Generation
« Reply #1 on: July 27, 2015, 10:11:46 pm »

Those look great. Assuming moisture/rainfall was one of the factors in determining the biomes. How did you go about determining the rainfall for each hex?

I have been working on something very similar, but it uses square tiles instead of hexes. I'm not sure how it seems to people, but I can agree with you that they are quite a large undertaking, and a project in themselves. Did the use of hexes make it much more difficult to code? Also, are you going to add rivers to it? Here is the one I made:
Spoiler (click to show/hide)

Besides a whole load of loose ends and tweaking, I am pretty happy with the results.

______________________________________________________________________________________________

What sort of game do you plan on making, a turn based strategy?
« Last Edit: July 27, 2015, 10:17:34 pm by HavingPhun »
Logged

Gatleos

  • Bay Watcher
  • Mournhold... City of Light... City of MAGIC!
    • View Profile
    • Someone Sig This
Re: Random Hex Map Generation
« Reply #2 on: July 30, 2015, 06:43:30 am »

Quote
Assuming moisture/rainfall was one of the factors in determining the biomes. How did you go about determining the rainfall for each hex?
The rainfall isn't really as sophisticated as it could be, it's just random noise. Right now it uses four overlaid Simplex Noise maps, for height, temperature (y-axis biased), rainfall and drainage. The terrain types are basically determined by all those noise values in order. Once I got the simplex noise working, it was pretty simple from there. Those mountain ranges were probably more effort all by themselves, at least getting them to look natural.

Quote
Did the use of hexes make it much more difficult to code?
I needed to use a whole different coordinate system and figure out how storing it all in memory would work, so it was quite a bit of extra work there. I'd suggest this fantastic guide by Amit Patel to anyone thinking about working with hex maps. Most of my understanding came from there.

Quote
Also, are you going to add rivers to it?
I've been thinking about it. There's a lot to think about if I wanted to do it right, like sprites.

Quote
What sort of game do you plan on making, a turn based strategy?
Yep! Pretty much. I've made quite a bit of progress since that 0.1.6 release, but there's no telling when I'll be able to get to gameplay stuff.
Logged
Think of it like Sim City, except with rival mayors that seek to destroy your citizens by arming legions of homeless people and sending them to attack you.
Quote from: Moonshadow101
it would be funny to see babies spontaneously combust
Gat HQ (Sigtext)
++U+U++ // ,.,.@UUUUUUUU

HavingPhun

  • Bay Watcher
    • View Profile
Re: Random Hex Map Generation
« Reply #3 on: July 30, 2015, 02:01:16 pm »

Quote
Assuming moisture/rainfall was one of the factors in determining the biomes. How did you go about determining the rainfall for each hex?
The rainfall isn't really as sophisticated as it could be, it's just random noise. Right now it uses four overlaid Simplex Noise maps, for height, temperature (y-axis biased), rainfall and drainage. The terrain types are basically determined by all those noise values in order. Once I got the simplex noise working, it was pretty simple from there. Those mountain ranges were probably more effort all by themselves, at least getting them to look natural.

I also used simplex noise for elevation, for temperature I just have a simple function that makes it hotter at the equator and colder as you go outwards. I'm not entirely happy with my rainfall. It does two things to determine the rainfall simulation. First, it calculates a rainshadow, so you end up with deserts on the eastern side of large enough mountains. Second, it propagates moisture from all water sources, in all directions. Something that I would eventually like to try is mentioned part way down in this article about generating different areas of wind speed and direction and then simulating the paths of several weather cells. Though the article is talking about generating using OpenCL, I still found it useful.

Quote
Did the use of hexes make it much more difficult to code?
I'd suggest this fantastic guide by Amit Patel to anyone thinking about working with hex maps. Most of my understanding came from there.

Have you read some of his other articles? I found this to be very useful, it helped me understand what I was doing early on. (Let me know if that link isn't working. I'm on a bad connection and can't load it right now). 

Quote
Also, are you going to add rivers to it?
I've been thinking about it. There's a lot to think about if I wanted to do it right, like sprites.

Doing the sprites wasn't that bad for me. It would be more time consuming since there are 6 directions for hexes instead of 4 for tiles. But, all I did was, pass each river tile through a function that determines which river sprite it should use. It just looks at all of the tiles adjacent to the river to do so. There would have to be many different sprites though because of the amount of directions and intersections possible.

The other issue that I see is making it so the rivers background color is the same as the surrounding land. Though it isn't perfect if you look at the image I linked, I have a something that could do it. The way I display the sprites is that initially, the background of the sprite is magenta, and the foreground is white. First it determines the background and foreground colors of each tile based on their biome. It's very subtle, but on the forests especially you can see slight variation in the background colors. I had the tiles elevations affect the background color. For rivers, I just took an average of background colors surrounding the river, and made that the river's background color.

It then runs each tile through a shader that replaces the magenta with that tile's background color, and the white with that tile's foreground color. Though my method only allows two colors in the sprite, it could be expanded to have more, and perhaps there is a better method. I think rivers were the most painstaking part for me so far though. They still need some tweaking, just like the rest of the generator.
Logged

Gatleos

  • Bay Watcher
  • Mournhold... City of Light... City of MAGIC!
    • View Profile
    • Someone Sig This
Re: Random Hex Map Generation
« Reply #4 on: July 30, 2015, 03:55:03 pm »

I also used simplex noise for elevation, for temperature I just have a simple function that makes it hotter at the equator and colder as you go outwards. I'm not entirely happy with my rainfall. It does two things to determine the rainfall simulation. First, it calculates a rainshadow, so you end up with deserts on the eastern side of large enough mountains. Second, it propagates moisture from all water sources, in all directions. Something that I would eventually like to try is mentioned part way down in this article about generating different areas of wind speed and direction and then simulating the paths of several weather cells. Though the article is talking about generating using OpenCL, I still found it useful.
I thought about rain shadows when I first started, and couldn't think of a method to quickly create them. I didn't want it to be unidirectional, since it might create noticeable patterns. I think I did read that article at some point.

Have you read some of his other articles? I found this to be very useful, it helped me understand what I was doing early on. (Let me know if that link isn't working. I'm on a bad connection and can't load it right now). 
Yeah, that was one of the earlier articles I read. I couldn't wrap my head around that random point relaxation and Voronoi stuff, but it gave me a few ideas for what I ended up trying later.

Doing the sprites wasn't that bad for me. It would be more time consuming since there are 6 directions for hexes instead of 4 for tiles. But, all I did was, pass each river tile through a function that determines which river sprite it should use. It just looks at all of the tiles adjacent to the river to do so. There would have to be many different sprites though because of the amount of directions and intersections possible.
If I do it right, I should only need 3 river sprites. They would run along hex edges instead of through the center, so I could make one sprite for each matching pair of edges. The tough part is generating the direction of the rivers, and the start and end points. Since I no longer use elevation to determine where mountains are placed (they're just cubic Bezier curves), it's not guaranteed that I can just let a river roll downhill to sea level. It would also be great if I could get them to fork or join in organic-looking ways.
Logged
Think of it like Sim City, except with rival mayors that seek to destroy your citizens by arming legions of homeless people and sending them to attack you.
Quote from: Moonshadow101
it would be funny to see babies spontaneously combust
Gat HQ (Sigtext)
++U+U++ // ,.,.@UUUUUUUU

HavingPhun

  • Bay Watcher
    • View Profile
Re: Random Hex Map Generation
« Reply #5 on: July 31, 2015, 12:53:21 pm »

Yeah, that was one of the earlier articles I read. I couldn't wrap my head around that random point relaxation and Voronoi stuff, but it gave me a few ideas for what I ended up trying later.
Yeah, neither could I really. At some point I might play around with that stuff. But, I had no problems creating everything without it.

If I do it right, I should only need 3 river sprites. They would run along hex edges instead of through the center, so I could make one sprite for each matching pair of edges. The tough part is generating the direction of the rivers, and the start and end points. Since I no longer use elevation to determine where mountains are placed (they're just cubic Bezier curves), it's not guaranteed that I can just let a river roll downhill to sea level. It would also be great if I could get them to fork or join in organic-looking ways.

Yeah, to make my rivers look semi nice I had to add in many different conditions for the rivers so they work correctly. One thing I had to do, was have each river keep a list of tiles adjacent to itself, and then ensure that it does not move into those tiles. That way it wouldn't just loop into itself and terminate, as that was a problem beforehand.

Another thing I did was that if every tile around a river is a higher elevation, then it will just plough through one of the obstacles in order to continue on.There were many other things I had to add in, I just don't really remember them. All I did really, is just kept adding rules for the rivers to follow until they looked nice.
Logged