Caster of Magic II Brainstorming Megathread

[massone]

It picks units that are at most distance X from the first. If there are at least 8 of those, that's success, if there aren't, that's fail.

Okay, I understand now, but to "find best units within range X" sounds like a very computationally expensive algorithm.

Range X is centred on a unit which could be anywhere on the map. That means you need to calculate distance from that unit to every other unit owned to determine which ones are in range X, before you can sort them according to their strength.

This sort is also an extra operation, because you have to do a new sort on a unique array of units "within range" that this algorithm generates every time it runs, instead of the global array ranking which you can do once and iteratively update every turn once at a much smaller cost. It's even worse if the success condition fails and you have to recalculate everything all over for the 2nd best unit after you remove the bestUnit from the list.

The extra sorting alone is likely to be at least O(n log n).

Maybe I misunderstood but you didn't specify to do that.
You specified to pick he great drake then the 8 bats, then replace the bats one at a time with a better "modifiedvalue" in other worse a closer unit. If there are no closer units, the drake and 8 bats will be picked, even if the 9 bats could have been because we aren't iterating this for every unit, only the first one.

But you are right, if we loop this process picking each unit on the list as "best unit" and using their position as the "build spot" then it does work and it only takes n^2 time which is still okay, at least it looks ok at first sight.
I'm not very comfortable with it assuming buildpoints that aren't going to be the actual buildpoints.

Yes, you've misunderstood. I am not suggesting to loop through all the units, and the algorithm would not pick the Great Drake on the second turn. If you apply the algorithm without considering the turn progression, yes it will have weird results. But the algorithm is meant to work continuously every turn, and is complexity O(n).

Since you don't like assuming the "build spot", let's just rename it "stack reference position", because that's what it really is, a way to do the distance calculations efficiently.

Before the Great Drake is summoned, the algorithm already ran. To simplify things, we'll say that on some arbitrary turn T1, the algorithm caused a stack of 9 doom bats to be formed at positionX, which we'll call stackX.

stackX thus calculated modifiedValue("unit", "stack_reference_position") inputting modifiedValue(STRONGEST_UNIT[ARRAY_INDEX], X)  for each of the doom bats, using X as the reference position for the distance modifier calculation. The algorithm stores a sumOfStackValue with these modifiedValues.

On turn T2, the Great Drake is summoned far away at position Y. The algorithm thus attempts to run through all the steps. It finds the next 8 best units on the global, unassigned (as in, not doing anything) strengthValue only, finding the doom bats. Then it calculates distance for the 8 doom bats only, and the modifiedValue centering on position Y. This outputs penalized modifiedValues because X is far from Y.

Reaching step 6, the algorithm thus compares the sumOfStackValues(stackY) against sumOfStackValues(stackX) stored from the previous turn. It finds that sumOfStackValues(stackX) is bigger because the stackY modifiedValues were heavily penalized by distance.

Thus, it retains the stackX instead of starting a stack at Y. At which point, I did not state it in my original post, but the algorithm should run again using stackX. Ideally, the whole stackX was stored and the algorithm checks that, skipping steps 1-3 and going straight to step 4. Otherwise, it needs to use the old bestUnit and run through the steps with it.

Now step 4 requires that it find the next best unit on the global ranked array. It starts from the top of the rank, and excludes any unit which is already in the stack. At the top of the rank, it finds the Great Drake, which is new. It calculates distance to the Great Drake centering on X, finding an individual modifiedValue(GREAT_DRAKE, X) that is bigger than modifiedValue(DOOM_BAT, X) of the weakest doom bat, despite the distance penalty.

Thus, it replaces the doom bat with the great drake, so the great drake "goes" to join the main doom bat stack.

But what really happens is that all units converge. It is not necessary to make them go to X. That's just the fastest computation. But you can make them go to the geometric median instead, in which case all will be closer to each other. You did say that the game normally sends selected units to the "average position" anyways, right? I did not originally suggest it because even the fastest known algorithm to find the geometric median discovered in 2016 was only "nearly linear time" and fairly obtuse to understand, while the most well known Weiszfeld's algorithm sometimes doesn't even converge and is extremely slow. But if there is already a decent implementation in the game, there's no reason not to use it.

Ultimately, the method of unit convergence is independent of the algorithm for identifying the units required in the stack.

Considering your examples after that you asked about:
example#1, if you use the geometric median as the rally point, they are the same.

