Class Project : Generation and Solving Maze (by Simulation)

ที่มาและปัญหา : โครงการนี้เป็นโครงการที่ส่งหุ่นยนต์ออกไปเก็บข้อมูลในเขาวงกต และสามารถเลือกเส้นทางจากจุดเริ่มต้นไปยังทางออกที่เร็วที่สุดได้

วัตถุประสงค์ : สามารถเขียนอัลกอริทึมในการเก็บแผนที่ของเขาวงกต และหาทางออกจากเขาวงกตได้

สมมุติฐาน : หุ่นยนต์สามารถเดินเก็บข้อมูลของเขาวงกต และหาเส้นทางที่เร็วที่สุดในการออกจากเขาวงกต

ขอบเขตการศึกษา : Program Visual Studio

ประโยชน์ที่คาดว่าจะได้รับ : การเรียนรู้ concept พื้นฐานของการเขียนโปรแกรมและ data structure เบื้องต้น

ผลงานวิจัยและทฤษฎีที่เกี่ยวข้อง

Dept First search (DFS)

การค้นหาแบบลึกก่อน(Depth first search) (DFS) เป็นการค้นหาที่กําหนดทิศทางจากรูปของโครงสร้างต้นไม้ ที่เริ่มต้นจากโหนดราก(Root node) ที่อยู่บนสุด แล้วเดินลงมาให้ลึกที่สุด เมื่อถึงโหนดล่างสุด(Terminal node) ให้ย้อนขึ้นมาที่จุดสูงสุดของกิ่งเดี่ยวกันที่มีกิ่งแยกและยังไม่ได้เดินผ่าน แล้วเริ่มเดินลงจนถึงโหนดลึกสุดอีก ทําเช่นนี้สลับไปเรื่อยจนพบโหนดที่ต้องการหาหรือสํารวจครบทุกโหนดแล้วตามรูปที่ 1 การค้นหาแบบลึกก่อนจะมีลําดับการเดิน ตามโหนดดังตัวอักษรที่กํากับไว้ในแต่ละโหนด.

โดย DFS จะมีการค้นหา สามวิธีคือ

• Preordering คือรายการของการจุดที่เป็นจุดเริ่มในการค้นหาแบบลึกก่อน. นี้เป็นวิธีที่กะทัดรัดและเป็นธรรมชาติในการอธิบายความคืบหน้าของการค้นหา การPreordering ของต้นไม้ได้แสดงออกมาใน Polish notation.

• Postordering คือรายการของการจุดที่เป็นจุดสุดท้ายหรือครั้งล่าสุดในการค้นหาแบบลึกก่อน. Postordering ของ ต้นไม้ได้แสดงออกมาใน reverse Polish notation.

• Postordering reverse เป็น reverse ของ postordering เช่นรายการจุดตามลำดับตรงข้ามของการเข้าชมครั้งล่าสุด. เมื่อเริ่มค้นหาในกราฟแบบต้นไม้, postordering reverse จะเหมือนกับ preordering แต่โดยทั่วไปจะแตกต่างกันเมื่อค้นหากราฟธรรมดา. เช่นการค้นหากราฟโดยตรง

Breadth-First search (BFS)

การค้นหาในแนวกว้างก่อน (Breadth-First search) (ฺBFS) เป็นขั้นตอนการหากราฟทั้งหมด ที่โหนดเริ่มต้น (Root) และทำการสำรวจโหนดของเพื่อนบ้าน การค้นหาแบบกว้างก่อนเป็นการกําหนดทิศทางการค้นหาแบบที่ละระดับของโครงสร้างต้นไม้โดยเริ่มจากโหนดราก(ระดับที่ 0) แล้วลงมาระดับที่ 1 จากซ้ายไปขวา เมื่อเสร็จระดับที่ 1 ไประดับที่ 2 จากซ้ายไปขวาเช่นกัน ทําเช่นนี้เรื่อย ๆ จนพบโหนดที่ต้องการตามรูปที่ 2 ลําดับการเดินทางของโหนดเป็นไปตามอักษรที่กํากับไว้บนโหนด

