disoriented
Level: Smitemaster

Rank Points: 2384
Registered: 08-07-2007
IP: Logged

Undoing is slow.

If I'm holding down a key to undo a large number of moves, it takes a long time for the game to become playable.

Is it possible to cache the state of the room every 10 turns or so, instead of on every turn? Just brainstorming ways of improving performance.

____________________________
34th Skywatcher

Best to PM me, since I might miss your message on CaravelNet chat.

skell
Level: Legendary Smitemaster

Rank Points: 3734
Registered: 12-28-2004
IP: Logged

Afaik that's more or less how it works. The algorithm goes as follows (it's from my memory):

- If total time spent on calculating moves since last snapshot is greater than X (where X is something like a second or two), make a new snapshot
- If there was no snapshot so far, consider 0th move a snapshot
- If there are too many snapshots, remove the oldest

Fun fact - I did not implement this in Flash DROD.

Fun fact 2 - I might be wrong, I remember this particular part of code from porting Flash DROD but I never investigated it too well.

____________________________
My website | Facebook | Twitter

Tuttle
Level: Smitemaster

Rank Points: 1545
Registered: 02-22-2003
IP: Logged

I don't know how the intervals are calculated, but in one room I was playing recently (lots of standard enemies, no scripts) it was around 300 moves between snapshots.

It's an interesting optimisation problem, because those snapshots all take space. If saves are purely based on the historical move list and don't store the snapshots then you could probably increase the frequency. If all those snapshots are committed to the database as well, I'd be wary of how much storage is used to optimise what is still a reasonably uncommon (but highly noticeable) case.

skell
Level: Legendary Smitemaster

Rank Points: 3734
Registered: 12-28-2004
IP: Logged

The snapshots are only stored temporarily until you leave the room afaik.

____________________________
My website | Facebook | Twitter

coppro
Level: Smitemaster
Rank Points: 1308
Registered: 11-24-2005
IP: Logged

I have no idea how it's currently implemented. But my guess as to a potential culprit would be that when recalculating states from a snapshot, the game doesn't take further snapshots. Interesting problem to determine the optimal amount of time to snapshot. I'll think about this a bit.

Tim
Level: Smitemaster

Rank Points: 1979
Registered: 08-07-2004
IP: Logged

I doubt it's too hard to keep an undo cache of 20 moves every time the undo key is pressed (you have to generate them if the last undo point is far away in the history anyway). That should solve the "too slow" problem.

On the other hand, I'd say that I believe it's not a good idea to expect undo to be fast by holding down the undo key, because the problem you will have is that you will over-undo it and end up redoing.

So my suggestion would be to limit undo to 2 to 3 turns a second (also depending on how much time it takes to draw everything on screen), and combine this with a 20 (or 40) turns cache should take care of the problem easily, as well as the problem of over-undoing.

____________________________
The best way to lose customers is to let little kids running loose on a forum with too many mod points.

Moo
Level: Master Delver
Rank Points: 224
Registered: 10-14-2006
IP: Logged

That's where the portable checkpoint/instant save key, and the redo key ideas would help. Either by meaning you don't have to undo a whole lot to begin with, or meaning that if you do overshoot, it's no problem getting back to where you really wanted.

TFMurphy
Level: Smitemaster
Rank Points: 3118
Registered: 06-11-2007
IP: Logged

skell wrote:
Afaik that's more or less how it works. The algorithm goes as follows (it's from my memory):

- If total time spent on calculating moves since last snapshot is greater than X (where X is something like a second or two), make a new snapshot
- If there was no snapshot so far, consider 0th move a snapshot
- If there are too many snapshots, remove the oldest

It would be useful if that was the case, but from reading the code, it seems to do this instead:

- If total time spent on calculating moves since last snapshot is less than 500ms, don't make a new snapshot.
- If total turns since the last snapshot is less than 30, don't make a new snapshot.
- If 30 snapshots have already been made, don't make a new snapshot.
- Otherwise, take a snapshot.

So in short, there must be both half a second and 30 turns between each snapshot, and only 30 snapshots may be taken.

If computation time between turns is constant, than that means the time it takes to rewind from one snapshot to the next is equal to Turns/4 seconds (since computation time from the previous snapshot to each rewound turn in course would have an average computation time of 250ms). So if there's 100 turns between two snapshots, even though it took 0.5 seconds to compute a single undo, it would take ~25 seconds to rewind the whole thing.

Note that this wasn't supposed to be *that* bad a thing when players were limited to a single undo (though the lack of continued snapshots after the 30th could be a problem with really intensive rooms). It's become more of a problem with the advent of UU, and the fact that the LCS puzzles are not hardcoded: the numbers next to the grid themselves are dynamically verifying the solution.

I'm not sure what's the best way to proceed from this, but that's my own findings on the subject.

coppro
Level: Smitemaster
Rank Points: 1308
Registered: 11-24-2005
IP: Logged

May I suggest the following algorithm:

Pick some definition of an interval for snapshots. 30 moves/half a second seems fine. Call this interval T. Let there be a configurable maximum number of snapshots.

Take a snapshot at each multiple of T. We will denote this as nT where n is the multiple of the snapshot.

If the total number of snapshots is greater than the maximum, then we need to delete one. I'll define the granularity of nT to be the largest power of 2 which divides n. We pick the smallest granularity such that we have at least two snapshots of that granularity, and delete the oldest.

If a recomputation is required, continue to take snapshots according to the above when recomputing the state.

This effectively implements an exponential backoff on snapshot times. If my intuition is correct, this would make undoing amortized constant time, although on very long rooms there will periodically be a long wait.

Moo
Level: Master Delver
Rank Points: 224
Registered: 10-14-2006
IP: Logged

Kind of related... Perhaps the last snapshot could be saved along with the checkpoint save, for long rooms. It takes longer and longer to display a room in the restore screen as the number of moves in its "active" save increases...

mrimer
Level: Legendary Smitemaster

Rank Points: 5056
Registered: 02-04-2003
IP: Logged

We don't save the in-memory state of the game anywhere in the data files. That would be a completely new feature, and not at all trivial to implement.

Having a progressive falloff strategy to be more dynamic sounds okay, but I don't have the time to carefully implement this for 5.0.1. We really need to get this upgrade released. For now, I'll make a couple simple changes. I'll allow up to 60 snapshot states to be retained instead of 30, and also allow taking a new snapshot every 15 turns instead of 30 turn, for when a long calculation time per turn is an issue, in order to help keep things more responsive.

____________________________
Gandalf? Yes... That's what they used to call me.
Gandalf the Grey. That was my name.
I am Gandalf the White.
And I come back to you now at the turn of the tide.