ĐẠI HỌC ĐÀ NẴNG

TRƯỜNG ĐẠI HỌC BÁCH KHOA

KHOA CÔNG NGHỆ THƠNG TIN
Bộ mơn Mạng & Truyền Thơng

ĐỒ ÁN 3
ĐỀ TÀI :

XÂY DỰNG TRÒ CHƠI BOMBERMAN NHIỀU
NGƯỜI CHƠI KẾT HỢP AI


MỤC LỤC
CHƯƠNG 1: TỔNG QUAN VỀ ĐỀ TÀI..................................................................4
I.
II.

Tên đề tài và giới thiệu về đề tài:...............................................................4
Giới thiệu về vấn đề và cách giải quyết :...................................................5
1.
Giao thức TCP/IP.................................................................................5
2.
Lập trình socket....................................................................................8
3.
Mơ hình Client.....................................................................................9
4.
Thuật tốn:.........................................................................................10
III. Cơng cụ được áp dụng :............................................................................12
CHƯƠNG 2: PHÂN TÍCH VÀ THIẾT KẾ HỆ THỐNG....................................12

I.
II.
III.

Các chức năng chính của người dùng:....................................................12
Mô tả các chức năng:................................................................................12
Thiết kế cơ sở dữ liệu:...............................................................................13

CHƯƠNG 3: ÁP DỤNG LÝ THUYẾT VÀ CHẠY THỬ SẢN PHẨM..............14
-

Vào GAME:...............................................................................................15
Màn hình chơi game:................................................................................15

TÀI LIỆU THAM KHẢO.......................................................................................17
PHỤ LỤC 18

2


CHƯƠNG 1: TỔNG QUAN VỀ ĐỀ TÀI
I.

Tên đề tài và giới thiệu về đề tài:
Bomberman (ボンバーマン) là một trò chơi video dạng mê cung theo phong

cách game thùng được phát triển bởi Hudson Soft. Phiên bản trò chơi trên máy tính
tại nhà đầu tiên là Bomber Man ( 爆 弾 男 Bakudan Otoko?) được phát hành vào
tháng 7 năm 1983 cho NEC PC-8801, NEC PC-6001 mkII, Fujitsu FM-7, Sharp
MZ-700, Sharp MZ-2000, Sharp X1 và MSX ở Nhật Bản, và một phiên bản được

kiểm duyệt cho MSX và ZX Spectrum ở Châu Âu như Eric và Floaters.Nó có một
phần tiếp theo tại Nhật Bản được gọi là Bomberman 3-D, trong đó Bomberman
điều khiển mê cung theo góc nhìn thứ nhất. Năm 1985, Bomberman được phát hành
cho hệ máy Nintendo. Nảy sinh ra loạt Bomberman với nhiều phần dựa trên lối chơi
cơ bản của nó.
Trong bản phát hành trên hệ NES / Famicom, nhân vật cùng tên, Bomberman, là
một robot phải tìm đường xuyên qua mê cung và lẩn tránh kẻ thù. Cửa ra vào dẫn
đến các mê cung lớn hơn được tìm thấy dưới những tảng đá, mà Bomberman phải
phá bằng cách đặt các quả bom. Có những vật phẩm có thể giúp cải thiện bom của
Bomberman, chẳng hạn như khả năng Fire, giúp tăng phạm vi nổ bom. Bomberman
sẽ biến thành con người khi anh ta trốn thốt thành cơng. Mỗi trị chơi có tổng cộng
50 cấp độ. Các trị chơi máy tính tại gia ban đầu khá là cơ bản và có một số quy tắc
khác nhau.
(Trong đồ án 3 này, em muốn cải tiến từ trò Bomberman cổ điển thành trị chơi có
thể kết nối cơ sở dữ liệu qua giao thức TCP, bên cạnh đó cịn cố gắng xây dựng và
phát triển Enemy AI)

3


Hình ảnh minh họa
II.

Giới thiệu về vấn đề và cách giải quyết :
Vấn đề ở đồ án này là việc làm sao để xây dựng 1 chương trình game giống như

