guitar83vn
New Member
Download miễn phí Đồ án Trí tuệ nhân tạo - Áp dụng thuật toán Heuristic trong game lựa đậu (mô phỏng game line)
MỤC LỤC
TỔNG QUAN 3
1. TÓM TẮT NỘI DUNG ĐỒ ÁN 3
2. CÔNG VIỆC 3
3. NGUỒN GỐC SOURCE CODE CỦA ĐỒ ÁN 3
4. ĐÁNH GIÁ ĐỒ ÁN 4
BÁO CÁO CHI TIẾT 5
1. Giới thiệu về đồ án/game 5
2. Phương pháp/thuật toán TTNT áp dụng vào đồ án (lý thuyết) 5
3. Cài đặt phương pháp/thuật toán TTNT vào đồ án 5
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
TRƯỜNG ĐẠI HỌC NGOẠI NGỮ - TIN HỌC TPHCMKHOA CÔNG NGHỆ THÔNG TIN
ĐỒ ÁN TRÍ TUỆ NHÂN TẠO
ÁP DỤNG THUẬT TOÁN
HEURISTIC
TRONG GAME LỰA ĐẬU
(Mô phỏng game Line)
TÊN NHÓM: LILO
DANH SÁCH THÀNH VIÊN TRONG NHÓM:
NGUYỄN THANH NGỌC LINH 08DH11286 NGUYỄN VŨ LONG 08DH11113
NGUYỄN LÊ NGỌC BẢO KHUYÊN 08DH11353
LÊ THỊ KIỀU HOA 08DH11284
MỤC LỤC
TỔNG QUAN
Tóm tắt nội dung của đồ án
Game Lựa Đậu
- Mô phỏng lại một game thông dụng : Line theo giải thuật Heuristic
- Cách chơi giống game Line , người chơi sẽ phải sắp tối thiểu 5 hạt đậu giống nhau thành một hàng (ngang hay dọc hay chéo) để ghi điểm.
Công việc
Khuyên: mô phỏng game , xây dựng đồ thị
Nguồn gốc source code của đồ án
Source code :
Trong source code này,nhóm đã thay đổi phần giao diện (thay thế hình ảnh,bố trí lại form,thay thế background)
Đánh giá đồ án
Mức độ phức tạp của đồ án:
Thấp Hơi thấp x Trung bình Khá
Rất phức tạp Ý kiến khác ......................................................
Giao diện/đồ họa của đồ án có bắt mắt người chơi hay người dùng không:
không có giao diện xấu hơi xấu tàm tạm
x Dễ nhìn Đẹp Rất đẹp
Ý Kiến Khác ..............................................................................................
Khả năng cuốn hút người dùng hay người chơi:
Nhàm chán x Tàm tạm Hấp dẫn Ly kỳ Chơi là ghiền
Ý kiến khác ................................................................................................
Mức độ phong phú của đồ án:
x Đơn giản Nhiều cấp độ Nhiều tình huống
Nhiều lựa chọn Ý kiến khác ..........................................................
Mức độ học hỏi của nhóm thông qua đồ án:
Không học được gì Học được ít ít x Học được nhiều
Học rất nhiều Ý kiến khác ..........................................................
Đánh giá khác:
Đánh giá của nhóm bạn về môn học này (nếu có)
BÁO CÁO CHI TIẾT
Giới thiệu
Line là một game mini cổ điển được nhiều người chơi ưa thích với cách chơi cực kỳ đơn giản được Microsoft tích hợp trong các hệ điều hành cũ bắt đầu từ Windows 98,Windows XP.
Game Lựa Đậu được xây dựng trên cơ sở của game Line, tuy nhiên hình ảnh và giao diện của game sẽ mang đến cho người chơi một cảm giác mới lạ dựa trên nền một câu chuyện cổ tích rất quen thuộc “Tấm Cám ”
Lựa Đậu thời @
Như thường lệ, hàng năm triều đình có một ngày hội game để các game thủ có dịp trổ tài và để chọn ra một đội tuyển để đi thi đấu với các vương quốc khác. Ngày hội đã sắp tới rồi mà Tấm thì lại rất muốn tham gia nhưng sợ dì ghẻ bắt phải lựa đậu mới cho đi như năm ngoái.Tấm gục mặt xuống bàn phím khóc nức nở. Không ngờ,tay Tấm đụng trúng phím tắt và Bụt Google hiện lên. Như bắt được vàng,Tấm liền hỏi Bụt Google cách để vượt qua thử thách lựa đậu do Dì Ghẻ đặt ra.Bụt liền đưa cho Tấm game Lựa Đậu và dặn: “Để có thể lựa đậu nhanh, hằng ngày con phải bỏ ra một ít thời gian để luyện game này,nhiệm vụ của con là phải sắp ít nhất 5 hạt đậu giống nhau thành một hàng ngang hay hàng dọc, hay chéo thì những hạt đậu đó sẽ tự động biến mất và tự chui vào những hộp đựng riêng biệt.Con cố luyện tập nhé! Chúc con thành công!” Bụt vừa dứt lời thì Dì Ghẻ phát hiện Tấm lên mạng nên đã ngắt kết nối internet nhưng may mắn cho Tấm game Lựa Đậu là game offline. Và kể từ hôm đó, ngày nào Tấm cũng dành một ít thời gian để luyện game với hi vọng vượt qua được thử thách của Dì Ghẻ để đi dự hội.
Phương pháp/thuật toán
Để làm trò chơi Lựa Đậu, đầu tiên phải xác định được đường đi của hạt đậu (khi chọn một hạt đậu và chọn vào một ô trống nào đó trên bảng). Có thể có nhiều cách để xác định đường đi này. Đồ án này sẽ trình bày cách sử dụng thuật toán Heuristic để tìm đường đi của hạt đậu trên bảng
Xây dựng đồ thị
Đưa ma trận cho trước về danh sách các điểm kề theo hình
Sau đó thiết lập danh sách kề bằng cách:
- Lặp xét hết từng điểm trên ma trận
- Tại mỗi điểm chỉ xét có tạo cạnh liên thông với 2 điểm lân cận tiến
Vì thuật toán này có tính lặp nên chỉ xét 2điểm các điểm lân cận trên cũng sẽ được xét và tạo cạnh với điểm đang được xét
Thuật toán Heuristic:
Ý tưởng:
Duyệt dần các điểm trên đồ thị này bằng cách sau khi đi tới 1 điểm, đánh dấu điểm đó đã đi và tiếp tục duyệt các điểm lân cận của điểm đó. Để duyệt những điểm kề của một điểm chúng ta tiến hành lặp để tìm kiếm có điểm hiện tại trong dach sách kề hay không. Heuristic là dựa vào các chỉ số tọa độ hiện tại của điểm hiện tại với điểm đích với mong muốn với bước đi như thế nào đó sẽ là đúng và trùng với bước đi ngắn nhất.
Tuy nhiên không phải mọi trường hợp heuristic cũng sử dụng số bước tính toán là ít nhất, thậm chí đôi lúc đường đi mà thuật heuristic tìm ra còn dài hơn các thuật toán vét cạn khác
Mô phỏng thuật toán
Thực hiện tìm kiếm heuristic trên danh sách
{Điểm s là điểm bắt đầu, điểm f là điểm kết thúc}
push s
pathVisited(s) := 1
isFound := false
while ()
{
pop x
if (x == f)
isFound := true
r := pathVisited(x)+1
}
Thực hiện tìm đường trên đồ thị
if (isFound=True)
{
tim := pathVisited(f)
curPos = f
trace(tim) := curPos
while (pathVisited(curPos)) > 1
{
Lặp tìm điểm x lân cận của curPos thỏa bằng tim-1
if (pathVisited(x) = tim-1)
{
trace(tim-1) := x
curPos := x
tim := tim-1
}
}
}
Kết quả trả về :
Độ dài đường đi : tim
Đường đi : Mảng trace
Demo
1.
2.
3.
4.
5.
6.
7.
8.
9
Kết quả :
Minh họa một trường hợp có chướng ngại vật :
Cài đặt
Các hàm xử lý Stack cơ bản
'---Stack---
Dim stack(99) As Long
Dim curPosStack As Long
Private Sub initStack()
curPosStack = -1
End Sub
Private Function isEmptyStack() As Boolean
If curPosStack = -1 Then
Return True
End If
Return False
End Function
Private Sub pushStack(ByVal lVal As Long)
curPosStack = curPosStack + 1
stack(curPosStack) = lVal
End Sub
Private Function popStack() As Long
If isEmptyStack() = False Then
Dim lRes As Long
lRes = stack(curPosStack)
curPosStack = curPosStack - 1
Return lRes
Else
Return -1
End If
End Function
'-----------
Tìm đường đi ngắn nhất dựa vào bảng ma trận kết quả duyệt bằng Heuristic
Private Sub findPath(ByVal pFrom As Point, ByVal pTo As Point)
'Tìm kiếm sử dụng heuristic
Dim pNext As Point
Dim iCount As Integer
'Khởi tạo thêm các giá trị điểm kề của điểm bắt đầu
For iCount = 0 To 3
pNext.x = pFrom.x + unitStep(iCount).x
pNext.y = pFrom.y + unitStep(iCount).y
If (pNext.x >= 0) And (pNext.x = 0) And (pNext.y <= 9)Then
If (iPixel(pNext.x, pNext.y) < 0) Then
With wWalk
lstGraph1.Items.Add(pos2index(pFrom))
lstGraph2.Items.Add(pos2index(pNext))
End With
End If
End If
Next iCount
'Bắt đầu tìm kiếm từ iFrom
Dim iFrom As Integer
'Điểm đích iTo
Dim iTo As Integer
iTo = pos2index(pTo)
Dim tim As Long
tim = 1
Dim pathVisited(99) As Integer
Dim i As Integer
For i = 0 To 99
pathVisited(i) = 0
Next
iFrom = pos2index(pFrom)
Dim isFounded As Boolean
isFounded = False
Dim iNext As Integer
'Khởi tạo stack
initStack()
'Điểm thêm điểm khởi đầu vào stack
pushStack(iFrom)
Dim curIndex As Integer
Dim curPos As Point
'Mảng lưu ưu tiên hệ số
Dim arrUnit(4) As Integer
pathVisited(iFrom) = 1
Do While isEmptyStack() = False
curInd...