# Tk_avoidance_walk_6.py

# Tk_avoidance_walk_6.py

import random
from Tkinter import *
from math import *

ri = random.randint
rs = random.shuffle
rc = random.choice

ww = 600
hh = 600

root = Tk()
root.title("Tk_avoidance_walk")
root.geometry("%dx%d+-6+-2"%(ww,hh))
cv = Canvas(width=ww, height=hh, bg='white')
cv.pack()

steps = ["N","E","S","W"]

r = 10
grid = dict([((x,y), 0) for x in range(r,ww-r) for y in range(r,hh-r)])
xy__ = x,y = ww/2, hh/2
xy = [(x,y)]
total = 1
grid[x,y] = total
path = [steps[:]]

while 1:
    x,y = xy[-1]
    ttt = []
    vvv = ((x,y-r),(x+r,y),(x,y+r),(x-r,y))
    for x2,y2 in vvv:
        if (x2,y2) in grid:
            step = steps[vvv.index((x2,y2))]
            try:
                if not grid[x2,y2] and (step in path[-1]):
                    ttt += [(x2, y2, step)]
            except:
                0
    if ttt:
        x2,y2,ttt = rc(ttt)
        total = total+1
        grid[x2,y2] = total
        path[-1].remove(ttt)
        xy.append((x2,y2))
        path.append((steps[:]))
    else:
        path.pop()
        xy.pop()

    if step:
        try:
            cv.create_line(xy[-2:],fill='red')
        except:
            break
        cv.update()

xy = [xy__]
Lx, Ly = max(grid.keys())
L = (Lx/5)*(Ly/5)

path = []
block = []
prev = []
i = 1
while 1:
    x,y = xy[-1]
    if len(path) < len(xy):
        ttt = []
        vvv = [(x,y-r),(x+r,y),(x,y+r),(x-r,y)]
        for x2,y2 in vvv:
            if (x2,y2) in grid:
                if (x2,y2) not in xy:
                    ttt += [(grid[x2,y2],x2,y2)]
        path.append(ttt)
    if path[-1]:
        t = min(path[-1])
        path[-1].remove(t)
        zzz,x2,y2 = t

        xy += [(x2,y2)]

        cv.delete('all')
        cv.create_line(xy,fill='blue')
        cv.update()
    else:
        if (x,y) in block:
            i += 5
        else:
            block += [(x,y)]
            block = block[-100:]
            i = 1
        if len(xy)-i > 4:
            xy = xy[:-i]
            path = path[:-i]

    # print len(xy)