Transcript Adversarial Search

Network in game (I)
Oct. 16, 2006
Courtesy of Sugih Jamin at Univ. of Michigan
outline
•
•
•
•
•
•
Multiplayer game
Network topology
Client-server
TCP/UDP
Synchronization
Consistency
Why multi-player game?
• Humans are better at most strategy than current
AIs
• Humans are less predictable
• Can play with people, communicate in natural
language
• Add social aspect to computer game
• Provides larger environments to play in with
more characters
• Make money as a professional game player
Two types of online experience
• Head-to-head death-match
–
–
–
–
–
Fast-pace, intense interaction/combat
No persistent state
Players from ad-hoc, short-lived sessions
Any client can be a server
Requires matchmaking service
• E.g. built-in lobby
– Doom, Counter-strike, StarCraft, AoE,…
• Persistent world, massively multiplayer onine
game (MMOG)
MMOG
• Most MMOGs are MMORPGs
– Servers keep persistent states, players can
drop in anytime
– Traditionally emphasized social interaction
(less combat than the 1st type)
– In the beginning: MUD in 1978
• Ultima Online
• Everquest
• Lineage and Lineage II
Networking in Games
• Differentiate between in-game networking and backend
infrastructure
• Backend infrastructure
–
–
–
–
–
–
–
–
–
Lobby where gamers meet
Authentication and CD key checking
Accounting and billing
Ranking and ladder
Reputation and black list
Buddy lists, clans, and tournaments
Mods and patches management
Virtual economy
Beware of DDoS
• Issues: scalability, adapting to failure, security
Networking in games
• In-game networking
–
–
–
–
–
–
–
Client-server vs. peer-to-peer
Socket programming
Which protocol to use?
Bandwidth limitation
Latency limitation
Consistency
Cheat proofing
application
Library/kernel
Network libraries
• Winsock
• Directplay
– A component of DirectX
– Simple, small scale
• Adaptive communication environment (ACE)
– C++
– a freely available, open-source object-oriented framework that
implements many core patterns for concurrent communication
software
Peer-to-peer
• O(N2) unicast connections
• Each player is connected to
directly to all other players
• Each player simulates the
whole world
• Advantages: reduced
latency, no single point of
failure
• Disadvantages: easier to
cheat, not scalable, each
client must send and
receive N-1 messages
• Used in Age of Empire
Client-server
• Two favors
– Ad hoc servers: death match
– Dedicated servers: MMORPG
• Two types of clients
– Clients simulate world; server has authoritative state
• Allows for client-side dead reckoning
– Clients for I/O; all simulations at server
• Useful for thin clients, e,g, cell phones and persistent world MMOG
* Dead reckoning: the program only sends updated information about the
entity's current state if it is not close enough to the predicted state.
Client-server
• Advantages: each client
sends only to server; server
can aggregate and order
moves
• Advantages( dedicated
servers): cheat proofing,
server can be better
provisioned, persistent
states (for MMOG)
• Disadvantages: longer
delay, server bottleneck,
single point of failure, need
management
MMOG server architecture
•
•
The world replicated at each server (shard); each shard contains an
independent world; players go to a specific shard.
Most MMORPG
Shard: a term for broken pieces of pottery or glass
MMOG server architecture 2
• The world replicated at each server (mirror); all the
worlds are synchronized; players see everyone
across all mirrors
Mirrors must be kept consistent
MMOG server architecture 3
• The world is split up into regions; each region is
hosted by a different server; servers must be kept
consistent
*example: secondlife
Client-server socket programming
• What is a socket?
– A data structure containing connection
information
• Connection identifying info
– Client IP address (building number)
– Client port number (room number)
– Source IP address
– Source port number
Client-server socket programming
• Client-server connection
– Server creates a socket and listens for
connection on a well-known port number
– Client creates a socket and connects to the
server address at the well-known port number
TCP vs. UDP
• What TCP gives you
– Reliable delivery
– Retransmission and reordering
– Congestion control
• What UDP gives you
– Unreliable delivery
– No retransmission, packets not ACKnowledged, no reordering
– No congestion control
What protocol to use?
• Game requirements
– Late packets may not be useful anymore
– Lost info can sometimes be interpolated
– But loss statistics may be useful
• Use UDP in game
–
–
–
–
–
Can prioritize data
Can perform reliability if needed
Can filter out redundant data
Use soft-state
Send absolute values, not differences
• If differences are used, send baseline data periodically
– Must do congestion control if large data
BW limitation
• What is Bandwidth?
• What information is sent?
– Game state: coordinates, status, action, damage
– User strokes
– Commands/moves
• Currently lower limit assumes 56Kbps
BW limitation
• BW requirement has been highly optimized
• Even with audio chat, at most 8Kbps
• So, BS is not a big issue
– Be careful about asymmetric topology
• Must be continually vigilant against bloat
• However, player-created objects and worlds
make BW an issue again.
– E.g. streaming, level of details, 3D
• RTS
Latency limitation
– < 250ms not noticeable
– Btw. 250 and 500 ms playable
– > 500ms noticeable
• FPS: < 150ms preferred
• Car racing
– < 100ms preferred
– Btw. 100 and 200 ms sluggish
– > 200 ms car out of control
• Player’s expectation can adapt to latency
• Slow but smooth is better than jittery
• DirectPlay not good
synchronization
• Ordering moves by their times of
occurrence
• Assume globally synchronized clocks
• Out-of-synch worlds are inconsistent
• Small inconsistencies not corrected can
lead to large compounded errors later on
(e.g. missing a hit)
Lock-step protocol
• Each player receives all
other players moves before
rendering next frame
• Problems
– Long internet delay
– Variable latencies
– Speed determined by the
slowest player
– Missing packet?
Bucket synchronization
• Buffer both local and remote
moves
• Play them sometime later
• Each bucket is a turn, say for
about 200ms
• Bucket size can be adapted to RTT
• Problems
– A move is lost or late?
– Game speed determined by
slowest player
consistency
• For consistency, all user input must pass through the
synchronization module
• Be careful with random number generators. Isolate the
one used for game state updating from other uses
• Design for multiplayer from the start.
consistency
Pessimistic consistency
• Every player must see the exact same world
• AoE:
–
–
–
–
–
Uses bucket synch.
Each player sends moves to all other players
Each player simulates its own copy of the world
All the worlds must be in synch.
A designated host collect measured RR from all players and set
future bucket size
• Problems
– Variable latencies
– Speed determined by the slowest player
Dead reckoning
• A.k.a. client-side prediction
• Extrapolate next move based on prior moves
• Compute the velocity and the acceleration of objects to
dead reckon
• Players can help by sending this info along
• Obviously, only works if velocity and acceleration and
direction haven’t changed