example#2, the algorithm would have the stack reference point where the main 7-stack already was, then pick the north unit and one of the south units as the closest units to add to it, and all move towards the rally point.

[Seravy]

Range X is centred on a unit which could be anywhere on the map. That means you need to calculate distance from that unit to every other unit owned to determine which ones are in range X, before you can sort them according to their strength.

No, the plan is to sort them first, then simply skip selecting the units that are not in range X.
Range is trivial to calculate, it's max(abs(x1-x2),abs(y1-y2)).
So it would be like "for i:=1 to listsize do if range(list[i],list[best])<X then select(i); stop after then 8th selected."

Yes, the time will be around nlogn. That's fine. Selecting targets to attack is much slower.

But I realized, mine had a problem. It shouldn't delete the best unit from the list when it found no group of 9 using it. It should keep the unit on the list but start finding a group using the next unit.

[massone]

Range X is centred on a unit which could be anywhere on the map. That means you need to calculate distance from that unit to every other unit owned to determine which ones are in range X, before you can sort them according to their strength.

No, the plan is to sort them first, then simply skip selecting the units that are not in range X.
Range is trivial to calculate, it's max(abs(x1-x2),abs(y1-y2)).
So it would be like "for i:=1 to listsize do if range(list[i],list[best])<X then select(i); stop after then 8th selected."

Yes, the time will be around nlogn. That's fine. Selecting targets to attack is much slower.

But I realized, mine had a problem. It shouldn't delete the best unit from the list when it found no group of 9 using it. It should keep the unit on the list but start finding a group using the next unit.

Yes, you're right. I was thinking in terms of pythagorean distance, which would be O(n log(n)^2) because of the sqrt() function. But the game treats diagonals as 1 move, so that max() of horizontal/vertical distance works very well. And if you sort global and exclude not in ranged, this would be fairly efficient.

[Seravy]

One more :

28. AI offensive Transmute

Basically, change Adamantium on enemy cities into crystal.
Might reduce ore relevance too much, as it means not only Chaos but also Nature wizards will disable your ores.
9 out of the 15 default wizard templates have either Chaos or Nature which is 60% but even a single random book or two can add the spell so the real rate is closer to 70-75% chance per opponent that they will destroy the player's ores.
With Chaos only, this is a much more reasonable 33%+random books chance so probably around 40% total.
I think those numbers are convincing enough that we don't want Nature AI to do it.

[massone]

One more :

28. AI offensive Transmute

Basically, change Adamantium on enemy cities into crystal.
Might reduce ore relevance too much, as it means not only Chaos but also Nature wizards will disable your ores.
9 out of the 15 default wizard templates have either Chaos or Nature which is 60% but even a single random book or two can add the spell so the real rate is closer to 70-75% chance per opponent that they will destroy the player's ores.
With Chaos only, this is a much more reasonable 33%+random books chance so probably around 40% total.
I think those numbers are convincing enough that we don't want Nature AI to do it.

My opinion is that it's not an issue of how often it happens. It's the cost vs. impact. Raise Volcano and Transmute are too cheap for the impact have, especially Volcano because it's permanent and irreversible. If the AI doesn't do it, it's a handicap. On Arcanus, where there's often only 1 natural Adamantium on the whole map even on rich settings, a 40 MP spell destroying it is quite excessive.

Aside from ores, the only other resources are just abstract numbers (gold and Power), where more is better, and scales directly with number of towns. There's no sense of a "strategic" resource or geographic competition if the ores can be too easily destroyed, or made obsolete by vastly superior fantastic units too soon. Even nodes aren't real strategic positions that needs holding--it's just another source of Power and the fact that it's easily substituted or ignored with town Power sources means it doesn't really matter when you lose one to an enemy.

The same logic that says Dispelling shouldn't be the main answer to stop all spells--because it becomes a contest of who has more mana--applies the same to destroying unique strategic resources.

I would propose that you consider rebuilding the system to move in the other direction. Make ores into the basis for a "Reagent" system, which requires that certain spells need strategic resources to be researched/cast. Therefore you cannot win simply by being bigger all the time and having more stuff, and you cannot dispel everything with pure mana. You need obtain and hold strategic reagents. You can also add in conditions that certain summons can only be performed within the vicinity of strategic locations, such as nodes and towers. Units can only be buffed with overland enchantments when in the vincinity of relevant ores, towns, or associated nodes, etc.

[Seravy]

