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

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
2.4. Cửa sổ Bookmark ........................................................................... 41
2.5. Thuộc tính của khối ........................................................................ 41
2.6. Thuộc tính của thực thể .................................................................. 43
3. Thiết kế một map..................................................................................... 45
4. Thực thể................................................................................................... 46
4.1. Thực thể mô hình............................................................................ 46

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

iii

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
4.1. Thực đơn File.................................................................................. 75
4.2. Thực đơn Edit ................................................................................. 76
4.3. Thực đơn Options ........................................................................... 76
4.4. Thực đơn Tools............................................................................... 77
4.5. Thực đơn Debug ............................................................................. 77
IV. Giao tiếp với các DLL ................................................................................ 79
1. Bắt đầu với SDK ..................................................................................... 79
2. Sử dụng đối tượng C-Script trong một DLL........................................... 82
3. Sử dụng các hàm API.............................................................................. 83

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

Chương 1: Giới thiệu
Với hàng trăm game đã được phát hành, 3D Game Studio xứng đáng là một
ngôn ngữ lập trình game lớn. Với 3D Game Studio, chúng ta có thể:
- Tạo ra một game đơn giản từ những script mẫu có sẵn.
- Tạo ra các game thương mại viết bằng ngôn ngữ script.
- Có thể sử dụng VisualC++ hoặc Delphi để kết hợp với 3D Game Studio
để viết game.
Có rất nhiều tài liệu hướng dẫn lập trình game bằng 3D Game Studio. Ngay
cả với những người ch
ưa có kiến thức về lập trình, nhưng nếu theo từng bước
hướng dẫn tạo một game hành động đơn giản thì cũng có thể hoàn thành nó

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 đó.
3

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

Chương 2

CÁC THUẬT TOÁN TÌM
ĐƯỜ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 (S


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.

5

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


17
1 10 12 1
1 1 1
1
1
Trạng thái mong muốn

6

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

ứng với mức sâu 3: (A,E,K), (B,F), (C,G,L), (C,H,M), (D,I), (D,J,N).
2.
Thuật giải tìm đường đi có giá thành nhỏ nhất
A
T

(Algorithm for Trees) với mỗi đỉnh n tương ưng số g(n) là giá thành
đường đi từ đỉnh đầu tới n. (g(n) có thể chưa xác định đối với các đỉnh thuộc
phần cây chưa hướng đến). Mỗi đỉnh n có thể là:
− Đỉnh đóng: nghĩa là đỉnh đã được xem xét;
− Đỉnh mở: là đỉnh giả định sẽ được xem ở bước sau;
− Đỉnh ẩn: là đỉnh mà hàm g(n) tương ứng ch
ưa được tính đến và chưa
được xem xét đến.
Thuật giải A
T
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).

đượ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
năng”, tìm kiếm đường đi với tri thức b
ổ sung. Họ thuật giải này mang tên là
A
KT
(Algorithm for knowledgeable Tree search). Tri thức bổ sung ở mỗi đỉnh
được tương ứng một giá trị
. Chẳng hạn đó là ước lượng giá thành đường
đi từ n đến mục tiêu (như vậy
là ước lượng giá thành đường đi con chương
biết đến).
)(nh
∧
∧
h
Thuật giải A
KT
gồm các bước sau:
a) Đầu tiên, mọi đỉnh cũng như giá trị g,
, 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

và gán cho f(s) giá trị .
)(
sh
∧
)()()(
shsgsf
∧∧
+=
d) Quay về bước 2.
Giải thích ý nghĩa A
KT
: 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
thì A
)()(
nhnh
≡
∧
KT
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ó
tri thức bổ sung,
và A
0)( =
∧
nh
KT
suy biến thành A
T
. Ta thấy rõ ràng rằng giữa

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

9

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 A
KT
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,
, đều xem như chưa biết,
mở đỉnh đầu tiên 0, gán cho g(0)=0, ước lượng
và gán .
∧
h
∧
f
)0(
∧
h )0()0(
∧∧
=
hf
Bước 2: Chọn đỉnh mở với giá trị
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.

Bây giờ chúng ta có thể dùng A* để tìm đường đi ngắn nhất giữa 2 thành
phố dựa theo bản đồ giao thông với tri thức bổ sung
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
với mọi n. Thuật giải A* với tri thức bổ sung 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
càng gần h(n).
)(nh
∧
)()( nhnh ≤
∧
)(nh
∧
)(nh
∧
Trong thuật giải A*, ta đặc
ở đây vai trò của g và được xem là
như nhau. Nhưng tùy theo trường hợp, có thể xét
với w1, w2
∧∧
+= hgf
∧
h
∧∧
+= hwgwf .2.1

10

engine, họ không cần quan tâm một engine thực sự làm việc như thế nào, họ
chỉ cần xác định đưa vào những gì, và engine sẽ đưa ra kết quả.
Có rất nhiều định nghĩa khác nhau về engine. Các nguyên lý tổng quát mà 1
engine ph
ải có :
1. Quản lý dữ liệu trong vùng mà nó chịu trách nhiệm.
2. Tính toán dữ liệu theo nhiệm vụ của nó.
3. Xử lý dữ liệu đến instance sau của nó, nếu cần thiết.
4. Nhận dữ liệu để quản lý và tính toán từ các instance có trước.
3D GameStudio cũng là một game engine. Nó bao gồm 3 thành phần sau:
WED editor, MED, C-Script editor. Chúng ta cùng tìm hiểu cách sử dụng của 3
bộ phận của 3D GameStudio.

12

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

Chương 3: Game Engine – Cách sử dụng WED
Khi click phải vào khung nhìn 3D và chọn GXL Properties, thì các đặc
điểm như độ sáng và tầm nhìn có thể được thay đổi.
Chúng ta có thể tìm thấy thanh bar ở phía trên, phía dưới là dòng trạng thái và
phía trái là cửa sổ dự án. Nó chứa các cửa sổ Objects, Views, Textures và
Resources.
b. Thanh Icon

Thanh bar này chứa những hàm thường dùng trong các menu, và chúng ta
có thể gọi một hàm bằng cách nhấp chuột. Khi rê chút đến một Icon sẽ xuất
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

Thành phần thứ 2 là thực thể, thực thể gồm 4 loại sau đây: terrain, map,
model và sprite. Mỗi loại được sử dụng cho những mục đích khác nhau.
e. Hướng đối tượng

16