A* search algorithm: Difference between revisions
m
→{{header|11l}}: X.throw
Thundergnat (talk | contribs) m (→{{header|C sharp}}: Regularize header markup to recommended on category page) |
Alextretyak (talk | contribs) m (→{{header|11l}}: X.throw) |
||
(16 intermediate revisions by 6 users not shown) | |||
Line 35:
{{trans|Python}}
<
F heuristic(start, goal)
V D = 1
Line 103:
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)</
{{out}}
Line 116:
=={{header|C}}==
<syntaxhighlight lang="c">
#include <stdlib.h>
#include <stdio.h>
Line 367:
return 0;
}
</syntaxhighlight>
{{out}}
<pre>
Line 396:
=={{header|C sharp|C#}}==
<
using System;
using System.Collections.Generic;
Line 646:
}
}
</syntaxhighlight>
{{out}}
<pre>
Line 663:
=={{header|C++}}==
<
#include <list>
#include <algorithm>
Line 828:
return 0;
}
</syntaxhighlight>
{{out}}
<pre>
Line 847:
=={{header|Common Lisp}}==
<
(eval-when (:load-toplevel :compile-toplevel :execute)
(ql:quickload '("pileup" "iterate")))
Line 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 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 1,023:
=={{header|D}}==
ported from c++ code
<syntaxhighlight lang="d">
import std.stdio;
Line 1,180:
return 0;
}
</syntaxhighlight>
{{out}}
<pre>
Line 1,198:
=={{Header|FreeBASIC}}==
<
'###############################
'### A* search algorithm ###
Line 1,446:
end if
end
</syntaxhighlight>
{{out}}
<pre>
Line 1,465:
=={{header|Go}}==
<
// on the graph representation.
package astar
Line 1,577:
h[last].fx = -1
return h[last]
}</
<
import (
Line 1,633:
fmt.Println("Route:", route)
fmt.Println("Cost:", cost)
}</
{{out}}
<pre>
Line 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,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,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,737:
getPath m = reverse $ goal : unfoldr go goal
where go n = (\x -> (x,x)) <$> Map.lookup n m</
Example
<
main = let
Line 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,776:
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
Line 1,804:
end.
((<end){values) ; (<end){best
}}</
Task example:
<
┌──┬───┐
│11│0 0│
Line 1,834:
...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,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,917 ⟶ 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 2,006 ⟶ 2,080:
}
}
</syntaxhighlight>
{{out}}
<pre>
Line 2,023 ⟶ 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 2,135 ⟶ 2,209:
path = []; createMap(); opn.push( start ); solveMap();
}
</syntaxhighlight>
{{out}}<pre>
Path: 11
Line 2,141 ⟶ 2,215:
</pre>
Implementation using recursive strategy
<
function manhattan(x1, y1, x2, y2) {
return Math.abs(x1 - x2) + Math.abs(y1 - y2);
Line 2,214 ⟶ 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,220 ⟶ 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,258 ⟶ 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,272 ⟶ 2,346:
=={{header|Kotlin}}==
<
import java.lang.Math.abs
Line 2,383 ⟶ 2,457:
println("Cost: $cost Path: $path")
}
</syntaxhighlight>
{{out}}<pre>
Cost: 11
Line 2,390 ⟶ 2,464:
=={{header|Lua}}==
<
-- QUEUE -----------------------------------------------------------------------
Queue = {}
Line 2,590 ⟶ 2,664:
print( "can not find a path!" )
end
</syntaxhighlight>
{{out}}
<pre>
Line 2,609 ⟶ 2,683:
=={{header|Nim}}==
Implementation of the Wikipedia pseudocode.
<syntaxhighlight lang="nim">
# A* search algorithm.
Line 2,740 ⟶ 2,814:
else:
printSolution(path, cost)
</syntaxhighlight>
{{out}}
Line 2,765 ⟶ 2,839:
A very close/straightforward implementation of the Wikipedia pseudocode.
<
module IntPairs =
struct
Line 2,894 ⟶ 2,968:
print_newline ()
) _board;
print_newline ()</
{{out}}
Line 2,923 ⟶ 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,989 ⟶ 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 3,047 ⟶ 3,121:
(for-each print solved)
</syntaxhighlight>
<pre>
Line 3,093 ⟶ 3,167:
=={{header|Perl}}==
<
use strict; # https://rosettacode.org/wiki/A*_search_algorithm
Line 3,140 ⟶ 3,214:
unshift @path, $pos = $from{$pos};
}
print "$grid\nvalue $values{$finish} path @path\n";</
{{out}}
<pre>
Line 3,156 ⟶ 3,230:
===Extra Credit===
<
use strict; # https://rosettacode.org/wiki/A*_search_algorithm
Line 3,233 ⟶ 3,307:
abs($r1 - $r2) + abs($c1 - $c2)
} @tiles;
}</
{{out}}
<pre>
Line 3,252 ⟶ 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,324 ⟶ 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,347 ⟶ 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,492 ⟶ 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,529 ⟶ 3,603:
=={{header|PowerShell}}==
<
$grid = 0..($h - 1) | ForEach-Object { , (, $fill * $w) }
return $grid
Line 3,641 ⟶ 3,715:
Write-Output "Cost: $cost"
$routeString = ($route | ForEach-Object { "($($_[0]), $($_[1]))" }) -join ', '
Write-Output "Route: $routeString"</
{{out}}
<pre>
Line 3,654 ⟶ 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,759 ⟶ 3,871:
plt.xlim(-1,8)
plt.ylim(-1,8)
plt.show()</
{{out}}
Line 3,768 ⟶ 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,991 ⟶ 4,103:
<path-display>
(path-image random-M random-path))</
{{out}}
Line 4,004 ⟶ 4,116:
=={{header|Raku}}==
{{trans|Sidef}}
<syntaxhighlight lang="raku"
class AStarGraph {
Line 4,096 ⟶ 4,208:
.join.say for @grid ;
say "Path cost : ", cost, " and route : ", route;</
{{out}}<pre>██████████
█x.......█
Line 4,110 ⟶ 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 4,192 ⟶ 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 4,217 ⟶ 4,329:
=={{header|SequenceL}}==
<
import <Utilities/Set.sl>;
import <Utilities/Math.sl>;
Line 4,317 ⟶ 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,335 ⟶ 4,447:
=={{header|Sidef}}==
{{trans|Python}}
<
has barriers = [
Line 4,439 ⟶ 4,551:
grid.each { .join.say }
say "Path cost #{cost}: #{route}"</
{{out}}
<pre>
Line 4,458 ⟶ 4,570:
{{works with|Bourne Again SHell}}
<
#!/bin/bash
Line 4,831 ⟶ 4,943:
main "$@"
</syntaxhighlight>
{{out}}
<pre>
Line 4,848 ⟶ 4,960:
=={{header|Wren}}==
{{trans|Sidef}}
<
var Contains = Fn.new { |pairs, p|
Line 4,964 ⟶ 5,076:
}
for (line in grid) System.print(line.join())
System.print("\npath cost %(cost): %(route)")</
{{out}}
Line 4,984 ⟶ 5,096:
=={{header|zkl}}==
{{trans|Python}}
<
fcn toKey(xy){ xy.concat(",") }
Line 5,038 ⟶ 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 5,065 ⟶ 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 5,076 ⟶ 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>
|