Instantly share code, notes, and snippets.

@wd /a_start.py
Created Nov 24, 2018

Embed
What would you like to do?
#!/usr/bin/python
import sys
import random
RED = '\033[31m'
GREEN = '\033[32m'
GRAY = '\033[35m'
NC = '\033[0m'
class Point(object):
x = 0
y = 0
close = False
open = False
start = False
end = False
wall = False
H = 99
G = 99
parent = None
def __init__(self, **kwargs):
if 'x' in kwargs:
self.x = kwargs['x']
if 'y' in kwargs:
self.y = kwargs['y']
self.key = '{}-{}'.format(self.x, self.y)
def __str__(self):
return '{},H{:2},G{:2},F{:2},P{:3}'.format(
self.key,
self.H if self.H != 99 else '',
self.G if self.G != 99 else '',
self.G + self.H if self.G != 99 else '',
self.parent.key if self.parent else '')
def __lt__(self, other):
return self.x < other.x if self.y == other.y else self.y < other.y
def get_area(width, height):
area = {}
for i in range(width):
for j in range(height):
point = Point(x=i, y=j)
area[point.key] = point
return area
def show_result(area_hash):
prev_y = -1
for point in sorted(area_hash.values()):
if ( prev_y != point.y ):
if (prev_y != -1):
print('')
prev_y = point.y
if point.start:
format = RED + 'S' + NC
elif point.end:
format = RED + 'E' + NC
elif point.wall:
format = GRAY + 'W' + NC
elif point.close:
format = GREEN + '0' + NC
else:
format = ' '
print((format + '({}) ').format(point), end='')
print('')
def set_preset(area, start, end, wall):
area[start].start = True
area[end].end = True
for key in wall:
area[key].wall = True
return area
def is_valid_point(point, width, height):
if point.wall or point.close:
return False
if point.x < 0 or point.x > width:
return False
if point.y < 0 or point.y > height:
return False
return True
def get_around(area, point, width, height):
n = '{}-{}'.format(point.x, point.y - 1)
s = '{}-{}'.format(point.x, point.y + 1)
l = '{}-{}'.format(point.x - 1, point.y)
r = '{}-{}'.format(point.x + 1, point.y)
res = {}
for key in [n, s, l, r]:
if key in area and is_valid_point(area[key], width, height):
area[key].parent = point
area[key].G = area[key].G if area[key].G != 99 else (point.G if point.G != 99 else 0) + 1
res[key] = area[key]
return res
def get_H(point, end_point):
return abs(point.x - end_point.x) + abs(point.y - end_point.y)
step = 0
opened = {}
def go(area, start, end, width, height):
global step, opened
start_point = area[start]
end_point= area[end]
start_point.close = True
if start_point.key in opened:
del opened[start_point.key]
points = get_around(area, start_point, width, height)
opened.update(points)
rnd = random.choice(list(opened))
next_point = area[rnd]
for key, point in opened.items():
point.H = get_H(point, end_point)
if point.H + point.G <= next_point.H + next_point.G:
next_point = point
print('step {}: {}'.format(step, next_point))
step += 1
if step >= 3:
pass
if next_point and next_point.key != end:
go(area, next_point.key, end, width, height)
def get_result(area, start, end):
print('{}{}{} <- '.format(RED, area[end].key, NC), end='')
parent = area[end].parent
if(parent.key != start):
get_result(area, start, parent.key)
else:
print('{}{}{}'.format(RED, area[start].key, NC), end='')
def main():
width = 10
height = 10
start = '1-3'
end = '8-4'
wall = ['2-2', '3-2', '3-3', '3-4', '3-5', '3-6', '5-4', '2-6', '1-6']
area = get_area(width, height)
area = set_preset(area, start, end, wall)
go(area, start, end, width, height)
show_result(area)
get_result(area, start, end)
if __name__ == '__main__':
main()
@wd

This comment has been minimized.

Copy link
Owner

wd commented Nov 24, 2018

image

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment