TR
NG Đ I H C
ƯỜ
Ạ Ọ NGO I NG - TIN H C
Ữ
Ọ TPHCM
Ạ KHOA CÔNG NGH THÔNG TIN
Ệ
Đ ÁN TRÍ TU NHÂN T O
Ồ
Ạ
Ệ
HU T TOÁN
ÁP D NG T Ụ
Ậ
Ự Ậ
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 NGUY N VŨ LONG NGUY N LÊ NG C B O KHUYÊN LÊ TH KI U HOA
08DH11286 08DH11113 08DH11353 08DH11284
Ễ Ễ Ễ Ị
Ề
M C L C Ụ Ụ
3 TỔNG QUAN ........................................................................................................................................
3 1.Tóm tắt nội dung của đồ án ...............................................................................................................
3 2.Công việc ...........................................................................................................................................
3 3.Nguồn gốc source code của đồ án ....................................................................................................
4 4.Đánh giá đồ án ..................................................................................................................................
5 BÁO CÁO CHI TIẾT .............................................................................................................................
5 1.Giới thiệu ...........................................................................................................................................
6 2.Phương pháp/thuật toán ...................................................................................................................
T NG QUAN
Ổ
1. 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 - Cách ch i gi ng game Line , ng ố gi ng nhau thành m t hàng (ngang ho c d c ho c chéo) đ ghi đi m.
i thu t Heuristic ể ụ ườ ơ ẽ ơ
ả ậ ạ ậ i thi u 5 h t đ u ả ắ ố ể ể i ch i s ph i s p t ặ ặ ọ ố ộ
2. Công vi cệ
Khuyên: mô ph nỏ g game , xây d ng đ th ồ ị
ự
3. Ngu n g c source code c a đ án
ủ ồ
ồ ố
Source code : http://virusvn.com/forum/showthread.php?2275-Source-Game-line
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) ế
4. Đánh giá đ ánồ
x Trung bình Khá - M c đ ph c t p c a đ án: ứ ộ ứ ạ ủ ồ ấ H i th p ơ
ứ ạ
Th pấ 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 ồ ọ ủ ồ ệ ắ ắ ườ ơ ườ
h i x u ơ ấ tàm t mạ
Đ pẹ
không: không có giao di nệ x uấ x D nhìn R t đ p ấ ẹ ễ Ý Ki n Khác .............................................................................................. ế
- Kh năng cu n hút ng i dùng hay ng ả ườ
i ch i: ơ ườ H p d n ấ x Tàm t mạ ẫ Ly kỳ Ch i làơ
ố Nhàm chán ghi nề Ý ki n khác ................................................................................................ ế
ộ Nhi u tình hu ng ề ố
- M c đ phong phú c a đ án: ủ ồ Nhi u c p đ ề ấ Ý ki n khác .......................................................... ế ọ ứ ộ x Đ n gi n ả ơ Nhi u l a ch n ề ự
ứ ộ ọ ỏ ủ ồ
- M c đ h c h i c a nhóm thông qua đ án: c gì H c đ x H c đ ọ ượ ọ ượ c nhi u ề
c ít ít Ý ki nế
- Đánh giá khác: Đánh giá c a nhóm b n v môn h c này (n u có)
Không h c đ ọ ượ H c r t nhi u ề ọ ấ khác ..........................................................
ủ ế ề ạ ọ
BÁO CÁO CHI TI TẾ
1. Gi
ớ
i thi u ệ
ộ c nhi u ng ề ơ ư ườ ượ
ượ ả ơ ớ i ch i a thích v i ổ ể c Microsoft tích h p trong các h đi u hành ệ ề ợ
Line là m t game mini c đi n đ cách ch i c c kỳ đ n gi n đ ơ ự cũ b t đ u t ắ ầ ừ
ườ ế ơ
d a trên n n m t câu chuy n c tích r t quen thu c Windows 98,Windows XP. Game L a Đ u đ ậ ự ệ ủ ộ ơ ở ủ ượ hình nh và giao di n c a game s mang đ n cho ng ả m i l ớ ạ ự c xây d ng trên c s c a game Line, tuy nhiên i ch i m t c m giác ộ ả ộ “T m Cám ” ấ ự ẽ ệ ổ ề ấ
L a Đ u th i @ ậ
ự
ờ
ộ ệ ư ườ
ị ể ể ớ ộ ể ộ ộ Nh th ủ
ấ ng qu c khác. ố ọ ắ ớ ồ ng l ổ Ngày h i đã s p t ộ
ợ ẻ ắ
ờ ắ
ấ
ử ư ấ ề ụ ề ả ự ậ ở ứ ư ắ ượ ậ ụ c vàng,T m li n h i B t Google cách đ ỏ ụ ư
ậ ự ể ằ
ấ ả ỏ ấ ể ự ậ ệ ặ ể ệ ờ
ộ ọ
đ ng bi n m t và t ự ế ấ ộ
ữ ụ ừ ố
ư ệ ạ
ẽ ự ộ ệ ậ ấ ự ể ừ ấ ậ
c th ượ ượ ệ ộ ớ
, 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 ấ ể i r t mu n tham gia i r i mà T m thì l v ố ươ ạ ấ 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 ặ ư ụ ấ ớ t và xu ng bàn phím khóc n c n . Không ng ,tay T m đ ng trúng phím t ố ể B t Google hi n lên. Nh b t đ ệ ụ 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 ho c hàng d c, ho c chéo thì nh ng ặ ặ ố ậ chui vào nh ng h p đ ng riêng h t đ u đó s t ạ ậ ự i thì Dì t.Con c luy n t p nhé! Chúc con thành công!” B t v a d t l bi ứ ờ ệ 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 ắ ắ ế ố ẻ ấ hôm đó, ngày nào T m cho T m game L a Đ u là game offline. Và k t cũng dành m t ít th i gian đ luy n game v i hi v ng v ử t qua đ ể ọ thách c a Dì Gh đ đi d h i. ự ộ ờ ẻ ể ủ
2. 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 trên b ng ủ 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). ọ ạ ậ ả ng đi này. Đ án này s trình bày cách Có th có nhi u cách đ xác đ nh đ ườ ể s d ng thu t toán Heuristic đ tìm đ ườ ử ụ ơ ự ộ ạ ậ ị ể ồ ủ ạ ậ ậ ả
2.1 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 ỉ ế ừ ể ỗ
ậ
ặ
ỉ
ậ
ể ạ
ể
ớ
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 đ ượ
ặ ạ ạ ạ thông v i 2 đi m lân c n ti n ế ể ậ ớ
2.2 Thu t toán Heuristic :
ậ
2.2.i Ý t
ng:
ưở
ằ ể Duy t d n các đi m trên đ th này b ng cách sau khi đi t ồ ị
ấ ệ ệ ầ ể ớ ể
ệ ể ề ủ ậ ủ ặ ể ế ể ể ế
Heuristic là d a vào các ch s ự
ế ụ ộ i trong dach sách k hay không. ể
ề i c a đi m hi n t ệ ạ ớ ể ố
i v i đi m đích v i mong mu n v i b ớ c đi ng n nh t. ắ ấ
ọ ườ ử ụ ả
ng h p heuristic cũng s d ng s b ậ ậ
2.2.ii Mô ph ng thu t toán ỏ
ậ
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 ệ ạ ớ ướ c t a đ hi n t ể ộ ệ ạ ủ ọ đi nh th nào đó s là đúng và trùng v i b ư ế ớ ướ ẽ c Tuy nhiên không ph i m i tr ố ướ ợ 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 ậ ạ ơ
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}
pop x
if (x == f)
isFound := true
r>
ọ
ể ư
ệ
ế
ạ
ộ
}
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
} } }
tim
K t qu tr v : ế ả ả ề ng đi : Đ dài đ ườ ộ M ng trace Đ ng đi : ả ườ
2.2.iiiDemo
1.
2.
3.
4.
5.
6.
7.
8.
9
K t qu : ế ả
ng h p có ch ng ng i v t : Minh h a m t tr ọ ộ ườ ợ ướ ạ ậ
3. 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 ắ ệ ằ ấ ự ế ả ả ậ
ử ụ
ế
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 <= 9) And (pNext.y >= 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
iFrom
ắ ầ
ế
'B t đ u tìm ki m t ừ Dim iFrom As Integer
'Đi m đích iTo
ể
ườ Private Sub findPath(ByVal pFrom As Point, ByVal pTo As Point) 'Tìm ki m s d ng heuristic
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 curIndex = popStack()
If curIndex = iTo Then isFounded = True Exit Do End If
'---Hàm heuristic--- curPos = index2pos(curIndex)
ị
ớ
ố
ầ
ằ
'Tính toán v trí pTo n m trong ph n g c nào so v i curPos ' | '---O--------------> X ' | 1 | 2 ' |-----curPos---- ' | 4 | 3 ' | ' Y
If (curPos.x >= pTo.x) And (curPos.y >= pTo.y) Then 'Góc 1 If (curPos.x - pTo.x) >= (curPos.y - pTo.y) Then ' |x |2 ' |1----x----4 ' | |3
arrUnit(4) = 1 arrUnit(3) = 0 arrUnit(2) = 2 arrUnit(1) = 3 Else ' | x|1 ' |2----x----3 ' | |4
arrUnit(4) = 0 arrUnit(3) = 1 arrUnit(2) = 3 arrUnit(1) = 2 End If ElseIf (curPos.x < pTo.x) And (curPos.y > pTo.y) Then 'Góc 2 If (pTo.x - curPos.x) >= (curPos.y - pTo.y) Then ' | |2 x ' |4----x----1 ' | |3
arrUnit(4) = 3 arrUnit(3) = 0 arrUnit(2) = 2 arrUnit(1) = 1 Else ' | |1x ' |3----x----2 ' | |4 arrUnit(4) = 0 arrUnit(3) = 3 arrUnit(2) = 1 arrUnit(1) = 2 End If ElseIf (curPos.x <= pTo.x) And (curPos.y <= pTo.y) Then 'Góc 3 If (pTo.x - curPos.x) >= (pTo.y - curPos.y) Then ' | |3 ' |4----x----1 ' | |2 x
arrUnit(4) = 3 arrUnit(3) = 2 arrUnit(2) = 0 arrUnit(1) = 1 Else ' | |4 ' |3----x----2 ' | |1x arrUnit(4) = 2 arrUnit(3) = 3 arrUnit(2) = 1 arrUnit(1) = 0 End If ElseIf (curPos.x > pTo.x) And (curPos.y < pTo.y) Then 'Góc 4 If (curPos.x - pTo.x) >= (pTo.y - curPos.y) Then
' | |3 ' |1----x----4 ' |x |2 arrUnit(4) = 1 arrUnit(3) = 2 arrUnit(2) = 0 arrUnit(1) = 3 Else ' | |4 ' |2----x----3 ' | x|1 arrUnit(4) = 2 arrUnit(3) = 1 arrUnit(2) = 3 arrUnit(1) = 0 End If End If
For iCount = 4 To 1 Step -1 pNext.x = curPos.x + unitStep(arrUnit(iCount)).x pNext.y = curPos.y + unitStep(arrUnit(iCount)).y If isHaveCanh(curIndex, pos2index(pNext)) = True Then If pathVisited(pos2index(pNext)) = 0 Then pushStack(pos2index(pNext)) pathVisited(pos2index(pNext))= pathVisited(pos2index(curPos)) + 1 End If End If Next
ế
'---H t hàm Heuristic--- Loop
tim = pathVisited(pos2index(pTo)) If isFounded = True Then 'N u tìm đ
ng đi
c đ ượ ườ
ế
trace.iLen = tim ReDim trace.pos(trace.iLen)
curIndex = iTo
Do While pathVisited(curIndex) > 1 For iCount = 0 To lstGraph1.Items.Count - 1 If (lstGraph1.Items(iCount) = curIndex) Or
ề ể
(lstGraph2.Items(iCount) =curIndex) Then i ệ ạ
'Tìm đi m k đi m hi n t ể If lstGraph1.Items(iCount) = curIndex Then iNext = Val(lstGraph2.Items(iCount)) Else iNext = Val(lstGraph1.Items(iCount)) End If
If pathVisited(iNext) = tim - 1 Then trace.pos(tim - 1) = index2pos(iNext) curIndex = iNext tim = tim - 1 Exit For End If
End If Next iCount Loop
ế
ể
ẽ ờ
'Ti n hành v c di chuy n Dim iIndex As Integer For iCount = 1 To trace.iLen - 1 iIndex = pos2index(trace.pos(iCount)) pPixel(iIndex).Image = imgGo.Images.Item(0) Next Else trace.iLen = 0 Dim iX As Integer Dim iTmp As Integer
'Xóa c nh trong list ạ iTmp = pos2index(pFrom) For iX = lstGraph1.Items.Count - 1 To 0 Step -1 If (lstGraph1.Items(iX) = iTmp) Or (lstGraph2.Items(iX) = iTmp) Then lstGraph1.Items.RemoveAt(iX) lstGraph2.Items.RemoveAt(iX) End If Next End If End Sub
