app - phase 1.py

# David Chen and Brian Yeh - CS440 Spring 2017

from random import choice, randint, random
from win32api import GetSystemMetrics
import pygame
import math
from datetime import datetime
from utils.the_david_brian_heap import DavidsAndBriansHeapForCellPriorityWithAReallyLongName as DABHFCPWARLN
from utils.colors import *
from utils.helper_defs import round_down_to_multiple as RDTM, euclidean_dist as E_dist, manhattan_dist as M_dist, \
                              change_direction as CD, chebyshev_dist as C_dist, our_inadmissible_dist as In_dist, \
                              our_admissible_dist as A_dist

SYSTEM_WIDTH = GetSystemMetrics(0)
SYSTEM_HEIGHT = GetSystemMetrics(1)
# print(SYSTEM_WIDTH, SYSTEM_HEIGHT)
# maps need to be 160 columns by 120 rows so the aspect ratio is 4:3 and thus landscape mode, wide > tall
GRID_BLOCKS_TALL = 120
GRID_BLOCKS_WIDE = 160

# assume screen to be landscape, so map height = map width = screen height, which is the lower pixel count
MAP_HEIGHT = SYSTEM_HEIGHT
SCALE = int(SYSTEM_HEIGHT / GRID_BLOCKS_TALL)
MAP_WIDTH = SCALE * GRID_BLOCKS_WIDE

INTERFACE_HEIGHT = MAP_HEIGHT
INTERFACE_WIDTH = SYSTEM_WIDTH - MAP_WIDTH
INTERFACE_PADDING = SCALE

# print(MAP_WIDTH,MAP_HEIGHT,INTERFACE_HEIGHT,INTERFACE_WIDTH,INTERFACE_PADDING)

NUMBER_OF_HTT_AREAS = 8
NUMBER_OF_RIVERS = 4
NUMBER_OF_BLOCKED_CELLS = int(GRID_BLOCKS_WIDE*GRID_BLOCKS_TALL*.2)

DEFAULT_BORDER_COLOR = LIGHT_GRAY
FONT_SIZE = 15
FONT = None
INTERNAL_MAP = []  # internal map (list of lists)
EXTERNAL_MAP_BASE = None  # map visual with no goals
EXTERNAL_MAP_FULL = None  # map visual with goals and all
START_NODE = None
GOAL_NODE = None
MAIN_SCREEN = None
GRAPH = None

H = A_dist
A_WEIGHT = 1.25
HTT_COORDS = None

# cell types
# blocked = 0
# regular unblocked = 1
# hard to traverse = 2x

class Cell(object):
    def __init__(self, pixel_x, pixel_y, row, col, c_type):
        self.pixel_x = int(pixel_x)
        self.pixel_y = int(pixel_y)
        self.row = int(row)
        self.col = int(col)
        self.c_type = int(c_type)
        self.is_highway = self.is_start = self.is_goal = self.in_fringe = self.expanded_already = False
        self.parent = None
        self.neighbors = []
        self.g_value = self.h_value = None
        if self.g_value and self.h_value:
            self.f_value = self.g_value + self.h_value
        else:
            self.f_value = None

    def get_color(self):
        if self.is_start:  # start cell
            return GREEN
        elif self.is_goal:  # goal cell
            return RED
        elif self.is_highway:  # is highway and is...
            if self.c_type == 1:   # normal cell
                return CYAN
            elif self.c_type == 2:  # HTT cell
                return DARK_CYAN
        elif self.c_type == 0:  # blocked cell
            return BLACK
        elif self.c_type == 1:  # normal cell
            return WHITE
        elif self.c_type == 2:  # HTT cell
            return BROWN
        else:  # unknown cell
            return YELLOW

    def get_type_string(self):
        if self.is_start:
            return 'START CELL'
        elif self.is_goal:
            return 'GOAL CELL'
        elif self.is_highway:  # is highway and is...
            if self.c_type == 1:  # normal cell
                return 'NORMAL HIGHWAY CELL'
            elif self.c_type == 2:  # HTT cell
                return 'HTT HIGHWAY CELL'
        elif self.c_type == 0:  # blocked cell
            return 'BLOCKED CELL'
        elif self.c_type == 1:  # normal cell
            return 'NORMAL CELL'
        elif self.c_type == 2:  # HTT cell
            return 'HTT CELL'
        else:  # unknown cell
            return 'UNKNOWN CELL'

    def is_edge_cell(self):
        if self.row == 0 or self.row == GRID_BLOCKS_TALL - 1 or self.col == 0 or self.col == GRID_BLOCKS_WIDE - 1:
            return True
        else:
            return False


