A* search algorithm: Difference between revisions
m
→{{header|11l}}: X.throw
m (→{{header|Phix}}: added syntax colouring the hard way) |
Alextretyak (talk | contribs) m (→{{header|11l}}: X.throw) |
||
| (25 intermediate revisions by 12 users not shown) | |||
Line 1:
{{draft task|Routing algorithms}}
<!-- A* is pronounced as: A star !-->
The A* search algorithm is an extension of [[Dijkstra's algorithm]] useful for finding the lowest cost path between two nodes (aka vertices) of a graph. The path may traverse any number of nodes connected by edges (aka arcs) with each edge having an associated cost. The algorithm uses a heuristic which associates an estimate of the lowest cost path from this node to the goal node, such that this estimate is never greater than the actual cost.
The algorithm should not assume that all edge costs are the same. It should be possible to start and finish on any node, including ones identified as a barrier in the task.
;Task
Consider the problem of finding a route across the diagonal of a chess board-like 8x8 grid. The rows are numbered from 0 to 7. The columns are also numbered 0 to 7. The start position is (0, 0) and the end position is (7, 7). Movement is allow by one square in any direction including diagonals, similar to a king in chess. The standard movement cost is 1. To make things slightly harder, there is a barrier that occupy certain positions of the grid. Moving into any of the barrier positions has a cost of 100.
The barrier occupies the positions (2,4), (2,5), (2,6), (3,6), (4,6), (5,6), (5,5), (5,4), (5,3), (5,2), (4,2) and (3,2).
A route with the lowest cost should be found using the A* search algorithm (there are multiple optimal solutions with the same total cost).
Line 31:
* [[Knapsack problem/0-1]]
<br><br>
=={{header|11l}}==
{{trans|Python}}
<syntaxhighlight lang="11l">F AStarSearch(start, end, barriers)
F heuristic(start, goal)
V D = 1
V D2 = 1
V dx = abs(start[0] - goal[0])
V dy = abs(start[1] - goal[1])
R D * (dx + dy) + (D2 - 2 * D) * min(dx, dy)
F get_vertex_neighbours(pos)
[(Int, Int)] n
L(dx, dy) [(1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (-1, 1), (1, -1), (-1, -1)]
V x2 = pos[0] + dx
V y2 = pos[1] + dy
I x2 < 0 | x2 > 7 | y2 < 0 | y2 > 7
L.continue
n.append((x2, y2))
R n
F move_cost(a, b)
L(barrier) @barriers
I b C barrier
R 100
R 1
[(Int, Int) = Int] G
[(Int, Int) = Int] f
G[start] = 0
f[start] = heuristic(start, end)
Set[(Int, Int)] closedVertices
V openVertices = Set([start])
[(Int, Int) = (Int, Int)] cameFrom
L openVertices.len > 0
(Int, Int)? current
V currentFscore = 0
L(pos) openVertices
I current == N | f[pos] < currentFscore
currentFscore = f[pos]
current = pos
I current == end
V path = [current]
L current C cameFrom
current = cameFrom[current]
path.append(current)
path.reverse()
R (path, f[end])
openVertices.remove(current)
closedVertices.add(current)
L(neighbour) get_vertex_neighbours(current)
I neighbour C closedVertices
L.continue
V candidateG = G[current] + move_cost(current, neighbour)
I neighbour !C openVertices
openVertices.add(neighbour)
E I candidateG >= G[neighbour]
L.continue
cameFrom[neighbour] = current
G[neighbour] = candidateG
V H = heuristic(neighbour, end)
f[neighbour] = G[neighbour] + H
X.throw RuntimeError(‘A* failed to find a solution’)
V (result, cost) = AStarSearch((0, 0), (7, 7), [[(2, 4), (2, 5), (2, 6), (3, 6), (4, 6), (5, 6), (5, 5), (5, 4), (5, 3), (5, 2), (4, 2), (3, 2)]])
print(‘route ’result)
print(‘cost ’cost)</syntaxhighlight>
{{out}}
<pre>
route [(0, 0), (1, 1), (2, 2), (3, 1), (4, 1), (5, 1), (6, 2), (6, 3), (6, 4), (6, 5), (6, 6), (7, 7)]
cost 11
</pre>
=={{header|C}}==
<syntaxhighlight lang="c">
#include <stdlib.h>
#include <stdio.h>
Line 284 ⟶ 367:
return 0;
}
</syntaxhighlight>
{{out}}
<pre>
Line 312 ⟶ 395:
</pre>
=={{header|C sharp|C#}}==
<
using System;
using System.Collections.Generic;
Line 339 ⟶ 422:
}
// Class Cell, with the cost to reach it, the values g and f, and the coordinates
// of the cell that precedes it in a possible path
public class Cell
Line 399 ⟶ 482:
if (newCell.row == finishCell.row && newCell.col == finishCell.col)
{
cells[newCell.row, newCell.col].g = cells[currentCell.row,
currentCell.col].g + cells[newCell.row, newCell.col].cost;
cells[newCell.row, newCell.col].parent.row = currentCell.row;
Line 410 ⟶ 493:
else if (!opened.Contains(newCell) && !closed.Contains(newCell))
{
cells[newCell.row, newCell.col].g = cells[currentCell.row,
currentCell.col].g + cells[newCell.row, newCell.col].cost;
cells[newCell.row, newCell.col].f =
cells[newCell.row, newCell.col].g + Heuristic(newCell);
cells[newCell.row, newCell.col].parent.row = currentCell.row;
Line 419 ⟶ 502:
}
// If the cost to reach the considered cell from the actual one is
// smaller than the previous one
else if (cells[newCell.row, newCell.col].g > cells[currentCell.row,
currentCell.col].g + cells[newCell.row, newCell.col].cost)
{
cells[newCell.row, newCell.col].g = cells[currentCell.row,
currentCell.col].g + cells[newCell.row, newCell.col].cost;
cells[newCell.row, newCell.col].f =
cells[newCell.row, newCell.col].g + Heuristic(newCell);
cells[newCell.row, newCell.col].parent.row = currentCell.row;
Line 483 ⟶ 566:
}
// It select the cell between those in the list opened that have the smaller
// value of f
public Coordinates ShorterExpectedPath()
Line 492 ⟶ 575:
for (int i = 1; i < opened.Count; i++)
{
if (cells[opened[i].row, opened[i].col].f < cells[opened[sep].row,
opened[sep].col].f)
{
Line 508 ⟶ 591:
for (int i = -1; i <= 1; i++)
for (int j = -1; j <= 1; j++)
if (c.row+i >= 0 && c.row+i < 8 && c.col+j >= 0 && c.col+j < 8 &&
(i != 0 || j != 0))
{
Line 519 ⟶ 602:
public bool IsAWall(int row, int col)
{
int[,] walls = new int[,] { { 2, 4 }, { 2, 5 }, { 2, 6 }, { 3, 6 }, { 4, 6 },
{ 5, 6 }, { 5, 5 }, { 5, 4 }, { 5, 3 }, { 5, 2 }, { 4, 2 }, { 3, 2 } };
bool found = false;
Line 563 ⟶ 646:
}
}
</syntaxhighlight>
{{out}}
<pre>
Line 580 ⟶ 663:
=={{header|C++}}==
<
#include <list>
#include <algorithm>
#include <iostream>
class point {
public:
Line 592 ⟶ 675:
int x, y;
};
class map {
public:
Line 611 ⟶ 694:
int w, h;
};
class node {
public:
Line 620 ⟶ 703:
int dist, cost;
};
class aStar {
public:
Line 629 ⟶ 712:
neighbours[6] = point( 0, 1 ); neighbours[7] = point( 1, 0 );
}
int calcDist( point& p ){
// need a better heuristic
Line 635 ⟶ 718:
return( x * x + y * y );
}
bool isValid( point& p ) {
return ( p.x >-1 && p.y > -1 && p.x < m.w && p.y < m.h );
}
bool existPoint( point& p, int cost ) {
std::list<node>::iterator i;
Line 654 ⟶ 737:
return false;
}
bool fillOpen( node& n ) {
int stepCost, nc, dist;
Line 664 ⟶ 747:
neighbour = n.pos + neighbours[x];
if( neighbour == end ) return true;
if( isValid( neighbour ) && m( neighbour.x, neighbour.y ) != 1 ) {
nc = stepCost + n.cost;
Line 671 ⟶ 754:
node m;
m.cost = nc; m.dist = dist;
m.pos = neighbour;
m.parent = n.pos;
open.push_back( m );
Line 679 ⟶ 762:
return false;
}
bool search( point& s, point& e, map& mp ) {
node n; end = e; start = s; m = mp;
n.cost = 0; n.pos = s; n.parent = 0; n.dist = calcDist( s );
open.push_back( n );
while( !open.empty() ) {
Line 693 ⟶ 776:
return false;
}
int path( std::list<point>& path ) {
path.push_front( end );
int cost = 1 + closed.back().cost;
path.push_front( closed.back().pos );
point parent = closed.back().parent;
for( std::list<node>::reverse_iterator i = closed.rbegin(); i != closed.rend(); i++ ) {
if( ( *i ).pos == parent && !( ( *i ).pos == start ) ) {
Line 709 ⟶ 792:
return cost;
}
map m; point end, start;
point neighbours[8];
Line 715 ⟶ 798:
std::list<node> closed;
};
int main( int argc, char* argv[] ) {
map m;
point s, e( 7, 7 );
aStar as;
if( as.search( s, e, m ) ) {
std::list<point> path;
Line 736 ⟶ 819:
std::cout << "\n";
}
std::cout << "\nPath cost " << c << ": ";
for( std::list<point>::iterator i = path.begin(); i != path.end(); i++ ) {
Line 745 ⟶ 828:
return 0;
}
</syntaxhighlight>
{{out}}
<pre>
Line 764 ⟶ 847:
=={{header|Common Lisp}}==
<
(eval-when (:load-toplevel :compile-toplevel :execute)
(ql:quickload '("pileup" "iterate")))
Line 878 ⟶ 961:
0)))
;; Check if this state was already looked at
(unless (gethash position visited
;; Insert the next node into the queue
(heap-insert
(node :pos position :path (cons position (node-path node))
:cost cost :f-value f-value)
queue)))))
;; The actual A* search
Line 898 ⟶ 981:
;; Output some information each counter or nothing if information
;; equals 0.
(when (and (not (zerop information))
(zerop (mod counter information)))
(format t "~Dth Node, heap size: ~D, current costs: ~D~%"
counter (heap-count queue)
(node-cost current-node)))
;; If the target is not reached continue
(until (equalp current-position goal))
Line 920 ⟶ 1,003:
(a* start goal heuristics #'next-positions 0)
(format t "Found the shortest path from Start (●) to Goal (◆) in ~D steps with cost: ~D~%" steps cost)
(print-path path start goal)))</
{{out}}
Line 940 ⟶ 1,023:
=={{header|D}}==
ported from c++ code
<syntaxhighlight lang="d">
import std.stdio;
Line 946 ⟶ 1,029:
import std.range;
import std.array;
struct Point {
int x;
Line 963 ⟶ 1,046:
];
}
struct Node {
Point pos;
Line 987 ⟶ 1,070:
return( x * x + y * y );
}
bool isValid(Point b) {
return ( b.x >-1 && b.y > -1 && b.x < m.w && b.y < m.h );
}
bool existPoint(Point b, int cost) {
auto i = closed.countUntil(b);
Line 1,005 ⟶ 1,088:
return false;
}
bool fillOpen( ref Node n ) {
int stepCost;
Line 1,011 ⟶ 1,094:
int dist;
Point neighbour;
for( int x = 0; x < 8; ++x ) {
// one can make diagonals have different cost
Line 1,017 ⟶ 1,100:
neighbour = n.pos + neighbours[x];
if( neighbour == end ) return true;
if( isValid( neighbour ) && m.m[neighbour.y][neighbour.x] != 1 ) {
nc = stepCost + n.cost;
Line 1,024 ⟶ 1,107:
Node m;
m.cost = nc; m.dist = dist;
m.pos = neighbour;
m.parent = n.pos;
open ~= m;
Line 1,032 ⟶ 1,115:
return false;
}
bool search( ref Point s, ref Point e, ref Map mp ) {
Node n; end = e; start = s; m = mp;
n.cost = 0;
n.pos = s;
n.parent = Point();
n.dist = calcDist( s );
open ~= n ;
while( !open.empty() ) {
Line 1,049 ⟶ 1,132:
return false;
}
int path( ref Point[] path ) {
path = end ~ path;
int cost = 1 + closed.back().cost;
path = closed.back().pos ~ path;
Point parent = closed.back().parent;
foreach(ref i ; closed.retro) {
if( i.pos == parent && !( i.pos == start ) ) {
Line 1,066 ⟶ 1,149:
}
};
int main(string[] argv) {
Map m;
Line 1,072 ⟶ 1,155:
Point e = Point( 7, 7 );
AStar as;
if( as.search( s, e, m ) ) {
Point[] path;
Line 1,088 ⟶ 1,171:
writeln();
}
write("\nPath cost ", c, ": ");
foreach( i; path ) {
Line 1,097 ⟶ 1,180:
return 0;
}
</syntaxhighlight>
{{out}}
<pre>
Line 1,115 ⟶ 1,198:
=={{Header|FreeBASIC}}==
<
'###############################
'### A* search algorithm ###
Line 1,334 ⟶ 1,417:
aCell.row = nCell.row
loop
'Drawing the path
for i = 0 to 7
Line 1,348 ⟶ 1,431:
print
next
'Writing the cells sequence and the path length
print
Line 1,363 ⟶ 1,446:
end if
end
</syntaxhighlight>
{{out}}
<pre>
Line 1,382 ⟶ 1,465:
=={{header|Go}}==
<
// on the graph representation.
package astar
Line 1,494 ⟶ 1,577:
h[last].fx = -1
return h[last]
}</
<
import (
Line 1,550 ⟶ 1,633:
fmt.Println("Route:", route)
fmt.Println("Cost:", cost)
}</
{{out}}
<pre>
Line 1,556 ⟶ 1,639:
Cost: 11
</pre>
=={{header|Haskell}}==
The simplest standalone FIFO priority queue is implemented after Sleator and Tarjan in Louis Wasserman's ''"Playing with Priority Queues"''[https://themonadreader.files.wordpress.com/2010/05/issue16.pdf].
<syntaxhighlight lang="haskell">{-# language DeriveFoldable #-}
module PQueue where
data PQueue a = EmptyQueue
| Node (Int, a) (PQueue a) (PQueue a)
deriving (Show, Foldable)
instance Ord a => Semigroup (PQueue a) where
h1@(Node (w1, x1) l1 r1) <> h2@(Node (w2, x2) l2 r2)
| w1 < w2 = Node (w1, x1) (h2 <> r1) l1
| otherwise = Node (w2, x2) (h1 <> r2) l2
EmptyQueue <> h = h
h <> EmptyQueue = h
entry :: Ord a => a -> Int -> PQueue a
entry x w = Node (w, x) EmptyQueue EmptyQueue
enque :: Ord a => PQueue a -> a -> Int -> PQueue a
enque q x w = if x `notElem` q
then entry x w <> q
else q
deque :: Ord a => PQueue a -> Maybe (a, PQueue a)
deque q = case q of
EmptyQueue -> Nothing
Node (_, x) l r -> Just (x, l <> r)</syntaxhighlight>
The simple graph combinators:
<syntaxhighlight lang="haskell">import PQueue
import Data.Map (Map(..))
import qualified Data.Map as Map
import Data.List (unfoldr)
newtype Graph n = Graph { links :: n -> Map n Int }
grid :: Int -> Int -> Graph (Int,Int)
grid a b = Graph $ \(x,y) ->
let links = [((x+dx,y+dy), dx*dx+dy*dy)
| dx <- [-1..1], dy <- [-1..1]
, not (dx == 0 && dy == 0)
, 0 <= x+dx && x+dx <= a
, 0 <= y+dy && y+dy <= b]
in Map.fromList links
withHole :: (Foldable t, Ord n) => Graph n -> t n -> Graph n
withHole (Graph g) ns = Graph $ \x ->
if x `elem` ns
then Map.empty
else foldr Map.delete (g x) ns </syntaxhighlight>
Finally, the search algorithm, as given in Wikipedia.
<syntaxhighlight lang="haskell">get :: (Ord k, Bounded a) => Map k a -> k -> a
get m x = Map.findWithDefault maxBound x m
set :: Ord k => Map k a -> k -> a -> Map k a
set m k x = Map.insert k x m
data AstarData n = SetData { cameFrom :: Map n n
, gScore :: Map n Int
, openSet :: PQueue n }
findPath
:: Ord n => Graph n -> (n -> n -> Int) -> n -> n -> [n]
findPath (Graph links) metric start goal = loop a0
where
a0 = SetData
{ cameFrom = mempty
, gScore = Map.singleton start 0
, openSet = entry start (h start) }
h = metric goal
dist = get . links
loop a = case deque (openSet a) of
Nothing -> []
Just (current, q') -> if current == goal
then getPath (cameFrom a)
else loop a'
where
a' = Map.foldlWithKey go a { openSet = q' } neighbours
neighbours = links current
go a n _ =
let g = get $ gScore a
trial_Score = g current + dist current n
in if trial_Score >= g n
then a
else SetData
( set (cameFrom a) n current )
( set (gScore a) n trial_Score )
( openSet a `enque` n $ trial_Score + h n )
getPath m = reverse $ goal : unfoldr go goal
where go n = (\x -> (x,x)) <$> Map.lookup n m</syntaxhighlight>
Example
<syntaxhighlight lang="haskell">distL1 (x,y) (a,b) = max (abs $ x-a) (abs $ y-b)
main = let
g = grid 9 9 `withHole` wall
wall = [ (2,4),(2,5),(2,6),(3,6)
, (4,6),(5,6),(5,5),(5,4)
, (5,3),(5,2),(3,2),(4,2) ]
path = shortestPath g distL1 (1,1) (7,7)
picture = [ [ case (i,j) of
p | p `elem` path -> '*'
| p `elem` wall -> '#'
| otherwise -> ' '
| i <- [0..8] ]
| j <- [0..8] ]
in do
print path
mapM_ putStrLn picture
putStrLn $ "Path score: " <> show (length path) </syntaxhighlight>
<pre>λ> main
[(1,1),(2,1),(3,1),(4,1),(5,1),(6,2),(6,3),(6,4),(6,5),(6,6),(7,7)]
*****
###*
#*
# #*
# #*
####*
*
Path score: 11</pre>
=={{header|J}}==
Implementation:
<syntaxhighlight lang="j">
barrier=: 2 4,2 5,2 6,3 6,4 6,5 6,5 5,5 4,5 3,5 2,4 2,:3 2
price=: _,.~_,~100 barrier} 8 8$1
dirs=: 0 0-.~>,{,~<i:1
start=: 0 0
end=: 7 7
next=: {{
frontier=. ~.locs=. ,/dests=. ($price)|"1 ({:"2 y)+"1/dirs
paths=. ,/y,"2 1/"2 dests
costs=. ,x+(<"1 dests){price
deals=. (1+locs <.//. costs) <. (<"1 frontier) { values
keep=. costs < (frontier i. locs) { deals
(keep#costs);keep#paths
}}
Asrch=: {{
values=: ($price)$_
best=: ($price)$a:
paths=: ,:,:start
costs=: ,0
while. #paths do.
dests=. <"1 {:"2 paths
values=: costs dests} values
best=: (<"2 paths) dests} best
'costs paths'=.costs next paths
end.
((<end){values) ; (<end){best
}}</syntaxhighlight>
Task example:
<syntaxhighlight lang="j"> Asrch''
┌──┬───┐
│11│0 0│
│ │1 1│
│ │2 2│
│ │3 1│
│ │4 1│
│ │5 1│
│ │6 2│
│ │7 3│
│ │7 4│
│ │7 5│
│ │7 6│
│ │7 7│
└──┴───┘
'A B'=: Asrch''
'x' (<"1 B)} '. #'{~(i.~~.@,) price
x.......
.x......
..x.###.
.x#...#.
.x#...#.
.x#####.
..x.....
...xxxxx
</syntaxhighlight>
Note that this is based on a literal reading of the task, where we are paying a cost to move into a new square -- here, we are not paying for the cost of the start square, because we never move into that square. If we paid to move into the start square, the final cost would have to include that price.
=={{header|Java}}==
<
package astar;
Line 1,564 ⟶ 1,845:
import java.util.ArrayList;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;
class AStar {
Line 1,575 ⟶ 1,861:
private int xend, yend;
private final boolean diag;
// Node class for convienience
static class Node implements Comparable {
Line 1,636 ⟶ 1,922:
}
/*
**This
**
**
*/
public void expandAStar(int[][] maze, int xstart, int ystart, boolean diag){
Queue<Mazecoord> exploreNodes = new LinkedList<Mazecoord>();
if(maze[stateNode.getR()][stateNode.getC()] == 2){
if(isNodeILegal(stateNode, stateNode.expandDirection())){
exploreNodes.add(stateNode.expandDirection());
}
}
/*
** Calculate distance for goal three methods shown.
**
**
*/
public void AStarSearch(){
this.start.setCostToGoal(this.start.calculateCost(this.goal));
this.start.setPathCost(0);
this.start.setAStartCost(this.start.getPathCost() + this.start.getCostToGoal());
Mazecoord intialNode = this.start;
Mazecoord stateNode = intialNode;
frontier.add(intialNode);
//explored<Queue> is empty
while (true){
if(frontier.isEmpty()){
System.out.println("fail");
System.out.println(explored.size());
System.exit(-1);
}
}
/*
** Second method.
**
**
*/
/**
* calculate the cost from current node to goal.
* @param goal : goal
* @return : cost from current node to goal. use Manhattan distance.
*/
public int calculateCost(Mazecoord goal){
int rState = this.getR();
int rGoal = goal.getR();
int diffR = rState - rGoal;
int diffC = this.getC() - goal.getC();
if(diffR * diffC > 0) { // same sign
return Math.abs(diffR) + Math.abs(diffC);
} else {
return Math.max(Math.abs(diffR), Math.abs(diffC));
}
}
public Coord getFather(){
return this.father;
}
public void setFather(Mazecoord node){
this.father = node;
}
public int getAStartCost() {
return AStartCost;
}
public void setAStartCost(int aStartCost) {
AStartCost = aStartCost;
}
public int getCostToGoal() {
return costToGoal;
}
public void setCostToGoal(int costToGoal) {
this.costToGoal = costToGoal;
}
/*
** Third method.
**
**
*/
private double distance(int dx, int dy) {
Line 1,684 ⟶ 2,039:
Collections.sort(this.open);
}
public static void main(String[] args) {
// -1 = blocked
Line 1,725 ⟶ 2,080:
}
}
</syntaxhighlight>
{{out}}
<pre>
[0, 0] [1, 0] [2, 0] [3, 0] [4, 0] [5, 1] [6, 2] [7, 3] [6, 4] [6, 5] [6, 6] [7, 7]
Total cost: 11,00
*****___
Line 1,742 ⟶ 2,097:
=={{header|JavaScript}}==
Animated.<br />To see how it works on a random map go [http://paulo-jorente.de/tests/astar/ here]
<
var ctx, map, opn = [], clsd = [], start = {x:1, y:1, f:0, g:0},
goal = {x:8, y:8, f:0, g:0}, mw = 10, mh = 10, neighbours, path;
Line 1,838 ⟶ 2,193:
}
}
map[5][3] = map[6][3] = map[7][3] = map[3][4] = map[7][4] = map[3][5] =
map[7][5] = map[3][6] = map[4][6] = map[5][6] = map[6][6] = map[7][6] = 1;
//map[start.x][start.y] = 2; map[goal.x][goal.y] = 3;
Line 1,849 ⟶ 2,204:
document.body.appendChild( canvas );
neighbours = [
{x:1, y:0, c:1}, {x:-1, y:0, c:1}, {x:0, y:1, c:1}, {x:0, y:-1, c:1},
{x:1, y:1, c:1.4}, {x:1, y:-1, c:1.4}, {x:-1, y:1, c:1.4}, {x:-1, y:-1, c:1.4}
];
path = []; createMap(); opn.push( start ); solveMap();
}
</syntaxhighlight>
{{out}}<pre>
Path: 11
[(1, 1) (2, 2) (2, 3) (2, 4) (2, 5) (2, 6) (3, 7) (4, 8) (5, 8) (6, 8) (7, 8) (8, 8) ]
</pre>
Implementation using recursive strategy
<syntaxhighlight lang="javascript">
function manhattan(x1, y1, x2, y2) {
return Math.abs(x1 - x2) + Math.abs(y1 - y2);
}
function aStar (board, startx, starty, goalx, goaly,
open = Array(8 * 8).fill(null),
closed = Array(8 * 8).fill(null),
current = {
"coord": [startx, starty],
"distance": 0,
"heuristic": manhattan(startx, starty, goalx, goaly),
"previous": null
}) {
const [x, y] = [...current.coord];
if (x === goalx && y === goaly) {
closed[x + y * 8] = current;
return (lambda = (closed, x, y, startx, starty) => {
if (x === startx && y === starty) {
return [[x, y]];
}
const [px, py] = closed.filter(e => e !== null)
.find(({coord: [nx, ny]}) => {
return nx === x && ny === y
}).previous;
return lambda(closed, px, py, startx, starty).concat([[x,y]]);
})(closed, x, y, startx, starty);
}
let newOpen = open.slice();
[
[x + 1, y + 1], [x - 1, y - 1], [x + 1, y], [x, y + 1],
[x - 1, y + 1], [x + 1, y - 1], [x - 1, y], [x, y - 1]
].filter(([x,y]) => x >= 0 && x < 8 &&
y >= 0 && y < 8 &&
closed[x + y * 8] === null
).forEach(([x,y]) => {
newOpen[x + y * 8] = {
"coord": [x,y],
"distance": current.distance + (board[x + y * 8] === 1 ? 100 : 1),
"heuristic": manhattan(x, y, goalx, goaly),
"previous": [...current.coord]
};
});
let newClosed = closed.slice();
newClosed[x + y * 8] = current;
const [newCurrent,] = newOpen.filter(e => e !== null)
.sort((a, b) => {
return (a.distance + a.heuristic) - (b.distance + b.heuristic);
});
const [newx, newy] = [...newCurrent.coord];
newOpen[newx + newy * 8] = null;
return aStar(board, startx, starty, goalx, goaly,
newOpen, newClosed, newCurrent);
}
const board = [
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,
0,0,0,0,1,1,1,0,
0,0,1,0,0,0,1,0,
0,0,1,0,0,0,1,0,
0,0,1,1,1,1,1,0,
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0
];
console.log(aStar(board, 0,0, 7,7));
</syntaxhighlight>
{{output}} <pre>
[ [ 0, 0 ], [ 1, 1 ], [ 2, 2 ], [ 3, 1 ], [ 4, 1 ], [ 5, 1 ], [ 6, 1 ], [ 7, 2 ], [ 7, 3 ], [ 7, 4 ], [ 7, 5 ], [ 7, 6 ], [ 7, 7 ] ]
</pre>
=={{header|Julia}}==
The graphic in this solution is displayed in the more standard orientation of origin at bottom left and goal at top right.
<
const chessboardsize = 8
Line 1,900 ⟶ 2,332:
println()
end
end</
Solution has cost 11:
Tuple{Int64,Int64}[(0, 0), (1, 1), (2, 2), (3, 1), (4, 1), (5, 1), (6, 2), (7, 3), (7, 4), (6, 5), (6, 6), (7, 7)]
Line 1,914 ⟶ 2,346:
=={{header|Kotlin}}==
<
import java.lang.Math.abs
Line 2,025 ⟶ 2,457:
println("Cost: $cost Path: $path")
}
</syntaxhighlight>
{{out}}<pre>
Cost: 11
Line 2,032 ⟶ 2,464:
=={{header|Lua}}==
<
-- QUEUE -----------------------------------------------------------------------
Queue = {}
Line 2,051 ⟶ 2,483:
if self[i]:F() < self[1]:F() then
s = self[1]
self[1] = self[i]
self[i] = s
end
Line 2,109 ⟶ 2,541:
-- A-STAR ----------------------------------------------------------------------
local nbours = {
{ 1, 0, 1 }, { 0, 1, 1 }, { 1, 1, 1.4 }, { 1, -1, 1.4 },
{ -1, -1, 1.4 }, { -1, 1, 1.4 }, { 0, -1, 1 }, { -1, 0, 1 }
}
local map = {
1,1,1,1,1,1,1,1,1,1,
1,0,0,0,0,0,0,0,0,1,
1,0,0,0,0,0,0,0,0,1,
Line 2,122 ⟶ 2,554:
1,0,0,0,0,0,0,0,0,1,
1,0,0,0,0,0,0,0,0,1,
1,1,1,1,1,1,1,1,1,1
}
local open, closed, start, goal,
mapW, mapH = Queue:new(), List:new(), Point:new(), Point:new(), 10, 10
start:set( 2, 2 ); goal:set( 9, 9 )
Line 2,137 ⟶ 2,569:
end
function isValid( pos )
return pos.x > 0 and pos.x <= mapW
and pos.y > 0 and pos.y <= mapH
and map[pos.x + mapW * pos.y - mapW] == 0
end
Line 2,153 ⟶ 2,585:
nNode.cost = node.cost + nbours[n][3]
nNode.dist = calcDist( nNode.pos )
if isValid( nNode.pos ) then
if nNode.pos:equals( goal ) then
closed:push( nNode )
return true
end
nx = hasNode( closed, nNode.pos )
Line 2,163 ⟶ 2,595:
nx = hasNode( open, nNode.pos )
if( nx < 0 ) or ( nx > 0 and nNode:F() < open[nx]:F() ) then
if( nx > 0 ) then
table.remove( open, nx )
end
Line 2,206 ⟶ 2,638:
if node == nil then break end
closed:push( node )
if addToOpen( node ) == true then
makePath()
return true
end
end
Line 2,232 ⟶ 2,664:
print( "can not find a path!" )
end
</syntaxhighlight>
{{out}}
<pre>
Line 2,251 ⟶ 2,683:
=={{header|Nim}}==
Implementation of the Wikipedia pseudocode.
<syntaxhighlight lang="nim">
# A* search algorithm.
Line 2,382 ⟶ 2,814:
else:
printSolution(path, cost)
</syntaxhighlight>
{{out}}
Line 2,407 ⟶ 2,839:
A very close/straightforward implementation of the Wikipedia pseudocode.
<
module IntPairs =
struct
Line 2,536 ⟶ 2,968:
print_newline ()
) _board;
print_newline ()</
{{out}}
Line 2,565 ⟶ 2,997:
=={{header|Ol}}==
<
; level: list of lists, any except 1 means the cell is empty
; from: start cell in (x . y) mean
Line 2,631 ⟶ 3,063:
(cons (+ x 1) y)))))
(step1 (- n 1) c-list-set o-list-set))))))))
</syntaxhighlight>
{{out}}
<
(define level '(
(1 1 1 1 1 1 1 1 1 1)
Line 2,689 ⟶ 3,121:
(for-each print solved)
</syntaxhighlight>
<pre>
Line 2,733 ⟶ 3,165:
(1 1 1 1 1 1 1 1 1 1)
</pre>
=={{header|Perl}}==
<syntaxhighlight lang="perl">#!/usr/bin/perl
use strict; # https://rosettacode.org/wiki/A*_search_algorithm
use warnings;
use List::AllUtils qw( nsort_by );
sub distance
{
my ($r1, $c1, $r2, $c2) = split /[, ]/, "@_";
sqrt( ($r1-$r2)**2 + ($c1-$c2)**2 );
}
my $start = '0,0';
my $finish = '7,7';
my %barrier = map {$_, 100}
split ' ', '2,4 2,5 2,6 3,6 4,6 5,6 5,5 5,4 5,3 5,2 4,2 3,2';
my %values = ( $start, 0 );
my @new = [ $start, 0 ];
my %from;
my $mid;
while( ! exists $values{$finish} and @new )
{
my $pick = (shift @new)->[0];
for my $n ( nsort_by { distance($_, $finish) } # heuristic
grep !/-|8/ && ! exists $values{$_},
glob $pick =~ s/\d+/{@{[$&-1]},$&,@{[$&+1]}}/gr
)
{
$from{$n} = $pick;
$values{$n} = $values{$pick} + ( $barrier{$n} // 1 );
my $new = [ $n, my $dist = $values{$n} ];
my $low = 0; # binary insertion into @new (the priority queue)
my $high = @new;
$new[$mid = $low + $high >> 1][1] <= $dist
? ($low = $mid + 1) : ($high = $mid) while $low < $high;
splice @new, $low, 0, $new; # insert in order
}
}
my $grid = "s.......\n" . ('.' x 8 . "\n") x 7;
substr $grid, /,/ * $` * 9 + $', 1, 'b' for keys %barrier;
my @path = my $pos = $finish; # the walkback to get path
while( $pos ne $start )
{
substr $grid, $pos =~ /,/ ? $` * 9 + $' : die, 1, 'x';
unshift @path, $pos = $from{$pos};
}
print "$grid\nvalue $values{$finish} path @path\n";</syntaxhighlight>
{{out}}
<pre>
s.......
.x......
..x.bbb.
.xb...b.
.xb...b.
.xbbbbb.
..x.....
...xxxxx
value 11 path 0,0 1,1 2,2 3,1 4,1 5,1 6,2 7,3 7,4 7,5 7,6 7,7
</pre>
===Extra Credit===
<syntaxhighlight lang="perl">#!/usr/bin/perl
use strict; # https://rosettacode.org/wiki/A*_search_algorithm
use warnings; # extra credit
use List::AllUtils qw( sum );
my $start = <<END;
087
654
321
END
my $finish = <<END;
123
456
780
END
my @tiles = $finish =~ /[1-9a-z]/g;
my $width = index $start, "\n";
my $gap = qr/.{$width}/s;
my $mod = $width + 1;
my %rc = map {$_, int($_ / $mod) . ',' . ($_ % $mod)} 0 .. length($start) - 2;
my %finishrc = map { $_, [ split /,/, $rc{index $finish, $_} ] } @tiles;
my %found = ( $start, 1 );
my @new = [ $start, heuristic($start) ]; # a priority queue
my %from;
my $mid;
while( ! exists $found{$finish} and @new )
{
my $pick = (shift @new)->[0];
for my $n ( grep ! exists $found{$_},
$pick =~ s/0(\w)/${1}0/r, # up
$pick =~ s/(\w)0/0$1/r, # down
$pick =~ s/0($gap)(\w)/$2${1}0/r, # left
$pick =~ s/(\w)($gap)0/0$2$1/r, # right
)
{
$found{$n} = $from{$n} = $pick;
my $new = [ $n, my $dist = heuristic( $n ) ];
my $low = 0; # binary insertion into @new (the priority queue)
my $high = @new;
$new[$mid = $low + $high >> 1][1] <= $dist
? ($low = $mid + 1) : ($high = $mid) while $low < $high;
splice @new, $low, 0, $new; # insert in order
}
}
#use Data::Dump 'dd'; dd \%found;
my $count = keys %found;
exists $found{$finish} or die "no solution found with $count\n";
my @path = my $pos = $finish; # the walkback to get path
unshift @path, $pos = $from{$pos} while $pos ne $start;
my $steps = @path - 1;
my $states = keys %found;
#print "$_\n" for @path;
my (undef, $w) = split ' ', qx(stty size);
while( @path )
{
my @section = splice @path, 0, int( $w / ($mod + 1) );
while( $section[0] )
{
s/(.*)\n/ print "$1 "; ''/e for @section;
print "\n";
}
print "\n";
}
print "steps: $steps states: $states\n";
sub heuristic
{
my $from = shift;
sum map
{
my ($r1, $c1) = split /,/, $rc{index $from, $_};
my ($r2, $c2) = @{ $finishrc{$_} };
abs($r1 - $r2) + abs($c1 - $c2)
} @tiles;
}</syntaxhighlight>
{{out}}
<pre>
087 807 870 874 874 874 874 874 074 704 740 741 741 741 741 741 041
654 654 654 650 651 651 651 051 851 851 851 850 852 852 852 052 752
321 321 321 321 320 302 032 632 632 632 632 632 630 603 063 863 863
401 410 412 412 412 412 412 012 102 120 123 123
752 752 750 753 753 753 053 453 453 453 450 456
863 863 863 860 806 086 786 786 786 786 786 780
steps: 28 states: 53
</pre>k
=={{header|Phix}}==
rows and columns are numbered 1 to 8. start position is {1,1} and end position is {8,8}.
barriers are simply avoided, rather than costed at 100.
Note that the 23 visited nodes does not count walls, but with them this algorithm exactly matches the 35 of Racket.
<!--<
<span style="color: #004080;">sequence</span> <span style="color: #000000;">grid</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">split</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"""
x:::::::
Line 2,750 ⟶ 3,337:
::::::::
"""</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'\n'</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">permitted</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}}</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">key</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},</span> <span style="color: #000080;font-style:italic;">-- chebyshev, cost</span>
<span style="color: #000000;">moves</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}},</span>
Line 2,783 ⟶ 3,368:
<span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">nx</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ny</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">'.'</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">newkey</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #7060A8;">max</span><span style="color: #0000FF;">(</span><span style="color: #000000;">8</span><span style="color: #0000FF;">-</span><span style="color: #000000;">nx</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">-</span><span style="color: #000000;">ny</span><span style="color: #0000FF;">),</span><span style="color: #000000;">key</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},</span>
<span style="color: #000000;">newmoves</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">
<span style="color: #000000;">newmoves</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">newmoves</span><span style="color: #0000FF;">,</span><span style="color: #000000;">newpos</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">newpos</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">8</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">}</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">moves</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">newmoves</span>
Line 2,791 ⟶ 3,377:
<span style="color: #004080;">integer</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">getd_index</span><span style="color: #0000FF;">(</span><span style="color: #000000;">newkey</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">data</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{
<span style="color: #008080;">else</span>
<span style="color: #000000;">data</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">data</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">data</span><span style="color: #0000FF;">,</span><span style="color: #000000;">newmoves</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">putd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">newkey</span><span style="color: #0000FF;">,</span><span style="color: #000000;">data</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
Line 2,811 ⟶ 3,398:
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">grid</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'\n'</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<!--</
{{out}}
Line 2,833 ⟶ 3,420:
task author assumed it would, instead the main loop uses a priority queue to obtain the next
lowest cost and a simple dictionary to avoid re-examination/inifinte recursion.
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #000080;font-style:italic;">--set_rand(3) -- (for consistent output)</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">optimal</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">mtm</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- mutli-tile metrics</span>
<span style="color: #
<span style="color: #000080;font-style:italic;">-- <-tile found 0..8-></span>
<span style="color: #000000;">mcost</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">},</span> <span style="color: #000080;font-style:italic;">-- position 1</span>
Line 2,854 ⟶ 3,442:
<span style="color: #0000FF;">{</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">},</span> <span style="color: #000080;font-style:italic;">-- left</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">}}</span> <span style="color: #000080;font-style:italic;">-- right</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">get_moves</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">grid</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">bool</span> <span style="color: #000000;">mtm</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">valid</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
Line 2,862 ⟶ 3,450:
<span style="color: #000000;">lim</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">lims</span><span style="color: #0000FF;">[</span><span style="color: #000000;">dx</span><span style="color: #0000FF;">][</span><span style="color: #000000;">p0</span><span style="color: #0000FF;">],</span>
<span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">step</span><span style="color: #0000FF;"><</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">i</span><span style="color: #0000FF;"><</span><span style="color: #000000;">lim</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">else</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">></span><span style="color: #000000;">lim</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">valid</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">valid</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">step</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">udlr</span><span style="color: #0000FF;">[</span><span style="color: #000000;">dx</span><span style="color: #0000FF;">],</span><span style="color: #000000;">count</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #000000;">mtm</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">count</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">valid</span>
Line 2,874 ⟶ 3,469:
<span style="color: #004080;">integer</span> <span style="color: #000000;">p0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">grid</span><span style="color: #0000FF;">),</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">step</span><span style="color: #0000FF;">,</span><span style="color: #000000;">lim</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">move</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">i</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">p0</span><span style="color: #0000FF;">+</span><span style="color: #000000;">step</span>
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">step</span><span style="color: #0000FF;"><</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">i</span><span style="color: #0000FF;"><</span><span style="color: #000000;">lim</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">else</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">></span><span style="color: #000000;">lim</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">p0</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #000000;">p0</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span>
<span style="color: #
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">grid</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">manhattan</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">grid</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
Line 2,892 ⟶ 3,495:
<span style="color: #004080;">sequence</span> <span style="color: #000000;">problem</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">grid</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">new_grid</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">moves</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">next_moves</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">move</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">show_grid</span><span style="color: #0000FF;">()</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s\n"</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">join_by</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sq_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">grid</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'0'</span><span style="color: #0000FF;">),</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #008000;">""</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #000000;">grid</span> <span style="color: #0000FF;">=</span> <span style="color: #
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1000</span> <span style="color: #008080;">do</span>
<span style="color: #000080;font-style:italic;">-- (initially shuffle as if mtm==true, otherwise
Line 2,908 ⟶ 3,511:
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"problem (manhattan cost is %d):\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">manhattan</span><span style="color: #0000FF;">(</span><span style="color: #000000;">grid</span><span style="color: #0000FF;">))</span>
<span style="color: #000000;">show_grid</span><span style="color: #0000FF;">()</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">todo</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">pq_new</span><span style="color: #0000FF;">(),</span>
<span style="color: #000000;">seen</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">new_dict</span><span style="color: #0000FF;">()</span>
Line 2,930 ⟶ 3,532:
<span style="color: #000000;">move</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">next_moves</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">new_grid</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">make_move</span><span style="color: #0000FF;">(</span><span style="color: #000000;">grid</span><span style="color: #0000FF;">,</span><span style="color: #000000;">move</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">mc</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">manhattan</span><span style="color: #0000FF;">(</span><span style="color: #000000;">new_grid</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">mc</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">new_grid</span><span style="color: #0000FF;">!=</span><span style="color: #
<span style="color: #000000;">moves</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">moves</span><span style="color: #0000FF;">,</span><span style="color: #000000;">move</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">found</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span>
Line 2,939 ⟶ 3,541:
<span style="color: #008080;">if</span> <span style="color: #7060A8;">getd_index</span><span style="color: #0000FF;">(</span><span style="color: #000000;">new_grid</span><span style="color: #0000FF;">,</span><span style="color: #000000;">seen</span><span style="color: #0000FF;">)=</span><span style="color: #004600;">NULL</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">optimal</span> <span style="color: #008080;">then</span> <span style="color: #000000;">mc</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">l</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #7060A8;">pq_add</span><span style="color: #0000FF;">({{</span><span style="color: #000000;">new_grid</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">moves</span><span style="color: #0000FF;">),</span><span style="color: #000000;">move</span><span style="color: #0000FF;">)},</span><span style="color: #000000;">mc</span><span style="color: #0000FF;">},</span><span style="color: #000000;">todo</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">setd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">new_grid</span><span style="color: #0000FF;">,</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,</span><span style="color: #000000;">seen</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
Line 2,960 ⟶ 3,562:
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000080;font-style:italic;">-- show_grid() -- (not very educational!)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">grid</span><span style="color: #0000FF;">!=</span><span style="color: #
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"solved in %d move%s:%s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">moves</span><span style="color: #0000FF;">),</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #000000;">soln</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"count:%d, seen:%d, queue:%d\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">count</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">dict_size</span><span style="color: #0000FF;">(</span><span style="color: #000000;">seen</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">pq_size</span><span style="color: #0000FF;">(</span><span style="color: #000000;">todo</span><span style="color: #0000FF;">)})</span>
<!--</
{{out}}
Note: The solutions are non-optimal (far from it, in fact), since it searches lowest manhattan() first.<br>
Line 3,000 ⟶ 3,603:
=={{header|PowerShell}}==
<
$grid = 0..($h - 1) | ForEach-Object { , (, $fill * $w) }
return $grid
Line 3,112 ⟶ 3,715:
Write-Output "Cost: $cost"
$routeString = ($route | ForEach-Object { "($($_[0]), $($_[1]))" }) -join ', '
Write-Output "Route: $routeString"</
{{out}}
<pre>
Line 3,125 ⟶ 3,728:
Cost: 11
Route: (0, 0), (1, 1), (2, 2), (3, 1), (4, 1), (5, 1), (6, 2), (7, 3), (6, 4), (7, 5), (6, 6), (7, 7)
</pre>
=={{header|Picat}}==
<syntaxhighlight lang="picat">% Picat's tabling system uses an algorithm like Dijkstra's to find an optimal solution.
% Picat's planner supports A* search with heuristics.
% See the program for the 15-puzzle at https://rosettacode.org/wiki/15_puzzle_solver#Picat
%
main =>
Maze = new_array(8,8),
Obs = [(2,4), (2,5), (2,6), (3,6), (4,6), (5,6), (5,5), (5,4), (5,3), (5,2), (4,2), (3,2)],
foreach ((R0,C0) in Obs)
Maze[R0+1,C0+1] = 100
end,
foreach (R in 1..8, C in 1..8)
(var(Maze[R,C]) -> Maze[R,C] = 1; true)
end,
search((1,1),(8,8),Maze,Cost,Path),
writeln(cost=Cost),
println([(R0,C0) : (R1,C1) in Path, R0 = R1-1, C0 = C1-1]).
table (+,+,+,min,-)
search(G,G,_Maze,Cost,Path) => Cost = 0, Path = [G].
search(S@(R,C),G,Maze,Cost,Path) =>
neibs(R,C,Neibs),
member(S1,Neibs),
S1 = (R1,C1),
search(S1,G,Maze,Cost1,Path1),
Cost = Cost1+Maze[R1,C1],
Path = [S|Path1].
neibs(R,C,Neibs) =>
Neibs = [(R1,C1) : Dr in [-1,0,1], Dc in [-1,0,1], R1 = R+Dr, C1 = C+Dc,
R1 >= 1, R1 <= 8, C1 >= 1, C1 <= 8, (R,C) != (R1,C1)].
</syntaxhighlight>
{{out}}
<pre>
cost = 11
[(0,0),(1,0),(2,0),(3,0),(4,0),(5,1),(6,2),(6,3),(6,4),(6,5),(6,6),(7,7)]
</pre>
=={{header|Python}}==
<
import matplotlib.pyplot as plt
class AStarGraph(object):
#Define a class board like grid with two barriers
def __init__(self):
self.barriers = []
Line 3,147 ⟶ 3,788:
dy = abs(start[1] - goal[1])
return D * (dx + dy) + (D2 - 2 * D) * min(dx, dy)
def get_vertex_neighbours(self, pos):
n = []
Line 3,158 ⟶ 3,799:
n.append((x2, y2))
return n
def move_cost(self, a, b):
for barrier in self.barriers:
Line 3,164 ⟶ 3,805:
return 100 #Extremely high cost to enter barrier squares
return 1 #Normal movement cost
def AStarSearch(start, end, graph):
G = {} #Actual movement cost to each position from the start position
F = {} #Estimated movement cost of start to end going via this position
#Initialize starting values
G[start] = 0
F[start] = graph.heuristic(start, end)
closedVertices = set()
openVertices = set([start])
cameFrom = {}
while len(openVertices) > 0:
#Get the vertex in the open list with the lowest F score
Line 3,196 ⟶ 3,837:
path.reverse()
return path, F[end] #Done!
#Mark the current vertex as closed
openVertices.remove(current)
closedVertices.add(current)
#Update scores for vertices near the current position
for neighbour in graph.get_vertex_neighbours(current):
if neighbour in closedVertices:
continue #We have already processed this node exhaustively
candidateG = G[current] + graph.move_cost(current, neighbour)
if neighbour not in openVertices:
openVertices.add(neighbour) #Discovered a new vertex
elif candidateG >= G[neighbour]:
continue #This G score is worse than previously found
#Adopt this G score
cameFrom[neighbour] = current
Line 3,217 ⟶ 3,858:
H = graph.heuristic(neighbour, end)
F[neighbour] = G[neighbour] + H
raise RuntimeError("A* failed to find a solution")
if __name__=="__main__":
graph = AStarGraph()
Line 3,230 ⟶ 3,871:
plt.xlim(-1,8)
plt.ylim(-1,8)
plt.show()</
{{out}}
Line 3,239 ⟶ 3,880:
This code is lifted from: [https://jeapostrophe.github.io/2013-04-15-astar-post.html this blog post]. Read it, it's very good.
<
@(chunk
<graph-sig>
Line 3,300 ⟶ 3,941:
(define count 0)
<a-star-setup>
(begin0
(let/ec esc
<a-star-loop>
#f)
(printf "visited ~a nodes\n" count))))
Line 3,316 ⟶ 3,957:
<a-star-setup-closed>
(define node->best-path (make-hash))
(define node->best-path-cost (make-hash))
(hash-set! node->best-path initial empty)
(hash-set! node->best-path-cost initial 0))
Line 3,340 ⟶ 3,981:
(define h-x (node-cost x))
(define path-x (hash-ref node->best-path x))
(when (zero? h-x)
(esc (reverse path-x))))
Line 3,347 ⟶ 3,988:
<a-star-loop-body>
<a-star-loop-stop?>
(define g-x (hash-ref node->best-path-cost x))
(for ([x->y (in-list (node-edges x))])
Line 3,400 ⟶ 4,041:
(define-unit map@
(import) (export graph^)
(define node? map-node?)
(define edge? map-edge?)
(define edge-src map-edge-src)
(define edge-dest map-edge-dest)
<map-graph-cost>
<map-graph-edges>))
Line 3,441 ⟶ 4,082:
2htdp/image
racket/runtime-path)
<graph-sig>
<map-generation>
<map-graph-rep>
<map-graph>
<a-star>
<map-node-cost>
<map-example>
Line 3,457 ⟶ 4,098:
(cons dx dy)])
random-path))
<map-display>
<path-display-line>
<path-display>
(path-image random-M random-path))</
{{out}}
Line 3,475 ⟶ 4,116:
=={{header|Raku}}==
{{trans|Sidef}}
<syntaxhighlight lang="raku"
class AStarGraph {
Line 3,567 ⟶ 4,208:
.join.say for @grid ;
say "Path cost : ", cost, " and route : ", route;</
{{out}}<pre>██████████
█x.......█
Line 3,581 ⟶ 4,222:
=={{header|REXX}}==
<
parse arg N sCol sRow . /*obtain optional arguments from the CL*/
if N=='' | N=="," then N=8 /*No grid size specified? Use default.*/
Line 3,663 ⟶ 4,304:
say ind translate(L'│', , .) /*display a " " " " */
end /*c*/ /*a 19x19 grid can be shown 80 columns.*/
say ind translate('└'_"┘",'┴',"┼"); return /*display the very bottom of the grid. */</
{{out|output|text= when using the default input:}}
<pre>
Line 3,688 ⟶ 4,329:
=={{header|SequenceL}}==
<
import <Utilities/Set.sl>;
import <Utilities/Math.sl>;
Line 3,715 ⟶ 4,356:
newActual[i,j] := 0 foreach i within 1...width, j within 1...height;
newCameFrom[i,j] := (x : 0, y : 0) foreach i within 1...width, j within 1...height;
searchResults := search((open : [start], closed : [], estimate : newEstimate, actual : newActual, cameFrom : newCameFrom), barriers, end);
shortestPath := path(searchResults.cameFrom, start, end) ++ [end];
Line 3,774 ⟶ 4,415:
y := n.y + p.y;
in
(x : x, y : y) when x >= 1 and x <= w and y >= 1 and y <= h;
calculateCost(barriers(1), start, end) := 100 when elementOf(end, barriers) else 1;
Line 3,788 ⟶ 4,429:
value when point.x = i and point.y = j else
map[i,j] foreach i within 1 ... size(map), j within 1 ... size(map[1]);
</syntaxhighlight>
{{out|Output|text= }}
<pre>
Line 3,806 ⟶ 4,447:
=={{header|Sidef}}==
{{trans|Python}}
<
has barriers = [
Line 3,910 ⟶ 4,551:
grid.each { .join.say }
say "Path cost #{cost}: #{route}"</
{{out}}
<pre>
Line 3,929 ⟶ 4,570:
{{works with|Bourne Again SHell}}
<
#!/bin/bash
Line 4,302 ⟶ 4,943:
main "$@"
</syntaxhighlight>
{{out}}
<pre>
path: 0,0 → 1,0 → 2,0 → 3,0 → 4,0 → 5,1 → 6,2 → 7,3 → 7,4 → 7,5 → 7,6 → 7,7
01234567
0◉
1↓
2↓ ■■■
3↓ ■ ■
4↘ ■ ■
5 ↘■■■■■
6 ↘
7 →→→→✪
</pre>
=={{header|Wren}}==
{{trans|Sidef}}
<syntaxhighlight lang="wren">var Equals = Fn.new { |p1, p2| p1[0] == p2[0] && p1[1] == p2[1] }
var Contains = Fn.new { |pairs, p|
for (pair in pairs) {
if (Equals.call(p, pair)) return true
}
return false
}
var Remove = Fn.new { |pairs, p|
for (pair in pairs) {
if (Equals.call(p, pair)) {
pairs.remove(pair)
return
}
}
}
class AStarGraph {
construct new() {
_barriers = [[2,4], [2,5], [2,6], [3,6], [4,6], [5,6], [5,5], [5,4], [5,3], [5,2], [4,2], [3,2]]
}
barriers { _barriers }
heuristic(start, goal) {
var D1 = 1
var D2 = 1
var dx = (start[0] - goal[0]).abs
var dy = (start[1] - goal[1]).abs
return D1 * (dx + dy) + (D2 - 2*D1) * dx.min(dy)
}
getVertexNeighbors(pos) {
var n = []
for (d in [[1,0], [-1,0], [0,1], [0,-1], [1,1], [-1,1], [1,-1], [-1,-1]]) {
var x2 = pos[0] + d[0]
var y2 = pos[1] + d[1]
if (x2 < 0 || x2 > 7 || y2 < 0 || y2 > 7) continue
n.add([x2, y2])
}
return n
}
moveCost(b) { Contains.call(_barriers, b) ? 100 : 1 }
}
var AStarSearch = Fn.new { |start, end, graph|
var G = {start.toString: 0}
var F = {start.toString: graph.heuristic(start, end)}
var closedVertices = []
var openVertices = [start]
var cameFrom = {}
while (openVertices.count > 0) {
var current = null
var currentFscore = 1 / 0
for (pos in openVertices) {
var v
if ((v = F[pos.toString]) && v && v < currentFscore) {
currentFscore = v
current = pos
}
}
if (Equals.call(current, end)) {
var path = [current]
while (cameFrom.containsKey(current.toString)) {
current = cameFrom[current.toString]
path.add(current)
}
path = path[-1..0]
return [path, F[end.toString]]
}
Remove.call(openVertices, current)
closedVertices.add(current)
for (neighbor in graph.getVertexNeighbors(current)) {
if (Contains.call(closedVertices, neighbor)) continue
var candidateG = G[current.toString] + graph.moveCost(neighbor)
if (!Contains.call(openVertices, neighbor)) {
openVertices.add(neighbor)
} else if (candidateG >= G[neighbor.toString]) continue
cameFrom[neighbor.toString] = current
G[neighbor.toString] = candidateG
var H = graph.heuristic(neighbor, end)
F[neighbor.toString] = G[neighbor.toString] + H
}
}
Fiber.abort("A* failed to find a solution")
}
var graph = AStarGraph.new()
var rc = AStarSearch.call([0,0], [7,7], graph)
var route = rc[0]
var cost = rc[1]
var w = 10
var h = 10
var grid = List.filled(h, null)
for (i in 0...h) grid[i] = List.filled(w, ".")
for (y in 0...h) {
grid[y][0] = "█"
grid[y][-1] = "█"
}
for (x in 0...w) {
grid[0][x] = "█"
grid[-1][x] = "█"
}
for (p in graph.barriers) {
var x = p[0]
var y = p[1]
grid[x+1][y+1] = "█"
}
for (p in route) {
var x = p[0]
var y = p[1]
grid[x+1][y+1] = "x"
}
for (line in grid) System.print(line.join())
System.print("\npath cost %(cost): %(route)")</syntaxhighlight>
{{out}}
<pre>
██████████
█x.......█
█.x......█
█..x.███.█
█.x█...█.█
█.x█...█.█
█.x█████.█
█..xxxxx.█
█.......x█
██████████
path cost 11: [[0, 0], [1, 1], [2, 2], [3, 1], [4, 1], [5, 1], [6, 2], [6, 3], [6, 4], [6, 5], [6, 6], [7, 7]]
</pre>
=={{header|zkl}}==
{{trans|Python}}
<
fcn toKey(xy){ xy.concat(",") }
Line 4,330 ⟶ 5,107:
F[kstart]=graph.heuristic(start,end);
closedVertices,openVertices,cameFrom := List(),List(start),Dictionary();
while(openVertices){
# Get the vertex in the open list with the lowest F score
Line 4,338 ⟶ 5,115:
if(current==Void or F[kpos]<currentFscore)
currentFscore,current = F[kpos],pos;
# Check if we have reached the goal
if(current==end){ # Yes! Retrace our route backward
Line 4,352 ⟶ 5,129:
openVertices.remove(current);
if(not closedVertices.holds(current)) closedVertices.append(current);
# Update scores for vertices near the current position
foreach neighbor in (graph.get_vertex_neighbors(current)){
Line 4,359 ⟶ 5,136:
kneighbor:=toKey(neighbor);
candidateG:=G[toKey(current)] + graph.move_cost(current, neighbor);
if(not openVertices.holds(neighbor))
openVertices.append(neighbor); # Discovered a new vertex
else if(candidateG>=G[kneighbor])
continue; # This G score is worse than previously found
# Adopt this G score
cameFrom[kneighbor]=current;
Line 4,373 ⟶ 5,150:
} // while
throw(Exception.AssertionError("A* failed to find a solution"));
}</
<
var [const] barriers =
T( T(3,2),T(4,2),T(5,2), // T is RO List
Line 4,400 ⟶ 5,177:
1 # Normal movement cost
}
}</
<
route,cost := AStarSearch(T(0,0), T(7,7), graph);
println("Route: ", route.apply(fcn(xy){ String("(",toKey(xy),")") }).concat(","));
Line 4,410 ⟶ 5,187:
foreach x,y in (graph.barriers){ grid[x][y]="#" }
foreach x,y in (route){ grid[x][y]="+" }
grid[0][0] = "S"; grid[7][7] = "E";
foreach line in (grid){ println(line.concat()) }</
{{out}}
<pre>
Route: (0,0),(1,1),(2,2),(3,1),(4,0),(5,1),(6,2),(7,3),(7,4),(7,5),(7,6),(7,7)
Cost: 11
S
+
+ ###
+# #
+ # #
+#####
+
++++E
</pre>
| |||