~~ Networking Concepts ~~

This section will cover basic networking concepts, not just those applicable to video games.
There are many resources covering these topics so I will try to give the brief rundown as is relevant to video games.
This is an oversimplification, but should give you some idea of how things work.

You can skip this section if you are familiar with networking basics.

How Data Goes from Point A to Point B

When two computers try to send data to each other over the internet that data must have some way of findings its way to the other
computer. The protocol for doing that is known as Internet Protocol (IP). Data is transmitted via *packets*. These packets contain
not only the data that the user wishes to send, but extra information in *headers* that contain information on where to send that
data to and more. When a sender, the *source host*, tries to send data to the *destination host*, it includes an *IP address* in
the packet header. This address can be thought of as the destination house address.

However, is it usually not the case that there is a direction connection between the two computers / *peers*.
Instead the packet is sent to some other in-between computer that then sends it to another in-between computer and so on, until it
reaches the destination. These *hops* between computers may be unreliable. The internet was built to withstand large scale
disruption by allowing packets to take multiple *routes* between the source and destination, but even with that packets may
still be *lost*.

IP Addresses

There are two main types of IP addresses you will probably encounter, IPv4 (INET), and IPv6 (INET6). In the past IPv4 had enough
possible address values for all the computers on the internet, but as the internet rapidly increased in size, they ran out of
IPv4 addresses, this oversight led to the creation of IPv6, which has more than enough possible values. But much of the software
running on the internet was programmed to work with IPv4 already, and so to prevent having to rewrite a ton of software internet
service providers started adding *subnetworks*.

The idea is that you can have a computer with one IPv4 address that accepts packets and distributes it to a
bunch of computers all on the same *network* that each have an address that is only valid within that network.
This led to the current structure of the internet consisting of networks of networks. And using IPv6
does not overcome this new problem, since the physical network structure is not changed by choice in address type.

Since personal computers now each exist on their own *local area network* (LAN), and talk to computers on the
*wide area network* (WAN), we now need to go through the *router* that manages communication between the LAN and the WAN.
This also means that there are now two IP addresses involved, the private address (inside our network), and the public address,
which is our address as seen from outside our network. There are services that can tell you what your public address is, for
more on that look into STUN, TURN, and ICE.

There are also several more layers in between us and the LAN, but those are outside of our control. We often need
to configure our routers to allow certain traffic through. This usually comes in the form of *port forwarding* when hosting a server locally.

Ports

In addition to IP addresses telling us where to send information to, we may also have multiple destinations at that destination
computer. If you are running two different networked applications on the same computer then the packets need to not only know
which computer to go to, but which application on that computer once it gets there. This is what the *port number* is for.

Each application is assigned a port number that is required in addition to the address. If a server is hosting some application on
some given port number it will accepts packets targeted at that port number. But if it's part of a local network, the router does
not know that, and so it needs to be configured to allow packets with the target port number to pass through. This is what port
forwarding is, we are forwarding our port through the router. Routers typically have a website that can be used to configure them.
You can access that website using a web browser. The address is some local network address, such as "192.168.0.1". You can find
instructions for your specific router online. If you are hosting on a server provided by some service, you will probably need to
configure some network traffic / firewalls rules, similar to port forwarding.

Communication Protocols

There are two widely used protocols for transmitting data on top of IP. They are the User Datagram Protocol (UDP), and
Transmission Control Protocol (TCP). A protocol being the agreed upon way to communicate between computers. UDP is the more raw
way to communicate, it leaves it up to the user to do what needs to be done. UDP does not have connections, establishing a
connection is left up to the user. UDP simply tries to send the given data to the destination, and it may fail, or arrive out of
order.

TCP does have connections, and many other things handled for the user, including reliable, order communication. The way it
achieves this is by sometimes resending packets until it gets confirmation from the other computer that it received the data.
It also assign ordering values to packets so that it can put them back in order on the receiving end. TCP seems a lot better
than UDP, but it comes with downsides. The resending behavior is not ideal for realtime video games due to it causing
high latency spikes.

References

+ https://en.wikipedia.org/wiki/Internet_Protocol
+ https://en.wikipedia.org/wiki/Local_area_network
+ https://en.wikipedia.org/wiki/Wide_area_network
+ https://en.wikipedia.org/wiki/Port_(computer_networking)
+ https://en.wikipedia.org/wiki/Port_forwarding

