Evenly choosing randomly generated capture points?

[dthecoolest]

So I have created an terrain generation system similar to armored patrol with random mountains big thanks to @okeanskiy for the triangle terrain generation, @ThanksRoBama for the fractal noise generator and introducing me to Red Blob Games, that website is amazing

Edit: Side view I believe is better:

Now the question is how would I choose the already generated random mountain points as a capture point in a way so it’s a bit more fair for both teams?

Armored patrol for reference and goal, the flags are placed within the middle:

My current method I’m going to try out is this:

1. Choose number of capture points, ex 3 points

2. Iterate through all the possible combinations of the already generated mountains of the three mountains selected as capture points.

3. While Iterating measure the mean distances from a base.

4. Choose the best set with the mean closest to the middle of the map (map is 5000 x 5000 studs so best mean is 2500 studs from a corner)

But this doesn’t seem exactly optimal kind of like dart throwing. That’s why I made this to post help brainstorm of methods to do this, currently can’t find any or the proper search terms for this problem.

Any ideas and any help are appreciated for a problem of this complexity.

local XSize = 5000 -- mapsize in studs
local ZSize = 5000-- mapsize in studs

local mountainRandom = Random.new()
local mountainDataTable = {}
for i=1,10 do
--current method of generating mountains, just random with certain conditions
--cannot be too close to each other or out of map bounds, also dart throwing method
--that is closed source tho :P
	local randomX = mountainRandom:NextNumber(-XSize/2, XSize/2)
	local randomZ = mountainRandom:NextNumber(-ZSize/2, ZSize/2)
	local mountainPosition = Vector3.new(randomX,0,randomZ)
local mountainData = {mountainPosition}
	table.insert(mountainDataTable,mountainData )
end

local BaseCorner1 = Vector3.new(-XSize/2,0,-ZSize/2)--team 1 map corner position
local BaseCorner3 = Vector3.new(XSize/2,0,ZSize/2)--team 2 map corner position

for i,mountainData in pairs(mountainDataTable) do
	local mountainXZPosition = mountainData[1]
	--Ways to choose 3 mountains to be somewhere around the middle?
--most important is that it's "fair"
--in between the two teams
end

Edit: Also I believe AP compensates if a capture point is too close to the enemy base by rewarding less points, even so the capture point still is generated somewhere around the middle somehow which is what I’m trying to achieve.

[CoderHusk]

did u ever think of generating like a 50x50 perlin 2d array buffer with each component containing the perlin value, x and z input then push the ones above like idk 1 too a seperate array then multiply the x an z by the map size / 50 then set the y to be the terrains height at that voxel

[dthecoolest]

Sounds like you are describing how to generate the terrain using noise.

Unfortunately my problem is with choosing a set of mountains to be a capture point fairly for both teams sorry if it’s not clear.

[CoderHusk]

i thought it was inferred you’d only choose farthest away 3 points after.

[okeanskiy]

Without some high degree of discrete or graph theory mathematics that I wouldn’t realistically expect anyone here really be able to bring to this discussion, and with some certainty that this is already the most optimal method for choosing the “fairest” sub-set of k mountains from the set of n mountains, I would say that there is not much to change here. On top of that, since this is a one-time operation per map load, there is not much of a need for an optimization unless you had a much greater n (try >100 mountains).

Only things I would keep in mind:
A. Not sure if you are doing this already but the way you worded it suggests maybe not. Steps 3 and 4 should really be combined into one step. Do not calculate and store all mean value sub-sets and then find the best one. Instead, store the current best mean value sub-set and as you iterate - calculate, compare, and re-set the current best mean sub-set if the comparison proves a sub-set to be fairer.

B. Consider edge cases where mean values for a set could be “fair” when in reality the control points are not, and adjust the formula for determining a sub-sets fairness value as necessary. Consider a sub-set where one team has a point extremely close, and the other team two points somewhat close. Your game’s mechanics may prove this to be very advantageous for the latter team, despite a mean value suggesting “fair”. Consider taking the nth-root mean value or an nth-power mean value as opposed to just a normal mean.

[ThanksRoBama (Emma)]

Just a suggestion: you could generate fairer mountain placements rather than trying to choose a fair combination of mountains that might not have such a combination. E.g. by making mountain placement symmetric across the map diagonal between bases. If I’m thinking right that should also make it much more likely that you’ll get cap points neary-ish to the corners where the bases are, which is still fair if it’s symmetric for both bases and a bit more interesting than always having cap points along the diagonal. You don’t have to make the entire map symmetric, which would probably be a bit boring.