Ores have low relevance because they are not strategic - they are random.

Having Adamantium (or Gold) doesn't mean you are a better player, it means you had better luck on map generation, for the first half of the game. (beyond that it still only means you're not an AI player and can actually see what resources the cities you attack have before deciding where to go. Unless you have Transmute but that's an entirely different thing.)

However games can't always play the same - would be boring - so some element of luck is necessary, but it can't be too significant. Ores fill this role.

Chaos magic destroys ores because that further reduces the relevance of ores, but not so much to make it entirely irrelevant, in fact does so by adding layers to gameplay - if you want to keep that ore, you have to stay friends with Chaos wizards or prevent their units from finding that city. Yes, destroying ores is powerful, but there are ways around it. However, this only really works as a feature if the number of enemies being able to destroy those ores is manageable.

The system you are suggesting penalizes AI players heavily - they attack things based on where they can win a fight, not based on terrain features so they'll miss those important resources most of the time. It also increases the luck factor to undesirable levels - should I really lose the game because my continent had no Horse resource so I cannot build Cavalry, Knights and Paladins?

It also simply doesn't have the right "feel" to it - I'm a powerful wizard, so I shouldn't depend on (strategic) resources to cast my spells to that extent.  It's fine if my troops, heroes or cities depend on these resources - those minions are just minions, of course they need that better sword to be more effective.

[massone]

I would say whether or not luck and randomness are "strategic" depends your perspective. I don't see it as being a replayability issue. Instead, I consider them key distinguishing features of strategy war games. It's one of the fundamental divides, alongside imperfect information and flavor, between abstract strategy games like chess and wargames. You don't go to war with the army you want. You go to war with the army you have. But it's a form of randomness that can be contested--resources can be fought over and acquired, and strategic resources remain key concerns in geopolitics today.

The question is which part of the spectrum should CoM fall into?

The truth is that map generation is already very unequal, even without ores. Because you can get stuck with a Fortress of sub 15-pop rather than a >25 pop spot. In the early game, it's a tremendous difference and leads to widening differences due to exponential growth in settlement. This is okay, because like ores, you can correct this problem by going to war, conquering good territory. That is the way most states in history averted Malthusian catastrophe when efficiency gains from technology were not an option.

Something like the randomness of spells in the spellbook, and in particular, the order in which they appear, is different. That's not a problem you can correct by going to war. It's just a pure dice roll that has nothing to do with player ability. That has a different justification--because research should be somewhat random to simulate imperfect information "at the time of researching", despite having metaknowledge through wiki/manual/replays. On this, despite the problems it sometimes causes, it's a big positive factor for the game compared to the fixed tech trees other games use.

The system doesn't penalize the AI. The system doesn't yet have an implementation, so of course the current AI hasn't been programmed to handle it. A valid argument would be that it's difficult to program the AI for the new system. But, I'd also say that a better AI for prioritizing targets through weighing strategic desires is an equally good feature, even independently.

The "feel" for flavor is a personal preference that I can't argue against. Magical reagents are by no means unusual in literature or games. Almost the opposite really, they're practically a staple. It's MoM that's unusual, especially with enchanting items not even requiring any base components.

Ultimately, all I can really say here is that the random map generation and random spellbook aspect of MoM are major selling points of the game for me. And in other games, good strategic resource management systems are also strong selling points. Hearts of Iron, Victoria 2 had some of the most complicated and impressive systems. In other game especially RTSes, strategic resources have served as a way to create choice as resources were limited, unlike MoM where gold and mana generated from nothing. Or in recent Civ's design decision, to create the dynamic that players must fight for limited strategic resources. It's a more relatable and fun mechanic because of the real world connection, in which many wars were fought over strategic resources, trade routes, etc. And in wars, denying opponents' access to those resources was also important--but they often couldn't destroy the resource itself, only the infrastructure for using it.

[Seravy]

The question is which part of the spectrum should CoM fall into?

There is another, less obvious question before that - what IS the army/strategy in this game?
Fantasy/Magic. Not your normal troops produced in your cities.

Your "army" in this case is your spellbook. The spells in them are your main strategic resources, and are randomly determined based on your starting picks in a balanced manner - you can be sure there will be enough to win the game, but it won't be always what you expect (unless you take 10 books but even then the order will be still random beyond uncommon). So there is the main "wargame" mechanic. I suspect the reason why every other fantasy 4X failed to be as good as MoM is because they placed too much relevance on generic 4X mechanics and not enough on magic becoming the thing you base your strategic decisions on.

