Algorithm Help
BlitzMax Forums/BlitzMax Programming/Algorithm Help
| ||
Hey all, I'm doing random worldmap generation right now, and am looking for a good algorithm to use as a starting point to solve the problem of creating provinces on the map. Here's what I've got. - a 2d array of map squares - each square knows its own height (the whole map was seeded heights by mid-point displacement - thanks impixi & the other contributors to that code) - a semi-random selection of squares that are also province capitals What I'd like to do is have each province capital spread outwards from itself "claiming" land, having its eventual outward movement limited by the advance of neighboring provinces. I'd also like the ability to make it more difficult to spread from one geographic zone to another - i.e., it's a lot harder to take over the mountain squares from the grasslands than it is to just spread out in the grasslands. Thanks for any help you can lend. |
| ||
Do a search on Influence Maps. They're used in strategy games but come from Heat Dissipation. Give your capital a heat radius and let it spread and cool gradually. Soon it will meet the 'heat' radius of another capital which will stop it's spreading. To make your regions each square has a temperature, mountains regions are colder than grasslands so it reduces the spread quicker. Hope that makes sense |
| ||
It does make sense - I'll take a look. Thanks! |
| ||
You can also use a method where you create a polygon web with the capitals in the center of each triangle/poly. [created by Chris Crawford] http://www.google.com/url?sa=t&ct=res&cd=1&url=http%3A%2F%2Fbooks.google.com%2Fbooks%3Fid%3DUSBbi1Dyw4sC%26pg%3DPA305%26lpg%3DPA305%26dq%3DChris%2Bcrawford%2Bpolygon%2Bmap%26source%3Dweb%26ots%3D7RdCKSBCVn%26sig%3DN2Q2rIaQWTnt0pv1xxQdLKudxtc%26hl%3Den%26sa%3DX%26oi%3Dbook_result%26resnum%3D1%26ct%3Dresult&ei=1SmvSN_QJJq4sAORutWEAQ&usg=AFQjCNEtD0FZ45xy4WGsFJlbAnnlHCrfIA&sig2=7n68fWAaQy_V226CewxPsg |
| ||
Huh. That's really interesting. Taking a look there, too. Thanks. |
| ||
Actually the link i posted was wrong, look to page 343 of that book for the formula of dividing up the provinces. |
| ||
I was actually just about to create a thread on this topic. But I'm gonna resurrect this one. Any chance any ones had any luck on any of this? lol. Since I'm working on a RTS I'm gonna need procedural generated maps. And I like the idea on displacement with heat. That actually makes a lot of sense to me. And I read the pages in that google book. There where good ideas but I cant see how I would really implement them. Now my first step is to ask. How would I go about generating the terrain part first? Should I look up life-cycle style algorithms? Since this is a top down, its tile-based. So getting map positions should be easy as pie. |
| ||
Here you go. I just use perlin noise with a bit of fiddling to generate a heightmap, representing the terrain. Then the provinces randomly pick adjacent points to spread to, with points at a different height harder to spread to. Last edited 2011 Last edited 2011 |
| ||
@warpy your code does not start! The dimensions of the arrays seem to be to small. work-around: ... Local map#[size+1,size+1] Local tmp#[size+1,size+1] .... Local control:province[size+1,size+1] .... |
| ||
That's what I get for not using debug mode! I've fixed the code in my post above. |