game Bomberman truyền thống, bên cạnh đó cịn phải thêm chức năng nhiều người
chơi kết nối mạng giữa các máy tính, chức năng chơi với Bomberman trí tuệ nhân
tạo.
Cụ thể cần áp dụng kiến thức lập trình hướng đối tượng kết hợp với các mẫu

thiết kế, kiến thức về lập trình mạng (giao thức TCP/IP) và các giải thuật tốn học
áp dụng cho các xử lý cơ bản, xây dựng Enemy (thuật toán BFS, A*,Neural
Network).
1. Giao thức TCP/IP
1.1 Tổng quan
TCP/IP là bộ giao thức cho phép kết nối các hệ thống mạng không đồng nhất
với nhau. TCP/IP được xem như giản lược của mơ hình tham chiếu OSI với 4 tầng
như sau:
- Tầng liên kết (Datalink Layer)
- Tầng mạng (Internet layer)
- Tầng giao vận (Transport Layer)
- Tầng Ứng Dụng (Application Layer)
a. Tầng liên kết
4


Tầng liên kết (còn được gọi là tầng liên kết dữ liệu hay tầng giao tiếp mạng) là
tầng thấp nhất trong mơ hình TCP/IP, bao gồm các thiết bị giao tiếp mạng và các
chương trình cung cấp các thơng tin cần thiết để có thể hoạt động, truy nhập đường
truyền vật lý qua các thiết bị giao tiếp mạng đó.
b. Tầng mạng
Tầng Internet ( hay còn gọi là tầng Mạng) xử lý q trình truyền gói tin trên
mạng, các giao thức của tầng này bao gồm : IP ( Internet Protocol) , ICMP
( Internet Control Message Protocol) , IGMP ( Internet Group Message Protocol )
c. Tầng giao vận
Tầng giao vận phụ trách luồng dữ liệu giữa 2 trạm thực hiện các ứng dụng của
tầng trên, tầng này có 2 giao thức chính là TCP ( Transmisson Control Protocol) và
UDP (User Datagram Protocol).
- TCP cung cấp luồng dữ liệu tin cậy giữa 2 trạm, nó sử dụng các cơ chế như
chia nhỏ các gói tin ở tầng trên thành các gói tin có kích thước thích hợp cho tầng

mạng bên dưới, báo nhận gói tin, đặt hạn chế thời gian timeout để đảm bảo bên
nhân biết được các gói tin đã gửi đi. Do tầng này đảm bảo tính tin cậy nên tầng trên
sẽ không cần quan tâm đến nữa.
- UDP cung cấp một dịch vụ rất đơn giản hơn cho tầng ứng dụng . Nó chỉ gửi dữ
liệu từ trạm này tới trạm kia mà khơng đảm bảo các gói tin đến được tới đích. Các
cơ chế đảm bảo độ tin cậy được thực hiện bởi tầng trên tầng ứng dụng.
1.2 Phương thức hoạt động của bộ giao thức TCP/IP.

5


Q trình đóng mở gói dữ liệu trong TCP/IP
Cũng tương tự như trong mơ hình OSI, khi truyền dữ liệu , quá trình tiến
hành từ tầng trên xuống tầng dưới, qua mỗi tầng dữ liệu được them vào thông tin
điều khiển gọi là Header. Khi nhận dữ liệu thì quá trình xảy ra ngược lại. dữ liệu
được truyền từ tấng dưới lên và qua mỗi tầng thì phần header tương ứng sẽ được lấy
đi và khi đến tầng trên cùng thì dữ liệu khơng cịn phần header nữa.

Cấu trúc dữ liệu trong TCP/IP
Hình trên cho ta thấy lược đồ dữ liệu qua các tầng.Trong hình ta thấy tại các
tầng khác nhau dữ liệu được mang những thuật ngữ khác nhau
6