~~ Game Networking Concepts ~~

There are different game networking models for different types of games. This section will cover some of them.
You can skip this section if you are familiar with game networking concepts.

Multiplayer Preparations

Adding multiplayer after the fact to a game may be infeasible. It's a good idea to think about multiplayer from the beginning.
However, not all the details need to be thought out from the beginning. With good preparation adding multiplayer can be made much
easier. Making the game logic mostly deterministic or entirely deterministic in the case of deterministic lockstep networking can
make adding multiplayer much easier. To achieve this it is important to have all the game's logic execute in a fixed timestep
update. Which means that the delta time used in physics processes, timers, etc is fixed, rather than variable.

Another important preparation is to have some convenient way of copying input and game state and saving it (in memory to a buffer).
This is required by several networking methods that require rewind and replay of the game. To achieve this it is recommend for
your entities to have a copy implementation and for the visual aspect of your entity to be separated from the game logic state.
If your game can run without any display (headless), it's a good sign that these two parts have been separated.

Finally, it's important to make sure that your game logic (not graphics) can run faster than realtime. This is needed for when a
networking method needs to replay game state. If the game struggles to run at the target framerate then it will have a hard time
with multiplayer. Make sure there is still a good chunk of compute still available for use.

Sending Inputs

One option is to only send player inputs across the network. This can either take the form of a "dumb terminal" or a
*deterministic lockstep* game. In the "dumb terminal" setup, each player sends their input to a server that is running the actual
game, and the servers sends back render information telling the clients how to display its game state. The clients themselves are
not actually running the game itself, they simply act as frontends rendering the game state to the user. In deterministic lockstep,
each peer sends their player inputs to each other, and use that to advance the game state. Each runs the game locally, see the
deterministic lockstep section for more. The main advantage to sending only player input is that it greatly reduces network usage,
and does not depend on the complexity or size of the game simulation, allowing the game simulation to be as big as is possible for
each client to run. It's CPU/GPU bound, rather than network bound.

Sending Game State

Another option is to send game state across the network. In this setup one peer is the server that has authority over the game
state. The server sends game state every time an action is taken for non-realtime games or at a fixed rate for realtime games.
The game state data sent over the network usually consists of an array of entity data and a unique ID number for each.

This ID number is the same on both the server and the client, and the client uses it to map the entity data it receives to
the associated entities. The client updates their local entity data with this new information. This approach is network bound,
the more entities that need to be send across the network, the more bandwidth is required. A game with too many entities will not
be able to use this approach. However, this approach is standard and will work well given that the amount of data being sent does
not become too large. If you are unsure whether to send just inputs or game state, sending game state is recommended as sending
just inputs places extra constraints on the game's code, and bandwidth has been increasing over time and continues to increase.

Client Authoritative

In client authoritative games the clients can determine their own player's state. They calculate their player state locally and
send it to the other peers/server.  This approach can simplify the networking code a lot for a game, but opens the game up to easy
cheating since each player is in full control of their own state. However, many games manage to get away with this approach and if
your game is not a highly competitive game, or you know that each player you are playing with is trusted, then it can be an
optimal choice in terms of complexity. Games that will use this method include party games, and self host / private server games.
This method is not well suited for a game that wants to have match making between strangers.

Server Authoritative

Server authoritative games have the server by the final authority over what the current game state is. Players may send their
inputs and/or state, but it's up to the server to choose what to do with that. Each client receives updates from the server and
use that to update their local state. If their local state does not match that which was received from the server, they use the
server's given state. This method does not allow for easy cheating via manipulation of player state or network packets and is well
suited for most games, but comes with a major downside of increased complexity. However, it's the ideal solution and should be
preferred given enough development time and budget. It requires having either dedicated servers hosting the game or allowing
players to host the game themselves by providing the server executable in addition to the client to users.
If you want your game to be competitive, or allow for match making between strangers, then server-authoritative dedicated servers
is the best choice.

Deterministic Lockstep

Deterministic lockstep is one of the main networking methods used in video games. It involves sending inputs between peers and
when they are ready, stepping, meaning running a single frame of the simulation with the given inputs. If each peer involved
has a simulation that gives the *exact same result* for a given starting state and inputs, then each peer will have the *exact
same simulation* running on their local machine and all peers will be in sync with each other. If there is even a slight
difference in how the state is calculated on each peer, their states will desync over time. This desync can happen much faster
than expected from only slight deviations in the calculations.This puts a great burden on the developers of the game to ensure
that their simulation is deterministic *across different devices*. This can require some drastic changes in how a game
is programmed.

