Islands Strategy Base Base Distance
I am creating a strategy game in Java for which I am currently writing a map editor. Before starting the game, the player makes a map with several islands and several resources on each island. After saving the map, the number of players is selected. Each player has a base, and bases should be located at the farthest distance from each other.
So, suppose I load a map with 5 islands and have 2 players, when the game starts - each player should have one island. These islands must be at the farthest distance from each other, so it should be like this: player 1 island, neutral island, neutral island, neutral island, player 2 island.
I don't know what my algorithm should be for this.
source to share
This problem seems to be equivalent to this question: https://cs.stackexchange.com/questions/22767/choosing-a-subset-to-maximize-the-minimum-distance-between-points . Solving this efficiently and accurately can be an open problem in theoretical CS! Since this is for the game, I'm not sure how much effort you go into solving this problem in exactly the optimal way.
It should be fairly easy, fast, and close to the rule to generate a random guess and multiple times (distort it, measure the badness of the indignant guess, and if the indignation of the predicted error is better than the current guess, make the indignant guess the current guess).
As for what you think is a bad guess, my suggestion is "the average (distance to the player closest to the island) across all player-inhabited islands."
source to share
Assuming your island count and your player number are pretty small, I think a simple exhaustive search would be the easiest and fastest way to implement a way to do this.
- make a matrix that keeps the distance from one island to each other on islands. (only necessary
- systematically iterate over all combinations of player placements, sum each distance from one to all other players, and keep the maximum
source to share