ClonesGame.com Forums

[Simon]

Hi folks,

the hosting player is at an advantage over everyone who joins, especially over those with high pings. I experience this every time as I connect from Germany to the devs' games hosted in Canada, with a ping of around 200 ms.

The goal of this thread is to discuss whether this is an issue worth fixing, and if so, what solution to go for.

Current implementation: Skill assignments are delayed according to the ping to the server. Thus, the host's assignments trigger instantly, whereas the joiner's assignments take some time until they trigger. This is true both for regular assignments as it is for queued ones.

However, validity of the assignment is checked immediately, whereas the assignment itself (queue or direct) will be delayed as just explained.

There are maneuvers that can't be carried out by a joiner with a somewhat high ping. Imagine two walls close to each other, and you wish to gulp-up through them. The distance between the walls will cancel the gulper, and the walk time is shorter than the ping. With a higher ping, you cannot reassign gulper quickly enough. You can't even queue it ahead of the time, since you can't queue gulper to gulper (which is checked immediately without delay), not even when you do it late enough so that the assignment would be delayed to the proper time!

Besides all this, it's obvious that the host is at an advantage just for getting more time to react. This issue gets more severe when players get stronger, since there are much more events that need attention and quick reaction.

Solution with latency: All players' assignments get delayed by the same time, which is the maximum of all pings of the active players. Also, the validation of assignments should occur at the same time as the actual assignment, not at the instant of pressing the morph key. IIRC this is how Starcraft 1 works.

Solution with backtracking: All assignments are carried out immediately, and other players have to go back in time and recalculate. This makes the assigned clone jump a bit on their screen. I use this in Lix (L++), where pixel precision is perceived to be even more important than in Clones. Players felt that this was a major advantage over previous methods to play Lemmings over the net, which are Snes and Genesis emulators. Obvious cosmetic disadvantage: The jump of the assigned lix is noticable, but it's not that large, except when the given skill was Jumper.

-- Simon

[rt]

Yes lag sucks. When i host a match on the net i normally click the clock icon once or twice which slows down the logic updates from 90ms apart to 100ms or 110ms apart. The default for singleplayer is 75ms. This helps a bit.

I can see that performing morph validation on the server-side only would be more consistent and allow a lag player to at least offset their timing to perform any sequence.

The latency approach might be most fair, everyone is delayed at the same rate.

Regarding the backtracking solution, it seems that it would allow for some confusing situations, consider:
- Blue group at 500ms lag, Green is host.
- Blue walker going towards Green Doppel
- Blue Spins at the last possible moment, going up past the Doppel locally.
- Green would see the Blue walker hit the Doppel and turn around, and might decide to Atomize the Doppel to let his own clones follow, but then 500ms later Green would see that Blue clone jump to be Spinning up past where the Doppel was.
Am i understanding this approach correctly?

Alternate solution: All competitive Clones players move to Canada. The springtime is lovely here.

[Simon]

Yes, this example is possible with the backtracking approach. It's another downside of that solution. Such examples get more critical when the ping approaches or exceeds human reaction time. 500 ms of lag is extremely much though, it shouldn't occur in a real match.

Backtracking is also more taxing on memory and processing time, though I'm sure it can be implemeted efficiently. It's a choice of priority, I'm not sure how much of the Clones play experience depends on this exact precision.

-- Simon

[tom]

validity of the assignment is checked immediately, whereas the assignment itself (queue or direct) will be delayed as just explained.

Not checking the validity of the morph immediately should be a simple change. I think currently it does the check both immediately, and at the time the target clone receives the morph command on the client. The immediate check was added as an optimization a while ago, but as you explained, it can affect gameplay.

There are maneuvers that can't be carried out by a joiner with a somewhat high ping. Imagine two walls close to each other, and you wish to gulp-up through them. The distance between the walls will cancel the gulper, and the walk time is shorter than the ping. With a higher ping, you cannot reassign gulper quickly enough. You can't even queue it ahead of the time, since you can't queue gulper to gulper

