Online multiplayer turn-based game sử dụng UDP

Giới thiệu

Online multiplayer turn-based game là thể loại game online chơi theo lượt ví dụ như cờ tướng online (2 người), cờ tỉ phú online (4 người)

Trong thiết kế phương thức truyền UDP cho Online multiplayer turn-based (OMT) game bao gồm 2 công đoạn chính:

Làm sao để 2 người chơi nhận ra nhau [1]
Làm sao để 2 người chơi chơi theo lượt [2]

Để trả lời câu hỏi [1], ta cần một server và quan tâm đến kỹ thuật UDP punch hole sẽ được trình bày ở phần sau.

Để trả lời câu hỏi [2], ta phải thiết kế 1 mô hình hợp lý đảm bảo chơi theo lượt

IP, Port, Socket, NAT

Khi một máy tính gia nhập vào mạng, nó sẽ có một địa chỉ để cho biết nó là ai. Từ đó, người khác mới đế thể gửi gói tin đến. Cũng giống như nhà có số, hay số phone của bạn vậy. Gọi là địa chỉ IP. Địa chỉ IP xét cho cùng là một con số rất lớn, và được cấp phát theo những nguyên tắc riêng cũng như luật đánh số nhà. Phiên bản được sử dụng phổ biến ngày nay là IPv4 (IPv6 ít được sử dụng)

Trên mỗi máy cho nhiều chương trình cần được kết nối mạng cùng một lúc, ví dụ như bạn cần duyệt cùng lúc 2 trang web là google.com và yahoo.com. Làm sao máy tính của bạn biết đâu là thông tin gửi về từ google, hay yahoo. Để phân biệt các ứng dụng chạy trên cùng máy (ip), một khái niệm khác được định nghĩa là port. Port là một con số 16 bit, đồng nghĩa theo lý thuyết có tối đa 2¹⁶ chương trình có thể chia sẽ cùng ip trên máy bạn.

Kết hợp hai khái niệm ip và port, được gọi chung là socket. Hay nói cách khác, socket là sự kết hợp của 2 thông tin ip address và port. Nó đại diện cho 1 "chương trình" truy cập mạng trên máy của bạn.

Lại nói về địa chỉ IP, một con số rất lớn nhưng là không đủ để dánh dấu tất cả các máy tính trên thế giới. Hãy làm nhẩm một phép tính đơn giản. IPv4 dùng 32 bit để đánh dấu, tức có thể đánh dấu tối đa được 2^32 máy (khoảng 4 tỉ máy). Dân số thể giới là 7 tỉ, trung bình mỗi người dùng 1 smart phone và 1 PC thì cũng cần đế 14 tỉ địa chỉ. IPv4 không có khả năng đó (IPv6 dùng đến 128 bit)

Để giải quyết bài toán nan giải này, một phương pháp được ra đời có tên gọi là NAT (Network Address Translation), làm nhiệm vụ chuyển đổi địa chỉ, cho phép nhiều máy cùng hoạt động trên một địa chỉ IP. Ví dụ, bạn được cấp một địa chỉ ip là 192.168.1.32, nhưng cần xài chung cho 4 máy. Lúc này, các máy con của bạn cũng sẽ được đánh địa chỉ được là intranet/local ip address. Các ip này bạn có thể đặt tùy ý theo luật đặt ip (xem thêm DHCP). Giả sử các máy của bạn sẽ có IP là 10.0.0.1 đến 10.0.0.4

Thông thường, NAT được cài đặt sẵn trong các thiết bị như hub, switch, router ...

Khi dữ liệu được chuyển đi từ 1 máy của bạn "đi ngang qua" router, nó sẽ được đổi địa chỉ thành 192.168.1.32. Như vậy, chiều đi đã ổn, nhưng theo chiều ngược lại, một thông tin được gửi đến 192.168.1.32 từ internet sẽ được đến máy nào?

Đến đây, ta xem lại khái niệm về socket, một chương trình khi gửi dữ liệu đi, hoặc nhận dữ liệu đến thì đều thông qua socket, hay nói cách khác mỗi chương trình được định danh bởi 1 socket gồm 2 thông tin ip và port. Như vậy, khi dữ liệu từ internet đến router, ngoài thông in ip, nó còn chứa thông tin về port. Lúc này, NAT không đơn thuần đổi địa chỉ, mà còn đó nhiệm vụ đổi cả port đồng thời xác định được máy cần gửi thông tin đến

Thời gian tồn tại các record trong bảng tra, cũng như qui tắt mapping, đổi port ... là không có qui chuẩn nhất định. Thông thường sau một khoảng thời gian không được "sử dụng", record trong bảng sẽ bị xóa đi (nguyên tắc Time to leave - TTL)

(Lưu ý: qua trình tìm máy đến khá phức tạp, thông tin trên chỉ mang tính chất đơn giản hóa, xem thêm rooting)

Mạng máy tính là một hệ thống phức tạp bao gồm nhiều tầng, nhiều phân cấp, và hiển nhiên đi qua nhiều NAT, do đó việc một máy tính có thể nhận biết 1 máy tính khác trên mạng là rất khó khăn.