def load_user_interface():


    pygame.draw.rect(MAIN_SCREEN, LIGHT_GRAY, (MAP_WIDTH, 0, INTERFACE_WIDTH, INTERFACE_HEIGHT), 0)  # BORDER
    pygame.draw.rect(MAIN_SCREEN, LIGHT_GRAY, (MAP_WIDTH + INTERFACE_PADDING, INTERFACE_PADDING,
                                               INTERFACE_WIDTH - 2 * INTERFACE_PADDING,
                                               INTERFACE_HEIGHT - 2 * INTERFACE_PADDING), 0)  # INNER

    textsurface = FONT.render('Click on any cell for more info', True, BLACK)
    MAIN_SCREEN.blit(textsurface,(MAP_WIDTH + INTERFACE_PADDING, INTERFACE_PADDING+50,
                                               INTERFACE_WIDTH - 2 * INTERFACE_PADDING,
                                               INTERFACE_HEIGHT - 2 * INTERFACE_PADDING))

    textsurface = FONT.render('Press G for new start and goal nodes', True, BLACK)
    MAIN_SCREEN.blit(textsurface, (MAP_WIDTH + INTERFACE_PADDING, INTERFACE_PADDING + 100,
                                   INTERFACE_WIDTH - 2 * INTERFACE_PADDING,
                                   INTERFACE_HEIGHT - 2 * INTERFACE_PADDING))

    textsurface = FONT.render('Press N for new map', True, BLACK)
    MAIN_SCREEN.blit(textsurface, (MAP_WIDTH + INTERFACE_PADDING, INTERFACE_PADDING + 150,
                                   INTERFACE_WIDTH - 2 * INTERFACE_PADDING,
                                   INTERFACE_HEIGHT - 2 * INTERFACE_PADDING))

    textsurface = FONT.render('Press U, A, or W for UCS, A*, w.A*', True, BLACK)
    MAIN_SCREEN.blit(textsurface, (MAP_WIDTH + INTERFACE_PADDING, INTERFACE_PADDING + 200,
                                   INTERFACE_WIDTH - 2 * INTERFACE_PADDING,
                                   INTERFACE_HEIGHT - 2 * INTERFACE_PADDING))

    textsurface = FONT.render('CURRENT WEIGHTED A* WEIGHT: {}'.format(A_WEIGHT), True, BLACK)
    MAIN_SCREEN.blit(textsurface, (MAP_WIDTH + INTERFACE_PADDING, INTERFACE_PADDING + 225,
                                   INTERFACE_WIDTH - 2 * INTERFACE_PADDING,
                                   INTERFACE_HEIGHT - 2 * INTERFACE_PADDING))

    textsurface = FONT.render('Press 1-5 for different heuristics', True, BLACK)
    MAIN_SCREEN.blit(textsurface, (MAP_WIDTH + INTERFACE_PADDING, INTERFACE_PADDING + 250,
                                   INTERFACE_WIDTH - 2 * INTERFACE_PADDING,
                                   INTERFACE_HEIGHT - 2 * INTERFACE_PADDING))

    textsurface = FONT.render('1: CHEB, 2: MAN, 3: EUC', True, BLACK)
    MAIN_SCREEN.blit(textsurface, (MAP_WIDTH + INTERFACE_PADDING, INTERFACE_PADDING + 300,
                                   INTERFACE_WIDTH - 2 * INTERFACE_PADDING,
                                   INTERFACE_HEIGHT - 2 * INTERFACE_PADDING))

    textsurface = FONT.render('4: INADMISSIBLE, 5: ADMISSIBLE', True, BLACK)
    MAIN_SCREEN.blit(textsurface, (MAP_WIDTH + INTERFACE_PADDING, INTERFACE_PADDING + 325,
                                   INTERFACE_WIDTH - 2 * INTERFACE_PADDING,
                                   INTERFACE_HEIGHT - 2 * INTERFACE_PADDING))

    if H == C_dist:
        h_string = "CHEBYSHEV"
    elif H == M_dist:
        h_string = "MANHATTAN"
    elif H == E_dist:
        h_string = "EUCLIDEAN"
    elif H == In_dist:
        h_string = "INADMISSIBLE"
    elif H == A_dist:
        h_string = "ADMISSIBLE"
    else:
        h_string = "ERROR"


    textsurface = FONT.render('CURRENT HEURISTIC: {}'.format(h_string), True, BLACK)
    MAIN_SCREEN.blit(textsurface, (MAP_WIDTH + INTERFACE_PADDING, INTERFACE_PADDING + 350,
                                   INTERFACE_WIDTH - 2 * INTERFACE_PADDING,
                                   INTERFACE_HEIGHT - 2 * INTERFACE_PADDING))


    textsurface = FONT.render('Press C to clear labels/path', True, BLACK)
    MAIN_SCREEN.blit(textsurface, (MAP_WIDTH + INTERFACE_PADDING, INTERFACE_PADDING + 400,
                                   INTERFACE_WIDTH - 2 * INTERFACE_PADDING,
                                   INTERFACE_HEIGHT - 2 * INTERFACE_PADDING))

    textsurface = FONT.render('Press Esc to close program', True, BLACK)
    MAIN_SCREEN.blit(textsurface, (MAP_WIDTH + INTERFACE_PADDING, INTERFACE_PADDING + 500,
                                   INTERFACE_WIDTH - 2 * INTERFACE_PADDING,
                                   INTERFACE_HEIGHT - 2 * INTERFACE_PADDING))

    pygame.display.update()
    return

