A* search algorithm: Difference between revisions

{{trans|Python}}

F heuristic(start, goal)

V D = 1

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)

{{out}}

=={{header|C}}==

#include <stdlib.h>

#include <stdio.h>

return 0;

}

{{out}}

<pre>

=={{header|C sharp|C#}}==

using System;

using System.Collections.Generic;

}

}

{{out}}

<pre>

=={{header|C++}}==

#include <list>

#include <algorithm>

return 0;

}

{{out}}

<pre>

=={{header|Common Lisp}}==

(eval-when (:load-toplevel :compile-toplevel :execute)

(ql:quickload '("pileup" "iterate")))

(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)

{{out}}

=={{header|D}}==

ported from c++ code

import std.stdio;

return 0;

}

{{out}}

<pre>

=={{Header|FreeBASIC}}==

'###############################

'### A* search algorithm ###

end if

end

{{out}}

<pre>

=={{header|Go}}==

// on the graph representation.

package astar

h[last].fx = -1

return h[last]

import (

fmt.Println("Route:", route)

fmt.Println("Cost:", cost)

{{out}}

<pre>

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

deque q = case q of

EmptyQueue -> Nothing

The simple graph combinators:

import Data.Map (Map(..))

import qualified Data.Map as Map

if x `elem` ns

then Map.empty

Finally, the search algorythm, as given in Wikipedia.

get m x = Map.findWithDefault maxBound x m

getPath m = reverse $ goal : unfoldr go goal

Example

main = let

print path

mapM_ putStrLn picture

<pre>λ> main

[(1,1),(2,1),(3,1),(4,1),(5,1),(6,2),(6,3),(6,4),(6,5),(6,6),(7,7)]

Implementation:

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

end.

((<end){values) ; (<end){best

Task example:

┌──┬───┐

│11│0 0│

...xxxxx

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;

}

}

{{out}}

<pre>

=={{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;

path = []; createMap(); opn.push( start ); solveMap();

}

{{out}}<pre>

Path: 11

</pre>

Implementation using recursive strategy

function manhattan(x1, y1, x2, y2) {

return Math.abs(x1 - x2) + Math.abs(y1 - y2);

console.log(aStar(board, 0,0, 7,7));

{{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 ] ]

=={{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

println()

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)]

=={{header|Kotlin}}==

import java.lang.Math.abs

println("Cost: $cost Path: $path")

}

{{out}}<pre>

Cost: 11

=={{header|Lua}}==

-- QUEUE -----------------------------------------------------------------------

Queue = {}

print( "can not find a path!" )

end

{{out}}

<pre>

=={{header|Nim}}==

Implementation of the Wikipedia pseudocode.

# A* search algorithm.

else:

printSolution(path, cost)

{{out}}

A very close/straightforward implementation of the Wikipedia pseudocode.

module IntPairs =

struct

print_newline ()

) _board;

{{out}}

=={{header|Ol}}==

; level: list of lists, any except 1 means the cell is empty

; from: start cell in (x . y) mean

(cons (+ x 1) y)))))

(step1 (- n 1) c-list-set o-list-set))))))))

{{out}}

(define level '(

(1 1 1 1 1 1 1 1 1 1)

(for-each print solved)

<pre>

=={{header|Perl}}==

use strict; # https://rosettacode.org/wiki/A*_search_algorithm

unshift @path, $pos = $from{$pos};

}

{{out}}

<pre>

===Extra Credit===

use strict; # https://rosettacode.org/wiki/A*_search_algorithm

abs($r1 - $r2) + abs($c1 - $c2)

} @tiles;

{{out}}

<pre>

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:::::::

<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}}

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>

<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}}

=={{header|PowerShell}}==

$grid = 0..($h - 1) | ForEach-Object { , (, $fill * $w) }

return $grid

Write-Output "Cost: $cost"

$routeString = ($route | ForEach-Object { "($($_[0]), $($_[1]))" }) -join ', '

{{out}}

<pre>

=={{header|Picat}}==

% Picat's planner supports A* search with heuristics.

% See the program for the 15-puzzle at https://rosettacode.org/wiki/15_puzzle_solver#Picat

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)].

{{out}}

<pre>

=={{header|Python}}==

import matplotlib.pyplot as plt

plt.xlim(-1,8)

plt.ylim(-1,8)

{{out}}

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>

<path-display>

{{out}}

=={{header|Raku}}==

{{trans|Sidef}}

class AStarGraph {

.join.say for @grid ;

{{out}}<pre>██████████

█x.......█

=={{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.*/

say ind translate(L'│', , .) /*display a " " " " */

end /*c*/ /*a 19x19 grid can be shown 80 columns.*/

{{out|output|text=&nbsp; when using the default input:}}

<pre>

=={{header|SequenceL}}==

import <Utilities/Set.sl>;

import <Utilities/Math.sl>;

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]);

{{out|Output|text=&nbsp;}}

<pre>

=={{header|Sidef}}==

{{trans|Python}}

has barriers = [

grid.each { .join.say }

{{out}}

<pre>

{{works with|Bourne Again SHell}}

#!/bin/bash

main "$@"

{{out}}

<pre>

=={{header|Wren}}==

{{trans|Sidef}}

var Contains = Fn.new { |pairs, p|

}

for (line in grid) System.print(line.join())

{{out}}

=={{header|zkl}}==

{{trans|Python}}

fcn toKey(xy){ xy.concat(",") }

} // 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

1 # Normal movement cost

}

route,cost := AStarSearch(T(0,0), T(7,7), graph);

println("Route: ", route.apply(fcn(xy){ String("(",toKey(xy),")") }).concat(","));

foreach x,y in (route){ grid[x][y]="+" }

grid[0][0] = "S"; grid[7][7] = "E";

{{out}}

<pre>