The A* Algorithm (A-star)

1. Introduction

The A* (A-star) algorithm is a highly popular pathfinding algorithm used in artificial intelligence and robotics to find the shortest path between a start node and a goal node in a weighted graph. In OCaml, we can define this algorithm following a functional approach.

Here is an example implementation of the A* algorithm in OCaml, with detailed explanations for each step:

1. Types Used:

We do not need to explicitly define the types used, as they are inferred by the OCaml type system. However, for the sake of clarity, here are the types used in this example:

type node = int * int
type cost = float
type 'a map = 'a array array
type heuristic = node -> node -> cost

type path = node list
type path_cost = cost

- `node`: Type identifier for nodes.
- `cost`: Type for representing the distance or weight of edges.
- `map`: Type for representing a simple map. The generalized A* algorithm uses a graph containing nodes, with each node having a list of its neighbors along with the associated costs.
- `heuristic`: Heuristic function that estimates the remaining cost to reach the goal from a given node.

2. The A* Function:

Here is the main A* function that takes the graph, the start node, the goal node, the heuristic function as inputs, and returns the shortest (or optimal) path along with its cost:

let rec a_star map start goal =
  let w = Array.length map.(0) in
  let h = Array.length map in
  let dirs = [ (1, 0, 1.0); (0, 1, 1.0); (-1, 0, 1.0); (0, -1, 1.0); ] in
  let rec search queue closed =
    match queue with
    | [] -> []  (* no path found *)
    | (current, path, g_cost) :: rest ->
      if current = goal then List.rev (current :: path)  (* return *)
      else if List.mem current closed then search rest closed
      else
        let neighbors =
          let x, y = current in
          List.map (fun (dx, dy, c) -> (x + dx, y + dy, c)) dirs
        in
        let neighbors =
          neighbors
            |> List.filter (fun (x, y, _) -> x >= 0 && y >= 0 && x < w && y < h)
            |> List.filter (fun (x, y, _) -> map.(y).(x) = 0)
        in
        let new_paths =
          List.map (fun (x, y, cost) ->
            ((x, y), current :: path, g_cost +. cost)
          ) neighbors
        in
        let queue =
          List.sort (fun (p1, _, g1) (p2, _, g2) ->
            compare
              (g1 +. heu p1 goal)
              (g2 +. heu p2 goal)
          ) (List.rev_append new_paths rest)
        in
        search queue (current :: closed)
  in
  search [(start, [], 0.0)] []

- `a_star`: The main function that handles pathfinding using A*.
- `map`: The map in which the search is conducted.
- `start`: The starting node from which the search begins.
- `goal`: The target node that we wish to reach.
- `heuristic`: The heuristic function that estimates the remaining cost to reach the goal node from a given node.
- `(path, path_cost)`: The result of the A* function, i.e., the optimal path found and its total cost. `g_cost` may also be returned.

Explanation of the Algorithm:

1. Initialization:

The search begins with a single start node `(start, [], 0)` in the `queue`, where `path` is initially empty and `g_cost` (the actual cost to reach the current node) is initialized to 0.

2. Main Loop:

- The `search` function explores nodes from the `queue`, selecting at each step the node with the lowest cost (f = g + h).
- If the current node is the goal node (`current = goal`), the optimal path is found and returned.
- Otherwise, the neighboring nodes of the current node are added to the `queue` with their paths updated and their costs evaluated using the heuristic function.
- Nodes that have already been visited are added to the `closed` list.

3. The `List.sort` Function:

- Sorts the list of nodes in `queue` based on the cost function (f = g + h), where `g` is the actual cost from the start to the current node, and `h` is the heuristic predicting the cost from the current node to the goal.

- The `queue` list is maintained in sorted order based on the costs of the nodes to be explored, so by exploring the first node in this list, we prioritize the node that is most likely to be the closest to the goal.

4. The `List.mem` Function:

- The instruction (List.mem current closed) prevents re-exploring nodes that have already been explored.

5. Result:

- Once the goal node is reached, the path is reversed (`List.rev`) to obtain the correct order from the start node to the goal node.

- The `g_cost` parameter can also be returned to provide information about the cost of the found path.

This implementation uses standard list manipulation functions like `List.sort` to sort the elements of the list based on their cost, as well as functions to access already visited elements such as `List.mem` to avoid traversing the same node twice.

This approach allows for a clear and concise implementation of the A* algorithm in OCaml, following functional principles in an elegant manner.

Usage Example:

The heuristic function calculates the distance between two points.

(* heuristic function *)
let heu (x1, y1) (x2, y2) =
  let x = x2 - x1 in
  let y = y2 - y1 in
  sqrt (float (x * x + y * y))

let map = [|
  [| 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; |];
  [| 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; |];
  [| 0; 0; 0; 0; 0; 0; 0; 0; 0; 1; 1; |];
  [| 0; 0; 0; 0; 0; 1; 1; 1; 0; 0; 0; |];
  [| 0; 0; 0; 0; 0; 1; 0; 0; 0; 0; 0; |];
  [| 0; 0; 0; 0; 1; 1; 0; 0; 0; 0; 0; |];
  [| 0; 0; 0; 1; 1; 0; 0; 0; 0; 0; 0; |];
  [| 0; 0; 0; 1; 0; 0; 0; 0; 0; 0; 0; |];
  [| 0; 0; 0; 1; 0; 0; 0; 0; 0; 0; 0; |];
|]

let () =
  let r = a_star map (0, 0) (10, 8) in
  let map =
    Array.map (fun line ->
      Array.map (fun d ->
        match d with
        | 0 -> '.'
        | 1 -> '#'
        | _ -> '?'
      ) line
    ) map
  in
  List.iter (fun (x, y) -> map.(y).(x) <- '*') r;
  List.iter (fun (x, y) -> Printf.printf " (%d, %d)\n" x y) r;
  Array.iter (fun line ->
    Array.iter (fun c ->
      Printf.printf " %c" c
    ) line;
    print_newline ()
  ) map;
;;

$ ocaml a-star.ml

 (0, 0)
 (1, 0)
 (2, 0)
 (3, 0)
 (4, 0)
 (5, 0)
 (6, 0)
 (7, 0)
 (8, 0)
 (8, 1)
 (8, 2)
 (8, 3)
 (8, 4)
 (8, 5)
 (8, 6)
 (8, 7)
 (9, 7)
 (9, 8)
 (10, 8)
 * * * * * * * * * . .
 . . . . . . . . * . .
 . . . . . . . . * # #
 . . . . . # # # * . .
 . . . . . # . . * . .
 . . . . # # . . * . .
 . . . # # . . . * . .
 . . . # . . . . * * .
 . . . # . . . . . * *

Possible Variations:

To reduce the amount of computation, you can also use a Manhattan distance calculation function as the heuristic, which will also yield satisfactory results:

(* heuristic function *)
let heu (x1, y1) (x2, y2) =
  let x = x2 - x1 in
  let y = y2 - y1 in
  (float (x + y))

Diagonal Movement:

To enable diagonal movement, add the following possible directions:

  let dirs = dirs @ [ (1, 1, 1.4); (1, -1, 1.4); (-1, -1, 1.4); (-1, 1, 1.4); ] in