Luận Văn ÁP DỤNG THUẬT TOÁN HEURISTIC TRONG GAME LỰA ĐẬU (Mô phỏng game Line)

TÊN ĐỀ TÀI: ÁP DỤNG THUẬT TOÁN HEURISTIC TRONG GAME LỰA ĐẬU (Mô phỏng game Line)
Information
[TABLE]
[TR]
[TD="width: 5%"][/TD]
[TD="width: 90%"]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

1. 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 hoặc hàng dọc, hoặc 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.



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

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





2.2 Thuật toán Heuristic:
¬¬¬¬
2.2.1 Ý 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

2.2.2 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}
<Khởi tạo stack rỗng>
push s
pathVisited(s) := 1
isFound := false
while (<Nếu stack chưa rỗng>)
{
pop x

if (x == f)
isFound := true

<Hàm heristic chọn các điểm ưu tiên, cho một biến đại diện chung là r>
<push r>
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[/TD]
[/TR]
[/TABLE]



​