We may have to revisit the queuing rules for some of the morphs in light of this issue. For gulp and clob morphs assignments, perhaps the queuing rule should be as follows:
- if not already gulping or clobbing, then use current rules
- if already clobbing or gulping, then queue the new clob or gulp morph. The queued morph gets executed at the next instance where the clone is walking and the queued morph would remove part of the terrain

Besides all this, it's obvious that the host is at an advantage just for getting more time to react. This issue gets more severe when players get stronger, since there are much more events that need attention and quick reaction.

Yes, this effect is noticeable with strong players. We added morph queuing to combat this problem, but in the end, lag is unavoidable so some tradeoff is necessary.

Solution with latency: All players' assignments get delayed by the same time, which is the maximum of all pings of the active players.

I think this is a good solution for very competitive matches, where fairness is desired. On the other hand, the lag can be used to handicap stronger players, so I think lag equalization should be optional.

Solution with backtracking: All assignments are carried out immediately, and other players have to go back in time and recalculate. This makes the assigned clone jump a bit on their screen. I use this in Lix (L++)

I knew about this technique but I never bothered to seriously consider it because of the assumption that it would be too difficult to implement efficiently. We did, at one point, have a feature that allowed a snapshot of the game state to be efficiently captured so that the current game state can be "reverted" to that point, and executed again with different conditions. However, this feature hasn't been tested in a while so it's probably really buggy. What method does L++ use to implement the backtracking? It's a tough problem, especially in Clones where there are many interactive traps, destructible terrain, and possibly thousands of clones to deal with. As rt mentioned, it could probably lead to some confusing (and frustrating) situations. I think with backtracking, the game becomes less predictable, but with lag equalization, you can deterministically plan for it (using morph queuing, for example).

[Simon]

- if not already gulping or clobbing, then use current rules
- if already clobbing or gulping, then queue the new clob or gulp morph. The queued morph gets executed at the next instance where the clone is walking and the queued morph would remove part of the terrain

It's very fine if you extend the queue possibilities, but then the need to erase the queue becomes even more important than it is now. The first walker assign might erase the queue, and the second one assign walker.

I think this is a good solution for very competitive matches, where fairness is desired. On the other hand, the lag can be used to handicap stronger players, so I think lag equalization should be optional.

Yeah, ranked matches really should use something like this to make the ranks more significant.

What method does L++ use to implement the backtracking?

I'm probably not very efficient. I have two gamestates which I alternately overwrite each second, two more which I alternately overwrite all 10 seconds, and the state from the very beginning. A gamestate is a whole copy of the land and all other information -- the game is a resource groundhog with larger maps. Reloading and recalculating is done from the youngest one that's still older than the incoming change.

A different approach would be to put all land alterations into a time-ordered list, and each entry saves which pixel changed from what state into what other one. This makes it easier to obtain the earlier land, but you must still save all non-land data explicitly in some time intervals, and the recalculation remains.

Or maybe backtracking simply isn't feasible for games where this much of the environment can change.

I think with backtracking, the game becomes less predictable, but with lag equalization, you can deterministically plan for it (using morph queuing, for example).

Hmm, it doesn't make it less predictable. If I sabotage a player who has 1 sec to react, and the lag is 200 ms, then he has 800 ms of reaction time regardless of latency or backtracking. The apparent chaos of the backtracking comes from the non-trustability of the most recent 200 ms, something which isn't natural in singleplayer. Latency isn't natural there either, but it's a more intuitive concept.

-- Simon

[geoo]

On the matter of the backtracking method...

[...]As rt mentioned, it could probably lead to some confusing (and frustrating) situations.

Every scenario of the kind rt described has an equivalent scenario with the current implementation, just with the annoyance for the other party.
In this particular instance, the analogous scenario is: You try to spin over the blocker, but the assignment is delayed, and subsequently the clone spins into the wrong direction after turning around. You can try to anticipate how much walking distance the lag will make up for, which doesn't apply to the original issue, but it's still about as annoying, and makes precision moves very difficult.

The thing is, in the current implementation, the lag affects the assigning player with every single assignment. With the alternative, it only affects the other player when he happens to be watching the morph assignment in this precise moment, poised to react, which is a less frequent occurrence. So if he hasn't the clone to perfrom the reaction already selected, the belated update will be performed before the harm is done (i.e. before the player has reacted to the percieved turn of events which was changed belatedly), unless the lag is massive. But in that case:

In your hypothetical scenario, the delay was 500ms. But if you got the same delay for every of your morph assignments, the game gets nigh unplayable. 500ms lag is too much in any case. (I don't know how frequently you two have been on the client side of things with a non-negligible lag, but when there are lag spikes, there's not much you can do but watch your clones do random things. With normal lag between Europe and Northern America, say 100-150, it's ok, but still a nuisance at times.)

Now to provide some real-world observations: I've been playing L++ a lot, with the central server being located in the US, and I can't even remember a single instance where the delayed updating would have caused some confusing situation or wrong assignment for me (save for one instance where the delay had been several seconds, because someone had massive connectivity issues, and like every 30 seconds the game situation changed completely because another update from him got through. In this case the downside is that all players are affected and not only the one with the sucky connection, but this could be prevented by treating players with the old method if their ping exceeds a certain high value, like 500ms). I never have issues with the controls in L++ as every assignment gets done as I want is, while I still keep having issues with the Clones controls (might partly also be attributed to the assignment scheme, i.e. click clone first, then press skill button instead of the Lemmings way).

So in clonclusion, I'd prefer the backtracking realization over the current one any day, but I see why you'd be hesitant with the code reworking and the implementation difficulties it would imply.

[tom]

I'm probably not very efficient. I have two gamestates which I alternately overwrite each second....

...A different approach would be to put all land alterations into a time-ordered list... but you must still save all non-land data explicitly in some time intervals, and the recalculation remains.

In Clones, the land (terrain) is divided/allocated in 128x128 pixel blocks in a sparse matrix style. If there is no terrain in a section of the level, then no memory or graphics is allocated for that area. This makes it really efficient to create large levels with a lot of open areas. On the other hand, this data structure also makes it more efficient to "save" and "restore" the state of the terrain. Instead of keeping track of the pixel alterations done, you just keep track of which blocks were modified since the last snapshot and save those only.

Hmm, it doesn't make it less predictable. If I sabotage a player who has 1 sec to react, and the lag is 200 ms, then he has 800 ms of reaction time regardless of latency or backtracking. The apparent chaos of the backtracking comes from the non-trustability of the most recent 200 ms, something which isn't natural in singleplayer. Latency isn't natural there either, but it's a more intuitive concept.

Well yes, technically both methods are equally unpredictable (chaotic) to some extent. But I think the backtracking method increases the overall amount of chaos for all players especially when you have a player with a higher lag. The level of chaos is proportional to the lag, so in the backtracking method, if you have a player that is experiencing high lag, everyone suffers from the introduced chaos. In the current method in clones, only that one player with high lag suffers (unless the proposed lag equalisation is implemented), so any connectivity issues are limited to that one player.

@geoo, you mention that your real world observations with L++ prove that the backtracking method works well. Did you also try the case of 4 to 8 players with one of the players from Australia? It would be nice to do some specific experiments on this. The easiest way to do this is by introducing simulated lag in the network connection (I have my workstation setup to do this).

Perhaps the ultimate approach would be a combination of backtracking and delayed morphs. For example, if the lag is 200ms, then when issuing a morph to a clone, it is backtracked by half the lag (100ms). Just a thought.

[geoo]

Well yes, technically both methods are equally unpredictable (chaotic) to some extent. But I think the backtracking method increases the overall amount of chaos for all players especially when you have a player with a higher lag. The level of chaos is proportional to the lag, so in the backtracking method, if you have a player that is experiencing high lag, everyone suffers from the introduced chaos. In the current method in clones, only that one player with high lag suffers (unless the proposed lag equalisation is implemented), so any connectivity issues are limited to that one player.

I think that specific issue would be solved by what I proposed in my previous post, namely treating players with an unusually bad ping with the current implementation, as not to affect other players. Then the time to backtrack on would be limited by a constant you can choose, and players that have a ping worse than that constant get delayed assignments without affecting the other players.

@geoo, you mention that your real world observations with L++ prove that the backtracking method works well. Did you also try the case of 4 to 8 players with one of the players from Australia? It would be nice to do some specific experiments on this. The easiest way to do this is by introducing simulated lag in the network connection (I have my workstation setup to do this).

We've had a few 7/8P games with people from Northern America, Europe and New Zealand, and I didn't note any issues either.
All you see at times is something like another player's Lix falling 2 or 3 pixels off a ledge, only to re-appear a fraction of a second later as a builder starting at said ledge. But I've never come across an instance where this has actually (wrongly) affected a decision of mine (because the short time-interval inbetween, and because these occurrences are usually at a different place than my current focus during that split second), so it's nothing more than a visual quirk, if you even notice it.
Note that in Lix, the characters move a lot faster than in Clones, so in Clones this effect would be even less pronounced.
If you want to see for yourself, just contact me and we can do some testing together, there really isn't much in regards of chaos with the backtracking in effect. I'll give you a link to a working build of Lix then.

Perhaps the ultimate approach would be a combination of backtracking and delayed morphs. For example, if the lag is 200ms, then when issuing a morph to a clone, it is backtracked by half the lag (100ms). Just a thought.

It seems to me that this approach would rather combine the disadvantages of the two methods rather than the advantages: You still sacrifice full precision by having the morph assignments delayed, but also have the side-effects of backtracking (which, as I said, have never been an issue to me though).

[rt]

There appears to be two concerns, first that a remote player with high lag will have a poor game experience because of morph delay, second that local players will have a poor experience seeing the game state jump when backtracking is enabled with a high lag remote player. Both of these are bad in the extreme case. The lag issue cannot be solved, only morphed into another form. The question is if it's possible to reduce the two concerns above so that they are either below human detectable threshold or occur so infrequently that it's worth the occasional frustration.

What is the acceptable morph delay? When i press the Mold hotkey how fast should the clone respond? 50ms? 100ms? 150ms? 200ms? What is the biggest game state jump that is acceptable? If a backtrack requires a 150ms jump then perhaps splitting it to make a 75ms morph delay (1 logical update) and a 75ms game jump might be the best of both worlds, assuming that a 75ms delay is not noticeable.

I'm interested in testing this out and tweaking the parameters to see what can be accomplished. There are other issues with Clones backtracking such as triggering game messages twice ("Player X has been eliminated"), and trap events keeping in sync since the laggy remote client will trigger first, Light Clone speed, but for our first prototype we can assume a level with no editor trap logic and no land-affecting particles just to evaluate the playability.

[Simon]

What is the acceptable morph delay? When i press the Mold hotkey how fast should the clone respond? 50ms? 100ms? 150ms? 200ms?

Immediately. :/

I have a Quake player in my peer group, and he gets upset by minimal delays due to the input hardware itself, or driver configuration. (Also to him: "what would be your reaction if your hardware input was delayed by 75 milliseconds?" -- "that would be a joke.") If a player is sensibilizied about this issue, you want the game to react as quickly as possible if you wish them to enjoy it. Even players who don't know the issues will feel it somewhat, but can't tell what it is.

I don't remember where I read it, it was on some game design site, but a quote there was "When the player presses the jump key, the character should jump." It should not wait for the time when the jump would look good, it should just fricken jump. >_>

Why can Starcraft 1 get away with latency? It doesn't hinder the player there. Unit selection is instantly, since there is no gamestate modification. Giving orders is delayed, but it doesn't throw off the timing much if the drone will go build 200 ms later in an internet game than in a LAN game, or if it will mine minerals 200 ms later, or attack if everyone has this delay on his orders. This is because neither the building site nor the minerals move. The attack command just remembers the target, it will always adjust properly even if the target moves. The only things people refrain from in internet games are e.g. super precise mutalisk micro, they opt for more safety here.

In Clones, nearly all morph orders are more like muta micro than like build commands...

but for our first prototype we can assume a level with no editor trap logic and no land-affecting particles just to evaluate the playability.

Yes, this is the important benchmark. I might even like a dual solution that backtracks when possible, and introduces latency for scripted levels.

-- Simon