For example, floating point operations do not always produce the same results on different devices and therefore floating point
operations can't be used. Instead games will use just integer types, and either use software fixed point or floating point
arithmetic,similar to how games used to before floating point hardware existed. In Python, there are some options to help with
this such as the decimal module. Lesser drastic changes are also required, such as making sure that all peers have the same seed
set for pseudo random number generation. Given that the developer is willing to put in the effort to make the simulation
deterministic, there is one other downside to consider. Since game state is not being sent across the network it implies that a
new peer can't join mid-game, unless game state is sent and then they catch up to the current state with the rest of the peers.
This may seems like some big downsides, and they are, but the reward is something that can easily run peer to peer, requires
almost no bandwidth that is constant in relation to the number of entities, and having a deterministic simulation allows for
easier debugging/replay/saving systems. This method is commonly used by realtime strategy games where the game state is too big to
send over the network, and fighting games due to them historically being deterministic because they used to be arcade games
without floating point hardware and they want to allow for easy peer-to-peer (no server) networking.

Snapshot Interpolation

Snapshot interpolation is likely the most commonly used method today. It's a method in which after receiving the game state the
peers also interpolate between states. The interpolation is used to *visually* smooth out state between updates. If a peer is
receiving game state updates at a fixed rate of 20 times per second, then if the peer simply updates their local state with that
new state and displays that state, the entities will by teleporting rather than moving smoothly between points.
Instead the peer keeps a circular buffer of updates received and interpolates between two of them smoothly.
This gives the player the illusion of a smooth experience.

It also implies that the interpolated objects are not the current state of the game, but rather a past version of it, and so
the user is seeing an old, and interpolated, version of the game state. However, if the time between updates is not too large
such that the interpolation time is low, this will be only slightly behind and usually not become a game breaking issue.
But in a fast paced game in which the players need to be precise about how they interact with such interpolated objects,
additional work may be required in the form of *server side lag compensation* to make up for this gap in time, in addition to the
already existing gap of network latency.

Server Side Lag Compensation

To make up for network latency, and added latency of interpolation methods. The server/peers may decide to give some slack to
a player's actions. To explain this, consider a first person shooter game with snapshot interpolation. When a player aims at
another player they are aiming at a past version of that player, the actual player state on the server is ahead in time due to
network latency of sending the player state to the client, and additional latency of interpolation.

Then when the player decides to shoot, there is even more latency from the player's input packet taking time to reach the server.
When the server receives the player's input to shoot, it can take into account this latency and decide to rewind the players by
an estimated amount of latency and then check to see if the player hit the other player, apply the effect of that, and then
play the game forward again (at faster than realtime speed) until it's caught back up to the current time.

This requires the server to keep a circular buffer of past states. And forthe game code to have some convenient way to making such
state backups. It also helps for the server to be *mostly* deterministic such that the replay gives a correct result.
Server side lag compensation is not applied to all game mechanics, typically only things that are instantaneous, such as ray casts.
Something like a rocket launcher that fires a slow moving projectile would not have server side lag compensation applied.

In that case, players with lower ping may have a significant advantage. One of the downsides of server side lag compensation is
that it may punish low latency players as they will not benefit nearly as much from the rewind process as high latency players,
and it can result in common issues such as being shot around corners.

A solution to this problem is to require all players in a match to have similar latencies within some range and to limit how far
back in time a rewind is allowed to go. The concept of rewinding and replaying applies not only to servers, but clients as well,
as they too need to handle latency and responsiveness.

Client Side Prediction

When a player takes an action and sends that input to the server, there is some latency from the network travel time, the server
process time, and return network travel time for the state update. If the client wait for that state update the player will have
a very unpleasant experience in which all of their inputs have latency. Even a small amount of latency is noticeable for this if
the game requires fast actions from the player. To make this experience better clients will apply the input locally immediately
as in a single player game while they wait for future state updates.

This works well until the server and client disagree on the player's state. When the predicted player state and the state received
from the server does not match, the client must use the server's state if it's a server authoritative state setup. However, it's
not as simple as just setting the current state to what was received by the client because that state is in the past.
The round trip time (RTT) latency means that the state is behind the server's current state, and even more behind
the client's predicted state.