def save_the_map():

    f = open('Generated Map.txt'.format(datetime.now()), 'a')
    f.write('{},{}\n'.format(START_NODE.row, START_NODE.col))
    f.write('{},{}\n'.format(GOAL_NODE.row, GOAL_NODE.col))
    for region in HTT_COORDS:
        f.write('{},{}\n'.format(region[1],region[0]))



    f.close()



def main():
    global FONT, MAIN_SCREEN, INTERNAL_MAP, H, A_WEIGHT

    pygame.init()
    MAIN_SCREEN = pygame.display.set_mode((SYSTEM_WIDTH, SYSTEM_HEIGHT), pygame.FULLSCREEN)
    icon = pygame.image.load('images/robot_icon.png')
    pygame.display.set_icon(icon)
    pygame.display.set_caption('CS440 Assignment 1')
    FONT = pygame.font.SysFont("monospace", FONT_SIZE)

    load_user_interface()
    generate_a_map()
    save_the_map()
    # draw_cell_rect(MAIN_SCREEN, GRASS_GREEN, 0, 0, RED, 1)  # top left corner
    # draw_cell_rect(MAIN_SCREEN, CYAN, SYSTEM_WIDTH - SCALE, 0, RED, 1)  # top right corner
    # draw_cell_rect(MAIN_SCREEN, CYAN, 0, SYSTEM_HEIGHT - SCALE, RED, 1)  # bottom left corner
    # draw_cell_rect(MAIN_SCREEN, GREEN, SYSTEM_WIDTH - SCALE, SYSTEM_HEIGHT - SCALE, RED, 1)  # bottom right corner
    #
    # draw_cell_rect(MAIN_SCREEN, PINK, MAP_WIDTH, 0, RED, 1)  # top left corner OF INTERFACE
    # draw_cell_rect(MAIN_SCREEN, GREEN, MAP_WIDTH, SYSTEM_HEIGHT - SCALE, RED, 1)  # bottom left corner OF INTERFACE
    pygame.display.update()

    # print_grid_map(grid)
    previous_highlighted_cell = normal_color = highlighted_cell = None
    while True:
        for e in pygame.event.get():
            if e.type == pygame.QUIT:
                pygame.quit()
                quit()

            if e.type == pygame.KEYDOWN:
                if e.key == pygame.K_c:  # clear labels, keep map and start/goal
                    MAIN_SCREEN.blit(EXTERNAL_MAP_FULL, (0, 0))
                    load_user_interface()
                    reset_cells()
                    pygame.display.update()
                if e.key == pygame.K_n:  # new map
                    generate_a_map()
                    pygame.display.update()
                if e.key == pygame.K_g:  # new start/goal cells
                    draw_get_start_and_goal()
                    pygame.display.update()
                if e.key == pygame.K_a:  # rerun a* normal
                    a_star()
                    pygame.display.update()
                if e.key == pygame.K_b:  # rerun a* normal with search space showing
                    a_star(show_search_space=True)
                    pygame.display.update()
                if e.key == pygame.K_u:  # rerun UCS
                    uniform_cost_search()
                    pygame.display.update()
                if e.key == pygame.K_w:  # rerun weighted A*
                    a_star_weighted(WEIGHT)
                    pygame.display.update()
                if e.key == pygame.K_1:
                    H = C_dist
                    load_user_interface()
                    set_cell_values()
                if e.key == pygame.K_2:
                    H = M_dist
                    load_user_interface()
                    set_cell_values()
                if e.key == pygame.K_3:
                    H = E_dist
                    load_user_interface()
                    set_cell_values()
                if e.key == pygame.K_4:
                    H = In_dist
                    load_user_interface()
                    set_cell_values()
                if e.key == pygame.K_5:
                    H = A_dist
                    load_user_interface()
                    set_cell_values()

                if e.key == pygame.K_LEFTBRACKET:
                    WEIGHT -= 0.25
                    load_user_interface()
                if e.key == pygame.K_RIGHTBRACKET:
                    WEIGHT += 0.25
                    load_user_interface()

                if e.key == pygame.K_ESCAPE:
                    pygame.quit()
                    quit()

            if e.type == pygame.MOUSEBUTTONDOWN and e.button == 1:  # if left mouse button clicked
                m_pos = pygame.mouse.get_pos()
                pix_x = m_pos[0]
                pix_y = m_pos[1]

                if pix_x < MAP_WIDTH:  # means clicked within the map and not the interface
                    c_pix_x = RDTM(pix_x, SCALE)
                    c_pix_y = RDTM(pix_y, SCALE)

                    row = int(c_pix_y / SCALE)
                    col = int(c_pix_x / SCALE)
                    clicked_cell = INTERNAL_MAP[row][col]
                    display_info(clicked_cell)
                else:
                    pass

            if e.type == pygame.MOUSEMOTION:
                m_pos = pygame.mouse.get_pos()
                pix_x = m_pos[0]
                pix_y = m_pos[1]

                if pix_x < MAP_WIDTH:  # means hovering within the map and not the interface
                    c_pix_x = RDTM(pix_x, SCALE)
                    c_pix_y = RDTM(pix_y, SCALE)
                    row = int(c_pix_y / SCALE)
                    col = int(c_pix_x / SCALE)

                    if highlighted_cell != INTERNAL_MAP[row][col]:
                        highlighted_cell = INTERNAL_MAP[row][col]

                        if previous_highlighted_cell:
                            if previous_highlighted_cell is not highlighted_cell:
                                draw_cell_rect(MAIN_SCREEN, normal_color, previous_highlighted_cell.pixel_x,
                                               previous_highlighted_cell.pixel_y, DEFAULT_BORDER_COLOR, 1)
                                pygame.display.update()

                        normal_color = MAIN_SCREEN.get_at((highlighted_cell.pixel_x + 5, highlighted_cell.pixel_y + 5))
                        draw_cell_rect(MAIN_SCREEN, YELLOW, highlighted_cell.pixel_x,
                                       highlighted_cell.pixel_y, DEFAULT_BORDER_COLOR, 1)
                        pygame.display.update()
                        previous_highlighted_cell = INTERNAL_MAP[row][col]

                else:
                    pass

    return


