simpleDeltas =: (1 0),(0 _1),(_1 0),,:(0 1)
eightdirDeltas =: (_1 1),(_1 _1),(1 _1),(1 1),simpleDeltas

indexOutOfBounds =: (0 > ]) +./@:, <: NB. x={vect}shapeOfArray, y={vect}index; z=bit

atIndex =: ({~ <@:|.)"_ 1 NB. equivalent of x[y2][...][y0] in C-style language

filter =: 1 : '((0~:u)"_1 y) # y' NB. removes all elements of y where u(y[i]) = 0

manhattanDistance =: +/@:|@:- NB. x={vect}, y={vect}; z={num}dist

shuffle =: (#?#) { ]

NB. x = [[bit]]  valid squares
NB. y = [num]    index
NB. z = [[num]]  neighbors
gridNeighbors =: 4 : 0
    neighbors =. simpleDeltas +"1 y
    neighbors =. (-.@(($x)&indexOutOfBounds)) filter neighbors NB. remove those leaving the grid
    neighbors =. x&atIndex filter neighbors NB. remove those entering a wall
)

NB. Path<T> =: [{boxed num}distance, {boxed [T]}path]

NB. m = [[bit]]        valid squares
NB. y = Path<tuple>
NB. z = [Path<tuple>]  extended paths
gridExtendPath =: 1 : 0
    newDist  =. 1 + > {. y
    path     =. > {: y
    lastPos  =. {: path
    newPoses =. m gridNeighbors lastPos
    newPaths =. path ,"_ 1 newPoses
    (newDist ; <)"_1 newPaths
)

NB. x = Node                        goal
NB. u = (Path<Node>)->[Path<Node>]  extendPath
NB. v = (Node,Node)->num            heuristicDist
NB. y = Node                        start
NB. z = Path<Node>                  shortest path
aStar =: 2 : 0
:
    closed   =. (0,$y) $ 0
    frontier =. ,: 0;<,:y
    while. #frontier do.
        currentPath =. {. frontier
        frontier    =. }. frontier
        last        =. {: > {: currentPath
        if. last e. closed do. continue.           end.
        if. last -: x      do. currentPath return. end.
        closed   =. closed, last
        frontier =. frontier, (u currentPath)
        NB. SORT FRONTIER
        scores   =. (>@{. + (x v {:@:>@:{:))"_1 frontier
        frontier =. frontier /: scores
    end.
    exception_message=:'No path found.' throw.
)

exampleG =: 10 10 $ (0 0 0 0 1 1 0 0 1 1 0 1 1 0 1 1 0 0 1 1 1 0 0 1 1 1 1 1 0 0 1 0 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 1 0 0 1 1 0 1 1 1 1 0 1 0 0 1 0 0 1 1 0 1 0 1 1 1 0 1 1 0 0 1 1 1 0 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 0 1)
exampleSolution =: 0 8 ((exampleG gridExtendPath) aStar manhattanDistance) 5 0