A* search algorithm: Difference between revisions
m
Automated syntax highlighting fixup (second round - minor fixes)
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
Thundergnat (talk | contribs) m (Automated syntax highlighting fixup (second round - minor fixes)) |
||
Line 35:
{{trans|Python}}
<syntaxhighlight lang="11l">F AStarSearch(start, end, barriers)
F heuristic(start, goal)
V D = 1
Line 116:
=={{header|C}}==
<syntaxhighlight lang="c">
#include <stdlib.h>
#include <stdio.h>
Line 396:
=={{header|C sharp|C#}}==
<syntaxhighlight lang="csharp">
using System;
using System.Collections.Generic;
Line 663:
=={{header|C++}}==
<syntaxhighlight lang="cpp">
#include <list>
#include <algorithm>
Line 847:
=={{header|Common Lisp}}==
<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
<syntaxhighlight lang=
import std.stdio;
Line 1,198:
=={{Header|FreeBASIC}}==
<syntaxhighlight lang="freebasic">
'###############################
'### A* search algorithm ###
Line 1,465:
=={{header|Go}}==
<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
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 #-}
module PQueue where
Line 1,673:
The simple graph combinators:
<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
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)
main = let
Line 1,776:
Implementation:
<syntaxhighlight lang=
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=
┌──┬───┐
│11│0 0│
Line 1,839:
=={{header|Java}}==
<syntaxhighlight lang="java">
package astar;
Line 2,097:
=={{header|JavaScript}}==
Animated.<br />To see how it works on a random map go [http://paulo-jorente.de/tests/astar/ here]
<syntaxhighlight lang="javascript">
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
<syntaxhighlight lang="javascript">
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=
const chessboardsize = 8
Line 2,346:
=={{header|Kotlin}}==
<syntaxhighlight lang="kotlin">
import java.lang.Math.abs
Line 2,464:
=={{header|Lua}}==
<syntaxhighlight lang="lua">
-- QUEUE -----------------------------------------------------------------------
Queue = {}
Line 2,683:
=={{header|Nim}}==
Implementation of the Wikipedia pseudocode.
<syntaxhighlight lang=
# A* search algorithm.
Line 2,839:
A very close/straightforward implementation of the Wikipedia pseudocode.
<syntaxhighlight lang="ocaml">
module IntPairs =
struct
Line 2,997:
=={{header|Ol}}==
<syntaxhighlight lang="scheme">
; level: list of lists, any except 1 means the cell is empty
; from: start cell in (x . y) mean
Line 3,066:
{{out}}
<syntaxhighlight lang="scheme">
(define level '(
(1 1 1 1 1 1 1 1 1 1)
Line 3,167:
=={{header|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
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.
<!--<syntaxhighlight lang=
<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,421:
lowest cost and a simple dictionary to avoid re-examination/inifinte recursion.
<!--<syntaxhighlight lang=
<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,603:
=={{header|PowerShell}}==
<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'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
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
@(chunk
<graph-sig>
Line 4,116:
=={{header|Raku}}==
{{trans|Sidef}}
<syntaxhighlight lang=
class AStarGraph {
Line 4,222:
=={{header|REXX}}==
<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}}==
<syntaxhighlight lang="sequencel">
import <Utilities/Set.sl>;
import <Utilities/Math.sl>;
Line 4,447:
=={{header|Sidef}}==
{{trans|Python}}
<syntaxhighlight lang="ruby">class AStarGraph {
has barriers = [
Line 4,570:
{{works with|Bourne Again SHell}}
<syntaxhighlight lang="bash">
#!/bin/bash
Line 4,960:
=={{header|Wren}}==
{{trans|Sidef}}
<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}}==
{{trans|Python}}
<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
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;
route,cost := AStarSearch(T(0,0), T(7,7), graph);
println("Route: ", route.apply(fcn(xy){ String("(",toKey(xy),")") }).concat(","));
| |||