Mở rộng thêm về socket. Một chương trình không chỉ đại diện bởi một socket, một chương trình có thể quản lý nhiều socket khác nhau. Các socket này (thường) có chung ip và có port khác nhau.

UDP

UDP là phương thức truyền dữ liệu qua mạng (user datagram protocol). UDP có thể hiểu nôm na là một gói dữ liệu, ví dụ như gói bưu kiện mà bạn gửi đi theo diện không đảm bảo. Bạn đính kèm địa chỉ nơi gửi, nơi đến và phó mặt cho nhà vận chuyển. Gói đó có thể mất, đến muộn mà bạn không cần quan tâm. Khi nhắc đến UDP, ta thường nhắc đến 1 đối trọng của nó là TCP. UDP có các đặc điểm:

Không kết nối (không biết đích đến còn sống hay không)
Không đảm bảo đến được đích
Không đảm bảo thứ tự
Nhanh, đơn giản, hiệu quả cho các gói tin nhỏ với số lượt yêu cầu nhiều

Vì sao chọn UDP? Vì với game online multiplayer turnbase:

Không đòi hỏi duy trì kết nối thường xuyên
Không cần phương thức "gửi đảm bảo" và đúng thứ tự

Server

Đây là khái niệm tương đối rộng. Trong pham vị bài biết, server là một máy tính có địa chỉ internet thật. Tức khi nói đến ip của nó, thì đó là ip của chính nó, không phải ip của một thiết bị truyền dữ liệu trung gian nào đó (hub, switch, router...)

Vì sao cần sự hiện diện của server? Vì nó có ip thật, nó hiện hữu là chính nó, mọi người đều biết về nó, và có thể liên lạc trực tiếp với nó.

Một chương trình chạy trên server sẽ có một hoặc nhiều socket thật, tức ip thật và nhiều port thật. Mọi người có thể kết nối vào chương trình đó từ ip và port được cung cấp.

Ở đây cần tránh sự nhầm lẫn. Thứ nhất, ví dụ khi có người nói, có nhiều hơn một trang web có cùng ip và port. Vậy sao nói socket là duy nhất cho một chương trình. Ở đây, một trang web không phải là một chương trình thực thụ, chương trình thật sự bạn đang nói đến khi web server (apache, ngix ...). Nó cho phép và quản lý nhiều hơn một website. Khi bạn gõ http://www.google.com tức bạn đang liên lạc với một chương trình web server có ip 74.125.128.99 và port 80 (port web) và yêu cầu nội dung trang web www.google.com (xem thêm dns)

Thứ hai, ví dụ khi có người nói, tôi dùng 1 chương trình duy nhất là chrome để duyệt nhiều trang web cùng lúc (có ip khác nhau). Vậy với một chương trình là chrome, làm sao có thể kết nối đến nhiều web server. Có 2 điều cần lưu ý trong trường hợp này (hoặc tương tự)

Bạn hoàn toàn có thể làm được nếu dùng UDP (dựa vào thông tin gói đến để biết đến từ đâu)
Bạn có thể chạy nhiều process chrome, mỗi process mở một port TCP khác nhau kết nối với web server.

UDP Punch Hole

NAT giúp nhiều máy có thể vào mạng, nhưng lại đặt ra một vấn đề là ngoại trừ những máy có ip thật (gọi là server), thì những máy khác "không biết mình là ai" và cũng chẵng thể biết đến ai ngoài "server". Vậy làm sao 2 người chơi "nói chuyện" với nhau ?

Cách giải quyết dễ thấy nhất là sẽ có 1 server trung gian chuyển tiếp thông điệp, đại loại như bạn với cô ấy cần tỏ tình với nhau nhưng e ngại, bèn nói với một người bạn mà hai người đều quen, nhờ nói qua nói lại vậy.

Một "chương trình" được chạy ở server làm nhiệm vụ này:

(Click vào hình trên để xem ảnh động, nếu bạn ko thấy có chuyển động)

Trong quá trình trên, bước "any message?" dùng để tạo ra một đường kết nối tạm thời từ server đế pc. Đường kết nối này được tạo lập bởi các bảng NAT ở các thiết bị trung gian. Đường kết nối này là tạm thời do các record NAT có thể thay đổi.

Để tăng tính "tức thời" trong chuyển tiếp thông tin, các gọi "any message" được thay bằng cơ chế ping, tức client sẽ gửi định kỳ các gói nhỏ chứa thông tin gọi là ping đến server. Server nhận được reply lại để duy trì kết nối ảo giữa client và server. Khi nhận được message thật, message này sẽ được chuyển tiếp đi ngay. Khi nhận được gói ping, socket tương ứng của client sẽ được lưu lại để tra cứu

Nhược điểm lớn nhất của quá trình này là:

Thông tin đi qua server làm tăng chi phí (bên dưới sẽ trình bày cách giảm bớt lưu lượng chuyển tiếp qua server).
Phụ thuộc vào hoạt động của NAT.

