TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
KHOA CÔNG NGHỆ THÔNG TIN
BỘ MÔN CÔNG NGHỆ TRI THỨC

NGUYỄN THANH PHONG

ỨNG DỤNG TRÍ TUỆ NHÂN TẠO
TRONG XÂY DỰNG GAME

KHÓA LUẬN CỬ NHÂN TIN HỌC

TP. HCM, 2005


TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
KHOA CÔNG NGHỆ THÔNG TIN
BỘ MÔN CÔNG NGHỆ TRI THỨC

NGUYỄN THANH PHONG - 0112191

ỨNG DỤNG TRÍ TUỆ NHÂN TẠO
TRONG XÂY DỰNG GAME
KHÓA LUẬN CỬ NHÂN TIN HỌC

GIÁO VIÊN HƯỚNG DẪN
TH.S BÙI TIẾN LÊN

NIÊN KHÓA 2001-2005


NHẬN XÉT CỦA GIÁO VIÊN HƯỚNG DẪN

......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................


LỜI CẢM ƠN
Em sẽ không thể hoàn thành luận văn nếu không có sự hướng dẫn và chỉ
bảo tận tình của thầy Bùi Tiến Lên. Em xin chân thành cảm ơn sự chỉ bảo của
thầy.
Em cũng rất cảm ơn các thầy cô trong khoa Công nghệ Thông tin trường
Đại học Khoa học Tự nhiên Tp.Hồ Chí Minh đã tận tình giảng dạy, truyền đạt
những kiến thức quý báu và tạo điều kiện cho em hoàn thành luận văn này.
Xin chân thành cảm ơn sự giúp đỡ, động viên của của tất cả các bạn trong
quá trình thực hiện luận văn.
Em cũng muốn cảm ơn những người thân trong gia đình đã động viên, giúp
đỡ và tạo điều kiện để hoàn thành luận văn.
Mặc dù đã cố gắng hoàn thành luận văn với tất cả sự nổ lực của bản thân,
nhưng luận văn chắc chắn không tránh khỏi những thiếu xót. Em rất mong
nhận được sự thông cảm và chỉ bảo tận tình của các thầy cô và các bạn.
Tp.HCM 7/2005
Sinh viên thực hiện
Nguyễn Thanh Phong


Hướng

đối

tượng

................................................................................ 16 f. Cửa sổ dự án
....................................................................................... 18
2. Các lệnh trong WED ............................................................................... 19
2.1.Các lệnh trong các thực đơn ............................................................ 19
2.1.1. Thực đơn file .......................................................................... 20
2.1.2. Thực đơn edit: ........................................................................ 24

i


Mục lục

2.1.3. Thực đơn mode ...................................................................... 25
2.1.4. Thực đơn Object..................................................................... 29
2.1.5. Thực đơn Texture ................................................................... 32
2.1.5. Thực đơn View....................................................................... 33
2.1.6. Thực đơn help ........................................................................ 34
2.2 Giao diện sử dụng ............................................................................ 35
2.3. Cửa sổ dự án ................................................................................... 36
2.3.1. Tab đối tượng ......................................................................... 36
2.3.2. Tab Views .............................................................................. 38
2.3.3. Tab Texture ............................................................................ 38
2.3.4. Tab Resource.......................................................................... 41

1.2.5. Toolbar các đối tượng cơ sở................................................... 61
1.2.6. Toolbar view .......................................................................... 62
1.2.7. Toolbar Frame ........................................................................ 63
1.2.8. Thanh trạng thái ..................................................................... 64
2.Trình thiết kế Skin .................................................................................... 64
2.1. Các thực đơn ................................................................................... 65
2.1.1. Thực đơn File ......................................................................... 65
2.1.2. Thực đơn Edit......................................................................... 66
2.1.3. Thực đơn View....................................................................... 67
2.2. Các Toolbar..................................................................................... 68
2.2.1. Toolbar Skin ........................................................................... 68
2.2.2. Toolbar Edit............................................................................ 68
2.2.3. Toolbar Paint .......................................................................... 69
III. SED, C-Script editor ................................................................................... 70
1. Giao diện sử dụng.................................................................................... 71
2. Soạn thảo ................................................................................................. 72
2.1. Lệnh Insert ...................................................................................... 72
2.2. Dòng chú thích................................................................................ 72
2.3. Nhảy đến một đoạn mã ................................................................... 72
2.4. Sử dụng danh sách các thành phần ................................................. 73
2.5. Kiểm tra cú pháp............................................................................. 73

