Starting TC distribution help

[b2198]

So, long story short, I'm trying to write a better version of the TC generation logic for the games, and think my method of determining the positions for the starting TCs might not be as good and/or as simple to do as I previously thought, so if you have any ideas on how to improve it, please share them here.

What I have working so far:
I've setup a logic to calculate scores for each tile of a map, based on a number of factors, like TC trnWalkTerrain values, how good water bodies and their shores are in the map, trnWalkTerrain values of some arbitrary units, some arbitrary trnWalkTerrain values for determining how good a tile would be as a nearby tile to a TC (for building factories, primarily), whether a tile has destructible or indestructible orbstacles on it, etc., and got some probability maps working decently enough (at least for now).

For example, these are the probability maps I've got for the map Riverside (currently, tests are only being done with AoS maps, but will most likely be expanded later to other games too)

(closest to 10 means "most probable", and closest to 0 means "least probable")
The "bad" probability map is for tiles in which a TC can be placed in, but that have too bad 8 surrounding tiles, so would only be considered as a last resort (and since being on an edge or corner of the map means some of those surrounding tiles are inexistent, this makes those tiles the most likely to be "bad" tiles), if the "good" tiles aren't enough to properly generate all the TCs needed.

Now, the next step is where I'm having problems at. I thought about dividing the map into 25 regions (in a 5x5 grid), and deciding the starting region for each player based on the total score of each region and some symmetry and distance rules. Here's what the region scores would look like:




For 2 players, this was just a matter of distance and symmetry. The logic would be to gather all pairs of regions that obey these rules:

• Manhattan distance between Region 1 and Region 2 is bigger than 2 (in the region grid, not in the map itself) AND
  • (Region 1's row = Region 2's row AND distance from Region 1's column to the center = distance from Region 2's column to the center) (in other words, symmetry relative to a vertical axis in the center) OR
  • (Region 1's column = Region 2's column AND distance from Region 1's row to the center = distance from Region 2's row to the center) (in other words, symmetry relative to a horizontal axis in the center) OR
  • (Region 1's row = Region 2's column AND Region 1's column = Region 2's row) (in other words, symmetry relative to the primary diagonal of the matrix) OR
  • (Region 1's row = column count - Region 2's column AND Region 1's column = row count - Region 2's row) (in other words, symmetry relative to the secondary diagonal of the matrix) OR
  • (Region 1's row = row count - Region 2's row AND Region 1's column = column count - Region 2's column) (in other words, radial symmetry relative to the center)

Then compare the differences between the scores of both regions and choose the combination with the least difference (in other words, the combination that, in theory, gave the least advantage to one of the players).

For 3 players, it started to get more complicated, because there would be no configuration (at least that I've found, I haven't proved it mathematically or anything near that) that would make all 3 players be equidistant from the center and from each other in a 5x5 grid using manhattan metric, so I started trying a different approach, which was drawing on a paper positions and try to analise how much territory each player would get in theory, assuming expansion occurred to all sides at the same rate, and stopped in regions shared by more than 1 player. The results I got were these:

So any valid combination would involve these positions or one of their rotations (with multiples of 90°, or PI/2 radians):



For 4 and 6 players, I went back to using radial symmetry, because I couldn't find any other configuration that would make the amount of territories for each player the same:



For 5 players it got tricky again, because radial symmetry didn't fit the grid, just like for 3 players, and a lot of combinations would leave some player between 2 others, so those were also discarded, ending up with:



The problems:

• These combinations wouldn't work for a lot of maps and, more importantly, for at least some player count in I'd say most maps.
• These combinations might not even be balanced in some extreme cases of terrain distributions.
• There are probably way better and simpler ways to solve this that I'm not aware of or didn't think to use.
• These combinations currently don't take into account player teams, which could allow for many more combinations by reducing the order of symmetry needed. (I have some ideas to solve this one, though)

[makazuwr32]

Would like to see this for aof eventually.

The problems:

• These combinations wouldn't work for a lot of maps and, more importantly, for at least some player count in I'd say most maps.
• These combinations might not even be balanced in some extreme cases of terrain distributions.
• There are probably way better and simpler ways to solve this that I'm not aware of or didn't think to use.
• These combinations currently don't take into account player teams, which could allow for many more combinations by reducing the order of symmetry needed. (I have some ideas to solve this one, though)

1. Won't comment this. I do not have idea how to make things better.
2. Well this one actually is solvable — we need to write in a more specific rules for random maps. Will still be problematic with old maps but new maps will be better.
3. Won't comment this since i have no idea how to make it simplier.

Also side note: do not forget about existance of preset tc maps (with fixed possible starting locations) and preset multiplayer maps.

[b2198]

2. Well this one actually is solvable — we need to write in a more specific rules for random maps. Will still be problematic with old maps but new maps will be better.

Hm, if there aren't a lot of maps with this issue, yeah, could be viable to do that.

Also side note: do not forget about existance of preset tc maps (with fixed possible starting locations) and preset multiplayer maps.

