# A* (A-Star) Algorithm

## Introduction

The A* algorithm is a pathfinding algorithm used in artificial intelligence and robotics to find the shortest path between two points. It is widely used in video games, GPS systems, and other applications that require finding optimal paths. The algorithm uses a heuristic function to estimate the distance between the current node and the goal node, and combines it with the cost of the path from the start node to the current node to determine the best next step.

## Implementation

The A* algorithm is implemented in OCaml using a priority queue to store the open set of nodes to be explored. The algorithm also uses two sets, closedSet and openSet, to keep track of visited and unvisited nodes, respectively. The function `find_path`

takes the starting and goal positions, as well as a board representing the environment in which the path is to be found. The board is represented as a two-dimensional array of integers, where 0 represents an obstacle and any positive integer represents a clear path.

```
module IntPairs =
struct
type t = int * int
let compare (x0,y0) (x1,y1) =
match Stdlib.compare x0 x1 with
| 0 -> Stdlib.compare y0 y1
| c -> c
end
module PairsMap = Map.Make(IntPairs)
module PairsSet = Set.Make(IntPairs)
let find_path start goal board =
let max_y = Array.length board in
let max_x = Array.length board.(0) in
let get_neighbors (x, y) =
let moves = [(0, 1); (0, -1); (1, 0); (-1, 0);
(1, 1); (1, -1); (-1, 1); (-1, -1)] in
let ms = List.map (fun (_x, _y) -> x+_x, y+_y) moves in
let ms = List.filter (fun (x, y) ->
x >= 0 && x < max_x && y >= 0 && y < max_y
&& board.(y).(x) <> 0
) ms in
(ms)
in
let h (x0, y0) (x1, y1) =
abs (x0 - x1) + abs (y0 - y1)
in
let openSet = PairsSet.add start PairsSet.empty in
let closedSet = PairsSet.empty in
let fScore = PairsMap.add start (h goal start) PairsMap.empty in
let gScore = PairsMap.add start 0 PairsMap.empty in
let cameFrom = PairsMap.empty in
let reconstruct_path cameFrom current =
let rec aux acc current =
let from = PairsMap.find current cameFrom in
if from = start then (from::acc)
else aux (from::acc) from
in
aux [current] current
in
let d current neighbor =
let x, y = neighbor in
board.(y).(x)
in
let g gScore cell =
match PairsMap.find_opt cell gScore with
| Some v -> v | None -> max_int
in
let rec _find_path (openSet, closedSet, fScore, gScore, cameFrom) =
if PairsSet.is_empty openSet then None else
let current =
PairsSet.fold (fun p1 p2 ->
if p2 = (-1, -1) then p1 else
let s1 = PairsMap.find p1 fScore
and s2 = PairsMap.find p2 fScore in
if s1 < s2 then p1 else p2
) openSet (-1, -1)
in
if current = goal then Some (reconstruct_path cameFrom current) else
let openSet = PairsSet.remove current openSet in
let closedSet = PairsSet.add current closedSet in
let neighbors = get_neighbors current in
neighbors |>
List.fold_left
(fun ((openSet, closedSet, fScore, gScore, cameFrom) as v) neighbor ->
if PairsSet.mem neighbor closedSet then (v) else
let tentative_gScore = (g gScore current) + (d current neighbor) in
if tentative_gScore < (g gScore neighbor) then
let cameFrom = PairsMap.add neighbor current cameFrom in
let gScore = PairsMap.add neighbor tentative_gScore gScore in
let f = (g gScore neighbor) + (h neighbor goal) in
let fScore = PairsMap.add neighbor f fScore in
let openSet =
if not (PairsSet.mem neighbor openSet)
then PairsSet.add neighbor openSet else openSet
in
(openSet, closedSet, fScore, gScore, cameFrom)
else (v)
) (openSet, closedSet, fScore, gScore, cameFrom)
|> _find_path
in
_find_path (openSet, closedSet, fScore, gScore, cameFrom)
```

Here is an example.

```
let () =
let board = [|
[| 1; 1; 1; 1; 1; 1; 1; 1; |];
[| 1; 1; 1; 1; 1; 1; 1; 1; |];
[| 1; 1; 1; 0; 0; 0; 1; 1; |];
[| 1; 1; 1; 1; 1; 0; 1; 1; |];
[| 1; 1; 0; 1; 1; 0; 1; 1; |];
[| 1; 1; 0; 1; 1; 0; 1; 1; |];
[| 1; 1; 0; 0; 0; 0; 1; 1; |];
[| 1; 1; 1; 1; 1; 1; 1; 1; |];
|] in
let start = (0, 0) in
let goal = (7, 7) in
let dim_x = Array.length board.(0) in
let dim_y = Array.length board in
let r = find_path start goal board in
match r with
| None -> failwith "path not found"
| Some p ->
List.iter (fun (x, y) -> Printf.printf " (%d, %d)\n" x y) p;
print_newline ();
let _board =
Array.init dim_y (fun y ->
Array.init dim_x (fun x ->
if board.(y).(x) = 0 then '#' else '.'))
in
List.iter (fun (x, y) -> _board.(y).(x) <- '*') p;
Array.iter (fun line ->
Array.iter (fun c ->
Printf.printf " %c" c;
) line;
print_newline ()
) _board;
print_newline ()
```

## Step-by-step Explanation

- The maximum x and y coordinates of the board are obtained using the
`Array.length`

function. - The
`get_neighbors`

function takes a position (x,y) and returns a list of neighboring positions that are not obstacles. - The
`h`

function takes two positions and returns the Manhattan distance between them. - The openSet is initialized with the starting position, and the closedSet is empty.
- The
`fScore`

and`gScore`

maps are initialized with the starting position, where`fScore`

is the sum of`gScore`

and the heuristic function. - The
`cameFrom`

map is initialized as empty. - The
`reconstruct_path`

function takes the`cameFrom`

map and the current position and returns the path from the starting position to the current position. - The
`d`

function takes two positions and returns the cost of moving from the first position to the second. - The
`g`

function takes the`gScore`

map and a position and returns its`gScore`

value. - The
`_find_path`

function takes the current state of the search and performs the following steps:- If the openSet is empty, return None.
- Select the node with the lowest
`fScore`

value from the openSet. - If the selected node is the goal, return the reconstructed path from the starting position to the goal.
- Remove the selected node from the openSet and add it to the closedSet.
- Generate a list of neighboring nodes.
- For each neighboring node:

- If it is in the closedSet, skip it.
- Calculate the tentative
`gScore`

value for the node. - If the
`gScore`

value is better than the current value, update the`gScore`

,`fScore`

, and`cameFrom`

maps. - If the node is not in the openSet, add it to the openSet.

- Recursively call`_find_path`

with the updated state.

- Call
`_find_path`

with the initial state.

## Complexity Analysis

The time complexity of the A* algorithm depends on the heuristic function used and the size of the board. In the worst case, where the heuristic function overestimates the true distance, the algorithm can explore all nodes in the board, resulting in a time complexity of O(b^d), where b is the branching factor (number of neighbors per node) and d is the depth of the goal node. However, in practice, the algorithm often explores fewer nodes than this worst-case bound.

The space complexity of the algorithm is also dependent on the size of the board, as it stores the openSet, closedSet, `fScore`

, `gScore`

, and `cameFrom`

maps. However, the space complexity can be reduced by using a more memory-efficient data structure for the