python 게임 맵 최 단 경로 설명
다음 그림 을 참고 하여 게임 맵 에서 출발점 에서 목표 점 까지 의 최 단 경 로 를 찾 습 니 다.
2.디자인 사고
먼저 게임 지 도 를 몇 가지 설정 하여 행렬 로 게임 지 도 를 모 의 했다.실행 가능 한 지역 위치 할당 0,장애 구역 할당 inf.지도 크기 를 고려 하여 시작 점 과 종점 구역 에 99 를 부여 합 니 다.
Start 점 A 부터 바깥쪽 으로 확장 합 니 다.확장 할 때마다 pathlen 이 1 을 추가 합 니 다.List Q 는 현재 확장 할 점 을 저장 하고 list P 는 현재 확장 층 을 저장 합 니 다.End 점 B 로 확장 할 때 확장 이 끝나 면 경 로 를 계획 할 수 있 습 니 다.Q 가 비어 있 을 때,이번 층 확장 이 끝나 면 P 를 검사 합 니 다.P 가 비어 있 지 않 으 면 P 층 에서 밖으로 확장 합 니 다.P 가 비어 있 으 면 End 점 B 에 도착 할 수 없습니다.
가장 짧 은 경 로 를 찾 을 때 End 점 B 부터 현재 점 부근 8 개 점 의 태그 중 현재 점 보다 작은 점 을 찾 아 1 로 표 시 될 때 까지 찾 습 니 다.
프로그램 주체
# -*-coding:gbk -*-
from numpy import *
dirs = [(1,1),(1,0),(1,-1),(0,-1),(-1,-1),(-1,0),(-1,1),(0,1)] # : ,
def find_path(oldmap,A,B):
oldmap[A[0], A[1]] = 99
oldmap[B[0], B[1]] = 99
[a,b]=oldmap.shape
pathmap=oldmap.copy()
Q=[]#
P=[]#
pathlen=1
if A==B:
print('start point is equal to end point')
return True
current=A
while (True):
for i in range(8):
neighbor=[current[0]+dirs[i][0], current[1]+dirs[i][1]]
if neighbor==B:
print('the way is found')######################wrong
print(' ')
print(oldmap)
find_way(oldmap,pathmap,A,B,a,b)#####
return True
if (neighbor[0]>=0 and neighbor[1]>=0 and neighbor[0]<a and neighbor[1]<b and oldmap[neighbor[0],neighbor[1]]==0):
P.append(neighbor)
oldmap[neighbor[0],neighbor[1]]=pathlen
if Q==[]:
if P ==[]:
print(oldmap) ##############
print('No path')
return False
else:
Q.extend(P)
P=[]
pathlen += 1
else:
current=Q.pop()
###################
def find_way(oldmap,pathmap,A,B,a,b):
currentpos=B
while (oldmap[currentpos[0],currentpos[1]]!=1):
for i in range(8):
neighborpos=[currentpos[0]+dirs[i][0], currentpos[1]+dirs[i][1]]
if (neighborpos[0] >= 0 and neighborpos[1] >= 0 and neighborpos[0] < a and neighborpos[1] < b and oldmap[neighborpos[0],neighborpos[1]]!=0):
if oldmap[neighborpos[0],neighborpos[1]]<oldmap[currentpos[0],currentpos[1]]:
pathmap[neighborpos[0],neighborpos[1]]=oldmap[neighborpos[0],neighborpos[1]]
currentpos=neighborpos
break
print('the way:')
print(pathmap)
주 함수
def main():
map =mat([[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, inf,inf, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0,inf, 0, 0, 0, 0, 0, 0, 0],
[inf,inf,inf, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0,inf, 0, 0, 0, 0, 0, 0, 0, 0, 0, inf],
[0, 0,inf, 0, 0, 0, 0, 0, 0, 0, 0, 0, inf],
[0, 0,inf, 0, 0, 0, 0, 0, 0, 0, 0, 0,inf],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, inf],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],])
print(' ')
print(map)
print('**********************************')
A = [5, 0]
# B=[5,0]
B = [3, 12]
find_path(map,A, B)
if __name__=='__main__':
main()
운행 결과결과 분석
중간 과정 에 대응 하 는 행렬 을 통 해 알 수 있 듯 이 모두 12 번 의 외부 확장 을 거 쳤 고 12 번 째 확장 은 목표 점 을 포함 할 수 있다.가장 짧 은 경 로 는 the way 에 대응 하 는 행렬 에서 보 듯 이 경사 가 내 려 가 는 것 과 유사 한 방법 으로 얻 을 수 있 습 니 다.
이상 이 바로 본 고의 모든 내용 입 니 다.여러분 의 학습 에 도움 이 되 고 저 희 를 많이 응원 해 주 셨 으 면 좋 겠 습 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.