Random Risk-Style Terrain Generation

Hello Everyone,

There are many tutorials out there explaining how one would randomly generate a dungeon consisting of square blocks, but I'm a little confused about how I should go about having my game randomly generate a Risk-style environment for my strategy game. The main issue is that the "sectors" on such a map would be entirely asymmetrical and yet would also have to naturally connect together while still retaining borders between them. The best example of what I'm trying to accomplish would be the random maps generated by a game like Dominions 5, a screenshot of which I've attached to this thread. I just can't get my head around the issue conceptually and so I don't know what the "building blocks" of my randomly generated worlds would be, if you know what I mean.
 

Attachments

Just to be safe before I start getting into it too much, are you talking about something like this? Where every 'country'/'dungeon'/'region'/etc. is a weird shape, and being able to stick that together, with collisions and all?
 
Just to be safe before I start getting into it too much, are you talking about something like this? Where every 'country'/'dungeon'/'region'/etc. is a weird shape, and being able to stick that together, with collisions and all?
Yeah that's what I'm talking about. There are seven nations in the game. Whenever a new game is started the system should randomly generate a world in the style of the one in your video and my screenshot. Each nation will own one territory in that world at the beginning, and then seek to expand from there. It's fairly standard, as far as gaming goes, but I couldn't find a tutorial for achieving it.
 
