A* search algorithm: Difference between revisions

Line 35:

<syntaxhighlight lang=11l>F AStarSearch(start, end, barriers)

<syntaxhighlight lang="11l">F AStarSearch(start, end, barriers)

F heuristic(start, goal)

V D = 1

Line 116:

=={{header|C}}==

#include <stdlib.h>

#include <stdio.h>

Line 396:

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

using System;

using System.Collections.Generic;

Line 663:

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

#include <list>

#include <algorithm>

Line 847:

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

<syntaxhighlight lang=lisp>;; * Using external libraries with quicklisp

<syntaxhighlight lang="lisp">;; * Using external libraries with quicklisp

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

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

Line 1,023:

=={{header|D}}==

ported from c++ code

import std.stdio;

Line 1,198:

=={{Header|FreeBASIC}}==

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

'### A* search algorithm ###

Line 1,465:

=={{header|Go}}==

<syntaxhighlight lang=go>// Package astar implements the A* search algorithm with minimal constraints

<syntaxhighlight lang="go">// Package astar implements the A* search algorithm with minimal constraints

// on the graph representation.

package astar

Line 1,578:

return h[last]

}</syntaxhighlight>

<syntaxhighlight lang=go>package main

<syntaxhighlight lang="go">package main

import (

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

<syntaxhighlight lang=haskell>{-# language DeriveFoldable #-}

<syntaxhighlight lang="haskell">{-# language DeriveFoldable #-}

module PQueue where

Line 1,673:

The simple graph combinators:

<syntaxhighlight lang=haskell>import PQueue

<syntaxhighlight lang="haskell">import PQueue

import Data.Map (Map(..))

import qualified Data.Map as Map

Line 1,697:

Finally, the search algorythm, as given in Wikipedia.

<syntaxhighlight lang=haskell>get :: (Ord k, Bounded a) => Map k a -> k -> a

<syntaxhighlight lang="haskell">get :: (Ord k, Bounded a) => Map k a -> k -> a

get m x = Map.findWithDefault maxBound x m

Line 1,741:

Example

<syntaxhighlight lang=haskell>distL1 (x,y) (a,b) = max (abs $ x-a) (abs $ y-b)

<syntaxhighlight lang="haskell">distL1 (x,y) (a,b) = max (abs $ x-a) (abs $ y-b)

main = let

Line 1,776:

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

Line 1,808:

Task example:

<syntaxhighlight lang=J> Asrch''

<syntaxhighlight lang="j"> Asrch''

┌──┬───┐

│11│0 0│

Line 1,839:

=={{header|Java}}==

package astar;

Line 2,097:

=={{header|JavaScript}}==

Animated. 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,215:

</pre>

Implementation using recursive strategy

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

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

Line 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.

<syntaxhighlight lang=~~Julia~~>using LightGraphs, SimpleWeightedGraphs

<syntaxhighlight lang="julia">using LightGraphs, SimpleWeightedGraphs

const chessboardsize = 8

Line 2,346:

=={{header|Kotlin}}==

import java.lang.Math.abs

Line 2,464:

=={{header|Lua}}==

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

Queue = {}

Line 2,683:

=={{header|Nim}}==

Implementation of the Wikipedia pseudocode.

# A* search algorithm.

Line 2,839:

A very close/straightforward implementation of the Wikipedia pseudocode.

module IntPairs =

struct

Line 2,997:

=={{header|Ol}}==

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

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

Line 3,066:

(define level '(

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

Line 3,167:

=={{header|Perl}}==

<syntaxhighlight lang=perl>#!/usr/bin/perl

<syntaxhighlight lang="perl">#!/usr/bin/perl

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

Line 3,230:

===Extra Credit===

<syntaxhighlight lang=perl>#!/usr/bin/perl

<syntaxhighlight lang="perl">#!/usr/bin/perl

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

Line 3,326:

Note that the 23 visited nodes does not count walls, but with them this algorithm exactly matches the 35 of Racket.

sequence grid = split("""

x:::::::

Line 3,421:

lowest cost and a simple dictionary to avoid re-examination/inifinte recursion.

--set_rand(3) -- (for consistent output)

constant optimal = false,

Line 3,603:

=={{header|PowerShell}}==

<syntaxhighlight lang=powershell>function CreateGrid($h, $w, $fill) {

<syntaxhighlight lang="powershell">function CreateGrid($h, $w, $fill) {

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

return $grid

Line 3,731:

=={{header|Picat}}==

<syntaxhighlight lang=~~Picat~~>% Picat's tabling system uses an algorithm like Dijkstra's to find an optimal solution.

<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

Line 3,770:

=={{header|Python}}==

<syntaxhighlight lang=python>from __future__ import print_function

<syntaxhighlight lang="python">from __future__ import print_function

import matplotlib.pyplot as plt

Line 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.

<syntaxhighlight lang=racket>#lang scribble/lp

<syntaxhighlight lang="racket">#lang scribble/lp

@(chunk

<graph-sig>

Line 4,116:

=={{header|Raku}}==

<syntaxhighlight lang=~~perl6~~># 20200427 Raku programming solution

<syntaxhighlight lang="raku" line># 20200427 Raku programming solution

class AStarGraph {

Line 4,222:

=={{header|REXX}}==

<syntaxhighlight lang=rexx>/*REXX program solves the A* search problem for a (general) NxN grid. */

<syntaxhighlight lang="rexx">/*REXX program solves the A* search problem for a (general) NxN grid. */

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

=={{header|SequenceL}}==

import <Utilities/Set.sl>;

import <Utilities/Math.sl>;

Line 4,447:

=={{header|Sidef}}==

<syntaxhighlight lang=ruby>class AStarGraph {

<syntaxhighlight lang="ruby">class AStarGraph {

has barriers = [

Line 4,570:

#!/bin/bash

Line 4,960:

=={{header|Wren}}==

<syntaxhighlight lang=ecmascript>var Equals = Fn.new { |p1, p2| p1[0] == p2[0] && p1[1] == p2[1] }

<syntaxhighlight lang="ecmascript">var Equals = Fn.new { |p1, p2| p1[0] == p2[0] && p1[1] == p2[1] }

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

Line 5,096:

=={{header|zkl}}==

<syntaxhighlight lang=zkl> // we use strings as hash keys: (x,y)-->"x,y", keys are a single pair

<syntaxhighlight lang="zkl"> // we use strings as hash keys: (x,y)-->"x,y", keys are a single pair

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

Line 5,151:

throw(Exception.AssertionError("A* failed to find a solution"));

}</syntaxhighlight>

<syntaxhighlight lang=zkl>class [static] AStarGraph{ # Define a class board like grid with barriers

<syntaxhighlight lang="zkl">class [static] AStarGraph{ # Define a class board like grid with barriers

var [const] barriers =

T( T(3,2),T(4,2),T(5,2), // T is RO List

Line 5,178:

}

}</syntaxhighlight>

<syntaxhighlight lang=zkl>graph:=AStarGraph;

<syntaxhighlight lang="zkl">graph:=AStarGraph;

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

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