from random import randint
from numpy import reshape

def get_shortest_way(width, height, start_coord=False, finish_coord=False, print_res=False, walls=False):
	# define signs for human
	wall_sign = '▫️'
	start_sign = '♦️'
	finish_sign = '🔹'
	way_sign = '🔸'
	free_way = ' '


	# creating world map
	world_map = [[] for i in range(height)]
	for i in range(height):
		for j in range(width):
			if walls == True:
				create_wall_chance = randint(1, 100)
				if create_wall_chance >= 65:
					world_map[i].append(wall_sign)
				else:
					world_map[i].append(free_way)

			else:
				world_map[i].append(free_way)

	# placing player and finish in different positions
	if not start_coord or start_coord[0] == width or start_coord[1] == height:
		start_coord = (randint(0, width-1), randint(0, height-1))
	if not finish_coord or finish_coord[0] == width or finish_coord[1] == height:
		finish_coord = (randint(0, width-1), randint(0, height-1))

	while start_coord == finish_coord:
		finish_coord = (randint(0, width-1), randint(0, height-1))

	world_map[start_coord[1]][start_coord[0]] = start_sign
	world_map[finish_coord[1]][finish_coord[0]] = finish_sign

	# class to identify every tile on the map
	class Tile:
		def __init__(self, x, y, role):
			self.x = x
			self.y = y
			self.value = 0
			self.role = role
			self.marked = False

		def satisfies_direction_condition(self, tile):
			return ((tile.x == self.x and tile.y == self.y - 1) or 
					(tile.x == self.x + 1 and tile.y == self.y) or 
					(tile.x == self.x and tile.y == self.y + 1) or 
					(tile.x == self.x - 1 and tile.y == self.y))

		# find and return unmarked neighbors
		def neighbors(self, needed_value):
			neighbors_list = []

			for tile in tiles:
				if tile.value == needed_value and tile.role != wall_sign:
					if self.satisfies_direction_condition(tile) and tile.marked == False:
						tile.marked = True
						tile.value = self.value + 1
						neighbors_list.append(tile)

			return neighbors_list

	# filling array with Tile objects
	tiles = []
	for y in range(len(world_map)):
		for x in range(len(world_map[y])):
				tiles.append(Tile(x, y, world_map[y][x]))

	# Searching and placing start and finish
	start_pos = False
	finish_pos = False
	for i in tiles:
		if not start_pos or not finish_pos:
			if i.role == start_sign:
				start_pos = i
				start_pos.marked = True
			
			if i.role == finish_sign:
				finish_pos = i

	# making a wave of steps around starting position
	cells = start_pos.neighbors(0)				# finding neighbors of starting cell(tile)	
	cells_copy = cells.copy() 					# dont even ask, it works
	counter = 0
	while finish_pos.marked != True:
		cells = []								# clearing it to have only new neighbors in the next step of loop
		for i in cells_copy:					# going through latest(newest) neighbors
			for cell in i.neighbors(counter):	# adding new neighbors
				cells.append(cell)

		cells_copy = cells.copy()
		if cells == []:							# it passes this condition only if all possible 
			break								# cells(tiles) are already marked

	# Searching for way
	# The idea is to make a wave of steps with its values (previous code)
	#	and then go back from finish to start, by decreasing value by one
	#	every loop, so we can get the fastest and shortest way
	if finish_pos.marked:
		steps = []																	# saving all steps, so in actual code
																					# player can know where to go
		# steps.append(finish_coord)
		counter = 1
		last_visited = [finish_pos.x, finish_pos.y] 								# saving it to start from the finish
		while (finish_pos.value - counter) != 0:									# go till we dont find the start position
			for tile in tiles:														# (below) get heighbors and check their value
				if ((tile.x == last_visited[0] and tile.y == last_visited[1] - 1) 
				 or (tile.x == last_visited[0] and tile.y == last_visited[1] + 1) 
				 or (tile.x == last_visited[0] - 1 and tile.y == last_visited[1]) 
				 or (tile.x == last_visited[0] + 1 and tile.y == last_visited[1])):
					if tile.value == (finish_pos.value - counter):
						if tile.value == 0:											# if script founds the start
							break
						steps.append([tile.x, tile.y])
						counter += 1
						last_visited = [tile.x, tile.y]


		if print_res:
			# draw way in the world_map
			for step in steps:
				for tile in tiles:
					if tile.x == step[0] and tile.y == step[1]:
						tile.role = way_sign


			# show result on the screen
			unformated_array = [i.role for i in tiles]
			array = reshape(unformated_array, (height, width))
			for i in array:
				print(*i, sep=' ')

		if steps != []:
			return steps[::-1]
		return False
	else:
		return False

print(get_shortest_way(20, 20, print_res=True, walls=True))