To solve this, the client keeps a circular buffer of player inputs (or entire game state). Each input is assigned an integer
*sequence number*, which is just an increasing integer for each frame. When the client sends the player input to the server, it
also sends the sequence number associated with that input. When the server processes client input, it keeps track of which
sequence number it last processed for each client. Then when it sends a game state update to a client, it also sends the last
processed sequence number with it. When the client receives this state update it uses the sequence number to tell how far ahead of
that state update the current predicted state is; the delta between the sequence number and the one received from the server.

The client now sets its state to the one received from the server and replays player inputs in the circular buffer from current
time minus the sequence number delta, to the current time. If the server state update plus replay matches the client's current
prediction then there will be no visible change, which is often the case, but when it does not match, the player may experience
"rubber banding," where their state snaps to the correct one from the server. This can be further improved with interpolation
on misprediction.

This may seem rather complicated, but in practice it turns out to be a small amount of code with multiplayer preparations.
Note that client side prediction only works well for predictable objects. Since the client does not have the other player's
immediate inputs, it can't be applied to other players well. For other players and other unpredictable objects interpolation
is used.

References

Gaffer on Games, highly recommended.

+ https://www.gafferongames.com/post/deterministic_lockstep/
+ https://www.gafferongames.com/post/snapshot_interpolation/
+ https://www.gafferongames.com/post/snapshot_compression/
+ https://www.gafferongames.com/post/state_synchronization/

Valve's networking model.

+ https://developer.valvesoftware.com/wiki/Source_Multiplayer_Networking
+ https://developer.valvesoftware.com/wiki/Prediction
+ https://developer.valvesoftware.com/wiki/Interpolation
+ https://developer.valvesoftware.com/wiki/Lag_Compensation

A nice article on deterministic lockstep.

+ https://quickgameworld.com/blog/deterministic-lockstep

A highly recommended article on prediction, and interpolation.
Includes a demo that runs in the browser.

+ https://www.gabrielgambetta.com/client-server-game-architecture.html

A talk on Overwatch's networking. This is more advanced.
The first part is on its entity component system, which can be skipped.

+ https://www.youtube.com/watch?v=zrIY0eIyqmI

With time skip to netcode:
+ https://youtu.be/zrIY0eIyqmI?t=1342

A video on "rollback" networking, a form of deterministic lockstep with prediction
used by modern fighting games.

+ https://www.youtube.com/watch?v=0NLe4IpdS1w

~~ Introduction to Ursina Networking ~~

Limitations

Ursina's networking currently uses TCP. Partially because it's much easier to implement, and partially because it makes things
more simple for the user. The general thing to keep in mind is that TCP works well for video games when there is little to no
packet loss, resulting in few or no packet resends. Meaning that the network connection by the users must be stable and reliable.

Network connections around the world have been improving over time making TCP more acceptable as an option. But if you need your
game to work everywhere, for as many users as possible, then you may want to use some other solution that uses UDP.
This does not apply to non-realtime networked games though, as any latency spikes causes by resends doesn't really matter.

Basics

The recommended way to do networking in Ursina is by using *remote procedure calls* (RPCs). This is an abstraction that lets
the user call functions on the server/client/peer. Effectively allowing the user to run functions (aka procedures) that exist on
another machine via a network connection. This hides all the details of packing up data and sending it over TCP to the other
machine, where it is unpacked and then used to call some function. Usage of remote procedure calls can be found in the networking
samples that come with Ursina.

RPC code will look something like this in typical use:

Then the say function can be called by another peer via their own RPCPeer:

Note that type hints are **required** for user arguments such as the message argument in the example.
The RPC code needs the type information to serialize and deserialize the data. Custom user types can be added.

Samples

It's recommended to read the networking samples included with Ursina. They build on each other and club_bear.py
is a functional realtime multiplayer game tested on a real server. Their order is:

1. hello_world.py which explains how to use the more low level Peer class.
2. hello_world_rpc.py gives an introduction to RPCs.
3. shared_object.py shows how to synchronize two player controlled objects.
4. host_authoritative.py is the same as shared_object.py but the host is in charge of object state.
5. club_bear.py is similar to host_authoritative.py but more fleshed out with multiple players, chat, and more.