Edit post

Title

上網睇過資料，A*係目前最高效率既search / path finding algorithm。成條algorithm既重點係列舉下一步既可能性，再假設自己係下一步入面，比較終點距離同埋上一步距離，最後計算得失。

以人類既角度解釋既話，比較似係一個人想走出迷宮，佢會一直望住個終點，睇下行邊步離終點直線距離會係最近。

當然，個heuristic function要根據唔同問題去改變，例如係呢個case，簡單既直線距離就夠。

本身我學校學過DFS、BFS、BST、Dijkstra，冇理由唔去識埋呢隻algorithm。

我想試下整好耐，但一直冇機會去做，但呢兩日終於無聊得濟斷斷續續搞掂佢。

#!/usr/bin/env python3
    from time import time
    from random import randint

SIZE = 20
    BLOCKS = 100

class AStarGrid():

def __init__(self):
            self.grid = AStarGrid.generate_grid()

def render_grid(self, path=None, goal=None):
            for y in range(SIZE):
                for x in range(SIZE):
                    p = (x, y,)
                    if path is not None and p in path:
                        print((len(path) - path.index(p)) % 10, end="")
                    elif self.grid[y][x]:
                        print("X", end="")
                    elif p == goal:
                        print("G", end="")
                    else:
                        print(".", end="")
                print()

def generate_neighbors(self, p):
            n = []
            if p[0] - 1 >= 0:
                n.append((p[0] - 1, p[1],))
            if p[0] + 1 <= SIZE - 1:
                n.append((p[0] + 1, p[1],))
            if p[1] - 1 >= 0:
                n.append((p[0], p[1] - 1,))
            if p[1] + 1 <= SIZE - 1:
                n.append((p[0], p[1] + 1,))
            for cell in n:
                if self.grid[cell[1]][cell[0]]:
                    n.remove(cell)
            return n

def find_path_from(self, start, goal):
            open_list, closed_list = [start], []
            g, f, h, came_from = {}, {}, {}, {}
            g[start] = 0
            f[start] = AStarGrid.distance(start, goal)
            h[start] = f[start]
            while open_list:
                parent = min(open_list, key=f.get)
                if parent == goal:
                    return AStarGrid.reconstruct_path(came_from, goal)
                open_list.remove(parent)
                closed_list.append(parent)
                for neighbor in self.generate_neighbors(parent):
                    if neighbor in closed_list:
                        continue
                    tmp_g = g[parent] + AStarGrid.distance(parent, neighbor)
                    better = False
                    if neighbor not in open_list:
                        open_list.append(neighbor)
                        better = True
                    elif tmp_g < g[neighbor]:
                        better = True
                    if better:
                        came_from[neighbor] = parent
                        g[neighbor] = tmp_g
                        h[neighbor] = AStarGrid.distance(neighbor, goal)
                        f[neighbor] = g[neighbor] + h[neighbor]

@staticmethod
        def generate_grid():
            grid = [[False] * SIZE for _ in range(SIZE)]
            for i in range(BLOCKS):
                x, y = randint(0, SIZE - 1), randint(0, SIZE - 1)
                grid[y][x] = True
            return grid

@staticmethod
        def distance(p1, p2):
            return (((p1[0] - p2[0]) ** 2) + ((p1[1] - p2[1]) ** 2)) ** 0.5

@staticmethod
        def reconstruct_path(came_from, current_node):
            path = []
            while current_node in came_from:
                current_node = came_from[current_node]
                path.append(current_node)
            return path

if __name__ == "__main__":
        start = (0, 0,)
        goal = (19, 19,)
        grid = AStarGrid()
        path = grid.find_path_from(start, goal)
        grid.render_grid(path, goal)

結果

1.X.X...........X...
    2..X.XX.X...X.......
    3XX...X...........X.
    4789XX....X.........
    56X012...X.....X....
    .XXX.34..........X..
    X..X..5.....X..X....
    .....X678X..X.......
    ........9........XX.
    ..X.XX.X0..X.....X..
    .X......1.X...X.X...
    X.......2X..X.XX....
    .....XX.3456X.X..X.X
    .X....X.X..7890....X
    ..XX..X...XXX.1XX...
    X......X.....X2XX...
    ....XX....X...3XX...
    X.X.X.........456789
    .....X........X...X0
    ...XX..XX.X....X...G
    ./astar.py  0.07s user 0.01s system 98% cpu 0.077 total

同埋，唔好overestimate個cost，否則個result唔會再係shortest path。

Content

Password

Edit post

Preview

Powered by Simple Blog