A*길찾기 소개(튜토리얼)

This is part 3 of a series on bot programming originally published on the Coder One blog.
Part 1: Getting started with the game environment
Part 2: Creating our first agent

A*길찾기(또는 A*검색) 알고리즘은 환경에서 두 점 사이의 가장 짧은 경로를 찾는 유행 기술이다.
본 강좌에서 우리는 Python에서 A*길 찾기 알고리즘을 실현하여 우리의 에이전트가 Dungeons and Data Structures environment의 목표 목적지로 내비게이션하는 것을 도울 것이다.서명Part 1을 해서 설치하거나 Part 2 간단한 로봇을 만들 수 있도록 하세요.

우리는 A*길찾기 알고리즘을 사용하여 기사가 목적지에 도착하는 가장 짧은 경로를 찾을 수 있도록 도울 것이다.
여기서 우리는 길을 찾는 배후의 이론을 깊이 연구하지 않을 것이다.대신 다음과 같은 유용한 리소스를 확인하십시오.

길 찾기 뒤의 직감을 느껴라: Introduction to A* Pathfinding[1]

우리가 실현할 알고리즘 위조 코드: Amit's thoughts on pathfinding[2]

A* 탐색 개요

시작 노드가 제공된 경우 * 탐색 방법은 다음과 같습니다.

인접 노드 검색

시작 노드에서 목적지에 도착하는 데 필요한 비용과 인접 노드에서 목적지

까지의 가장 저렴한 경로에 대한 추정 비용에 따라 총 비용(즉 소요 시간, 이동 타일 등)을 분배한다.
A*의 목표는 최소화입니다.
f(n)=g(n)+h(n)
어디:

n은 경로의 현재 노드

입니다.

g(n)는 시작 노드에서 n까지의 경로의 비용이다

n(n): n에서 목표 단원으로 이동하는 비용을 추정하는 계발식 함수

우리 환경에서 f(n), g(n)와 h(n) 값의 예시.

What's the difference between A* and Dijkstra's algorithm?
The A* search algorithm can be considered an application of Dijkstra's algorithm, which adds heuristics to guide its search and achieve better performance. If you set the heuristic function h(n) equal to 0, the A* algorithm essentially boils down to Dijkstra's algorithm.

개시하다

목표는 에이전트가 환경 지하도와 데이터 구조에서 지정된 목적지로 성공적으로 이동하도록 돕는 것입니다.

Part 1 및 Part 2에 대한 관심이 계속되면 프로젝트를 손쉽게 관리할 수 있도록 재구성할 것입니다.
먼저 작업 디렉토리에 세 개의 파일을 생성합니다.

__init__.py - 주 환경에서 호출

from . import my_agent

def agent():
    return my_agent.Agent()

my_agent.py - 우리 대리인의 행위 논리를 소지

from .helpers import *

class Agent:

    def __init__(self):
        '''
        Place any initialization code for your agent here (if any)
        '''
        self.pending_actions = []

    def next_move(self, game_state, player_state):
        '''
        This method is called each time your Agent is required to choose an action
        '''

        pass

helpers.py - 모든 지원 함수와 클래스를 저장합니다

.

보조 함수

우리는 일부 보조 함수를 정의할 것이다. 이 함수들은 뒤의 A*길 찾기 알고리즘에서 유용할 것이다.helpers.py 파일에 추가합니다.

Note: For consistency in the following sections, we'll refer to tiles as an (x,y) location of any tile on the map, and nodes as specific instances of the Node class object (which we'll cover later on). A node will contain a location property equivalent to a tile.

너의 이웃을 자유롭게 하다

다음에 검색할 배열의 목록을 가져오는 데 사용할 배열을 지정합니다.

# given our current location, return only surrounding tiles that are free
def get_free_neighbors(game_state, location):

    x, y = location
    neighbors = [{(x-1, y): 'l'}, {(x+1, y): 'r'}, {(x, y-1): 'd'}, {(x, y+1): 'u'}]
    free_neighbors = []

    for neighbor in neighbors:
        for tile, direction in neighbor.items():
            if game_state.is_in_bounds(tile):
                if game_state.is_occupied(tile):
                    # check if this tile contains treasure or ammo
                    if game_state.entity_at(tile) == 't' or game_state.entity_at(tile) == 'a':
                        free_neighbors.append({tile:direction})
                else:
                    free_neighbors.append({tile:direction})

    return free_neighbors

보물을 얻다

