[BUG][PLAYER] Cloner and Replay Insert Mode/Edit Mode Edge Cases

[Dullstar]

I was working on an unrelated practice project earlier today, and some of what I was thinking about while working on it made me curious to see if the lemming indexes would get messed up if you used cloners with replay insert mode.

Sure enough, this causes assignments to get shifted to different lemmings.

I created a fairly generic level layout where lemmings would be trapped on either side of the level, remaining capable of receiving assignments. Lemmings spawning from the trapdoor would head to the right, while lemmings created by cloners assigned to newly spawned lemmings would head left. Lemmings had access to being a cloner or a builder.

Test Case 1:
- Assign a builder to the second lemming some time after spawn.
- Restart the level, and turn on Replay Insert Mode (the blue R thing)
- Assign a cloner to the first lemming before the second lemming spawns
Expectation: The builder assignment should be unaltered (assigned to the second lemming from the hatch).
Result: The clone will use the builder.

Test Case 2:
- Assign a cloner to the first lemming as soon as it spawns.
- After the second lemming spawns from the hatch, assign a builder to the clone
- Restart the level
- Bring up the replay edit mode and delete the cloner assignment.
Expectation: The clone's builder assignment shouldn't happen because the lemming no longer exists.
Result: The second lemming from the hatch will use the builder.

Test Case 3:
- Assign a builder to the third lemming.
- Restart the level and turn on Replay Insert Mode
- Assign a cloner to the first lemming as soon as it spawns
Expectation: The builder assignment should be unaltered (assigned to the third lemming from the hatch).
Result: The second lemming from the hatch will use the builder

Because of the behavior here, a cloner assignment can cause problems to skill assignments that should have been independent of the cloner; for example, in a multitasking level.

This is likely caused by the lemming indexes: Lemming 0 is the first to spawn, Lemming 1 is the second; if a cloner is used when N lemmings are in the level, the spawned lemming will have the index N (not N+1, because the count starts at 0). Normally, lemming N would have been the next lemming to spawn from the hatch. When a cloner is inserted or removed, indexes at or above the clone's index get shifted around to different lemmings than they would have otherwise been, so the skills get assigned to the wrong lemming.

But if you altered the resulting lemming index for the clone, it would break replays. Maybe it would be possible to adjust the assignments such that they will still correspond to the same lemming (probably deleting them if they would have corresponded to the clone)?

[namida]

The most likely way to approach this is to not rely purely on index in an array, but rather, give every lemming an ID number. The first lemming spawned is 0, then 1, then 2 etc as normal for regular lemmings, however, for clones, perhaps negative numbers can be used, so that the first clone is -1, the next is -2, etc. Replays then refer to lemmings by these ID numbers, rather than just their index by spawn order. Perhaps there's a better way to generate these ID numbers that's less prone to even cloners interfering with other cloners?

This still has weaknesses, eg. suppose you delete a cloner assignment to one lemming, then instead clone another lemming; all actions that previously belonged to the now-deleted clone get transferred to the new one. However, this would be a significant improvement over the status quo, and probably as good as can be done without the code getting really complex.

[ccexplore]

With the proposed ID system, to complete the fix, whenever you delete or insert a cloner assignment, you:

1) See how many cloner assignments occur (and thus how many cloners created) before the affected cloner assignment.  The IDs of those cloners remain unaffected by the edit.
2) The IDs of the other (later) cloners in the replay will need to be updated to account for the deletion or insertion.
3) In addition, in the case of delete, all future moves of the affected cloner (as identified by ID) will need to be removed from replay.  Note that some of those such removed moves may themselves be cloner assignments, so you'd need to reapply 1-3 as well.

For the UI, it may be worth considering a confirmation popup whenever user deletes a cloner assignment, as it can potentially remove a whole cascade of later moves stemming from the clone that no longer exists, plus all further clones descended (once or more) from the deleted clone.

4) Any edits (not just to cloner assignments) may potentially result in a cloner assignment in the future failing, specifically if it causes the death of the source lemming you are cloning from.  You can react to this case one of two ways:
  A) When it occurs (ie. the replay just played the move that no longer works), treat it as a delete of the now defunct assignment and apply all of the above; or
  B) When it occurs, you still move on to the next cloner ID even though the cloner assignment didn't actually clone anyone, and you leave the defunct cloner assignment in the replay.

