'maze solver for Picaxe 18X '© D Hall & J Chidley 2008 'Hardware setup symbol Maze_reset_Button=pin2 symbol green_led=4 symbol yellow_led=5 'Memory setup symbol Map_walls=b0 'this is overlaied by the folwing 8 symbols symbol w_north=bit5 '1 if wall to north symbol w_south=bit7 '1 if wall to south symbol w_west=bit4 '1 it wall to west symbol w_east=bit6 '1 if wall to east symbol w_visited=bit2 '1 if mouse has visited this square symbol w_done=bit3 'used in maze solver symbol w_direc1=bit0 'bit 0 of solved direction symbol w_direc2=bit1 'bit 1 of solved direction symbol solvit=bit8 'run the solver symbol Map_walls2=b1 'this is overlaied by the folwing 8 symbols symbol w_north2=bit13 '1 if wall to north symbol w_south2=bit15 '1 if wall to south symbol w_west2=bit12 '1 it wall to west symbol w_east2=bit14 '1 if wall to east symbol w_visited2=bit10 '1 if mouse has visited this square symbol w_done2=bit11 'used in maze solver symbol w_direc12=bit8 'bit 0 of solved direction symbol w_direc22=bit9 'bit 1 of solved direction symbol backup_b0=239 'Temporary storage registers symbol backup_b1=127 symbol temp=b2 symbol temp2=b6 symbol done=b5 'Used in maze solver symbol sensor=b7 'sensor reading from pic28 symbol maze_pos=b10 'used by maze solver symbol list1=b11 'address of list1 entry(used in maze solver) symbol list2=b12 'address of list2 entry (used in maze solver) symbol pos=b13 'current position of mouse in maze map symbol direc=b9 'direction of mouse in maze 0=north 1=east 2=south 3=west symbol target=b4 'address of target for maze solver symbol maze_start=$F0 'Position in maze map after a reset symbol maze_center=$87 '$87 $87 is centre for 16*16 maze main: 'Setup for new run setfreq m8 'run at 8mhz if maze_reset_button=0 then gosub clear_maze 'if button pressed then reset the maze map else gosub clear_maze_bits 'Reset the maze for solving endif switch on yellow_led let target=maze_center 'first run to the center let pos=maze_start-16 'start in bottom left square (mouse starts with forward move so assume start one square forward) let direc=0 'start facing north let solvit=0 gosub solve_maze 'solve the maze switch off yellow_led 'mouse ready to go when yellow led is off the_loop: gosub check_28 if pos=target then 'if at target swap to go back to start/center if target=maze_center then let target=maze_start switch on green_led else let target=maze_center switch off green_led endif gosub solve_maze let solvit=0 endif goto the_loop END check_28: 'check if direction required for PICAXE28 Do if maze_reset_button=0 Then 'Check if button presed gosub list_maze 'if yes output maze to PC endif loop until pin1=1 'wait for picaxe28 to be ready high 7 'signal Picaxe28 we are ready for sensor reading serin 1,N4800,sensor 'get sensor reading from Picaxe28 low 7 switch on yellow_led read pos,map_walls 'get the maze map info for the position of the mouse if w_visited=0 then 'if we have not visited this square before then save the sensor readings in the map let solvit=1 endif if solvit=1 then if sensor=0 or sensor=1 or sensor=2 or sensor=4 then 'Only solve the maze if we have a direction choice gosub write_the_mazemap gosub solve_maze let solvit=0 read pos,map_walls endif endif select case sensor case 3 let b8=1 'if walls both sides and no front wall always go forward case 5 let b8=2 'If walls to front and left always go right case 6 let b8=3 'If walls to front and right always go left case 7 let b8=0 'If in dead end turn always turn round else let b8=map_walls & %00000011 'Else use the maze map to decide where to go select case direc ;convert to wall map bits depending on the direction of the mouse case 0 lookup b8,(1,2,0,3),b8 'mouse facing north case 1 lookup b8,(3,1,2,0),b8 'mouse facing east case 2 lookup b8,(0,3,1,2),b8 'mouse facing south case 3 lookup b8,(2,0,3,1),b8 'mouse facing west endselect endselect serout 7,N4800,(b8) 'Send direction for mouse to go to PICAXE28 low 7 if w_visited=0 then gosub write_the_mazemap endif on b8 gosub go_round,go_forward,go_right,go_left switch off yellow_led return go_left: 'Mouse turning left dec direc if direc=255 then let direc=3 endif gosub go_forward return go_right: 'Mouse turning right inc direc if direc=4 then let direc=0 endif gosub go_forward return go_round: 'Mouse to do a U turn let direc=direc+2 if direc>3 then let direc=direc-4 endif gosub go_forward return go_forward: 'mouse moving forward (Also move forward after a turn) select case direc case 0 let pos=pos-16 'move forward north case 1 inc pos 'move forward east case 2 let pos=pos+16 'move forward south case 3 dec pos 'move forward west endselect return write_the_mazemap: select case direc ;convert to wall map bits depending on the direction of the mouse case 0 lookup sensor,(0,16,64,80,32,48,96,112),b3 'mouse facing north case 1 lookup sensor,(0,32,128,160,64,96,192,224),b3 'mouse facing east case 2 lookup sensor,(0,64,16,80,128,192,144,208),b3 'mouse facing south case 3 lookup sensor,(0,128,32,160,16,144,48,176),b3 'mouse facing west endselect let map_walls = map_walls & %00001111 let map_walls = map_walls | b3 let w_visited = 1 'set visited bit write pos,map_walls 'store maze walls in map return solve_maze: 'Solve the maze 'save varibals poke backup_b0,map_walls poke backup_b1,map_walls2 switch on yellow_led let list1=$50 'initalize list1 address let list2=$C0 'initalize list2 address poke list1,target 'add maze center to list 1 poke $51,target 'terminate list1 read target,map_walls2 let w_done2=done write target,map_walls2 do do peek list1,maze_pos 'get next pos from list1 inc list1 read maze_pos,map_walls2 'get wall map if w_north2=0 then 'add_north let b2=maze_pos-16 read b2,map_walls if w_done<>done and w_south=0 then let w_done=done let w_direc1=0 let w_direc2=1 write b2,map_walls poke list2,b2 'add to list2 inc list2 endif endif if w_south2 = 0 then 'add_south let b2=maze_pos+16 read b2,map_walls if w_done<>done and w_north=0 then let w_done=done let w_direc1=0 let w_direc2=0 write b2,map_walls poke list2,b2 'add to list2 inc list2 endif endif if w_east2 = 0 then 'add_east let b2=maze_pos+1 read b2,map_walls if w_done<>done and w_west=0 then let w_done=done let w_direc1=1 let w_direc2=1 write b2,map_walls poke list2,b2 'add to list2 inc list2 endif endif if w_west2 = 0 then 'add_west let b2=maze_pos-1 read b2,map_walls if w_done<>done and w_east=0 then let w_done=done let w_direc1=1 let w_direc2=0 write b2,map_walls poke list2,b2 'add to list2 inc list2 endif endif loop until maze_pos = target poke list2,target 'terminate list 2 if list1<$C0 then 'Swap and reset the lists let list1=$C0 let list2=$50 else let list1=$50 let list2=$C0 endif peek list1,maze_pos 'get next pos from list1 loop until maze_pos=target if done=0 then let done=1 'invert done 1=0,0=1 else let done=0 endif read pos,map_walls if w_done = done then goto maze_unsolvable 'the maze is solved peek backup_b0,map_walls peek backup_b1,map_walls2 switch off yellow_led return clear_maze_bits: 'clear done bits in maze map toggle green_led for temp=0 to 255 read temp,map_walls if w_done<>0 then let w_done=0 write temp,map_walls endif next toggle green_led return clear_maze: for temp=$01 to $0E 'clear the top line write temp,$20 next for temp=$F2 to $FE 'clear the bottom line write temp,$80 next for b3=$10 to $E0 step $10 'clear left side write b3,$10 for temp=$01 to $0E let b0=temp+b3 'clear center maze write b0,$00 next inc b0 write b0,$40 'clear right side next write $00,$30 'clear maze corners write $0F,$60 write $F0,$D4 write $FF,$C0 write $F1,$90 let done=1 Return List_maze: ;list maze to debug window sertxd(" ",13,10) for temp=0 to 240 step 16 let b8=temp+15 for temp2=temp to b8 read temp2,map_walls let b3=temp2-16 read b3,map_walls2 if w_north=1 or w_south2=1 then sertxd("+-") else sertxd("+ ") endif next sertxd("+",13,10) let map_walls2=0 let b8=temp+15 for temp2=temp to b8 read temp2,map_walls if w_west=1 or w_east2=1 then sertxd("|") else sertxd(" ") endif let map_walls2=map_walls let b3=map_walls & %00000011 lookup b3,("^",">","v","<"),b3 sertxd(b3) next sertxd("|",13,10) next sertxd("+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+",13,10) return maze_unsolvable: switch on green_led pause 250 switch off green_led switch on yellow_led pause 250 switch off yellow_led pause 250 switch on yellow_led pause 250 switch off yellow_led switch on green_led pause 250 switch off green_led pause 250 If maze_reset_button=0 then gosub list_maze endif goto maze_unsolvable 'Blank maze data data $00, ($30, $20, $20, $20, $20, $20, $20, $20, $20, $20, $20, $20, $20, $20, $20, $60) data $10, ($10, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $40) data $20, ($10, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $40) data $30, ($10, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $40) data $40, ($10, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $40) data $50, ($10, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $40) data $60, ($10, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $40) data $70, ($10, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $40) data $80, ($10, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $40) data $90, ($10, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $40) data $A0, ($10, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $40) data $B0, ($10, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $40) data $C0, ($10, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $40) data $D0, ($10, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $40) data $E0, ($10, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $00, $40) data $F0, ($D4, $90, $80, $80, $80, $80, $80, $80, $80, $80, $80, $80, $80, $80, $80, $C0)