ภาพรวมรายละเอียดโดยรวมของระบบ

จากวัตถุประสงค์ที่ต้องการให้เขียนอัลกอริทึมในการเก็บแผนที่ของเขาวงกต และหาทางออกจากเขาวงกตได้

ดังนั้น เป้าหมายในการสร้างโปรเจคชิ้นนี้ จึงมีอยู่ 2 อย่างด้วยกันคือ

1. การเก็บแผนที่ในเขาวงกตทั้งหมด : ซึ่งในส่วนนี้ จะใช้ DFS ในการเก็บแผนที่
2. การหาเส้นทางในการออกจากเขาวงกต : ซึ่งในส่วนนี้จะใช้ BFS ในการหาเส้นทางเพื่อออกจากเขาวงกต

โดยรูปแบบในการแสดงผล คือการใช้ code python ในการ จำลองการทำงานของอัลกอริทึมทั้งสองออกมา ซึ่งจะออกมาในรูปแบบหน้าต่างโปรแกรม

1. การเก็บแผนที่ในเขาวงกตทั้งหมด

ดังที่ได้กล่าวไปข้างต้น ผู้จัดทำ ได้ใช้วิธีการแบบ DFS หรือ Depth first search ในการเก็บแผนที่เขาวงกต โดยวิธีการทำงาน จะเป็นดังนี้

1. เลือก Cell เริ่มต้น และทำเครื่องหมายว่าสำรวจแล้วส่งไปยัง Stack
2. ในขณะที่ Stack ไม่ว่าง
   • ทำการดึงค่าข้อมูลสุดท้ายของ Cell จาก Stack และทำให้เป็น Cell ปัจจุบัน
   • หาก Cell ปัจจุบัน มีพื้นที่ไปต่อที่ยังไม่ได้สำรวจ
     • ย้ายเซลล์ปัจจุบันไปที่ Stack
     • เลือกเส้นทางที่ยังไม่ได้สำรวจ
     • ลบกำแพงระหว่าง Cell ปัจจุบัน และ Cell ที่ถูกเลือก
     • ทำเครื่องหมายเซลล์ที่ว่าสำรวจแล้วส่งไปยัง Stack

การเก็บแผนที่ โดยใช้อัลกอริทึม DFS

# การสร้างแผนที่จากการใช้ อัลกอริทึม DFS
import pygame
from random import choice

#สร้างขนาดของMaze ที่จะใช้
RES = WIDTH, HEIGHT = 600, 600
TILE = 60
cols, rows = WIDTH // TILE, HEIGHT // TILE

pygame.init()
sc = pygame.display.set_mode(RES)
clock = pygame.time.Clock()

class Cell:
    def __init__(self, x, y):
        self.x, self.y = x, y
        self.walls = {'top': True, 'right': True, 'bottom': True, 'left': True}
        self.visited = False

    def draw_current_cell(self):
        x, y = self.x * TILE, self.y * TILE
        pygame.draw.rect(sc, pygame.Color('saddlebrown'), (x + 2, y + 2, TILE - 2, TILE - 2))

    def draw(self):
        x, y = self.x * TILE, self.y * TILE
        if self.visited:
            pygame.draw.rect(sc, pygame.Color('black'), (x, y, TILE, TILE))

        if self.walls['top']:
            pygame.draw.line(sc, pygame.Color('darkorange'), (x, y), (x + TILE, y), 3)
        if self.walls['right']:
            pygame.draw.line(sc, pygame.Color('darkorange'), (x + TILE, y), (x + TILE, y + TILE), 3)
        if self.walls['bottom']:
            pygame.draw.line(sc, pygame.Color('darkorange'), (x + TILE, y + TILE), (x , y + TILE), 3)
        if self.walls['left']:
            pygame.draw.line(sc, pygame.Color('darkorange'), (x, y + TILE), (x, y), 3)

    def check_cell(self, x, y):
        find_index = lambda x, y: x + y * cols
        if x < 0 or x > cols - 1 or y < 0 or y > rows - 1:
            return False
        return grid_cells[find_index(x, y)]

    def check_neighbors(self):
        neighbors = []
        top = self.check_cell(self.x, self.y - 1)
        right = self.check_cell(self.x + 1, self.y)
        bottom = self.check_cell(self.x, self.y + 1)
        left = self.check_cell(self.x - 1, self.y)
        if top and not top.visited:
            neighbors.append(top)
        if right and not right.visited:
            neighbors.append(right)
        if bottom and not bottom.visited:
            neighbors.append(bottom)
        if left and not left.visited:
            neighbors.append(left)
        return choice(neighbors) if neighbors else False