def generate_a_map():
    global INTERNAL_MAP, EXTERNAL_MAP_BASE, EXTERNAL_MAP_FULL

    map_surface = pygame.Surface((MAP_WIDTH, MAP_HEIGHT), pygame.SRCALPHA, 32)
    map_surface = map_surface.convert_alpha()

    draw_init_grid(map_surface)
    draw_htt_areas(map_surface, NUMBER_OF_HTT_AREAS)
    draw_rivers(map_surface, NUMBER_OF_RIVERS)
    draw_blocked_cells(map_surface, NUMBER_OF_BLOCKED_CELLS)

    EXTERNAL_MAP_BASE = map_surface.copy()

    draw_get_start_and_goal()




    return


def draw_init_grid(map_surface):
    global INTERNAL_MAP
    grid_map = []

    for vertical_pixel in range(0, MAP_HEIGHT, SCALE):
        temp_row = []
        for horizontal_pixel in range(0, MAP_WIDTH, SCALE):
            temp_cell = Cell(horizontal_pixel, vertical_pixel, vertical_pixel / SCALE, horizontal_pixel / SCALE, 1)
            temp_row.append(temp_cell)
            draw_cell_rect(map_surface, temp_cell.get_color(), horizontal_pixel, vertical_pixel, DEFAULT_BORDER_COLOR, 1)
        grid_map.append(temp_row)

    INTERNAL_MAP = grid_map
    MAIN_SCREEN.blit(map_surface, (0, 0))
    pygame.display.update()
    return


def draw_htt_areas(map_surface, num_htt_areas):
    global HTT_COORDS
    random_htt_area_coords = []

    while len(random_htt_area_coords) != num_htt_areas:
        htt_area_origin_column = randint(0, GRID_BLOCKS_WIDE - 1)
        htt_area_origin_row = randint(0, GRID_BLOCKS_TALL - 1)
        htt_area_origin_coords = [htt_area_origin_column, htt_area_origin_row]
        if htt_area_origin_coords not in random_htt_area_coords:
            random_htt_area_coords.append(htt_area_origin_coords)

    for coordinates in random_htt_area_coords:
        htt_col = coordinates[0]
        htt_row = coordinates[1]
        for tmp_col in range(htt_col-15, htt_col+16):
            for tmp_row in range(htt_row-15, htt_row+16):
                if tmp_col < 0 or tmp_col > GRID_BLOCKS_WIDE - 1 or tmp_row < 0 or tmp_row > GRID_BLOCKS_TALL - 1:
                    continue
                else:
                    if random() < 0.5:
                        tmp_cell = INTERNAL_MAP[tmp_row][tmp_col]
                        tmp_cell.c_type = 2  # set to HTT
                        draw_cell_rect(map_surface, tmp_cell.get_color(),
                                       tmp_cell.pixel_x, tmp_cell.pixel_y, DEFAULT_BORDER_COLOR, 1)

        MAIN_SCREEN.blit(map_surface, (0, 0))
        pygame.display.update()

    HTT_COORDS = random_htt_area_coords
    return


