from random import randint from PIL import Image 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): self.img = Image.open('xiaoditu.png') width, height = self.img.size self.width = width self.height = height self.map = [[0 for y in range(self.height)] for x in range(self.width)] self.pathlist=[]; # 遍历图片吧黑色像素都设置1 障碍物 def createBlock(self): pixels = self.img.load() for y in range(self.height): for x in range(self.width): r, g, b = pixels[x, y] # in case your image has an alpha channel # r, g, b, a = pixels[x, y] if(r>=15): self.map[x][y]=1 # 最后再循环遍历map绘图 0是白色 可通行 1 障碍物 黑色不可通行 2 红色 可通行陆星 def showMap(self): for y in range(self.height): for x in range(self.width): val = self.map[x][y] if(val==0): self.img.putpixel((x,y),(255,255,255,255)) elif(val==1): self.img.putpixel((x,y),(0,0,0,255)) else: self.pathlist.append([x,y]); self.img.putpixel((x,y),(255,0,0,255)) self.img.save('daohang.png') return self.pathlist 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 map = Map() # 注意Y,X source = (8,3) dest =(142,200) map.createBlock(); AStarSearch(map, source, dest) pathlist=map.showMap() # 返回路径数组 x y print(pathlist);
标签:map,cost,python,self,pos,像素,openlist,寻址,location From: https://www.cnblogs.com/newmiracle/p/16607281.html