def remove_walls(current, next):
    dx = current.x - next.x
    if dx == 1:
        current.walls['left'] = False
        next.walls['right'] = False
    elif dx == -1:
        current.walls['right'] = False
        next.walls['left'] = False
    dy = current.y - next.y
    if dy == 1:
        current.walls['top'] = False
        next.walls['bottom'] = False
    elif dy == -1:
        current.walls['bottom'] = False
        next.walls['top'] = False


grid_cells = [Cell(col, row) for row in range(rows) for col in range(cols)]
current_cell = grid_cells[0]
stack = []
colors, color = [], 40

while True:
    sc.fill(pygame.Color('darkslategray'))

    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            exit()

    [cell.draw() for cell in grid_cells]
    current_cell.visited = True
    current_cell.draw_current_cell()
    [pygame.draw.rect(sc, colors[i], (cell.x * TILE + 2, cell.y * TILE + 2,
                                         TILE - 4, TILE - 4)) for i, cell in enumerate(stack)]

    next_cell = current_cell.check_neighbors()
    if next_cell:
        next_cell.visited = True
        stack.append(current_cell)
        colors.append((min(color, 255), 10, 100))
        color += 1
        remove_walls(current_cell, next_cell)
        current_cell = next_cell
    elif stack:
        current_cell = stack.pop()

    pygame.display.flip()
    clock.tick(10)

2. การหาเส้นทางในการออกจากเขาวงกต

ดังที่ได้กล่าวไปข้างต้น ผู้จัดทำ ได้ใช้วิธีการแบบ ฺBFS หรือ Breadth first search ในการค้นหาเส้นทางในการออกจากเขาวงกต โดยวิธีการทำงาน จะเป็นดังนี้

1. เลือก Cell เริ่มต้น และ Cell เป้าหมาย และเพิ่ม Queue กับ root
2. Dequeue Cell จาก Queue
3. ในขณะที่ Queue ไม่ว่าง
   • ย้ายข้อมูล Cell ไปที่ Queue
   • ชี้ ตำแหน่ง root ปัจจุบัน ที่มี Cell อยู่ติดกัน
   • ณ ตำแหน่ง root นั้นได้สำรวจ Cell ติดกันหรือไม่
     • ถ้า Cell ยังไม่ถูกสำรวจแล้ว
       • จะย้ายไปที่ Cell ที่อยู่ติดกัน ใน root นั้น
     • ถ้า Cell ถูกสำรวจ จะวางตำแหน่ง Cell มันถูกสำรวจแล้ว

การหาเส้นทางออกจากเขาวงกต โดยใช้อัลกอริทึม BFS

#การหาเส้นทางในการออกจากเขาวงกตด้วย BFS
from pyamaze import maze,agent,textLabel,COLOR
from collections import deque