def draw_rivers(map_surface, num_rivers):

    for r_num in range(num_rivers):
        valid_river = False
        drawing_q = []

        while not valid_river:
            # if not valid river...
            drawing_q = []  # reset the drawing queue
            river_origin_cell = get_riverless_edge_cell()  # get a new river origin not on a river
            current_direction = river_start_direction(river_origin_cell)  # get direction to begin in
            drawing_q.append(river_origin_cell)
            edge_hit = False
            river_hit = False
            self_hit = False

            begin_direction = current_direction
            begin_cell = river_origin_cell

            while not edge_hit:
                mini_q = twenty_steps_in_direction(begin_cell, begin_direction)
                if not mini_q:  # in the event the function above encountered another river, break and scrap
                    river_hit = True
                    break
                else:  # below here means the function made 20 steps or encountered an edge
                    for tmp_cell in mini_q:  # check if any of the mini q cells are already existing in q; if so, remake
                        if tmp_cell in drawing_q:
                            self_hit = True
                            break
                    begin_direction = CD(begin_direction)
                    begin_cell = mini_q[-1]
                    drawing_q.extend(mini_q)

                    if begin_cell.is_edge_cell():  # if the last cell queued is an edge cell, set edge_hit to true
                        edge_hit = True

            if len(drawing_q) >= 100 and not river_hit and not self_hit:
                valid_river = True

        if valid_river:
            for cell in drawing_q:
                cell.is_highway = True
                draw_cell_rect(map_surface, cell.get_color(), cell.pixel_x, cell.pixel_y, DEFAULT_BORDER_COLOR, 1)
                MAIN_SCREEN.blit(map_surface, (0, 0))
                pygame.display.update()

            # first_cell = drawing_q[0]
            # draw_cell_rect(map_surface, GREEN, first_cell.pixel_x, first_cell.pixel_y, LIGHT_GRAY, 1)
            # last_cell = drawing_q[-1]
            # draw_cell_rect(map_surface, RED, last_cell.pixel_x, last_cell.pixel_y, LIGHT_GRAY, 1)

    return


def draw_blocked_cells(map_surface, num_blocked):

    blocked_cells_drawn = 0
    while blocked_cells_drawn != num_blocked:
        random_cell = INTERNAL_MAP[randint(0, GRID_BLOCKS_TALL-1)][randint(0, GRID_BLOCKS_WIDE-1)]
        if not random_cell.is_highway or not random_cell.c_type:
            random_cell.c_type = 0  # update to blocked cell
            blocked_cells_drawn += 1
            draw_cell_rect(map_surface, random_cell.get_color(), random_cell.pixel_x, random_cell.pixel_y, DEFAULT_BORDER_COLOR, 1)

    MAIN_SCREEN.blit(map_surface, (0, 0))
    pygame.display.update()
    return