I'm taking those into account. I'm not entirely sure how old maps will be handled (I think a new option will be created in ME, but I'm not sure about that), but the logic will have support for taking into account existing TCs and spawners, and just fill in the remaining ones, if needed.

[phoenixffyrnig]

Once again, your mathematics has me running scared...
So I will play Watson to your Holmes, and pose a few questions and make some points, (mostly obvious ones unfortunately) in the hope of leading to some clarity.

It is a very worthwhile project that would really improve gameplay, so I whole-heartedly approve of your efforts. While preset TCs is in theory a good idea, I think in practice it would be extremely difficult to make a preset TC map that would turn out fair for 2, 4 and 6 player games, let alone odd numbers of participants. It would be a good approach for skirmish maps with a fixed number of players, but clearly you are searching for a more all encompassing approach with universal application here.


Firstly, a rhetorical question. Are you searching for a perfect solution? Clearly a very difficult undertaking and a very difficult goal - perhaps lowering your sights for just an improvement would be more likely to bring results. (for example, is a system of arranging players to be equidistant from the centre or equidistant from eachother achievable given the variety of maps in question?)

Maybe it would be better to not look at this problem in isolation, but in conjunction with the TC generation issue as well - ie an imperfect spawn could be made a lot more playable with a better TC spread.

I mentioned to you recently an appalling start I was given in a 1 on 1 that had no business to give such a skewed beginning because of the many better options available (I will send you a pic to fully show what I mean). That made me wonder if it would be possible to have minimum requirement checks for start points. Specifically things like minimum distance from another player, relative to map size. Or minimum adjacent free space relative to free space on the map (take Vaardenfell as an example, and the possibility of being spawned on a tiny island as opposed to the mainland). Obviously things like essential bridge building or terrain clearing in the first few turns can be a huge disadvantage, but becomes less of a drawback as the game develops.

What are trnWalkTerrain values, and how do they impact what we're talking about?

A fighting chance to gain an equal-ish number of TCs as your opponents is fairly crucial I believe. Obviously TC generation being a spatial algorithm that doesn't factor in terrain or water barriers can seriously skew this. Perhaps this is related to my above question. But if the nearby TCs that are intended for a certain player were determined as the horse rides rather than as the crow flies than this would be a lot better.

Hugely obvious point, but as we all know, the middle start positions can be pretty unforgiving. The main reason for this isn't spatial, but to do with the number of fighting fronts that must be maintained. On the one new map I designed I attempted to compensate for this with geographical features giving all 6 positions pros and cons, but in general, could/should these start points be compensated by having more TCs in their zone to give them a fairer shot?

Again obviously, some maps have been designed with the current system in mind (Sailors 20 20 and Pirate Hunger Games being good examples) so if a new system is achieved perhaps it would need a way of being turned off for maps which wouldn't benefit from it.

These combinations wouldn't work for a lot of maps and, more importantly, for at least some player count in I'd say most maps

That is completely correct, and a huge hurdle to overcome. While a 5 player set up could obviously be fairly playable with a quincunx arrangement (think the number 5 on dice) this would require an extra spawn zone 5 that overrides the two middle spawn zones to give the 5th player more space all round. As you say, 3 player set ups are very problematic. I often shudder in horror seeing people set up games with clearly the wrong number of players for the map in question, eg 6 players on Underworld, or 3 players in Abandoned Willage - I don't think we can legislate for people misusing the tools they have been given.

I'm not confident I have been any help at all I'm afraid, but that's all I got atm. I'll let you know if anything else occurs to me.

[b2198]

Once again, your mathematics has me running scared...
So I will play Watson to your Holmes, and pose a few questions and make some points, (mostly obvious ones unfortunately) in the hope of leading to some clarity.

Any help is better than no help

Firstly, a rhetorical question. Are you searching for a perfect solution? Clearly a very difficult undertaking and a very difficult goal - perhaps lowering your sights for just an improvement would be more likely to bring results. (for example, is a system of arranging players to be equidistant from the centre or equidistant from eachother achievable given the variety of maps in question?)

Yeah, I'll very likely need to allow way more combinations that are considerably less than ideal otherwise it would fail in too many cases. I've discussed this with Stratego already, and his idea was to make the code point this out in the output so that those maps can be tweaked at a later point.

Maybe it would be better to not look at this problem in isolation, but in conjunction with the TC generation issue as well - ie an imperfect spawn could be made a lot more playable with a better TC spread.

This is one of the steps for that, in this one, it's just deciding where to place the starting TC for each player, a better TC spread is also planned when the logic gets to that point.

I mentioned to you recently an appalling start I was given in a 1 on 1 that had no business to give such a skewed beginning because of the many better options available (I will send you a pic to fully show what I mean). That made me wonder if it would be possible to have minimum requirement checks for start points. Specifically things like minimum distance from another player, relative to map size. Or minimum adjacent free space relative to free space on the map (take Vaardenfell as an example, and the possibility of being spawned on a tiny island as opposed to the mainland). Obviously things like essential bridge building or terrain clearing in the first few turns can be a huge disadvantage, but becomes less of a drawback as the game develops.

There are already some requirement checks for individual tiles. That is what categorizes them as "good" or "bad", like in the images up there /\. In this specific step, it would also check for "least unbalanced combination of starting regions", that is, it would check every valid combination of starting regions and choose the one in which the regions chosen are the least different in value (but also above some minimum threshold too).

What are trnWalkTerrain values, and how do they impact what we're talking about?

Basically, the values you see when you press Speed on unit info.

A fighting chance to gain an equal-ish number of TCs as your opponents is fairly crucial I believe. Obviously TC generation being a spatial algorithm that doesn't factor in terrain or water barriers can seriously skew this. Perhaps this is related to my above question. But if the nearby TCs that are intended for a certain player were determined as the horse rides rather than as the crow flies than this would be a lot better.

Also planned.

Hugely obvious point, but as we all know, the middle start positions can be pretty unforgiving. The main reason for this isn't spatial, but to do with the number of fighting fronts that must be maintained. On the one new map I designed I attempted to compensate for this with geographical features giving all 6 positions pros and cons, but in general, could/should these start points be compensated by having more TCs in their zone to give them a fairer shot?

Well, those middle positions are very unbalanced in basically any FFA case, so the logic will try as much as possible to not use them, if there are better alternatives in those cases. But I can see them still being used in a 3v3 or 2v2, if I'm able to implement team combinations.

Again obviously, some maps have been designed with the current system in mind (Sailors 20 20 and Pirate Hunger Games being good examples) so if a new system is achieved perhaps it would need a way of being turned off for maps which wouldn't benefit from it.

Not really turned off, but if everything works as it should (i.e. if I can figure out the problems in this topic), the new logic will eventually settle on choosing those positions if they are the best option possible for those maps.

That is completely correct, and a huge hurdle to overcome. While a 5 player set up could obviously be fairly playable with a quincunx arrangement (think the number 5 on dice) this would require an extra spawn zone 5 that overrides the two middle spawn zones to give the 5th player more space all round. As you say, 3 player set ups are very problematic. I often shudder in horror seeing people set up games with clearly the wrong number of players for the map in question, eg 6 players on Underworld, or 3 players in Abandoned Willage - I don't think we can legislate for people misusing the tools they have been given.

Those zones will in theory cease to exist if this starts working properly. Also, in some maps, it's possible to distribute the players in a somewhat balanced way even for 3 or 5 player FFAs. There will also be some more tentatives to balance those positions in some other steps.

I'm not confident I have been any help at all I'm afraid, but that's all I got atm. I'll let you know if anything else occurs to me.

Again, any help is better than no help, thanks

[Endru1241]

I think the split into regions is wrong here.
Simulation 101 - get a model that could come from regression of reality, but still maintain relations.
First of all - when counting for complex calculations ordinary dimension split is not good representation.
The bigger chunk you get - the worse it shows reality.
So even if region split in such simple way would be used - 3x3 grid is at least falsifies reality somewhat less.
Here originally map size is perfectly divided by 5, but region creation needs to take into account what to do with remaining tiles and in such simple approach - I think most central zones should be given additional 1 or tiles.
But it's flawed for two reasons - positioning and distance.
Positioning of regions can sometimes split good starting position, but score it both of them are decreased significantly ( it's not really apparent in this map)
Distance has to be real unit movement distance and also it's not really a distance from enemy or map center that determines good position, but rather distance from most potential tcs.

Different idea would be to look for potential tc focal points by making a grid of values counting neighbouring probability, e.g. adding to tile probability modified by distance (e.g. *distance^0.3) probabilities of all tiles within movement distance of exemplary average unit. Maybe just with coordinates max +6, to make things easier (so +6,+0; +5,+1;+4+2; etc.).
Once knowing tiles with highest score in that - we should know average desirable central points of interest.
Not sure if it would come right though.
Maybe determining such points, areas needs to be made differently or maybe it's not a good idea at all.
But if such points are calculated there could be some algorithm to determine starting positions by average walking distance (real movement without simplifying of e.g. starting units) and walking distance to another starting point. Having sufficient space for mega construction around starting position should also be important point giving additional score.

[b2198]

I think the split into regions is wrong here.
Simulation 101 - get a model that could come from regression of reality, but still maintain relations.
First of all - when counting for complex calculations ordinary dimension split is not good representation.
The bigger chunk you get - the worse it shows reality.
So even if region split in such simple way would be used - 3x3 grid is at least falsifies reality somewhat less.
Here originally map size is perfectly divided by 5, but region creation needs to take into account what to do with remaining tiles and in such simple approach - I think most central zones should be given additional 1 or tiles.
But it's flawed for two reasons - positioning and distance.
Positioning of regions can sometimes split good starting position, but score it both of them are decreased significantly ( it's not really apparent in this map)

Good points. I've taken into account cases where the division would not be perfect already, by using modulus operator and distributing the extra 1 to 4 rows/columns needed.

Distance has to be real unit movement distance and also it's not really a distance from enemy or map center that determines good position, but rather distance from most potential tcs.

I had this one planned only for TC distribution, but I'll look into using it in this step.

Different idea would be to look for potential tc focal points by making a grid of values counting neighbouring probability, e.g. adding to tile probability modified by distance (e.g. *distance^0.3) probabilities of all tiles within movement distance of exemplary average unit. Maybe just with coordinates max +6, to make things easier (so +6,+0; +5,+1;+4+2; etc.).
Once knowing tiles with highest score in that - we should know average desirable central points of interest.
Not sure if it would come right though.
Maybe determining such points, areas needs to be made differently or maybe it's not a good idea at all.
But if such points are calculated there could be some algorithm to determine starting positions by average walking distance (real movement without simplifying of e.g. starting units) and walking distance to another starting point.

Hm, interesting idea, I might try it. What about determining balance of, as phoenix stated, number of fronts in this idea? So that central positions are way less likely to be chosen in FFAs, for example?

Having sufficient space for mega construction around starting position should also be important point giving additional score.

This one I've discussed with Stratego, and considered too complex to check for now, given that it would need to check for size of all megas in the variant, their trnWalkTerrain values and how terrain changes from one to another (by clearing forests, for example) in that variant. Could be done with some more arbitrary inputs, but I don't think it will be implemented in the first version of this logic, but could be implemented after the rest is working.

[Endru1241]

Different idea would be to look for potential tc focal points by making a grid of values counting neighbouring probability, e.g. adding to tile probability modified by distance (e.g. *distance^0.3) probabilities of all tiles within movement distance of exemplary average unit. Maybe just with coordinates max +6, to make things easier (so +6,+0; +5,+1;+4+2; etc.).
Once knowing tiles with highest score in that - we should know average desirable central points of interest.
Not sure if it would come right though.
Maybe determining such points, areas needs to be made differently or maybe it's not a good idea at all.
But if such points are calculated there could be some algorithm to determine starting positions by average walking distance (real movement without simplifying of e.g. starting units) and walking distance to another starting point.

Hm, interesting idea, I might try it. What about determining balance of, as phoenix stated, number of fronts in this idea? So that central positions are way less likely to be chosen in FFAs, for example?

That's what I meant by distances - walk distances to all other starting positions ( because if map has really hard to pass terrain blocking movement - even central positions become possible).

Having sufficient space for mega construction around starting position should also be important point giving additional score.

This one I've discussed with Stratego, and considered too complex to check for now, given that it would need to check for size of all megas in the variant, their trnWalkTerrain values and how terrain changes from one to another (by clearing forests, for example) in that variant. Could be done with some more arbitrary inputs, but I don't think it will be implemented in the first version of this logic, but could be implemented after the rest is working.

Well - it's only map generation, so something rather expected to take some time.
Algoriths here don't really need to be optimized for speed in any way.

[b2198]

That's what I meant by distances - walk distances to all other starting positions ( because if map has really hard to pass terrain blocking movement - even central positions become possible).

Ooh, got it, that's true, I'll try that later today (I'm going to sleep right now, it's 0:18AM here), seems like it could work really well.

Well - it's only map generation, so something rather expected to take some time.
Algoriths here don't really need to be optimized for speed in any way.

I didn't mean complex as in it would take a long time to run the code, but that it would be complex to implement in a way that's generic enough to be used in all variants, so I'll leave it for after the other parts of the logic are working properly.

[b2198]

Different idea would be to look for potential tc focal points by making a grid of values counting neighbouring probability, e.g. adding to tile probability modified by distance (e.g. *distance^0.3) probabilities of all tiles within movement distance of exemplary average unit. Maybe just with coordinates max +6, to make things easier (so +6,+0; +5,+1;+4+2; etc.).
Once knowing tiles with highest score in that - we should know average desirable central points of interest.
Not sure if it would come right though.
Maybe determining such points, areas needs to be made differently or maybe it's not a good idea at all.
But if such points are calculated there could be some algorithm to determine starting positions by average walking distance (real movement without simplifying of e.g. starting units) and walking distance to another starting point. Having sufficient space for mega construction around starting position should also be important point giving additional score.

Just did a bunch of tests with that... I don't think I'm doing this the right way.

I went tile by tile summing the probabilities of all other tiles times some multiplier, that based on distance, what I got was:
(note: I'm using tile distances for now, not movement distance, but it shouldn't matter for finding any focal points, and not actually finding the right ones, right? Also, for simplicity's sake, I'm only showing the results using both "good" and "bad" tiles combined)
Original:

• Multiplier = distance^0.3
• Multiplier = distance^(1/0.3)
• Multiplier = 1 / max(1, distance)^0.3
• Multiplier = 1 / max(1, distance)^2
• Multiplier = 1 / max(1, distance)^50

Is this an algorithm for blur or am I doing it in the wrong way? I'm already applying a gaussian blur on the scores, here is the full process:


And for the step of "Blurred Score" to ""Good" TC Probability Map", I should have specified there, but forgot. I'm storing the best score in the blurred scores and going tile by tile and updating it like this:

1. If the tile is not marked as possible in "Possible TC locations", its probability is set to 0
2. If the tile is not marked as "good" in ""Good" Tiles", its probability is set to 0
3. Otherwise, the score of the tile is set as 10 * (tile score/maximum score)^3

[Endru1241]

I made a mistake and wrote *distance^0.3, when obviously meant /distance^0.3
So actually Multiplier = 1 / max(1, distance)^0.3 is closest to that.
Maybe instead of max(1, distance) it could have distance +1.
It somehow is similar to Gaussian Blur.
But I don't know if the math behind is similar or it's only a coincidence.

But image looks quite what I thought about.
When on such 2d array of values local maxima are found - those would be focal points.
Don't know what math could be used though.

For this particular map I am not sure if it's 2 or 3 points, but viewing few more samples (more maps) parameters could be adjusted to go along with reality.

BTW. Making distance higher and higher makes Final value closing to score, because 1/x->infinity closes down to 0 leaving only those with distance 0 or 1 still significant.

[b2198]

I modified that idea a bit to get individual tiles in the map as focal points. Going back to the probability map step, I made it just copy from the blurred scores (and zero out impossible tiles) normalizing the results to the [0,10] range, but this time without elevating the results by 3 (and also ignoring "good" and "bad" tiles for now, for simplicity).

With this new probability map, I made a loop that gets 2 * number of non-neutral players (in this case, 2, so 4) focal points by doing the following:
For each iteration

1. Store the position of the first tile found with a value of 10 (in other words, the best tile)
2. Add the best tile to the focal points found
3. Update the values of all tiles , multiplying it by (distance to the best tile)^0.3 (so the entire area near the best tile gets increased way less than areas farther away), and store the value of the new best tile.
4. Normalize all tiles again to the [0,10] range, but this time using the new best tile as maximum

And it seems to work considerably well, at least for this map.

Modified Probability Map:


Iteration results:





End result:



Some thoughts:

• Maybe instead of using raw distance, using (distance / maximum distance possible to that point) would be better? It would make for a distribution that scales more properly with the map size.
• The last focal point found here was a "bad" tile, because it was on a corner, so I've been thinking, what if instead of using "good" and "bad" tiles, I just reduce the value of "bad" tiles directly in the preliminary score (and rename it, because it wouldn't be really a preliminary score anymore) by multiplying it by something like 0.25 or so? This would reduce the complexity of further steps and would make it so that if a tile considered "bad" is REALLY the best option left for a focal point in its vicinities (which could happen in theory), it will be chosen without any other logic needed.
• After making distances defined by unit movement, it would also work way better in water focused maps, because landmasses would be considered way farther apart than just their simple tile distance, and as such, more than 1 focal point being chosen in the same landmass would only happen with a high enough number of focal points in landmasses that are big enough for that.
• Water Bodies probably need a slightly bigger weight on scores. This map, while not the best for water, still benefits players who are nearby water quite a bit in the left and most of the central parts of the map.
• I should increase the gaussian blur size (and the size scaling alongside it? It already gets bigger on bigger maps, but I'm not sure if that scaling is properly tweaked right now), so that it takes into account more of the surrounding tiles, because in this case, the next focal point would be in the bottom right corner of the map, which is a terrible starting position because it's impossible to place more than 4 TCs there, and they would be glued together, making factory building a very slow and inefficient process for anyone that starts there.
• After this step is properly tweaked, the next step will be determining which combination of focal points is the best to use for that map, team configuration and player count, which is probably gonna be choosing the combination with least difference on player distances (based on unit movement), right?

[Endru1241]

3rd and 4th seem to represent much less important focal points.

For focal points there would need to be second parameter - something to represent how important it is (in effect how many tc would be generated there on average).

But I guess if just used as potential starting positions - they seem much better.

I haven't proposed any scaling with map size, as pure determination of focal points (with weights each) would just be another step before determining starting positions - I was thinking, that there can be smaller amount of focal points, than number of players (or much larger on larger maps) and they are also very often not really equal.
So instead of placing each player right in the center of focal point - place them in similar distance to focal points, on tile patch, that allows initial infrastructure.

BTW. Looking at those modified probablity maps it's obvious, that somehow this left upper corner tile gets too much probability somehow.
Using bad tiles increase could work, but imho they don't really take into account everything.
Apart of bad positions there are somehow bad - all those with only 1 adjacent position initially available (either obstacle, forest, water on sides).

Imho - size available should be more important, or maybe water tiles, like you suggest, because little island seems like interesting position to start on (and could be much better than 3rd one calculated depending on situation).

[b2198]

3rd and 4th seem to represent much less important focal points.

Probably due to the "bad" tiles + water score + blur size configurations, and also if everything works as it should, they would also be ruled out in the next step unless both are used, so that both players would have "almost equally bad" positions, but I think that should probably also be avoided.

For focal points there would need to be second parameter - something to represent how important it is (in effect how many tc would be generated there on average).

Yeah, I'm currently counting on the blur size increase to determine that, but if that's not enough, I might make an additional score to check something like that.

But I guess if just used as potential starting positions - they seem much better.

Yeah, placement of other TCs is still at least 3 steps further down the line.

I haven't proposed any scaling with map size, as pure determination of focal points (with weights each) would just be another step before determining starting positions - I was thinking, that there can be smaller amount of focal points, than number of players (or much larger on larger maps) and they are also very often not really equal.
So instead of placing each player right in the center of focal point - place them in similar distance to focal points, on tile patch, that allows initial infrastructure.

I'm not sure if this would be a good solution, because being in a similar distance from a focal point doesn't guarantee that one position is about as good as the other, even with the initial infrastructure space considered. Also, there can be as many focal points as there are tiles in the map, because with each focal point removed, some other tile will become the next focal point, yeah, some could be really better than others, and that's why in the next step the combination that's closest in terms of player distances and value will be chosen, if it works as it should.

BTW. Looking at those modified probablity maps it's obvious, that somehow this left upper corner tile gets too much probability somehow.
Using bad tiles increase could work, but imho they don't really take into account everything.
Apart of bad positions there are somehow bad - all those with only 1 adjacent position initially available (either obstacle, forest, water on sides).

Imho - size available should be more important, or maybe water tiles, like you suggest, because little island seems like interesting position to start on (and could be much better than 3rd one calculated depending on situation).

Yeah, I'll do a lot more testing after adjusting those parameters and see if it gets better.

[Endru1241]

3rd and 4th seem to represent much less important focal points.

Probably due to the "bad" tiles + water score + blur size configurations, and also if everything works as it should, they would also be ruled out in the next step unless both are used, so that both players would have "almost equally bad" positions, but I think that should probably also be avoided.

The problem is when first two players get almost equally good positions, two next - almost equally bad.
And only one of them is endangered by 2 way or even potentially 3 way battle.

For focal points there would need to be second parameter - something to represent how important it is (in effect how many tc would be generated there on average).

Yeah, I'm currently counting on the blur size increase to determine that, but if that's not enough, I might make an additional score to check something like that.

Blur size would work this out if there are real, concentrated focal points of required number, but reality of the map can be different.
You don't name something a peak if there is not at least 300m above surrounding area level.
That's why my thought was to only look for focal points above certain level of summed probability.
Not sure if with "Few" TC setting there is even significant enough chance for TC to be generated in those later ones.

But I guess if just used as potential starting positions - they seem much better.

Yeah, placement of other TCs is still at least 3 steps further down the line.

Then maybe I did misunderstood.

I haven't proposed any scaling with map size, as pure determination of focal points (with weights each) would just be another step before determining starting positions - I was thinking, that there can be smaller amount of focal points, than number of players (or much larger on larger maps) and they are also very often not really equal.
So instead of placing each player right in the center of focal point - place them in similar distance to focal points, on tile patch, that allows initial infrastructure.

I'm not sure if this would be a good solution, because being in a similar distance from a focal point doesn't guarantee that one position is about as good as the other, even with the initial infrastructure space considered. Also, there can be as many focal points as there are tiles in the map, because with each focal point removed, some other tile will become the next focal point, yeah, some could be really better than others, and that's why in the next step the combination that's closest in terms of player distances and value will be chosen, if it works as it should.

Imho the point is to have 3 main requirements met:
- similar average expected number of TC accessible with similar difficulty
- similar average accessibility to other players (to avoid one being in the middle or two being too close to start fighting when the rest safely expands
- similar minimum space for basic infrastructure
Of course then there goes choke points, accessibility to more infrastructure after clear terrain which could be harder to check.

BTW. Looking at those modified probablity maps it's obvious, that somehow this left upper corner tile gets too much probability somehow.
Using bad tiles increase could work, but imho they don't really take into account everything.
Apart of bad positions there are somehow bad - all those with only 1 adjacent position initially available (either obstacle, forest, water on sides).

Imho - size available should be more important, or maybe water tiles, like you suggest, because little island seems like interesting position to start on (and could be much better than 3rd one calculated depending on situation).

Yeah, I'll do a lot more testing after adjusting those parameters and see if it gets better.

And may the math be with you.

[b2198]

The problem is when first two players get almost equally good positions, two next - almost equally bad.
And only one of them is endangered by 2 way or even potentially 3 way battle.

Very unlikely to happen if I get both this and the next step working properly, because every player would be checked against every other player for every combination of focal points, so that is only gonna happen if exactly 0 combinations of focal points are at least somewhat balanced for all players.

Imho the point is to have 3 main requirements met:
- similar average expected number of TC accessible with similar difficulty
- similar average accessibility to other players (to avoid one being in the middle or two being too close to start fighting when the rest safely expands
- similar minimum space for basic infrastructure
Of course then there goes choke points, accessibility to more infrastructure after clear terrain which could be harder to check.

I can guarantee the first one for almost any case when it gets to that step, unless I really messed up my line of thinking for that. The second one depends heavily on whether I get both this and the next step right. The third one I can't guarantee with the current logic, the blur size increase should help in that regard, but I might need to add an additional score that checks for that.

Choke points would indeed be a harder one to check, but I think could be another score to add in the future.

More infrastructure after clear terrain is somewhat already kinda working, but not nearly as well as it should, and it has no checks for megas specifically, so could be improved a lot after the rest starts working.

And may the math be with you.

Thanks for the help

[Hyuhjhih]

There are already some requirement checks for individual tiles. That is what categorizes them as "good" or "bad",.........

I'm thinking about a similar thing. Like adding 'tile value' and 'distance value' (probably considering the movement of either a land or water unit, but not flying units) so that the map checks the value between each tc is similar(or approximately similar) so, they are somewhat equidistant or equally resistant in terms of reachability.

[b2198]

There are already some requirement checks for individual tiles. That is what categorizes them as "good" or "bad",.........

I'm thinking about a similar thing. Like adding 'tile value' and 'distance value' (probably considering the movement of either a land or water unit, but not flying units) so that the map checks the value between each tc is similar(or approximately similar) so, they are somewhat equidistant or equally resistant in terms of reachability.

Yeah, that's what I'm thinking to do for the next step.

[b2198]

Ok, after some more tweaks, I've changed a bit some of the scores (and removed 2 of them), made the focal point score drop being exponentially higher near the chosen focal point, instead of using a polynomial function, and adjusted the weights and inputs, and asked for the first 8 focal points it could find, these were the results:


What do you think? Are those good candidates for starting positions? (disregarding the number of players in the match for now, since that's the next step in the logic, choosing which combination of these would be the least unbalanced for all players involved. Also, 8 was just an arbitrary number, I don't know yet for sure how many are needed to have enough, but not too excessive choices for a given player amount)

(Also distances for focal point calculations are still tile based, not movement based, I'll change that after the tests are automated, and some focal point choices will probably change due to this)

What I'm gonna do now is do some more heavy automation in my tests, so that I can change parameters and maps and have a complete test done within seconds, instead of spending a few minutes doing ctrl-c ctrl-v and then a few dozen more assembling everything together in paint every time I want a complete test file, taking up around ~15-30min per test. When that's done, I'll test with a bunch more maps to see if it's working as it should in them too.

[Endru1241]

Purely for this map 0 seems like real central point of interest - most important focal point and while player starting there would have biggest number of tc available and would have huge advantage in any 1 vs 1 situation from 3 players up - it's like he's bound to loose.
1, 2 and 5 are possibly greatest positions, unless screwed by two-pronged attacks.
The rest seems like more or less good if distances to 0 would be maintained similar, so 3 vs 4 and 6 vs 7 seems good.

Well - it would have to be tested on few more maps, but from what I see focal points being too much in the center should be left as targets for equidistance calcs, but not used as potential starting positions.
So maybe if those with highest scores would be considered last it could work?
Something like - generate few focal points more than number of players, take most central, possibly highest scored few out of equation and try to randomly assign starting positions with similar distance to those?

[godOfKings]

I know its kind of extreme thought process, but what about changing the roadmap of the future of ao games in this direction? https://www.ageofstrategy.net/viewtopi ... &t=11598

[b2198]

Purely for this map 0 seems like real central point of interest - most important focal point and while player starting there would have biggest number of tc available and would have huge advantage in any 1 vs 1 situation from 3 players up - it's like he's bound to loose.
1, 2 and 5 are possibly greatest positions, unless screwed by two-pronged attacks.
The rest seems like more or less good if distances to 0 would be maintained similar, so 3 vs 4 and 6 vs 7 seems good.

Yeah, 0 looks like the best position for a 1v1 by far. 1 vs 2 looks the most natural to me for 2 players, but those others also seem to be good.

Well - it would have to be tested on few more maps, but from what I see focal points being too much in the center should be left as targets for equidistance calcs, but not used as potential starting positions.
So maybe if those with highest scores would be considered last it could work?
Something like - generate few focal points more than number of players, take most central, possibly highest scored few out of equation and try to randomly assign starting positions with similar distance to those?

Maybe, would need more tests to tell if that could work in the next step, I'll give an update on that when i get there. Maybe the combination checks will already rule out those as being unbalanced for those cases, though, not 100% sure. Also there might be some maps where those positions are actually balanced, but I don't remember any from the top of my head right now.

[Endru1241]

Purely for this map 0 seems like real central point of interest - most important focal point and while player starting there would have biggest number of tc available and would have huge advantage in any 1 vs 1 situation from 3 players up - it's like he's bound to loose.
1, 2 and 5 are possibly greatest positions, unless screwed by two-pronged attacks.
The rest seems like more or less good if distances to 0 would be maintained similar, so 3 vs 4 and 6 vs 7 seems good.

Yeah, 0 looks like the best position for a 1v1 by far. 1 vs 2 looks the most natural to me for 2 players, but those others also seem to be good.

5 is in moat cases equivalent to 2. Unless facing 2.
Take 5 vs 4 or 5 vs 6 as an extreme case of unfair advantage.

Well - it would have to be tested on few more maps, but from what I see focal points being too much in the center should be left as targets for equidistance calcs, but not used as potential starting positions.
So maybe if those with highest scores would be considered last it could work?
Something like - generate few focal points more than number of players, take most central, possibly highest scored few out of equation and try to randomly assign starting positions with similar distance to those?

Maybe, would need more tests to tell if that could work in the next step, I'll give an update on that when i get there. Maybe the combination checks will already rule out those as being unbalanced for those cases, though, not 100% sure. Also there might be some maps where those positions are actually balanced, but I don't remember any from the top of my head right now.

But still - most maps are designed so that 20%-50% of the map at center is main battleground.
Of course there those positions could be removed as starting positions by some walk distance comparisons between other starting positions, but whatever the case - in any at least 3 player game the position that most players can reach in similar time, while other positions have vastly higher average walking distance to enemy starting positions is bound to be attacked from at least 2 sides.
Let's take extreme case here - 4 player game and they took positions 0, 1, 2, 3.
0 is screwed.
From the rest- the one that will manage to take most advantage is probably gonna win (much lower chance for 3).

One of the main reasons behind any talk about tc placement and random positions was exactly to avoid such situation.

Of course - I don't mean that it has to be parameter center of the map - rather walkRange center between starting positions - that should be avoided.
But even avoiding parameter center would in most cases prevent many weird placements.

[b2198]

Ok, after spending about a week solving some issues in the bridging algorithm for the AI, and being busy in a new job these last two weeks, I finally managed to complete the first version of "semi-automated" tests, which can be done in as few as 30sec if everything else is already set up beforehand (the input file for the Java code to read, the data output from the Java code for the Python code to read, and the image operations to build the test report in the Python code). Now I'll start mass testing the maps with the current logic.

First test: Riverside


Distance is still tile-based, I didn't change that part yet, and I actually don't know for sure how it's gonna be done, because in other variants (and in AoS to a lesser extent if/when Cultures are implemented) unit movement might be different for different players, and I'm not certain on how the code will handle that without even knowing beforehand which players will have which units. Any clue on this?

Also I'll do a small change on focal points, instead of showing as booleans based on their position, the tests will show their actual score, because they will almost always have different scores from each other, which will be considered when comparing their combinations, and just showing their positions is not helpful to communicate that. Also also, I'll probably do some tweaks with the formula used for distance, because I feel like it's affecting scores far away more than it should, so probably a bigger base and decreasing the coeficient on the exponent should do, so that closer scores are affected more and farther scores are affected less.

[b2198]

Also also, I'll probably do some tweaks with the formula used for distance, because I feel like it's affecting scores far away more than it should, so probably a bigger base and decreasing the coeficient on the exponent should do, so that closer scores are affected more and farther scores are affected less.

Seems a little better now.
previous formula: 1 - 1/2^(0.5*distance)
now: 1 - 1/4^(0.3*distance)



...Also I should include these numbers in the test report itself too, will do that (and the focal point display changes) later today.

[godOfKings]

I m sorry i want to help but my brain aint big enough to contain all this information

[b2198]

Ok, changes done, and 5 more tests done (and the first one redone):

Riverside:


Tropical Islands:


Tropical Ocean:


Perilous Realm:


Indogletser:


Aerolian:


notes:

• The focal points are not necessarily starting TC positions, just possible locations in which they could be distributed in the next step (which is the one that will be actually responsible for making things like player count and teams as balanced as it can based on these, and will use their score and distances relative to each other in that decision)
• The player count is not taken into account yet, I'll probably have to test and tweak to see how many focal points to choose for each player count
• Riverside, Tropical Islands, Tropical Ocean and Perilous Realm seem fine for me in terms of focal points.
• Indogletser is a weird map, but by being a weird map it showed some issues with the water bodies part of the score, in regards to multiple disconnected water bodies. I already have that noted, but this change will most likely be delayed for after the first functional version of the algorithm, since it's a rare occurrence afaik, and is not a critical problem for now.
• Aerolian is also a weird map. I'm not sure if those focal points are good for it, but they seem good enough when looking at the next candidates in iteration 7. What do you think?

I m sorry i want to help but my brain aint big enough to contain all this information

Mine isn't either lol, that's why I'm struggling to get it done

[makazuwr32]

Indogletser:
This one might probably be fine for me.

Aerolian:
That one indeed is somewhat weird.
Especially the fact that it does exclude still passable bottom left and top right parts.

[Endru1241]

Indogletser:
This one might probably be fine for me.

Aerolian:
That one indeed is somewhat weird.
Especially the fact that it does exclude still passable bottom left and top right parts.

It doesn't exlude.
This algorithm is showing 8 most desirable locations - those with biggest chance to have TCs.

For those maps it's just logical to really have more focal points, while riverside or tropical islands - less.

Ok, changes done, and 5 more tests done (and the first one redone):

Riverside:


Tropical Islands:


Tropical Ocean:


Perilous Realm:


Indogletser:


Aerolian:


notes:

• The focal points are not necessarily starting TC positions, just possible locations in which they could be distributed in the next step (which is the one that will be actually responsible for making things like player count and teams as balanced as it can based on these, and will use their score and distances relative to each other in that decision)
• The player count is not taken into account yet, I'll probably have to test and tweak to see how many focal points to choose for each player count
• Riverside, Tropical Islands, Tropical Ocean and Perilous Realm seem fine for me in terms of focal points.
• Indogletser is a weird map, but by being a weird map it showed some issues with the water bodies part of the score, in regards to multiple disconnected water bodies. I already have that noted, but this change will most likely be delayed for after the first functional version of the algorithm, since it's a rare occurrence afaik, and is not a critical problem for now.
• Aerolian is also a weird map. I'm not sure if those focal points are good for it, but they seem good enough when looking at the next candidates in iteration 7. What do you think?

I m sorry i want to help but my brain aint big enough to contain all this information

Mine isn't either lol, that's why I'm struggling to get it done

I agree that this point is probably done.
To be sure we could look into few more open big maps if it's not a problem.

[b2198]

I agree that this point is probably done.
To be sure we could look into few more open big maps if it's not a problem.

Here's Great Greenfields:

For those maps it's just logical to really have more focal points, while riverside or tropical islands - less.

Yeah, the amount of focal points will probably depend not only on player count, but on map size too, I'll look into that when making the next step.