Sample algorithm
算法介绍
英文介绍
- This is a fairly simple and easy-to-understand pathfinding algorithm for tile-based maps. To start off, you have a map, a start coordinate and a destination coordinate. The map will look like this, X being walls, S being the start, O being the finish and _ being open spaces, the numbers along the top and right edges are the column and row numbers:
-
First, create a list of coordinates, which we will use as a queue. The queue will be initialized with one coordinate, the end coordinate. Each coordinate will also have a counter variable attached (the purpose of this will soon become evident).
-
Then, go through every element in the queue, including new elements added to the end over the course of the algorithm, and for each element, do the following:
- 1.Create a list of the four adjacent cells, with a counter variable of the current element’s counter variable + 1
- 2.Check all cells in each list for the following two conditions:
- 1.If the cell is a wall, remove it from the list
- 2.If there is an element in the main list with the same coordinate, remove it from the cells list
- 3.Add all remaining cells in the list to the end of the main list
- 4.Go to the next item in the list
我的翻译
- 对于基于瓦片的地图来说，这是一个相当简单且易于理解的寻路算法。首先，你有一张地图，一个起始坐标和一个目的地坐标。地图是这样的，X是墙，S是开始，O是结束，_是开放空间，顶部和右边的数字是列号和行号:
- 首先，创建一个坐标列表，我们将其用作队列。队列将用一个坐标初始化，即end坐标。每个坐标还将附加一个计数器变量(其目的很快就会变得明显)。
- 然后，遍历队列中的每个元素，包括在算法过程中添加到队列末尾的新元素，并对每个元素执行以下操作:
- 1。创建一个包含四个相邻单元格的列表，使用当前元素的计数器变量+1做新格的计数器变量
- 2。检查每个列表中的所有单元格，满足以下两个条件:
- 1。如果单元格是一堵墙，将其从列表中删除
- 2。如果主列表中有一个具有相同坐标的元素，则将其从单元格列表中删除
- 3。将列表中所有剩余的单元格添加到主列表的末尾
- 4。转到列表中的下一项
寻路结果图
; 演示代码
import random
import pygame
import maze
pygame.init()
size = width, height = 800, 600
screen = pygame.display.set_mode(size)
diamond_color_size = 8
COLOR_RED, COLOR_BLUE, COLOR_GREEN, COLOR_YELLOW, COLOR_BLACK, COLOR_GREY, COLOR_GOLDEN, COLOR_NO_DIAMOND = list(range(
diamond_color_size))
COLOR = {
COLOR_RED: (255, 0, 0),
COLOR_BLUE: (0, 0, 255),
COLOR_GREEN: (0, 255, 0),
COLOR_YELLOW: (255, 255, 0),
COLOR_BLACK: (0, 0, 0),
COLOR_GREY: (250, 240, 230),
COLOR_GOLDEN : (255,215,0),
COLOR_NO_DIAMOND: (100, 100, 100),
}
DIAMOND_SIZE = (20, 20)
DIAMOND=pygame.surface.Surface(DIAMOND_SIZE).convert()
DIAMOND.fill(COLOR[COLOR_BLUE])
DIAMOND_GREEN=pygame.surface.Surface(DIAMOND_SIZE).convert()
DIAMOND_GREEN.fill(COLOR[COLOR_GREEN])
DIAMOND_RED=pygame.surface.Surface(DIAMOND_SIZE).convert()
DIAMOND_RED.fill(COLOR[COLOR_RED])
DIAMOND_YELLOW=pygame.surface.Surface(DIAMOND_SIZE).convert()
DIAMOND_YELLOW.fill(COLOR[COLOR_YELLOW])
DIAMOND_GREY=pygame.surface.Surface(DIAMOND_SIZE).convert()
DIAMOND_GREY.fill(COLOR[COLOR_GREY])
use_font = pygame.font.Font("FONT.TTF", 16)
use_font12 = pygame.font.Font("FONT.TTF", 12)
background=pygame.surface.Surface(size).convert()
background.fill(COLOR[COLOR_BLACK])
score_surface = use_font.render("找到终点", True, COLOR[COLOR_BLACK], COLOR[COLOR_GREY])
clock = pygame.time.Clock()
NOWALL=maze.NOWALL
WALL=maze.WALL
WALL2=maze.WALL2
VISIT=maze.VISIT
NOVISIT=maze.NOVISIT
VERTICAL = maze.VERTICAL
HORIZONTAL = maze.HORIZONTAL
INFINITE = maze.INFINITE
INFINITE = maze.INFINITE
def sample_pathfinding(rows, cols, walls, startPoint=(0,0), endPoint=None):
grids=[[ INFINITE for i in range(cols)]for j in range(rows)]
r=startPoint[0]
c=startPoint[1]
findEndPoint=False
findPath=False
if endPoint:
stopPoint=endPoint
else:
stopPoint=(rows-1,cols-1)
mainList=[]
pathList=[(r,c,0)]
grids[r][c]=0
while not findPath:
if pathList and not findEndPoint:
nextList = []
for node in pathList:
r, c, l = node
if (r,c) == stopPoint:
grids[r][c] = l
findEndPoint=True
break
if r>0 and NOWALL == walls[r][c][1] and INFINITE == grids[r-1][c]:
nr=r-1
nc=c
nextList.append((nr,nc,l+1))
if c>0 and NOWALL == walls[r][c][0] and INFINITE == grids[r][c-1]:
nr=r
nc=c-1
nextList.append((nr,nc,l+1))
if c<cols-1 and NOWALL == walls[r][c+1][0] and INFINITE == grids[r][c+1] :
nr=r
nc=c+1
nextList.append((nr,nc,l+1))
if r<rows-1 and NOWALL == walls[r+1][c][1] and INFINITE == grids[r+1][c] :
nr=r+1
nc=c
nextList.append((nr,nc,l+1))
if INFINITE == grids[r][c]:
grids[r][c] = l
pathList = nextList
elif findEndPoint and not findPath:
""
mainList.append((r,c))
l = grids[r][c]
nl=l-1
if r>0 and NOWALL == walls[r][c][1] and nl == grids[r-1][c]:
nr=r-1
nc=c
nextList.append((nr,nc,l+1))
if c>0 and NOWALL == walls[r][c][0] and nl == grids[r][c-1]:
nr=r
nc=c-1
nextList.append((nr,nc,l+1))
if c<cols-1 and NOWALL == walls[r][c+1][0] and nl == grids[r][c+1] :
nr=r
nc=c+1
nextList.append((nr,nc,l+1))
if r<rows-1 and NOWALL == walls[r+1][c][1] and nl == grids[r+1][c] :
nr=r+1
nc=c
nextList.append((nr,nc,l+1))
if 0 == nl:
mainList.append((nr,nc))
findPath = True
break
r,c=nr,nc
return mainList, grids
def sample_pathfinding_demo(rows, cols):
walls = maze.wilson_maze(rows, cols)
POSX=40
POSY=40
grids=[[ INFINITE for i in range(cols)]for j in range(rows)]
r=0
c=0
findEndPoint=False
findPath=False
startPoint=(r,c)
stopPoint=(rows-1,cols-1)
mainList=[]
pathList=[(r,c,0)]
grids[r][c]=0
while True:
for event in pygame.event.get():
if event.type == pygame.QUIT:
return
if pathList and not findEndPoint:
nextList = []
for node in pathList:
r, c, l = node
if (r,c) == stopPoint:
grids[r][c] = l
pathList=[]
findEndPoint=True
break
if r>0 and NOWALL == walls[r][c][1] and INFINITE == grids[r-1][c]:
nr=r-1
nc=c
nextList.append((nr,nc,l+1))
if c>0 and NOWALL == walls[r][c][0] and INFINITE == grids[r][c-1]:
nr=r
nc=c-1
nextList.append((nr,nc,l+1))
if c<cols-1 and NOWALL == walls[r][c+1][0] and INFINITE == grids[r][c+1] :
nr=r
nc=c+1
nextList.append((nr,nc,l+1))
if r<rows-1 and NOWALL == walls[r+1][c][1] and INFINITE == grids[r+1][c] :
nr=r+1
nc=c
nextList.append((nr,nc,l+1))
if INFINITE == grids[r][c]:
grids[r][c] = l
pathList = nextList
elif findEndPoint and not findPath:
""
mainList.append((r,c))
l = grids[r][c]
nl=l-1
if r>0 and NOWALL == walls[r][c][1] and nl == grids[r-1][c]:
nr=r-1
nc=c
nextList.append((nr,nc,l+1))
if c>0 and NOWALL == walls[r][c][0] and nl == grids[r][c-1]:
nr=r
nc=c-1
nextList.append((nr,nc,l+1))
if c<cols-1 and NOWALL == walls[r][c+1][0] and nl == grids[r][c+1] :
nr=r
nc=c+1
nextList.append((nr,nc,l+1))
if r<rows-1 and NOWALL == walls[r+1][c][1] and nl == grids[r+1][c] :
nr=r+1
nc=c
nextList.append((nr,nc,l+1))
if 0 == nl:
mainList.append((nr,nc))
findPath = True
r,c=nr,nc
screen.blit(background, (0, 0))
for cx in range(cols):
for ry in range(rows):
px,py=POSX + 1 + (cx) * DIAMOND_SIZE[0], POSY + 1 + (ry) * DIAMOND_SIZE[1]
if maze.INFINITE == grids[ry][cx]:
screen.blit(DIAMOND, (px, py))
else:
screen.blit(DIAMOND_GREY, (px, py))
s = "{}".format(grids[ry][cx])
distance_surface = use_font12.render(s, True, COLOR[COLOR_BLACK], COLOR[COLOR_GREY])
screen.blit(distance_surface, (px, py))
if pathList and not mainList:
for pos in pathList:
px,py=POSX + 1 + (pos[1]) * DIAMOND_SIZE[0], POSY + 1 + (pos[0]) * DIAMOND_SIZE[1]
screen.blit(DIAMOND_GREEN, (px, py))
s = "{}".format(grids[pos[0]][pos[1]])
distance_surface = use_font12.render(s, True, COLOR[COLOR_BLACK], COLOR[COLOR_GREEN])
screen.blit(distance_surface, (px, py))
if mainList:
for pos in mainList:
px,py=POSX + 1 + (pos[1]) * DIAMOND_SIZE[0], POSY + 1 + (pos[0]) * DIAMOND_SIZE[1]
screen.blit(DIAMOND_YELLOW, (px, py))
s = "{}".format(grids[pos[0]][pos[1]])
distance_surface = use_font12.render(s, True, COLOR[COLOR_BLACK], COLOR[COLOR_YELLOW])
screen.blit(distance_surface, (px, py))
px,py=POSX + 1 + (c) * DIAMOND_SIZE[0], POSY + 1 + (r) * DIAMOND_SIZE[1]
screen.blit(DIAMOND_GREEN, (px, py))
s = "{}".format(grids[r][c])
distance_surface = use_font12.render(s, True, COLOR[COLOR_BLACK], COLOR[COLOR_GREEN])
screen.blit(distance_surface, (px, py))
pygame.draw.rect(screen, COLOR[COLOR_RED], (POSX + 0, POSY + 0, 20*cols+1, 20*rows+1), 2)
for cx in range( cols):
for ry in range(rows):
px,py=POSX + 1 + (cx) * DIAMOND_SIZE[0], POSY + 1 + (ry) * DIAMOND_SIZE[1]
color = COLOR[COLOR_BLACK]
color2 = COLOR[COLOR_RED]
if maze.WALL == walls[ry][cx][0]:
pygame.draw.line(screen, color, (px, py), (px, py+20), 2)
if maze.WALL == walls[ry][cx][1]:
pygame.draw.line(screen, color, (px, py), (px+20, py), 2)
if findEndPoint:
screen.blit(score_surface, (POSX+50, POSY+rows*22))
time_passed = clock.tick(25)
pygame.display.update()
return
if __name__ == "__main__":
'''main'''
sample_pathfinding_demo(20, 30)
GIF动画演示
; maze.py
import random
NOWALL=0
WALL=1
WALL2=2
VISIT=1
NOVISIT=0
VERTICAL = 0
HORIZONTAL = 1
INFINITE = -1
def aldous_broder_maze(rows, cols):
grids=[[ NOVISIT for i in range(cols)]for j in range(rows)]
wall=[[ [WALL,WALL] for i in range(cols)]for i in range(rows)]
notusegrids = []
for tr in range(rows):
for tc in range(cols):
notusegrids.append((tr,tc))
r,c = random.choice(notusegrids)
grids[r][c]=VISIT
notusegrids.remove((r,c))
while notusegrids:
directions = []
if r > 0:
directions.append('u')
if c > 0:
directions.append('l')
if r < rows-1:
directions.append('d')
if c < cols-1:
directions.append('r')
if len(directions):
move = random.choice(directions)
if move == 'u':
newr = r-1
newc = c
opwall=(r, c, HORIZONTAL)
if move == 'l':
newr = r
newc = c-1
opwall=(r, c, VERTICAL)
if move == 'd':
newr = r+1
newc = c
opwall=(newr, newc, HORIZONTAL)
if move == 'r':
newr = r
newc = c+1
opwall=(newr, newc, VERTICAL)
if grids[newr][newc] == NOVISIT:
grids[newr][newc]=VISIT
notusegrids.remove((newr,newc))
wall[opwall[0]][opwall[1]][opwall[2]] = NOWALL
r=newr
c=newc
else:
r=newr
c=newc
return wall
def depth_maze(rows, cols):
history = [(0,0)]
wall=[[ [WALL,WALL] for i in range(cols)]for i in range(rows)]
way=[[ NOVISIT for i in range(cols)]for i in range(rows)]
r=0
c=0
history = [(r,c)]
while history:
way[r][c] = VISIT
check = []
if c > 0 and way[r][c-1] == NOVISIT:
check.append('L')
if r > 0 and way[r-1][c] == NOVISIT:
check.append('U')
if c < cols-1 and way[r][c+1] == NOVISIT:
check.append('R')
if r < rows-1 and way[r+1][c] == NOVISIT:
check.append('D')
if len(check):
history.append((r, c))
move_direction = random.choice(check)
if move_direction == 'L':
wall[r][c][0] = NOWALL
c=c-1
if move_direction == 'U':
wall[r][c][1] = NOWALL
r=r-1
if move_direction == 'R':
c=c+1
wall[r][c][0] = NOWALL
if move_direction == 'D':
r=r+1
wall[r][c][1] = NOWALL
else:
r, c = history.pop()
return wall
def kruskal_maze(rows, cols):
grids=[[ NOVISIT for i in range(cols)]for i in range(rows)]
wall=[[ [WALL,WALL] for i in range(cols)]for i in range(rows)]
r=0
c=0
gridlist=[]
gridlist.append((r,c))
collection =[]
wallList=[]
for r in range(rows):
for c in range(cols):
collection.append([(r,c)])
for x in (HORIZONTAL, VERTICAL):
if r == 0 and x == HORIZONTAL:
continue
if c == 0 and x == VERTICAL:
continue
wallList.append((r,c,x))
while wallList:
r,c,x = random.choice(wallList)
wallList.remove((r,c,x))
if x == VERTICAL:
a = (r,c-1)
b = (r,c)
else :
a = (r,c)
b = (r-1,c)
coll1 = []
coll2 = []
for coll in collection:
if a in coll:
coll1 = coll
if b in coll:
coll2 = coll
grids[a[0]][a[1]] = VISIT
grids[b[0]][b[1]] = VISIT
if coll1 != coll2:
wall[r][c][x] = NOWALL
coll = coll1+coll2
collection.remove(coll1)
collection.remove(coll2)
collection.append(coll)
return wall
def prim_maze(rows, cols):
wall=[[ [WALL,WALL] for i in range(cols+1)]for i in range(rows+1)]
way=[[ NOVISIT for i in range(cols)]for i in range(rows)]
r=0
c=0
way[r][c]=VISIT
walllist=[]
walllist.append((r+1,c, HORIZONTAL))
walllist.append((r,c+1, VERTICAL))
while walllist:
r, c, d = random.choice(walllist)
walllist.remove((r,c,d))
if d == VERTICAL:
if c > 0 and (not way[r][c-1] == way[r][c] ):
wall[r][c][0]=NOWALL
if way[r][c] == VISIT:
nc=c-1
else:
nc=c
c=nc
way[r][c]=VISIT
if r > 0 and wall[r][c][1] == WALL:
walllist.append((r,c,1))
if r+1 < rows and wall[r+1][c][1] == WALL:
walllist.append((r+1,c,1))
if c > 0 and wall[r][c][0] == WALL:
walllist.append((r,c,0))
if c+1 < cols and wall[r][c+1][0] == WALL:
walllist.append((r,c+1,0))
elif d == HORIZONTAL:
if r > 0 and ( (not way[r-1][c]) == way[r][c] ):
wall[r][c][1]=NOWALL
if way[r][c] == VISIT:
nr=r-1
else:
nr=r
r=nr
way[r][c]=VISIT
if r > 0 and wall[r][c][1] == WALL:
walllist.append((r,c,1))
if r + 1 < rows and wall[r+1][c][1] == WALL:
walllist.append((r+1,c,1))
if c > 0 and wall[r][c][0] == WALL:
walllist.append((r,c,0))
if c + 1 < cols and wall[r][c+1][0] == WALL:
walllist.append((r,c+1,0))
for rrr1, ccc1, ddd1 in walllist:
if ddd1 == VERTICAL:
if ccc1 > 0 and way[rrr1][ccc1-1] == VISIT and way[rrr1][ccc1] == VISIT:
walllist.remove((rrr1,ccc1,ddd1))
elif ddd1 == HORIZONTAL:
if rrr1 > 0 and way[rrr1-1][ccc1] == VISIT and way[rrr1][ccc1] == VISIT:
walllist.remove((rrr1,ccc1,ddd1))
return wall
def wilson_maze(rows, cols):
wall=[[ [WALL,WALL] for i in range(cols+1)]for i in range(rows+1)]
grids=[[ NOVISIT for i in range(cols)]for j in range(rows)]
tmpgrids = []
tmpwalls = []
notusegrids = []
for tr in range(rows):
for tc in range(cols):
notusegrids.append((tr,tc))
r,c = random.choice(notusegrids)
notusegrids.remove((r,c))
grids[r][c]=VISIT
r,c = notusegrids[0]
tmpgrids.append((r,c))
while notusegrids:
directions = []
if r > 0:
directions.append('u')
if c > 0:
directions.append('l')
if r < rows-1:
directions.append('d')
if c < cols-1:
directions.append('r')
if len(directions):
move = random.choice(directions)
if move == 'u':
newr = r-1
newc = c
nextgrid=(newr, newc)
opwall=(r, c, HORIZONTAL)
if move == 'l':
newr = r
newc = c-1
nextgrid=(newr, newc)
opwall=(r, c, VERTICAL)
if move == 'd':
newr = r+1
newc = c
nextgrid=(newr, newc)
opwall=(newr, newc, HORIZONTAL)
if move == 'r':
newr = r
newc = c+1
nextgrid=(newr, newc)
opwall=(newr, newc, VERTICAL)
if (newr, newc) in tmpgrids:
i = tmpgrids.index((newr, newc))
tmpgrids=tmpgrids[:i+1]
tmpwalls=tmpwalls[:i]
r=newr
c=newc
elif grids[newr][newc] == VISIT:
tmpwalls.append(opwall)
for (r,c) in tmpgrids:
notusegrids.remove((r,c))
grids[r][c]=VISIT
for (r,c,x) in tmpwalls:
wall[r][c][x]=NOWALL
tmpgrids=[]
tmpwalls=[]
if notusegrids:
r,c = notusegrids[0]
tmpgrids.append((r, c))
else:
tmpgrids.append(nextgrid)
tmpwalls.append(opwall)
r=newr
c=newc
return wall
if __name__ == "__main__":
'''main'''
aldous_broder_maze(20, 30)
参考
https://en.wikipedia.org/wiki/Pathfinding
Original: https://blog.csdn.net/x82488059/article/details/116165933
Author: 火苗999℃
Title: 迷宫最短路径算法(Sample algorithm)
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/783450/
转载文章受原作者版权保护。转载请注明原作者出处！