3


Mục lục

2.6. Soạn thảo thông minh ..................................................................... 73
3. Cấu hình .................................................................................................. 74
4. Thực đơn.................................................................................................. 75


Chương 1: Giới thiệu

Chương 1

GIỚI THIỆU
1. Lý do chọn đề tài
Ngày nay, do nhu cầu đời sống của con người ngày càng được nâng cao,
trong đó nhu cầu giải trí của con người được quan tâm đến rất nhiều. Trong đó
việc giải trí bằng Game máy tính ngày càng phát triển nhanh và lan rộng ra do
sự lôi cuốn rất mạnh mẽ của nó. Hầu như ai đã sử dụng máy tính đều đã giải trí
bằng một số game nào đó trên máy tính. Có thể nói Game là một thể loại phóng
phú nhất trong tất cả các loại chương trình trên máy tính.
Mặc dù các chương trình Game rất nhiều, nhưng để có thể viết ra được một
game hay, có thể chơi được quả là một điều không dễ. Tuy vậy, với niềm đam
mê về game máy tính, em cũng muốn tiếp cận với lĩnh vực này.

1.1. Các ngôn ngữ lập trình game
Có rất nhiều chương trình hỗ trợ cho việc viết game: các ngôn ngữ lập trình
như C++, Visual C++, Delphi, Dark Basic Pro, 3D Game Studio.
Nhưng với các ngôn ngữ lập trình C++, Visual C++, DelPhi… có thể là
những ngôn ngữ rất mạnh, có thể viết ra được những game có quy mô lớn. Đây
là những ngôn ngữ lập trình có thể hoạt động trong nhiều lĩnh vực: với cơ sở dữ
liệu, lập trình hệ thống, hoặc viết game…Do đó sự hỗ trợ của nó trong việc viết
game là rất ít. Để có thể viết được một game bằng những ngôn ngữ lập trình
này mà không sử dụng một thư viện nào, đòi hỏi phải bỏ ra rất nhiều công sức.
Với engine Dark Basic Pro, đây là loại engine rất đơn giản và dễ sử dụng, là
một ngôn ngữ Script theo họ Basic. Nó chỉ thích hợp với các game nhỏ.
Tại sao lại sử dụng ngôn ngữ 3D Game Studio để viết game?
3D Game Studio là chương trình chuyên dụng dùng để tạo ra game 3D.


1.2.2. Game nhập vai
Game nhập vai thường có hai đặc trưng là: sự thay đổi, phát triển nhân vật
và một câu chuyện mà trong đó nhân vật sẽ trải qua.

1.2.3. Game thể thao
Game thể thao là sự thách thức cho các nhà thiết kế game. Không giống như
hầu hết các thể loại game khác, người chơi biết rất ít về nó, trong game thể thao
người chơi biết rất rõ vì nó mô phỏng một môn thể thao có sẵn trong thực tế.

1.2.3. Game đua xe
Game đua xe tạo ra cảm giác giống như người chơi đang lái xe bên ngoài
thế giới thực.
Tuy trong đề tài của em không thể nói là viết ra được một game chơi được
như một game đua xe, mà đây chỉ là một chương trình ở mức độ mô phỏng
giao thông trên đường phố.