Well, as I love strategy game (that's my main thing), I tried multiple times to do something like this, in various ways.
From what I see and assume (not a good thing, but hey, gotta start somewhere!) of your screenshot, I would not suggest to use the method I used in that clip, which would be more suited for non-random maps.
That said, I think the approach I would first try in your case is basically to use a grid (could be square or hex), but make the 'base tile' quite small so you have plenty of room and options for cool-shaped borders.
You would first generate the whole map, and then procedurally generate the borders. That would make it much more simple in the long run, as your only algorithm to determine in which region you are/are selecting/hovering would be one that convert mouse/cursor/etc to a spot in a 2D array, which is quite simple in itself.
The bigger the resolution (i.e. cool-shaped borders), the bigger the array would be, but once there, there's many ways to optimize stuff, so I wouldn't be concerned with it at this stage. You could even make a 1-pixel grid, if you were THAT motivated and really want hi-end resolution on the borders, but I think this<d be way overkill.
A basic constructor architecture I'd use for each cell would probably look like this (add stuff as you need it)
GML:
function init_tile(grid_x, grid_y, _center_x, center_y, tile_type, occupying_team, is_explored) constructor{
         //Just stick those arguments to your struct variables
}
This way, you would also not have to deal with the nightmare of determining which regions are connecting to each other (like in my Risk clip), which is really not fun. Just compare grid positions and occupying team, and you know if it's friendly territory or not right away.
 
Most of the reason why people focus on dungeon generation over this style of generation is because dungeon generation is vastly simpler to explain and implement, lol. Here's a page that explains at least a little of what you are wanting: http://www-cs-students.stanford.edu/~amitp/game-programming/polygon-map-generation/

I'm not entirely sure what direction @Slow Fingers is going to go into, but I, at least, think of the problem like this.

1. I need to develop a good data structure format to hold all the details about how each polygon within the game map should be thought of. Polygons are not the whole "regions" of the map (i.e. Africa in the world map is not a single polygon), but instead the pieces the region is made up of. If you wanted a detailed world map, then polygons would be individual pixels (as the world map is highly detailed), but going down to the individual pixel level would mean everything would run very slowly during the generation so most games make the polygons into larger chunks (this can be seen in Civilisation when you pick the World map, as each polygon is a rather large standard Civ hexagon making some of the countries look a little...odd (Australia in particular)). In Amit's example (the page I linked), they are using voronoi polygons. Each polygon should also hold some way of determining what other polygons it is connected to, to make sure that the map is traversable for things like pathfinding.

2. Once I have that data structure, I need to "fill" the world with these polygons in some way. Usually this would be an array, with each position in the array holding a single polygon. If the polygons are irregular sizes, this can be a tricky process, but in general, I would find some way of boiling everything down to an array or potentially a map.

3. I need to determine how the borders of each "region" are decided. Am I picking competing points and then floodfilling out from them until they hit each other? Am I predefining border sizes? If so, what happens when borders clash? Etc.

4. Once I know how the borders are determined, I need to find each polygon within each border and mark it down somewhere as "belonging" to that bordered region (normally when I am generating stuff like this that kinda gets more granular as you go down, I store it all in a single array, which holds structs which can hold arrays which can hold structs, all the way down. Then, for instance, position 0 in the top array would be "border region 0" and that would hold a struct that contains the border colour, etc, any information about that region, an array of the cells within the borders, and so on for each region).

5. You are basically done at this point. Now would be when I add any non-region related things (such as treasure, or villages, or whatever random stuff you want in the game). This way you can use the existing border structures to figure some stuff out (for instance, you might not want villages to spawn in a bordered region or whatever).

6. Optimisation. This is the real final step, once you have everything sorted out in a way that works, it's time to benchmark and then start thinking about optimisation steps if needed. It's always best to save this step to the last, instead of trying to optimise throughout the process, because only at this point are you really fully aware of everything that needs to happen and how the overall structure of the generation will interact with itself. Maybe there's a "2D" array somewhere you can convert to a "1D" by using a position conversion key (x + y * width) or whatever. If so, try it out and see if it speeds things up? Etc. But this step is only needed if things are actually running slowly because of the map in some way.

That would be how I would try to approach the problem. I've never done anything like this before and there's almost guaranteed to be some "gotchas" caught up in the steps I describe above, but that's part of figuring out this generation stuff. Tackle it head on as hard as you can and hope you can hit it hard enough to bounce any problems out of the way.
 
@RefresherTowel brings up a lot of good points. The fact of the matter is: this ain't going to be a weekend-long walk in the park. I would definitely take the time to make some flowcharts, and write down the logic of what happens from the moment you press "Start Game" to the moment the map appears. You'll save time and frustration. This is a big meal of which not every bite is going to taste good, but it's really fun, tho!
I forgot to mention, but maybe this is an option for you: some games do this stuff in pre-made chunks that fit together, and use a random combination of those chunks to give some map variety. You could for example have, say 10 "continent" models, and if a small map has 4 continents, that's like a 700 possible combinations right there (+- 11k possible combinations if you go 7 continents). XCOM (the modern ones) comes to mind of a good example of building maps in chunks like this.
 
Okay, thanks guys. This is very advanced for me and there's a lot for me to digest here so I'll need some time, but I'm determined to get this working. I really have no other choice since the whole premise of the game rests upon it.
 
Okay, thanks guys. This is very advanced for me and there's a lot for me to digest here so I'll need some time, but I'm determined to get this working. I really have no other choice since the whole premise of the game rests upon it.
If you haven't done much procedural generation before, I do have a tutorial series (link in my sig) that goes through a number of different proc gen concepts explained specifically for GMS that I would definitely be using in a generation system like this. Might be helpful depending on your level of programming experience.
 
If you haven't done much procedural generation before, I do have a tutorial series (link in my sig) that goes through a number of different proc gen concepts explained specifically for GMS that I would definitely be using in a generation system like this. Might be helpful depending on your level of programming experience.
Yeah I'm a complete beginner so even that tutorial is way beyond me. I got lost early on the second page. You said in your tutorial that you're bad at maths, and so am I, but almost certainly much worse than you, so it takes a lot of time for me to process this kind of information. That's okay though, I never assumed this kind of thing would be easy or quick or painless.
 
Last edited:

TheouAegis

Member
Get really fancy and use a naturalistic method. Just as an abstract, you could make a terrain generator (mountains, rivers, oceans), then add a foliage generator. Then generate nation borders (utilizing what the other guys mentioned) based around the terrain. Then generate additional borders based around an arbitrary grid of latitude and longitude. In any case, divide & conquer would be a "natural" progression, since borders are determined by conflict over natural resources first and foremost, then by negotiation later.
 
Get really fancy and use a naturalistic method. Just as an abstract, you could make a terrain generator (mountains, rivers, oceans), then add a foliage generator. Then generate nation borders (utilizing what the other guys mentioned) based around the terrain. Then generate additional borders based around an arbitrary grid of latitude and longitude. In any case, divide & conquer would be a "natural" progression, since borders are determined by conflict over natural resources first and foremost, then by negotiation later.
Nice idea if I knew what I was doing at all. Having spent the morning trying to understand Refresher's tutorial, it seems like this is something way too advanced for me to even be entertaining at the moment. I guess what I'll do is try and achieve what I want with the game on a preset map, something I have some grasp of how to do. Hopefully I can then return to this thread and all of this good advice and understand it due to the experience that I've acquired in the meantime. The kind of map generation I'm trying for has been a part of games for so long now that I didn't really expect it to be such a big ask, if you know what I mean.
 
Top