Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- NB. true for rows in x which index true value in y
- validIn =: (<"1@(|~ #) { ]) *. (|~ #) -:"1 [
- filter =: 1 : '#~ u' NB. removes all elements of y where u(y[i]) is false
- manhattanDistance =: +/@:|@:- NB. x={vect}, y={vect}; z={num}dist
- manhattanDeltas=: 3 :'(,-)=i.#$y' NB. unit vectors oriented on coordinate axes
- NB. x = [[bit]] valid squares
- NB. y = [num] index
- NB. z = [[num]] neighbors
- gridNeighbors =: 1 : 0
- [: validIn&m filter (manhattanDeltas m) +"1 ]
- )
- NB. m = [[bit]] valid squares
- NB. y = Path<tuple>
- NB. z = [Path<tuple>] extended paths
- gridExtendPath =: 1 : 0
- > <@,"_ 1 m gridNeighbors@{:@>
- )
- 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 =. ,<,: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 {:)&> frontier
- frontier =. frontier /: scores
- end.
- exception_message=:'No path found.' throw.
- )
- exampleG =: '#' = ];._2]0 :0
- ....##..##
- .##.##..##
- #..#####..
- #.#...##..
- .##...###.
- .##.####.#
- ..#..##.#.
- ###.##..##
- #.#####..#
- ...####..#
- )
- exampleSolution =: 0 8 (((|:exampleG) gridExtendPath) aStar manhattanDistance) 5 0
- NB. to inspect this solution, use:
- '*' (<"1 exampleSolution)} '.#' {~ |:exampleG
- NB. or
- '*' (<@|."1 exampleSolution)} '.#' {~ exampleG
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement