A* search algorithm: Difference between revisions
m
→{{header|11l}}: X.throw
m (→{{header|Phix}}: fixed some syntax colouring issues) |
Alextretyak (talk | contribs) m (→{{header|11l}}: X.throw) |
||
| (22 intermediate revisions by 9 users not shown) | |||
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 563 ⟶ 646:
}
}
</syntaxhighlight>
{{out}}
<pre>
Line 580 ⟶ 663:
=={{header|C++}}==
<
#include <list>
#include <algorithm>
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 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 1,097 ⟶ 1,180:
return 0;
}
</syntaxhighlight>
{{out}}
<pre>
Line 1,115 ⟶ 1,198:
=={{Header|FreeBASIC}}==
<
'###############################
'### A* search algorithm ###
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,560 ⟶ 1,643:
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].
<
module PQueue where
Line 1,586 ⟶ 1,669:
deque q = case q of
EmptyQueue -> Nothing
Node (_, x) l r -> Just (x, l <> r)</
The simple graph combinators:
<
import Data.Map (Map(..))
import qualified Data.Map as Map
Line 1,610 ⟶ 1,693:
if x `elem` ns
then Map.empty
else foldr Map.delete (g x) ns </
Finally, the search
<
get m x = Map.findWithDefault maxBound x m
Line 1,654 ⟶ 1,737:
getPath m = reverse $ goal : unfoldr go goal
where go n = (\x -> (x,x)) <$> Map.lookup n m</
Example
<
main = let
Line 1,675 ⟶ 1,758:
print path
mapM_ putStrLn picture
putStrLn $ "Path score: " <> show (length path) </
<pre>λ> main
[(1,1),(2,1),(3,1),(4,1),(5,1),(6,2),(6,3),(6,4),(6,5),(6,6),(7,7)]
Line 1,688 ⟶ 1,771:
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,696 ⟶ 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,768 ⟶ 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,857 ⟶ 2,080:
}
}
</syntaxhighlight>
{{out}}
<pre>
Line 1,874 ⟶ 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,986 ⟶ 2,209:
path = []; createMap(); opn.push( start ); solveMap();
}
</syntaxhighlight>
{{out}}<pre>
Path: 11
Line 1,992 ⟶ 2,215:
</pre>
Implementation using recursive strategy
<
function manhattan(x1, y1, x2, y2) {
return Math.abs(x1 - x2) + Math.abs(y1 - y2);
Line 2,065 ⟶ 2,288:
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 ] ]
Line 2,071 ⟶ 2,294:
=={{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 2,109 ⟶ 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 2,123 ⟶ 2,346:
=={{header|Kotlin}}==
<
import java.lang.Math.abs
Line 2,234 ⟶ 2,457:
println("Cost: $cost Path: $path")
}
</syntaxhighlight>
{{out}}<pre>
Cost: 11
Line 2,241 ⟶ 2,464:
=={{header|Lua}}==
<
-- QUEUE -----------------------------------------------------------------------
Queue = {}
Line 2,441 ⟶ 2,664:
print( "can not find a path!" )
end
</syntaxhighlight>
{{out}}
<pre>
Line 2,460 ⟶ 2,683:
=={{header|Nim}}==
Implementation of the Wikipedia pseudocode.
<syntaxhighlight lang="nim">
# A* search algorithm.
Line 2,591 ⟶ 2,814:
else:
printSolution(path, cost)
</syntaxhighlight>
{{out}}
Line 2,616 ⟶ 2,839:
A very close/straightforward implementation of the Wikipedia pseudocode.
<
module IntPairs =
struct
Line 2,745 ⟶ 2,968:
print_newline ()
) _board;
print_newline ()</
{{out}}
Line 2,774 ⟶ 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,840 ⟶ 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,898 ⟶ 3,121:
(for-each print solved)
</syntaxhighlight>
<pre>
Line 2,942 ⟶ 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}}==
Line 2,948 ⟶ 3,326:
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 3,020 ⟶ 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 3,043 ⟶ 3,421:
lowest cost and a simple dictionary to avoid re-examination/inifinte recursion.
<!--<
<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>
Line 3,188 ⟶ 3,566:
<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}}
Line 3,225 ⟶ 3,603:
=={{header|PowerShell}}==
<
$grid = 0..($h - 1) | ForEach-Object { , (, $fill * $w) }
return $grid
Line 3,337 ⟶ 3,715:
Write-Output "Cost: $cost"
$routeString = ($route | ForEach-Object { "($($_[0]), $($_[1]))" }) -join ', '
Write-Output "Route: $routeString"</
{{out}}
<pre>
Line 3,350 ⟶ 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
Line 3,455 ⟶ 3,871:
plt.xlim(-1,8)
plt.ylim(-1,8)
plt.show()</
{{out}}
Line 3,464 ⟶ 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,687 ⟶ 4,103:
<path-display>
(path-image random-M random-path))</
{{out}}
Line 3,700 ⟶ 4,116:
=={{header|Raku}}==
{{trans|Sidef}}
<syntaxhighlight lang="raku"
class AStarGraph {
Line 3,792 ⟶ 4,208:
.join.say for @grid ;
say "Path cost : ", cost, " and route : ", route;</
{{out}}<pre>██████████
█x.......█
Line 3,806 ⟶ 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,888 ⟶ 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,913 ⟶ 4,329:
=={{header|SequenceL}}==
<
import <Utilities/Set.sl>;
import <Utilities/Math.sl>;
Line 4,013 ⟶ 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 4,031 ⟶ 4,447:
=={{header|Sidef}}==
{{trans|Python}}
<
has barriers = [
Line 4,135 ⟶ 4,551:
grid.each { .join.say }
say "Path cost #{cost}: #{route}"</
{{out}}
<pre>
Line 4,154 ⟶ 4,570:
{{works with|Bourne Again SHell}}
<
#!/bin/bash
Line 4,527 ⟶ 4,943:
main "$@"
</syntaxhighlight>
{{out}}
<pre>
Line 4,540 ⟶ 4,956:
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,598 ⟶ 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,625 ⟶ 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,636 ⟶ 5,188:
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>
| |||