How Cyst starvation works
Squidget
Join Date: 2003-06-13 Member: 17334Members
Join Date: 2003-06-13 Member: 17334Members
<div class="IPBDescription">What you don't know can kill you (long, geeky)</div>I think cyst "starvation" (for lack of a better term) is unintuitive as of build 182. I'll explain why I think so, and why some cyst chains may die off sooner than you expect.
<u>Rule 1: Each cyst only has one parent, either another cyst or a hive. If none of a cyst's ancestors (parent, grandparent, etc.) are a hive, the cyst is in a "orphaned chain," and will eventually starve to death.</u>
This seems reasonable enough. For example, here is a nourished cyst chain (connected to a hive):
<img src="http://i.imgur.com/0QV25.png" border="0" class="linked-image" />
The gray circles are the supply radius. The "H" is a hive, numbered circles are cysts. The cyst's number shows the order it was built. Since every cyst has a hive as an ancestor, they are nourished and will not starve. So far so good.
<u>Rule 2: A cyst begins to starve when its parent dies due to starvation.</u>
This means cysts starve from the POINT OF CUT. In our example, if cyst 1 is killed, then cyst 2 will starve first. After cyst 2 dies, cyst 3 begins to starve.
You may have noticed that the chain is very stretched out. You may want to "backfill" by adding redundant cysts. If the chain gets cut off, extra cysts will buy you more time to recover, right? Well, no, due to rule 3:
<u>Rule 3: When created, a cyst always chooses the closest entity as its parent. This may not be the parent you would prefer.</u>
This means that the ORDER you place cysts determines which ones starve first. It makes "backfilling" much less effective. It may not be obvious why, so lets look at another example:
<img src="http://i.imgur.com/m9FNq.png" border="0" class="linked-image" />
The comm started by placing cyst 1 and then cyst 2. But since cyst 2 was at the limit of the supply radius, the comm placed cyst 3 as "backfill." The comm figures that if cyst 1 dies, cyst 3 will act as a "starvation" buffer, protecting cyst 2 for a time. The problem is, it doesn't work this way. Cyst 2 will die in the same amount of time. To understand why, let's zoom in:
<img src="http://i.imgur.com/tKxNo.png" border="0" class="linked-image" />
The arrows show the path from parent to child. This is also the starvation order. Due to rule 3, both cyst 2 and cyst 3 have the same parent: cyst 1. Due to rule 2, when cyst 1 is killed, BOTH cyst 2 and cyst 3 immediately begin to die.
<b>Takeaway lesson: For starvation, ORDER matters more than position. You can't backfill to slow down starvation. If you want to slow down starvation, you MUST build for it up front! You can't backfill later.</b>
To be clear: Backfilling still is still useful to make it hard to cut off a chain. But once the chain is cut off, the backfill doesn't help at all.
This puts a big burden on the comm, because they need to remember the exact ORDER they place cysts, otherwise it may collapse faster than expected. This also means gorges who place backfill cysts are giving comms a false sense of security. And this makes multiple comms a lot harder, because a new comm won't know the order of cyst placement. The glowing trace effect is virtually invisible, so that's little help.
It actually gets more complicated. If a cyst chain is connected to TWO or more hives at some point, the order of starvation might be reversed. This depends on various factors beyond the scope of this post. The important point: backfilling works better during reversed starvation.
<b>Takeaway lesson: always connect cyst chains to multiple hives to improve your chance of getting a reversed starvation pattern, and thus slow down starvation.</b>
---
To UWE, I propose these changes:
1) Cysts who lose their parent should be demotable to be a child under other cysts. This means backfilling will work. (Mechanically, this is the "swim down" move used in standard B-trees. The traversal and demotion logic may not be obvious. An algo that works: Only run if a dying cyst has multiple children. Place all to-be orphaned siblings into an ordered circular list. For every orphan, proceed through the list, stopping when a cyst is found in range. Become a child of that cyst. Terminate inner loop if you arrive back at self, as this cyst is a true orphan. The one-way circular buffer prevents cycles, so preserves the acylic nature of the tree.)
2) In addition to the above, a simple "heat map" should be used to select the next cyst to die. Heat is generated by buildings such as harvesters; coldest cyst dies first. For example: a cyst directly feeding a harvester would be very hot, and the last one to die. In other words, cysts chains act intelligently to preserve buildings as long as possible. This removes placement ordering from the equation, so only positions matter. Easier to understand, easier on multiple comms.
<u>Rule 1: Each cyst only has one parent, either another cyst or a hive. If none of a cyst's ancestors (parent, grandparent, etc.) are a hive, the cyst is in a "orphaned chain," and will eventually starve to death.</u>
This seems reasonable enough. For example, here is a nourished cyst chain (connected to a hive):
<img src="http://i.imgur.com/0QV25.png" border="0" class="linked-image" />
The gray circles are the supply radius. The "H" is a hive, numbered circles are cysts. The cyst's number shows the order it was built. Since every cyst has a hive as an ancestor, they are nourished and will not starve. So far so good.
<u>Rule 2: A cyst begins to starve when its parent dies due to starvation.</u>
This means cysts starve from the POINT OF CUT. In our example, if cyst 1 is killed, then cyst 2 will starve first. After cyst 2 dies, cyst 3 begins to starve.
You may have noticed that the chain is very stretched out. You may want to "backfill" by adding redundant cysts. If the chain gets cut off, extra cysts will buy you more time to recover, right? Well, no, due to rule 3:
<u>Rule 3: When created, a cyst always chooses the closest entity as its parent. This may not be the parent you would prefer.</u>
This means that the ORDER you place cysts determines which ones starve first. It makes "backfilling" much less effective. It may not be obvious why, so lets look at another example:
<img src="http://i.imgur.com/m9FNq.png" border="0" class="linked-image" />
The comm started by placing cyst 1 and then cyst 2. But since cyst 2 was at the limit of the supply radius, the comm placed cyst 3 as "backfill." The comm figures that if cyst 1 dies, cyst 3 will act as a "starvation" buffer, protecting cyst 2 for a time. The problem is, it doesn't work this way. Cyst 2 will die in the same amount of time. To understand why, let's zoom in:
<img src="http://i.imgur.com/tKxNo.png" border="0" class="linked-image" />
The arrows show the path from parent to child. This is also the starvation order. Due to rule 3, both cyst 2 and cyst 3 have the same parent: cyst 1. Due to rule 2, when cyst 1 is killed, BOTH cyst 2 and cyst 3 immediately begin to die.
<b>Takeaway lesson: For starvation, ORDER matters more than position. You can't backfill to slow down starvation. If you want to slow down starvation, you MUST build for it up front! You can't backfill later.</b>
To be clear: Backfilling still is still useful to make it hard to cut off a chain. But once the chain is cut off, the backfill doesn't help at all.
This puts a big burden on the comm, because they need to remember the exact ORDER they place cysts, otherwise it may collapse faster than expected. This also means gorges who place backfill cysts are giving comms a false sense of security. And this makes multiple comms a lot harder, because a new comm won't know the order of cyst placement. The glowing trace effect is virtually invisible, so that's little help.
It actually gets more complicated. If a cyst chain is connected to TWO or more hives at some point, the order of starvation might be reversed. This depends on various factors beyond the scope of this post. The important point: backfilling works better during reversed starvation.
<b>Takeaway lesson: always connect cyst chains to multiple hives to improve your chance of getting a reversed starvation pattern, and thus slow down starvation.</b>
---
To UWE, I propose these changes:
1) Cysts who lose their parent should be demotable to be a child under other cysts. This means backfilling will work. (Mechanically, this is the "swim down" move used in standard B-trees. The traversal and demotion logic may not be obvious. An algo that works: Only run if a dying cyst has multiple children. Place all to-be orphaned siblings into an ordered circular list. For every orphan, proceed through the list, stopping when a cyst is found in range. Become a child of that cyst. Terminate inner loop if you arrive back at self, as this cyst is a true orphan. The one-way circular buffer prevents cycles, so preserves the acylic nature of the tree.)
2) In addition to the above, a simple "heat map" should be used to select the next cyst to die. Heat is generated by buildings such as harvesters; coldest cyst dies first. For example: a cyst directly feeding a harvester would be very hot, and the last one to die. In other words, cysts chains act intelligently to preserve buildings as long as possible. This removes placement ordering from the equation, so only positions matter. Easier to understand, easier on multiple comms.
Comments
And if there's confusion where two nodes are left hanging, like your example in rule 3 where Cysts 2 and 3 would try to connect to each other as parent, the one closest to a hive becomes the 'starvee'. So, in your example, Cyst 3 would start starving, and Cyst 2 would latch onto it as its parent.
if you have this chain:
H..1..2..3..4..5
and cut 1, both 2 and 5 should start to starve. At least to me that would make more sense
Not necessarily. In terms of theory the cysts could be intelligently keeping their nutrients, or whatever, from one Cyst at a time. Although by this rule, I suppose you'd expect them to starve quicker at first and slow down as there are less Cysts.
if you have this chain:
H..1..2..3..4..5
and cut 1, both 2 and 5 should start to starve. At least to me that would make more sense<!--QuoteEnd--></div><!--QuoteEEnd-->
makes also more sense to me
cysts Hive.1.2.3.4.5
5 is the child (youngest cyst)
cysts 1 to 4 are only there to supply "their" child. (hive supplies cyst 1, cyst 1 supplies cyst 2,...)
When for example cyst 2 is destroyed the following mechanic activates:
Cyst 5 needs supplies, it gets it from it's parent, Cyst 4 his supplies are being drained, he gets his supplies from Cyst 3, Cyst 3 his supplies are being drained but he isn't connected anymore, to keep the chain alive he sacrifices his own life to provide supplies to his children until his death.
This is repeated with Cyst 4.
Not sure if I made my point lol
Cysts will actually reconnect and rebuild their chain - at the moment a cysts is disconnected, it will look around for a connected cyst or hive to connect to. If it finds it, it will become the parent of the chain.
So if you have Hive1 -> C1 -> C2 -> C3 -> C4 Hive2 and kill Cyst 1, Cyst 4 will connect to Hive 2 and reorient the chain so it becomes Hive 1 C2 <- C3 <- C4 <- Hive2.
If in the 2nd example of the OP cyst 1 dies, theoretically, cyst 2 could connect to 3 or vice versa thus preventing one of them dieing early. But I think they won't. What the OP suggested was that cysts that lost their parent should try to reconnect themselves even to an unconnected cyst, combined with some smart logic that should prevent cyclic connections (thus creating an island that could exist independent from the hive). And he suggested as second to include a smart system that should make cysts that are close to valuable structures (like harvesters) always to die as the last in the chain.
What he wasn't too clear about is that blackfilling works <i>if</i> it is still possible to create a new uninterrupted chain between the hive and the outermost cyst after a cyst in the chain dies. If in this example you would place another cyst (5) between H and 1 and then cyst 1 is killed, 5 will reconnect to H, 3 to 5 and 2 to 3. He specifically talked about what happens if the connection is broken.
<strike>And one thing is just wrong: You don't need to remember the connection, you can <i>see</i> it. Just watch the yellow impulse travel from one cyst to the next.</strike>
edit: well, with cysts no longer requiring LOS, the visible impulse is somewhat broken, so I take back the last statement. You'll have to remember the connection now I'm afraid.
<img src="http://i.imgur.com/tKxNo.png" border="0" class="linked-image" />
Then marine kills cyst 1, what should happen? Cyst 2 and 3 (as they are oldest ancestors in disconnected chain) should automatically reconnected to nearest "active" cyst in range (in this situation Hive if is in range).
or works as my updated prototype (use multiple connections):
<a href="http://www.unknownworlds.com/ns2/forums/index.php?showtopic=114159" target="_blank">Cyst prototype update</a>
Z.
Yep, that was basically my suggestion at the bottom. I phrased it differently, but that's the idea.
<!--quoteo(post=1864139:date=Jul 28 2011, 05:50 AM:name=Asraniel)--><div class='quotetop'>QUOTE (Asraniel @ Jul 28 2011, 05:50 AM) <a href="index.php?act=findpost&pid=1864139"><{POST_SNAPBACK}></a></div><div class='quotemain'><!--quotec-->I actually think that not only the cyst at the cutting point should start to die, but the one at the other end too.<!--QuoteEnd--></div><!--QuoteEEnd-->
Unfortunately, you can't code that. Imagine a spider web of cysts: determining the outer ring of cysts is non-trivial math, and that means a slower game. It also means that larger, denser chains of cycts die FASTER than linear chains, and that seems unfair. I think it should be kept simple: 1 cyst dies at a time, always.
<!--quoteo(post=1864168:date=Jul 28 2011, 07:51 AM:name=matso)--><div class='quotetop'>QUOTE (matso @ Jul 28 2011, 07:51 AM) <a href="index.php?act=findpost&pid=1864168"><{POST_SNAPBACK}></a></div><div class='quotemain'><!--quotec-->You know, if backfill is what you want to do, just place cyst 3 to overlap its infestation with cyst 2, making it the child of cyst 2.<!--QuoteEnd--></div><!--QuoteEEnd-->
Yep, a nuance I skipped for brevity. The post was already hella long.
<!--quoteo(post=1864168:date=Jul 28 2011, 07:51 AM:name=matso)--><div class='quotetop'>QUOTE (matso @ Jul 28 2011, 07:51 AM) <a href="index.php?act=findpost&pid=1864168"><{POST_SNAPBACK}></a></div><div class='quotemain'><!--quotec-->Cysts will actually reconnect and rebuild their chain - at the moment a cysts is disconnected, it will look around for a connected cyst or hive to connect to. If it finds it, it will become the parent of the chain.
So if you have Hive1 -> C1 -> C2 -> C3 -> C4 Hive2 and kill Cyst 1, Cyst 4 will connect to Hive 2 and reorient the chain so it becomes Hive 1 C2 <- C3 <- C4 <- Hive2.<!--QuoteEnd--></div><!--QuoteEEnd-->
Yep, I mentioned that but skipped the details, since it's non-intuitive. For example, the chain doesn't get reoriented, it just dies from the bottom up. So, if we extend example 2 like this:
<!--c1--><div class='codetop'>CODE</div><div class='codemain'><!--ec1-->H1 -> C1 -> C2 -> C4 -> H2
-> C3<!--c2--></div><!--ec2-->
If you cut C4 first, then C1, no reorientation happens, so C2 and C3 still die at the same time. If you reverse the cuts: C1 first, then C4, then the C2 dies first, then C3 dies. What I *think* happens is that the chains NEVER reorient, the game just runs the starvation algorithm from either the top or the bottom of the chain, depending on where the cut occurs. This is why I said that reverse starvation MIGHT extend the lives of the chains. Depends on the order of cuts, and the placements of the cysts.
In any case, this is FAR too complicated to deal with in an action game. A simpler model is needed.
<!--quoteo(post=1864188:date=Jul 28 2011, 09:27 AM:name=wulf 21)--><div class='quotetop'>QUOTE (wulf 21 @ Jul 28 2011, 09:27 AM) <a href="index.php?act=findpost&pid=1864188"><{POST_SNAPBACK}></a></div><div class='quotemain'><!--quotec-->If in the 2nd example of the OP cyst 1 dies, theoretically, cyst 2 could connect to 3 or vice versa thus preventing one of them dieing early. But I think they won't. What the OP suggested was that cysts that lost their parent should try to reconnect themselves even to an unconnected cyst, combined with some smart logic that should prevent cyclic connections (thus creating an island that could exist independent from the hive). And he suggested as second to include a smart system that should make cysts that are close to valuable structures (like harvesters) always to die as the last in the chain.
What he wasn't too clear about is that blackfilling works <i>if</i> it is still possible to create a new uninterrupted chain between the hive and the outermost cyst after a cyst in the chain dies. If in this example you would place another cyst (5) between H and 1 and then cyst 1 is killed, 5 will reconnect to H, 3 to 5 and 2 to 3. He specifically talked about what happens if the connection is broken.<!--QuoteEnd--></div><!--QuoteEEnd-->
Exactly right on all counts. And yes, you can repair a cut with backfilling, but you can't preventively backfill.
To Wulf, since you understand the details: I think my proposals would would be far more intuitive and less of a burden on the comm, what do you think?
uh, good? i like this and think it keeps the mechanics fair:
<i>a marine can always break the chain as intended and it can always be repaired if necessary, as intended.</i>
back filling proactively to prevent any breakage would become the primary tactic and then what? the entire game would be "testing the fence" for marines. as charlie said for the last patch changes, or dev blog i forget, cysts shouldn't be the primary draw or effort in the game, it should still be PvP. if cysts become this difficult to break due to well overlapped chains, it will just turn into a PvE game quickly where the actual chain system isn't very clear to the rines on the ground so they will play that testing the fence game.
idk just my thought, wondering why this is seen as an issue i guess?
It's not about balance.
It's about making the game comprehensible. Fast-paced games can't have all kinds of oddball rules with non-intuitive edge cases. Arguably, no game should have those kinds of rules. It frustrates players who can't understand why something happens the way it does. Comming is already very difficult, every edge case makes it a worse experience.
I'm perfectly OK with the assertion that cysts shouldn't be a primary focus. Unfortunately, while that sounds nice, the game mechanics AS GIVEN contradict that. Cyst chains are INCREDIBLY important right now. For example, on summit, aliens are limited to exactly one harvester if they don't use cysts. Only Alien start has a node in range of the hive!
Thus, like it or not, this is a real issue. When it requires a 500 word explanation, with diagrams, in order to explain how cysts work, we have a problem.
I don't exactly understand what you mean with testing the fence (like this T-Rex did with his hands?) but i think spending a lot of energy for redundand cysts should be rewarded. You can't afford to pre-backfill a whole map anyway, just the areas which are very important. And killing cysts isn't a biggie. A suicidal marine that runs into a hive room, kills a few cysts and knifes the hive a little shouldn't be rewarded with a quarter of a map worth of alien infestation dying.
As long as you decide to limit the children of each node to, say, 3 max, it could still be done with a minor performance hit while still allowing for alien commanders to have some redundancy in their node trees.
Leave it to the marines to kill all the cysts. It's more stuff to shoot, and once you get grenade launchers, you can clear entire rooms easily. It's less server calculations, less education needed for each player on how the intricate cyst chain system works.
Basically, the same as what starcraft 2 has.
You should talk more about the green light pulse. You say it is almost invisible - really? I see it really easily. Does it follow the order the comm/gorges placed cysts? Im not sure :/
Actually, this is already how it works. Each cyst has only parent, but can any number of direct children. In some cases, half a dozen or more.
This is an extremely common design in Computer Science, and can be implemented very efficiently. In tech speak, it's a directed acyclic graph, AKA a "tree." So there's no reason to set a limit on the number of children.
<!--quoteo(post=1864414:date=Jul 28 2011, 07:54 PM:name=peregrinus)--><div class='quotetop'>QUOTE (peregrinus @ Jul 28 2011, 07:54 PM) <a href="index.php?act=findpost&pid=1864414"><{POST_SNAPBACK}></a></div><div class='quotemain'><!--quotec-->You should talk more about the green light pulse. You say it is almost invisible - really? I see it really easily. Does it follow the order the comm/gorges placed cysts? Im not sure :/<!--QuoteEnd--></div><!--QuoteEEnd-->
Depends on the map, and the layout. The pulse tends to disappear into the floor due to elevation changes, for example. So you can't rely on it. It can be almost invisible when cysts are far apart. In any case, do you want your comm constantly going AFK for 10 or more seconds to watch some light pulses move around?
The pulses follow the starvation order (the gray arrows in my example). So it's a combination of WHEN and WHERE the cysts are placed.
I know this can be really hard to visualize. Does anyone remember the link to that java applet that prototyped the cysts? I've lost it. If we can find that, curious people can play with it and better understand what is going on.
Edit: here it is. Play with it, and it will be lot easier to understand.
<a href="http://www.openprocessing.org/visuals/?visualID=27777" target="_blank">http://www.openprocessing.org/visuals/?visualID=27777</a>
You should talk more about the green light pulse. You say it is almost invisible - really? I see it really easily. Does it follow the order the comm/gorges placed cysts? Im not sure :/<!--QuoteEnd--></div><!--QuoteEEnd-->
Every 10 seconds, each hive sends out a light impulse to all its cyst-children. Any cyst receiving an impulse sends it onwards to all its children etc. So the light impulse shows the parent/child relationsship. It's actually intended as a stand-in for a future vein-system.
Originally, the path was laid on the ground meaning the light impulse was always visible. When the new pathing system was introduced, the path isn't stuck to the ground in the same way and that means the lights sometimes fly in mid-air and can't be seen.
But I would like to see the tree keep itself as efficient and understandable as possible rather than be based on placement order as well, if that's truly how it's currently designed.
No, you can kill any of them by shooting them. They just made it so that a chain unconnected to a hive has only has one cyst take automatic damage over time. (as opposed to all of them) It causes the unconnected "islands" to stay alive longer if they aren't all manually shot down and allows the aliens to repair more easily.
OH I see, thanks for the clarification.
didnt the dev's patch it so this cant happen? didnt they make it so only the outside cysts take effective damage and the inside ones barely get hurt? i swear..
also i mean, testing the fence as in, im a marine and i kill a cyst, but it doesnt get rid of the infestation because the aliens placed 3 to 4 "redundant" cysts in nearby rooms that i cant see and they are still providing infestation to their structures etc, so i must run around and attempt to find these redundant cysts in hope that it accomplishes my goal of killing infestation. its boring, non intuitive, not balanced, and its time consuming PvE.
that extremely confusing to a new marine and doesnt follow any natural "chain" of thought (hehe). And as others are mentioning its important that its simple.
<i>balance or ease of undestanding still suggests that the topic at hand - <u><b>proactive backfilling</b></u> - should not be implemented.</i>
agree?
And I think, it's the other way round: Because it was so easy to let whole cyst chains collapse, people got so attack-the-cyst focused. If the cyst system is harder to kill, people would directly attack structures and ignore the cysts unless they want to clean the infestation to build own stuff, which they still can, even without knowing about the connections.