우리는 우리의 목표 지점을 어떤 보물이 탄생하는 지점으로 만들 것이다.(또는treasure를 ammo로 전환하여 스파이에게 지도 주위에서 탄약을 줍게 한다.

# finds treasure, if any
def get_treasure(game_state):

    treasure = game_state.treasure

    if treasure:
        return treasure[0] # return first treasure on the list

맨해튼 거리

앞서 언급한 바와 같이 A* 길찾기 알고리즘은 계발식 함수 $h(n)$가 인도합니다.우리가 사용할 계발식 함수는 맨해튼 거리입니다.

Source
맨해튼 거리는 현재 노드와 목적지 사이의 거리의 근사치이다. 왜냐하면 어떤 장애도 고려하지 않기 때문이다.완벽하지는 않지만 우리의 목적을 위해 역할을 발휘할 것이다.

맨해튼의 거리는 결코 우리 도로의 장애를 설명할 수 없다

def manhattan_distance(start, end):

    distance = abs(start[0] - end[0]) + abs(start[1] - end[1])

    return distance

A* 알고리즘

다음은 우리가 [2]에서 실현할 위조 코드입니다.

OPEN = priority queue containing START
CLOSED = empty set
while lowest rank in OPEN is not the GOAL:
  current = remove lowest rank item from OPEN
  add current to CLOSED
  for neighbors of current:
    cost = g(current) + movementcost(current, neighbor)
    if neighbor in OPEN and cost less than g(neighbor):
      remove neighbor from OPEN, because new path is better
    if neighbor in CLOSED and cost less than g(neighbor): ⁽²⁾
      remove neighbor from CLOSED
    if neighbor not in OPEN and neighbor not in CLOSED:
      set g(neighbor) to cost
      add neighbor to OPEN
      set priority queue rank to g(neighbor) + h(neighbor)
      set neighbor's parent to current

reconstruct reverse path from goal to start
by following parent pointers

다음은 Dell의 구현입니다(link to full code.

########################
###    Pathfinder    ###
########################

class Node:

    def __init__(self, parent=None, location=None, action=None):
        self.parent = parent
        self.location = location
        self.action = action

        self.h = 0
        self.g = 0
        self.f = 0

def get_path(node):
    path = []

    while node.parent:
        path.append(node)
        node = node.parent

    return path

def get_path_actions(path):

    actions = []

    for node in path:
        actions.append(node.action)

    return actions

def astar(game_state, start, target):

    print("----A* STAR----")
    path = []

    # add starting node to open list
    open_list = [Node(None, start, None)]
    closed_list = []

    # exit the loop early if no path can be found
    # (the target is likely blocked off)
    max_loops = 1000
    counter = 0

    # while lowest rank in OPEN is not the GOAL:
    while len(open_list) > 0 and counter <= max_loops:

        # find the node with the lowest rank
        curr_node = open_list[0]
        curr_index = 0

        for index, node in enumerate(open_list):
            if node.f < curr_node.f:
                curr_node = node
                curr_index = index

        # check if this node is the goal
        if curr_node.location == target:
            print(f"~~~~~~~FOUND TARGET~~~~~~~")
            path = get_path(curr_node)
            return path

        # current = remove lowest rank item from OPEN
        # add current to CLOSED
        del open_list[curr_index]
        closed_list.append(curr_node)

        # get neighbors of current
        neighbors = get_free_neighbors(game_state, curr_node.location)
        neighbor_nodes = []
        for neighbor in neighbors:
            for location, action in neighbor.items():
                neighbor_nodes.append(Node(None, location, action))

        #   for neighbors of current:
        for neighbor in neighbor_nodes:

            # used for loop behavior
            in_closed = False
            in_open = False

            # cost = g(current) + movementcost(current, neighbor)
            cost = curr_node.g + 1

            # if neighbor in OPEN and cost less than g(neighbor):
            #   remove neighbor from OPEN, because new path is better
            for index, node in enumerate(open_list):
                if neighbor.location == node.location and cost < neighbor.g:
                    del open_list[index]
                    in_open = True

            # if neighbor in CLOSED and cost less than g(neighbor): ⁽²⁾
            #   remove neighbor from CLOSED
            for index, node in enumerate(closed_list):
                if neighbor.location == node.location and cost < neighbor.g: 
                    del closed_list[index]
                    in_closed = True

            # if neighbor not in OPEN and neighbor not in CLOSED:
            #   set g(neighbor) to cost
            #   add neighbor to OPEN
            #   set priority queue rank to g(neighbor) + h(neighbor)
            #   set neighbor's parent to current
            if not in_open and not in_closed:
                neighbor.g = cost
                open_list.append(neighbor)
                neighbor.h = manhattan_distance(neighbor.location, target)
                neighbor.f = neighbor.g + neighbor.h
                neighbor.parent = curr_node

        counter += 1

    print(f"---NO PATH FOUND---")

에 추가helpers.py합니다.
주의, 우리는 get_path_actions()를 추가했다.이것은 우리의 대리인이 목적지에 도착하기 위해 취한 행동으로 돌아갈 것이다(예를 들어 ['u', 'l', ...]

우리 탐정에게 길찾기 기능을 추가하다

모든 것이 정상적인지 확인하려면 next_move() 파일의 my_agent.py 방법을 업데이트하십시오.

def next_move(self, game_state, player_state):

    print(f"tick: {game_state.tick_number}")

    # treasure spawns randomly
    treasure = get_treasure(game_state)

    if len(self.pending_actions) > 0:
        action = self.pending_actions.pop()
    elif treasure:
        path = astar(game_state, player_state.location, treasure)

        if path:
            actions = get_path_actions(path)
            print(f"--ACTIONS: {actions}")

            for action in actions:
                self.pending_actions.append(action)

            action = self.pending_actions.pop()
        else:
            action = ''
    else:
        action = ''

    return action

Link to full code
터미널에서 다음을 실행합니다.

coderone-dungeon my_agent --interactive

--interactive기가 기사 역할을 허락한다)
만약 당신이 모든 것을 성공적으로 설치했다면, 당신의 대리인이 지도 주위에서 보물을 줍는 것을 보아야 합니다.

----A* STAR----
~~~~~~~FOUND TARGET~~~~~~~
--ACTIONS: ['d', 'd', 'd', 'r', 'r', 'd', 'r', 'r', 'r']

주의: 우리는 목표 노드에서 뒤로 경로를 구축했기 때문에 이 조작 목록도 반대로 되어 있습니다.이것은 아주 좋습니다. pop() 을 사용하기 때문에 목록의 끝에서부터 작업을 시작합니다.