#4 actually can occur even without cloners involved, an edit might cause death of a lemming rendering a later assignment to that lemming no longer applicable.  I don't know if NeoLemmix today tries to clean up such defunct moves as they occur vs leave them in the replay.  There may be an argument for keeping them, as user may want to tweak the edits that broke these later assignments so that they are no longer broken.

I think the above is complete, but feel free to poke holes at it.  It is somewhat complex but doable.  #3 is particularly tricky to get right and maybe I'll provide a pseudocode implementation later.

[namida]

I don't see a problem with #3 in terms of implementing it, however the issue is - what happens if the assignment being deleted is already one that would fail, but has somehow remained in the replay, with further actions at a later point (that would be interfered with by the above algorithm)?

This is why I think a better approach is to attempt to uniquely generate an ID number for cloners. There will likely still be edge cases, but if perhaps the ID for a cloned lemming is based on the original source lemming and generation (rather than just first clone is -1, second is -2, etc) this might be workable. I'd just have to think of what the ideal algorithm for this would be. It'd be ideal if this could ultimately produce a 32-bit value (signed or otherwise), but 64-bit or even a string is fine if it needs to be. I'd rather avoid floats due to the possibility of rounding error; I know it's very unlikely, but I prefer not to take that risk.

If any of the maths / logic geniuses here have ideas for a suitable algorithm, go ahead. I'd consider it ideal if, in the absence of cloners, the ID number matches the index number in the current setup, or has some obvious correspondence to it (such as "a string representation of said number" or "that number but negative" etc). Keep in mind that a cloner can be assigned to any lemming at (almost) any time, including to a lemming that's already been cloned (whether or not the clone is still alive) or is a clone themself.

Backwards compatibility on the replays would likely need to remain indefinitely; either this, or a "replay update" feature would need to be built into NL itself. While backwards compatibility is not a particularly difficult task, updating a replay without outright playing it back would be almost impossible (again, due to the possibility that some assignments in it are already invalid).

[ccexplore]

I don't see a problem with #3 in terms of implementing it, however the issue is - what happens if the assignment being deleted is already one that would fail, but has somehow remained in the replay, with further actions at a later point (that would be interfered with by the above algorithm)?

Isn't that exactly the same as my #4?  A failed cloner assignment is one that would've created clone -N but didn't.  All future assignments in the replay to ID -N will also fail because there's no -N.  You can elect to delete -N now, removing all assignments involving ID -N from the replay, then adjust the IDs of -(N+1) onwards.  Or you can leave it in the replay as a defunct record.   If you do leave it, you must still subtract one anyway for the next clone ID to use.

Basically there's a fixed relation between the ID to use for a newly created clone and how many cloner assignments (both successful and defunct) have been executed so far.  This saves you from having to explicitly record the clone IDs into the records of the cloner assignments, at a cost of having to maintain this relationship correctly during any insertion/deletion of moves.

This is why I think a better approach is to attempt to uniquely generate an ID number for cloners.

That's fair.  If you change the format so that for cloner assignments, you also store the new clone's ID in the replay record for the assignment, then all you have to do is to keep decrementing (ie. more negative) to get the next cloner ID to use, and it'd be unique.  In other words:

- When you load a replay, scan through the cloner assignments (which would now contain the IDs used for the newly created clones) to find the lowest (ie. most negative) clone ID used.  Subtract 1 from it to get the number (N) to use for the next cloner assignment.  Note that this means N = -1 for the case where there's no replay or no cloner assignments in the replay.
- If the assignment comes from a replay, then ignore N and just use the stored clone ID for the new clone being created.
- For an assignment not coming from a replay (ie. from an actual player-executed assignment, or an inserted assignment during editing), use N for the clone ID and subtract 1 to update N afterwards.

In this system, you don't have to ever readjust any existing clone IDs in response to insertion or deletion of cloner assignments, since there's no longer a relationship to maintain between number of clones made so far and the IDs of the clones.  You can still propagate deletes (if you want to) to delete all future moves on the deleted clone plus all of its descendant clones, since the cloner ID of the clone created is part of the replay record for a cloner assignment.  Assignments that become invalid has no impact since any assignments from the replay don't change N, you just use the stored ID.

Off top of my head, I don't believe there's any simple system to assign unique clone IDs if you can't also store those IDs as part of the replay records of the cloner assignments.

Backwards compatibility on the replays would likely need to remain indefinitely; either this, or a "replay update" feature would need to be built into NL itself. While backwards compatibility is not a particularly difficult task, updating a replay without outright playing it back would be almost impossible (again, due to the possibility that some assignments in it are already invalid).