def draw_get_start_and_goal():
    global EXTERNAL_MAP_FULL, START_NODE, GOAL_NODE

    tmp_map_surface = EXTERNAL_MAP_BASE.copy()

    start_row = start_col = goal_row = goal_col = color = None

    if START_NODE:  # if start node already exists, clear it
        START_NODE.is_start = False

    if GOAL_NODE:  # if goal node already exists, clear it
        GOAL_NODE.is_goal = False

    MAIN_SCREEN.blit(tmp_map_surface, (0,0))
    pygame.display.update()

    while True:  # first determine the start cell
        if random() < 0.5:
            start_row = choice([randint(0, 19), randint(100, 119)])  # rows: top 20 or bottom 20
            start_col = randint(0, GRID_BLOCKS_WIDE-1)
        else:
            start_row = randint(0, GRID_BLOCKS_TALL-1)
            start_col = choice([randint(0, 19), randint(139, 159)])  # cols: left 20 or right 20

        START_NODE = INTERNAL_MAP[start_row][start_col]
        if START_NODE.c_type != 0:  # if this cell is not blocked, break out of the while loop
            break

    while True:  # then determine goal cell and test the distance
        if random() < 0.5:
            goal_row = choice([randint(0, 19), randint(100, 119)])  # rows: top 20 or bottom 20
            goal_col = randint(0, GRID_BLOCKS_WIDE-1)
        else:
            goal_row = randint(0, GRID_BLOCKS_TALL-1)
            goal_col = choice([randint(0, 19), randint(139, 159)])  # cols: left 20 or right 20

        GOAL_NODE = INTERNAL_MAP[goal_row][goal_col]
        distance = E_dist(START_NODE, GOAL_NODE)
        if GOAL_NODE.c_type != 0 and distance >= 100:  # if this cell is not blocked, test to see if it's euclidean distance >= 100

            START_NODE.is_start = True
            GOAL_NODE.is_goal = True

            # code snippet below draws a halo around start node and goal node (comes before goal/start drawing so its underneath them)
            # tmp_rect = pygame.Surface((SCALE * 7, SCALE * 7))
            # tmp_rect.set_alpha(100)
            # tmp_rect.fill(YELLOW)
            # tmp_map_surface.blit(tmp_rect, (START_NODE.pixel_x - 3 * SCALE, START_NODE.pixel_y - 3 * SCALE))
            # tmp_map_surface.blit(tmp_rect, (GOAL_NODE.pixel_x - 3 * SCALE, GOAL_NODE.pixel_y - 3 * SCALE))
            # -------

            draw_cell_rect(tmp_map_surface, START_NODE.get_color(), START_NODE.pixel_x, START_NODE.pixel_y, DEFAULT_BORDER_COLOR, 1)
            draw_cell_rect(tmp_map_surface, GOAL_NODE.get_color(), GOAL_NODE.pixel_x, GOAL_NODE.pixel_y, DEFAULT_BORDER_COLOR, 1)

            MAIN_SCREEN.blit(tmp_map_surface, (0,0))
            pygame.display.update()

            break

    EXTERNAL_MAP_FULL = tmp_map_surface.copy()

    # AFTER ESTABLISHING START/GOALS, SET THE G, H, AND F VALUES AND SET THE NEIGHBORS OF EACH ONE AND SOLVE PATH
    set_cell_values()
    set_cell_neighbors()

    # a_star()
    # a_star_weighted(1.25)
    # uniform_cost_search()

    return


def twenty_steps_in_direction(cell, direction):  # returns empty list if invalid river, otherwise returns mini q

    mini_q = []
    current_row = cell.row
    current_col = cell.col

    if direction == 'Up':
        tmp_range = range(current_row, current_row - 20, -1)  # iterates from current cell's row to 20 rows above it
        vertical = True
        sign = -1
    elif direction == 'Down':
        tmp_range = range(current_row, current_row + 20, 1)  # iterates from current cell's row to 20 rows below it
        vertical = True
        sign = 1
    elif direction == 'Left':
        tmp_range = range(current_col, current_col - 20, -1)  # iterates from current cell's col to 20 rows left of it
        vertical = False
        sign = -1
    elif direction == 'Right':
        tmp_range = range(current_col, current_col + 20, 1)  # iterates from current cell's col to 20 rows right of it
        vertical = False
        sign = 1
    else:
        print('NOT SUPPOSE TO GET HERE.')
        return

    for new in tmp_range:
        if vertical:
            next_cell = INTERNAL_MAP[new + sign*1][current_col]
        else:
            next_cell = INTERNAL_MAP[current_row][new + sign * 1]

        if next_cell.is_highway:
            return []

        if next_cell.is_edge_cell():  # if prematurely hits edge cell, add that edge cell to mini q and return
            mini_q.append(next_cell)
            return mini_q
        else:
            mini_q.append(next_cell)  # otherwise continue adding next cells to q

    return mini_q  # if not failed, then return list which will guarantee to have at least one cell in it


def river_start_direction(cell):

    if cell.col == 0: return 'Right'
    elif cell.col == GRID_BLOCKS_WIDE - 1: return 'Left'
    elif cell.row == 0: return 'Down'
    elif cell.row == GRID_BLOCKS_TALL - 1: return 'Up'
    else: return 'DIRECTIONAL ERROR OCCURRED.'


def get_riverless_edge_cell():  # returns a cell object on the edge that is not occupied by a river
    # random cell on top-most row excluding corners
    rand_top_edge = [0, randint(1, GRID_BLOCKS_WIDE - 2)]
    # random cell on bottom-most row excluding corners
    rand_bot_edge = [GRID_BLOCKS_TALL - 1, randint(1, GRID_BLOCKS_WIDE - 2)]

    # random cell on left-most column excluding corners
    rand_left_edge = [randint(1, GRID_BLOCKS_TALL - 2), 0]
    # random cell on right-most column excluding corners
    rand_right_edge = [randint(1, GRID_BLOCKS_TALL - 2), GRID_BLOCKS_WIDE - 1]

    # now choose from the above four:
    rand_row_col = choice([rand_top_edge, rand_bot_edge, rand_left_edge, rand_right_edge])

    temp_cell = INTERNAL_MAP[rand_row_col[0]][rand_row_col[1]]

    if temp_cell.is_highway:
        return get_riverless_edge_cell()
    else:
        return temp_cell


