Weighted difficulty for Endless levels generation

[Cwpute]

As previously mentioned in issue #95 , i think Endless could benefit from having its levels generated based on an expected difficulty level, that could be weighted based on a lot of different variables. Each variable alone would have a set value that could all be summed up (or more broadly, calculated) into what we would call "level difficulty", which level generation would then use to determine what level to generate next.
I'll just copy-paste my initial list here so we can discuss it further, if anyone is interested.

1. Attacker spawn points: managing a single entry point is different from managing 3 or 5! they complexify chip placement and chip spot hierarchy.
2. Entry lanes into the CPU: same as with previously, different lanes accessing a single CPU also multiplies the number of chips needed to achieve the same damage output.
3. Number of CPUs: same as the two previous points…
4. Number of chip placement spots: as the levels get harder, you'll need more chips to efficiently dispatch the attackers, so reducing the number of spots inherently reduces the potential for defense ! the contrary is also true: more chip séots means easier levels.
5. Independant lanes: having independant lanes requires yet more ressources for dedicated chips.
6. Number of cryptocoins: cryptocoins can be realy hard to tackle if you use many MEM chips. I believe this is already randomly chosen, but it can provide a challenge is later levels if you have to manage let's say 3 different cryptocoins on 3 different lanes.
7. Alternate paths: if you generate alternative chip paths in your level (alternative ways attackers travel through lanes), this should also weigh in in the level's difficulty, as this creates unexpected attacker behavior that could throw the player off and require them to reconsider their strategy.
8. Branching lanes: a single lane separating into two lanes creates are more complex level, and increases its difficulty. Merging two lanes does so as well, but to a lesser degree (as you need to manage, buy and upgrade less chips for the same amount of attackers).
9. Lowest number of chips between a spawn point and a CPU: probably my most feared feature in a level is a lane only passing through 2 chips before reaching the CPU. This shortest possible path should probably be taken as the basis on which to build the rest of the level's difficulty.
10. Lane lenght: different from the previous point, as this is about the actual lenght of the paths, rather than the number of chips it contains. You can have a really long lane with only two chips, that is manageable because you can tap on the attackers to reverse them, and a super short path with 3 chips that is harder to manage because you can't tap on them at all, and you have to rely on your chips efficiency rather than your own ability to react.
11. Wave diversity: diverse ways makes for a more difficult level you have to adapt to, while similar waves only test your current chip setup resistance.

[Cwpute]

Mostly, this is all about effective difficulty (what makes a level actually difficult), but we should probably also tke into account perceived diffiuclty (what players perceive as difficult to tackle).

For example, branching lanes can look mazelike in most current endless levels, and it makes for a lot of the difficulty in these levels. But play that same level several times, and you'll probably have the attacker paths memorized, rendering this initial perceived difficulty obsolete. Same goes for uneven waves of attackers, or attacker spawn points that don't output the same number of attackers: they are initially difficult to work with, but once you know which lane to prioritize, or when and where to place down you chips, then they become easier to deal with.

So i think these points should be recognized and taken into account, but probably to a lesser extent

[Cwpute]

Maybe perceived difficulty could be referenced as "Complexity", and applied after most other important variables have been calculated, as some sort of slight multiplier ?

[Cwpute]

Something i think should be our basis of calculation is the most menacing path aka. the shortest path attackers can take to reach the CPU. Combined with the speed, power and number of attackers that will take this most menacing path, it will make for a first strong reliable marker for level difficulty, until we find more variables to integrate into it and play around with.
What do you think ?

[ochadenas]

In fact, it is a bit like that now. The length of paths is taken into account. But perhaps not enough.

Currently (1.32) the endless levels work like that:

A basic layout is generated: empty slots, links between slots, and possible paths. If there are "lone" chips, they get removed.

If the shortest path contains less than 4 links (i.e. 3 possible slots), the layout is discarded and created anew. Then the average length of paths is calculated. The "difficulty" of the layout is 8 - (average path length). That is, the longer the paths, the smaller the difficulty; the value may drop below 0.

The "target difficulty" for the level is 2 * √(level). If it is greater than the actual calculated difficulty, then a number of undesired chips are created and randomly placed, so that the sum of their weighted difficulty makes up for the difference (approximately, not exactly). Where "weighted" means from 0.5 (NOP) to 2.0 (DUP).

Example 1

You are at stage 50, which means that the target difficulty is 2*√50 = 14.1. A layout is created with an average path length of 5.6, yielding a basic difficulty of 2.4. Then we'll need to place 11.7 "worth" of negative chips. You have Kilby at level 4, which reduces this value to 7.7.

The game then randomly creates some chips:
DUP
ADD
ADD 2
SHL 2
NOP
which sums up to 2 + 1 + 2 * 1 + 2 * 1.2 + 0.5 = 7.9.

At stage 100, the target difficulty is 20, so approx. 6 additional negative chips will get placed or upgraded. In fact, an ADD 2 counts the same as two ADD 1.

Example 2

You are at stage 9, which means that the target difficulty is 2*√9 = 6. A layout is created with an average path length of 6.2, which means a difficulty of 1.8 (the longer the paths, the less difficult). This means 4.4 negative chips to be placed. If you have Kilby at level 4, this means one undesired chip. A NOP would do, but it can also be any of the others.

[Cwpute]

Thanks a lot for this in-depth insight, and swrry to have you all explicitely write it down in plain english ! As i said before, maybe sometimes i should dive into thi code myself to tweak things and see for myself.

I'll take some time another day to properly answer, but i feel what could be done is take each lane lenght and difficulty separately instead of averaging them… i'll give it some thought!