- Trong tầng ứng dụng: dữ liệu là các luồng được gọi là stream.
- Trong tầng giao vận: đơn vị dữ liệu mà TCP gửi xuống gọi là TCP
segment.
- Trong tầng mạng, dữ liệu mà IP gửi xuống tầng dưới gọi là IP Datagram
- Trong tầng liên kết, dữ liệu được truyền đi gọi là frame.
2. Lập trình socket

2.1 Khái niệm Socket
Socket là một điểm cuối trong một kết nối giữa hai chương trình đang chạy trên
mạng. Trên quan điểm của người phát triển ứng dụng, Socket là một phương pháp
để thiết lập kết nối truyền thông giữa một chương trình yêu cầu dịch vụ (được gắn
nhãn Client) và một chương trình cung cấp dịch vụ (được gắn nhãn là Server) trên
mạng hoặc trên cùng một máy tính.
Đối với người lập trình, họ nhìn nhận Socket như một giao diện nằm giữa tầng
ứng dụng và tầng khác trong mơ hình mạng OSI có nhiệm vụ thực hiện việc giao
tiếp giữa chương trình ứng dụng với các tầng bên dưới của mạng.
Để có thể thực hiện các cuộc giao tiếp, một trong hai q trình phải cơng bố số
hiệu cổng socket mà mình sử dụng. Mỗi cổng giao tiếp thể hiện một địa chỉ xác
định trong hệ thống. Khi quá trình được gán một số hiệu cổng, nó có thể nhận dữ
liệu gửi đến cổng này từ các quá trình khác. Q trình cịn lại cũng được u cầu
tạo ra một socket.
Ngồi số hiệu cổng, hai bên giao tiếp cịn phải biết địa chỉ IP của nhau. Địa chỉ
IP giúp phân biệt máy tính này với máy tính khác trên mạng TCP/IP. Trong khi số
hiệu cổng dung để phân biệt các q trình khác nhau trên cùng một máy tính.
Số hiệu cổng gán cho socket phải duy nhất trên phạm vi máy tính đó, có giá trị
trong khoảng từ 0 đến 65535 (16 bit). Trong thực tế thì các số hiệu cổng từ 0 đến
1023 (gồm có 1024 cổng) đã dành cho các dịch vụ nổi tiếng như: http: 80, telnet:
21, ftp: 23, … Nếu chúng ta không phải là người quản trị thì nên dùng từ cổng 1024
trở lên.
2.2 Nguyên lý hoạt động
Dưới góc độ lập trình các socket thường làm việc theo cặp, một socket đóng vai
trị làm server cịn các socket khác đóng vai trị như clients. Socket phía server xác
7


định một cổng cho giao tiếp mạng, sau đó chờ nghe yêu cầu mà client gửi tới nó
bằng client socket. Do đó các cổng cho server socket phải được biết bởi các chương

trình client.
Như vậy số hiệu cổng của socket phía server được xác định bởi chương trình,
ngược lại cổng cho client socket được xác định bởi hệ điều hành. Khi một socket
phía client gửi một gói tin tới socket phía server thì trong gói tin đã có chứa thơng
tin về địa chỉ của hệ thống client và cổng của socket phía client nên server hồn
tồn có thể gửi thơng tin phản hồi cho client.
Khái quát quá trình trao đổi dữ liệu thơng qua các socket như sau:
+ Chương trình phía server tạo ra một socket, socket này được chương trình gắn
với một cổng trên server. Sau khi được tạo ra, socket này sẽ chờ lắng nghe yêu cầu
từ phía clients.
+ Khi chương trình phái clients cần kết nối với một server, nó cũng tạo ra một
socket, socket này cũng được hệ điều hành gắn với một cổng. Chương trình client
sẽ cung cấp cho socket của nó địa chỉ mạng và cổng của socket phía server và yêu
cầu thực hiện kết nối.
+ Chương trình phía server và chương trình phía clients trao đổi dữ liệu với
nhau bằng cách đọc từ socket hoặc ghi vào socket của mình.
3. Mơ hình Client
Server Mơ hình client/server sử dụng socket ở chế độ hướng kết nối TCP
Giai đoạn 1: Server tạo socket, gán số hiệu cổng và lắng nghe yêu cầu kết nối
 socket(): Server yêu cầu tạo một socket để sử dụng các dịch vụ của tầng vận