def print_grid_map():
    for row in INTERNAL_MAP:
        for cell in row:
            g_s_indicator = highway_indicator = ''
            if cell.is_start:
                g_s_indicator = 'START'
            if cell.is_goal:
                g_s_indicator = 'GOAL'
            if cell.is_highway:
                highway_indicator = 'HIGHWAY'
            print('[{}][{}]-{}-{}-{}'.format(cell.row, cell.col, cell.c_type, highway_indicator, g_s_indicator), end='  |  ')
        print('')

    return


def print_neighbors():

    for row in INTERNAL_MAP:
        for cell in row:
            print('R{}C{}: {}'.format(cell.row, cell.col, [(c.row, c.col) for c in cell.neighbors]))


def draw_cell_rect(map_surface, inner_color, pix_x, pix_y, border_color = DEFAULT_BORDER_COLOR, border_thickness = 0):

    if border_thickness <= 0:  # if not border needed
        pygame.draw.rect(map_surface, inner_color, (pix_x, pix_y, SCALE, SCALE), 0)
    else:
        pygame.draw.rect(map_surface, border_color, (pix_x, pix_y, SCALE, SCALE), border_thickness)
        pygame.draw.rect(map_surface, inner_color, (pix_x + border_thickness,
                                                    pix_y + border_thickness,
                                                    SCALE - border_thickness,
                                                    SCALE - border_thickness), 0)

    return


def set_cell_values():
    for row in INTERNAL_MAP:
        for cell in row:
            if cell.c_type == 0:  # if blocked cell, you can't get to it, and you can't use it to get anywhere
                cell.h_value = 99999999
                cell.g_value = 99999999
            else:
                cell.h_value = H(cell, GOAL_NODE)  # HEURISTIC VALUE (EUCLIDEAN, MANHATTAN, ETC.)
                cell.g_value = 99999999  # THE COST FROM START TO N FOUND SO FAR
    return


def set_cell_neighbors():
    for r in INTERNAL_MAP:
        for cell in r:
            tmp_neighbors = []
            for row in range(cell.row-1, cell.row+2):
                if row < 0:
                    continue
                for col in range(cell.col-1, cell.col+2):
                    if col < 0:
                        continue

                    try:
                        neighbor = INTERNAL_MAP[row][col]
                        if neighbor is not cell and neighbor.c_type != 0:
                            tmp_neighbors.append(neighbor)
                    except IndexError:
                        pass
            cell.neighbors.extend(tmp_neighbors)
    return


def draw_instructions(screen, font):
    instructions = 'NOTE: Click a cell for details. Press \'c\' to clear all labels. Press \'n\' for new map.'.upper()
    label_width, label_height = font.size(instructions)
    label = font.render(instructions, 1, BLACK, DARK_CYAN)
    screen.blit(label, ((SYSTEM_WIDTH-label_width)/2, 0))
    pygame.display.update()


def display_info(cell):

    l_bgc = cell.get_color()
    if l_bgc == WHITE or l_bgc == GREEN or l_bgc == RED:
        l_ftc = BLACK
    else:
        l_ftc = WHITE

    if l_bgc == WHITE:
        l_bgc = LIGHT_GRAY

    text = '{} | h={} g={} f={} | ROW{}, COL{}'.format(cell.get_type_string(), cell.h_value, cell.g_value,
                                                       cell.h_value+cell.g_value, cell.row+1, cell.col+1)
    label_width, label_height = FONT.size(text)

    if cell.row < GRID_BLOCKS_TALL/2:
        y_offset = SCALE
    else:
        y_offset = -label_height

    if cell.col < GRID_BLOCKS_WIDE/2:
        x_offset = SCALE
    else:
        x_offset = -label_width

    label = FONT.render(text, 1, l_ftc, l_bgc)
    MAIN_SCREEN.blit(label, (cell.pixel_x+x_offset, cell.pixel_y+y_offset))
    pygame.display.update()

    return


