DrPraetorious
August 20th, 2007, 12:05 PM
I have a very nice fair site finder script that I posted - it works great on *wraparound* maps.
It works okay on flat maps except that it doesn't know about corners.
The only way to arrange fair start sites on flat map is to put them equally spaced in a ring around the middle. Unfortunately, I'm not sure how you'd do this on an arbitrary graph.
So how's about this for an approximate algorithm:
* Find the shortest route between every province pair.
* Find four provinces which are the "center" of this map: these four provinces will have the lowest sum-distance-to-all-provinces, and will not be within 3 provinces of one another. The remoteness of a potential start location is going to be the sum of the distance of that start to the four centers.
* Potential start locations must be in in the second quintile of remoteness. That is to say: a start location must be less remote than at least 20% of all provinces, and a start location must be more remote than at least 60% of all provinces.
* In addition, the start locations can be as far apart and have as many (non-waste, non-deep-sea, non-swamp) neighbors as you specify.
* Enable as many such start locations as you can using the same algorithm I had before.
This is fairly complicated and I need to go to my own posting and get a copy of my script which I did not otherwise backup for some time http://forum.shrapnelgames.com/images/smilies/frown.gif (I have some proof of concept stuff on the machines at work but I lost quite a bit when I dropped my frickin' HD on the floor).
Thoughts? Suggestions? Comments?
It works okay on flat maps except that it doesn't know about corners.
The only way to arrange fair start sites on flat map is to put them equally spaced in a ring around the middle. Unfortunately, I'm not sure how you'd do this on an arbitrary graph.
So how's about this for an approximate algorithm:
* Find the shortest route between every province pair.
* Find four provinces which are the "center" of this map: these four provinces will have the lowest sum-distance-to-all-provinces, and will not be within 3 provinces of one another. The remoteness of a potential start location is going to be the sum of the distance of that start to the four centers.
* Potential start locations must be in in the second quintile of remoteness. That is to say: a start location must be less remote than at least 20% of all provinces, and a start location must be more remote than at least 60% of all provinces.
* In addition, the start locations can be as far apart and have as many (non-waste, non-deep-sea, non-swamp) neighbors as you specify.
* Enable as many such start locations as you can using the same algorithm I had before.
This is fairly complicated and I need to go to my own posting and get a copy of my script which I did not otherwise backup for some time http://forum.shrapnelgames.com/images/smilies/frown.gif (I have some proof of concept stuff on the machines at work but I lost quite a bit when I dropped my frickin' HD on the floor).
Thoughts? Suggestions? Comments?