2. Mục đích của đề tài
Tìm hiểu ngôn ngữ lập trình game trong 3D GameStudio:
- Tìm hiểu về WED, một chương trình thiết kế khung cảnh trong game.
- Tìm hiểu về MED, một chương trình thiết kế các mô hình trong game.
- Tìm hiểu về SED, trình soạn thảo dùng để viết các câu lệnh script để kết
nối các mô hình được tạo ra trong MED, các khung cảnh được tạo ra trong
WED và sử dụng những hàm có sẵn trong SED hoặc trong các DLL khác để
tạo ra một game.
Sử dụng thuật toán cổ điển A* tìm kiếm đường đi để một đối tượng có thể
chuyển động theo một hướng mong muốn nào đó.


Chương 2: Các thuật toán tìm đường đi


thị hoặc cây tìm kiếm. Nhiều bài toán phức tạp nếu giải quyết bằng phương
pháp tìm kiếm ngẫu nhiên thì hầu như vô vọng vì số đường đi có thể sẽ tăng lên
theo hàm mũ của số đỉnh. Chính ở đây biểu lộ toàn bộ bản chất của trí tuệ nhân
tạo khi giải quyết các vấn đề: Đó là nghệ thuật xử trí với các vấn đề lớn bằng
cách giảm số lượng tìm kiếm.
Các thủ tục tìm kiếm điển hình bao gồm:
− Tìm kiếm rộng: đường đi được tìm theo mọi hướng có thể ở mỗi bước.
− Tìm kiếm sâu: đường đi sâu mãi theo một hướng đến khi nào không tiếp
tục được nữa mới chuyển sang hướng khác.
− Tìm kiếm sâu dần: kết hợp tìm kiếm rộng và tìm kiếm sâu trên cơ sở cho
trước mức sâu n rồi tìm kiếm rộng ứng với mức sâu đó.
− Tìm kiếm cực tiểu hóa giá thành: mỗi cung của cây (đồ thị) được gán giá
thành và hướng tìm kiếm được xác định bởi việc cực tiểu hóa giá thành
đường đi.
− Tìm kiếm với tri thức bổ sung: hướng tìm kiếm được xác định với tri
thức bổ sung ở mỗi bước.
Trước hết các thủ tục tìm kiếm rộng, sâu và sâu dần sẽ được mô tả qua một
ví dụ. Sau đó một số thuật giải tìm kiếm cực tiểu hóa giá thành và bổ sung tri
thức sẽ được trình bày chi tiết.


Chương 2: Các thuật toán tìm đường đi

1. Mô tả các thủ tục tìm kiếm rộng, sâu và sâu dần
100
B

A
1


1

1

1

O
1

P

Q

R

1

1
T

S
1

U
1
Trạng thái mong muốn

V


Thuật giải A gồm các bước sau:
Bước 1: Đầu tiên, mọi đỉnh n và mọi giá trị g(n) đều là ẩn. Mở đỉnh đầu tiên
(coi đỉnh đầu tiên là đỉnh mở và đặt giá trị g tương ứng bằng 0).
Bước 2: Chọn đỉnh mở với giá thành g tương ứng nhỏ nhất. Gọi đỉnh này là
N, nếu N là đỉnh mục tiêu thì đường dẫn tới N là đường đi có giá thành nhỏ
nhất g(n) và vấn đề đã được giải. Nếu không còn đỉnh mở nào thì cây biểu
diễn vấn đề không có đường đi tới mục tiêu. Nếu có từ 2 đỉnh trở lên cùng
giá trị g nhỏ nhất thì kiểm tra trong số đó có đỉnh mục tiêu không? Nếu có
thì chọn đỉnh mục tiêu đó và quá trình giải kết thúc. Nếu không thì chọn tùy
ý một đỉnh trong số đó và gọi là N.
Bước 3: Đóng đỉnh N và mở các đỉnh sau N (có cùng hướng đến N), với
mỗi đỉnh sau N gọi là s, ta tính:
g(s)=g(N)+(giá thành cung từ N tới s)
Bước 4: Quay trở lại bước 2.
T

