user
The A\* search algorithm is an extension of Dijkstra's algorithm useful for finding the lowest cost path between two nodes (aka vertices) of a graph. The path may traverse any number of nodes connected by edges (aka arcs) with each edge having an associated cost. The algorithm uses a heuristic which associates an estimate of the lowest cost path from this node to the goal node, such that this estimate is never greater than the actual cost.

The algorithm should not assume that all edge costs are the same. It should be possible to start and finish on any node, including ones identified as a barrier in the task.

Task

Consider the problem of finding a route across the diagonal of a chess board-like 8x8 grid. The rows are numbered from 0 to 7. The columns are also numbered 0 to 7. The start position is (0, 0) and the end position is (7, 7). Movement is allow by one square in any direction including diagonals, similar to a king in chess. The standard movement cost is 1. To make things slightly harder, there is a barrier that occupy certain positions of the grid. Moving into any of the barrier positions has a cost of 100.

The barrier occupies the positions (2,4), (2,5), (2,6), (3,6), (4,6), (5,6), (5,5), (5,4), (5,3), (5,2), (4,2) and (3,2).

A route with the lowest cost should be found using the A\* search algorithm (there are multiple optimal solutions with the same total cost).

Print the optimal route in text format, as well as the total cost of the route.

Optionally, draw the optimal route and the barrier positions.

Note: using a heuristic score of zero is equivalent to Dijkstra's algorithm and that's kind of cheating/not really A\*!

*Extra Credit*

Use this algorithm to solve an 8 puzzle. Each node of the input graph will represent an arrangement of the tiles. The nodes will be connected by 4 edges representing swapping the blank tile up, down, left, or right. The cost of each edge is 1. The heuristic will be the sum of the manhatten distance of each numbered tile from its goal position. An 8 puzzle graph will have 9!/2 (181,440) nodes. The 15 puzzle has over 10 trillion nodes. This algorithm may solve simple 15 puzzles (but there are not many of those).

See also

* Wikipedia webpage:   A\* search algorithm.
* An introduction to: Breadth First Search |> Dijkstra’s Algorithm |> A\*

Related tasks

* 15 puzzle solver
* Dijkstra's algorithm
* Knapsack problem/0-1
assistant
**Translation of**: Sidef

```
# 20200427 Raku programming solution

class AStarGraph {

   has @.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>;

   method heuristic(\start, \goal) {
      my (\D1,\D2) = 1, 1;
      my (\dx,\dy) = ( start.list »-« goal.list )».abs;
      return  (D1 * (dx + dy)) + (D2 - 2*D1) * min dx, dy
   }

   method get_vertex_neighbours(\pos) {
      gather {
         for <1 0>,<-1 0>,<0 1>,<0 -1>,<1 1>,<-1 1>,<1 -1>,<-1 -1> -> \d {
            my (\x2,\y2) = pos.list »+« d.list;
            (x2 < 0 || x2 > 7 || y2 < 0 || y2 > 7) && next;
            take x2, y2;
         }
      }
   }

   method move_cost(\a,\b) { (b ~~ any self.barriers) ?? 100 !! 1 }
}

sub AStarSearch(\start, \end, \graph) {

   my (%G,%F);

   %G{start.Str} = 0;
   %F{start.Str} = graph.heuristic(start, end);

   my @closedVertices = [];
   my @openVertices = [].push(start);
   my %cameFrom;

   while (@openVertices.Bool) {
      my $current = Nil; my $currentFscore = Inf;

      for @openVertices -> \pos {
         if (%F{pos.Str} < $currentFscore) {
            $currentFscore = %F{pos.Str};
            $current = pos
         }
      }

      if $current ~~ end {
         my @path = [].push($current);
         while %cameFrom{$current.Str}:exists {
            $current = %cameFrom{$current.Str};
            @path.push($current)
         }
         return @path.reverse, %F{end.Str}
      }

      @openVertices .=  grep: * !eqv $current;
      @closedVertices.push($current);

      for (graph.get_vertex_neighbours($current)) -> \neighbour {
         next if neighbour ~~ any @closedVertices;
         my \candidateG = %G{$current.Str}+graph.move_cost($current,neighbour);

         if !(neighbour ~~ any @openVertices) {
            @openVertices.push(neighbour)
         } elsif (candidateG ≥ %G{neighbour.Str}) {
            next
         }

         %cameFrom{neighbour.Str} = $current;
         %G{neighbour.Str} = candidateG;
         my \H = graph.heuristic(neighbour, end);
         %F{neighbour.Str} = %G{neighbour.Str} + H;
      }
   }
   die "A* failed to find a solution"
}

my \graph = AStarGraph.new;
my (\route, \cost) = AStarSearch(<0 0>, <7 7>, graph);

my \w = my \h = 10;

my @grid = [ ['.' xx w ] xx h ];
for ^h -> \y { @grid[y;0] = "█"; @grid[y;*-1] = "█" }
for ^w -> \x { @grid[0;x] = "█"; @grid[*-1;x] = "█" }

for (graph.barriers) -> \d { @grid[d[0]+1][d[1]+1] = "█" }
for @(route)         -> \d { @grid[d[0]+1][d[1]+1] = "x" }

.join.say for @grid ;

say "Path cost : ", cost, " and route : ", route;

```

Output:

```
██████████

█x.......█
█.x......█
█..x.███.█
█.x█...█.█
█.x█...█.█
█.x█████.█
█..xxxxx.█
█.......x█
██████████

Path cost : 11 and 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))
```