Yeah, unfortunately I don't see a way around this.  The old format is based on indices, and failed cloner assignments will definitely affect indices in the same way a delete of a successful cloner assignment during replay editing can.  And there's no way to predict whether the assignment is ok or not without outright playing it all back.  This is always a problem regardless of what system you choose for the IDs of the clones.

[Simon]

This is a lovely problem. I've lurked since the thread's beginning but don't have good answers yet.

A possible ID datatype might be finite list of integers ≥ 0. Hatch-spawned lemmings have only one element in their list: the old ID integer. Cloned lemmings copy the source lemming's list and append the smallest integer ≥ 0 that wasn't yet given to an earlier cloner with this same source lemming. List of integer is reasonably easy to serialize to file.

The idea is that each lemming remembers its source, which remembers its source etc., and at the beginning there is only the pool of hatch-spawned lemmings and pre-placed lemmings, which have a natural order (at least when we assume 12.09 physics features) and thus need not remember additional sources.

If you want to make it even sturdier/more elaborate, you might even argue that there are other ways that spawn lemmings in hardly-forseeable orders, and that it makes sense to explicitly remember ((hatch pool) -> 3rd) instead of only (3rd). Or maybe the system should remember different ways to produce a lemming from a source, e.g., lemming walks into hypothetical cloning apparatus, which should not affect cloner assignments that we later want to reorder. But I'm likely overdesigning.

Anything we do here Most ideas introduces a format change and should be mentally squished thoroughly.

-- Simon

[Simon]

There are really two problems here:

• Internal representation while the replay is in RAM. We want to reorder cloners in the replay without the replay failing unrelated assignments. This internal representation I had in mind as target for the idea with the list of integers (= recursive tracking of sources plus the n-th time the source has produced a lemming).
• Serialization to file. We don't necessarily have to touch the format definition; we might work around it and avoid a format change.
  

