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

Viết thuê luận văn thạc sĩ
- 0972.162.399


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 PHẢN BIỆN
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................
......................................................................................................

Viết thuê luận văn thạc sĩ
- 0972.162.399


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

2. Thuật giải tìm đường đi có giá thành nhỏ nhất AT ................................... 7
3.Tìm kiếm với tri thức bổ sung.................................................................... 8
4.Tìm đường đi trên đồ thị tổng quát ............................................................ 9
Chương 3 GAME ENGINE ........................................................................... 12
I. WED editor:................................................................................................... 13
1. Những khái niệm cơ bản ......................................................................... 13
a. Giao diện người dùng......................................................................... 13
b. Thanh Icon ......................................................................................... 15
c. Mode .................................................................................................. 15
d. Thiết kế một khung cảnh ................................................................... 14
e. 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

Viết thuê luận văn thạc sĩ
- 0972.162.399


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

Mục lục

1.1.4. Thực đơn Options................................................................... 56
1.1.5. Thực đơn Help........................................................................ 57
1.2. Toolbars................................................................................................ 58
1.2.1. Toolbar File ............................................................................ 58
1.2.2. Toolbar Edit............................................................................ 58
1.2.3. Toolbar Select ........................................................................ 60
1.2.4. Toolbar Mesh ......................................................................... 60
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

2.3. Cách để cho camera tránh chạm vào tường .................................. 106
II. Xe tự động .................................................................................................. 108
Tránh chướng ngại vật trên đường đi........................................................ 108

iv

Viết thuê luận văn thạc sĩ
- 0972.162.399


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à

script trong 3D Game Studio để viết và phân phối một game thương mại. Dưới
đây là những game thương mại được làm bằng 3D Game Studio:

1.2. Phân loại game
Thể loại của game thì rất phong phú và đa dạng, ở đây chúng ta chỉ xét các
thể loại game thường thấy nhất là:

1.2.1. Game hành động
Game hành động xuất hiện rất nhiều trong cả game 3D và game 2D. Game
loại này có đặc điểm chúng là tính co giật trong game, như trong game bắn

2

Viết thuê luận văn thạc sĩ
- 0972.162.399


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

súng. Game hành động thường đơn giản hơn tất cả các loại game khác bởi vì
những người bình thường dễ dàng biết cách chơi và chơi hay game này .

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ế.

ĐƯỜNG ĐI
Hầu hết các bài toán hoặc vấn đề đều có thể phát biểu dưới dạng “từ một
trạng thái xuất phát hãy tìm đường dẫn đến một trạng thái kết thúc mong
muốn”
Việc tìm “đường dẫn” từ trạng thái xuất phát (S0) đến trạng thái kết thúc
(Sn) gồm có một số bước sau đây:
− Chọn không gian tìm kiếm thích hợp.
− Tiến hành tìm kiếm có hệ thống và hiệu quả trong không gian tìm kiếm.
− Sử dụng triệt để các nguồn tri thức liên quan trong quá trình tìm kiếm
tương ứng với miền đối tượng cụ thể.
Không gian tìm kiếm của một vấn đề cần giải trên máy tính thường được
biểu diễn bằng đồ thị hay một dạng đặt biệt của đồ thị là cây. Đồ thị là một tập
hợp giữa các đỉnh và các cung nối giữa các đỉnh. Các cung có thể được định
hướng hoặc không định hướng, gán giá trị hoặc không gán giá trị.
Cây là đồ thị định hướng đặt biệt có duy nhất một đỉnh mà không có cung
nào hướng đến (gốc của cây), và mỗi đỉnh khác của cây chỉ có duy nhất một
cung hướng đến.
Sau khi bài toán hoặc vấn đề được biểu diễn lại dưới dạng đồ thị hoặc cây:
− Mỗi đỉnh là một trạng thái của quá trình giải bài toán.
− Mỗi cung là tác động biến đổi quá trình từ giai đoạn này sang giai đoạn
khác.
Như vậy, việc giải quyết một bài toán cũng chỉ là tìm đường đi từ trạng thái
ban đầu đến trạng thái mong muốn được biểu diễn qua hai đỉnh nào đó của đồ

4

Viết thuê luận văn thạc sĩ
- 0972.162.399



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

A

B
1

1

17

F

10

10

G
1

H

L

M

K
1


P

Q

R

1

1
T

S
1

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

V

Tìm kiếm rộng: quá trình tìm kiếm sẽ lần lượt là A, B, C, D, E, F, G, H, I,
J, K, L, M, N, O, P, Q, R, S, T, U, V…
Tìm kiếm sâu: quá trình tìm kiếm sẽ lần lượt là A, E, K, O, Q, S, T, U, V,
…B, F,… C, G, L, H, M, … D, I, J, N, P, R.
Chú ý: nếu nhánh dưới v dài vô hạn thì quá trình tìm kiếm sẽ không bao giờ
đến được mục tiêu.
Tìm kiếm sâu dần: ứng với mức sâu 2: (A,E), (B,F), (C,G), (C,H), (D,I),
(D,J).

6

ý 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.
Thuật giải AT đã đượ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.

7

Viết thuê luận văn thạc sĩ
- 0972.162.399


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
Thuật giải AT 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
tìm kiểm dựa trên 3 cách tiếp cận:
− Không tính đến các tri thức bổ sung ngoài thông tin về đỉnh, cung, giá
thành.
− Sử dụng tri thức bổ sung để tìm cách giải riêng biệt cho vấn đề mà bỏ
qua việc xây dựng cây biểu diễn cho vấn đề.
− Xây dựng biểu diễn vấn đề dưới dạng cây có tính đến tri thức bổ sung
trong cấu trúc cây hoặc giá thành các cung.
Ngoài ra có có cách tiếp cạn theo hướng xây dựng các thuật giải “vạn


