Khóa luận Xây dựng hệ thống mô phỏng và thực tại ảo sử dụng ngôn ngữ wave
Tài liệu Khóa luận Xây dựng hệ thống mô phỏng và thực tại ảo sử dụng ngôn ngữ wave: 1 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ CHƯƠNG 1. Đỗ Thế Chuẩn XÂY DỰNG HỆ THỐNG MÔ PHỎNG VÀ THỰC TẠI ẢO SỬ DỤNG NGÔN NGỮ WAVE XÂY DỰNG HỆ THỐNG THỰC TẠI ẢO KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin 2 MỤC LỤC CHƯƠNG 1. GIỚI THIỆU........................................................................................... 10 1.1. Giới thiệu về mô phỏng ........................................................................................10 1.2. Công nghệ WAVE ................................................................................................11 CHƯƠNG 2. NGÔN NGỮ WAVE.............................................................................. 14 2.1. Giới thiệu về ngôn ngữ Wave ...............................................................................14 2.2. Node, Link và Không gian phân tán : Knowledge Network (KN).......................14 2.3. Tổ chức chung của ngôn ngữ Wave.................
Bạn đang xem trước 20 trang mẫu tài liệu Khóa luận Xây dựng hệ thống mô phỏng và thực tại ảo sử dụng ngôn ngữ wave, để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên
1
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
CHƯƠNG 1. Đỗ Thế Chuẩn
XÂY DỰNG HỆ THỐNG MÔ PHỎNG VÀ THỰC TẠI ẢO
SỬ DỤNG NGÔN NGỮ WAVE
XÂY DỰNG HỆ THỐNG THỰC TẠI ẢO
KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY
Ngành: Công nghệ thông tin
2
MỤC LỤC
CHƯƠNG 1. GIỚI THIỆU........................................................................................... 10
1.1. Giới thiệu về mô phỏng ........................................................................................10
1.2. Công nghệ WAVE ................................................................................................11
CHƯƠNG 2. NGÔN NGỮ WAVE.............................................................................. 14
2.1. Giới thiệu về ngôn ngữ Wave ...............................................................................14
2.2. Node, Link và Không gian phân tán : Knowledge Network (KN).......................14
2.3. Tổ chức chung của ngôn ngữ Wave......................................................................16
2.4. Cấu trúc dữ liệu cơ bản của Wave ........................................................................17
2.5. Biến Spatial và kiểu ..............................................................................................18
2.5.1. Task variables.................................................................................................18
2.5.2. Environment variables ...................................................................................18
2.6. Các hành động – ACTS ........................................................................................19
2.6.1. Control acts ....................................................................................................19
2.6.2. Fusion acts: Các phép toán hợp nhất..............................................................22
2.7. Rules – Các luật trong Wave ................................................................................23
2.8. Wave và mô hình lập trình truyền thống ..............................................................26
2.8.1. Sơ đồ luồng (SD)............................................................................................26
2.8.2. Wave và mô hình lập trình song song............................................................28
2.8.3. Wave và mô hình lập trình tuần tự.................................................................30
CHƯƠNG 3. CÁC BÀI TOÁN MÔ PHỎNG CƠ BẢN VÀ ĐỒ HỌA 2D ................ 38
3.1. Cách tạo thực địa...................................................................................................38
3.1.1. Thuật toán tạo lưới đơn hướng.......................................................................39
3.1.2. Thuật toán tạo lưới trên máy khác .................................................................40
3.1.3. Thuật toán tạo lưới đa hướng .........................................................................41
3.2. Các phép di chuyển cơ bản ...................................................................................43
3
3.2.1. Di chuyển tự do ..............................................................................................43
3.2.2. Di chuyển tránh chướng ngại vật ...................................................................44
3.2.3. Di chuyển vòng quanh chướng ngại vật.........................................................46
3.2.4. Nhìn trong không gian với độ sâu cho trước..................................................48
3.3. Các mô phỏng tương tác cơ bản ...........................................................................50
3.3.1. Đuổi bắt trong không gian..............................................................................50
3.3.2. Di chuyển cùng nhau kiểu tịnh tiến ...............................................................53
3.4. Hiển thị trong Java2D ...........................................................................................56
3.4.1. Giới thiệu về Java 2D.....................................................................................56
3.4.2. Giới thiệu một vài đối tượng đồ họa trong Java2D........................................57
3.4.3. Tương tác giữa chương trình hiển thị và Wave .............................................62
3.4.4. Tạo lưới ..........................................................................................................64
3.4.5. Tạo chướng ngại vật.......................................................................................69
3.4.6. Di chuyển .......................................................................................................71
CHƯƠNG 4. CÁC BÀI TOÁN MÔ PHỎNG PHỨC TẠP......................................... 75
4.1. Bài toán “Hồng cầu, Bạch cầu, Virus” .................................................................75
4.1.1. Mô tả chung....................................................................................................75
4.1.2. Hồng cầu ........................................................................................................75
4.1.3. Bạch cầu .........................................................................................................76
4.1.4. Virus ...............................................................................................................77
4.2. Bài toán “Rầy nâu” ...............................................................................................79
4.2.1. Mô tả chung....................................................................................................79
4.2.2. Chi tiết bài toán ..............................................................................................83
CHƯƠNG 5. 3D VÀ THỰC TẠI ẢO.......................................................................... 87
5.1. Giới thiệu công nghệ 3D.......................................................................................87
5.1.1. Công nghệ 3D ................................................................................................87
5.1.2. Giới thiệu về Java 3D.....................................................................................88
5.2. Chương trình GnuPlot...........................................................................................88
4
5.3. Ngôn ngữ VRML..................................................................................................90
5.3.1. Khái niệm VRML và các phiên bản của VRML ...........................................90
5.3.2. Ngôn ngữ VRML ...........................................................................................92
5.4. Sử dụng Wave và GnuPlot....................................................................................94
5.4.1. Giới thiệu chung.............................................................................................94
5.4.2. Đọc file và tạo KN .........................................................................................95
5.4.3. Cập nhật dữ liệu .............................................................................................95
5.4.4. Duyệt KN và tạo file đầu vào cho GnuPlot ...................................................95
5.5. Thực tại ảo ............................................................................................................95
5.5.1. Giới thiệu chung.............................................................................................95
5.5.2. Đọc file và tạo KN .........................................................................................96
5.5.3. Cập nhật VRML...........................................................................................103
5.5.4. Duyệt KN và tạo file VRML........................................................................104
5.5.5. Thay đổi cách nhìn .......................................................................................105
5.5.6. Hiển thị trên nhiều máy tính.........................................................................107
CHƯƠNG 6. CÀI ĐẶT VÀ THỬ NGHIỆM............................................................. 112
6.1. Cài đặt .................................................................................................................112
6.1.1. Các yêu cầu về phần cứng............................................................................112
6.1.2. Các yêu cầu về phần mềm............................................................................112
6.2. Thử nghiệm.........................................................................................................113
6.2.1. Sử dụng chương trình...................................................................................113
6.2.2. Tạo lưới thực địa ..........................................................................................115
6.2.3. Di chuyển tự do ............................................................................................116
6.2.4. Di chuyển tránh chướng ngại vật .................................................................118
6.2.5. Di chuyển vòng quanh chướng ngại vật.......................................................120
6.2.6. Di chuyển cùng nhau kiểu tịnh tiến .............................................................124
6.2.7. Hiển thị hình ảnh 3D động bằng GnuPlot....................................................124
6.2.8. Hiển thị hình ảnh 3D của tệp tin VRML......................................................126
5
6.2.9. Hiển thị hình ảnh 3D với các góc nhìn khác nhau .......................................126
6.2.10. Hiển thị hình ảnh 3D VRML trên nhiều máy...........................................128
CHƯƠNG 7. PHỤ LỤC A – WAVE CODE ............................................................. 130
7.1. Tạo lưới đơn hướng ............................................................................................130
7.2. Tạo lưới theo đa hướng.......................................................................................132
7.3. Di chuyển tự do...................................................................................................133
7.4. Di chuyển tránh chướng ngại vật ........................................................................134
7.5. Di chuyển vòng quanh chướng ngại vật .............................................................136
7.6. Nhìn trong không gian với độ sâu cho trước ......................................................138
7.7. Di chuyển cùng nhau kiểu tịnh tiến ....................................................................139
7.7.1. Chuỗi wave chạy theo ..................................................................................139
7.7.2. Chuỗi wave dẫn đầu .....................................................................................140
CHƯƠNG 8. PHỤ LỤC B – TÀI LIỆU THAM KHẢO ........................................... 142
6
MỤC LỤC HÌNH VẼ
Hình 1-1.Mô hình Wave.....................................................................................................13
Hình 2-1.Knowledge Network ...........................................................................................16
Hình 2-2.Thành phần của Spread Diagrams ......................................................................27
Hình 2-3.Tự động tách trong chuỗi Wave..........................................................................28
Hình 2-4.Một số trường hợp xử lý song song ....................................................................29
Hình 2-5.Wave xử lý song song có kèm theo Rule............................................................30
Hình 2-6.Xử lý tuần tự không Rule và có Rule..................................................................31
Hình 2-7.Wave xử lý tuần tự có Rule.................................................................................32
Hình 2-8.Một số trường hợp với mệnh đề If – else............................................................33
Hình 2-9.Một số trường hợp với mệnh đề If – else............................................................33
Hình 2-10.Else – if với filter ..............................................................................................34
Hình 2-11.Else – if parallel ................................................................................................34
Hình 2-12.Else – if với Rule...............................................................................................35
Hình 2-13.Switch................................................................................................................35
Hình 2-14.Câu lệnh lặp sử dụng Repetition .......................................................................36
Hình 2-15.Câu lệnh lặp sử dụng Recursion........................................................................37
Hình 3-1.Lưới thực địa .........................................................................................................1
Hình 3-2.Tạo lưới đơn hướng...............................................................................................1
Hình 3-3.Tạo lưới đa hướng .................................................................................................1
Hình 3-4.Di chuyển tự do .....................................................................................................1
Hình 3-5.Di chuyển tránh chướng ngại vật ..........................................................................1
Hình 3-6.Di chuyển vòng quanh chướng ngại vật................................................................1
7
Hình 3-7.Nhìn trong không gian với độ sâu cho trước ........................................................1
Hình 3-8.Đuổi bắt trong không gian.....................................................................................1
Hình 3-9.Di chuyển cùng nhau kiểu tịnh tiến ......................................................................1
Hình 3-10.Giao diện người dùng........................................................................................56
Hình 3-11.Hệ tọa độ màn hình .............................................................................................1
Hình 3-12.Vẽ đường thẳng...................................................................................................1
Hình 3-13.Vẽ hình chữ nhật .................................................................................................1
Hình 3-14.Vẽ hình elip .........................................................................................................1
Hình 3-15.Vẽ hình tròn.........................................................................................................1
Hình 3-16.Sự liên hệ giữa WAVE và chương trình hiển thị ................................................1
Hình 3-17.Lưới thực địa quy ước.........................................................................................1
Hình 3-18.Lưới thực địa trong chương trình đồ họa ..........................................................65
Hình 3-19.Lưới thực địa với gốc là tọa độ (6-1) ..................................................................1
Hình 3-20. Chướng ngại vật tại tọa độ (4,4) ......................................................................70
Hình 3-21. Chướng ngại vật được tạo liên tiếp ..................................................................71
Hình 3-22. Tạo node với tọa độ (1-1) và màu đỏ ...............................................................73
Hình 3-23.Tạo node với tọa độ (3-2) và màu xanh ............................................................73
Hình 3-24. Di chuyển node trên lưới thực địa....................................................................74
Hình 5-1.Xe đạp được thể hiện với công nghệ 2D.............................................................87
Hình 5-2.Xe đạp được thể hiện với công nghệ 3D.............................................................88
Hình 5-3.Đồ thị hàm sin(x) ................................................................................................89
Hình 5-4.Đồ thị hàm x2 + y2 hiển thị 3D............................................................................90
Hình 5-6.Khối cầu với bán kính 10 trong VRML..............................................................93
8
Hình 5-5.Tọa độ trong VRML..............................................................................................1
Hình 5-7.KN dạng cây của file VRML ................................................................................1
Hình 5-8.Sơ đồ khối thuật toán Parser .................................................................................1
Hình 5-9.Sơ đồ khối thuật toán kiểm tra một file có phải là VRML hay không..................1
Hình 5-10.KN sau khi thêm node mới .................................................................................1
Hình 5-11.Hai cách nhìn khác nhau trong VRML ...............................................................1
Hình 5-12.Cách nhìn ban đầu...............................................................................................1
Hình 5-13.Một cách nhìn khác .............................................................................................1
Hình 5-14.Hiển thị trên nhiều máy tính ...............................................................................1
Hình 5-15.Mỗi máy tính hiển thị một khu vực khác nhau ...................................................1
Hình 5-16. Đặt nút start tại một node khác node gốc...........................................................1
Hình 6-1. Chương trình hiển thị khi mới được chạy ........................................................113
Hình 6-2. Chương trình WAVE khi bắt đầu chạy...........................................................114
Hình 6-3. Lưới 5x5 ...........................................................................................................115
Hình 6-4. Cửa sổ output của Netbeans.............................................................................115
Hình 6-5. Vị trí đầu tiên 1-1 .............................................................................................116
Hình 6-6. Chạy ngẫu nhiên tới vị trí tiếp theo..................................................................116
Hình 6-7. Các bước chạy ngẫu nhiên tiếp theo ....................................................................1
Hình 6-9. Dừng khi chạy tới đích.....................................................................................118
Hình 6-8. Tiếp tục chạy ngẫu nhiên .....................................................................................1
Hình 6-10. Di chuyển qua chướng ngại vật..........................................................................1
Hình 6-11. Vượt qua chướng ngại vật và về đến đích..........................................................1
Hình 6-12. Di chuyển vòng quanh chướng ngại vật.............................................................1
9
Hình 6-13. Vòng quanh chướng ngại vật 1 vòng thì dừng...................................................1
Hình 6-14. Di chuyển tịnh tiến cùng nhau ...........................................................................1
Hình 6-15. Hình ảnh 3D trên máy thứ nhất sử dụng GnuPlot..........................................125
Hình 6-16. Hình ảnh 3D trên máy thứ hai sử dụng GnuPlot............................................125
Hình 6-17. Tệp tin VRML được hiển thị sau khi được tạo bởi KN .................................126
Hình 6-18. Các đối tượng hiển thị theo cách khác thi thay đổi Transform......................127
Hình 6-19. Một cách nhìn khác thi thay đổi Transform...................................................127
Hình 6-20. Hiển thị đối tượng đầu tiên trên máy 1 ..........................................................128
Hình 6-21. Hiển thị đối tượng thứ hai trên máy 2............................................................129
10
CHƯƠNG 2. GIỚI THIỆU
2.1. Giới thiệu về mô phỏng
Mô phỏng là làm giống như, bắt chước như… một đối tượng, hiện tượng nào đó
phục vụ được cho rất nhiều mục đích sử dụng.
Mô phỏng song song phân tán là công nghệ cho phép một chương trình giả lập có
thể được thực thi song song hoặc phân tán trên một hệ thống máy tính với nhiều máy tính
kết nối với nhau. Chương trình mô phỏng trên máy tính là sự tính toán để mô tả các thể
hiện của hệ thống thật hoặc giả lập. Ngày nay, mô phỏng được ứng dụng rộng rãi trong
các nhiều mặt của cuộc sống, như giáo dục, giao thông, y tế…
Với mô phỏng phân tán và mô phỏng song song, một chương trình mô phỏng có thể
thực thi trên một máy tính có nhiều bộ vi xử lý như PC.Độ lớn và phức tạp của các
chương trình giả lập ngày càng tăng theo thời gian. Trong một chương trình mô phỏng
phân tán lớn với nhiều đối tượng, một PC có thể không đủ bộ nhớ và khả năng tính toán
để thực hiện. Việc phân tán thực thi trên nhiều máy tính có thể giúp tăng hiệu quả xử lý
và lưu trữ hơn là làm trên một máy như trên. Các máy tính có thể được phân tán trong các
vùng địa lý khác nhau, ví dụ như trong các phòng của một tòa nhà, trong một thành phố,
hoặc rộng hơn là trên toàn thế giới.
Bằng việc chia nhỏ một khối lượng tính toán mô phỏng lớn sang các khối tính toán
bé hơn, và thực thi các khối đó đồng thời với N bộ vi xử lý, ta có thể tăng tốc độ lên N lần
so với trên 1 bộ vi xử lý trên một máy. Trong các bộ mô phỏng trên máy tính việc giảm
thời gian thực thi rất quan trọng bởi vì các kĩ sư sẽ không muốn phải đợi một thời gian dài
cho việc nhận kết quả trả về bởi chương trình. Trong việc mô phỏng thực tại ảo, nơi mà
con người hòa mình vào, thời gian xử lý đóng một vai trò rất quan trọng giúp mô phỏng
được thực hơn, mang hiệu quả cao hơn. Thực thi mô phỏng trên các máy tính phân tán
trên các vùng địa lý khác nhau giúp chúng ta linh hoạt hơn, không bị hạn chế về không
gian. Khi nhiều máy tính cùng thực thi song song, nếu một máy tính bị lỗi, các máy tính
11
khác vẫn có thể hoạt động tính toán bình thường. Điều này giúp tăng hiệu suất lên đáng
kể.
Việc tìm kiếm một ngôn ngữ hỗ trợ cho mô phỏng đáp ứng tốt các yêu cầu của mô
phỏng có vai trò rất lớn. Ngôn ngữ WAVE dùng cho mô phỏng vốn đã song song, xử lý
trên các cấu trúc dạng đồ thị và phân tán giữa các nút xử lý. Tất cả các chương trình
WAVE đều mang tính di động cao và thông dịch. Điều đó giúp giảm tải mạng, giảm thời
gian truyền dữ liệu dẫn đến giảm thời gian chờ đợi chung của mô phỏng phân tán song
song.
2.2. Công nghệ WAVE
Ngày nay, các hệ thống mở và mạng máy tính đang phát triển rất nhanh và được cả
thế giới quan tâm. Hệ thống mạng máy tính kết nối công việc từ khắp nơi trên thế giới,
mạng máy tính cũng giữ một khối lượng khổng lồ dữ liệu dịch vụ và thông tin. Những
công cụ tương tác không chỉ để tìm kiếm thông tin, dịch vụ hoặc file ngay trên máy tính
mà còn được mở rộng về địa lý, không gian… và hoàn toàn mở trên Internet. Một ví dụ
điển hình ở đây chính là World Wide Web. Tuy nhiên, hầu hết các mô hình và công cụ
lập trình phân tán thiếu đi khả năng linh hoạt để khai thác thông tin về cấu trúc mở một
cách tự động.
Những mô hình lập trình và hệ thống phân tán truyền thống thường dựa trên dữ liệu
đóng. Công việc được xử lý trong các ứng dụng phân tán thường phải được định nghĩa
trước hoặc được gọi thông qua việc kích hoạt thủ tục, phương thức. Phần lớn việc xử lý
và tương tác thông qua việc trao đổi thông điệp chứa dữ liệu. Ngoài ra hệ thống phân tán
có thể cung cấp dữ liệu và dịch vụ chia sẻ. Trong mạng máy tính, dịch vụ và thông tin chỉ
nằm ở các máy chủ ứng dụng (ví dụ như việc sử dụng của các tổ chức kinh doanh…). Tuy
nhiên, phương pháp tiếp cận này vẫn chưa tối ưu. Do đó, chúng ta sẽ cần phải tích hợp
linh hoạt các máy chủ ứng dụng trong một hệ thống tổng thể và có cơ sở hạ tầng mở hơn
nữa.
WAVE không chỉ là một mô hình. Wave còn là công nghệ dựa trên sự liên kết và
điều khiển của các hệ thông lớn được hỗ trợ bởi mạng máy tính và viễn thông. Wave cho
12
phép linh động tạo các cấu trúc điều khiển và việc xử lý mạng tri thức (phân tán và song
song) thông minh. Các cấu trúc này có thể cung cấp khả năng tự tổ chức, phục hồi, tạo
khuôn mẫu để kết nối tới các hệ thống khác. Công nghệ này dựa trên việc cài đặt nhiều
tác nhân thông minh trên hệ thống phân tán để tối ưu hóa việc xử lý dữ liệu cục bộ thông
qua việc lan tỏa thông tin ở các hệ thống nhỏ với nhau hoặc ở hai hệ thống nhỏ khác nhau.
Tất cả công việc trên đều được thông dịch qua ngôn ngữ Wave. Mã đệ quy được viết từ
ngôn ngữ này có khả năng tự lan tỏa trong không gian hệ thống. Không giống các hệ
thống truyền thống, nó là một hệ thống dựa trên sự linh động của chương trình có thể tùy
ý mở rộng về mặt địa lý và hỗ trợ nhiều máy tính trên mạng. Trong Wave, chương trình
có thể cho vào trong hệ thống bất kỳ chỗ nào. Khi đó các chương trình này có khả năng
lan tỏa qua mạng như virus. Nhiều người sử dụng có thể độc lập phát triển các chương
trình Wave hoặc liên kết trong cùng một hệ thống không gian, chia sẻ biến cục bộ (biến
này được liên kết với Node) với các biến khác (được kèm theo sự di chuyển của mã
Wave). Nói cách khác:
• Wave là một ngôn ngữ, model đặc biệt và là công nghệ mới cho hệ thống song
song, phân tán hay kết hợp các hệ thống đó với nhau.
• Wave ban đầu được thiết kế cho việc mô phỏng mạng ảo như là mạng tri thức
(Knowledge Networks).
• Wave dựa trên các chương trình mà có thể lan tỏa, mở rộng, chia nhỏ và có thể
tự hồi đáp trong những mạng tri thức đã được kích hoạt.
13
Hình 2-1.Mô hình Wave
14
CHƯƠNG 3. NGÔN NGỮ WAVE
Trong phần này chúng tôi trình bày về cú pháp và ngữ nghĩa của ngôn ngữ Wave.
Đây là một ngôn ngữ đặc biệt cho phép tạo và xử lý thông tin trong không gian mạng theo
hướng. Chương trình viết bằng ngôn ngữ này có thể được coi như những thành phần linh
hoạt, có khả năng di động và kết hợp với các thành phần riêng lẻ, phân tán khác. Trong
quá trình “di chuyển”, chương trình có thể mang theo dữ liệu đồng thời cập nhật vào dữ
liệu lưu tại mạng KN. Các chương trình mặc dù được xử lý song song nhưng vẫn có
những cơ chế cho phép chúng phối hợp đồng bộ với nhau thông qua hệ thống các luật.
Ở phần cuối chương này chúng tôi còn đề cập tới một vấn đề nữa: Wave và các phương
pháp lập trình truyền thống (lập trình tuần tự và lập trình song song).
3.1. Giới thiệu về ngôn ngữ Wave
Wave là một ngôn ngữ đặc biệt cung cấp khả năng thực thi mềm dẻo, đa người dùng
trên hệ thống phân tán. Quá trình thực thi của ngôn ngữ Wave giống như virus, tức là có
khả năng nhân bản và lan tỏa qua mạng, thực thi phân tán mà không cần bất kỳ sự điều
khiển tập trung nào.
Kiến trúc Wave mô tả quá trình xử lý phân tán qua việc tự định hướng luồng chương
trình qua không gian dữ liệu phân tán có cấu trúc như một đồ thị hay được gọi là
Knowledge Network. Các node trên mạng phân tán thuộc về một Wave Interpreter nào
đấy. WI là thành phần có trách nhiệm thực thi trên từng bộ phận riêng lẻ của mạng, thao
tác lên dữ liệu được lưu trữ trong các node.Trong khi di chuyển, những thành phần của
mã Wave có thể tự nhân bản, phân chia hay được chỉnh sửa trong khi vẫn duy trì sự trao
đổi dữ liệu qua lại lẫn nhau.
3.2. Node, Link và Không gian phân tán : Knowledge Network (KN)
Định nghĩa:
15
• Node: Có thể coi là một đối tượng – hay một điểm trong không gian, chứa các
biến (biến là thuộc tính của node)
• Link: Có thể coi là một quan hệ giữa các nút - hay một đoạn, đường thẳng
trong không gian. Nó cũng có các thuộc tính
Wave tạo và xử lý KN – là tập hợp các node và các link có hướng hoặc vô hướng.
Cả node và link đều có nội dung riêng của mình (kiểu giá trị là string). KN có thể được
phân tán trong không gian mạng, tồn tại trên nhiều máy tính khác nhau. Mỗi máy tính có
thể không chứa hoặc chứa nhiều node của KN và các link có thể kết nối tới các node
trong cùng máy tính hoặc với các máy tính khác.
Tất cả các node đều có địa chỉ duy nhất trong không gian phân tán bao gồm 2 thành
phần: thành phần thứ nhất để phân biệt các node trong cùng một máy, và thứ hai là để
phân biệt các node giữa các máy khác nhau trong không gian mạng. Node có thể được
truy cập qua các node khác một cách trực tiếp bằng Content hay bằng Address của
chúng hoặc qua quá trình mở rộng qua các link của KN, việc đặt tên cho link và node
nhằm phục vụ điều này. Có 2 kiểu nhảy qua lại giữa các node đó là direct hop và surface
hop để thực hiện việc nhảy tới 1 node hay có thể nhảy đến tất cả các node khác – được
dùng cho việc gửi quảng bá.
Không giống với node, link của KN không thể truy xuất trực tiếp qua tên. Dữ liệu
lưu trữ trong link chỉ có thể nhận được hoặc thay đổi một cách cục bộ, trong quá trình di
chuyển qua link hay khi đứng trực tiếp tại một node cụ thể nào đó. Từ một node, cả nội
dung và hướng của link có thể truy xuất trực tiếp.
Ví dụ:
16
Hình 3-1.Knowledge Network
3.3. Tổ chức chung của ngôn ngữ Wave
Ngôn ngữ Wave đặc trưng cho quá trình lan tỏa song song trong không gian dữ liệu
phân tán được biết là KN. Do vậy cú pháp của ngôn ngữ miêu tả rõ quá trình hoạt động
này:
trong đó các phần nằm trong [] là tùy chọn
Một chương trình Wave hay gọi đơn giản là Wave bao gồm sự kết hợp các tác động
lên KN gọi là các move – thành phần có thể thực hiện xử lý dữ liệu cục bộ tại các Node
của KN và mở rộng tới các Node khác. Quá trình thực thi song song hay thực thi không
theo thứ tự được tách biệt bởi dấu phẩy (,) phát triển một cách độc lập từ cùng một Node
wave Æ {{move , } . }
move Æ { data_unit act } | [rule] (Wave) }
rule ÆSQ | OS | AS | AP | RP | WT | ID | CR
unit Æ{ stirng; } | N{l_d} | F{l_d} | C | A | P | S | L | T |
act Æ# | ~ | /~ | == | / = | < | <= | + | - | * | / |** | | | % | & | : | :: | = | ? | !
17
trong KN. Tập các moves độc lập gọi là zone, được tách biệt nhau bởi dấu chấm câu (.),
các thành phần này sẽ được thực thi một cách tuần tự.
Ví dụ:
Ft={Fa=1;2;3}. Fa+1. ^Ft.T=Fa
Các Rule trong Wave cung cấp cho Wave khả năng mở rộng trong không gian
mạng, kết hợp cùng với các Wave khác. Một ví dụ, các luật có thể tự động tách Wave ra
thành nhiều nhánh riêng biệt rồi sau đó phát triển chúng song song hoặc tuần tự trong KN,
chúng có thể tạo ra hoặc mở rộng KN trong khi di chuyển. Các Rule sẽ được làm rõ hơn
trong phần sau.
Một cách tổng quát, việc thực thi phần đầu của Wave (Wave’s Head) tại một vài
Node có thể là nguyên nhân dẫn tới quá trình lan tỏa của Tail của chuỗi Wave (Wave’s
Tail) tới 0 hay nhiều các Node khác – chúng ta sẽ gọi chúng là tập các Node tới được
(SNR).
Ví dụ:
• w1.w2.w3.w4: cấu trúc của một chương trình Wave - sự nối tiếp của các zones
• w1,w2,w3: zone đơn lẻ với tập các move độc lập, tất cả đều được thực thi tại
cùng một Node bắt đầu
• w1,w2.w3,w4: sự kết hợp của 2 kiểu trên
3.4. Cấu trúc dữ liệu cơ bản của Wave
Wave là ngôn ngữ được dùng cho quá trình xử lý trên mạng, nhưng không giống các
ngôn ngữ khác, kiểu dữ liệu cơ sở không phản ánh việc đó. Wave sử dụng kiểu dữ liệu cơ
sở là Vector: là tập các string được phân tách nhau bới dấu chấm phẩy (;). Tất cả các hoạt
động của ngôn ngữ đều thực thi trên Vector. Truy cập tới thành phần của Vector có thể
18
thông qua chỉ số hay chính nội dung của các thành phần trong Vector – indexing và
contenting. Dữ liệu lưu trữ trong Vector là động, tức có thể thay đổi khi có sự thêm bớt
dữ liệu một cách tự động.
Ví dụ:
• Vector chứa 1 phần tử: 3
• Chứa 6 phần tử: 1;2;3;4;5;6
• Chứa nhiều kiểu dữ liệu khác nhau: 34;NONE;25;;a;;;b
3.5. Biến Spatial và kiểu
Wave thao tác trên kiểu biến được gọi là spatial variable, chúng nằm phân tán và
thường liên quan tới dữ liệu cục bộ tại các Node của KN hay có thể thuộc về một chuỗi
Wave nào đó. Biến kiểu này được chia làm 2 loại: task variable và environment
variable
3.5.1. Task variables
Task variable bao gồm: node variable và frontal variable. Các biến kiểu nodal được
lưu cục bộ tại node của KN, các biến kiểu frontal có thể đi cùng Wave qua các node khác
nhau trong mạng. Cả 2 loại biến này đều là tạm thời.
9 Biến Nodal: các biến loại này được khai báo bắt đầu bằng ký tự N
9 Biến Frontal: các biến loại này được khai báo bắt đầu bằng ký tự F
3.5.2. Environment variables
Biến môi trường có những định danh và ý nghĩa khác nhau:
19
9 CONTENT (C): chứa content của Node hiện thời. Giá trị của C luôn là
string, việc thay đổi nội dung của C có thể được gán trực tiếp bằng giá trị
nào đó hoặc NONE – xóa Node cùng với các Link liên kết với nó.
9 ADDRESS (A): địa chỉ của Node hiện thời. Luôn trả lại địa chỉ đầy đủ của
Node nơi Wave đang đứng gồm định danh của Node trong máy và định
danh của Node trong mạng. Đây là biến chỉ đọc.
9 PREDECESSOR (P): biến lưu địa chỉ của Node trước đó Wave đã đi qua.
Nó chỉ thay đổi khi có sự di chuyển của Wave sang Node khác.
9 LINK (L): chứa content của Link vừa mới đi qua.
9 TERMINAL (T): một loại biến đặc biệt dùng để in ra giá trị tương ứng tại
một đầu cuối nào đó.
Ví dụ:
• Biến Nodal: N, Nhieu, Ntue…
• Biến Frontal: Fpath, Ftemp…
• Biến môi trường: TERMINAL, LINK, L…
3.6. Các hành động – ACTS
3.6.1. Control acts
Các Act thực hiện các phép toán cơ bản bên trong move, dùng để thay đổi giá trị các
biến, thay đổi trạng thái hoạt động của wave. Giá trị trả về gồm 3 loại chính sau:
• TRUE (2): thành công và cho phép Wave tiếp sau đó thực thi tại Node hiện
thời.
20
• DONE (1): thành công nhưng không cho phép Wave thực thi tiếp tại Node hiện
thời.
• FALSE (0): thất bại, loại bỏ Wave tại Node hiện thời.
Control acts được phân loại như hop, filters, assignment, state genertator và code
injection.
Hop. Được thực thi bằng toán hạng #. Ta sẽ hiểu rõ hơn cách thực thi của Hop qua các Ví
dụ sau:
• DIRECT # ANY, cách viết khác @#: nhảy tới tất cả các node khác trong KN
trên cùng máy tính từ một node nào đó
• -p#b: nhảy từ node hiện thời theo cung đi ra (-)p tới node b
• ANY#ANY hay #: nhảy qua tất cả các link tới tất cả hàng xóm của một node
• Và một số kiểu nhảy khác: x#ANY, ANY#x
• Để nhảy sang 1 node ở máy khác ta có cấu trúc: a#b$$`IP, trong đó IP là địa chỉ
IP của máy đích
Filter. Các filter gồm các phép toán sau đây: ~ (thuộc về), /~ (không thuộc về), == (so
sánh bằng), /= (so sánh không bằng), < (so sánh nhỏ hơn), <= (so sánh nhỏ hơn hoặc
bằng), > (so sánh lớn hơn), >= (so sánh lớn hơn hoặc bằng). Giá trị trả về sẽ là TRUE
hoặc FALSE. Nếu giá trị trả về là TRUE, node hiện thời sẽ trở thành một SNR và Wave
tail sẽ tiếp tục phát triển từ node này.
• Filter ~:
o Cú pháp: vector1 ~ vector2
o Chức năng: kiểm tra các phần tử của vector 1 có nằm trong vector 2 hay
không
21
• Ví dụ: a;b ~ p;q;b;a sẽ trả về TRUE
• Filter /~: ngược lại toán tử ~
• Filter ==:
o Cú pháp: v1 == v2
o Chức năng: kiểm tra 2 vector có bằng nhau hay không
o Ví dụ: 2;3 == 2;3 sẽ trả lại TRUE
• Filter /=: ngược lại với ==
• Các filter còn lại: >,>=,<,<= có ý nghĩa toán học thông thường nhưng được
thực hiện trên vector
Nếu 1 filter trả lại giá trị TRUE, node hiện tại sẽ trở thành SNR, ngược lại SNR sẽ
rỗng và chuỗi Wave sẽ dừng quá trình thực thi.
Assignment.Toán tử gán = sẽ gán giá trị của toán hạng bên phải vào toán hạng bên trái.
Dữ liệu bên phải có thể là giá trị số, string, biến, vector. Phép gán luôn trả lại kết quả là
TRUE.
Ví dụ: Na=1, Na=1;2;3, Na=Nb;2;3;Fc
State Generator. Các trạng thái trả về ở trên đều xảy ra sau một quá trình thực thi nào đó.
Đôi khi ta muốn trực tiếp xác định trạng thái kết quả trả về để điều khiển luồng chương
trình, có một cách khác để thực hiện đó là dùng State Generator gồm 4 trạng thái: TRUE,
DONE, FALSE, ABORT. Cú pháp gồm tên trạng thái, theo sau là dấu !
Ví dụ:
w1.TRUE!.w2
Trong Ví dụ này w2 sẽ tiếp tục thực hiện
22
• w1.DONE.w2 hoặc w1.!.w2 sẽ dừng sau khi thực hiện xong w1
Code Injection. Cú pháp ^Func, trong đó Func là một chuỗi Wave. Phép chèn mã này sẽ
bổ sung thêm vào chuỗi Wave một chuỗi nằm trong biến sau ^. Phép này hay được sử
dụng khi gọi chương trình con.
Ví dụ:
Ft={Fa=1;2;3}. Fa+1. ^Ft.T=Fa
3.6.2. Fusion acts: Các phép toán hợp nhất
Các phép toán số học. Bao gồm các phép toán +, -, *, /. Nếu thực hiện chia cho 0, kết quả
trả về là FALSE.
Ví dụ:
• `124.36’ + 100 có kết quả: `224.36’
• 66;4;24 – 1;1;1;1;1;1;1 có kết quả: 65;3;23;-1;-1;-1;-1
• 1;2;3;4;5 * 1;1;1 có kết quả: 1;2;3;0;0
• 2;3;4 / 1;2 có kết quả: FALSE
• NONE * sẽ trả lại rỗng
Các phép toán trên Vector đặc biệt. Gồm 1 số phép toán sau:
• &: append, nối 1 Vector vào sau 1 Vector khác
o Ví dụ: v1 & v2 – v1, v2 là 2 Vector
• Toán tử hai chấm (:) : lấy giá trị tại 1 vị trí của Vector
o Ví dụ: Fa=3;2;3. Fa:1 sẽ trả lại 3
23
• Toán tử (::):
o Ví dụ: Fa=3;2;3. Fa::3 = 10. Kết quả Fa = 10;2;10
• |: splits, chia string ở toán hạng bên trái thành 1 Vector các string con bởi dấu
phân cách ở toán hạng bên phải
o Ví dụ: `a+b+c’ | `+’ sẽ trả lại a;b;c
• %: join, ngược lại với | tức nó sẽ hợp các Vector con lại thành 1 string với phân
cách là toán hạng bên phải.
o Ví dụ: a;b;c % `+’ sẽ trả lại a+b+c
Gọi hàm bên ngoài (External calls).Thực hiện qua toán tử ?, gọi một hàm nào đó của hệ
thống với đầu vào là các tham số từ Wave truyền vào.
Ví dụ: 50?`sleep’ sẽ dừng chương trình 50 giây
3.7. Rules – Các luật trong Wave
Wave có thể phát triển độc lập, dị bộ và được xử lý song song trong không gian
phân tán. Tuy nhiên điểm mạnh của Wave là nó có hệ thống các RULE để quản lý và
đồng bộ các các hành động. RULE thiết lập các ràng buộc trong việc lan tỏa chuỗi Wave.
Thông qua RULE, hệ thống có thể thực thi nhiều lần một Wave, hay tiếp tục lan tỏa Wave
nếu thỏa mãn một điều kiện nào đó, hoặc có thể chấm dứt toàn bộ wave. RULE thường
“treo” phần còn lại của chuỗi Wave (remainder) và lan tỏa nó ra chỉ khi chuỗi Wave nằm
trong luật thực thi xong và trả lại trạng thái TRUE.
Các Luật Rẽ Nhánh
• SEQUENCE(SQ): kích hoạt tất cả các nhánh một cách tuần tự mà không cần
quan tâm tới trạng thái kết quả trả về. SNR trên SQ là tập các SNR từ các
nhánh con.
24
Ví dụ: SQ(Fa=1, Fa+1).T=Fa sẽ tạo ra 2 nhánh Fa=1 và Fa+1, thực hiện tuần tự
2 nhánh này. Kết quả cuối là 2
• OS_SEQUENCE: kích hoạt tất cả các nhánh tuần tự cho tới khi nó nhận được
kết quả TRUE hoặc DONE trả về từ một nhánh nào đó
Ví dụ: OS(Fa=5.Fa>1, T=Fa) tạo ra 2 nhánh Fa=5.Fa>1 và T=Fa và thực hiện
tuần tự. Nhưng do nhánh thứ nhất trả về TRUE nên không thực hiện tiếp nhánh
thứ 2
• AND_SEQUENCE(AS): tương tự SQ nếu tất cả các nhánh đều trả về TRUE
hoặc DONE, nếu 1 nhánh FALSE, trạng thái toàn bộ AS sẽ là FALSE
Ví dụ: AS(TRUE!, FALSE!) sẽ trả lại FALSE
• OR_PARALLEL(OP): kích hoạt các nhánh và thực thi chúng song song, nếu 1
nhánh trả về TRUE hoặc DONE, OP sẽ nhận TRUE. Nếu không nhánh nào trả
về TRUE hoặc DONE, OP sẽ FALSE
Ví dụ:OP(FALSE!, FALSE!, TRUE!) sẽ trả lại TRUE
• AND_PARALLEL(AP): như AS nhưng các nhánh thực thi song song
Ví dụ: AP(TRUE!, TRUE!, FALSE!) sẽ trả lại FALSE
• RANDOM(RN): chọn một nhánh ngẫu nhiên để phát triển tiếp
Repetition
Luật REPEAT với khả năng vòng lặp cho phép chia Wave thành các phần nhỏ hơn
khi di chuyển trong KN.
25
Nếu kết quả trạng thái trả về là TRUE hoặc FALSE (SNR không rỗng) thì mỗi thành
phần này sẽ được ghép thêm Tail của Wave. Lúc này, ở tất cả SNR Node đều chứa biến
Frontal (biến này được mang tới từ các Node).
Nếu kết quả trạng thái trả về là DONE (SNR không rỗng) thì Tail của Wave sẽ bị
loại bỏ.
Ví dụ: F = 1; 9; 5; 6; 7; 8; 12.
REPEAT ( Fi +1. F : Fi /= NONE. N + ( F: Fi)).
TERMINAL =N.
Create
Luật CREATE(CR) cho phép Wave có khả năng mở rộng chính mạng KN trong khi
lan tỏa trong không gian. Chuỗi Wave chứa luật này vẫn phát triển như thông thường, chỉ
có các bước nhảy là bị ảnh hưởng - có thể thay đổi chế độ của chúng từ chế độ lan tỏa
(navigation) sang chế độ tạo mới (creation). Khi đó các node và link nếu chưa có sẽ được
tạo ra.
Có rất nhiều chi tiết quan trọng trong ngữ nghĩa của luật CR. Nếu node của 1 bước
nhảy tương ứng bằng địa chỉ của nó – điều này có nghĩa node đó đã tồn tại, tức các thành
phần trong luật CR nếu chưa có sẽ được tạo ra, còn nếu đã tồn tại thì quá trình CR sẽ
không tạo ra node hoặc link mới.
Ví dụ:
CR(@#a.+p#b.+q$$c`192.168.1.10’)
Ý nghĩa: nhảy trực tiếp tới node a mặc dù node a chưa có nhưng do nằm trong luật
CR nên node a sẽ được tạo ra, sau đó tạo ra link có hướng +p tới node b, tạo node c và
link +q nối từ a đến c trên máy 192.168.1.10
26
Release
Luật RL sẽ khởi tạo một Wave mới độc lập với chuỗi Wave ban đầu, mã của Wave
mới này là phần nằm trong dấu ngoặc của RL, WE của Wave mới chính là WE của Wave
ban đầu. Wave mới được tạo ra được đưa vào Wave Queue để chờ xử lý. Phần remainder
của Wave ban đầu sẽ tiếp tục được thực hiện như bình thường.
Ví dụ:
w1.RL(w2).w3
Ý nghĩa: sau khi thực thi xong w1, gặp RL chương trình Wave sẽ tách w2 cùng với
biến môi trường thành Wave mới cho vào hàng đợi xử lý, chuỗi Wave tiếp tục thực thi là
w3 cùng với biến môi trường của nó.
3.8. Wave và mô hình lập trình truyền thống
3.8.1. Sơ đồ luồng (SD)
Wave là ngôn ngữ có khả năng xử lý cấu trúc dữ liệu không gian phân tán lớn. Một
thuộc tính quan trọng của Wave là các chương trình điều khiển luôn được liên kết với vị
trí nào đó trong không gian dữ liệu (trong khi dữ liệu giữa các Node lan tỏa, hay giữa các
SNR lan tỏa). Dữ liệu của cùng một Node có thể xuất hiện ở những nơi khác nhau trong
cùng một SNR ở cùng một không gian cục bộ.
27
Hình 3-2.Thành phần của Spread Diagrams
Các kiểu module của Spread Diagram là
• SNR
• Move
• Rule
• Halt
• Các thành phần liên quan
o Link
o Biến Spatial
28
3.8.2. Wave và mô hình lập trình song song
Wave biểu diễn theo SD trong mạng dữ liệu có thể được điều khiển hoàn toàn bởi
Rule. Các thành phần của chuỗi Wave tự tách thành các nhánh trước và trong quá trình
thực thi.
Ví dụ: Tách chuỗi Wave
m1, m2 , m3. m4, m5 Æ
(m1. m4, m5), (m2. m4, m5 ), (m3. m4, m5)
Hình 3-3.Tự động tách trong chuỗi Wave
Ngoài ra, trong quá trình Wave thực thi, các thành phần của nó có thể được sao chép
và thay thế mà dữ liệu không bị thay đổi (Như trong Hình 3-4: m2 được sao chép và thay
thế mà dữ liệu vẫn được giữ nguyên)
m1. m2. m3 Æ
m1. m2, m2, m2. m3 Æ
29
m1.(m2. (m3, m3, m3)),
(m2. (m3, m3, m3)),
(m2. (m3, m3, m3))
Hình 3-4.Một số trường hợp xử lý song song
Ở một ví dụ khác ta thấy rõ hơn Rule điều khiển chuỗi Wave như nào (Hình 3-5).
30
Hình 3-5.Wave xử lý song song có kèm theo Rule
m1. OR_PARALLEL (m2, m3. m4). m5 Æ
m1. OR_PARALLEL((m2, m4), (m3. m4)) .m5 Æ
m1. OR_PARALLEL((m2. m4, m4, m4), ( m3. m4, m4, m4) ). m5
3.8.3. Wave và mô hình lập trình tuần tự
Việc cho phép phát triển không gian, xử lý song song và tự động trong môi trường
phân tán, Wave có thể dễ dàng mô hình hóa một số chương trình xử lý tuần tự. Giống các
chương trình bình thương, truyền thống ở cùng một máy tính, Wave phải ở cùng một
điểm trong không gian và chỉ có duy nhất một luồng được xử lý. Chúng ta sẽ bàn về vấn
đề này thông qua các ví dụ ở dưới đây.
Ví dụ 1
31
s1. s2. s3. s4
Ví dụ 2
SEQUENCE (s1, s2, s3, s4)
Hai ví dụ trên được thể hiện ở Hình 3-6
Hình 3-6.Xử lý tuần tự không Rule và có Rule
Ngoài ra có thể xem ví dụ ở Hình 3-7
s1. SQ ((s2. s3), s4)
và
SQ (s1, (s2. SQ (s3, s4)))
32
Hình 3-7.Wave xử lý tuần tự có Rule
• Biều thức If-else
Biểu thức điều kiện “If- else” trong mô hình lập trình tuần tự có cú pháp như sau:
If (e) s1 else s2
Mệnh đề s1 thực hiện và trả về kết quả đúng thì mệnh đề s2 sẽ được thực thi.
Ở Hình 3-8.Một số trường hợp với mệnh đề If – else:
OR_SEQUENTIAL (( e. s1) và
OR_SEQUENTIAL (AND_SEQUENTIAL ( (e. DONE ! ) , s1). s2)
33
Hình 3-8.Một số trường hợp với mệnh đề If – else
Hình 3-9.Một số trường hợp với mệnh đề If – else
• Lựa chọn nhiều nhánh
o If – else với filter
34
Hình 3-10.Else – if với filter
o Else – if parallel
Hình 3-11.Else – if parallel
o Else – if với Rule
35
Hình 3-12.Else – if với Rule
o Switch
Hình 3-13.Switch
36
• Vòng lặp
o while ( e ) s
o do s while ( e )
o For (e1 ; e2 ; e3) s
Hình 3-14.Câu lệnh lặp sử dụng Repetition
37
Hình 3-15.Câu lệnh lặp sử dụng Recursion
38
CHƯƠNG 4. CÁC BÀI TOÁN MÔ PHỎNG CƠ BẢN VÀ ĐỒ HỌA 2D
4.1. Cách tạo thực địa
Cách đơn giản nhưng hiệu quả trong việc tạo thực địa là sử dụng lưới. Trong đó mỗi
node sẽ biểu thị cho 1 cặp giá trị (x,y) và tất cả các node đều được liên kết với nhau bởi
các cung +x,+y,-x,-y tương ứng.
Hình 3-1 mô tả lưới thực địa được dùng trong các bài toán giả lập
Hình 3-1 minh họa cấu trúc của lưới thực địa gồm nhiều node và các link liên kết.
Ngoài ra, chúng ta có thể thêm các chướng ngại vật bằng cách sử dụng biến nodal đánh
y y y y y
2-1 2-2 2-3 2-4 2-5
5-1 5-2 5-3 5-4 5-5
4-1 4-2 4-3 4-4 4-5
3-1 3-2 3-3 3-4 3-5
1-1 1-2 1-3 1-4 1-5
x x x x
x x
x x x
x x x x
x x x x
x
y y y y y
x x
y y
y y
y y y
y y y
Hình 4-1.Lưới thực địa
39
dấu vị trí node thuộc chướng ngại vật đó. Việc tạo lưới, chướng ngại vật và các đối tượng
di chuyển sẽ được đề cập trong các phần tiếp theo.
4.1.1. Thuật toán tạo lưới đơn hướng
Mô tả chung
Đây là cách tạo lưới cơ bản. Nó sẽ tạo ra các node trong từng hàng. Các hàng sau sẽ
nối với các hàng trước qua các link tương ứng của từng node trong hàng đó.
Thuật toán
40
Hình 3-2 mô tả việc tạo lưới đơn hướng. Chúng ta khởi đầu từ hàng dưới cùng.
Node 1-1 sẽ được tạo đầu tiên. Các node được tạo theo thứ tự từ trái qua phải, từ dưới lên
trên. Các node hàng trên sẽ có link xuống các node tương ứng ở hàng dưới.
4.1.2. Thuật toán tạo lưới trên máy khác
Mô tả chung
Ta có thể dễ dàng tạo lưới giữa nhiều máy. Trong ví dụ ở dưới, ta sẽ tạo lưới trên 5
máy, mỗi máy sẽ là 1 hàng trong 5 hàng của lưới cần tạo.
Thuật toán
Hình 4-2.Tạo lưới đơn hướng
41
4.1.3. Thuật toán tạo lưới đa hướng
Mô tả chung
Với thuật toán này ta có thể tạo song song lưới trên nhiều máy một lúc. Việc đó giúp
tận dụng được việc xử lý phân tán làm tăng hiệu suất và thời gian tạo. Ở ví dụ dưới ta bắt
đầu từ hàng giữa. Việc tạo các hàng trên và dưới được tao song song trên 2 máy.
Thuật toán
42
Hình 4-3.Tạo lưới đa hướng
43
Trong Hình 3-3, chúng ta khởi đầu ở hàng giữa. Các node đươc tạo từ trái sang phải.
Sau khi tạo xong hàng giữa, wave tự động tách ra 2 hướng khác và tạo song song 2 hàng
tiếp theo theo mỗi hướng.
4.2. Các phép di chuyển cơ bản
4.2.1. Di chuyển tự do
Mô tả chung
Đây là một trong các bước di chuyển cơ bản. Chuỗi wave sẽ chạy đến các node
trong lưới một cách tự do. Ta sẽ cho 1 chuỗi wave di chuyển từ điểm đầu đến điểm đích
định sẵn. Mỗi bước đi, node tiếp theo sẽ được random tự chọn. Nếu sự lựa chọn không
thỏa, sẽ tiếp tục lựa chọn random mới.
Thuật toán
44
Theo Hình 3-4, từ node `1-5’ ban đầu, chuỗi wave của chúng ta sẽ chạy random theo
các hướng. Trong ảnh trên, chuỗi wave random và chạy theo lộ trình: 1-5 1-4 2-4 2-3 2-
1 3-1 4-1 5-1.
4.2.2. Di chuyển tránh chướng ngại vật
Mô tả chung
Chướng ngại vật được đánh dấu bằng các node tương ứng. Khi chuỗi wave di
chuyển từ điểm đầu đến đích, nó sẽ kiểm tra các node được đánh dấu và di chuyển
random tránh các node đó ra.
Thuật toán
5
4
3
2
1
5 4321
a
a a
a
a
a aa a
Hình 4-4.Di chuyển tự do
45
46
Từ node 1-5 ban đầu, chuỗi wave sẽ di chuyển random theo chiều x hoặc y. Mỗi lần
di chuyển nó sẽ tránh node đang được đánh dấu là chướng ngại vật. Chuỗi wave sẽ di
chuyển từ điểm đầu 1-5 đến điểm đích 5-1 như trên Hình 3-5.
4.2.3. Di chuyển vòng quanh chướng ngại vật
Mô tả chung
Một dạng quan trọng khác trong di chuyển cơ bản là di chuyển vòng quanh chướng
ngại vật. Chuỗi wave sẽ biết trước chướng ngại vật và khi di chuyển phải đảm bảo không
cách chướng ngại vật quá một bước nhảy.
Thuật toán
5
4
3
2
1
54321
a
a
a
a a
a a a a
Hình 4-5.Di chuyển tránh chướng ngại vật
47
5
4
3
2
1
5 4321
a
a
a
a
a aaa
a
a
Hình 4-6.Di chuyển vòng quanh chướng ngại vật
48
Hình 3-6 minh họa cho chuỗi wave di chuyển xung quanh một chướng ngại vật cho
trước. Khi mới bắt đầu, chuỗi wave sẽ random theo hai hướng: ngược hoặc xuôi chiều
kim đồng hồ. Sau khi đã xác định được hướng, chuỗi wave sẽ di chuyển vòng sát vào
chướng ngại vật lặp các vòng di chuyển đó.
4.2.4. Nhìn trong không gian với độ sâu cho trước
Mô tả chung
Trong các bài toán phức tạp, tầm nhìn trước của wave trong lưới có một vai trò rất
quan trọng. Chuỗi wave có thể nhận biết được xung quanh nó còn có các chuỗi wave khác
không để từ đó nó có thể di chuyển được tối ưu hơn. Việc ứng dụng của tầm nhìn trong
không gian sẽ được chúng ta đề cập đến trong các phần sau.
Thuật toán
49
50
Trong hình vẽ trên, ta bắt đầu từ node 3-4. Chuỗi wave sẽ lan ra theo các hướng và
thu thập các node trong khoảng cách gần nó với độ sâu là 2. Kết quả chúng ta thu được 3
node có đánh dấu là a,b,c.
4.3. Các mô phỏng tương tác cơ bản
4.3.1. Đuổi bắt trong không gian
Mô tả chung
Bài toán này sẽ gồm 2 chuỗi wave đuổi (B) và chạy(A). B rượt đuổi sẽ chạy nhanh
hơn A.B sẽ có chức năng nhìn trước với độ sâu cho trước để B luôn rượt duổi hiệu quả
hơn, giảm thời gian chạy xuống tối đa. Khi A bị bắt, màn hình sẽ in ra là b kill a và a
killed.
Thuật toán
5
4
3
2
1
5 4321
a
b
c
v
w
Node ẩn
Hình 4-7.Nhìn trong không gian với độ sâu cho trước
51
Với con chạy (A)
Với con đuổi (B)
52
53
Hình 3-8 mô tả quá trình đuổi bắt trong không gian. Ta khởi đầu escaper ở vị trí 2-2.
Cứ sau mỗi bước chạy escaper sẽ phải đợi trong một khoảng thời gian nào đó. Pursuer sẽ
chạy từ vị trí 2-5 để rượt đuổi escaper. Mỗi bước chạy của pursuer là kết quả của quá trình
nhìn trong không gian với độ sâu cho trước và random. Khi pursuer bắt được escaper,
dòng chữ Killed sẽ được in ra trên màn hình của chuỗi wave điều khiển con escaper.
4.3.2. Di chuyển cùng nhau kiểu tịnh tiến
Mô tả chung
5
4
3
2
1
54321
b
b
b
b b
a a a
Killed
Pursuer
Escaper
Hình 4-8.Đuổi bắt trong không gian
54
Một dạng di chuyển phổ biết khác chạy đuổi trong không gian đó là di chuyển dắt
tay nhau trong không gian. Khi đó, một đối tượng sẽ đóng vai trò là con dẫn đầu và không
thể di chuyển xa trừ khi con đi theo theo sát nó. Đối với đối tượng là con đi theo, nó chỉ
có thể di chuyển khi con dẫn đầu cho nó biết vị trí di chuyển.
Thuật toán
Với con dẫn đầu
Với con chạy theo
55
3
1 2 3 4 5
F L
3
1 2 3 4 5
LF
Bước 1
Bước 2
Hình 4-9.Di chuyển cùng nhau kiểu tịnh tiến
56
Hình 3-9 minh họa cho di chuyển dắt tay nhau. L tượng trưng cho con dẫn đầu và F
tượng trưng cho con chạy theo. Cả 2 sẽ dắt tay nhau di chuyển dọc theo trục x.
4.4. Hiển thị trong Java2D
4.4.1. Giới thiệu về Java 2D
Ngày nay, với sự phát triển như vũ bão của công nghệ thông tin, đồ họa máy tính đã
có sự thay đổi cực kỳ lớn. Các ngôn ngữ lập trình truyền thống đã được trực quan hóa
khiến cho việc viết các ứng dụng giao diện người dùng (GUI – Graphics User Interface)
trở nên dễ dàng hơn. Java cũng không nằm ngoài xu hướng này. Java đã có các thư viện
hỗ trợ viết các ứng dụng giao diện người dùng giúp lập trình viên có thể viết các ứng
dụng giao diện người dùng nhanh chóng và không có gì khó khăn nữa.
Hình 4-10.Giao diện người dùng
Như vậy, Java có thể được dùng để viết các ứng dụng giao diện đồ họa (GUI) và
những ứng dụng giao diện dòng lệnh (command-line). Các chương trình tương tác với
người dùng hiện này được sử dụng chủ yếu là các ứng dụng giao diện đồ họa. Chính vì
việc sử dụng giao diện đồ họa mà phiên bản Java để lập trình nên các ứng dụng giao diện
đồ họa được gọi là Java2D.
Java2D sử dụng các hàm thư viện AWT (Abstract Windows Toolkit) để thực hiện
xử lý đồ họa. Java là ngôn ngữ được viết có thể chạy trên các hệ điều hành khác nhau,
miễn là hệ điều hành này có cài đặt máy ảo Java (Java Virtual Machine). Với ưu thế này,
57
AWT cũng là thư viện được viết có thể chạy trên miền môi trường đồ họa của các hệ điều
hành khác nhau.
4.4.2. Giới thiệu một vài đối tượng đồ họa trong Java2D
Khi lập trình các ứng dụng giao diện người dùng đồ họa, các lập trình viên sẽ phải
quan tâm tới các hàm giao tiếp lập trình đồ họa (API) của hệ điều hành đang sử dụng.
Chúng ta cũng đều biết, mỗi hệ điều hành đều có các hàm đồ họa API khác nhau, các hàm
API của hệ điều hành Windows sẽ khác với các hàm API của hệ điều hành MAC,
Linux… Sự phát triển của công nghệ thông tin kéo theo sự phát triển của Internet, đồng
thời yêu cầu của người sử dụng ngày càng khắt khe hơn đòi hỏi các ứng dụng cần phải
được chạy trên các máy khác nhau sử dụng các hệ điều hành khác nhau. Lập trình viên
viết chương trình trên một hệ điều hành cố định mà không biết trước được người sử dụng
dùng chương trình của mình trên hệ điều hành nào. Java sinh ra cũng là để giải quyết vấn
đề này một các triệt để. Các chương trinh được viết bằng ngôn ngữ Java có thể chạy trên
các nền tảng hệ điều hành khác nhau. Các hàm API của thư viện đồ họa Java được thiết
kế rất trừu tượng, do đó lớp thư viện đồ họa AWT có thể giúp chúng ta chuyển đổi dễ
dàng từ API của Java sang API của hệ điều hành tương ứng một cách dễ dàng.
Khi muốn vẽ bất cứ cái gì, chúng ta đều phải sử dụng tới đối tượng Graphics, đối
tượng Graphics như một cây bút vẽ để vẽ. Bất cứ khi nào chương trình muốn tái tạo lại
hình ảnh đều phải dùng tới phương thức paintComponent (với Java 1.5 trở đi), phương
thức cài đặt cho lớp này như sau:
public void paintComponent(Graphics g) {
}
Với các phiên bản Java 1.4 trở về trước, phương thức paintComponent chưa được
sử dụng, lúc đó Java dùng phương thức paint, phương thức này được cài đặt như sau:
public void paint (Graphics g) {}
58
Để vẽ lại các hình ảnh, chúng ta phải gọi là phương thức paint hoặc paintComponent,
tuy nhiên việc sử dụng hai phương thức trên sẽ khiến chương trình tốn nhiều thời gian xử
lý nếu bị gọi liên tục. Và do vây phương thức repaint() được sử dụng để thay thế trong
trường hợp này giúp chương trình xử lý nhanh hơn và làm cho hình ảnh mượt mà hơn
khiến mắt người không có cảm giác hình bị giật, không tự nhiên.
Sau đây, chúng ta sẽ đi tìm hiểu một số đối tượng đồ họa cơ bản được sử dụng cũng
như một số phương thức để biểu diễn các đối tượng đó lên trên màn hình trong Java2D.
Thư viện AWT cung cấp lớp Graphics, đưa ra một số phương thức để vẽ các hình
cơ bản: đường thẳng (Lines), vòng tròn và elip (Circle và Ellipes), hình chữ nhật và đa
giác (Rectangle và Polygon), hình ảnh (Image) và văn bản với các font chữ (Text và
Font).
Chúng ta đều đã biết, màn hình máy tính hiện nay có độ phân giải khác nhau như
800x600, 1024x768, 1920x1080, … Độ phân giải này thể hiện được tọa độ lớn nhất có
thể có được ở góc tận cùng bên phải màn hình. Tọa độ ở đây được sử dụng trong hệ tọa
độ Đề-Các là tọa độ bao gồm các điểm (x,y) với trục tung hướng xuống và góc trái phía
trên màn hình là điểm có tọa độ (0,0). Tọa độ các điểm tăng dần về phí phải và từ trên
xuống dưới.
x
y
(1920,0
(0,1080) (1920,1080
Màn hình
(0,0)
Hình 4-11.Hệ tọa độ màn hình
59
Vẽ đường thẳng là việc làm cơ bản nhất trong đồ họa. Để vẽ một đường thẳng trong
Java2D là một việc cực kỳ đơn giản:
public void drawLine(int x1, int y1, int x2, int y2)
Phương thức này sẽ tạo ra được một đường thẳng tư điểm có vị trí (x1, y1) tới điểm
có vị trí (x2, y2) trên màn hình.
Ví dụ, để vẽ đường thẳng được tạo bởi hai điểm (0,0) và (250, 250) ta sử dụng như
sau:
public void paintComponent(Graphics g){
g.drawLine(0, 0, 250, 250);
}
Hình chữ nhật cũng là một trong các hình cơ bản của toán học, hình chữ nhật là một
hình có 4 đỉnh với 4 góc vuông. Hình vuông là trường hợp đặc biệt của hình chữ nhật.
Trong Java2D có nhiều cách để vẽ một hình chữ nhật nhưng phương thức cơ bản nhất để
vẽ hình chữ nhật là:
public void drawRect(int x, int y, int width, int height)
Hình 4-12.Vẽ đường thẳng
60
Chúng ta muốn vẽ một hình chữ nhật, điều đầu tiên cần phải xác định được là tọa độ
của điểm góc trái phía trên của hình chữ nhật (x, y) và chiều rộng cũng như chiều dài (ở
đây được đặt là height do trục tung hướng từ trên xuống dưới) của nó. Chẳng hạn, để vẽ
hình chữ nhật ở tọa độ (20,20) có kích thước 200x200, hình chữ nhật này trở thành hình
vuông, chúng ta sử dụng:
public void paintComponent(Graphics g){
g.drawRect(20, 20, 200, 200);
}
Hình tròn và hình elip cũng được sử dụng rộng rãi trong đời sống cũng như trong giao
diện. Java2D gọi chung hai hình này là hình bầu dục (Oval) và sử dụng chung phương
thức để vẽ hình tròn và hình elip. Phương thức cơ bản nhất là drawOval:
public void drawOval(int x, int y, int width, int height)
Hình 4-13.Vẽ hình chữ nhật
61
Để vẽ một hình tròn chúng ta chỉ cần đặt width = height. Để vẽ một hình tròn và
hình elip ta dùng:
public void paintComponent(Graphics g){
g.drawOval(10, 10, 30, 30);
g.drawOval( 50, 10, 30, 40);
}
Chúng ta vừa tìm hiểu về các hình cơ bản, các hình khối này được hình thành và
được xác định từ cơ sở là tọa độ các điểm. Thư viện AWT của Java cung cấp cho đối
height
width
x,
Hình 4-14.Vẽ hình elip
Hình 4-15.Vẽ hình tròn
62
tượng Point, Point là đối tượng biểu diễn tọa độ điểm (x,y). Để tạo ra một đối tượng (một
điểm) có tọa độ x, y:
public void Point(int x, int y)
Chúng ta cũng có thể tạo ra một điểm từ một điểm khác:
public void Point(Point p)
Nếu chưa biết được vị trí chính xác của điểm, chúng ta muốn gán tọa độ cho nó sau
này, tạo một điểm rỗng cũng thực hiện được trong Java:
public void Point()
Giả sử chúng ta tạo ra điểm có tọa độ (2,10). Trong chương trình, ta dùng lệnh:
Point p = new Point(2, 20)
Sauk hi có điểm p, chúng ta muốn thay đổi hoặc lấy vị trí của x hoặc y, Java cung
cấp các thành phần x, y của đối tượng Point giúp truy cập dễ dàng hơn: p.x để lấy ra vị trí
x, p.y để lấy ra vị trí y.
4.4.3. Tương tác giữa chương trình hiển thị và Wave
Wave không bó hẹp trong bản thân chương trình, Wave còn có khả năng tương tác
với các chương trình bên ngoài cũng như hệ điều hành mà Wave đang chạy. Sự tương tác
này có được là do Wave tích hợp một hàm được gọi là SystemCall, giúp Wave thực thi
các chương trình bên ngoài, đây là một hàm rất mạnh và được sử dụng tương đối nhiều.
Chương trình Wave có thể thực thi các lệnh thường dùng của hệ điều hành đang
thực thi Wave. Trên hệ điều hành Windows, Wave có khả năng gọi toàn bộ các lệnh
ipconfig, dir, ren … Và trên Linux các lệnh thường dùng cũng được gọi một cách dễ
dàng:ifconfig, ls, …
63
Không bị bó hẹp bởi các lệnh hệ thống sẵn có, Wave cũng có thể chạy một ứng
dụng, là các tệp tin chương trình, tại bất cứ đâu trên máy. Tính năng này được đánh giá rất
cao vì đây chính là cách mà Wave tương tác với các chương trình bên ngoài một cách trực
tiếp.
Bản thân chương trình Wave được viết bằng ngôn ngữ Java nên Wave có đầy đủ các
đặc tính của một chương trình Java. Một trong các đặc tính đó là Wave có thể gọi và thực
thi một class (lớp) khác được viết bằng Java một cách dễ dàng.
Chương trình hiển thị đồ họa là một chương trình độc lập với Wave. Sự liên hệ giữa
chương trình hiển thị và Wave được thể hiện theo sơ đồ dưới đây:
Dựa vào sơ đồ trên ta có thể nhìn thấy rõ giữa Wave và chương trình hiển thị đồ họa
có một chương trình con làm trung gian. Cơ cấu hoạt động của sơ đồ như sau:
Ban đầu, chương trình hiển thị sẽ được chạy và lắng nghe ở một cổng nào đó, chờ
các thông điệp được chuyển đến. Từ bước này, có thể thấy, chương trình hiển thị có thể
được viết bằng bất kỳ ngôn ngữ nào trên bất cứ hệ điều hành nào và ở bất kỳ máy nào.
Bước tiếp theo, chương trình Wave chạy và thực hiện các công việc mà người dùng
đưa dữ liệu vào, khi cần hiển thị Wave sẽ gọi chương trình trung gian bằng hàm
SystemCall.
Chương trình trung gian là một lớp (class) được viết bằng Java hoặc là một chương
trình có khả năng thực thi. Chương trình này sẽ nhận các tham số được truyền từ Wave.
Chương trình
hiển thị
Chương trình
trung gian
Gọi Wave
Đưa dữ
liệu
Truyền
tham số
Hình 4-16.Sự liên hệ giữa WAVE và chương trình hiển thị
64
Sau đó chương trình sẽ xử lý các tham số nhận được (nếu cần) rồi truyền cho chương
trình hiển thị qua socket. Khi truyền dữ liệu xong, chương trình trung gian sẽ kết thúc.
Chương trình hiển thị đang lắng nghe thì nhận được thông điệp từ chương trình
trung gian gửi tới, thông điệp được xử lý và hiển thị lên màn hình tương ứng với dữ liệu
truyền vào. Trong khi hiển thị, chương trình vẫn tiếp tục lắng nghe để đợi dữ liệu được
tiếp tục truyền vào.
4.4.4. Tạo lưới
Trong chương trình hiển thị, lưới được tạo ra là hình chữ nhật hoặc hình vuông. Hầu
hết lưới được tạo bởi Wave là các hình vuông, các hình này được chia nhỏ thành các hình
vuông nhỏ hơn tạo thành các hàng và cột. Như vậy, lưới là tập hợp các hình vuông nhỏ và
có thể được gọi là một bảng gồm hàng và cột. Hình bên dưới minh họa cho ta một lưới
(5x5 nút hay 5x5 ô vuông, từ bây giờ khi nói tạo ra một lưới 5x5 chúng ta ngầm hiểu là
tạo ra một lưới 5x5 nút):
1 2 4 3
1
5
4
2
5
3
Hình 4-17.Lưới thực địa quy ước
65
Với một lưới được tạo ra như hình vẽ trên, chúng ta đặt tọa độ cho các đỉnh của các
hình vuông theo số của các nút tương ứng với chiều ngang và chiều dọc. Theo như hình
vẽ trên, tọa độ của nút đầu tiên sẽ là (1,1) và nút cuối cùng nằm ở góc dưới bên phải của
hình vẽ là (5,5).
Trong chương trình hiển thị, lưới sẽ được nằm trong một khung được gọi là frame.
Khung sẽ có kích thước được đặt sẵn và tính theo pixel. Ví dụ khung có kích được
1024x768 là khung có chiều dài 1024 pixel và chiều rộng là 768 pixel. Dưới đây là một ví
dụ có trong chương trình hiển thị khi lưới được tạo ra nằm trong khung chính là giao diện
của chương trình hiển thị:
Hình 4-18.Lưới thực địa trong chương trình đồ họa
Hình 4-18 minh họa cho lưới thực địa được hiển thị trong chương trình đồ họa khi
chương trình nhận được lệnh tạo lưới từ WAVE.
Kỹ thuật dùng để tạo lưới trong chương trình như sau, khi nhận được thông điệp từ
chương trình trung gian hoặc Wave theo đúng định dạng, chương trình hiển thị sẽ phân
tích và lấy ra các kích thước là số hàng và số cột. Dựa vào số hàng và số cột, chương trình
66
sẽ chia hình cần biểu diễn thành các phần bằng nhau chính là các ô vuông nhỏ. Tiếp theo,
chương trình sẽ vẽ lần lượt từng ô vuông một cho tới khi hết tức cho tới khi tạo thành
được hình vẽ theo yêu cầu.
Vừa rồi, chúng ta vừa tìm hiểu kỹ thuật tạo ra một lưới trong chương trình, bây giờ,
chúng ta sẽ đi đến chi tiết sử dụng trong mã chương trình.
Định dạng của lệnh để tạo ra một lưới trong chương trình là:
CREATEGRID(num_x,num_y;root_x,root_y)
Trong đó:
CREATEGRID: mã lệnh tạo lưới
num_x: số nút theo chiều ngang
num_y: số nút theo chiều dọc
root_x:tọa độ theo chiều ngang của chương trình Wave
root_y:tọa độ theo chiều dọc của chương trình Wave
Ở đây, tọa độ theo chiều ngang và theo chiều dọc của chương trình Wave được hiểu
như sau: với Wave hay bất cứ chương trình nào khác, việc tạo ra một lưới đối với chương
trình hiển thị trên màn hình đều vẽ ra một lưới mà không vẽ ra chỉ số hay tọa độ của lưới.
Chúng ta đều biết nút đầu tiên của lưới là (1,1), mặc dù vậy chương trình muốn quy ước
nút đầu tiên có tọa độ khác đi nhưng khi hiển thị vẫn hiển thị một cách bình thường thì
khi tạo lưới sẽ quy ước tọa độ ban đầu của lưới sẽ ứng với tọa độ nào của chương trình
đưa dữ liệu vào. Để cho dễ hiểu, chúng ta muốn tạo một lưới 5x5 với tọa độ ban đầu ứng
với tọa độ (1,1), câu lệnh tạo lưới sẽ như sau:
CREATEGRID(5,5;1,1)
Với câu lệnh trên, chương trình sẽ tạo ra giao diện như Hình 4-18
67
Các điểm được quy ước như Hình 3-17
Bây giờ, chúng ta tạo một lưới có tọa độ ban đầu ứng với tọa độ (6,1), câu lệnh tạo lưới
như sau:
CREATEGRID(5,5;6,1)
Và câu lệnh này sẽ tạo ra hình ảnh giống Hình 4-18
Mặc dù hình ảnh hiển thị là giống nhau giữa câu lệnh: CREATEGRID(5,5;1,1) và
CREATEGRID(5,5;6,1). Tuy nhiên CREATEGRID(5,5;6,1) có các điểm được quy
ước ngầm như bên dưới:
Hình 3-19 minh họa cho lưới thực địa ngầm định trong trường hợp gốc tọa độ ở vị
trí (6-1)
Mã được viết trong chương trình để tạo ra một lưới rất đơn giản.Ban đầu, chương
trình đặt biến trạng thái status. Khi khởi tạo chương trình, biến này sẽ có giá trị bằng 0.
6 7 9 8
1
10
4
2
5
3
Hình 4-19.Lưới thực địa với gốc là tọa độ (6-1)
68
Khi chương trình hiển thị nhận được một thông điệp và kiểm tra xem thông điệp đó có
chứa lệnh điều khiển để tạo ra một lưới hay không, nếu đó là lệnh tạo lưới, chương trình
sẽ phân tích lệnh này tiếp nhằm kiểm tra các tham số của lệnh có phù hợp và đúng với
định dạng của lệnh tạo lưới hay không. Đoạn mã dưới được cài đặt vào trong chương
trình:
69
Sau khi phân tích dữ liệu và lấy được ra tham số phù hợp với lệnh, chương trình sẽ
gọi đến hàm tạo lưới:
Hàm này, thực chất chỉ thay đổi biến status thành 1 và thiết lập độ dài và độ rộng
cho lưới, còn việc hiển thị lưới được đặt trong trong hàm paintComponent:
4.4.5. Tạo chướng ngại vật
Chướng ngại vật là tập hợp của các hình vuông. Mỗi một chướng ngại vật khi được
thiết lập chương trình hiển thị sẽ thiết lập và tạo ra tại nút tương ứng một hình vuông
được tô màu, để tạo ra một chướng ngại vật liên tiếp tại nhiều nút khác nhau cần truyền
vào cho chương trình hiển thị vị trí của các nút tương ứng và chương trình sẽ hiển thị hình
vuông tại mỗi nút đó.
if (status == 1) {
int x_grid = translation_x;
int y_grid = translation_y;
for (int i = 0; i < x; i++) {
for (int j = 0; j < y; j++) {
g.drawRect(x_grid, y_grid,
similar_width, similar_width);
x_grid += similar_width;
}
x_grid = translation_x;
y_grid += similar_width;
}
}
private void createGrid(int num_x, int num_y) {
x = num_x;
y = num_y;
status = 1;
repaint();
}
70
Để tạo ra một chướng ngại vật, câu lệnh để tạo có định dạng:
CREATEOBST(x,y):
Trong đó:
CREATEOBST: mã lệnh tạo chướng ngại vật
x: vị trí của chướng ngại vật theo chiều ngang
y: vị trí của chướng ngại vật theo chiều dọc
Ví dụ, chúng ta muốn tạo một chướng ngại vật tại nút có tọa độ (4,4), câu lệnh tạo
chướng ngại vật là: CREATEOBST(4,4)
Hình 4-20. Chướng ngại vật tại tọa độ (4,4)
Muốn tạo một chướng ngại vật theo hình tam giác tại (2,2), (2,3), (3,2) chúng ta phải
sử dụng liên tiếp: CREATEOBST(2,2), CREATEOBST(2,3), CREATEOBST(3,2)
71
Hình 4-21. Chướng ngại vật được tạo liên tiếp
4.4.6. Di chuyển
Sự di chuyển vị trí của một nút từ vị trí này đến vị trí khác thực ra chỉ là các thủ tục:
xóa nút ở vị trí cũ và tạo ra một nút giống hệt nút cũ ở vị trí mới.
Để tạo ra một nút mới, cần truyền cho chương trình hiển thị một lệnh có định dạng:
CREATENODE(x,y,color)
Để xóa một nút, cần truyền cho chương trình hiển thị một lệnh có dạng:
DELETENODE(x,y,color)
Trong đó:
CREATENODE: mã lệnh tạo nút
DELETENODE: mã lệnh xóa nút
72
x: vị trí của nút theo chiều ngang
y: vị trí của nút theo chiều dọc
color: màu của nút
Màu của nút được quy ước:
0: Black (màu đen)
1: White (màu trắng)
2: Red (màu đỏ)
3: Blue (màu xanh)
Để di chuyển một nút từ tọa độ(x1,y1) có màu color đến tọa độ(x2,y2), câu lệnh di
chuyển như sau:
MOVEFROMTO(x1,y1,color;x2,y2)
Ví dụ, chúng ta tạo ra một nút có màu đỏ tại tọa độ (1,1) và một nút màu xanh tại tọa
độ (3,2):
CREATENODE(1,1,2)
73
Hình 4-22. Tạo node với tọa độ (1-1) và màu đỏ
Hình 4-22 minh họa cho việc tạo node với màu đỏ trên lưới thực địa
CREATENODE(3,2,3)
Hình 4-23.Tạo node với tọa độ (3-2) và màu xanh
Hình 4-23 minh họa cho việc tạo node với màu xanh trên lưới thực địa
Sau đó, chúng ta di chuyển nút màu đỏ sang tọa độ (2,2):
74
MOVEFROMTO(1,1,2;2,2)
Hình 4-24. Di chuyển node trên lưới thực địa
Hình 4-24 minh họa cho việc di chuyển một node trên lưới thực địa sang một vị trí
mới.Trong hình trên, màu đỏ đã di chưyển từ vị trí (1-1) sang (2-2).
75
CHƯƠNG 5. CÁC BÀI TOÁN MÔ PHỎNG PHỨC TẠP
5.1. Bài toán “Hồng cầu, Bạch cầu, Virus”
5.1.1. Mô tả chung
Trong chương trước, chúng ta đã làm quen được với các bài toán cơ bản khi sử dụng
ngôn ngữ Wave trong việc mô phỏng. Chương này sẽ giới thiệu một bài toán phức tạp
hơn, ứng dụng đầy đủ các bài toán trước. Đó là bài toán mô phỏng hồng cầu, bạch cầu,
virus. Chúng ta sẽ sử dụng lưới để mô phỏng không gian thực địa. Các đối tượng sẽ có thể
di chuyển theo 4 hướng trong lưới: đi lên, đi xuống, sang bên phải, sang bên trái. Chúng
ta có ba loại đối tượng đó là đối tượng hồng cầu, đối tượng bạch cầu, và đối tượng virus.
Hồng cầu là đối tượng di chuyển tự do trong không gian.Virus luôn tìm cách tiếp cận
hồng cầu và ăn hồng cầu đồng thời sản sinh ra virus mới. Bạch cầu luôn tìm virus để tiêu
diệt.Tùy vào độ lớn của virus mà cần 1 số lượng bạch cầu để tiêu diệt.
5.1.2. Hồng cầu
Mô tả
Đây là đối tượng di chuyển tự do. Hồng cầu khởi đầu có số lượng nhiều nhất. Khi
gặp virus, hồng cầu sẽ bị virus ăn và biến mất.
Thuật toán
76
5.1.3. Bạch cầu
Mô tả
Đối tượng bạch cầu khi di chuyển luôn tìm kiếm virus. Nếu không thấy, nó sẽ di
chuyển tự do trong không gian. Khi gặp virus, hồng cầu sẽ chết đi và làm cho virus bị suy
yếu.
Thuật toán
77
5.1.4. Virus
Mô tả
Đối tượng virus luôn tìm hồng cầu để gây bệnh. Nếu không tìm thấy hồng cầu, virus
sẽ di chuyển tự do. Khi ăn được hồng cầu, virus sẽ sinh ra một virus khác. Mỗi virus sẽ có
một chỉ số sức khỏe nhất định. Khi gặp bạch cầu, virus sẽ bị suy yếu, giảm chỉ số sức
khỏe. Nếu chỉ số sức khỏe xuống mức 0, virus sẽ bị chết.
Thuật toán
78
79
5.2. Bài toán “Rầy nâu”
5.2.1. Mô tả chung
Sơ bộ về cây lúa
Lúa (Oryza sativa L.) gồm 3 loại: Indica, Japonica, Javanica. Các giống lúa nhiệt đới
thuộc loại Indica, các giống lúa ôn đới thuộc loại Japonica, còn loại Javanica có hạt rất
dài, hàm lượng amylose từ 20 - 25 thì rất ít gặp. Giống địa phương là những giống cổ
truyền được gieo trồng theo tập quán địa phương, thường cao gầy, dễ đổ, năng suất thấp,
yêu cầu phân bón ít.
Chu kỳ sinh trưởng của cây lúa trải qua 6 giai đoạn: mạ, đẻ nhánh, làm đòng, ngậm
sữa, trổ bông và chín rộ.
Hạt lúa sau khi chín có thời gian ngủ nghỉ vài ba tuần hoặc lâu hơn. Đặc tính này có
lợi cho vùng nhiệt đới nóng và ẩm, đặc biệt khi bị ngập nước và lúa đổ.
Sơ bộ về sâu rầy nâu
Chu kỳ sinh trưởng và phát triển sâu rầy nâu
Rầy nâu hay còn gọi là muội nâu,có tên khoa học là Nilaparvata lugens Stal, thuộc
họ muội bay (Delphacidae), bộ cánh đều (Homoptera). Nó có ở các vùng trồng lúa trong
nước và thế giới. Ngoài cây lúa, rầy nâu còn có thể phá hoại trên các cây ngô, mì, mạch,
kê, cỏ gấu, cỏ lồng vực...
Vòng đời của rầy nâu thay đổi theo mùa, trải qua 3 giai đoạn chính: thời gian trứng,
rầy non, rầy trưởng thành.
Rầy trưởng thành sau khi vũ hoá 3 - 5 ngày thì bắt đầu đẻ trứng, thời gian đẻ trứng
dài. Mỗi con cái có khả năng đẻ từ 71 - 408 quả trứng, thường đẻ vào buổi chiều. Thời
gian trứng nở phụ thuộc nhiều vào yếu tố ngoại cảnh. Trứng rầy nâu ở nhiệt độ 18.7 -
21.6o C, qua 13 - 14 ngày thì nở, ở nhiệt độ 23.4 - 29.6o C qua 5 - 9 ngày nở. Trứng nở rải
rác trong một ngày. Tỉ lệ trứng nở cao trên 90%.
80
Rầy non ít di động, thường tập trung hút dịch cây ở phần dưới khóm lúa. Nếu khua
động có thể nhảy hoặc bỏ trốn.
Rầy trưởng thành có hai dạng: cánh dài và cánh ngắn. Tỉ lệ xuất hiện cửa các dạng
phụ thuộc vào điều kiện nhiệt độ, độ ẩm, và dinh dưỡng. Nhiệt độ thấp, độ ẩm cao, thức
ăn phong phú thì xuất hiện dạng cánh ngắn nhiều. Nhiệt độ cao, độ ẩm thấp, thức ăn
không thích hợp thì xuất hiện dạng cánh dài nhiều. Rầy dạng cánh ngắn có tuổi sống dài,
tỉ lệ cái/đực cao, số lượng rầy đẻ trứng cao hơn cánh dài. Do đó khi rầy cánh ngắn xuất
hiện nhiều thì có khả năng thành dịch. Rầy trưởng thành có thể sống từ 3 - 50 ngày.
Nhìn chung, thời gian sinh trưởng phát dục các giai đoạn của rầy nâu biến động như
sau:
• Trứng: 5.5- 14 ngày.
• Rầy non: 12.5 - 32.5 ngày.
• Rầy trưởng thành: 3 - 50 ngày.
Quy luật phát sinh phát triển và các yếu tố ảnh hưởng
Rầy thường tập trung thành đám ở trên thân cây lúa dưới khóm để hút nhựa, làm cho
cây khô héo và chết. Khi bị khua động thì bỏ trốn bằng cách bò ngang, nhảy sang cây
khác, hoặc xuống nước, hoặc bay xa đi chỗ khác. Ban ngày rầy ít hoạt động ở trên lá lúa,
chiều tối bò lên phía trên thân lúa hoặc lá lúa. Khi lúa ở thời kỳ chín, phần dưới của thân
lúa đã cứng khô thì ban ngày rầy tập trung phía trên cây lúa hoặc gần chỗ non mềm của
cuống bông để hút nhựa, làm cho bông lúa bị lép một nửa hoặc toàn bộ. Rầy nâu còn là
véc tơ truyền bệnh lúa lùn xoăn lá gây thiệt hại rất lớn cho mùa màng.
Kinh nghiệm thực tế nhiều năm cho thấy khi ruộng lúa xuống giống được khoảng
20-25 ngày, lúa bắt đầu “phát” thì cũng là lúc Rầy nâu cánh dài từ nơi khác di chuyển đến
đẻ trứng tạo thế hệ Rầy non thứ nhất. Nếu gặp điều kiện thuận lợi Rầy sẽ nhanh chóng
tích lũy số lượng và tạo thế hệ rầy non thứ hai vào khoảng 50-55 ngày sau khi gieo sạ (lúc
lúa làm đòng) và thế hệ Rầy non thứ ba vào khoảng 30 ngày sau đó (sau trổ-ngậm sữa).
81
Những năm có dịch thường Rầy sẽ gây “cháy rầy” vào hai đợt rầy sau (nhất là ở đợt rầy
non thứ ba), vì thế cần hết sức cảnh giác với hai đợt rầy này. Như vậy, một năm rầy nâu
có thể sinh thành 6 -7 lứa. Trong đó có 2 lứa cần được chú ý theo dõi để phòng trừ, đó là
lứa rầy phá hại vào tháng 4 - 5 (đối với vụ chiêm xuân, đặc biệt vùng chiêm trũng) và lứa
tháng 7 - 9 (đối với vụ mùa).
Rầy nâu phát sinh gây hại thường đầu tiên xuất hiện thành từng vạt giữa ruộng, sau
đó lan dần ra quanh ruộng. Qui luật phát sinh và mức độ gây hại liên quan nhiều đến yếu
tố sinh cảnh. Thường thường nếu trước một thời gian nào đó nhiệt độ không khí cao, độ
ẩm cao, lượng mưa nhiều, sau đó trời hửng nắng, nhiệt độ cao, độ ẩm thấp thì rầy nâu dễ
phát sinh thành dịch. Thông thường nhiệt độ 20 - 30oC và độ ẩm 80 - 85 % là điều kiện
thích hợp cho rầy nâu sinh sống và phát triển.
Mức độ và triệu chứng tác hại
Sâu rầy nâu là một trong những loại sâu được xếp vào hàng sâu bệnh nguy hiểm cho
cây lúa. Chúng chích hút nhựa làm cây khô héo và chết hoặc làm cho bông lúa bị lép một
nửa hoặc toàn bộ, làm giảm năng suất cây trồng và giảm chất lượng sản phẩm. Ngoài ra,
rầy nâu còn là vectơ truyền bệnh vàng lùn và lùn xoắn lá - một bệnh cực kỳ nguy hiểm,
gây nhiều thiệt hại cho cây trồng.
Năm 1958, rầy nâu phát sinh thành dịch phá hại lúa chiêm từ thời kỳ trổ - chín ở
các tỉnh phía Bắc. Vụ mùa năm 1962 và 1971, rầy nâu đã gây nhiều thiết hại lớn cho lúa
như ở Nghệ An. Ở các tỉnh phía Nam từ năm 1970, rầy nâu đã gây thiệt hại nặng trên các
giống lúa NN8, NN5, NN20 ở nhiều tỉnh thuộc đồng bằng sông Cửu Long, đồng bằng ven
biển khu 5 và Thừa Thiên.
Năm 1974, diện tích lúa bị rầy nâu hại ở các tỉnh phía Nam lên tới 97.869 ha. Từ
năm 1975, đặc biệt từ tháng 11/1977, trong suốt 3 tháng từ tháng 11 – 1, rầy nâu gây
thành dịch trên diện tích lúa rộng 200.000 ha. Các tỉnh Bến Tre, Tiền Giang và Long An
là nơi bị rầy hại nghiêm trọng nhất (Tài liêu Cục bảo vệ thực vật)
82
Trong những năm gần đây, đặc biệt là vụ hè thu năm 2005 - 2006, nạn rầy nâu,
kéo theo là dịch bênh vàng lùn xoắn lá lại trở lại, gây thiệt hại trên diện tích lúa rộng hơn
73.000 ha. Các tỉnh vùng Đồng bằng sông Cửu Long bị thiệt hại nặng nhất.
Bài toán dự đoán
Giới thiệu bài toán dự đoán tổng quát
Trong thực tế, có rất nhiều vấn đề cần được dự toán trước. Một ví dụ đơn giản, một
câu lạc bộ có truyền thống là tổ chức buổi tiệc thường niên cho tất cả các thành viên của
câu lạc bộ và cả bạn bè của họ, có thể gặp gỡ. Những người có ý định tham dự sẽ báo
trước cho ban tổ chức chậm nhất là trước nửa tháng. Vấn đề đặt ra là ban tổ chức muốn
dự đoán số người thực sự sẽ đến dựa trên cơ sở số người báo trước là bao nhiêu để tránh
phí phạm. Hay trong kinh kế, người ta muốn dự đoán giá cả thị trường tăng hay giảm để
quyết định việc mua hay bán các mặt hàng sao cho có lãi nhất. Rất nhiều nhiều các nhu
cầu dự đoán khác trong tương lai làm cơ sở cho phương hướng hoạt động của cá nhân, tập
thể trong thời gian tới. Bài toán đặt ra là, chúng ta có thể xây dựng một mô hình toán học
dựa trên các yếu tố ảnh hưởng tới vấn đề cần dự đoán để dự đoán một vấn đề nào đó hay
không.
Hướng tiếp cận bài toán
Có hai hướng tiếp cận chính để dự đoán. Hoặc là ước lượng giá trị tương lai dựa
trên phân tích các nhân tố có ảnh hưởng tới các giá trị tương lai (phương thức chứng minh
(the explanatory method)), hoặc là dự đoán dựa trên việc suy luận từ các dữ liệu tổng quát
trên thực tế đã xảy ra theo thời gian (phương thức ngoại suy - the extrapolation method).
Trong phương thức chứng minh, từ các nhân tố có ảnh hưởng tới các giá trị tương
lai, ta xây dựng một hàm tương quan. Từ đó, ta có thể dự đoán giá trị tương lai khi có giá
trị các nhân tố ảnh hưởng.
Trong phương thức ngoại suy, các dữ liệu tổng quát trên thực tế đã xẩy ra thường
biến thiên theo một quy luật nhất định. Bằng việc thu thập dữ liệu đã xẩy ra trong thời
gian dài, ta tìm ra quy luật biến thiên và từ đó, suy luận giá trị tương lai se xẩy ra
83
Giới thiệu bài toán đự đoán mật độ rầy nâu tên cây lúa
Như đã nói ở trên, sâu rầy nâu thường tập trung gây hại trên diện rộng ở một số thời
kỳ nhất định của vụ lúa. Bài toán đặt ra là chúng ta muốn dự đoán thời kỳ sâu gây hại
nặng nhất để có biện pháp phòng trừ thích hợp.
Hướng giải quyết
Để tìm được hướng giải quyết, ta nghiên cứu vòng đời, quy luật phát sinh gây hại của
rầy nâu và các yếu tố liên quan. Ta đã biết, qui luật phát sinh và mức độ gây hại của Rầy
nâu liên quan nhiều đến yếu tố sinh cảnh. Có hai yếu tố chính ảnh hưởng đến vòng đời và
mức độ gây hại của rầy nâu là: nhiệt độ và độ ẩm. Qua tài liệu thống kê, mặc dù mật độ
rầy nâu gây thiệt hại ở từng thời kỳ qua từng năm là có quy luật, song rất khó để xác định
được hàm tuyến tính để dự đoán mật độ rầy nâu gây hại trong thời gian tới một cách
chính xác chỉ bằng phương pháp mô hình hoá thống kê thông thường. Phương pháp dùng
ngôn ngữ WAVE để mô phỏng hành vi của Rầy từ đó tạo ra các dữ liệu thống kê theo
thời gian được đề xuất sử dụng rất hữu hiệu.
5.2.2. Chi tiết bài toán
Để đơn giản, coi nhiệt độ và độ ẩm là tham số theo ngày – tức là được cập nhật hàng
ngày.
Môi trường:
Môi trường trong bài toán này là ruộng lúa lớn. Môi trường được chia ra thành lưới
ô vuông, mỗi ô vuông ứng với một node, giữa các node cạnh nhau có link nối với nhau
thể hiện chúng tiếp giáp với nhau. Hàng ngày, số lượng lúa trong mỗi node sẽ tăng theo
một lượng nhất định. Rầy nâu đầu tiên sẽ xuất hiện trên khu vực giữa của lưới. Sau đó nó
sẽ lan rộng ra các node xung quanh, mỗi ngày lan được tối đa một node.
Tại mỗi node, ta định ra một số tham số sau:
• Nraytt: số lượng rầy trưởng thành trên 1 node
84
• Ntrung: số lượng trứng rầy trong 1 node
• Nlua: số lượng đơn vị thức ăn cho rầy trong 1 node
Mỗi Đối tượng Rầy có những tham số sau:
• Tuổi (tính theo ngày):
o Tuổi <14: dưới dạng trứng
o 14<Tuổi <32:rầy non
o Tuổi >32: rầy trưởng thành
• Di chuyển: Nếu node bên cạnh có Nlua lớn và Nraytt ít thì sẽ di chuyển đến node
đó. Nếu không nó sẽ ở lại node hiện tại đợi đến ngày tiếp theo.
• Ăn:
o rầy non ăn 1lúa/ngày
o rầy trưởng thành ăn 2 lúa/ngày
• Đẻ: rầy trưởng thành đẻ 8 trứng / ngày
• Chết: Rầy chết khi xảy ra các trường hợp sau
o Tuổi >60
o Nlua tại node hiện tại bằng 0 và nó cũng không di chuyển được vì xung
quanh không đạt được đủ điều kiện di chuyển.
Thuật toán
85
Với hệ thống:
86
Khởi tạo Nlua trên các node bằng 100
Khởi tạo thời gian Ntime bằng 1. Cứ sau một khoảng thời gian, ta sẽ tăng Ntime lên
1. Ntime tăng đến 110 (gần 4 tháng cho một vụ lúa).
Song song với việc tăng Ntime, ta sẽ tăng thêm Nlua ở mỗi node thêm một lượng
nào đó.
Cách thể hiện của chương trình
Chúng ta sẽ sử dụng hệ thống đi theo lượt. Cứ mỗi khi chạy xong một bước, chuỗi
wave rầy sẽ phải tạm dừng lại đợi chuỗi wave tăng Ntime và Nlua chạy thì mới tiếp tục
chạy tiếp.
87
CHƯƠNG 6. 3D VÀ THỰC TẠI ẢO
6.1. Giới thiệu công nghệ 3D
6.1.1. Công nghệ 3D
Các ứng dụng đồ họa thường thấy trên tivi hoặc trên máy tính thực ra chỉ là tập
hợp của các bức ảnh hai chiều. Các bức ảnh này, chỉ đưa ra hình chiếu của vật thể theo
một góc nào đó. Để theo dõi được hết vật thể, chúng ta cần chụp lại một số lượng lớn ảnh
hai chiều. Điều này đã gây nên sự hạn chế khác lớn của con người với vật thể được quan
sát. Công nghệ này được gọi là công nghệ 2D.
Ví dụ, nếu bạn muốn mua một chiếc xe đạp, bạn ghé thăm một trang web bán xe đạp
và tìm chiếc xe mà mình ưng ý. Tuy nhiên, trang web này chỉ có thể đưa cho bạn các
thông tin về chiếc xe và một số hình ảnh chụp được về nó.
Hình 6-1.Xe đạp được thể hiện với công nghệ 2D
88
Công nghệ 3D ra đời đã tạo ra một sự biến đổi to lớn giúp con người có thể quan
sát vật thể dưới dạng 3 chiều. Bạn có thể quan sát từng chi tiết trên vật thể, có thể quay
mọi hướng tương tự như ngoài đời vậy.
Hình 6-2.Xe đạp được thể hiện với công nghệ 3D
6.1.2. Giới thiệu về Java 3D
Java 3D được phát triển bởi Sun Microsystems. Java 3D thực ra là một giao diện
lập trình ứng dụng cho phép lập trình viên thiết kế và xây dựng các ứng dụng 3D. Chương
trình được viết bằng Java 3D có thể là một chương trình ứng dụng hoặc được nhúng vào
Applet. Các chương trình được viết bằng Java 3D có thể chạy trên bất cứ hệ điều hành
nào có cài đặt máy ảo Java và các thư viện hỗ trợ Java 3D.
6.2. Chương trình GnuPlot
GnuPlot là một chương trình mô phỏng được ứng dụng rộng rãi trong các ngành
khoa học với khả năng đưa ra đồ thị của các hàm và dữ liệu được đưa ra từ dòng lệnh.
89
Gnuplot được phát triển trên nhiều nền tảng khác nhau nên nó có nhiều phiên bản để chạy
trên các hệ thống cài đặt hệ điều hành riêng, do vậy nó chạy được trên Unix, Linux, IBM
OS/2, MS Windows, DOS, Macintosh, VMS, Atari và nhiều hệ điều hành khác.
GnuPlot được thiết kế nhằm mục đích phục vụ cho sinh viên và các nhà khoa học
để trực quan hóa các hàm và dữ liệu toán học, do vậy GnuPlot được phân phối miễn phí.
GnuPlot hỗ trợ vẽ đồ thị dưới dạng 2D và 3D. Nó có thể vẽ được hầu hết các đối
tượng hình học cơ bản và nâng cao như điểm, đoạn thẳng, hình hộp, vec tơ, bề mặt vật
thể, …
Bên dưới là đồ thị hàm sin(x) với x nằm trong khoảng từ -5 đến 5 dưới dạng 2D:
Hình 6-3.Đồ thị hàm sin(x)
Đồ thị được hiển thị dưới dạng 3D của hàm x2 + y2:
90
Hình 6-4.Đồ thị hàm x2 + y2 hiển thị 3D
6.3. Ngôn ngữ VRML
6.3.1. Khái niệm VRML và các phiên bản của VRML
VRML (Virtual Reality Modeling Language) là ngôn ngữ mô hình hóa thực tại ảo,
sử dụng mô hình phân cấp trong việc thể hiện các tương tác với đối tượng của mô hình.
Phiên bản đầu tiên của VRML là 1.0, nó được ra đời vào tháng 10 năm 1994. Các
file VRML 1.0 phải khai báo tại dòng đầu tiên của file nội dung #VRML V1.0 ascii.
Dưới đây là một file VRML 1.0:
91
Sau một thời gian VRML được cải tiến lên phiên bản 2.0 với nhiều ưu điểm hơn so
với 1.0 với các chức năng mạnh mẽ và trở thành một chuẩn phát triển cho các ứng dụng
đồ họa. Các file VRML 2.0 bắt buộc phải có #VRML V2.0 utf8 tại dòng đầu tiên.
#VRML V1.0 ascii
Separator {
Separator{
Material {
diffuseColor 0 1 1
}
Sphere { radius 10 }
}
Transform {
rotation 1 100 8 1
}
Separator {
Transform { translation 0 20 20 }
Material { diffuseColor 0 0 1 }
Sphere { radius 2 }
}
}
92
Ví dụ một một file VRML 2.0:
VRML ra đời nhằm mục đích xây dựng lên một ngôn ngữ internet 3D để phát triển
đồ họa 3D trên web.
6.3.2. Ngôn ngữ VRML
Các file VRML có phần mở rộng *.wrl, *.wgz, *.wrz. Trong đó wrl là định dạng
chuẩn, còn hai định dạng còn lại là các định dạng nén của VRML.
Thực chất các file VRML chỉ là các file văn bản nhưng nó được sắp xếp theo một
trật tự và quy tắc nhất định để mô tả về vật thể trong thế giới 3D.
#VRML V2.0 utf8
Transform {
translation -4 4 0
children
Transform {
rotation 0 1 1 0
children
Shape {
appearance
Appearance {
material
Material {
diffuseColor 1 0 0
}
}
geometry
Cylinder {
}
}
}
}
93
Một file VRML được cấu tạo từ các nút cơ bản. Các nút cơ bản này là các khối
hình học cơ sở dùng để tạo nên thế giới 3D. Các đối tượng hình học này bao gồm: hình
hộp (Box), hình trụ (Cylinder), hình nón (Cone), hình cầu (Sphere), …
Tọa độ trong VRML được quy ước như hình vẽ:
Với VRML 1.0, để vẽ một hình cầu với bán kính là 10, chúng ta chỉ cần khai báo:
Sphere { radius 10 }
Hình 6-6.Khối cầu với bán kính 10 trong VRML
VRML có các phép biến đổi là: phép quay, phép dịch chuyển, phép tỉ lệ.
x
y
z
Hình 5-5.Tọa độ trong VRML 6
94
Phép quay (Rotation): được sử dụng để cho phép quay trong không gian 3 chiều.
Cú pháp của phép quay: rotation x y z a – với x, y, z tương ứng là ba trục, a là góc quay.
Phép dịch chuyển (Translation): dịch chuyển đối tượng tới vị trí bất kỳ trong
không gian. Cú pháp của phép dịch chuyển: translation x y z - với x, y, z là các toạ độ
theo ba trục tương ứng.
Phép tỉ lệ (Scale): được hiểu như phép đồng dạng, cho phép nhân đối tượng với
các tỷ lệ khác nhau. Cú pháp của phép tỉ lệ: scale x y z - trong đó x, y, z là tỉ lệ theo ba
trục tương ứng.
Ba loại biến đổi trên được sử dụng bên trong nút Transform.
Ví dụ:
Transform {
translation 1 1 1
rotation 0 1 0 0.78
scale 2 1 2
}
6.4. Sử dụng Wave và GnuPlot
6.4.1. Giới thiệu chung
Trong các chương trước, chúng ta đã nói về việc sử dụng lưới thực địa trong môi
trường 2D. Nếu chúng ta thêm vào mỗi node giá trị Nodal z lưu giữ về độ cao, chúng ta
có thể làm việc được với môi trường 3D, đặc biệt là việc mô phỏng các địa hình động với
sự trợ giúp của các chương trình hiển thị đồ họa 3D, trong đó có GnuPlot.
95
6.4.2. Đọc file và tạo KN
Với sự trợ giúp của chương trình đọc file, ta sẽ lấy được tọa độ (x, y, z) tại mỗi
node. Từ đó ta sẽ có được tập các giá trị đầu vào để tạo KN. Việc tạo KN hoàn toàn giống
như tạo trong môi trường 2D nhưng chỉ khác một điểm là chúng ta có thêm một biến
Nodal Nz lưu giữ chiều cao (tọa độ z). Với sức mạnh của wave, chúng ta có thể lưu giữ
KN trên một hoặc nhiều máy, từ đó tạo điều kiện tốt cho việc xử lý song song trên nhiều
máy trong việc cập nhật hoặc duyệt KN để hiển thị file. Phần code tạo KN minh họa xin
xem thêm ở phần phụ lục A.
6.4.3. Cập nhật dữ liệu
Việc cập nhật dữ liệu có thể tiến hành hết sức đơn giản. Chúng ta chỉ việc thay đổi
giá trị độ cao bằng cách nhảy đến node có tọa độ (x-y) và thay đổi giá trị Nz(z) tương
ứng.
6.4.4. Duyệt KN và tạo file đầu vào cho GnuPlot
Việc duyệt KN có thể tiến hành bằng cách đi lần lượt qua từng node trong KN từ trái
qua phải, từ dưới lên trên. Cứ đi đến đâu, ta lưu ra giá trị x, y, Nz tương ứng. Nếu KN
phân tán trên nhiều máy, ta có thể làm tăng hiệu suất duyệt bằng cách sử dụng nhiều bộ
xử lý trên nhiều máy cùng duyệt KN một cách song song. Dữ liệu sau khi duyệt xong sẽ
trở thành đầu vào cho chương trình tạo file đầu vào cho GnuPlot. Phần hiển thị sẽ được
trình bày sau trong chương sau.
6.5. Thực tại ảo
6.5.1. Giới thiệu chung
Việc mô phỏng các đối tượng 3d trên máy tính ngày càng phổ biến. Các ngôn ngữ
hỗ trợ cho việc hiển thị cũng phát triển không ngừng. VRML là một trong những ngôn
ngữ hỗ trợ như thế. Trong mục này, chúng ta đề cập đến VRML 1.0. Kết hợp với ngôn
ngữ WAVE, chúng ta có thể mô phỏng được các thực thể 3d trong file VRML trên một
hoặc nhiều máy, tận dụng được sức mạnh xử lý song song và phân tán.
96
6.5.2. Đọc file và tạo KN
Với một chương trình parser VRML, chúng ta có thể dễ dàng đọc được các node
trong file VRML. Những node đó sẽ là đầu vào cho chuỗi wave tạo KN. Chương trình
Wave hiển thị cấu trúc của một file VRML dưới dạng cây. Sau khi tạo được KN từ file
VRML ban đầu, ta có thể tận dụng được sức mạnh của WAVE trong việc xử lý phân tán
trên nhiều máy, cập nhật trong lúc chạy và xử lý một cách song song, từ đó chúng ta đã
biến file VRML từ thực thể tĩnh thành thực thể động.
Ví dụ với 1 file VRML đơn giản:
#VRML V1.0 ascii
Separator
{
Separator
{
Material { diffuseColor 0 1 1}
Sphere { radius 10 }
}
Separator
{
Transform { translation 0 20 20 }
Material { diffuseColor 0 0 1 }
Sphere { radius 2 }
97
}
}
Thuật toán sinh Wave code tạo KN:
98
KN của chúng ta sau khi đọc file và tạo với WAVE
Hình 5-7 biểu diễn KN của Wave khi mô tả cấu trúc của file VRML. Việc duyệt nội
dung hoặc cập nhật file VRML đều rất đơn giản. Để duyệt nội dung một file VRML sau
đó sử dụng WAVE để tạo ra một KN cần phải qua một bước trung gian phân tích cú pháp
file VRML và trình bày dữ liệu của file VRML dưới một cấu trúc dữ liệu bao gồm các nút
và các nhánh con. Cấu trúc dữ liệu sẽ được sử dụng có cấu trúc dạng cây. Khi có cấu trúc
dữ liệu này và dữ liệu phân tích được gán chương trình sẽ lấy dữ liệu ra từ cây và đưa vào
KN một cách dễ dàng.
Chương trình phân tích dữ liệu của file VRML được gọi là parser, hiện tại chương
trình chỉ phân tích các file VRML đơn giản, hỗ trợ các dữ liệu phổ biến trong VRML 1.0.
Chương trình parser được thiết kế với thuật toán như sau:
1
start
3
2
1
2
1
1
2
1
1
1
1
p
Separator
Separator1
Material1 diffuseColor 0 1 1
Radius1 10Sphere1
Separator2
Material1 diffuseColor 0 1 1
Radius2 2Sphere1
Transform translation 0 20 20
1
Hình 6-7.KN dạng cây của file VRML
99
Thuật toán được thể hiện dưới dạng sơ đồ khối:
Bắt đầu
Đọc file VRML
Lấy nội dung file
Kiểm tra xem nội dung file có đúng chuẩn VRML 1.0 hay
không
Nếu không đúng, kết thúc
Nếu đúng chuyển sang bước tiếp theo
Lấy dữ liệu từng thành phần trong nội dung file VRML
Gắn dữ liệu nhận được vào từng nút tương ứng của dữ
liệu hình cây
Kết thúc
100
Nội dung file sau khi được đọc cần được duyệt lại và kiểm tra xem có tuân thủ theo
chuẩn VRML 1.0 hay không. Thuật toán kiểm tra được thiết kế với các dữ liệu trong file
VRML đơn giản, mặc dù chưa thể kiểm tra hết tất cả các trường hợp hợp lệ nhưng thuật
toán cũng đã kiểm tra được các cú pháp phổ biến của VRML 1.0 như tiêu đề file và dấu
kết thúc file. Đoạn chương trình kiểm tra sẽ được viết dưới dạng hàm, kết quả trả về của
hàm là TRUE hoặc FALSE. Nếu kết quả trả về là TRUE, nội dung của file được kiểm tra
là file VRML 1.0. Nếu kết quả trả về là FALSE, nội dung của file không tuân thủ đúng
tiêu chuẩn của file VRML 1.0. Đầu tiên, chúng ta sẽ gán một biến isVRML bằng FALSE,
biến này sẽ được dùng làm giá trị trả về của hàm kiểm tra. Sau đó kiểm tra dòng đầu và
ký tự cuối cùng của file để thay đổi giá trị của biến isVRML. Sau khi kiểm tra xong, hàm
trả về giá trị của isVRML là TRUE hay FALSE. Thuật toán có thể rút gọn bằng cách
kiểm tra đồng thời cả dòng đầu tiên lẫn ký tự cuối cùng để đưa ra kết quả, tuy nhiên, do
Bắt đầu
Đọc file
Lấy nội dung
file
Kết thúc
Lấy dữ liệu từng thành phần
Gắn dữ liệu nhận được và từng nút của cây
Không theo
chuẩn VRML 1.0
Theo chuẩn
VRML 1.0
Hình 6-8.Sơ đồ khối thuật toán Parser
101
trong quá trình duyệt là tuần tự nên ở đây, thuật toán kiểm tra từng điều kiện một sau đó
mới đưa ra kết quả.
Sơ đồ khối của thuật toán:
Bắt đầu
Đặt isVRML = FALSE
Duyệt nội dung file
Kiểm tra dòng đầu tiên của nội dung file
Nếu bắt đầu bằng #VRML V1.0 ascii (không phân
biệt hoa thường), gán isVRML = TRUE
Nếu không gán isVRML = FALSE
Kiểm tra ký tự kết thúc nội dung file VRML
Nếu ký tự là }, gán isVRML = isVRML ∩ TRUE
Nếu không phải là }, gán isVRML = isVRML ∩ FALSE
Trả về giá trị của isVRML
Kết thúc
102
Bắt đầu
isVRML = FALSE
line1 = Dòng đầu của file
endChar = Ký tự cuối cùng của file
line1 == “#VRML
V1.0 ascii”
isVRML = TRUE
Đúng
isVRML = FALSE
Sai
endChar == ‘}’
isVRML = isVRML ∩ TRUE isVRML = isVRML ∩FALSE
Đúng
Sai
Kết thúc
Sơ đồ khối thuật toán kiểm tra một file có phải là VRML hay khôngHình 6-9.Sơ đồ khối thuật toán kiể tra ột file có phải là VR L hay không
103
6.5.3. Cập nhật VRML
Sau khi kiểm tra nội dung của file tuân thủ đúng chuẩn của VRML 1.0, chúng ta cần
phải lấy dữ liệu từng thành phần của file sau đó gắn dữ liệu này vào cấu trúc cây của
chương trình.
Việc cập nhật file VRML rất đơn giản. Chúng ta chỉ cần thêm vào KN những node
tương ứng và cập nhật vào cây cấu trúc. Trong ví dụ dưới đây, chúng ta sẽ làm cho hình
cầu nhỏ quay quanh hình cầu lớn bằng cách thêm thuộc tính rotation cho nó. Node mới sẽ
kết nối với Seperator 2 theo link “1”. Số thứ tự của cách link cũ sẽ được cập nhật tăng lên
1 đơn vị để thể hiện thứ tự mới của các phần tương ứng trong file VRML. Với mỗi ba
giây, chúng ta sẽ cập nhật file một lần với giá trị rotation mới thể hiện việc hình cầu nhỏ
quay xung quanh hình cầu lớn.
104
6.5.4. Duyệt KN và tạo file VRML
Khi chúng ta đã có KN gồm tất cả các node, khâu cuối cùng trước khi hiển thị file
VRML đó là duyệt các node trên KN để đưa ra đầu vào cho chương trình tạo file VRML.
Thuật toán
Material1
Transform2
Separator
Separator1
star
Separator2
t ri l2
4
3
2
1
2
1
1
2
1
1
diffuseColor2 0 1 1
Sphere2
Transform1
Radius2 2
rotation1 0 20 20
Sphere1 Radius1 10
diffuseColor1 0 1 1 Material1
Translation1 0 20 20
1
1
1
1
1
Hình 6-10.KN sau khi thêm node mới
105
6.5.5. Thay đổi cách nhìn
Trong ngôn ngữ VRML, các đối tượng hình học được biểu diễn trong không gian
tại các vị trí đã xác định. Mặc dù là cố định nhưng chúng ta vẫn có thể thay đổi cách nhìn
của các vật thể này theo các hướng khác nhau, phụ thuộc vào việc chúng ta đặt nguồn
sáng ở đâu trong không gian và hướng nhìn của chúng ta từ phía nào. Hình bên dưới mô
tả một cách trực quan hơn về vấn đề này:
106
Để có thể thay đổi cách nhìn trong VRML, chúng ta sử dụng nút Transform và sử
dụng phép một trong các phép biến đổi dịch chuyển, xoay và tỉ lệ. Ban đầu nội dung của
file VRML được chuyển vào thành một KN như bên dưới:
Muốn thay đổi cách nhìn, chúng ta có thể sử dụng một, hai hoặc cả ba phép biến
đổi cùng một lúc. Ở đây chúng ta chỉ sử dụng phép biến đổi translation (dịch chuyển), chỉ
cần thay đổi giá trị của translation, file VRML có thể được nhìn thấy dưới một góc khác:
Separator
diffuseColor 0 1 1 0
Sphere
Transform
Radius 2
translation 0 20 20
Materia
Cách nhìn 1 Cách nhìn 2
Hình 6-11.Hai cách nhìn khác nhau trong VRML
Hình 6-12.Cách nhìn ban đầu
107
6.5.6. Hiển thị trên nhiều máy tính
Ngày nay, tính toán và xử lý song song là vấn đề được quan tâm nhiều nhất. Hiệu
năng của một máy tính dù cao đến đâu cũng chỉ đáp ứng được tối đa một số lượng công
việc nào đó. Tính toán và xử lý song song đem lại hiệu suất cao trong công việc. Để dễ
hình dung, chúng ta có ví dụ cụ thể về con người, với một khối lượng công việc A, theo
mô hình làm việc cũ, một người chỉ có thể làm công việc A, những người con lại không
thể tham gia vào công việc này. Thời gian để một người làm xong A là T. Ngày nay, công
việc A có thể được làm chung bởi một nhóm người, những người này cùng nhau làm công
việc A, thời gian để hoàn thành công việc giảm xuống rất nhiều, nhỏ hơn so với T nhiều
lần, phụ thuộc vào số lượng người tham gia. Như vậy, nhiều người tham gia làm cùng
một công việc sẽ nâng cao hiệu suất, giảm thời gian trễ.
Các tệp tin VRML được thiết kế đơn giản và cấu trúc dữ liệu của tệp tin VRML có
thể hình dung như cấu trúc dữ liệu của một cây với nhiều nhánh (lá) khác nhau. Bình
thường, việc hiển thị các tệp tin VRML cực kỳ đơn giản và nhanh chóng. Tuy nhiên, khi
dung lượng của tệp tin lớn dần, số nhánh tăng lên với số lượng cực kỳ lớn, lúc đó, vấn đề
hiển thị file bắt đầu phát sinh. Bộ nhớ của máy tính cần phải được cấp phát cho chương
trình hiển thị sẽ bắt buộc phải được nâng cấp đủ để hiển thị, bộ vi xử lý phải hoạt động
nhiều và chiếm tài nguyên của máy tính do số lượng đối tượng hình họa cần biểu diễn rất
lớn. Thông thường, các tệp tin VRML có kích thước lớn chiếm rất nhiều tài nguyên của
máy tính để hiển thị được, cũng có nhiều trường hợp không thể hiển thị được các tệp tin
Separator
diffuseColor 0 1 1 0
Sphere
Transform
Radius 2
translation 0 2 2
Materia
Hình 6-13.Một cách nhìn khác
108
có dung lượng lớn này. Như vậy, một máy tính có thể không đảm đương được nhiệm vụ
hiển thị một tệp tin VRML. Mục đích cuối cùng của người sử dụng là làm sao hiển thị
được nội dung này. Trong khi một máy tính là không thể nhưng nhiều máy tính sẽ là có
thể. Dựa vào cấu trúc linh hoạt của tệp tin VRML, chúng ta sẽ phân bổ các nhánh (nút)
trong tệp tin VRML tới các máy tính khác nhau để mỗi máy tính nhận nhiệm vụ hiển thị
từng nhánh. Tổng hợp tất cả các máy tính chúng ta sẽ quan sát được tổng thể nội dung cần
hiển thị của tệp tin VRML.
Trong thực tế, một trường đại học có nhiều cửa ra vào khác nhau, tại mỗi một cửa
ra vào sẽ có một khu vực bảo vệ. Mỗi khu vực bảo vệ chỉ có quyền kiểm soát và quản lý
khu vực của mình. Tất cả các khu vực đều chịu sự quản lý chung của một khu vực bảo vệ
Một máy tính không thể hiển thị được
Máy tính 1 Máy tính 2 Máy tính 3
Nhưng nhiều máy tính có thể hiển thị được
Hình 6-14.Hiển thị trên nhiều máy tính
109
cao nhất, khu vực này quản lý toàn bộ các khu vực khác và có quyền kiểm soát toàn bộ
mọi khu vực trong trường. Vấn đề nảy sinh trong trường này ở chỗ phải làm sao để mỗi
một khu vực khác nhau chỉ có quyền với khu vực đó mà không có quyền tại khu vực
khác, các sự việc tại khu vực này không làm xáo trộn khu vực kia và khu vực bảo vệ cao
nhất biết được việc làm và giải quyết được tại mọi khu vực.
Tương tự trong việc hiển thị tệp tin VRML, giả sử trong một chương trình, một file
VRML bao gồm 3 khu vực hiển thị, chúng ta cần mỗi một máy tính chỉ được nhìn thấy
một phần nội dung là mỗi môt khu vực hiển thị. Nếu để các máy tính đều hiển thị chung
một tệp tin VRML thì các máy này sẽ nhìn thấy được toàn bộ nội dung hình ảnh hiển thị
của tệp tin. Như vậy, vấn đề chưa được giải quyết. Phần trên, chúng ta đã biết, tệp tin
VRML có thể được hình dung việc tổ chức dữ liệu được thực hiện theo dạng cây nên ta
có thể phân chia việc hiển thị theo các nhánh khác nhau. Dựa vào đặc điểm này, chúng ta
sẽ chia từng nhánh, chính là các khu vực hiển thị, cho các máy tính. Mỗi máy tính sẽ chịu
trách nhiệm hiển thị từng nhánh. Do vậy đảm bảo được yêu cầu mỗi máy sẽ chỉ xem được
nội dung hình ảnh hiển thị là một phần hình ảnh của tệp tin VRML. Tại mỗi một máy
tính, công việc cập nhật nội dung cho nhánh đó sẽ không thể ảnh hưởng được tới các
nhánh còn lại, chính vì thế đảm bảo được quyền truy cập cho tệp tin được đặt ra ở trên đối
với một máy tính. Chúng ta sẽ thiết lập một máy tính có thể xem được toàn bộ nội du
Các file đính kèm theo tài liệu này:
LUẬN VĂN-XÂY DỰNG HỆ THỐNG MÔ PHỎNG VÀ THỰC TẠI ẢO SỬ DỤNG NGÔN NGỮ WAVE.pdf
