 !   - going up costs 5 points
 !   - going down costs 1 point
 !   - going left or right costs 2 points
+
+<<
+
+TUPLE: maze < astar ;
 
 : reachable? ( pos -- ? )
     first2 [ 2 * 5 + ] [ 2 + ] bi* $[

  8  X X X X X X X X X X"
        "\n" split ] nth nth CHAR: X = not ;

: neighbours ( pos -- neighbours )
     first2
     { [ 1 + 2array ] [ 1 - 2array ] [ [ 1 + ] dip 2array ] [ [ 1 - ] dip 2array ] } 2cleave
     4array
     [ reachable? ] filter ;

: heuristic ( from to -- cost )
    v- [ abs ] [ + ] map-reduce ;

: cost ( from to -- cost )
    2dup [ first ] bi@ = [ [ second ] bi@ > 1 5 ? ] [ 2drop 2 ] if ;

: test1 ( to -- path considered )
    { 1 1 } swap [ neighbours ] [ cost ] [ heuristic ] <astar> [ find-path ] [ considered ] bi ;
>>

! Existing path from s to f

! Non-existing path from s to g -- all positions must have been considered
[ f 26 ] [ { 1 7 } test1 length ] unit-test

! Look for a path between A and C. The best path is A --> D --> C. C will be placed
! in the open set early because B will be examined first. This checks that the evaluation
! of C is correctly replaced in the open set.
