diff options
Diffstat (limited to 'doc/devel/netplay')
| -rw-r--r-- | doc/devel/netplay/notes | 21 | ||||
| -rw-r--r-- | doc/devel/netplay/protocol | 336 | ||||
| -rw-r--r-- | doc/devel/netplay/states | 178 | ||||
| -rw-r--r-- | doc/devel/netplay/todo | 120 |
4 files changed, 655 insertions, 0 deletions
diff --git a/doc/devel/netplay/notes b/doc/devel/netplay/notes new file mode 100644 index 0000000..afac628 --- /dev/null +++ b/doc/devel/netplay/notes @@ -0,0 +1,21 @@ +As the game currently unfortunately works with polling, this is how +to integrate network handling with the game. + +In the function called periodically by DoInput(), there should be a call +to netInput() somewhere at the beginning, and a call to flushPacketQueues() +somewhere at the end. + +netInput() checks all connections for incoming packets, and calls +the appropriate packet handlers. + +flushPacketQueues() sends all pending packets on their way, for all +connections. + +In between, you can call functions that enqueue packets. +You would also check the network state here to determine whether you need to +act on some packet that has been delivered to the local party. + + + + + diff --git a/doc/devel/netplay/protocol b/doc/devel/netplay/protocol new file mode 100644 index 0000000..5b82a1f --- /dev/null +++ b/doc/devel/netplay/protocol @@ -0,0 +1,336 @@ +There are several types of negotiations used to synchronised the parties +of a network connection. + +- Continue when we know the other is ready ("Ready") + This is used when both parties need to sending information to the + other side, but what each party is doing does not interfere with + what the other party is doing. +- Agree on changes ("Update") + This is used when the parties have changes to make to common data. +- Mutual agreement on an action ("Confirm") + This is used to end a state where both parties are modifying + common data. Both parties have to agree with the data for either + party to continue. +- Reset a connection. This is used to abort a game in progress and return + to the fleet setup menu. + +============================================================================ + +"Ready" negotiation. + +Sometimes the parties need to notify eachother of their local state, +and then go on when both are ready. For this purpose both parties signify +that they are ready by sending the READY message. When a party is ready +and has received notice that the other party is ready, it can go on. + +States: +0. notReady - send nor received READY + !localReady && !remoteReady +1. localReady - sent READY, not yet received READY + localReady && !remoteReady +2. remoteReady - received READY, not yet sent READY + !localReady && remoteReady +3. ready - sent and received READY + +Messages: +- READY - "I have nothing further to send at this point" + + +From state 0 (notReady): +local decision -> Send READY, goto 1 +received READY -> goto 2 + +From state 1 (localReady): +received READY -> goto 3 + +From state 2 (remoteReady): +local decision -> Send READY goto 3 + + +============================================================================ + +"Update" negotiation. + +During configuration, both sides may change the same properties. So that the +two sides don't have to take turns, the changes are made locally, and then +the changes are synchronised. + +To this end, each side has a state containing two copies of each property: + 1. The value of the property as it is locally + 2. The last value which it sent to the other side (until it is no longer + relevant for the protocol) + +The basic idea of the Update protocol is: +- both sides each send and receive one packet before being allowed to + send another one (we'll call this a "turn" here) +- when a packet has been sent and one has been received in a turn, + and the sent and received values are the same, then that value is the + agreed upon value. If the sent and received values differ, then a + tie breaker determines which one prevails. +- when the first local change of a turn is made, the change is sent to + the other side +- when a local change has been made while a packet has already been + sent this turn, the change will be made locally, but communicating the + change will be postponed +- when a turn ends while a change has been postponed, and this change isn't + negated by a remote change, then the change will be sent +- when a remote change arrives, and a packet has not been sent this turn, + the local state is updated with the change, and the same packet is sent + to the other side to confirm the change + +The tie breaker is required to always let one side win, and the other +side lose, given the same property. +Any function satisfying this requirement is usable, but the currently +used one will return true for the side which 'owns' the property, and +false on the other side. +Another tie breaker could be one which always lets the same side win, +regardless of the property. + + +The protocol: + +From state 1, {own=x0, sent=--}: +1a Local change x1 -> send(x1); state=2:{own=x1,sent=x1} +1b Received UPDATE(x1) -> send(x1); state=1:{own=x1,sent=--} + +From state 2, {own=x0, sent=x0}: +2a Local change x1 -> state=3:{own=x1,sent=x0} +2b Received UPDATE(x0) -> state=1:{own=x0,sent=--} +2c+ Received UPDATE(x1) -> state=1:{own=x0,sent=--} if winTieBreak +2c- Received UPDATE(x1) -> state=1:{own=x1,sent=--} if !winTieBreak + +From state 3, {own=x1, sent=x0}: +3a Local change x0 -> state=2:{own=x0,sent=x0} +3b Local change !x0 -> state=3:{own=xN,sent=x0} +3c Received UPDATE(x0) -> send(x1); state=2:{own=x1,sent=x1} +3d+ Received UPDATE(!x0) -> send(x1); state=2:{own=x1,sent=x1} if winTieBreak +3d- Received UPDATE(!x0) -> state=1:{own=x?,sent=--} if !winTieBreak + + +Explanation: +We keep track of the local value ('own'), and whether or not we sent a packet +in this turn ('sent' != '--'), and if we did, the last packet which we sent +('sent'). When we proceed to the next turn, 'sent' is set to '--'. + +State 1: We have not yet sent a packet this turn (which implies that we +haven't made a local change this turn). +1a. A local change is made. We update our local value, and send this to + the remote side. +1b. A remote change arrives. We don't have any local change ourselves, + so we accept the remote change, and sent it back to confirm. + With both a packet sent and one received, the turn ends, and 'sent' + is set back to '--'. + +State 2: We have sent a packet this turn (after making a local change), and +have not changed our local value since (or we have changed it and changed +it back). +2a. A local change is made. We update our local value, but we have already + sent a packet this turn, so we can't report it until the next turn. +2b. A remote change arrives, and it is equal to both our local value and + the value which we sent to the other side this turn. + This remote notification may be a confirmation of our update, or a + coincidental identical remote change. + Either way, the packet acts as a confirmation, and we do not need + to change anything. With both a packet sent and received, the turn ends + and so 'sent' is set back to '--'. +2c. A remote change arrives, and it is not equal to our local value (which + is the same as the value which we sent). + The tie breaker decides which value prevails. The same value will + prevail on the remote side, so there is no need to send any confirmation + packets. The turn ends, and 'sent' is set back to '--'. + +State 3: We have sent a packet this turn, and have made a local change since. +3a. A local change is made back to the value which we sent. No action + is required. +3b. A local change is made. We update our local value, but we have already + sent a packet this turn, so we can't report it until the next turn. +3c. A remote change arrives, and it is equal to the value which we sent + (which isn't equal to the current local value). + The sent/received value is the accepted value and the turn ends. + But we have changed our value since already, so as the next turn + starts, we immediately send an update. +3d. A remote change arrives, and it is not equal to the value which we sent + this turn. + + We win the tie break, so the value which we sent prevails. + But we have changed our value since already, so as the next turn + starts, we immediately send an update. + - We lose the tie break, so the value which the remote value sent + prevails. We accept the value and the turn ends. + (An alternative would be to consider the local change(s) which + we made after our change was sent as made in the following turn, + in which case we would send our current local value in the next turn. + The advantage would be that 3d- would become equal to 3d+, + so these could be joined (with 3c too), which saves a few + if-statements in the code, but this requires another packet to be sent + and replied to in what currently is 3d-.) + + +Proof outline that this works: +- The states can never get out of sync: + After both a packet has been sent and received, both sides (temporarilly) + have accepted the same value +- There can be no indefinite loop without ongoing local changes. + Once there are no more local changes: + from state 3 we always go to state 2 or 1, + from state 2 we always go to state 1 + from state 1 we can only go back to state 1, and only when a packet + has been received. + So eventually, both sides are in states 1. With both sides in state 1, + no packets have been sent in the current turn, so no more packets are + there to be received. +- Both sides can make changes, as long as the side which wins the tie breaks + stops making changes now and then: + Without making local changes, a side will go to state 1 eventually. + If a side makes a local change, and this is received by the other side + while it is in state 1, then that other side will accept the change. + + +The Confirm negatiation is used to finish the Update negotiation. +This works because local changes triggered by the reception of remote changes +are treated as local modifications for the purpose of the Confirm negotiation. +And this can be done because whenever the Confirm negotiation is in a state +where remote changes may be expected, local modifications are still allowed +(possily after sending a CANCEL packet). + + +============================================================================ + +"Confirm" negotiation. + +Some actions (like agreeing on a configuration) require confirmation +from both parties. This section documents the handshaking protocol involved. + +Each player must manually confirm the action. +After a player has confirmed an action, he may cancel it as long as +he hasn't received a confirmation from the other party. + +All messages arrive in the order sent. + + +States: +0. waiting + !handshake.canceling && !handshake.localOk && !handshake.remoteOk +1. localOk (cancelable) - sent CONFIRM1 (since last CANCEL) + !handshake.canceling && handshake.localOk && !handshake.remoteOk +2. remoteOk (cancelable) - received CONFIRM1 + !handshake.canceling && !handshake.localOk && handshake.remoteOk +3. committed - sent CONFIRM1 (since last CANCEL, + received CONFIRM1, + sent CONFIRM2 (since last CANCEL) + !handshake.canceling && handshake.localOk && handshake.remoteOk +4. cancelWaiting - sent CANCEL + handshake.canceling && !handshake.localOk && !handshake.remoteOk +5. cancelLocalOk - sent CANCEL and ready to send CONFIRM1, + but received no CANCELACK + handshake.canceling && handshake.localOk && !handshake.remoteOk +6. cancelRemoteOk - sent CANCEL and received CONFIRM1, + but received no CANCELACK + handshake.canceling && !handshake.localOk && handshake.remoteOk +7. cancelCommitted - sent CANCEL and ready to send CONFIRM2, + received CONFIRM1, + but received no CANCELACK + handshake.canceling && handshake.localOk && handshake.remoteOk +8. done - sent and received CONFIRM1 and CONFIRM2 + (since last CANCEL) + + +Handshake messages: +- CONFIRM1 - "the current local configuration is OK for me" +- CONFIRM2 - "acknowledging your CONFIRM1; my own configuration is unchanged + since I sent CONFIRM1 (after the last CANCEL)" +- CANCEL - "forget about my earlier CONFIRM1" +- CANCELACK - "received your CANCEL" +MESSAGE(x) indicates any other message. + + +From state 0: (waiting) +local confirmation -> Send CONFIRM1, goto 1 +local changes -> Send MESSAGE(changes) (goto 0) +received CONFIRM1 -> goto 2 +received MESSAGE(changes) -> Process(changes) (goto 0) + +From state 1: (localOk) +local cancel -> Send CANCEL, goto 4 +received CONFIRM1 -> Send CONFIRM2, goto 3 +received CONFIRM2 -> Send CONFIRM2, goto 8 +received MESSAGE(changes) -> Send CANCEL, Process(changes), goto 4 + +From state 2: (remoteOk) +local confirmation -> Send CONFIRM2, goto 3 +local changes -> Send MESSAGE(changes), (goto 2) +received CANCEL -> Send CANCELACK, goto 0 + +From state 3: (committed) +received CONFIRM2 -> goto 8 +received CANCEL -> Send CANCELACK, goto 1 + +From state 4: (cancelWaiting) +local changes -> Send MESSAGE(changes), (goto 4) +local confirmation -> goto 5 +received CONFIRM1 -> goto 6 +received CONFIRM2 -> goto 6 +received CANCELACK -> goto 0 +received MESSAGE(changes) -> Process(changes), (goto 4) + +From state 5: (cancelLocalOk) +local cancel -> goto 4 +received CONFIRM1 -> goto 7 +received CONFIRM2 -> goto 7 +received CANCELACK -> SEND CONFIRM1 goto 1 +received MESSAGE(changes) -> Process(changes), goto 4 + +From state 6: (cancelRemoteOk) +local confirmation -> goto 7 +local changes -> Send MESSAGE(changes), (goto 6) +received CONFIRM2 -> (goto 6) +received CANCEL -> Send CANCELACK, goto 4 +received CANCELACK -> goto 2 + +From state 7: (cancelCommitted) +received CONFIRM2 -> (goto 7) +received CANCEL -> Send CANCELACK, goto 5 +received CANCELACK -> Send CONFIRM2, goto 3 + +On receiving local confirmation, sending CONFIRM2 is a shortcut for +sending CONFIRM1 followed by CONFIRM2. Receiving CONFIRM2 from localOk +and cancelLocalOk is accepted just for this shortcut. + + +To prove there are no race conditions, I examine all the combinations +of states and messages that are underway. Whenever the order of actions +isn't fixed, the result should be the same (eg. recv(CONFIRM1) followed +by send(CANCEL) should leave the party in the same state as when +the send(CANCEL) preceded the recv(CONFIRM1)). +I also check whether it is possible for packets to arrive that +aren't expected. + + +============================================================================ + +"Reset" negotiation. + +See src/sc2code/netplay/proto/reset.c + + +============================================================================ + +Battle ending negotiation. + +This negotation consists of: +1. a 'Ready' negotiation, before stopping sending frame data +2. communication of each sides current battle frame count +3. the side running behind processes more frames to catch up + + +States: + +0. Playing +1. localReady +2. remoteReady +3. countSent +4. catchingUp +5. awaitingCatchup + +// Unfinished... partially described in readyForBattleEndPlayer() + + diff --git a/doc/devel/netplay/states b/doc/devel/netplay/states new file mode 100644 index 0000000..9727172 --- /dev/null +++ b/doc/devel/netplay/states @@ -0,0 +1,178 @@ +== Any connected state == +Some packets may be sent and received in any state except +NetState_unconnected. +These are: PING, ACK, ABORT, RESET +These are not listed below at each individual state. + +Whenever a connection is aborted, the state is returned to +NetState_unconnected. This state transition is not listed below at each +individual state. + + +== NetState_unconnected == +NetState_unconnected is the initial state. + +NetConnection.state: NULL + +Packets ok to send: none +Packets ok to receive: none + +Next state: + NetState_connecting -- connection attempt in progress + + +== NetState_connecting == +NetState_connecting indicates that a connection is in progress. + +When the connection is established, the state is changed to NetState_init +and InputFunc is set to DoNetworkInit. + +NetConnection.state: instance of ConnectStateData + +Packets ok to send: none +Packets ok to receive: none + +Next state: + NetState_init -- connection established + + +== NetState_init == +NetState_init is for initialising the connection before actual game +information is sent. + +As this state is entered, an INIT packet is sent. When an INIT packet +has also been received, the state is set to NetState_inSetup and +InputFunc is set to DoMelee. + +NetConnection.state: instance of BattleStateData + +Packets ok to send: INIT +Packets ok to receive: INIT + +Next state: + NetState_inSetup -- received an INIT packet + + +== NetState_inSetup == +NetState_inSetup is the state in which the fleet configuration is negotiated. + +This does not necessarilly mean that the fleet setup screen is visible; +this state is also held after a battle when the battle outcome is still +displayed. + +Each side may send fleet configuration changes to the other side, by means of +FLEET and TEAMNAME packets. Agreement on configuration settings is provided +through the Update negotiation. +The Confirm negotiation is used to end this state and go to +NetState_preBattle. At this time InputFunc is set to DoPreMelee. + +NetConnection.state: instance of BattleStateData + +Packets ok to send: FLEET, TEAMNAME, HANDSHAKE0, HANDSHAKE1, + HANDSHAKECANCEL, HANDSHAKECANCELACK +Packets ok to receive: FLEET, TEAMNAME, HANDSHAKE0, HANDSHAKE1, + HANDSHAKECANCEL, HANDSHAKECANCELACK + +Next state: + NetState_preBattle -- configuration has been confirmed + + +== NetState_preBattle == +NetState_preBattle is used for non-interactive battle negotiations. + +One side sends the random seed; the other receives it. +Both sides send their input delay value. +The Ready negotiation is used to end this state and go to +NetState_interBattle. + +NetConnection.state: instance of BattleStateData + +Packets ok to send: SEEDRANDOM, INPUTDELAY, READY +Packets ok to receive: SEEDRANDOM, INPUTDELAY, READY + +Next state: + NetState_interBattle -- ready to continue + + +== NetState_interBattle == +NetState_interBattle is used to allow each side to do some local +initialisations before moving on. +The Ready negotiation is used to end this state and go to +NetState_selectShip, or if all sides have selected a ship, to +NetState_inBattle, or if there are no more ships in a fleet, +to NetState_inSetup. + +If there are no more ships, the the Ready negotiation is used to +enter NetState_inSetup. + +NetConnection.state: instance of BattleStateData + +Packets ok to send: READY +Packets ok to receive: READY + +Next state: + NetState_selectShip -- ready to select the next ship + NetState_inBattle -- ready to start the battle + NetState_inSetup -- no more ships; game over + + +== NetState_selectShip == +NetState_selectShip is where a side may select their ship. The other +side is waiting for notice of this selection. +As soon as the selection has been sent or received, the state is changed +back to NetState_interBattle. + +NetConnection.state: instance of BattleStateData + +Packets ok to send: SELECTSHIP +Packets ok to receive: SELECTSHIP + +Next state: + NetState_interBattle -- a selection has been made + + +== NetState_inBattle == +NetState_inBattle is where the actual melee takes place. +Both sides send their input until the game is over, at which point +the Ready negotiation is used to end this state and go to +the NetState_endingBattle state. Until the Ready negotiation has been +completed, the simulation is continuing. + +NetConnection.state: instance of BattleStateData + +Packets ok to send: BATTLEINPUT, READY +Packets ok to receive: BATTLEINPUT, READY + +Next state: + NetState_endingBattle -- ready to end the battle + + +== NetState_endingBattle == +NetState_endingBattle is where the local side waits for the remote +battle frame count, after it has sent its own. When it arrives, +the state changes to NetState_endingBattle2. + +NetConnection.state: instance of BattleStateData + +Packets ok to send: BATTLEINPUT, FRAMECOUNT +Packets ok to receive: BATTLEINPUT, FRAMECOUNT + +Next state: + NetState_endingBattle2 -- we know when to end the battle + + +== NetState_endingBattle2 == +NetState_endingBattle2 is where the side with the lowest battle frame count +catches up with the other other side, while the other side waits. +The Ready negotiation is used to signal that each side is ready, +and the state changes to NetState_interBattle. + +NetConnection.state: instance of BattleStateData + +Packets ok to send: BATTLEINPUT, READY +Packets ok to receive: BATTLEINPUT, READY + +Next state: + NetState_interBattle -- get ready for the next ship + + diff --git a/doc/devel/netplay/todo b/doc/devel/netplay/todo new file mode 100644 index 0000000..33102c7 --- /dev/null +++ b/doc/devel/netplay/todo @@ -0,0 +1,120 @@ +High priority items: + + +Medium-priority: +- For the battle ending synchronisation, set the end at at least + getBattleInputDelay() + 1 frames in the future (instead of just 1), + so that there will be no hickup during the end synchronisation. + Also check this value for incoming packets. +- If a player only moves away from 'Battle!' there's no need for the other + to have to reconfirm. +- decent pause handling +- make compilation of crc.c and checksum.c conditional. +- negotiate checksum interval +- Closing and destroying of NetConnections is a terrible mess. +- Checks allConnected() shouldn't be needed if CHECK_ABORT is set + on disconnect. +- Shorten or lengthen the time between frames depending on how full the input + buffer is, to prevent one side constantly stalling when the connection in + one direction is slower than in the other direction. + + +Low-priority: +- Some difference in pictures to indicated confirmed/unconfirmed. + A check mark perhaps. +- Check whether the random seed and frame delay have been agreed before + continuing (in doConfirmSettings). +- Replacement for TOS. It is IPv4 only. +- Integrate network check functions with doInput + It will be easy to get rid of the separate threads then too. +- The state changes from interBattle to interBattle. That shouldn't happen, + but it doesn't seem to cause any problems. Need to investigate. + Addition: negotiateReadyConnections() is called again just to make sure + all sides pass this checkpoint. This is not a problem. It should be + documented in STATES though. +- More files define NETCONNECTION_INTERNAL than they should. +- voice transmission during the game (using an external lib) + read ramjee94adaptive.pdf +- Keep-alive packets. Store time of last packet sent, use alarms to determine + when to send the next one. Count received messages? +- Some way to (optionally) hide your fleet setup until the start of the + game? With either a previously determined maximum fleet value, or + just display a number to the opponent. +- (when ships stats are in the content) Negotiate the ship stats, so people + can play with non-default ships. +- Pre-fleet-setup setup + The values negotiated could include handicapping (different values for + each player) + - hide fleets (also handicapping here) + - maximum number of ships per side + - maximum ship cost per side + - ship properties +- Send taunts (prerecorded samples) at the touch of a button? + Use taunt add-on packages? Send the opponent's package before the start + of a game? + + +Future improvements/optimisations: +- For BSD sockets: use dup2() to move fds to lower values, so that less fds + have to be checked on select(). +- Use writev() to send multiple packets in one syscall, instead of + calling send() for each packet. +- Refusing games with both parties network controlled is not always + necessary. In theory it should be possible to have a client work + as "proxy". The client can watch as the actual players play the game. + Checking for "loops" would be tricky (eventually there should be a human + or computer controller for each side). +- Concurrent selection of ships. Note that if this is handled properly, it + will also be easy to take care of the "Allow Shofixti to choose last" bug. + Note that one party will still have to send his choice to the other side + first, which may be "exploited". Encryption would take care of this, + but at the least make sure the same player who gets to chose first + every time. +- meta-server. Use HTTP? Existing libs can be used, no problems with NAT, + human-readable. Speed is not an issue. +- move to UDP. Repeat past battleinput packets for each new packet that + is sent until they are confirmed. +- Once the protocol is stable: register the port number with IANA +- Per state data (in NetConnection.stateData) is unnecessarilly complicated. + Putting all fields directly in NetConnection simplifies things a lot. + It's not as generic, but this code won't be used elsewhere anyhow. +- Send captain names to the other side + + +Bugs: +- as positions are dependant on the screen resolution, you won't be able + to keep sync on games with a different resolution. +- collision detection is dependant on the images used. Using different + graphics packs will result in a desync. +- Both sides need identical battle frame rates. This value is not + negotiated. +- If one player closes the connection while the other player is selecting + a ship to put in his fleet, or loading a fleet, the "Network Control" + button won't be updated. +- If one side is computer-controlled, sync loss will occur, because the AI + uses the RNG. It needs its own RNG context. +- Pressing F10 to exit the supermelee setup when a connection is active + will cause an attempt to draw a NULL frame. (possibly the disconnect + feedback) + + +Final actions: +- Check out TODO, XXX, WORK tags +- memleak testing + - check for and remove mtrace()/muntrace() calls. +- update documentation + - FILES, also note which part of the separation they are in +- check coding style (search for '\>(') +- compile with maximum warnings + + +To put in the announcement of Netplay: +- Slow connections is acceptable. Packet loss isn't. + + +Bugs and todos unrelated to netplay. +- other player being able to choose the next ship after 3 seconds + of inactivity +- DoRunAway() shouldn't be handled in ProcessInput() + + |