[ochadenas]

In 1.34, there have been some more changes in the calculation, and there will be more to come probably. The shortest path is taken into account separately, in addition to the average path length. Still, the average difficulty should raise roughly with the square root of the level.

General difficulty has been made easier, because you'll start without heroes. And at least the first levels will have only one entry and one cpu.

[ochadenas]

The perceived difficulty is quite impossible to calculate, I think. First, "perceived" depends heavily on the player and their perception. And then, most of the metrics proposed above are extremely hard to calculate. I have no idea how to take into account "complexity", at least not without some serious mathematics. The game (let me say this once again ;) ) is much less intelligent than you think, and it does not know about the topology of the layout. It only knows the existing paths.

However, the lengths of the links are known and could be taken into account. (Currently they aren't.)

[Cwpute]

I was thinking of somethink like complexicity being valued at 1 for levels with a single lane, attacker spawn point and CPU, and progressively getting higher as you add more spawn points, CPUs, etc… for a maximum value of 2 maybe ? that would be applied at the end of the whole level generation.

[The-JMFB]

As a conversational input without a substantial amount of solutions, I'd like to add that the difficulty of getting a usable map at the higher levels is almost as time consuming as playing the level. I completed level 100 and I spent a good 20 minutes "replaying" the stage just to generate a new map until I finally pulled one that was (barely!) winnable. For reference, I've been playing 1.32

The speed, strength and number of attackers at these levels requires plenty of slots to have any chance at all because all of the chips are severely underpowered in relation to the strength, speed and number of attackers. At this point, I won't even attempt a map that has fewer than 5 slots in the shortest path from entry to chip. Even then, I won't attempt it unless only one path is limited to 5 slots because you really need 6+ in the last 20-25 waves due to the swarm effect of the massive number of attackers converging from multiple paths.

Problems that I think need the most attention for these late levels:

When 2 or 3 attackers are right on top of each other, only one will usually be killed by a max sub chip with a max clock chip. This really doesn't make any sense to me when all of the attackers have been reduced to zero and a level 12 sub + level 12 clock can't easily stop all of them. Maybe I could understand if some of the attackers still had more life remaining, but I am frequently encountering this scenario where multiple lanes converge and the attackers stack onto one another, even though all of them have been reduced to 0, when they reach my final sub chip only one will be killed and the remaining attackers glide right by.

The increased cost of the ACC chips has had a massive impact on the early half of these late levels. I now have to employ a 3 phase strategy to build my defense and that includes using far more mem chips than I've ever wanted to use for the first phase. I'm now spending more time pausing so I can clear them than I'm spending on anything else in the first phase. There is no getting around the need for a lot of ACC chips in these higher levels. The swarms are completely unmanageable without 6-9 ACC chips, depending on map size. As a general rule, I need 3 per lane to keep the swarm under control. No other combination of chips will work because the swarm just glides right over so many chips with none of them taking any damage.

I think one of the things we need to help mitigate these issues is some kind of Area Of Affect chip that can damage more than a single attacker. Something to slow, regulate, and/or detour attackers would also be helpful.

Between the extremely high attacker strength/rate, the inflated ACC chip costs, huge increase in negative chips and their ever inflating costs to remove, absence of any increase in starting information or information accrual rates, the game really starts to feel out of balance beyond level ~60 or so. I like a challenge, and I definitely want to be challenged, but these higher levels have a balance issue that is far beyond challenging. The need to pull a map of adequate size is the paramount priority. Managing resources (information) is so critical and has razor thin tolerances. Having to employ so many MEM chips early on (requiring constant pausing to manually clear the chip + you have so many attackers coming that you have to pause the MOMENT they are captured and clear the chip to have any hope of catching the next attacker) so that you can clear the negative chips and very slowly aquire the ACC chips. The micromanagement just becomes very tedious.

I know that the chips and their upgrades were not created with these difficulty levels in mind. I just wanted to demonstrate that there is a need for some kind of defense increase at these higher difficulty levels because the cost of defense continues to grow exponentially while the effectiveness of the defense is reducing at almost the same rate and your starting resources remain static and not nearly adequate.

I know the current version has the new higher capacity MEM upgrades and they will help with this a little, but it's not going to eliminate the fundamental problem of exponentially increasing difficulty with static resources, defense caps, and chip logic that doesn't include massive amounts of swarming enemies.

As always - this is meant as constructive criticism. This game continues to dominate my spare time on mobile.

[Cwpute]

What we're doing here is essentialy trying to come up with a system that can rate the difficulty of levels. It's hard.
But, don't we already know of a tool that-does this perfectly ? humans players. What wouldn't we let them rate when a level is too hard to continue ?

The player would be able to generate new levels on demand, and each of them would be its own renewable experience, with the objective to push them to their highest difficulty until it becomes unbeatable or players are bored, then move on to some new generated level.
Each level would increase in difficulty in two possible waves:

• infinite number of waves, and the difficulty achieved by the player being represented by the highest wave they tackled successfully
• a set number of waves to clear, but once beaten it requires the player to start that same level again, with harder and longer waves, less chip slots, or more atacker spawn points etc… until again they're done with it, the difficulty achieved then being represented by the number of increasingly harder restarts they'd have done.

[ochadenas]

Thanks for the insight on actual game play. I must admit that I myself have never even come close to the levels you are playing ...

Let's continue trying to balance the game better. Please have a new go with 1.34, because the difficulty levels have completely changed. But the effect still remains that at one point the attackers will be so fast and numerous that they can't be fended off.

On the other hand, the game should end at a certain point, shouldn't it?