Viết thuê luận văn thạc sĩ
- 0972.162.399


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

∧

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,
∧

∧

∧

ước lượng h( s) và gán cho f(s) giá trị f ( s) = g ( s ) + h( s) .
d) Quay về bước 2.
Giải thích ý nghĩa AKT: giả sử h(n) là giá thành nhỏ nhất được biết chính
xác từ n đến mục tiêu. Như vậy h(n) chỉ là ước lượng gần đúng về h(n). nếu
∧

h(n) ≡ h(n) thì AKT là thủ tục hoàn toàn tuyệt đối (các đỉnh đóng đúng là các

đỉnh nằm trên đường đi ngắn nhất đến mục tiêu). Trong trường hợp không có
∧


Chương 2: Các thuật toán 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 AKT thành
thuật giải tổng quát A* như sau:
∧

∧

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

∧

∧

mở đỉnh đầu tiên 0, gán cho g(0)=0, ước lượng h(0) và gán f (0) = h(0) .
∧

∧

Bước 2: Chọn đỉnh mở với giá trị f = g + h nhỏ nhất và gọi là N. Nếu N là
mục tiêu thì đường dẫn tới N đã tìm được và g(N) là giá thành của đường đi đó.
Nếu không tồn tại đỉnh mở thì đồ thị đó không tồn tại đường đi đến mục tiêu.
∧

Nếu có từ 2 đỉnh mở trở lên cùng giá trị f và 1 trong 2 đỉnh đó là mục tiêu thì
quá trình tìm đường đi cũng kết thúc, còn không thì chọn tùy ý một trong 2
đỉnh đó là N.
Bước 3: Đóng đỉnh N và đối với mỗi đỉnh sau đó, ta tính g′( s) = g ( N ) + (giá

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. h với w1, w2

10

Viết thuê luận văn thạc sĩ
- 0972.162.399


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

∧

là các trọng số cho biết vai trò của g và h tham gia trong quá trình giải. Ngoài
∧

ra cũng cần thêm các ước lượng về giá thành (độ phức tạp) của việc xác định h
và tập đỉnh đóng để có cơ sở đánh giá hiệu quả của thuật giải một cách đầy đủ.

11

Viết thuê luận văn thạc sĩ
- 0972.162.399


Chương 3: Game Engine



Chương 3: Game Engine – Cách sử dụng WED

I. WED editor
WED là một trình biên soạn. Lập trình viên có thể sử dụng nó để tạo ra một
thế giới ảo của game. WED là công cụ để kết hợp lại toàn bộ các thành phần:
level (được tạo ra bởi WED), các mô hình (được tạo ra bởi MED) và các mã
lệnh (được viết trong SED) tạo ra sản phẩm cuối cùng.
Với WED, chúng ta có thể tạo ra được một khung cảnh 3D hết sức dễ dàng
mà không cần phải có bất cứ kinh nghiệm gì về việc tạo hình 3D. Với cả những
người mới bắt đầu và những nhà thiết kế chuyên nghiệp, WED cũng sẽ là một
công cụ rất cần thiết có thể tạo ra một khung cảnh 3D chuyên nghiệp một cách
đơn giản và nhanh chóng.

1.Những khái niệm cơ bản
a. Giao diện sử dụng
Khi mở WED, màn hình giao diện sau sẽ xuất hiện:

13

Viết thuê luận văn thạc sĩ
- 0972.162.399


Chương 3: Game Engine – Cách sử dụng WED

Đây chính là môi trường mà chúng ta sẽ làm việc để tạo ra một game trong
3D GameStudio. Tạo ra một game 3D, tức là đưa những đối tượng vào môi
trường 3D này, và gắn các thuộc tính và hành vi mà chúng ta đã lập trình vào

hiện một dòng chữ gần con chuột để giải thích ý nghĩa của nút này. Có thể cho
hiển thị hay ẩn đi các thanh bar File, Edit và View bằng cách chọn vào menu
View/Toolbar. Ngoài ra, chúng ta có thể di chuyển từng thanh bar đến bất cứ
đâu trên cửa sổ. Mặc định, sau đây là thứ tự của các nút trên thanh bar:
New, Open, Save, Copy, Paste, Undo, Build, Run, Select, Move, Rotate, Scale,
Vertex Move, Edge Move, Face Move, Add Object, Delete Object, Snap on/off,
Snap Mode, Snap Size, Axis Restriction, Eye Move, Eye Rotate, Eye Zoom,
Camera Move, Camera Walkthru, Scope Up, Scope Down.

c. Mode
Chế độ Select: Nếu chế độ này được chọn, khi nhấn
nút trái chuột thì một khối, nhóm hoặc một đối tượng
nào đó sẽ được chọn. Nếu không chọn được đối tượng
mong muốn, có thể là nó đang được phủ bởi một đối
tượng khác, vì thế chỉ cần nhấn nút chuột trái tiếp đến
khi nào chọn được thì thôi. Chúng ta có thể chọn nhiều
đối tượng bằng cách kéo rê một hình chữ nhật xung

15

Viết thuê luận văn thạc sĩ
- 0972.162.399


Chương 3: Game Engine – Cách sử dụng WED

quanh chúng, hoặc giữ phím [CTRL] trong khi chọn các đối tượng.
Chế độ Move: Nếu chế độ này được chọn, thì có thể di chuyển một đối
tượng bằng cách nhấn nút trái chuột và rê nó đến vị trí mong muốn. Hãy nhìn
vào các khung nhìn để kiểm tra xem đối tượng có đến được nơi mong muốn

- 0972.162.399