chuyển.
 bind(): Server yêu cầu gán số hiệu cổng (port) cho socket.
 listen(): Server lắng nghe các yêu cầu nối kết từ các client trên cổng đã được
gán.
Giai đoạn 2: Client tạo Socket, yêu cầu thiết lập một nối kết với Server.
 socket(): Client yêu cầu tạo một socket để có thể sử dụng các dịch vụ của
tầng vận chuyển, thông thường hệ thống tự động gán một số hiệu cổng còn
rảnh cho socket của Client.

8



 Connect(): Client gởi yêu cầu kết nối đến Server có địa chỉ IP và Port xác
định.
 Accept(): Server chấp nhận kết nối của Client, khi đó một kênh giao tiếp ảo
được hình thành, Client và Server có thể trao đổi thông tin với nhau thông
qua kênh ảo này.
Giai đoạn 3: Trao đổi thông tin giữa Client và Server
 Sau khi chấp nhận yêu cầu kết nối, thông thường Server thực hiện lệnh
receive() và nghe cho đến khi có thơng điệp yêu cầu (Request Message) từ
Client gởi đến.
 Server phân tích và thực thi yêu cầu. Kết quả sẽ được gởi về client bằng lệnh
send(). Sau khi gởi yêu cầu bằng lệnh send(), client chờ nhận thông điệp kết
quả (ReplyMessage) từ Server bằng lệnh receive().
Giai đoạn 4: Kết thúc phiên làm việc.
 Các câu lệnh receive(), send() có thể được thưc hiện nhiều lần (ký hiệu bằng
hình ellipse).
 Kênh ảo sẽ bị xóa khi Server hoặc Client đóng socket bằng lệnh close().
Như vậy tồn bộ q trình sẽ diễn ra như hình bên dưới:

4. Thuật tốn:
4.0 Random (Low AI):
9


Cho Enemy chạy random, trên dưới trái phải.
4.1 BFS:
Trong lý thuyết đồ thị, tìm kiếm theo chiều rộng (BFS) là một thuật tốn tìm
kiếm trong đồ thị trong đó việc tìm kiếm chỉ bao gồm 2 thao tác: (a) cho trước một
đỉnh của đồ thị; (b) thêm các đỉnh kề với đỉnh vừa cho vào danh sách có thể hướng

tới tiếp theo. Có thể sử dụng thuật tốn tìm kiếm theo chiều rộng cho hai mục đích:
tìm kiếm đường đi từ một đỉnh gốc cho trước tới một đỉnh đích, và tìm kiếm đường
đi từ đỉnh gốc tới tất cả các đỉnh khác. Trong đồ thị khơng có trọng số, thuật tốn
tìm kiếm theo chiều rộng ln tìm ra đường đi ngắn nhất có thể. Thuật tốn BFS bắt
đầu từ đỉnh gốc và lần lượt nhìn các đỉnh kề với đỉnh gốc. Sau đó, với mỗi đỉnh
trong số đó, thuật tốn lại lần lượt nhìn trước các đỉnh kề với nó mà chưa được quan
sát trước đó và lặp lại. Xem thêm thuật tốn tìm kiếm theo chiều sâu, trong đó cũng
sử dụng 2 thao tác trên nhưng có trình tự quan sát các đỉnh khác với thuật tốn tìm
kiếm theo chiều rộng.
Cho Bomberman xác định các Enemy, con nào gần nhất tiêu diệt con đó, từ đó
đặt bom tại để tiêu diệt Enemy. Tồn tại khi Enemy di chuyển thì Bomberman lại đổi
mục tiêu, điều này làm cho thời gian tiêu diệt Enemy bị kéo dài.
4.2 A*:
Trong khoa học máy tính, A* (đọc là A sao) là một thuật tốn tìm kiếm trong đồ
thị. Thuật tốn này tìm một đường đi từ một nút khởi đầu tới một nút đích cho trước
(hoặc tới một nút thỏa mãn một điều kiện đích). Thuật tốn này sử dụng một "đánh
giá heuristic" để xếp loại từng nút theo ước lượng về tuyến đường tốt nhất đi qua
nút đó. Thuật tốn này duyệt các nút theo thứ tự của đánh giá heuristic này. Do đó,
thuật tốn A* là một ví dụ của tìm kiếm theo lựa chọn tốt nhất (best-first search).
Thuật toán A* được mô tả lần đầu vào năm 1968 bởi Peter Hart, Nils Nilsson,
và Bertram Raphael. Trong bài báo của họ, thuật toán được gọi là thuật toán A; khi
sử dụng thuật tốn này với một đánh giá heuristic thích hợp sẽ thu được hoạt động
tối ưu, do đó mà có tên A*.
Năm 1964, Nils Nilsson phát minh ra một phương pháp tiếp cận dựa trên khám
phá để tăng tốc độ của thuật toán Dijkstra. Thuật toán này được gọi là A1. Năm
10


