Algorithm Help

BlitzMax Forums/BlitzMax Programming/Algorithm Help

Macguffin(Posted 2008) [#1]
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.


tonyg(Posted 2008) [#2]
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


Macguffin(Posted 2008) [#3]
It does make sense - I'll take a look. Thanks!


GW(Posted 2008) [#4]
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


Macguffin(Posted 2008) [#5]
Huh. That's really interesting. Taking a look there, too. Thanks.


GW(Posted 2008) [#6]
Actually the link i posted was wrong, look to page 343 of that book for the formula of dividing up the provinces.


Baystep Productions(Posted 2011) [#7]
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.


Warpy(Posted 2011) [#8]
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


Midimaster(Posted 2011) [#9]
@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]
....



Warpy(Posted 2011) [#10]
That's what I get for not using debug mode! I've fixed the code in my post above.