The truth is that map generation is already very unequal, even without ores.

Only for CoM 1. For CoM 2, there will be a minimal and maximal terrain quality for fortresses instead of just a very low minimal one. It will be a wide range, and only applies to the starting city but it is enough to let the conquering do the balancing afterwards, as you say. The important difference is ores will be included in "terrain quality" so you might still get 2 starting gold ores, or a max pop 25 city, but you won't get "max pop 25 with 2 golds and two mithrils". In CoM 1, ores play no role in starting location at all.

A valid argument would be that it's difficult to program the AI for the new system. But, I'd also say that a better AI for prioritizing targets through weighing strategic desires is an equally good feature, even independently.

True, I meant it that way. To be specific the AI does pick the highest value target among targets it can attack, but "can attack" only extends to targets it is expected to beat in a single battle, when picking a destination for a stack nearby. It cannot plan ahead, build 2-3 stacks of units with the specific purpose to conquer a strategic target like humans and even if it could the human player would intercept and damage/kill those stacks before they reach the city.

I'll go further - the game mechanics of this game do not allow for placing a large importance on any single tile of the map. The attacker can attack the tile with many stacks in the same turn without the defender being able to refill their garrison. So it's (sometimes) impossible to defend a specific city as long as the other player commits enough effort into attacking it and the armies aren't killed on the way there. This is why banishing wizards had to be toned down to have a less severe penalty as well.

Speaking of which, having to defend your fortress means we already have a "this city is important" game mechanic - in fact considering human players usually only build their best military units at 1-2 places at first they already have enough critically important locations to defend. Losing either will likely lead to defeat on the long term. That leaves the "what to attack" decision.

In this game, you have enough factors that determine which player you attack already as well. There is diplomacy, the weaknesses and strengths of your realm(s), which enemies have stronger late game potential, who has curses, and even what your troops can or cannot do. I don't think a critically important resource helps, as there are already plenty of reasons why you should or should not attack a specific enemy at a given time. In games with more generic troops, no fortress, a more forgiving diplomacy system and a global techtree, strategic resources can be the main determining factor for selecting a location to attack or defend, but here we have enough other game mechanics to cover that.

[Seravy]

29. AI node scouting system

Basically the same thing the AI uses to determine if they have seen a city to target it with a curse, but for Warp Node. If added, it will not be used for anything else.
Magic Spirits will be limited from going too far from the AI's own territory (to avoid making long distance diplomacy contact without a reason) but that will be independent of this.

[massone]

I really don't think the AI should be limited from long distance diplomacy, if the human player isn't. The human player would always scout as far as possible for trading and to find lairs, so the AI should too.

If the concern is alliances ganging up on the human, a better solution that isn't unfair to either human or AI would be to apply for acceptance calculations:
-a negative modifier for for every existing alliance the recipient already has
-a negative modifier for every existing alliance the offeror already has, which is not already allied to the recipient, and inversely scales with relation to that other "indirect" potential ally
-a positive modifier for every existing the offeror already has, who is already allied to the recipient
-a positive modifier for the size of the largest known alliance bloc both the recipient and offeror are not part of, as measured by military and power ratings, not quantity of wizards

This needs to be apply to both human-AI and AI-AI alliances. This has the following effects:
-Wizard A is more likely to ally B when B neither have other allies
-If A and B are already allied, they are less likely to ally others because it's less necessary
-C will be less likely to ally A or B because each would cause C to be indirectly allied with the other (with more resistance if C and the other wizard have hostile relations, and less if they are also friendly), matching A and B's less likely chance to be willing to accept C
-If C successfully overcomes the mutual negative modifiers and allies with either A or B, they naturally form a triple-alliance, but becomes even more resistant to anyone else allying any of them
-If there is another alliance bloc, both blocs will suffer large negative modifiers from any of them allying to the other bloc as a result of the above interactions
-If there is a larger known alliance bloc, all wizards are more willing to ally together to counter the threat of the larger alliance bloc by forming an equally large alliance
-The "size" of an alliance bloc in the threat calculation is measured by military rating or comprehensive power rating, not by quantity of wizards.

This will simulate natural alliance formation and retain balance of power multipolar dynamics, as well as the possibility of "world wars" instead of everyone ganging up on one (unless they're too powerful, in which case they definitely should gang up).