1967 Bertram Raphael đã cải thiện đáng kể thuật toán này, nhưng khơng thể hiển
thị tối ưu. Ơng gọi thuật tốn này là A2. Sau đó, trong năm 1968 Peter E. Hart đã

giới thiệu một đối số chứng minh A2 là tối ưu khi sử dụng thuật toán này với một
đánh giá heuristic thích hợp sẽ thu được hoạt động tối ưu. Chứng minh của ơng về
thuật tốn cũng bao gồm một phần cho thấy rằng các thuật toán A2 mới là thuật
tốn tốt nhất có thể được đưa ra các điều kiện. Do đó ơng đặt tên cho thuật tốn mới
là A *(A sao, A-star).
Thuật tốn A* cũng có cách tìm kiếm Enemy giống với BFS tuy nhiên có một số sự
ưu tiên, không phải tiêu diệt Enemy gần nhất như BFS, A* chọn một Enemy đến
chết thì thơi.
III.

Cơng cụ được áp dụng :
Ngơn ngữ lập trình : Java (xây dựng chương trình bằng các thư viện có sẵn trong

Java, và với đồ họa sử dụng thư viện Java Swing).
Cơ sở dữ liệu : MySQL.

CHƯƠNG 2: PHÂN TÍCH VÀ THIẾT KẾ HỆ THỐNG
I. Các chức năng chính của người dùng:


User :


Có thể đăng ký, đăng nhập để vào chơi trị chơi.



Có thể xem, sửa thơng tin cá nhân.




Có thể xem top user xếp hạng.



Có thể kết bạn, xem danh sách bạn bè.



Có thể tạo phịng, chọn bản đồ chơi, mời bạn vào phịng chơi, chơi
game.

II. Mơ tả các chức năng:


Đăng ký, đăng nhập: Nhiệm vụ ban đầu của người dùng trước khi vào chơi
là đăng ký và đăng nhập.


Đăng ký: Từ màn hình đăng ký người dùng sẽ nhập username,
password và xác nhận lại password của mình sau đó gửi lên server,
11


server xác thực người dùng đã tồn tại hay chưa, nếu đã có rồi thì báo
“username đã tồn tại”, nếu chưa xác nhận “đăng ký thành công”, vào
game.


Đăng nhập: Từ màn hình đăng nhập người dùng nhập username,

password sau đó gửi lên server, server xác thực việc tồn tại của
username, hoặc đúng password hay chưa, nếu chưa thì báo “sai
username hoặc password”, ngược lại người dùng vào được game.



Xem, sửa thơng tin cá nhân: Khi người dùng có nhu cầu xem, sửa thơng
tin. Từ màn hình sau khi đăng nhập người dùng có thể nhấn vào nút “thơng
tin cá nhân” và xem, sửa thơng tin của mình. Sau đó việc sửa thơng tin (nếu
có) sẽ gửi đến server để cập nhật database.



