@if-using not(MAZE-MAC) @use (MAZE-MAC) @use (SHOW-PATH) ; the current path is marked with o (SLOWER) @if-using (SHOW-PATH) ;@use (HIDE_SEARCH) ; don't display the search, only the result @fi {{{ description of the problem and its solution {{{ the algorithm ; These macros 'solve' any maze produced by the a-maze-ing maze.c program. ; ; First, a bit of maze theory. ; If you were put into a maze, a guaranteed method of finding your way ; out of the maze is to put your left hand onto a wall and just keep walking, ; never taking your hand off the wall. This technique is only guaranteed to ; work if the maze does not have any 'islands', or if the 'exit' is on the ; same island as your starting point. These conditions hold for the mazes ; under consideration. ; ; Assuming that the maze is made up of horizontal and vertical walls spaced ; one step apart and that you can move either north, south, east or west, ; then you can automate this procedure by carrying out the following steps. ; ; 1. Put yourself somewhere in the maze near a wall. ; 2. Check if you have a wall on your left. If so, go to step 4. ; 3. There is no wall on your left, so turn on the spot to your left and step ; forward by one step and repeat step 2. ; 4. Check what is directly in front of you. If it is a wall, turn on the ; spot to your right by 90 degrees and repeat step 4. ; 5. There is no wall in front of you, so step forward one step and ; go to step 2. }}} {{{ the used maze-format ; By examining a maze produced by the maze.c program you will see that ; each square of the maze is one character high and two characters wide. ; To go north or south, you move by a one character step, but to move east or ; west you move by a two character step. Also note that in any position ; there are four places where walls could be put - to the north, to the south, ; to the east and to the west. ; A wall exists to the north of you if the character to the north of ; you is a _ (otherwise it is a space). ; A wall exists to the east of you if the character to the east of you ; is a | (otherwise it is a .). ; A wall exists to the west of you if the character to the west of you ; is a | (otherwise it is a .). ; A wall exists to the south of you if the character where you are ; is a _ (otherwise it is a space). }}} {{{ implementation ; i implemented it with a couple of macros ; maze-step - do one of the above mentioned steps of ; the algorithm ; set-destination - ; check the current cursor-position to be a correct ; destination-point. (Its a little bit simple, if you ; are not in the maze, it will not work correct). ; get-new-maze - ; append at the end of ypur text a new maze. ; the command 'maze' must be available. ; ; all other macros are help-functions ; ; used variables: ; maze-dir: direction of movement ; 0 - up ; 1 - left ; 2 - down ; 3 - right ; maze-state: state of the machine like above ; maze-front: is set by front-wall, if there is a wall }}} {{{ how to do it ; 0. Put the command maze in your path. This is the same a for vi and the ; used maze-format is the same too! ; 1. put the following macros in your OCL-file and make a new .origamirc . ; 2. Choose keybindings for the macros maze-step, get-new-maze, set-destination ; 3. get a maze with get-new-maze ; 4. go into the maze and set the destination with set-destination ; 5. do maze-stepo and it runs!!! }}} }}} {{{ vars ( defvar ( maze-dir ; direction to go maze-front ; what is in front of me maze-x-pos ; current cursor-position maze-y-pos maze-begin-line ; first state in the maze maze-state ; code the current state of the automata maze-new-x-pos maze-new-y-pos go-line-arg- x case-0 case-1 case-2 case-3 case-4 case-5 ) ) }}} {{{ help-functions {{{ turn-left (deffun turn-left ( if counter-0 maze-dir ( set-counter maze-dir 3 ) else ( set-counter maze-dir +(maze-dir -1) )fi ) ) }}} {{{ test-case (deffun test-case ( set-counter case-1 +(case-0 -1) set-counter case-2 +(case-0 -2) set-counter case-3 +(case-0 -3) set-counter case-4 +(case-0 -4) set-counter case-5 +(case-0 -5) )) }}} {{{ front-wall (deffun front-wall ( set-counter maze-front 0 set-counter case-0 maze-dir test-case case {{{ dir up (counter-0 case-0 ( previous-line if or(test-char "_, test-char "O) (set-counter maze-front 1) fi next-line )) }}} {{{ dir left (counter-0 case-1 ( backward-character if test-char "| (set-counter maze-front 1) fi forward-character )) }}} {{{ dir down (counter-0 case-2 ( if or(test-char "_, test-char "O) (set-counter maze-front 1) fi )) }}} {{{ dir right (counter-0 case-3 ( forward-character if test-char "| (set-counter maze-front 1) fi backward-character )) }}} default (message-exit "incorrect_dir_in_front) esac )) }}} {{{ go {{{ go-line- ( deffun go-line- ( local ( go-line-arg- ) ( while pre ( set-counter x -(go-line-arg- store-line) ) not(counter-0 x) {{{ one step to correct line ( if counter>0 x {{{ down ( if test-bottom ( @if-using (SCR-OFF) screen-on redraw-display @fi return-from-macro ) fi next-line ) }}} else {{{ up ( if test-top ( return-from-macro ) fi previous-line {{{ on fold?, maybe down again if or(test-fold-line,test-filed) ( set-counter x -(go-line-arg- store-line) if counter-0 x ( return-from-macro ) fi {{{ maybe skip to end of this fold if counter>0 x ( if test-filed ( return-from-macro ) fi open-fold mtool-bot ) fi }}} ) fi }}} ) }}} fi ) }}} ) ) ) }}} (deffun go ( set-counter maze-x-pos store-pos set-counter maze-y-pos store-line case @if-using (SHOW-PATH) (test-char " ("o )) (test-char "_ ("O )) @fi default (forward-character) esac backward-character set-counter case-0 maze-dir test-case case (counter-0 case-0 (previous-line)) (counter-0 case-1 (backward-character backward-character)) (counter-0 case-2 (next-line)) (counter-0 case-3 (forward-character forward-character)) default (message-exit "incorrect_dir_in_go) esac @if-using (SHOW-PATH) if or(test-char "o,test-char "O) ( set-counter maze-new-x-pos store-pos set-counter maze-new-y-pos store-line set-counter go-line-arg- maze-y-pos go-line- goto-counter maze-x-pos case (test-char " ("o )) (test-char "_ ("O )) (test-char "o (" )) (test-char "O ("_ )) default (message-exit "invalid_maze ) esac set-counter go-line-arg- maze-new-y-pos go-line- goto-counter maze-new-x-pos ) fi @fi )) }}} }}} {{{ get new maze (deffun get-new-maze ( beginning-of-fold beginning-of-line set-counter maze-begin-line +(store-line 1) next-line pipe-from-command "maze newline-and-indent message-exit "new_maze_read )) }}} {{{ set-destination (deffun set-destination ( if or(test-char " ,test-char "_) (delete-character "X ) else (message-exit "no_correct_position) fi )) }}} {{{ maze-step (deffun maze-step ( @if-using (HIDE_SEARCH) screen-off @fi add-mode-overwrite set-counter maze-state 1 set-counter maze-dir 0 if counter-0 maze-begin-line ( set-counter maze-begin-line store-line ) fi goto-line-counter maze-begin-line search-forward "X newline-and-indent if not(test-char "X) (message-exit "no_destination-point) fi goto-line-counter maze-begin-line search-forward "| newline-and-indent forward-character set-counter maze-state 2 while not(test-char "X) ( show-cursor 0 set-counter case-0 maze-state test-case case {{{ state 2 (counter-0 case-2 ( turn-left front-wall repeat 3(turn-left) if counter-0 maze-front ( set-counter maze-state 3 ) else ( set-counter maze-state 4 ) fi )) }}} {{{ state 3 (counter-0 case-3 ( turn-left go set-counter maze-state 2 )) }}} {{{ state 4 (counter-0 case-4 ( front-wall if counter-0 maze-front (set-counter maze-state 5) else (repeat 3 (turn-left)) fi )) }}} {{{ state 5 (counter-0 case-5 ( go set-counter maze-state 2 )) }}} default (message-exit "incorrect_maze_state) esac ) delete-mode-overwrite @if-using (HIDE_SEARCH) screen-on redraw-display @fi )) }}} @fi