python A*길 찾기 알고리즘 구현
A*알고리즘 은 두 개의 데이터 구 조 를 유지 해 야 합 니 다.OPEN 집합 과 CLOSED 집합 입 니 다.OPEN 집합 은 검색 할 대상 노드 를 모두 포함 합 니 다.초기 상태 에서 OPEN 집합 은 하나의 요소 만 포함 합 니 다:시작 노드.CLOSED 집합 은 검 측 된 노드 를 포함 합 니 다.초기 상태,CLOSED 집합 이 비어 있 습 니 다.각 노드 에는 추적 관 계 를 확인 하기 위해 부모 노드 를 가리 키 는 지침 도 포함 되 어 있다.
A*알고리즘 은 검색 한 노드 마다 G+H 와 값 F 를 계산 합 니 다.
4.567917.4 인접 지역 으로 이동 할 수 있다 면 맨 해 튼 거 리 를 사용 합 니 다
1.OPEN 에서 가장 좋 은 노드 n(즉,F 값 이 가장 작은 노드)을 집중 적 으로 추출 하여 검 측 합 니 다.
2 노드 n 을 OPEN 집중 에서 제거 한 다음 CLOSED 집중 에 추가 합 니 다.
3 n 이 목표 노드 라면 알고리즘 이 끝 납 니 다.
4.그렇지 않 으 면 노드 n 의 모든 이웃 노드 n 을 추가 하려 고 합 니 다.
4.567917.이웃 노드 는 CLOSED 에 집중 되 어 검 측 되 었 음 을 나타 내 고 더 이상 추가 할 필요 가 없다4
핵심 코드 소개
기본 정 보 를 저장 하 는 지도 클래스
지도 류 는 랜 덤 으로 길 찾기 알고리즘 작업 을 위 한 기초 지도 정 보 를 만 드 는 데 사용 된다.
먼저 맵 클래스 를 만 들 고 매개 변 수 를 초기 화하 여 맵 의 길이 와 폭 을 설정 하 며 맵 정 보 를 저장 하 는 2 차원 데이터 맵 의 값 을 0 으로 설정 합 니 다.값 은 0 으로 이 노드 로 이동 할 수 있 음 을 표시 합 니 다.
class Map():
def __init__(self, width, height):
self.width = width
self.height = height
self.map = [[0 for x in range(self.width)] for y in range(self.height)]
def createBlock(self, block_num):
for i in range(block_num):
x, y = (randint(0, self.width-1), randint(0, self.height-1))
self.map[y][x] = 1
def showMap(self):
print("+" * (3 * self.width + 2))
for row in self.map:
s = '+'
for entry in row:
s += ' ' + str(entry) + ' '
s += '+'
print(s)
print("+" * (3 * self.width + 2))
def generatePos(self, rangeX, rangeY):
x, y = (randint(rangeX[0], rangeX[1]), randint(rangeY[0], rangeY[1]))
while self.map[y][x] == 1:
x, y = (randint(rangeX[0], rangeX[1]), randint(rangeY[0], rangeY[1]))
return (x , y)
OPEN 집합 에 추 가 될 노드 를 검색 할 때마다 아래 노드 클래스 를 만 들 고 entry 가 있 는 위치 정보(x,y)를 저장 하 며 계 산 된 G 값 과 F 값,이 노드 의 부모 노드(preentry）。
class SearchEntry():
def __init__(self, x, y, g_cost, f_cost=0, pre_entry=None):
self.x = x
self.y = y
# cost move form start entry to this entry
self.g_cost = g_cost
self.f_cost = f_cost
self.pre_entry = pre_entry
def getPos(self):
return (self.x, self.y)
다음은 위의 알고리즘 주 순환 에 소 개 된 코드 구현 입 니 다.OPEN 집합 과 CLOSED 집합 데이터 구 조 는 사전 을 사 용 했 습 니 다.일반적인 상황 에서 노드 를 찾 고 추가 하고 삭제 하 는 시간 복잡 도 는 O(1)이 고 옮 겨 다 니 는 시간 복잡 도 는 O(n)이 며 n 은 사전 의 대상 수 입 니 다.
def AStarSearch(map, source, dest):
...
openlist = {}
closedlist = {}
location = SearchEntry(source[0], source[1], 0.0)
dest = SearchEntry(dest[0], dest[1], 0.0)
openlist[source] = location
while True:
location = getFastPosition(openlist)
if location is None:
# not found valid path
print("can't find valid path")
break;
if location.x == dest.x and location.y == dest.y:
break
closedlist[location.getPos()] = location
openlist.pop(location.getPos())
addAdjacentPositions(map, location, dest, openlist, closedlist)
#mark the found path at the map
while location is not None:
map.map[location.y][location.x] = 2
location = location.pre_entry
다음 함 수 는 OPEN 에서 F 값 이 가장 작은 노드 를 집중 적 으로 가 져 오 는 것 입 니 다.OPEN 집회 가 비어 있 으 면 None 으로 돌아 갑 니 다.
# find a least cost position in openlist, return None if openlist is empty
def getFastPosition(openlist):
fast = None
for entry in openlist.values():
if fast is None:
fast = entry
elif fast.f_cost > entry.f_cost:
fast = entry
return fast
# add available adjacent positions
def addAdjacentPositions(map, location, dest, openlist, closedlist):
poslist = getPositions(map, location)
for pos in poslist:
# if position is already in closedlist, do nothing
if isInList(closedlist, pos) is None:
findEntry = isInList(openlist, pos)
h_cost = calHeuristic(pos, dest)
g_cost = location.g_cost + getMoveCost(location, pos)
if findEntry is None :
# if position is not in openlist, add it to openlist
openlist[pos] = SearchEntry(pos[0], pos[1], g_cost, g_cost+h_cost, location)
elif findEntry.g_cost > g_cost:
# if position is in openlist and cost is larger than current one,
# then update cost and previous position
findEntry.g_cost = g_cost
findEntry.f_cost = g_cost + h_cost
findEntry.pre_entry = location
위,아래,왼쪽,오른쪽 4 인접 지역 의 이동 을 허용 합 니 다위,아래,왼쪽,오른쪽,왼쪽 위,오른쪽 위,왼쪽 아래,오른쪽 아래 8 인접 지역 의 이동 을 허용 합 니 다.
def getNewPosition(map, locatioin, offset):
x,y = (location.x + offset[0], location.y + offset[1])
if x < 0 or x >= map.width or y < 0 or y >= map.height or map.map[y][x] == 1:
return None
return (x, y)
def getPositions(map, location):
# use four ways or eight ways to move
offsets = [(-1,0), (0, -1), (1, 0), (0, 1)]
#offsets = [(-1,0), (0, -1), (1, 0), (0, 1), (-1,-1), (1, -1), (-1, 1), (1, 1)]
poslist = []
for offset in offsets:
pos = getNewPosition(map, location, offset)
if pos is not None:
poslist.append(pos)
return poslist
# check if the position is in list
def isInList(list, pos):
if pos in list:
return list[pos]
return None
getMoveCost 함 수 는 경사 방향 이동 여부 에 따라 소 모 를 계산 합 니 다(경사 방향 은 2 의 루트 번호 로 약 1.4 와 같 습 니 다)
# imporve the heuristic distance more precisely in future
def calHeuristic(pos, dest):
return abs(dest.x - pos[0]) + abs(dest.y - pos[1])
def getMoveCost(location, pos):
if location.x != pos[0] and location.y != pos[1]:
return 1.4
else:
return 1
지도의 길이,너비,이동 할 수 없 는 노드 의 수 를 조정 할 수 있 습 니 다.
시작 노드 와 목표 노드 의 수치 범 위 를 조정 할 수 있 습 니 다.
WIDTH = 10
HEIGHT = 10
BLOCK_NUM = 15
map = Map(WIDTH, HEIGHT)
map.createBlock(BLOCK_NUM)
map.showMap()
source = map.generatePos((0,WIDTH//3),(0,HEIGHT//3))
dest = map.generatePos((WIDTH//2,WIDTH-1),(HEIGHT//2,HEIGHT-1))
print("source:", source)
print("dest:", dest)
AStarSearch(map, source, dest)
map.showMap()
두 번 째 그림 에서 값 이 2 인 노드 는 찾 은 경 로 를 표시 합 니 다.
전체 코드
python 3.7 컴 파일 사용
from random import randint
class SearchEntry():
def __init__(self, x, y, g_cost, f_cost=0, pre_entry=None):
self.x = x
self.y = y
# cost move form start entry to this entry
self.g_cost = g_cost
self.f_cost = f_cost
self.pre_entry = pre_entry
def getPos(self):
return (self.x, self.y)
class Map():
def __init__(self, width, height):
self.width = width
self.height = height
self.map = [[0 for x in range(self.width)] for y in range(self.height)]
def createBlock(self, block_num):
for i in range(block_num):
x, y = (randint(0, self.width-1), randint(0, self.height-1))
self.map[y][x] = 1
def generatePos(self, rangeX, rangeY):
x, y = (randint(rangeX[0], rangeX[1]), randint(rangeY[0], rangeY[1]))
while self.map[y][x] == 1:
x, y = (randint(rangeX[0], rangeX[1]), randint(rangeY[0], rangeY[1]))
return (x , y)
def showMap(self):
print("+" * (3 * self.width + 2))
for row in self.map:
s = '+'
for entry in row:
s += ' ' + str(entry) + ' '
s += '+'
print(s)
print("+" * (3 * self.width + 2))
def AStarSearch(map, source, dest):
def getNewPosition(map, locatioin, offset):
x,y = (location.x + offset[0], location.y + offset[1])
if x < 0 or x >= map.width or y < 0 or y >= map.height or map.map[y][x] == 1:
return None
return (x, y)
def getPositions(map, location):
# use four ways or eight ways to move
offsets = [(-1,0), (0, -1), (1, 0), (0, 1)]
#offsets = [(-1,0), (0, -1), (1, 0), (0, 1), (-1,-1), (1, -1), (-1, 1), (1, 1)]
poslist = []
for offset in offsets:
pos = getNewPosition(map, location, offset)
if pos is not None:
poslist.append(pos)
return poslist
# imporve the heuristic distance more precisely in future
def calHeuristic(pos, dest):
return abs(dest.x - pos[0]) + abs(dest.y - pos[1])
def getMoveCost(location, pos):
if location.x != pos[0] and location.y != pos[1]:
return 1.4
else:
return 1
# check if the position is in list
def isInList(list, pos):
if pos in list:
return list[pos]
return None
# add available adjacent positions
def addAdjacentPositions(map, location, dest, openlist, closedlist):
poslist = getPositions(map, location)
for pos in poslist:
# if position is already in closedlist, do nothing
if isInList(closedlist, pos) is None:
findEntry = isInList(openlist, pos)
h_cost = calHeuristic(pos, dest)
g_cost = location.g_cost + getMoveCost(location, pos)
if findEntry is None :
# if position is not in openlist, add it to openlist
openlist[pos] = SearchEntry(pos[0], pos[1], g_cost, g_cost+h_cost, location)
elif findEntry.g_cost > g_cost:
# if position is in openlist and cost is larger than current one,
# then update cost and previous position
findEntry.g_cost = g_cost
findEntry.f_cost = g_cost + h_cost
findEntry.pre_entry = location
# find a least cost position in openlist, return None if openlist is empty
def getFastPosition(openlist):
fast = None
for entry in openlist.values():
if fast is None:
fast = entry
elif fast.f_cost > entry.f_cost:
fast = entry
return fast
openlist = {}
closedlist = {}
location = SearchEntry(source[0], source[1], 0.0)
dest = SearchEntry(dest[0], dest[1], 0.0)
openlist[source] = location
while True:
location = getFastPosition(openlist)
if location is None:
# not found valid path
print("can't find valid path")
break;
if location.x == dest.x and location.y == dest.y:
break
closedlist[location.getPos()] = location
openlist.pop(location.getPos())
addAdjacentPositions(map, location, dest, openlist, closedlist)
#mark the found path at the map
while location is not None:
map.map[location.y][location.x] = 2
location = location.pre_entry
WIDTH = 10
HEIGHT = 10
BLOCK_NUM = 15
map = Map(WIDTH, HEIGHT)
map.createBlock(BLOCK_NUM)
map.showMap()
source = map.generatePos((0,WIDTH//3),(0,HEIGHT//3))
dest = map.generatePos((WIDTH//2,WIDTH-1),(HEIGHT//2,HEIGHT-1))
print("source:", source)
print("dest:", dest)
AStarSearch(map, source, dest)
map.showMap()
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
로마 숫자를 정수로 또는 그 반대로 변환그 중 하나는 로마 숫자를 정수로 변환하는 함수를 만드는 것이었고 두 번째는 그 반대를 수행하는 함수를 만드는 것이었습니다. 문자만 포함합니다'I', 'V', 'X', 'L', 'C', 'D', 'M' ; 문자열이 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