Xem top user xếp hạng: Khi người dùng có nhu cầu xem top người chơi
trong game.Từ màn hình sau khi đăng nhập nhấn vào nút “top xếp hạng”.
Server sẽ trả về kết quả 10 người chơi có điểm số tích lũy cao nhất.



Kết bạn, xem danh sách bạn bè: Chức năng kết bạn xây dựng làm sao cho
người dùng có thể dễ thao tác nhất. Từ màn hình sau khi đăng nhập bấm vào
nút “bạn bè”, xem danh sách bạn bè của mình, nếu muốn thêm bạn chỉ cần
nhập username mà người dùng muốn làm bạn. Sau đó gửi thơng tin lên
server để cập nhật database.



Tạo phịng chơi, chọn bản đồ chơi, mời bạn vào phòng chơi, chơi game:
Chức năng chính của chương trình. Từ màn hình sau khi đăng nhập bấm vào
nút “chơi game”. Sau khi nhấn nút “chơi game” hiển thị các phịng đang tồn

tại. Có thể vào chơi 1 phịng nào đó của người khác (có thể sẽ bị chủ phịng
đá ra ngồi). Hoặc nhấn nút “tạo phịng chơi”, chọn “bản đồ”, có thể mời
bạn trong danh sách vào chơi qua nút “mời”, nhấn nút “start” và chơi game.

12


III.









Thiết kế cơ sở dữ liệu:

Bảng user : Giúp hệ thống quản lý user:


user_id: số thứ tự đăng ký của người dùng (khóa)



user_name: tên tài tài khoản




password: mật khẩu



sex: giới tính của user



win: số trận thắng



lose: số trận thua



state : true online, false offline

Bảng friend: Giúp hệ thống quản lý danh sách friend của mỗi user:


friend_id: số thứ tự (khóa)



user_id: id của user 1 (khóa ngoại)



user_id_1: id của user 2 (khóa ngoại)


Bảng history: Giúp hệ thống quản lý lịch sử đăng nhập của user:


history_id: số thứ tự (khóa)



log_in: thời điểm đăng nhập



log_out: thời điểm đăng xuất



user_id: id của user (khóa ngoại)

Bảng room: Giúp hệ thống quản lý lịch sử đăng nhập của user:


room_id: số thứ tự (khóa)



state: true cịn người tạo phịng, false người tạo phịng đã thốt, phịng
sẽ bị đóng
13







quantity: số lượng người chơi trong phòng



user_id: id của user tạo phịng (khóa ngoại)

User :


Có thể đăng ký, đăng nhập để vào chơi trị chơi.



Có thể xem, sửa thơng tin cá nhân.



Có thể xem top user xếp hạng.



Có thể kết bạn, xem danh sách bạn bè.



Có thể tạo phịng, chọn bản đồ chơi, mời bạn vào phòng chơi, chơi

game.

IV.Sơ đồ thuật toán:
 Xem rank:

 Vào game:

14


 Xem lịch sử:
15


CHƯƠNG 3: ÁP DỤNG LÝ THUYẾT VÀ CHẠY THỬ SẢN
PHẨM


-

Môi trường chạy: Eclipse
Vào GAME:

16


Màn hình vào game (1)
-

Màn hình chơi game:


Bắt đầu game

Màn hình chơi game (1)
Tiêu diệt Enemy

17


Màn hình chơi game (2)
Bị Enemy tiêu diệt

Màn hình chơi game (3)

18


TÀI LIỆU THAM KHẢO
/> />329453697_Beating_Bomberman_with_Artificial_Intelligence
/>
/>
19


PHỤ LỤC
Phần này bao gồm những nội dung cần thiết nhằm minh họa hoặc bổ trợ cho
nội dung luận văn như số liệu, mẫu biểu, tranh ảnh... Phụ lục không được dày hơn
phần chính của luận văn. Phụ lục đuợc đánh số trang tiếp với đồ án.
Source code và thông tin chi tiết về game:
/>

20