Thuật giải A đã được chứng minh là luôn luôn tìm được đường đi với giá
thành nhỏ nhất nếu như tồn tại đường đó trên đồ thị và là thuật giải tối ưu theo
nghĩa số đỉnh đóng trong quá trình tìm kiếm là ít nhất.


Chương 2: Các thuật toán tìm đường đi

3. Tìm kiếm với tri thức bổ sung
T

Thuật giải A là thuật giải tìm kiếm đường đi tốt nhất đối với các cây chỉ có
thông tin về đỉnh, cung và giá thành cung. Nhưng trong nhiều trường hợp việc
tìm kiếm đường đi sẽ được định hướng rõ thêm nếu sử dụng các tri thức thu
được dựa trên những hiểu biết về tình huống vấn đề ở mỗi bước. Các thủ tục

a) Đầu tiên, mọi đỉnh cũng như giá trị g, h , f là chưa biết. Mở đỉnh đầu
tiên (o) và gán g(0), sử dụng tri thức bổ sung để ước tính h(0) và tính
∧

∧

f (0) = g (0) + h(0) .
∧

∧

b) Chọn đỉnh mở có giá trị f = g (n) + h(n) nhỏ nhất. Gọi đỉnh này là N. Nếu
N là mục tiêu thì đường tới N là đường đi có giá thành nhỏ nhất g(N). Nếu
không tồn tại đỉnh mở nào thì cây không tồn tại đường đi tới mục tiêu. Nếu có



∧

từ 2 đỉnh mở trở lên cùng giá trị f nhỏ nhất, hãy kiểm tra trong các đỉnh này
có chứa mục tiêu không? Nếu một trong các đỉnh này là mục tiêu thì vấn đề đã
được giải quyết, còn không thì chọn tùy ý một trong các đỉnh này là N.
c) Đóng đỉnh N, mở đỉnh sau N. Với mỗi đỉnh S sau N ta tính
g(s)=g(N)+(giá thành cung từ N đến S). Sử dụng tri thức bổ sung ở bước này,
∧

∧

∧


KT

tìm ra vẫn dùng được

trong nhiều trường hợp thực tiễn giải quyết vấn đề.

4. Tìm đường đi trên đồ thị tổng quát
Các phần trên đã trình bày thuật giải tìm đường đi trên đồ thị dạng cây. Tuy
nhiên biểu diễn dạng cây nhiều khi sẽ lặp lại quá nhiều một trạng thái. Điều đó
sẽ tăng thêm thời gian tim kiếm. Để khắc phục cần nới bỏ điều kiện mỗi đỉnh
chỉ có một cung hướng đến và do vậy phải nghiên cứu thuật giải tìm đường đi


trên một đồ thị dạng tổng quát. Ta cũng có thể mở rộng thuật giải A
*

thuật giải tổng quát A như sau:

KT

thành


∧

∧

Bước 1: Đầu tiên, mọi đỉnh và các giá trị g, h , f đều xem như chưa biết,
∧


∧

phố dựa theo bản đồ giao thông với tri thức bổ sung h(n) có thể là khoảng cách
đường chim bay từ điểm (thành phố) n tới mục tiêu (thành phố cần đến). Do
khoảng cách đường chim bay bao giờ cũng nhỏ hơn khoảng cách đường giao
∧

∧

thông nên h(n) ≤ h(n) với mọi n. Thuật giải A* với tri thức bổ sung h(n) như
trên sẽ tìm được đường đi ngắn nhất (hoặc giá thành nhỏ nhất) với mức độ hiệu
∧

quả càng cao nếu h(n) càng gần h(n).
∧

∧

∧

Trong thuật giải A*, ta đặc f = g + h ở đây vai trò của g và h được xem là
∧

∧

như nhau. Nhưng tùy theo trường hợp, có thể xét f = w1.g + w2. với w1, w2
h