Nhìn chung, có mối quan hệ của 2 client sẽ rơi vào 1 trong 3 trường hợp

1. Hai client cùng ở chung một mạng riêng

Trong trường hợp này, hai máy A & B có thể truyền dữ liệu trực tiếp cho nhau mà không cần đến server

2. Hai client kết nối vào 2 NAT khác nhau, mà hai NAT này cùng kết nối vào internet với ip thật (static ip)

Lúc này, hai Client A & B giao tiếp thông qua 2 NAT trung gian.

3. Hai client có kết nối phức tạp nhiều tầng NAT, hoặc không thể thành công khi kết nối bằng trường hợp 1 & 2

Đa phần trường hợp 3 chiếm số lượng lớn, song trường hợp 1& 2 vẫn có thể tính đến để tiết kiệm chi phí cho server.

Để phân loại, ta thực hiện:

Khi ping, user gửi thông tin ip local cho host, host lưu lại 2 thông tin
- local socket của client. Client phải chủ động gửi cho server thông tin này
- socket của thiết bị NAT "cuối cùng". Giá trị này có được dễ dàng bằng việc lấy thông tin socket của gói đến server
Client A trước khi "kết nối" một client B, yêu cầu server cho biết thông tin client B
Từ thông tin có được, tiến hành gửi 3 gói thăm dò đến 3 địa chỉ khác nhau: server ip, local ip, và nat-ip
Client B khi nhận được gói thăm dò, dựa vào kênh được chuyển tới sớm nhất, đồng thời phân loại kết nối, gửi trả lời. Không nhất thiết cả 3 gói ping đều đến được server mà tùy vào từng trường hợp (như đã nói ở trên)
- case 1: cả 3 gói sẽ tới, ưu tiên chọn gói tới nhanh nhất -> low latency
- case 2: chỉ gói từ nat-ip và server tới. Chọn cái tới sớm nhất -> low latency
- case 3: chỉ có gói ping chuyển tiếp tới từ server. Hiễn nhiên chọn giải pháp chuyển tiếp qua server
- Trong trường hợp không có gói nào tới, cố gắng thử gửi 1 vài lần, không được thì fail
Client A nhận được trả lời, từ đó phân loại kết nối

Xem chi tiết quá trình kết nối tại http://www.brynosaurus.com/pub/net/p2pnat/

Case 1:

Case 2:

Case 3:

Sau khi đã có được kết nối, việc cần làm là duy trì kết nối bằng cách gửi thông tin "ping" qua lại giữa máy A và B

Cơ chế turn-based

Sau khi kết nối thành công, phần việc tiếp theo là thực hiện logic của một game kết nối theo kiểu turn-based

Trong các client, sẽ có 1 client đóng vai trò làm "host". Host quản lý thông tin game và logic game, các client chỉ có vai trò nhận tương tác và render. (Nói cách khác, một máy là host thì nó sẽ vừa làm client, vừa làm host)

Hoạt động của client dựa trên 3 trạng thái: LOCK, INPUT và SYNC

LOCK: client không có lượt đi, chỉ tiến hành nhận thông tin cập nhật từ server
INPUT: server đang trong lượt đi của mình, cho phép nhận điều khiển từ user
SYNC: kết thúc di chuyển, đồng bộ thông tin với server

Hoạt động của host gồm 2 phần: logic game và gửi thông tin cập nhật

seqNo = 0

userInTurn = 0

while (true)

    if receive_submit() then

        seqNo = seqNo  + 1

        userInTurn = get_next_turn()

end

    update_game_logic()

    deliver_to_all_clients(seqNo, userInTurn, gamedata)

end

Thông tin điều khiển quan trọng nhất cần lưu ý là seqNo và userInTurn:

seqNo: lượt chơi của game, dùng để đồng bộ với các client
userInTurn: đến lượt user nào chơi

Mỗi client sẽ có cặp thông tin tương ứng là <seqNo, turnIndex>:

seqNo: lượt chơi của game, dùng để đồng bộ với host
turnIndex: thứ tự chơi của user

Client khi nhận được thông tin từ server:

seqNo = -1

function On_Receive_Data_Update(ServerSeqNo, currentTurnIndex, gamedata)

    if ServerSeqNo >= seqNo then -- valid seq

        if ServerSeqNo > seqNo -- change state

            if state is LOCK then

                if currentTurnIndex == turnIndex then

                    switch_to_state(INPUT)

end

            elseif state is INPUT then

                if currentTurnIndex != turnIndex then

                    switch_to_state(LOCK)

end

           else

                if currentTurnIndex == turnIndex then

                    switch_to_state(INPUT)

                else

                    switch_to_state(LOCK)

end

end

end

        update_game_with_data(gamedata)

end

end

function update_client_control()

    if state is INPUT then

       update_game_input()

       if hasEndTurn() then submit() end

end

end

Tùy vào theo game để có thể lựa chọn thông tin update cho client

Thông tin update là một bản snap-shoot dữ liệu từ server
Thông tin update là một list các transaction

Page updated

Google Sites

Report abuse