A* in IPython

# coding: utf-8

# In[1]:

from IPython.display import SVG

# In[2]:

CELL_SIZE = 10
GRID_SIZE = 50

# In[3]:

def tosvg(tiles, border=0):
    import xml.etree.ElementTree as ET
    svg = ET.Element('svg', xmlns="http://www.w3.org/2000/svg", version="1.1",
                      height = "500", width = "500")

    for tile in tiles:
        x,y = tile.grid_location
        xmin = x * CELL_SIZE
        xmax = (x + 1) * CELL_SIZE
        ymin = y * CELL_SIZE
        ymax = (y + 1) * CELL_SIZE
        p = [(xmin, ymin), (xmax, ymin), (xmax, ymax), (xmin, ymax)]
        point_list = " ".join(["%d,%d" % (a, b) for (a, b) in p])
        ET.SubElement(svg, "polygon", fill=tile.tile_color, stroke="black",
                     points = point_list)
            
    return ET.tostring(svg)

# In[4]:

class Tile:
    grid_location = (0,0)
    tile_color = 'honeydew'
    status = 'normal'
    h = 0
    g = 0
    f = 0
    leader = None
    
    def __init__(self, loc):
        self.grid_location = loc
        self.tile_color = 'honeydew'
        x,y  = loc
        loc_number = x + y
        if loc_number % 2 == 0:
            self.tile_color = 'lightgray'

    def set_status_barrier(self):
        self.status = 'barrier'
        self.tile_color = 'darkslategray'
    
    def set_status_origin(self):
        self.status = 'origin'
        self.tile_color = 'firebrick'
        return self.grid_location

    def set_status_target(self):
        self.status = 'target'
        self.tile_color = 'forestgreen'
        return self.grid_location
    
    def calculate_heuristic(self, target):
        tx, ty = target
        x, y = self.grid_location
        self.h = (abs(x - tx) + abs(y - ty))

# In[5]:

def get_neighbors(n, open_list, closed_list, tiles):
    x, y = n.grid_location
    neighbors = []
    neighbor_locations = [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]
    for p in neighbor_locations:
        for tile in tiles:
            if p == tile.grid_location:
                if tile not in open_list:
                    if tile not in closed_list:
                        if tile.status != 'barrier':
                            tile.g = n.g + 1
                            tile.leader = n
                            neighbors.append(tile)
                            
    return neighbors

# In[6]:

open_list = []
closed_list = []

# In[7]:

tiles = []
for j in range(GRID_SIZE):
    for i in range(GRID_SIZE):
        tiles.append(Tile((i,j)))

origin_location = (0, 0)
target_location = (0, 0)
origin_tile = None
target_tile = None

# In[8]:

barrier_set = []
for x in range(5,21):
    barrier_set.append((x,10))
    barrier_set.append((x,35))
for y in range(11,35):
    barrier_set.append((20,y))
for y in range(11,18):
    barrier_set.append((5,y))
for y in range(21,35):
    barrier_set.append((5,y))
for x in range(5,14):
    barrier_set.append((x,21))
for tile in tiles:
    x,y = tile.grid_location
    if (x,y) in barrier_set:
        tile.set_status_barrier()
    if (x == 0) or (x == (GRID_SIZE-1)) or (y == 0) or (y == (GRID_SIZE-1)):
        tile.set_status_barrier()
    if (x == 10) and (y == 25):
        origin_location = tile.set_status_origin()
        origin_tile = tile
    if (x == 40) and (y == 27):
        target_location = tile.set_status_target()
        target_tile = tile

# In[9]:

for tile in tiles:
    tile.calculate_heuristic(target_location)

# In[10]:

SVG(tosvg(tiles))

# In[11]:

open_list.append(origin_tile)

# In[12]:

target_reached = False

while not target_reached:
    for tile in open_list:
        tile.f = tile.g + tile.h

    n = open_list[0]
    for tile in open_list:
        if tile.f < n.f:
            n = tile
    
    if n.status == 'target':
        target_reached = True
    else:
        open_list.remove(n)
        closed_list.append(n)
        neighbors = get_neighbors(n, open_list, closed_list, tiles)
        for neighbor in neighbors:
            open_list.append(neighbor)

# In[13]:

print(n.grid_location)

# In[14]:

path_completed = False
while not path_completed:
    n = n.leader
    if n.status == 'origin':
        path_completed = True
    else:
        n.status = 'path'
        n.tile_color = 'cadetblue'

SVG(tosvg(tiles))