## Friday, September 26, 2014

### simple locating goal and finding short path to it algorithm

The red square can move to any white square but is blocked by black squares. It can only check whether the square it is on is yellow (the goal). So the object is for the red square to find the yellow square and return a reasonably short path to getting there around obstacles and so on.
My algorithm is very simple, the red square keeps a list of squares he's visited, and randomly moves to another acceptable square by moving up,down,left,right, or any diagonal one square. Then he checks his list to see if he's ever been 1 move away from any square on his list starting at the beginning of the list. If he has been then he shortens his list by removing every square visited in between where he currently is and the earliest time he was 1 square away from where he is now. This has the effect of removing loops and double backs from the final path. This is like finding a "short cut" between where he is and where he was. Eventually he will end up on the yellow square and the program ends and returns his list.
**Python Source code
import Image
import random
class board():
board = [[0,0,0,0,0,0,0,0,0,0],[0,1,1,1,1,1,1,1,1,0],[0,2,1,1,1,1,1,1,1,0],[0,1,1,1,1,1,1,1,1,0], [0,1,1,1,0,0,1,1,1,0], [0,1,1,1,0,0,1,1,1,0], [0,1,1,1,1,1,1,1,1,0], [0,1,1,1,1,1,1,1,1,0], [0,1,1,1,1,1,1,1,1,0],[0,0,0,0,0,0,0,0,0,0]]
mousepos = [8,8]
def drawboard(self, img):
for i in range(0, 10):
for j in range(0, 10):
if self.board[i][j] == 1:
for m in range(i*50, (i+1)*50):
for n in range(j*50, (j+1)*50):
img.putpixel((m,n),(255,255,255))
if self.board[i][j] == 2:
for m in range(i*50, (i+1)*50):
for n in range(j*50, (j+1)*50):
img.putpixel((m,n),(255,255,0))
if self.mousepos[0] == i and self.mousepos[1]==j:
for m in range(i*50+10, (i+1)*50-10):
for n in range(j*50+10, (j+1)*50-10):
img.putpixel((m,n),(255,0,0))
def drawsolution(self, img, states):
for i in range(0, 10):
for j in range(0, 10):
if self.board[i][j] == 1:
for m in range(i*50, (i+1)*50):
for n in range(j*50, (j+1)*50):
img.putpixel((m,n),(255,255,255))
if self.board[i][j] == 2:
for m in range(i*50, (i+1)*50):
for n in range(j*50, (j+1)*50):
img.putpixel((m,n),(255,255,0))
for mousepos in states:
for m in range(mousepos[0]*50+10, (mousepos[0]+1)*50-10):
for n in range(mousepos[1]*50+10, (mousepos[1]+1)*50-10):
img.putpixel((m,n),(255,0,0))

class mouse():
b = board()
states = []
def move(self, img):
mousepos = self.b.mousepos
okmove = False
while(okmove == False):
tx = random.randint(-1,1)
ty = random.randint(-1,1)
if self.b.board[mousepos[0]+tx][mousepos[1]+ty] != 0:
if self.b.board[mousepos[0]+tx][mousepos[1]+ty] == 2:
print "Found cheese"
print self.states
self.b.drawsolution(img, self.states)
return True
mousepos = [mousepos[0]+tx, mousepos[1]+ty]
self.b.mousepos = mousepos
okmove = True
self.checkstate(mousepos)
return False
def checkstate(self, mousepos):
print mousepos
self.states.append(mousepos)

for i in range(0, len(self.states)-1):
if self.states[i][0] == mousepos[0]-1 or self.states[i][0] == mousepos[0]+1:
if self.states[i][1] == mousepos[1]-1 or self.states[i][1] == mousepos[1]+1:
print "shortcut"
states2=[]
for j in range(0, i+1):
states2.append(self.states[j])
self.states = states2
self.states.append(mousepos)
break

def main():

img = Image.new("RGB", [500,500])
m = mouse()
while(m.move(img) == False):
pass

img.save("mouseboard.png")
main()