Khóa luận Ứng dụng trí tuệ nhân tạo trong xây dựng game

N ...................................................................................................... ...................................................................................................... ...................................................................................................... ...................................................................................................... ...................................................................................................... ...................................................................................................... ...................................................................................................... ...................................................................................................... ...................................................................................................... ...................................................................................................... ...................................................................................................... ...................................................................................................... ...................................................................................................... ...................................................................................................... ...................................................................................................... ...................................................................................................... ...................................................................................................... ...................................................................................................... ...................................................................................................... NHẬN XÉT CỦA GIÁO VIÊN PHẢN BIỆ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 Mục lục MỤC LỤC Chương 1 GIỚI THIỆU ................................................................................... 1 1. Lý do chọn đề tài ....................................................................................... 1 1.1. Các ngôn ngữ lập trình game............................................................ 1 1.2. Phân loại game.................................................................................. 2 1.2.1. Game hành động....................................................................... 2 1.2.2. Game nhập vai.......................................................................... 3 1.2.3. Game đua xe............................................................................. 3 2. Mục đích của đề tài ................................................................................... 3 Chương 2 CÁC THUẬT TOÁN TÌM ĐƯỜNG ĐI ....................................... 4 1. Mô tả các thủ tục tìm kiếm rộng, sâu và sâu dần ...................................... 6 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 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 4.2. Thực thể Sprite................................................................................ 47 4.3. Thực thể Map.................................................................................. 47 4.4. Thực thể Địa hình (terrain) ............................................................. 48 4.5. Bóng................................................................................................ 48 4.5. Thuộc tính trong suốt...................................................................... 49 II. CÁCH SỬ DỤNG MED.............................................................................. 50 1. Trình thiết kế ........................................................................................... 50 1.1. Các thực đơn ................................................................................... 50 1.1.1. Thực đơn File ......................................................................... 50 1.1.2. Thực đơn Edit......................................................................... 53 1.1.3. Thực đơn View....................................................................... 55 ii 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 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 4. Lập trình một game trong C++................................................................ 87 Chương 4 CÀI ĐẶT........................................................................................ 89 I. Người chơi ..................................................................................................... 89 1. Chuyển động vật lý.................................................................................. 89 a. Gia tốc, quán tính và lực ma sát......................................................... 89 b. Rơi từ trên xuống ............................................................................... 93 2. Cách di chuyển camera theo người chơi ................................................. 97 2.1. Tầm nhìn của người thứ nhất.......................................................... 97 2.2. Quay tự do tầm nhìn của người thứ 3 ........................................... 101 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 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 gameDo đó 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ó trong một thời gian ngắn. Theo Dr.Dobb's Journal: “Đây là bộ công cụ tuyệt vời để nhanh chóng tạo ra mẫu ban đầu và phát triển ứng dụng 3D”. Chúng ta có thể sử dụng ngôn ngữ 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 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ế. 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 đó. 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 (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 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. 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 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). R V U T S Q P O K L M N J I H G F E A B C D 1 1 1 1 1 1 1 1 1 10 100 1 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 AT (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 AT 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. 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 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 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à AKT(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 AKT 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 . ∧ h ∧ f )0()0()0( ∧∧ += hgf b) Chọn đỉnh mở có giá trị 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ó )()( nhngf ∧∧ += 8 Chương 2: Các thuật toán tìm đường đi từ 2 đỉnh mở trở lên cùng giá trị 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. ∧ f 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 và gán cho f(s) giá trị . )(sh ∧ )()()( shsgsf ∧∧ += 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 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à A0)( =∧ nh KT suy biến thành AT. Ta thấy rõ ràng rằng giữa và sẽ tồn tại các thuật giải với mức độ hiệu quả rất thú vị. Nếu (với mọi n), A 0=∧h hh =∧ hh ≤∧ KT sẽ bảo đảm tìm ra được đường đi giá thành nhỏ nhất và tối ưu theo nghĩa sử dụng số đỉnh đóng ít nhất so với mọi thuật giải cũng chỉ làm việc với các tri thức như vậy. Nếu (với mọi n, hoặc với một số đỉnh). Ahh >∧ KT không bảo đảm tìm được đường đi giá thành nhỏ nhất nhưng đường đi mà AKT 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 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 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, , đề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. Nếu có từ 2 đỉnh mở trở lên cùng giá trị 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. ∧∧ += hgf ∧ f Bước 3: Đóng đỉnh N và đối với mỗi đỉnh sau đó, ta tính +=′ )()(g Ngs (giá thành cung từ N đến S). Nếu đỉnh S đã mở và )(gg(s) s′≤ thì bỏ qua S. Ngược lại ta mở S và đặt )(gg(s) s′= , tính và . )(sh∧ )()()( shsgsf ∧∧ += Bước 4: Quay về bước 2. 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 n... độ lớn và phạm vi của tài nguyên âm thanh. Add Position: Đặt một vị trí vào map. Vị trí có thể được xác định trong lúc viết mã. Nếu không có thực thể người chơi, vị trí đầu tiên được sử dụng là vị trí bắt đầu của camera. 31 Chương 3: Game Engine – Cách sử dụng WED Add Map Entity: Đặt một thực thể map (tập tin WMB) như cửa, thang máy, sân ga. Thực đơn hiện ra tất cả các thực thể map trong thư mục map và trong các thư mục con. Chúng ta có thể tự tạo ra một thực thể thể map bằng cách mở một đối tượng đã được làm sẵn, và BUILD để tạo ra tập tin WMB. Khi thêm một thực thể mới vào WED sẽ đặt chúng vào chính giữa 4 cửa sổ thiết kế. Add Model: đưa một thực thể mô hình (tập tin MDL) vào map, là các thực thể có thể chuyển động. Thực đơn hiện ra tất cả các thực thể mô hình trong thư mục map và trong các thư mục con. Chúng ta có thể tạo ra một thực thể mô hình bằng cách sử dụng chương trình thiết kế các mô hình, MED. Add Terrain: đưa một thực thể địa hình (tập tin HMP; không được hỗ trợ trong tất cả các phiên bản). Thực thể địa hình có thể được tạo ra bằng chương trình MED. Thực thể địa hình có thể được di chuyển và thay đổi kích thướt nhưng không quay được. Add Sprite: đưa một thực thể cảnh (tập tin PCX), như đồng cỏ, câyThực đơn hiện ra tất cả các thực thể cảnh trong thư mục map và trong các thư mục con. Có thể sử dụng các chương trình vẽ hình, như Paint Shop Pro, để tạo ra một thực thể cảnh. Nhớ lưu tâp tin PCX theo định dạng có màu sắc thật. Add Path: Thêm vào một đường dẫn, để các thực thể hành động sử dụng (không được hỗ trợ trong mọi phiên bản). Chúng ta có thể đặt tên cho đường dẫn trong properties; còn không thì một tên mặc định được tạo ra. Trong chế độ Vertex Mode, các điểm trong đường dẫn có thể được tạo thêm hoặc xóa đi. Load Entity: Đưa một tập tin thực thể từ một thư mục nào đó, đưa nó vào map, và sao chép nó vào thư mục map. Cẩn thận nếu không nó sẽ đè lên thực thể có cùng tên. Load Sound: Đưa một tập tin WAV từ một thư mục nào đó, đưa nó vào map, và sao chép nó vào thư mục map. 32 Chương 3: Game Engine – Cách sử dụng WED Load Prefab: Đưa tập tin WMP như là đối tượng kiểu khối vào khung cảnh thiết kế. Save Prefab: Lưu khối đối tượng được chọn vào tập tin WMP, để sử dụng trong các khung cảnh thiết kế khác. 2.1.5. Thực đơn Texture Apply to Object: Lệnh này gắn kết cấu được chọn trong cửa sổ texture đến tất cả các mặt của đối tượng được chọn. Hoặc chúng ta có thể nhấp double vào kết cấu được chọn trong cửa sổ kết cấu. Texture Bookmarks: Lệnh này mở ra một cửa sổ cho phép cất giữ các kết cấu ưa thích trong cửa sổ kết cấu. Texture Manager: Lệnh này đưa ra một hộp thoại, trên đó chúng ta có thể thêm hoặc xóa đi bộ kết cấu WAD trong thanh texture. Trên đó có các tùy chọn sau: New WAD: Tạo ra một tập tin WAD rỗng, để chúng ta có thể thêm các kết cấu mới vào thanh texture. Add WAD: Thêm một tập tin WAD vào texture. Add Folder:Thêm tất cả các tập tin WAD trong thư mục được chọn. Save WAD: Lưu tập tin WAD sau khi nó đã bị thay đổi như thêm vào hoặc bỏ đi một kết cấu nào đó. Build WAD: Tạo ra một tập tin WAD mới chứa đựng tất cả các kết cấu được sử dụng trong lúc thiết kế. Remove WAD: Xóa đi một kết cấu trên thanh kết cấu. 33 Chương 3: Game Engine – Cách sử dụng WED 2.1.6. Thực đơn View GXL Properties: Danh sách các thuộc tính của thư viện đồ họa được sử dụng trong khung nhìn 2D và 3D. Toolbars: Hiển thị hoặc ẩn đi một toolbar nào đó hoặc cửa sổ dự án. Add View: Thêm một cửa sổ khung nhìn mới ngoài 4 cửa số thiết kế đã có. Wireframe: Chọn loại biểu diễn trong cửa sổ 3D theo dạng khung dây. Solid: Chọn loại biểu diễn trong cửa sổ 3D theo dạng khối đặc. Textured: Chọn loại biểu diễn trong cửa sổ 3D theo dạng kết cấu. Goto Center: Đưa tiêu điểm của 4 cửa sổ thiết kế đến phạm vi của đối tượng đang chọn. Lock Views: Mặc định, tiêu điểm của 4 cửa sổ thiết kế nằm trên cùng một điểm trong không gian. Khi thay đổi vị trí của một khung nhìn, các khung nhìn thiết kế khác cũng sẽ tự động cập nhật vị trí của chúng tùy vào tiêu điểm mới. Lệnh Lock Views sẽ cho phép hoặc vô hiệu đặc điểm này. Khi vô hiệu, các cửa sổ thiết kế này có thể di chuyển một cách độc lập, không phụ thuộc vào nhau. Decrease View Depth: làm cho dễ dàng thấy cửa sổ thiết kế hơn, WED sẽ không hiển thị những phần của khung cảnh nằm ngoài phạm vi nào đó. Lệnh này sẽ làm giảm phạm vi tầm nhìn này. Increase View Depth: làm cho dễ dàng thấy cửa sổ thiết kế hơn, WED sẽ không hiển thị những phần của khung cảnh nằm ngoài phạm vi nào đó. Lệnh này sẽ tăng phạm vi tầm nhìn này. 2.1.6. Thực đơn help 34 Chương 3: Game Engine – Cách sử dụng WED Tutorial: mở tập tin hướng dẫn sử dụng 3D GameStudio. About WED: Thông tin về WED và phiên bản GameStudio. 2.2. Giao diện sử dụng 4 cửa sổ thiết kế hiển thị khung cảnh mà chúng ta xây dựng từ 4 khung nhìn khác nhau theo các hướng: hướng trên, sau lưng, bên cạnh và ở một góc tùy ý trong cửa sổ 3D. Theo mặc định, 4 khung nhìn có tiêu điểm nằm trên cùng một điểm trong không gian. Có thể cuộn một cửa sổ bằng cách nhấp phải và kéo rê chuột, và phóng to, thu nhỏ bằng nút lăn chuột hoặc giữ phím [SHIFT] và rê nút chuột phải. Khi di chuyển một khung nhìn trong cửa sổ WED sẽ tự động cập nhật các khung nhìn khác tùy vào vị trí của tiêu điểm mới. Chúng ta có thể khóa hoặc mở khóa khung nhìn của 4 cửa sổ bằng cách chọn Lock Views. Engine sử dụng hệ tọa độ thuận tay phải trong lúc thiết kế. Để hiểu được hệ thống này, hãy tưởng tượng về con đường đi hằng ngày. Chiều dương của trục X chỉ về hướng đông, và hướng đến cạnh bên phải trong cửa sổ khung nhìn trên. Chiều dương của trục Y chỉ về hướng bắc, và hướng lên trên trong cửa sổ khung nhìn trên. Còn trục Z thì chỉ chiều cao của khung cảnh. Chiều dương của trục Z tiến ra bên ngoài cửa sổ khung nhìn trên và hướng về phía chúng ta. Cửa sổ sau lưng quy định khung nhìn hướng đến hướng bắc, và cửa sổ bên cạnh quy định khung nhìn hướng đến hướng tây. Hệ thống lưới của cửa sổ không chia lưới tọa độ theo bội số của 10, như chúng ta mong đợi mà được chia theo bội số của 8 (có thể điều chỉnh trong Preference). Theo phương pháp này chúng ta có thể dễ dàng tạo ra một đối tượng có chính xác cùng kích thướt với kết cấu của mình, thông thường kích thướt của nó chính là bội số của 2 (như 64x64, 128x128, hoặc 256x256). Sử dụng mạng lưới mặc định và kích thướt của kết cấu, ví dụ với một kết cấu 128x128 điểm sẽ bao phủ 128 hình lập phương đơn vị mà không cần phải lợp thêm vào nữa. Kích thướt của một hộp lưới nhỏ, và số hộp nhỏ trên hộp lưới lớn, được cho biết trên thanh tiêu đề. 35 Chương 3: Game Engine – Cách sử dụng WED Trong cửa sổ 3D chỉ là một khung nhìn quay xung quanh tiêu điểm thiết kế trong không gian. Cửa sổ 3D có thể được biểu diễn ở dạng khung dây, rắn, hoặc kết cấu để xem trước. Cách biểu diễn này có thể được thay đổi bằng cách chọn thực đơn View/Render. Trong Preferences chúng ta có thể chọn giữa phần mềm biểu diễn cơ sở (GXL_BASE) và biểu diễn DirectX 8.1(GXL_DX81) cho khung nhìn 2D và khung nhìn 3D. Tất cả chúng cũng đều hiển thị màu sắc của nguồn sáng và đưa ra một khung nhìn khá thực cho toàn cảnh, tuy nhiên nó không có cùng chất lượng như sản phẩm cuối cùng. Nếu phần mềm biểu diễn là DirectX, chúng ta có thể điều chỉnh các tham số biểu diễn bằng cách nhấn phải chuột vào cửa sổ và chọn GXL_Properties. Lúc này chúng ta có thể điều chỉnh tác dụng của mặt trời, ánh sáng được biểu diễn trong cửa sổ 3D. Chúng ta có thể đưa các khung nhìn của các cửa sổ thiết kế trở về trạng thái ban đầu bằng lệnh View/Home. Cửa sổ thiết kế có giới hạn theo chiều sâu. Nhiều đối tượng của khung cảnh sẽ không được hiển thị nếu nó vượt ra khỏi phạm vi nào đó của khung nhìn. Nó rất hữu ích khi chúng ta xây dựng một level quá lớn, bởi vì nó có thể làm giảm số đối tượng được hiển thị trên màn hình. Chúng ta có thể điều chình giá trị khoảng cách trong GXL_Properties hoặc sử dụng lệnh View/Decrease ViewDepth và View/Increase View Depth. Để dọn dẹp cửa sổ thiết kế trong lúc xây dựng level, chúng ta có thể tắt việc hiện thị các thực thể trong map. Chúng ta có thể việc này bằng cách bỏ chọn tùy chọn Show Entities trong cửa sổ Preferences. 2.3. Cửa sổ dự án 2.3.1. Tab đối tượng Cửa sổ này hiển thị danh sách tất cả các đối tượng ở dạng cây trong toàn bộ level. Đối tượng được chọn được làm nổi bật trong cây danh sách. Chúng ta có thể chọn một đối tượng bằng cách nhấp double vào nó. Có thể chọn nhiều đối 36 Chương 3: Game Engine – Cách sử dụng WED tượng trong cây đối tượng bằng cách giữ phím [CTRL] trong khi nhấp vào các đối tượng. Khi nhấp phải vào một đối tượng sẽ đưa ra tùy chọn sau đây: Scope to: Giới hạn lại một nhóm trong cửa sổ 2D và 3D. Goto Object: Trung tâm của khung nhìn được chọn bao quanh đối tượng được chọn. New Group: Tạo ra một nhóm mới bên trong nhóm hiện tại. Ungroup: Đưa các đối tượng ra khỏi nhóm hiện tại. Cut/Copy/Delete: Thay đổi một đối tượng hoặc nhóm đối tượng. Render style: Chọn loại biểu diễn (khung dây, đặc, kết cấu) của đối tượng hoặc nhóm. Cũng cho phép nó không được chọn (disable) và di chuyển đối tượng, và làm cho nó không thể nhìn thấy được (invisible) trong khung nhìn. Đối tượng hoặc nhóm các đối tượng có thể được bỏ qua trong quá trình biên dịch, để tăng tốc độ biên dịch để kiểm tra các phần khác trong toàn level. Để làm điều này, chúng ta có thể nhấp chuột phải vào đối tượng và chọn Render Style->Ignore Properties: mở ra cửa sổ thuộc tính của đối tượng. 37 Chương 3: Game Engine – Cách sử dụng WED 2.3.2 Tab Views Cửa sổ này hiển thị một danh sách các khung nhìn đã được lưu, và cho phép lưu vị trí một khung nhìn nào đó bằng cách nhấp phải chuột. Add View Setting: vị trí mới của khung nhìn. Save View Settings: lưu vị trí của khung nhìn. Restore View Setting: Gọi lại vị trí của khung nhìn. Delete: Xóa vị trí của khung nhìn đang chọn. 2.3.3. Tab Texture Cửa sổ này hiển thị tất cả các kết cấu từ các tập tin kết cấu đã được xác định trong texture manager. Chúng ta có thể mở một bộ các kết cấu WAD bằng cách nhấp vào nó, thay đổi kích thướt cửa số texture bằng cách kéo rê chuột ở cạnh phía dưới, và có thể cuộn một WAD bằng thanh cuộn nằm ở phía bên phải. Nếu con chuột đang nằm trên một texture nào, thì tên của nó sẽ được hiển thị trong cửa sổ cửa sổ Texture. Khi nhấp vào một kết cấu thì hình ảnh của nó sẽ được xuất hiện ở 38 Chương 3: Game Engine – Cách sử dụng WED cửa sổ Texture, chúng ta có thể thay đổi các thuộc tính của kết cấu bằng cách nhấp phải chuột vào nó và chọn Setting. Khi nhấp double chuột vào một kết cấu, thì nó sẽ xuất hiện trong cửa sổ Object và gắn đến tất cả các mặt của khối đang chọn. Muốn thay đổi kết cấu của một khối map, đầu tiên chọn khối, rồi cuộn đến cửa sổ kết cấu, nhấp trái chuột vào kết cấu mong muốn, rồi nhấp chuột phải vào nó và chọn lệnh apply. Hộp thoại cũng cho phép thêm vào hoặc xóa đi một kết cấu trong bộ sưu tập các kết cấu WAD. Nhấp chuột phải vào một kết cấu đưa ra những tùy chọn sau đây: Apply: Gắn kết cấu vào đối tượng được chọn. Settings: Xuất hiện bảng điều chỉnh các thuộc tính của một kết cấu. Tên, độ phân giải, độ sâu của màu sắc. x – y offset: độ dịch chuyển của kết cấu. x – y scale: kích thướt của kết cấu. Angle: góc quay của kết cấu. Ambient: điều chỉnh cường độ ambient. Albedo: Albedo dưới 5 để điều chỉnh màu sương mù, trên 5 chỉ cường độ suất phân chiếu. Flags Được sử dụng trong lúc viết mã. Smooths Để điều chỉnh độ mịn của bóng. Mirror Làm cho kết cấu có độ phản chiếu lại. Shaded kết cấu vô hình Flat kết cấu phẳng 39 Chương 3: Game Engine – Cách sử dụng WED Sky kết cấu bầu trời Turbulence kết cấu chuyển động None không có kết cấu Add Teture: sẽ thêm một kết cấu PCX, BMP, TGA đến WAD, để làm kết cấu cho các bề mặt. Tên kết cấu được tạo từ các kí tự thông thường, số, gạch dưới (không chứa các kí tự đặc biệt và khoảng cách). Các trường hợp ngoài lệ: nếu một kết cấu được đặt tên bắt đầu là một kí tự ‘+’, theo sau là 1 số, thì kết cấu này là một hoạt ảnh với chu trình từ ‘+0+9’. Nếu tên bắt đầu là ‘*’ thì đây chính là một kết cấu chuyển động hỗn loạn có thể qua lại được; nếu nó bắt đầu với sky, thì nó chính là kết cấu loại bầu trời. Remove Texture: sẽ xóa kết cấu đang chọn ra khỏi WAD. Rename: đổi tên kết cấu đang chọn. Extract Texture: lưu kết cấu được chọn vào tập tin BMP hoặc PCX. Add to Bookmarks: thêm kết cấu được chọn vào tập các kết cấu được làm dấu. Save WAD: Lưu tập tin WAD. Chú ý rằng tập tin WAD trong GameStudio có định dạng khác với định dạng tập tin WAD trong Quake. Tuy nhiên, WED đều có thể truy cập cả hai loại theo cách thức riêng. Show Texture: Đưa ra nhiều cách thức hiển thị của kết cấu. 1:1 hiển thị kết cấu cùng với kích thướt gốc của nó 64x64 hiển thị kết cấu có kích thướt là 64x64 32x32 hiển thị kết cấu có kích thướt là 32x32 40 Chương 3: Game Engine – Cách sử dụng WED Texture Name hiển thị tên của kết cấu dưới ảnh của nó Texture Name Only chỉ hiển thị tên của kết cấu 2.3.4. Tab Resource Cửa sổ này hiển thị danh sách tất cả các tập tin và mã nguồn trong game. Chúng ta có thể xem mã nguồn hoặc nhấp double chuột vào một tập tin nào đó để mở nó bằng trình soạn thảo của nó. 2.4. Cửa sổ Bookmark chúng ta sử dụng cửa sổ này để đánh dấu những kết cấu trong cửa sổ texture. Để mở cửa sổ này chọn lệnh Textures/Bookmarks. Để đánh dấu một kết cấu thường sử dụng, nhấp phải chuột vào kết cấu trong cửa sổ kết cấu rồi chọn lệnh Add to Bookmarks. 2.5. Thuộc tính của khối Properties Block: Cho phép đặt tên cho một khối. Texture Lock: kết cấu được giữ thẳng hàng trong lúc di chuyển khối. Chúng không được giữ thẳng hàng trong lúc quay và thay đổi kích thướt. Passable: Được dùng khi muốn tạo ra một môi trường chất lỏng. Để cho khối có thể qua lại được và có thể thấy được bề mặt có nó từ bên trong. Invisible: Chướng ngại vật không nhìn thấy được. Chú ý rằng những khối không nhìn thấy thì không thể được dò tìm bởi lệnh trace(). Nếu muốn một 41 Chương 3: Game Engine – Cách sử dụng WED khối khối nhìn thấy nhưng có thể được dò tìm bằng lệnh trace() thì hãy sử dụng cờ none. Surface/Texture Surface: Cho phép gắn một kết cấu khác đến từng bề mặt của khối được chọn, và điều chỉnh các tham số của bề mặt này. sử dụng nút >> và nút << để chuyển đến bề mặt mong muốn. Bề mặt được chọn sẽ có màu vàng trong khung nhìn hiện tại. Để gắn một kết cấu khác đến bề mặt này, chọn một kết cấu mới trong cửa sổ kết cấu, nhấp phải chuột và chọn apply. Sử dụng X/Y offset, và X/Y scale để sửa lại cho kết cấu thẳng hàng với cạnh bề mặt nếu cần. Chúng ta có thể quan sất kết quả trong khung nhìn 3D. Điều chỉnh Angle để quay hướng của kết cấu trên bề mặt. Ô flags cho phép thay đổi các thuôc tính của bề mặt. Ambient: làm tối hoặc chiếu sáng kết cấu của khối, -100..+100 (mặc định là 0). Albedo/Fog: hệ số phản xạ của mặt trời (10..100, mặc định là 50), hệ số phản xạ của gương hoặc màu sắc (1..4). Shaded: kết cấu thông thường có bóng mờ với ánh sáng tĩnh và ánh sáng động. Flat: kết cấu phía bên ngoài, không có bóng mờ. Bóng thẳng theo góc chiếu sáng của mặt trời. Sky: bề mặt bầu trời nhiều lớp, cần thiết cho hộp bầu trời bao quanh khung cảnh. Là mặc định nếu tên kết cấu bắt đầu là ‘sky’. Turbulence: được dùng cho các chất lỏng, kết cấu này được dùng cho nước hoặc dung nham. Là mặc định nếu tên kết cấu bắt đầu là ‘*’. 42 Chương 3: Game Engine – Cách sử dụng WED None: bề mặt không được hiển thị. Flag1..7 thông thường được sử dụng trong lúc viết mã. Mirror: xác định bề mặt này có chiều ngang hoặc dọc (chỉ sử dụng trong các phiên bản chuyên nghiệp). Possition: cho phép chỉnh sửa bằng số để di chuyển, quay, kích thướt của khối. Các giá trị quay và kích thướt có thể nhập vào nhưng không được thay đổi. Object: Hiển thị vị trí cục bộ (trong một nhóm) và toàn cục của một khối. 2.6. Thuộc tính của thực thể Nhấp phải chuột vào thực thể, rồi chọn Properties để hiển thị hộp thoại này. Tùy chọn bên phải xuất hiện: Name: Mỗi thực thể có một tên duy nhất, để xác định thực thể trong lúc viết mã. Tên này được phát sinh tự động nhưng cũng có thể được sửa lại (tối đa 20 kí tự). File: Tên tập tin địa hình, map, mô hình, ảnh của thực thể (tối đa 32 kí tự). Ambient: giảm hoặc tăng độ sáng cho thực thể (-100...+100). 43 Chương 3: Game Engine – Cách sử dụng WED Flags: Transparent – làm cho thực thể trở nên trong mờ. Invisible – thực thể không nhìn thấy được, nhưng nó vẫn còn là một chướng ngại vật. Shadow – thực thể sẽ có bóng nửa trong suốt trên nền đất. Overlay – chuyển kết cấu của các mô hình hoặc map từ đen sang trong suốt. Flare – sự trong suốt của một mô hình hoặc một cảnh phụ thuộc vào độ sáng của nó. Bright – tăng độ sáng của một mô hình hoặc cảnh trong mờ, cho các ngọn lửa hoặc tia sáng. Metal – làm cho vỏ bên ngoài của thực thể có thể phản xạ lại khi bị ánh sáng mặt trời chiếu vào. Action: Hành vi của thực thể, nhận được từ mã nguồn. Flag1..Flag8: Có nhiệm vụ là làm một công tắc, phụ thuộc vào hành vi của thực thể trong mã nguồn. Chúng có thể xuất hiện dưới tên gọi khác được định nghĩa bởi khai báo define trong mã nguồn. Skill1..Skill20: chứa các giá trị kiểu số, phụ thuộc vào hành vi của thực thể trong mã nguồn. Chúng có thể xuất hiện dưới tên gọi khác được định 44 Chương 3: Game Engine – Cách sử dụng WED nghĩa bởi khai báo define trong mã nguồn. Position: Cho phép di chuyển, quay và thay đổi kích thướt của thực thể bằng cách nhập giá trị vào các ô position, angle, scale. Object: hiển thị vị trí cục bộ (trong một nhóm) và vị trí toàn cục của thực thể. 3.Thiết kế một map Không những về mặt thẩm mỹ mà còn cả những kỹ thuật phát sinh cũng phải được đề cập đến trong lúc thiết kế một level. Một cấu trúc cây BSP chứa tất cả các bề mặt mà cắt với các mặt khác. Các cạnh và đỉnh không được nhận từ WED, mà được tính toán từ các phần giao nhau. Ưu điểm của ý tưởng này là chúng ta có thể sử dụng những khối trùng lắp lên nhau - những phần giao không nhìn thấy được sẽ bị bỏ đi trong quá trình xử lý, và các cạnh và đỉnh mới sẽ tự động được thêm vào phần giao nhau. Chính vì đặc điểm này mà biên dịch sẽ nhanh hơn, bởi vì những khối bị trùng lắp, không thấy được không được biên dịch (những engine khác sẽ biên dịch tất cả các khối giao với nhau). Khuyết điểm của ý tưởng này chính là khi các đỉnh tạo ra một góc quá nhỏ dẫn đến sự chênh lệch vị trí giữa các đỉnh là rất lớn. Nếu bề mặt tiếp xúc hoặc giao nhau tạo ra một góc rất nhỏ, sai lệch khoảng 1/100 độ có thể cách vị trí các cạnh khoảng một vài pixel thì có thể thấy được trong level. Với đặc điểm này, chúng ta không nên sử dụng những khối quá hẹp, quá dài, hoặc quá nhọn. Không nên tạo ra những khối có cạnh nhỏ hơn 2 quants. Hãy thiết kế các map có bề mặt ít nhất như có thể, và sử dụng những khối dày như có thể. Đôi khi chúng ta không thể không sử dụng những bề mặt có góc quá nhỏ, những vẫn có một cách thiết kế tốt và xấu để thiết kế những bề mặt này. Ví dụ, khi thiết kế một đoạn đường dốc như thế này: 45 Chương 3: Game Engine – Cách sử dụng WED Thiết kế tồi: sử dụng khối quá mỏng, góc chênh lệch quá nhỏ. Và các chỗ nối sẽ có thể giống như là những lỗ hổng. Thiết kế tốt: sử dụng 3 khối với 15 bề mặt thay vì 5 khối với 20 bề mặt, và sự sai lệch của một góc, khi xảy ra cũng không nhìn thấy được. 4. Thực thể Thực thể là loại tập tin ngoài nằm ở thư mục work hoặc trong các thư mục con của nó. Có 4 loại thực thể có thể đưa vào WED. 4.1. Thực thể mô hình Một mô hình là một đối tượng 3D có thể chuyển động, được lưu trữ trong tập tin ngoài MDL. Nó bao gồm một mạng lưới 3D với vỏ bao rất mịn. Mô hình thực thể thường dùng là các đối tượng nhỏ có thể chuyển động: diễn viên, quái vật hoặc giống như vậy. Chúng có thể được tạo ra bằng cách sử dụng 46 Chương 3: Game Engine – Cách sử dụng WED chương trình thiết kế mô hình, như MED, là một thành phần của 3D gameStudio. Hầu hết tất cả các chương trình thiết kế mô hình, kể cả MED, đều có thể hiểu các định dạng 3D khác như 3DS, X, hoặc MD2 và chuyển nó thành mô hình MDL. Vì thế nếu muốn đưa các đối tượng, cảnh được tạo ra bởi một chương trình khác, như Truespace®, Maya® hoặc 3D Studio MAX®. Với các mô hình nhận được từ các chương trình như MAX hoặc MAYA có thể được tải từ trang web GameStudio. 4.2 Thực thể Sprite Một sprite là một hình phẳng 2 chiều, nó giống như là một hình vẽ trên một bức tường, hoặc luôn luôn đối mặt với camera nếu cả 3 góc của nó đều là 0. Nó được lưu trữ trong các tập tin ngoài theo các định dạng PCX, BMP, TGA và có thể được tạo ra bằng các chương trình vẽ hình chuẩn, như PaintShop Pro hoặc Adobe Photoshop. Loại tập tin TGA có chứa kênh alpha có thể đưa ra được giá trị trong suốt trong từng điểm ảnh. Thực thể sprite được biên dịch nhanh hơn các thực thể map hoặc thực thể mô hình, và rất thích hợp để sử dụng để tạo ra các vụ nổ, nguồn sáng, ngọn lửa hoặc như thứ tương tự như vậy. Nếu không muốn một thực thể luôn luôn di chuyển theo camera, thì cần thiết lập các góc của nó khác 0, như 0.1 chẳng hạn. Với các sprite có thể chuyển động, cất tất cả các khung chuyển động liên tục trong cùng một tập tin, ví dụ như tập tin explo+7.pcx trong thư mục template. Thông thường, cần đặt 4 sprite vào một hình dạng ‘X’ để tạo ra một đối tượng giống thế giới thực như các loại cây. Một vài chương trình làm ảnh chuyển động 3D, như VoodooT không cho phép kích thướt của các sprite lớn hơn 256x256 điểm ảnh. 4.3 Thực thể Map Một thực thể map là một đối tượng 3D tĩnh, được lưu trữ trong tập tin ngoài có định dạng WMB. Thực thể map có thể được sử dụng như là các thành phần 47 Chương 3: Game Engine – Cách sử dụng WED của level như cửa, nền đất, các loại xe cộ. Bởi vì chúng chỉ là một map đã được biên dịch, vì thế chúng ta có tạo ra chúng bằng trình thiết kế WED. Thí dụ, chúng ta có thể chuyển từng map đã được làm sẵn thành một thực thể bằng cách mở nó, thực hiện BUILD với tùy chọn Map Entity, rồi chép tập tin WMB vào thư mục hiện tại. Chúng ta có thể tìm thấy các loại map đã được làm sẵn như cửa, đồ đạc, xe cộ trong thư mục con prefab. Các thực thể mô hình (model), ảnh (sprite), địa hình (terrain) đều là như bộ phận cấu thành thực thể map sẽ được đưa vào level khi thực thể map được đưa vào level. Như vậy, một nhóm thực thể có thể được định nghĩa và biên dịch thành các thực thể map. Chúng ta có thể truy cập đến các thực thể trong thực thể map bằng chỉ lệnh map_subents. 4.4. Thực thể Địa hình (terrain) Thực thể địa hình gồm nhiều kết cấu được ánh xạ vào mạng lưới hình chữ nhật. Nó được tập tin ngoài HMP (không được hỗ trợ trong tất cả các phiên bản). Giống như tên gọi thực thể địa hình có thể được sử dụng như là các thành phần lớn hoặc nhỏ của level mà không theo bất kì quy luật nào của địa hình. Địa hình không quay được. 4.5. Bóng Chỉ các thực thể mô hình mới có bóng động trên mặt đất. Tuy nhiên, nếu một thực thể không di chuyển mà không hoạt động, như cây, chúng ta nên chọn loại bóng cho nó là bóng tĩnh. Bóng tĩnh thì mịn hơn và được biên dịch nhanh hơn, và được hỗ trợ trong tất cả các phiên bản. Tạo ra một khối có kích thướt và hình dạng gần giống như thực thể, đặt vào vị trí của thực thể, bật cờ detail và chọn chế độ kết cấu cho tất cả các mặt của nó là None để cho nó không thấy được. Khối sẽ tạo ra một bóng tĩnh trên nền đất và nó các tác dụng như một 48 Chương 3: Game Engine – Cách sử dụng WED chướng ngại vật, nhưng không thấy được. Có thể bật cờ passable để cho sự dò tìm thực thể được nhanh hơn. 4.5. Thuộc tính trong suốt Thực thể có thể trở nên trong suốt nếu bật cờ transparent hoặc cờ flare, hoặc sử dụng ảnh có định dạng với kênh alpha cho các thực thể sprite hoặc vỏ bao bên ngoài của thực thể. 49 Chương 3: Game Engine – Cách sử dụng MED II. Cách sử dụng MED MED được sử dụng để tạo hoặc chuyển đổi định dạng các mô hình hoặc các địa hình 3D trong 3D GameStudio. Giao diện rất dễ sử dụng để tạo ra các mô hình 3D và vỏ bao bên ngoài đơn giản. 1. Trình thiết kế Dưới đây là giao diện của MED: Chúng ta thấy rằng 4 khung nhìn của MED rất giống 4 khung nhìn của WED. Tuy nhiên, vì chức năng và nhiệm vụ của nó là thiết kế một mô hình chuyển động, khác so với WED là thiết kế level, nên tương tác với người dùng là khác. Khi kéo rê vào các thanh trong các khung nhìn thì sự cân xứng của các khung nhìn sẽ bị thay đổi. Khi nhấp phải vào khung nhìn 3D và chọn GXL Properties, thì thuộc tính của nó như độ sáng và phạm vi khung nhìn có thể được thay đổi. 1.1. Các thực đơn 1.1.1. Thực đơn File Với thực đơn file, chúng ta có thể lưu, gọi lại, nhập hoặc xuất các tập tin từ MED. 50 Chương 3: Game Engine – Cách sử dụng MED New Model: Tạo ra một mô hình mới. New Terrain:Tạo ra một địa hình mới. Open Save Lưu mô hình hoặc địa hình với đến tập tin hiện trong các định dạng MDL5, MDL7, HMP của GameStudio. Định dạng MDL không giống như định dạng mô hình có cung phần mở rộng trong QuakeT. Khung xương chỉ được hỗ trợ trong định dạng MDL7. Save As: Lưu với tên mới. Merge: Cộng mô hình khác vào mô hình hiện tại, vì thế kết quả là sự kết hợp của hai mô hình. Choose Palette: Gọi một bảng màu cho các mô hình mà vỏ bọc có kết cấu kiểu 8 bit. Bảng màu có thể nhận được từ các định dạng như BMP, PCX, PAL, LMP hoặc RAW. Import / Append Vertices: Nhập một mô hình từ các định dạng .ASC hoặc .3DS. Lệnh này sẽ nhập các mô hình được tạo ra từng các ứng dụng 3D như 3D Studio. Cả hình dạng và kết cấu của các mô hình đều được đưa vào. Muốn đưa một mô hình đã được tạo ra bởi các ứng dụng khác, đầu tiên cần đưa khung vào trước, rồi sử dụng tùy chọn "Import Append Frames" giữ nguyên các khung. Khi nhập một tập tin 3DS quá phức tạp, chúng ta nên chọn tùy chọn Model Properties / Fast Prec trước khi lưu nó. Sau khi nhập theo phương pháp này, các bản vẽ và kết cấu có thể được tạo ra bằng trình thiết kế skin. Import / Append Frames: Đưa vào một vài khung chuyển động của một mô hình. Để cho các khung theo đúng thứ tự, đầu tiên, chọn khung cuối cùng, rồi 51 Chương 3: Game Engine – Cách sử dụng MED giữ phím SHIFT, rồi chọn tập tin đầu tiên trong nhóm muốn đưa vào, rồi nhấn OK. Import / Frame Names From Text : Lệnh này nhập các khung có tên trong tập tin kiểu text. Để tạo ra một tập tin kiểu text, đặt tên một khung trên một dòng không có khoảng trống. Export / Q1 MDL: Xuất mô hình ra định dạng Quake 1 MDL. Export / MD2: Xuất mô hình ra định dạng Quake 2 MDL, là định dạng được sử dụng rất phổ biến và là phần thứ 3 của trình thiết kế mô hình. Sẽ xuất hiện một hộp thoại lưu các tập tin có định dạng .MD2 này trong đó cần nhập đường dẫn để lưu tập tin skin của mô hình. Export / AQM: Xuất mô hình ra định dạng .AQM, là định dạng được sử dụng trong trình thiết kế mô hình Quake 2. Export / Frame to ASC: Xuất khung hiện thời ra định dạng .ASC. Export / Model to ASC: Xuất mô hình hiện thời ra nhiều định dạng .ASC tùy thuộc vào số khung của nó. Export / Frame to 3DS: Xuất mô hình hiện thời ra định dạng .3DS (không có skin). Export / Model to 3DS: Xuất mô hình hiện thời ra nhiều định dạng .3DS tùy thuộc vào số khung của nó. History: Chỉ 8 tập tin đã mở. Exit: Thoát khỏi chương trình. 52 Chương 3: Game Engine – Cách sử dụng MED Open: Mở hoặc đưa một mô hình hoặc địa hình. Danh sách các tập tin này đưa ra nhiều định dạng khác nhau. Chúng ta có thể mở các định dạng MDL, MD2, WMP hoặc X đối với các mô hình, và các định dạng PCX, BMP hoặc HMP đối với các địa hình. Khi nhập một định dạng nào đó thì một cửa sổ sẽ hiện ra để chúng ta có thể chọn các thuộc tính của cần đưa vào. Khi nhập một mô hình phức tạp có định dạng là MD2 hoặc X thì tùy chọn Model Properties/Fast Prec nên được chọn trước khi lưu chúng. Một bản đồ địa hình có định dạng PCX, BMP hoặc RAW có thể được tạo ra từ các chương trình vẽ phong cảnh hoặc địa hình. Các định dạng bitmap sẽ được nhập vào và chuyển thành mô hình theo định dạng HMP. Chúng ta có thể xác định giá trị tốt nhất của độ phân giải của một mắt lưới theo chiều ngang hoặc chiều dọc theo mỗi hướng từ 30 đến 100 đỉnh. Một vài hướng có thể được phát sinh tự động. 1.1.2. Thực đơn Edit 53 Chương 3: Game Engine – Cách sử dụng MED Undo: Quay trở lại hành động vừa mới thực hiện. Redo: Quay trở lại hành động Undo vừa mới thực hiện. Copy Selected: Lưu phần được chọn vào clipboard. Paste: Dán dữ liệu đã được sao chép vào mô hình. Hộp thoại đưa ra các tùy chọn cho phép thay thế các vị trí của các đỉnh trong mô hình và thêm vào mô hình như đó là các đỉnh mới. Việc thay các đỉnh cũng có một nhân tố pha trộn, vì thế khi chép dữ liệu từ một khung và dán vào khung khác, chúng ta có thể pha trộn giữa hai bộ dữ liệu. Paste range: Dán dữ liệu đã được sao chép vào một phần nào đó của khung, tùy vào yếu tố pha trộn ở trên. Change Frame Name: Đổi tên khung hiện tại. Thông thường tên khung nên bao gồm một từ mô tả và 1 số, như “walk1”, “walk2”. Tên khung xác định các khung này có chức năng là đi bộ, tấn công, chết Các hoạt động này sẽ được gắn vào sau. Goto Frame: Nhảy đến một khung xác định, chọn khung mà bạn muốn đến trong danh sách và nhấp OK. Add New Frame: Thêm một khung mới. Hộp thoại sẽ đưa ra những tùy chọn là đặt khung mới sau khung cuối cùng, trước khung đầu tiên, hoặc sau một khung nào đó. Chúng ta cũng có thể nhập vào tên của một khung. Delete Current Frame: Xóa khung hiện tại, xuất hiện hộp thoại xác nhận quyế...rotate)((long)target,(long)&(ent->pan)); Có một ít khác so với việc thường gọi một hàm trong C++. Tuy nhiên, nó khá dễ hiểu: Chúng ta có một con trỏ hàm, vì thế để gọi nó, chúng ta phải sử dụng (*). Và đối số được đưa luôn luôn là kiểu fixed hoặc long. Chúng ta đã ép kiểu nó thành kiểu long thay cho kiểu fixed, đó chỉ là sự thỏa thuận rằng chúng ta đang đưa một tham số con trỏ. Tất cả các chỉ lệnh vector đều đòi hỏi một con trỏ các số fixed. Nếu chỉ lệnh không đòi hỏi một vector hoặc một giá trị mà là cái gì đó phức tạp hơn như là một thực thể. Chúng ta chỉ cần đưa một con trỏ A4_ENTITY được ép sang kiểu long. Nhưng nếu nó đòi hỏi một chuỗi thì sao – chúng ta sẽ sử dụng con trỏ kiểu A4_STRING hoặc chỉ cần đưa char*? Chúng ta phải sử dụng A4_STRING. Trong thí dụ ackdll.cpp, chúng ta có thể tìm thấy cách để đưa một hằng chuỗi vào một chỉ lệnh trong C-Script. long pSTRING(char* chars) { static A4_STRING tempstring; static char tempchar[256]; strncpy(tempchar,chars,255); tempstring.chars = tempchar; tempstring.link.index = 4<<24; 85 Chương 3: Game Engine – Cách viết một DLL return (long)&tempstring; } //thí dụ được ra một chuỗi để tạo một thực thể DLLFUNC fixed create_warlock(long vec_pos) { static wdlfunc3 ent_create = (wdlfunc3)a5dll_getwdlfunc("ent_create"); return (*ent_create)(pSTRING("warlock.mdl"),vec_pos,0); } Một vài chỉ lệnh không thể được gọi trực tiếp từ một DLL. Tuy nhiên, chúng có thể được thi hành trực tiếp bằng cách gọi một script thực hiện những chỉ lệnh đó. Script có thể được gọi từ DLL bằng hàm sau: long a5dll_getscript(char *name); Hàm này trả về địa chỉ của một hàm script được định nghĩa bởi người dùng có tên được đưa. Nó có thể được dùng để gọi một hàm hoặc hành động trong C- Script được định nghĩa bởi người dùng bên trong một DLL. Nếu hàm không tìm thấy, NULL sẽ được trả về và phát sinh ra một lỗi. fixed a5dll_callscript(long script,long p1=0,long p2=0,long p3=0,long p4=0); fixed a5dll_callname(char *name,long p1=0,long p2=0,long p3=0,long p4=0); Hàm này gọi một hàm script được định nghĩa bởi người dùng có địa chỉ hoặc tên được đưa. 4 tham số được đưa có thể là một số kiểu fixed, mảng, hoặc một con trỏ đến một đối tượng C-Script. Nếu hàm yêu cầu ít hơn 4 tham số, các tham số còn lại đặt là 0. Thí dụ một hàm DLL gọi một hàm đã được định nghĩa trong C-Script: DLLFUNC fixed WDLBeep(fixed value) { // lấy con trỏ hàm static long beeptwice = a5dll_getscript("beeptwice"); // gọi hàm 86 Chương 3: Game Engine – Cách viết một DLL return a5dll_callscript(beeptwice,0,0,0,0); } Hàm DLL này sẽ yêu cầu hàm trong C-Script sau sẽ được gọi: function beeptwice() { beep; beep; } 4. Lập trình một game trong C++ Sử dụng đối tượng A4_ENTITY, một DLL có thể thực thi một hàm AI phức tạp, mà nó sẽ rất khó để viết trong C-Script. Ngay cả toàn bộ game đều có thể được viết trong một DLL. Thí dụ sau chỉ ra cách thay đổi tham số thực thể trong một hàm DLL. // lăn tròn thực thể được đưa một góc 180 độ DLLFUNC fixed FlipUpsideDown(long entity) { if (!entity) return 0; // lấy con trỏ đến thực thể được đưa A4_ENTITY *ent = (A4_ENTITY *)entity; // gán góc lăn tròn của thực thể đến 180 độ ent->roll = FLOAT2FIX(180); return 0; } Hàm này sẽ được gọi trong C-Script bằng hàm FlipUpsideDown(my). Để điều khiển toàn bộ thực thể trong một DLL, giả sử chúng ta viết toàn bộ một game bằng ngôn ngữ C++, một hành động giả trong C-Script có thể được gắn vào thực thể như sau: var appdll_handle; dllfunction dll_entmain(entity); dllfunction dll_entevent(entity); function main() { // Mở DLL appdll_handle = dll_open("myapp.dll"); ... } action myent_event { dll_handle = appdll_handle; 87 Chương 3: Game Engine – Cách viết một DLL dll_entevent(my); // hàm DLL này điều khiển tất cả các sự kiện của thực thể } action myentity { my.event = myent_event; while(1) { dll_handle = appdll_handle; dll_entmain(my); // hàm DLL này điều khiển thực thể wait(1); } } 88 Chương 4: Cài đặt 89 Chương 4 CÀI ĐẶT Game được tạo thành từ các thành phần: các khối và các thực thể. Các khối sẽ được kết hợp lại trong lúc thiết kế bằng WED để tạo ra một khung cảnh môi trường tĩnh trong game. Các thực thể: sprite (núi, mặt trời, mây), mô hình (bao gồm cây trồng, xe của người chơi và các xe tự điều khiển), terrain (tạo ra một địa hình có hình dạng phức tạp). Các thành phần tĩnh hoặc không cần xử lý hoặc đòi hỏi xử lý rất ít trong lúc viết mã. Do đó lúc cài đặc chủ yếu tập trung vào hai đối tượng quan trọng là chiếc xe do người chơi khiển khiển và những chiếc xe tự chuyển động theo một hướng nào đó. I. Cài đặt cho người chơi 1. Chuyển động vật lý a. Gia tốc, quán tính và lực ma sát Giả định rằng, người chơi di chuyển thẳng về phía trước, quãng đường mà nó đi được tăng lên theo vận tốc và thời gian: ds=v*dt v là tốc độ đo bằng quants (khoảng 1 inch) trên tick(khoảng 1/16s). ds quãng đường đi được đo bằng quants. dt thời gian để người chơi đi được quãng đường ds, do bằng tick. Nếu muốn thay đổi vận tốc của người chơi, chúng ta cần phải tác dụng một lực lên người chơi, lực càng lớn làm cho vận tốc người chơi thay đổi càng Chương 4: Cài đặt 90 nhanh. Theo vật lý học, thì khi một vật thay đổi vận tốc, thì nó sẽ bị một sự kháng cự nào đó. Đó chính là quán tính, phụ thuộc vào khối lượng m của một vật. Với cùng một lực tác dụng, thì vật có khối lượng càng lớn có sự thay đổi vận tốc càng nhỏ. Ta đã biết được các công thức: a - gia tốc – sự thay đổi của vận tốc trên 1 tick f - lực tác dụng m - khối lượng của vật. Chúng ta sẽ xem xét 3 loại lực tác dụng. - Lực đẩy (propelling force): Lực này dùng để thay đổi vận tốc người chơi, được tạo ra khi ấn phím. Trong một game đơn giản, lực này sẽ tùy thuộc vào khối lượng của người chơi. Đối với người chơi có khối lượng càng lớn thì lực tác dụng đến nó càng lớn. p=p*m - Lực thứ hai là lực hấp dẫn, có thể là một lực hút người chơi đến một hướng nào đó, hoặc là trọng lực của trái đất. Lực hấp dẫn thay đổi từ nơi này đến nơi khác. Trong game, độ lớn của lực này cũng tùy thuộc vào khối lượng của người chơi. Điều này rất dễ thấy trong trường hợp lực này là trọng lực: d=d*m - Lực thứ 3 tác dụng lên người chơi là lực ma sát. Lực này làm cản trở hoạt động của người chơi, liên tục làm giảm tốc độ của anh ta. Không giống như vật lý học, là lực hãm bao gồm lực ma sát và những thành phần suy giảm, chúng ta sử dụng lực giả tạo, nó sẽ tăng với khối lượng người chơi (sức ép lên mặt đất) và tốc độ: r= - f*m*v r: lực ma sát. dv = a*dt a=f/m Chương 4: Cài đặt 91 f: hệ số ma sát. v: vận tốc. m: khối lượng. Hệ số của lực ma sát tùy thuộc vào bề mặt mà người chơi đang di chuyển trên đó: tuyết có hệ số ma sát thấp hơn đá. Trong không trung, hệ số ma sát hầu như bằng 0. Dấu trừ chỉ rằng lực lực có chiều ngược hướng với vận tốc của người chơi. Khối lượng của người chơi là m, cũng là một thành phần trong phương trình, bởi vì trong game, nếu trọng lượng của người chơi lớn thì lực ma sát ép vào bề mặt càng lớn. Như vậy, 3 lực: lực đẩy f, lực hấp dẫn d và lực giảm tốc độ r đều làm thay đổi vận tốc của người chơi. dv phải được thêm vào vận tốc sau mỗi trạng thái (frame). p, d và f là các lực đẩy, lực hấp dẫn, lực ma sát. dt là khoảng thời gian mà vận tốc thay đổi - ở đây nó là thời giữa hai trang thái, bởi vì chúng ta đang tính vận tốc mới sau mỗi trạng thái. Chúng ta sẽ làm cho tất cả các lực cân xứng với trọng lượng, vì thế yếu tố khối lượng sẽ không còn cần thiết nữa, nó không còn có tác dụng gì trong chuyển động vật lý nữa, chúng ta sẽ loại nó ra khỏi phương trình. Chúng ta sẽ viết mã nguồn cho công thức cuối cùng như sau: dv = a * dt dv = (p + d + r) / m * dt dv = (p + d - f * v) * dt Chương 4: Cài đặt 92 Lực tác dụng là 10, lực ma sát là 0.7 trong cả lúc quay và lúc di chuyển. Chúng ta sử dụng các skill (biến có sẵn của thực thể), để lưu giữ vận tốc hiện tại của thực thể, bởi vì cần biết vận tốc của người chơi ở trạng thái trước để tính toán lực tác dụng hiện tại vào người chơi. Chúng ta đã sử dụng skill14 để cất giữ vận tốc góc, và skill11 để lưu vận tốc di chuyển về phía trước. time là dt trong công thức tính quãng đường đi được, vì thế người chơi sẽ di chuyển cùng vận tốc trên mọi PC, nó hầu như độc lập với tốc độ khung! Chú ý rằng, chúng ta đã thay đổi công thức gốc, theo lý thuyết thì công thức tính sự thay đổi của vận tốc trên một chu kỳ trạng thái là: Nó sẽ được viết lại trong script như sau: var force[3]; var dist[3]; action move_me { while (1) { force.PAN = -10 * KEY_FORCE.X; // tính lực quay my.SKILL14 = TIME*force.PAN + max(1- TIME*0.7,0)*my.SKILL14; // vận tốc quay my.PAN += TIME * my.SKILL14; // quay người chơi force.X = 10 * KEY_FORCE.Y; // tính toán lực di chuyển my.SKILL11 = TIME*force.X + max(1-TIME*0.7,0)*my.SKILL11; // tính vận tốc dist.X = TIME * my.SKILL11; // quãng đường đi được dist.Y = 0; dist.Z = 0; move_mode = ignore_passable + glide; ent_MOVE(dist,nullvector); // di chuyển người chơi move_view(); // di chuyển camera theo người chơi wait(1); } } v -> v + dv v -> v + (p - f * v) * d Chương 4: Cài đặt 93 my.SKILL11 = my.skill11 + (force.X - 0.7 * my.SKILL11) * time; và được thay đổi từng bước như sau: my.SKILL11 = my.skill11 + TIME * force.X - time * 0.7 * my.SKILL11; my.SKILL11 = TIME * force.X + (1-time*0.7) * my.SKILL11; Cuối cùng cho ra một kết quả khá phức tạp: my.SKILL11 = TIME * force.X + max(1-TIME*0.7,0) * my.SKILL11; Như vậy, chúng ta đã hoàn thành script cho công thức tính vận tốc trên. Nhưng chúng ta sử dụng hàm max ở đây để làm gì. Max(a.b) so sánh hai giá trị a và b, và trả về giá trị nào lớn hơn. Khi sử dụng max(1-TIME*0.7,0), nó sẽ chỉ cho ra kế quả dương, chúng ta phải làm như vậy, bởi vì trong các máy tính có tốc độ khung quá thấp, và giá trị time quá lớn – TIME*0.7 có thể sẽ lớn hơn 1, cho ra kết quả âm. Điều này làm cho vận tốc bị đảo chiều, và người chơi sẽ di chuyển ngược ra sau. b. Rơi từ trên xuống Trong khi sự di chuyển theo chiều ngang của người chơi chủ yếu được tác dụng từ các lực do người sử dụng ấn phím, thì sự di chuyển theo chiều dọc là do tác dụng của trọng lực tác dụng vào người chơi. Nếu người chơi đang đứng ở trên mặt đất, nó sẽ không cần di chuyển theo chiều dọc. Nhưng nếu người chơi bỗng nhiên rơi vào không trung – như nếu nó tiến đến một vực thẳm, thì nó nhất định phải rơi xuống. Để xác định người chơi có ở trạng thái này hay không, cần phải xác định người chơi cách đất bao nhiêu. Chúng ta sẽ sử dụng lệnh trace: Chương 4: Cài đặt 94 Lệnh trace trả về khoảng cách đến chướng ngại vật đầu tiên mà một tia giữa 2 điểm (2 vector được đưa). Chúng ta đang sử dụng điểm trung tâm của người chơi (my.x) là điểm thứ nhất, và điều chỉnh điểm temp để nó là điểm thứ 2 nằm phía dưới người chơi khoảng 4000 quant. Bằng cách sử dụng chế độ use_box, chúng ta đang sử dụng tia truy tìm có một bề dày là vỏ bao bên ngoài người chơi, thông thường có đường kính là 32 quant – nó cũng trả về khoảng cách đến điểm dưới cùng của hộp bao bên ngoài người chơi, không phải là trung tâm action move_me { while (1) { force.PAN = -10 * KEY_FORCE.X; // tính lực quay my.SKILL14 = TIME*force.PAN + max(1-TIME*0.7,0)*my.SKILL14; // tính vận tốc quay my.PAN += TIME * my.SKILL14; // quay người chơi force.X = 10 * KEY_FORCE.Y; my.SKILL11 = TIME*force.X + max(1-TIME*0.7,0)*my.SKILL11; // tính vận tốc tiến về trước dist.X = TIME * my.SKILL11; // quãng đường đi được về phía trước dist.Y = 0; vec_set(temp,my.x); temp.z -= 4000; // một vị trí nằm dưới người chơi 4000 quants // chọn các chế độ truy tìm các thực thể và bề mặt từ vị trí của người chơi trace_mode = ignore_me+ignore_sprites+IGNORE_MODELS+USE_BOX; dist.z = -trace(my.x,temp); // trừ khoảng cách theo chiều dọc move_mode = ignore_passable + glide; ent_MOVE(dist,nullvector); // di chuyển người chơi move_view(); // di chuyển camera wait(1); } } Chương 4: Cài đặt 95 của người chơi. Nếu chúng ta xem điểm dưới cùng của hộp bao bên ngoài là chân của người chơi, thì lệnh trace sẽ tính chân người chơi đang cách mặt đất là bao nhiêu. Nếu chân của nó đang ở dưới nền đất, lệnh trace sẽ trả về kết quả âm. Vì thế dist.z được gán bằng phủ định của khoảng cách trả về từ lệnh trace. Theo phương pháp này, người chơi có thể đi bộ giữa những vùng có độ cao khác nhau, như lên hoặc xuống cầu thang. Chú ý để cho đơn giản chúng ta dùng vector khoảng cách tương đối (dist) để di chuyển người chơi theo hướng Z. Thông thường ở đây, nên sử dụng khoảng cách tương đối. Nhưng người chơi sẽ điều chỉnh đến các độ cao khác nhau ngay lập tức. Cách di chuyển này rất không tự nhiên. Để cho sự di chuyển được tự nhiên hơn, chúng ta sẽ tìm các lực tác động đến người chơi theo hướng thẳng đứng: - Khi người chơi là một chiếc máy bay thì lệnh trace trả về một giá trị lớn hơn 0 - chỉ những lực hấp dẫn và ma sát mới tác dụng lên nó. Lực hấp dẫn ở đây là trọng lực mà chúng ta đã đề cập, nó kéo người chơi xuống phía dưới. - cho đến khi người chơi tiến đến mặt đất hoặc chìm vào nó - lệnh trace sẽ trả về một giá trí nhỏ hơn hoặc bằng 0. Trong trường hợp này thì lực đàn hồi sẽ tác động. Đây là loại lực mới, nó càng mạnh khi người chơi càng chìm sâu trong nền đất. Nó tạo ra cho người chơi một gia tốc hướng lên. Hơn nữa gia tốc của người chơi sẽ tăng đáng kể khi người chơi tiến vào mặt đất. Sử dụng kĩ thuật này, và tùy theo trung tâm của thực thể người chơi, mà chân của thực thể có thể đi xuyên qua bề mặt rắn, không thể qua được. Trong thế giới thực loại bề mặt này dĩ nhiên không bao giờ đi qua được, nhưng với đầu gối của người chơi, nó sẽ tạo ra cùng tác dụng. Vì thế sự xuất hiện của lực đàn hồi là kết quả từ việc nhún của đầu gối - nếu người chơi là một động cơ – thì đó là bộ giảm xóc. Cũng tương tự chúng ta có thể giải thích sự tăng lên của Chương 4: Cài đặt 96 lực ma sát trên nền đất bằng lực ma sát được tạo ra bởi lực nhún của người chơi hoặc bộ giảm xóc của xe. var friction; action move_me { while (1) { force.PAN = -10 * KEY_FORCE.X; // tính lực quay my.SKILL14 = TIME*force.PAN + max(1-TIME*0.7,0)*my.SKILL14; // vận tốc quay my.PAN += TIME * my.SKILL14; // quay người chơi vec_set(temp,my.x); temp.z -= 4000; // một vị trí nằm dưới người chơi 4000 quants // chọn các chế độ truy tìm các thực thể và bề mặt từ vị trí của người chơi trace_mode = ignore_me+ignore_sprites+IGNORE_MODELS+USE_BOX; result = trace(my.x,temp); // subtract vertical distance to ground if (RESULT > 5) // có phải đang ở trong không gian? { force.X = 0; // không có lực đẩy force.Y = 0; force.Z = -5; // trọng lực friction = 0.1; // lực ma sát của không khí } Chương 4: Cài đặt 97 Bằng cách sử dụng lệnh if với kết quả truy tìm được, chúng ta có thể xác định người chơi đang ở trong không khí hoặc cách mặt đất 5 quant. Trong trường hợp đầu tiên, các lực được tạo ra từ bàn phím sẽ không có tác dụng, mà người chơi sẽ rơi xuống dưới tác dụng của trọng lực. Trong trường hợp sau, xuất hiện lực đàn hồi tương ứng với độ sâu khi thực thể chìm vào mặt đất, sẽ đẩy người chơi ra khỏi mặt đất. Chúng ta đang sử dụng nhiều skill của thực thể, skill13 sẽ lưu vận tốc theo phương thẳng đứng hiện tại của thực thể. 2. Cách di chuyển camera theo người chơi 2.1. Tầm nhìn của người thứ nhất else // đang ở trên mặt đất { force.X = 10 * KEY_FORCE.Y; // lực quay force.Y = 0; force.Z = -0.5 * RESULT; // lực nẩy friction = 0.7; // lực ma sát dưới nền đất } my.SKILL11 = TIME*force.X + max(1-TIME*friction,0)*my.SKILL11; // tính vận tốc tiến về phía trước my.SKILL13 = TIME*force.Z + max(1-TIME*friction,0)*my.SKILL13; // tính vận tốc theo phương thẳng đứng dist.X = TIME * my.SKILL11; // quãng đường tiến về phía trước dist.y = 0; dist.Z = TIME * my.SKILL13; // quãng đường rơi xuống move_mode = ignore_passable + glide; ent_MOVE(dist,nullvector); // di chuyển người chơi move_view(); // di chuyển camera theo wait(1); } } Chương 4: Cài đặt 98 Hãy đặt viết mã nguồn như sau: Và gọi hàm init_camera trong hàm main sau khi gọi hàm level_load. Lưu và chạy ứng dụng. Khi đó camera sẽ di chuyển theo người chơi. Chúng ta đã định nghĩa một khung nhìn mới. Hãy tượng tượng một khung nhìn trong game. Nó chỉ là một cửa sổ. Chúng ta có thể xác định vị trí và kích thướt của cửa sổ bằng cách điều chỉnh các thuộc tính pos_x, pos_y, size_x, size_y. Như trên, chúng ta đã định nghĩa, góc trên bên trái của khung nhìn trùng với góc trên bên trái của màn hình và có kích thướt của nó cũng bằng kích thướt của màn hình. view 1st_person { layer = 1; pos_x = 0; pos_y = 0; } function init_cameras() { camera.visible = off; 1st_person.size_x = screen_size.x; 1st_person.size_y = screen_size.y; 1st_person.genius = player; 1st_person.visible = on; } function update_views() { 1st_person.x = player.x; 1st_person.y = player.y; 1st_person.z = player.z; 1st_person.pan = player.pan; 1st_person.roll = player.roll; 1st_person.tilt = player.tilt; } Chương 4: Cài đặt 99 Hàm update_views, sẽ được cập nhật sau mỗi trạng thái và thay đổi tọa độ x, y, z của camera trong game. Ở đây, chúng ta thay đổi nó đến tọa độ của người chơi, vì thế làm cho camera luôn luôn ở bên trong người chơi. Đoạn mã vẫn chưa được hoàn hảo. Ví dụ, nếu camera được đặt ở điểm trung tâm của mô hình người chơi, không ở trên đầu, là nguyên nhân làm cho khung nhìn đặt quá gần nền đất. Như vậy chúng ta chưa thể nhìn lên hoặc xuống. Chúng ta định nghĩa thêm một biến ở đầu đoạn mã. var eye_height = 20; và thay vì 1st_person.z = player.z; chúng ta viết lại là: 1st_person.z = player.z + eye_height; Nó sẽ điều chỉnh camera lên cao hơn 20 quant. Nếu giá trị này chưa được tốt, có thể điều chỉnh lại trong lúc chơi game. Bây giờ, chúng ta muốn người chơi có thể nhìn lên hoặc nhìn xuống. Để thực hiện được, chúng ta cần các biến sau: var tilt_1st = 0; var cam_turnspeed = 2; var max_tilt_1st = 40; và thay đổi dòng mã: 1st_person.tilt = player.tilt; thành: 1st_person.tilt = player.tilt + tilt_1st; và thêm các hàm sau: Chương 4: Cài đặt 100 Những hàm này phải được gọi trong lúc chơi game. Ví dụ, chúng ta có thể định nghĩa như thế này: on_pgup = look_up; on_pgdn = look_down; Hãy lưu lại và chạy thử. Không tồi, nhưng chưa có tác dụng như mong muốn. Nếu ấn một phím và giữ nó, thì khung nhìn chỉ di chuyển một ít và sẽ không thay đổi nữa. Chúng ta phải ấn nó nhiều lần để khung nhìn có thể di chuyển và điều này quá chậm chạp. Chúng ta sẽ thay đổi nó như thế nào? Thay đổi định nghĩa on_pageup và on_pagedown như sau: on_pgup = handle_pageup; on_pgdn = handle_pagedown; Và định nghĩa 2 hàm sau: function look_up() { if (tilt_1st < max_tilt_1st) { tilt_1st += cam_turnspeed; } } function look_down() { if (tilt_1st > -max_tilt_1st) { tilt_1st -= cam_turnspeed; } } Chương 4: Cài đặt 101 Theo cách này các hàm của chúng ta sẽ được gọi trong mỗi trạng thái trong khi các phím này đang được ấn. Nếu camera quay quá nhanh hoặc quá chậm, có thể điều chỉnh giá trị cam_turnspeed. Nếu phạm vi của khung nhìn quá nhỏ và để người chơi có thể thay đổi góc nhìn nhiều hơn, hãy thay đổi biến max_tilt_1st. Giá trị 90 ở đây có nghĩa là: người chơi có thể nhìn thẳng lên hoặc xuống. Giá trị trên 90 tức là người chơi có thể nhìn ngược ra sau. 2.2 Quay tự do tầm nhìn của người thứ 3 Bây giờ chúng ta muốn tạo ra một khung nhìn có thể quay của người thứ 3. Có hai cách thực hiện: cách thứ nhất là tạo ra một camera ở bên ngoài người chơi và không quay, ngay cả khi nó đi, luôn luôn đối diện với nó từ một hướng nào đó. Cách thứ 2 là tạo ra một camera có thể rẽ khi người chơi rẽ, vì thế nó sẽ luôn nằm ở đằng sau người chơi (hoặc trước, hoặc bên cạnh ). Chúng ta sẽ làm cho camera này có thể rẽ và phóng to thu nho tự do. Để bắt đầu, chúng ta sẽ tạo ra một khung nhìn của người thứ 3 luôn luôn đối mặt với function handle_pageup() { while (key_pgup) { look_up(); wait(1); } } function handle_pagedown() { while (key_pgdn) { look_down(); wait(1); } } Chương 4: Cài đặt 102 người chơi từ một hướng và những thay đổi khi muốn khung nhìn quay cùng với thực thể. Định nghĩa khung nhìn thứ 2 như sau: Chúng ta chưa làm cho nó có thể nhìn thấy được. Thay vì, chúng ta sẽ có thể thay đổi camera trong lúc chơi game. Chúng ta sẽ định nghĩa thủ tục chuyển đổi camera ngay bây giờ: view 3rd_person { layer = 1; pos_x = 0; pos_y = 0; } Thêm dòng sau vào bên trong hàm "init_cameras": ... 3rd_person.size_x = screen_size.x; 3rd_person.size_y = screen_size.y; ... var cam_mode = 0; // 0 cho người thứ nhất, 1 cho người thứ 3 function toggle_cams() { if (cam_mode == 0) { // Thay đổi đến người thứ 3 1st_person.visible = off; 3rd_person.visible = on; cam_mode = 1; } else { // thay đổi đến người thứ nhất 3rd_person.visible = off; 1st_person.visible = on; cam_mode = 0; } } on f8 = toggle cams; Chương 4: Cài đặt 103 Như vậy, bằng cách nhấn f8 ta có thể chuyển đổi giữa các khung nhìn. Tuy nhiên, nó chưa có tác dụng, bởi vì các tọa độ x, y, z của người thứ 3 chưa được định nghĩa. Chúng ta sẽ định nghĩa ngay giờ bằng cách thay đổi hàm "update_views". Nhưng chúng ta sẽ định nghĩa một camera quay quanh người chơi như thế nào? Nó nên nằm trên cùng một mặt phẳng, vì thế giá trị z là giống nhau. Nhưng chúng ta sẽ tính giá trị x và y như thế nào? Chúng ta cần một chút toán học. Tưởng tượng người chơi được quan sát từ phía trên. Cách tốt nhất là lấy một tờ báo và đặt một điểm trên nó, ở một nơi nào đó, để chỉ ra vị trí của người chơi được thấy từ phía trên. Vẽ một đường tròn xung quanh điểm này. Đây là vòng tròn mà camera sẽ di chuyển trên đó. Vòng tròn này có một bán kính nào đó. Giả sử trên vòng tròn có một điểm là điểm gốc, khi đó chúng ta có thể xác định một điểm P trên vòng tròn bằng một cung giữa đường thẳng vẽ từ gốc đến tâm và từ P đến tâm của đường tròn. Như vậy, khi có khoảng cách đến người chơi (bán kính của đường tròn) và một góc trong mặt phẳng thì vị trí của camera sẽ được xác định. Chương 4: Cài đặt 104 Lưu mã nguồn và chạy nó. Chọn f8 để chuyển đổi giữa các khung nhìn. Nên xem người chơi trong khung nhìn của người thứ 3. Khi di chuyển, camera sẽ luôn luôn di chuyển cùng khoảng cách với người chơi, và sẽ không thay đổi vị trí khi người chơi rẽ. Nếu thay đổi giá trị của biến dist_planar thì camera sẽ tiến lại gần hoặc lùi ra xa. Nếu thay đổi góc cam_angle thì nó sẽ quay xung quanh người chơi, và luôn luôn đối diện với người chơi. Tuy nhiên vẫn còn vấn đề khi người chơi ở gần các bức tường. Camera sẽ thường xuyên đi xuyên qua các bức tường, và các chướng ngại vật sẽ chắn tầm nhìn của người chơi. Chúng ta sẽ giải quyết vấn đề này trong phần sau. Bây giờ chúng ta sẽ thay đổi mã nguồn một ítchúng ta muốn di chuyển camera lên phía trên nhưng vẫn đối diện với người chơi. Và cũng cần phải giữ cùng var dist_planar = 300; // khoảng cách đến người chơi var cam_angle = 0; function update_views() { if (cam_mode == 0) { 1st_person.x = player.x; 1st_person.y = player.y; 1st_person.z = player.z + eye_height; 1st_person.pan = player.pan; 1st_person.roll = player.roll; 1st_person.tilt = player.tilt + tilt_1st; } else { 3rd_person.x = player.x - cos (cam_angle) * dist_planar; 3rd_person.y = player.y - sin (cam_angle) * dist_planar; 3rd_person.z = player.z; 3rd_person.pan = cam_angle; 3rd_person.roll = 0; 3rd_person.tilt = 0; } } Chương 4: Cài đặt 105 khoảng cách đến người chơi, vì thế sự di chuyển không còn theo đường tròn nữa mà theo hình cầu. Chúng ta sẽ thực hiện điều này như thế nào? Hãy tưởng tượng người chơi được nhìn từ bên cạnh. Nếu camera nằm trên mặt phẳng XY của người chơi. Hãy vẽ một đường thẳng từ nó đến người chơi, chúng ta sẽ nhận được một góc giữa mặt phẳng XY và đường này. Góc này sẽ xác định chính xác vị trí của người chơi. Hình sau đây sẽ biểu diễn vị trí của camera trong trường hợp này: Lúc này chúng ta cần chỉnh lại mã nguồn như sau: Chương 4: Cài đặt 106 Bằng cách thay đổi giá trị của các biến tilt_3rd, cam_angle, dist_total, chúng ta có thể di chuyển camera tự do xung quanh người chơi. Nó sẽ được di chuyển trên một mặt cầu với bán kính có thể được thay đổi bằng cách thay đổi giá trị của biến. 2.3 Cách để cho camera tránh chạm vào tường Ý tưởng là gửi một tia từ người chơi đến vị trí mới của camera, nếu thấy có một chướng ngại vật nằm trên tia này. Khi đó, khoảng cách giữa người chơi và camera cần được thay đổi bằng khoảng cách giữa người chơi và chướng ngại vật. Thêm những dòng sau vào hàm update_views: var dist_total = 300; // thay đổi giá trị này để tiến lại gần hoặc ra xa thực thể var tilt_3rd = 0; function update_views() { ... else { dist_planar = cos (tilt_3rd) * dist_total; 3rd_person.x = player.x - cos (cam_angle) * dist_planar; 3rd_person.y = player.y - sin (cam_angle) * dist_planar; 3rd_person.z = player.z + sin (tilt_3rd) * dist_total; 3rd_person.pan = cam_angle; 3rd_person.roll = 0; 3rd_person.tilt = - tilt_3rd; } Chương 4: Cài đặt 107 Hàm này xác định vị trí của camera một cách hoàn toàn giống như cách trên, nó chỉ sử dụng một khoảng cách mới đến người chơi, đó là khoảng cách từ người chơi đến chướng ngại vật. Nó sẽ thay đổi từ từ để ngăn chặn việc camera nằm bên trong bức tường. Để đặt camera sau người chơi, chúng ta thay đổi những dòng: 3rd_person.x = player.x - cos (cam_angle) * dist_planar; 3rd_person.y = player.y - sin (cam_angle) * dist_planar; thành: function update_views() { ... 3rd_person.roll = 0; 3rd_person.tilt = - tilt_3rd; validate_view(); } ... } hàm trên sẽ được định nghĩa như sau: var dist_traced; function validate_view() { my = player; trace_mode = ignore_me + ignore_passable; dist_traced = trace (player.x, 3rd_person.x); if (dist_traced == 0) { return; } // không chạm vào bất kì chướng ngại vật nào if (dist_traced < dist_total) { dist_traced -= 5; // Di chuyển ra ngoài bức tường dist_planar = cos (tilt_3rd) * dist_traced; 3rd_person.x = player.x - cos (cam_angle) * dist_planar; 3rd_person.y = player.y - sin (cam_angle) * dist_planar; 3rd_person.z = player.z + sin (tilt_3rd) * dist_traced; } } Chương 4: Cài đặt 108 3rd_person.x = player.x - cos (cam_angle + player.pan) * dist_planar; 3rd_person.y = player.y - sin (cam_angle + player.pan) * dist_planar; chúng ta chỉ cần thêm góc quay của thực thể (player.pan) vào cam_angle. II. Xe tự động Tránh chướng ngại vật trên đường đi Giả sử người chơi muốn di chuyển từ một điểm bắt đầu đến điểm kết thúc. Tất nhiên nếu giữa nó không có chướng ngại vật nào hết thì rất đơn giản, chỉ cần cho nó di chuyển theo một đường thẳng đi qua điểm bắt đầu và điểm kết thúc. Ở đây chúng ta đặc biệt chú ý đến trường hợp: giữa 2 điểm bắt đầu và kết thúc có các chướng ngại vật: là các chiếc xe khác hoặc là các chướng ngại vật tĩnh. Hình 1 Chương 4: Cài đặt 109 Ví dụ ở đây: để người chơi di chuyển đến một vị trí nào đó ta có thể nhấp chuột đến vị trí cần người chơi cần đến: Lúc này điểm bắt đầu là vị trí của người chơi, điểm kết thúc là vị trí nút nhất của chuột. Có 8 hướng khác nhau xung quanh một người chơi, mỗi một hướng khác nhau ta xem đó là một nút. Một nút có thể có độ rộng khác nhau tùy thuộc vào chúng ta muốn chọn bao nhiêu. Hình 2 Nếu một nút chứa một chướng ngại vật thì ta xem nút đó là nút không có giá trị, sẽ không được chọn trong lúc tìm đường đến đích. Hình 3 3 4 5 kt 2 v v 1 v v bđ v V Chương 4: Cài đặt 110 Giả sử từ nút bắt đầu bđ, muốn tìm một đường đi đi đến nút cần đến (nút kt). Và các nút v là các chướng ngại vật: Ở đây, mỗi nút trung gian (như các nút 0, 1 7), sẽ chứa 2 giá trị là chi phí đường đi (waycost), và chi phí toàn bộ nút (nodecost). Mỗi nút có một nút cha, và một nút cha có 8 nút con (trong trường hợp bình thường), nằm xung quanh nút này. Giả sử một nút có chi phí đường đi là waycost, thì các nút con của nó sẽ có waycostcon=waycostcha+1; Trong đó nút bắt đầu không có nút cha và ta cho waycost của nó là 0. Ở đây ta sử dụng một heuristic, đó là khoảng cách từ nút đó đến nút đích (nút kt), ta kí hiệu là goal_dist, thì chi phí của một nút sẽ là: nodecost=waycost+goal_dist Như vậy thuật toán sẽ gồm các bước sau: Với thuật toán như vậy, trong hình 3 để tìm đường đi từ điểm bắt đầu (bd) đến điểm kết thúc (kt), ta sẽ đi qua con đường đi qua các nút 1, 2, 3, 4, 5. Bước 1: Mở nút bắt đầu Bước 2: - Chọn trong danh sách các nút mở ra một nút có nodecost nhỏ nhất. - Nếu không còn nút nào nữa thì kết thúc thuật toán. Bước 3: - Nếu nút này là nút đích thì thuật toán kết thúc. - Nếu không thì: + Tạo ra các nút con từ nút này, với điều kiện các nút con không phải là nút chứa các chướng ngại vật. + Đóng nút này lại và mở tất cả các nút con được tạo ra. Bước 4: Chương 4: Cài đặt 111 TÀI LIỆU THAM KHẢO [1] Hướng dẫn có sẵn trong chương trình 3D Game Studio. [2] Các tài liệu hướng dẫn trên trang web: www.3DGameStudio.com. [3] Bạch Hưng Khang, Hoàng Kiếm, Trí tuệ nhân tạo, các phương pháp và ứng dụng, Nhà xuất bản Khoa học và Kỹ thuật Hà Nội - 1999