def BFS(m,start=None):
    if start is None:
        start=(m.rows,m.cols)
    frontier = deque()
    frontier.append(start)
    bfsPath = {}
    explored = [start]
    bSearch=[]

    while len(frontier)>0:
        currCell=frontier.popleft()
        if currCell==m._goal:
            break
        for d in 'ESNW':
            if m.maze_map[currCell][d]==True:
                if d=='E':
                    childCell=(currCell[0],currCell[1]+1)
                elif d=='W':
                    childCell=(currCell[0],currCell[1]-1)
                elif d=='S':
                    childCell=(currCell[0]+1,currCell[1])
                elif d=='N':
                    childCell=(currCell[0]-1,currCell[1])
                if childCell in explored:
                    continue
                frontier.append(childCell)
                explored.append(childCell)
                bfsPath[childCell] = currCell
                bSearch.append(childCell)
    # print(f'{bfsPath}')
    fwdPath={}
    cell=m._goal
    while cell!=(m.rows,m.cols):
        fwdPath[bfsPath[cell]]=cell
        cell=bfsPath[cell]
    return bSearch,bfsPath,fwdPath

if __name__=='__main__':

    m=maze(10,10)
    # m.CreateMaze(5,4,loopPercent=100)
    m.CreateMaze(loopPercent=10,theme='light')
    bSearch,bfsPath,fwdPath=BFS(m)
    a=agent(m,footprints=True,color=COLOR.blue,shape='square',filled=True)
    b=agent(m,footprints=True,color=COLOR.red,shape='square',filled=False)
    # c=agent(m,5,4,footprints=True,color=COLOR.cyan,shape='square',filled=True,goal=(m.rows,m.cols))
    c=agent(m,1,1,footprints=True,color=COLOR.cyan,shape='square',filled=True,goal=(m.rows,m.cols))
    m.tracePath({a:bSearch},delay=100)
    m.tracePath({c:bfsPath},delay=100)
    m.tracePath({b:fwdPath},delay=100)

    m.run()

เอกสารอ้างอิง

การค้นหาแบบลึกก่อน

https://tni.fandom.com/th/wiki/%E0%B8%81%E0%B8%B2%E0%B8%A3%E0%B8%84%E0%B9%89%E0%B8%99%E0%B8%AB%E0%B8%B2%E0%B9%83%E0%B8%99%E0%B9%81%E0%B8%99%E0%B8%A7%E0%B8%A5%E0%B8%B6%E0%B8%81%E0%B8%81%E0%B9%88%E0%B8%AD%E0%B8%99

การค้นหาในแนวกว้างก่อน

https://tni.fandom.com/th/wiki/%E0%B8%81%E0%B8%B2%E0%B8%A3%E0%B8%84%E0%B9%89%E0%B8%99%E0%B8%AB%E0%B8%B2%E0%B9%83%E0%B8%99%E0%B9%81%E0%B8%99%E0%B8%A7%E0%B8%81%E0%B8%A7%E0%B9%89%E0%B8%B2%E0%B8%87%E0%B8%81%E0%B9%88%E0%B8%AD%E0%B8%99

https://wikkihut.com/breadth-first-traversal/

แนวทางการใช้ DFS และ BFS

• https://www.youtube.com/watch?v=sTRK9mQgYuc
• https://www.youtube.com/watch?v=sTRK9mQgYuc
• https://www.youtube.com/watch?v=Ez7U6jU0q5k
• https://www.youtube.com/watch?v=D14YK-0MtcQ
• https://www.youtube.com/watch?v=abHftC1GU6w
• https://www.youtube.com/watch?v=lyIUnFvYt14
• https://www.youtube.com/watch?v=ZuHW4fS60pc

ผู้จัดทำ

63340700402 นางสาวเมธิณี   แสงประดิษฐ์

• ศึกษา ทฤษฎี Depth-First Search และ Breadth-First search
• ออกแบบ และเขียน Algorithm เพื่อเก็บรายละเอียดของแผนที่ และเส้นทางในการออกจากเขาวงกต โดยใช้ ภาษา python ในการเขียน