gwg/pathfinding

Types

Action

A transition to a state by an action with a weight.

The weight could mean a cost, the distance or terrain difficulty, …

pub type Action(action, state) {
  Action(action: action, state: state, weight: Float)
}

Constructors

Action(action: action, state: state, weight: Float)

Successor

</>

A function that takes the current state and its G score and returns a list of possible Actions.

pub type Successor(action, state) =
  fn(state, Float) -> List(Action(action, state))

Values

astar

</>

pub fn astar(
  init state: state,
  successor successor_fun: fn(state, Float) -> List(
    Action(action, state),
  ),
  heuristic heuristic_fun: fn(state) -> Float,
) -> Result(List(action), List(action))

Performs an A* search to find the optimal path from an initial state.

This function returns a the sequence of actions to reach the goal when the heuristic_fun returns 0.0 (or less), signaling the goal has been reached.

If the goal can not be reach, it will returns the sequence of actions to the “closest” state reached.

Examples

let actions = [
  Vec2(-1, 0),
  Vec2(1, 0),
  Vec2(0, -1),
  Vec2(0, 1),
  Vec2(-1, -1),
  Vec2(-1, 1),
  Vec2(1, -1),
  Vec2(1, 1),
]

let world0 =
  vec2i_dict.from_string(
    ""
    <> "###########\n"
    <> "#   #     #\n"
    <> "#   #     #\n"
    <> "#   #     #\n"
    <> "#   ## ####\n"
    <> "#   #     #\n"
    <> "#   #     #\n"
    <> "## ##### ##\n"
    <> "#   # #   #\n"
    <> "#         #\n"
    <> "###########\n",
  )

let world1 =
  vec2i_dict.from_string(
    ""
    <> "###########\n"
    <> "#   #     #\n"
    <> "#   #     #\n"
    <> "#   #     #\n"
    <> "#   ##x####\n"
    <> "#   #     #\n"
    <> "#   #     #\n"
    <> "## ##### ##\n"
    <> "#   # #   #\n"
    <> "#         #\n"
    <> "###########\n",
  )

let init = Vec2(2, 2)
let target = Vec2(7, 2)

fn successor(
  state: Vec2i,
  g_score: Float,
  world: Dict(Vec2i, String),
) -> List(Action(Vec2i, Vec2i)) {
  actions
  |> list.filter_map(fn(action) {
    let weight = action |> vec2i.length

    use <- bool.guard(g_score +. weight >. 32.0, Error(Nil))

    let state = state |> vec2i.add(action)

    case world |> dict.has_key(state) {
      True -> Error(Nil)
      False -> Ok(Action(action:, state:, weight:))
    }
  })
}

fn heuristic(state: Vec2i) -> Float {
  vec2i.distance(state, target)
}

astar(
  init:,
  successor: fn(state, g_score) {
    successor(state, g_score, world0)
  },
  heuristic:,
)
// Ok:
// ###########
// #   #     #
// # @ #  *  #
// # ↓ # ↗   #
// # ↓ ##↑####
// # ↓ #  ↖  #
// # ↓ #   ↖ #
// ##↘#####↑##
// #  ↘# #↗  #
// #   →→↗   #
// ###########

astar(
  init:,
  successor: fn(state, g_score) {
    successor(state, g_score, world1)
  },
  heuristic:,
)
// Error:
// ###########
// #   #     #
// # @ #  *  #
// # ↓ #     #
// # ↓ ##x####
// # ↓ #     #
// # ↓ #   ↖ #
// ##↘#####↑##
// #  ↘# #↗  #
// #   →→↗   #
// ###########

flowfield

</>

pub fn flowfield(
  init state: state,
  successor successor_fun: fn(state, Float) -> List(
    Action(action, state),
  ),
) -> dict.Dict(state, action)

Generates a flowfield (also known as vector field or Dijkstra map).

Examples

let actions = [
  Vec2(-1, 0),
  Vec2(1, 0),
  Vec2(0, -1),
  Vec2(0, 1),
  Vec2(-1, -1),
  Vec2(-1, 1),
  Vec2(1, -1),
  Vec2(1, 1),
]

let world =
  vec2i_dict.from_string(
    ""
    <> "     #     \n"
    <> " ###   ### \n"
    <> "           \n"
    <> "### ##### #\n"
    <> "# # #   # #\n"
    <> "# # # # # #\n"
    <> "# # ### # #\n"
    <> "# #     # #\n"
    <> "# ####### #\n"
    <> "#         #\n"
    <> "###########\n",
  )

let target = Vec2(5, 5)

fn successor(state: Vec2i, g_score: Float) -> List(Action(Vec2i, Vec2i)) {
  actions
  |> list.filter_map(fn(action) {
    let weight = action |> vec2i.length

    use <- bool.guard(g_score +. weight >. 32.0, Error(Nil))
    use <- bool.guard(vec2i.distance(state, target) >. 16.0, Error(Nil))

    let state = state |> vec2i.subtract(action)

    case world |> dict.has_key(state) {
      True -> Error(Nil)
      False -> Ok(Action(action:, state:, weight:))
    }
  })
}

astar(init:, successor:)
// ↓↙→↘↓#↙←←←←
// ↘###↓↙←###↙
// →→↘↓↙←←←←←←
// ###↓#####↖#
// # #↓#↓↙←#↑#
// # #↓#*#↖#↑#
// # #↘###↑#↑#
// # #→→→↗↑#↑#
// # #######↑#
// #→→→→→→→↗↑#
// ###########