def a_star(weight=1, show_search_space=True):
    reset_cells()

    if weight == 0:
        path_color = YELLOW
        print('\nUNIFORM COST SEARCH - - - -')
    elif weight == 1:
        path_color = GREEN
        print('\nA* NORMAL - - - -')
    else:
        path_color = CYAN
        print('\nA* WEIGHTED (w={}) - - - -'.format(weight))

    runtime_start = datetime.now()
    memory_start = memory()

    START_NODE.g_value = 0
    START_NODE.parent = None
    fringe = DABHFCPWARLN()
    fringe.insert(START_NODE, START_NODE.g_value + START_NODE.h_value * weight)
    START_NODE.in_fringe = True
    path_solution = []

    while not fringe.is_empty():

        current_cell = fringe.pop()


        # snippet colors in search process.
        if show_search_space and current_cell.c_type == 1 and not current_cell.is_highway:
            current_color = map_color_gradient(gradient_color_1, gradient_color_2, current_cell)
            tmp_rect = pygame.Surface((SCALE-1, SCALE-1))
            tmp_rect.set_alpha(100)
            tmp_rect.fill(current_color)
            MAIN_SCREEN.blit(tmp_rect, (current_cell.pixel_x+1, current_cell.pixel_y+1))
            pygame.display.update()
        # --------

        if current_cell is GOAL_NODE:  # goal found
            runtime = datetime.now() - runtime_start
            memory_used = memory() - memory_start

            previous = GOAL_NODE.parent
            while previous.parent:
                path_solution.append(previous)
                previous = previous.parent

            path_solution = path_solution[::-1]
            for cell in path_solution:
                tmp_sq = pygame.Surface((SCALE - 1, SCALE - 1))
                tmp_sq.fill(YELLOW)
                MAIN_SCREEN.blit(tmp_sq, (cell.pixel_x + 1, cell.pixel_y + 1))
                pygame.display.update()

            print('RUNTIME: {} milliseconds'.format(runtime.microseconds / 1000))
            print('LENGTH OF PATH: {}'.format(sum([cell.g_value for cell in path_solution])))
            print('NODES EXPANDED: {}'.format(sum([cell.expanded_already for row in INTERNAL_MAP for cell in row])))
            # print('MEMORY USED: {} bytes ({} MB)'.format(memory_used, memory_used / 1000000))

            return

        current_cell.expanded_already = True
        for neighbor in current_cell.neighbors:


            if not neighbor.expanded_already:
                if not neighbor.in_fringe:
                    neighbor.g_value = 99999999
                    neighbor.parent = None
                if current_cell.g_value + calc_g_value(current_cell, neighbor) < neighbor.g_value:
                    neighbor.g_value = current_cell.g_value + calc_g_value(current_cell, neighbor)
                    neighbor.parent = current_cell
                    if neighbor.in_fringe:
                        fringe.remove(neighbor)
                        neighbor.in_fringe = False
                    fringe.insert(neighbor, neighbor.g_value + neighbor.h_value * weight)
                    neighbor.in_fringe = True

    print('No Path to Goal Found.')



    return


def a_star_weighted(w):
    a_star(weight=w)
    return


def uniform_cost_search():
    a_star(weight=0)
    return


def calc_g_value(current, next):
    tmp_value = 0

    if (current.row != next.row) and (current.col != next.col):  # we are moving diagonally
        if current.c_type == 2 and next.c_type == 2:  # both are HTT
            tmp_value = math.sqrt(8)
        elif current.c_type == 1 and next.c_type == 1:  # both are normal
            tmp_value = math.sqrt(2)
        else:
            tmp_value = (math.sqrt(2) + math.sqrt(8)) / 2

    else:  # we are moving horizontally OR vertically, not both
        if current.c_type == 2 and next.c_type == 2:  # both are HTT
            tmp_value = 2
        elif current.c_type == 1 and next.c_type == 1:  # both are normal
            tmp_value = 1
        else:
            tmp_value = 1.5

    # now we check if both cells are highways
    if current.is_highway and next.is_highway:
        return tmp_value * 0.25

    return tmp_value


def memory():
    import os
    from wmi import WMI
    w = WMI('.')
    result = w.query("SELECT WorkingSet FROM Win32_PerfRawData_PerfProc_Process WHERE IDProcess=%d" % os.getpid())
    return int(result[0].WorkingSet)


def map_color_gradient(c1, c2, current_cell):
    # uses distance to goal from current cell to get current color

    percentage = (START_NODE.h_value-current_cell.h_value)/START_NODE.h_value

    if percentage > 1:
        percentage = 1
    elif percentage < 0:
        percentage = 0


    r = c2[0] - c1[0]
    g = c2[1] - c1[1]
    b = c2[2] - c1[2]

    return (int(percentage * r) + c1[0], int(percentage * g) + c1[1], int(percentage * b) + c1[2])


def reset_cells():

    set_cell_values()

    for row in INTERNAL_MAP:
        for cell in row:
            cell.parent = None
            cell.in_fringe = False
            cell.expanded_already = False


if __name__ == '__main__':
    main()