Maybe we can serialize the IDs to the classical integers (including their odd behavior, and future NL must remember 12.09's quirks of how it assigns IDs internally, to use that quirk for this serialization of list-of-integer to a single integer). When the replay gets loaded, the integer IDs convert to list-of-integer.

The problem is that this loading-and-converting seems to need a physical passthrough, or at least an interpretation of RR changes. Nasty nasty nasty, many little details to squish in mind. There is no clear good and bad here.

-- Simon

[ccexplore]

What if we use the frame number (ie. "number of phyus" in Lix parlance) as the ID for new cloners (or to be more precise, the negation of the value, to distinguish from positive values relating to regular lemmings coming from entrances or preplaced)?  It's definitely unique assuming only one assignment allowed per frame/phyus.  And it doesn't require storing the clone ID with the cloner assignments--we already store the frame/phyus information.  The disadvantage is you need to readjust IDs whenever you changed the timing of a cloner assignment during replay editing, but this can be handled by the replay editor automatically.

[ccexplore]

The problem is that this loading-and-converting seems to need a physical passthrough, or at least an interpretation of RR changes.

You need a physics passthrough to deal with cloner assignments in the replay that might not actually work because they are referencing a lemming that is dying or already died (plus whatever other states may exist for a lemming to not be able to be assigned cloner).  The cloner assignment can be "defunct" in this manner due to replay editing, either through NeoLemmix's interfaces or by direct hand-editing of the replay file.  The creation of a cloner affects the indices of all future lemmings to be entered or cloned into the level after the creation of the current cloner.

If it can be trusted that all cloner assignments in the replay will be successful, then in theory you don't need a full physics passthrough, you just need to track RR changes to accurately work out the timing of spawning of new lemmings from entrances.

One can perhaps argue that the likelihood of a defunct cloner assignment remaining in a saved replay is low enough to be ok to potentially invalidate a replay when we try to up-convert to the new format (with IDs rather than indices).  It should only be the result of replay editing, and it seems unlikely for an intentional replay edit to indirectly invalidate a later cloner assignment versus explicitly deleting that assignment.  After all, the resulting loss of a cloner is a pretty big deal solution-wise.

You can also consider a method of progressive rewrite of the replay records into the new ID-based reference to lemmings.  This means in the new format, each record has extra data/flags to indicate whether the record is using index vs ID to refer to the target lemming.  An old replay containing cloner assignments will need to initially stick with using indices for the records from the replay.  Then as you play through each record of the replay, you can start progressively update records from indices to IDs once a lemming has actually been created (either via entering or cloning) at a particular index, thereby establishing the correct relationship between that index and the ID (so you can change all records in the replay with that index to the ID).  Once all cloner assignments in the replay have been played through, it should also be possible to convert all remaining replay records to IDs.  The replay editor may need to warn/block certain edits as unsafe while the replay still has records with indices rather than IDs, with a button user can invoke to allow the game to take some time to run through physics to convert everything else still unconverted.

[namida]

No matter how much I think about this, every possible solution, at best, moves the problem to one that either (a) instead kills actions assigned to the cloner if the cloner assignment is moved to a different frame; or else (b) will move assignments from a deleted cloner, to subsequent cloners.

B doesn't really fix the problem, it just reduces the impact a bit. Not enough to be worth the effort, in my opinion.

Does A sound acceptable; ie: if a cloner assignment gets deleted (or moved to a different frame), it would delete that cloner's later actions? It's pretty much either that, or things remain as is, as far as I can tell.

[Strato Incendus]

A sounds good, but how does the engine track which lemmings are clones and which aren't?

I thought after a clone has been created, it's just treated like any other lemming?

[namida]

A sounds good, but how does the engine track which lemmings are clones and which aren't?

I thought after a clone has been created, it's just treated like any other lemming?

Well - currently, each lemming has an index number. The first lemming spawned in a level gets zero, the next gets 1, the next 2, etc. Of particular importance, if two lemmings spawn, then you assign a Cloner, the clone gets 2 (and the next natural spawn gets 3, etc), which is why inserting or removing cloners can break replays. Replays refer to lemmings by this index number.

The proposal here (most of which comes from ccexplore's post above) is that the replay format gets tweaked slightly, so that clones are referenced by the frame on which they spawn (or perhaps, the negative value of the frame on which they spawn, to avoid conflicts with normal lemmings). This would probably need to be, in practice, "negative (spawn frame + 1)", in case a cloner is used on frame zero in a replay.

From there, it's just a matter of figuring out "how do I implement backwards-compatibility for this?" Suggestions so far rely on either (a) a full physics simulation of the level when the replay is loaded; (b) assuming that all Cloner assignments in old replays are successful and adjusting based on this; or (c) retaining support for current notation internally (rather than just "in the file formats"), and continuing to use the existing system for old replays while using the new system for new ones.

A is basically just C with extra steps, so we'll rule out A now. Between B and C, it will come down to which one seems more practical and/or less prone to side effects - it should ideally be entirely invisible to the user, that this is even happening; the only time actual end users should notice it is if they try to reproduce this bug intentionally, or if they examine a post-change replay file in a text editor.

One bottom line here is - if I cannot fix this without existing valid replays breaking, I will not fix it at all. Even invalid ones (eg. if they contain failed Cloner assignments), I would rather avoid breakage if at all possible - and option C is definitely far more likely to avoid such breakage, so I will be looking into that first.

[namida]

Proposed format change is that instead of just a number alone, the lemming index in the replay will be either "N0", "N1", "N2" etc for naturally-spawned lemmings (preplaced or otherwise), and "C138", "C885", etc for cloned lemmings (with the number component being the frame they were spawned on). If an index is found that has neither an N nor a C before it, it is treated as an absolute index in the same way it would be now.

To be clear again - not breaking existing valid replays is a bottom line here. These changes will not occur if compatibility of existing replays cannot be maintained while doing so.

Can anyone think of any reason it would be beneficial to separate out preplaced lemmings in this system too? My hunch is that if a preplaced lemming were to be removed, the replay would almost certainly fall apart quite majorly even if the other lemmings were still tracked accurately. But maybe I'm overlooking something. If I were to do this, the most logical way to do so would be to identify them by their initial coordinates, I think.

[Dullstar]

I'd say preplaced lemmings being removed would qualify as a potentially breaking level change where I'd expect replays to be broken if they were removed, although technically separating them out would probably increase the probability a replay still works, but I'd still expect replay breakage in the majority of situations even with accurate tracking of which lemmings are which, at least not without a total overhaul of the replay format to account for delays/speedups in lemmings arriving to the skill assignment location, which sounds like way more work than it would be worth.

[namida]

I thought of a case in which it would be useful to track preplaced lemmings independently of their index: In case the index order, but not positions, of them is changed in the level file. This would not likely break the replay.