问题：给定几个元动作及起始点、终止点、还有起始方向，生成一条随机行走的路径。
暂时用最笨的解决方法，回溯法，找到一条就返回。
现有元动作，左转，直行，右转.用pygame进行图形显示。
扩展性有点差，每个方向都要根据当前的方向和元动作进行判断。
import pygame
import math
import random
black = (0, 0, 0)
white = (255, 255, 255)
red = (255, 0, 0)
green = (0, 255, 0)
blue = (0, 0, 255)
yellow = (255, 255, 0)
done = False
#define move direction to local
Move_Left, Move_Forward, Move_Right = range(0, 3)
#define world direction
Dir_Up, Dir_Right, Dir_Down, Dir_Left = range(0, 4)
pygame.init()
size = [800, 600]
screen = pygame.display.set_mode(size)
pygame.display.set_caption("Animation Path")
def dir_str(cur_dir):
dir_str = ""
if cur_dir == Dir_Up:
dir_str = "↑"
elif cur_dir == Dir_Right:
dir_str = "→"
elif cur_dir == Dir_Down:
dir_str = "↓"
elif cur_dir == Dir_Left:
dir_str = "←"
return dir_str
def movestate_str(move_state):
move_str = ""
if move_state == Move_Left:
move_str = "Turn Left"
elif move_state == Move_Forward:
move_str = "Forward"
elif move_state == Move_Right:
move_str = "Turn Right"
return move_str
class AnimationPath:
def __init__(self):
self.width = 0
self.height = 0
self.cell_size = 50
self.one_step = 1
self.start_pos = [0,0]
self.path_width = 2
self.initialize()
def initialize(self):
self.is_find = False
self.result_list = []
self.count = 0
def draw_board(self):
start_pos = self.start_pos
total_width = self.width * self.cell_size
total_height = self.height * self.cell_size
for i in range(0, self.width+1):
begin_pos_x = start_pos[0] + i * self.cell_size
end_pos_y = start_pos[1] - total_height
pygame.draw.line(screen, white, [begin_pos_x,start_pos[1]],
[begin_pos_x, end_pos_y], 1)
for j in range(0, self.height+1):
begin_pos_y = start_pos[1] - j * self.cell_size
end_pos_x = start_pos[0] + total_width
pygame.draw.line(screen, white, [start_pos[0], begin_pos_y],
[end_pos_x, begin_pos_y], 1)
def draw_line(self, start_pos, end_pos, color, width):
base_x = self.start_pos[0]
base_y = self.start_pos[1]
pygame.draw.line(screen,color,
[base_x + start_pos[0] * self.cell_size,
base_y - start_pos[1] * self.cell_size],
[base_x + end_pos[0] * self.cell_size,
base_y - end_pos[1] * self.cell_size],
width)
#画出行走路线
def draw_path(self, cur_pos, cur_dir, move_state, color, width):
cur_x = cur_pos[0]
cur_y = cur_pos[1]
base_x = self.start_pos[0]
base_y = self.start_pos[1]
if cur_dir == Dir_Up:
if move_state == Move_Left:
pygame.draw.arc(screen, color,
[(base_x + cur_x * self.cell_size - self.cell_size*2,
base_y - cur_y * self.cell_size - self.cell_size),
(self.cell_size * 2,
self.cell_size * 2)],
0,math.radians(90), width)
elif move_state == Move_Forward:
self.draw_line(cur_pos, [cur_pos[0], cur_pos[1]+self.one_step * 2], color, width)
elif move_state == Move_Right:
pygame.draw.arc(screen, color,
[base_x + cur_x * self.cell_size,
base_y - cur_y * self.cell_size - self.cell_size,
self.cell_size * 2,
self.cell_size * 2],
math.radians(90), math.radians(180), width)
elif cur_dir == Dir_Right:
if move_state == Move_Left:
pygame.draw.arc(screen, color,
[base_x + cur_x * self.cell_size - self.cell_size,
base_y - cur_y * self.cell_size - self.cell_size * 2,
self.cell_size * 2,
self.cell_size * 2],
math.radians(270),
math.radians(360),
width)
elif move_state == Move_Forward:
self.draw_line(cur_pos, [cur_pos[0] + self.one_step * 2, cur_pos[1]], color, width)
elif move_state == Move_Right:
pygame.draw.arc(screen, color,
[base_x + cur_x * self.cell_size - self.cell_size,
base_y - cur_y * self.cell_size,
self.cell_size * 2,
self.cell_size * 2],
0,
math.radians(90),
width)
elif cur_dir == Dir_Down:
if move_state == Move_Left:
pygame.draw.arc(screen, color,
[base_x + cur_x * self.cell_size,
base_y - cur_y * self.cell_size - self.cell_size,
self.cell_size * 2,
self.cell_size * 2],
math.radians(180),
math.radians(270),
width)
elif move_state == Move_Forward:
self.draw_line(cur_pos, [cur_pos[0], cur_pos[1] - self.one_step * 2], color, width)
elif move_state == Move_Right:
pygame.draw.arc(screen, color,
[base_x + cur_x * self.cell_size - self.cell_size * 2,
base_y - cur_y * self.cell_size - self.cell_size,
self.cell_size * 2,
self.cell_size * 2],
math.radians(270),
math.radians(360),
width)
elif cur_dir == Dir_Left:
if move_state == Move_Left:
pygame.draw.arc(screen, color,
[base_x + cur_x * self.cell_size - self.cell_size,
base_y - cur_y * self.cell_size,
self.cell_size * 2,
self.cell_size * 2],
math.radians(90),
math.radians(180),
width)
elif move_state == Move_Forward:
self.draw_line(cur_pos, [cur_pos[0] - self.one_step * 2, cur_pos[1]], color, width)
elif move_state == Move_Right:
pygame.draw.arc(screen, color,
[base_x + cur_x * self.cell_size - self.cell_size,
base_y - cur_y * self.cell_size - self.cell_size * 2,
self.cell_size * 2,
self.cell_size * 2],
math.radians(180),
math.radians(270),
width)
else:
pass
pass
#根据现在的方向和动作判断下一个位置
def move_to_next(self, cur_pos, cur_dir, move_state):
# new_pos = cur_pos
cur_x = cur_pos[0]
cur_y = cur_pos[1]
new_dir = cur_dir
canMove = False;
if cur_dir == Dir_Up:
if move_state == Move_Left:
if cur_x == 0 or cur_y == self.height:
#can't move this way
pass
else:
cur_x = cur_x - self.one_step
cur_y = cur_y + self.one_step
new_dir = Dir_Left
canMove = True
elif move_state == Move_Forward:
if cur_y >= self.height-1:
#can't move up
pass
else:
cur_y = cur_y + self.one_step*2
canMove = True
elif move_state == Move_Right:
if cur_x == self.width or cur_y == self.height:
#can't move this way
pass
else:
cur_x = cur_x + self.one_step
cur_y = cur_y + self.one_step
new_dir = Dir_Right
canMove = True
elif cur_dir == Dir_Right:
if move_state == Move_Left:
if cur_x == self.width or cur_y == self.height:
#can't move
pass
else:
cur_x = cur_x + self.one_step
cur_y = cur_y + self.one_step
new_dir = Dir_Up
canMove = True
elif move_state == Move_Forward:
if cur_x >= self.width -1:
#can't move
pass
else:
cur_x = cur_x + self.one_step*2
canMove = True
elif move_state == Move_Right:
if cur_x == self.width or cur_y == 0:
#can't move
pass
else:
cur_x = cur_x + self.one_step
cur_y = cur_y -1
new_dir = Dir_Down
canMove = True
elif cur_dir == Dir_Down:
if move_state == Move_Left:
if cur_x == self.width or cur_y == 0:
#can't move
pass
else:
cur_x = cur_x + self.one_step
cur_y = cur_y - self.one_step
new_dir = Dir_Right
canMove = True
elif move_state == Move_Forward:
if cur_y <= 1:
#can't move
pass
else:
cur_y = cur_y - self.one_step*2
canMove = True
elif move_state == Move_Right:
if cur_x == 0 or cur_y == 0:
#can't move
pass
else:
cur_x = cur_x - self.one_step
cur_y = cur_y - self.one_step
new_dir = Dir_Left
canMove = True
elif cur_dir == Dir_Left:
if move_state == Move_Left:
if cur_x == 0 or cur_y == 0:
#can't move
pass
else:
cur_x = cur_x - self.one_step
cur_y = cur_y - self.one_step
new_dir = Dir_Down
canMove = True
elif move_state == Move_Forward:
if cur_x <= 1:
#can't move
pass
else:
cur_x = cur_x - self.one_step*2
canMove = True
elif move_state == Move_Right:
if cur_x == 0 or cur_y == self.height:
#can't move
pass
else:
cur_x = cur_x - self.one_step
cur_y = cur_y + self.one_step
new_dir = Dir_Up
canMove = True
new_pos = [cur_x, cur_y]
return [canMove, new_pos, new_dir]
pass
def traceback_move(self, cur_pos, cur_dir):
if not self.is_find:
cur_x = cur_pos[0]
cur_y = cur_pos[1]
if cur_x == self.width and cur_y == self.height:
self.count= self.count + 1
print ("reach goal%s"%self.count)
#reslut_list.append([cur_x, cur_y])
self.is_find = True
return True
else:
state_list = range(0,3)
while len(state_list) > 0:
state_left = len(state_list)
state_index = random.randint(0, state_left-1)
state = state_list[state_index]
state_list.remove(state)
move_result = self.move_to_next(cur_pos, cur_dir, state)
if move_result[0]:
cur_x = move_result[1][0]
cur_y = move_result[1][1]
new_dir = move_result[2]
if self.traceback_move([cur_x,cur_y], new_dir) or self.is_find:
print ("[%s,%s]:%s:%s"%(cur_pos[0], cur_pos[1],dir_str(cur_dir), movestate_str(state)))
self.result_list.append([cur_pos,cur_dir,state])
return True
#if is_ok:
#print ("[%s,%s]"%(cur_x,cur_y))
#return is_ok
return False
else:
return True
pass
def calc_board_size(self, start_pos, end_pos):
width = abs(end_pos[0] - start_pos[0])/self.cell_size
height = abs(end_pos[1] - start_pos[1])/self.cell_size
self.height = height
self.width = width
def findPath(self, start_pos, end_pos, start_dir):
cur_x = 0
cur_y = 0
cur_dir = start_dir
self.start_pos = start_pos
self.calc_board_size(start_pos, end_pos)
self.initialize()
self.traceback_move([cur_x, cur_y], cur_dir)
def draw_result(self):
for step in self.result_list:
self.draw_path(step[0], step[1], step[2], green, 2)
s_pos = [100,550]
e_pos = [600,50]
c_dir = Dir_Up
anim_path = AnimationPath()
anim_path.findPath(s_pos, e_pos, c_dir)
results = anim_path.result_list
results.reverse()
step_index = 0
one_step = False
while done == False:
for event in pygame.event.get():
if event.type == pygame.QUIT:
done = True
if event.type == pygame.KEYDOWN:
if event.key == pygame.K_SPACE:
one_step = not one_step
elif event.key == pygame.K_LEFT:
if step_index > 0:
step_index = step_index - 1
elif event.key == pygame.K_RIGHT:
if step_index < len(results)-1:
step_index = step_index + 1
elif event.key == pygame.K_g:
print ("G")
anim_path.findPath(s_pos, e_pos, c_dir)
results = anim_path.result_list
results.reverse()
step_index = 0
screen.fill(black)
anim_path.draw_board()
anim_path.draw_result()
if not one_step:
for i in range(0,step_index+1):
step = results[i]
anim_path.draw_path(step[0],step[1],step[2], red, 3)
else:
step = results[step_index]
anim_path.draw_path(step[0],step[1],step[2], red, 3)
pygame.display.flip()
#clock.tick(5)
pygame.quit()
截图：
按左右键进行路径的跟踪，空格进行单步路径根据的切换。G键重新生成路径。