Decomposing a map

[Anarchid]

So, i imagined myself a problem, that sounds this way:

"Given the following: heightmap, typemap, metal spots, create a voronoi-like diagram using spots for seeds, while trying to keep cells to equal area each, avoiding long-and-narrow cells, and aligning cell edges to obstacles such as cliffs or lava".

So far i've been thinking of using lua pathfinder calls for calculations of distance as a magic bullet for taking height/type into the equation, but i've no real idea on how to balance it out with the equal-area demand.

What i'm hoping to achieve with this is a map is divided into sectors, which can be 'conquered' by units and serve as the game's only (re)source of income, while reusing many of the existing maps made for other spring games.

(because the old approach i used - that's, just dropping a rectgrid on top of those maps - is just ugly, terribad, and doesn't respect the map in absolutely any way; and because i'm not that fond of an idea of making a lot of my own maps from scratch at least right now)

Any ideas/suggestions how i can do this? Is using pathfinder here a good idea or a hopelessly abusive fail?

[knorke]

so you want oddly shaped borders like in Risk?


unless you want to invent an algorithm for fun/learning i would say make some editor to edit borders by hand.

[Anarchid]

i would generally prefer convex regions that would be more or less square.

Though, hand-editing sounds like a simple option, but then i'd need to spend time on making all these manual polygons either way, and somehow tag them for all the maps - not sure if that's quicker in any way, so i'll at least experiment with something first.

[PicassoCT]

well.. then you basicall need a random generator you give it certain ranges that are allowed (math.random(75,120) degrees).. and let it slave away. Every five or six points you calc the area. Then you need a "open"List of the map, which contains all the still "free" borders. You find the closest one, check if you can fit the cell into the map (and if you have to transform it, is it still within the treshold), then you glue it in, (meeting in the middle with all the neighbours) asign all the borders who are free to the open List. Do so until the break of days.

Alternative: You use sort of kaleidoscope approach. And then distort it in a way that doesent hurt the equal area to much.