///|
/// One action of a goal-oriented plan: when it applies, what it changes, and what it costs.
///
/// A GOAP plan is searched over world states, so an action has to be a pure function of the
/// state it runs in — that is what lets the search try it without side effects.
pub(all) struct GoapAction[S] {
name : String
applies : (S) -> Bool
effect : (S) -> S
cost : (S) -> Double
}
///|
/// An action named `name` that applies when `applies`, produces `effect`, and costs 1 by
/// default.
pub fn[S] GoapAction::new(
name~ : String,
applies~ : (S) -> Bool,
effect~ : (S) -> S,
cost? : (S) -> Double,
) -> GoapAction[S] {
{
name,
applies,
effect,
cost: match cost {
Some(cost) => cost
None => _state => 1.0
},
}
}
///|
/// What a plan is for: a test for "done", and an estimate of how far away that is.
pub(all) struct GoapGoal[S] {
reached : (S) -> Bool
estimate : (S) -> Double
}
///|
/// A goal with no estimate beyond "zero when reached" — Dijkstra's search instead of A*.
pub fn[S] GoapGoal::new(
reached~ : (S) -> Bool,
estimate? : (S) -> Double,
) -> GoapGoal[S] {
{
reached,
estimate: match estimate {
Some(estimate) => estimate
None => state => if reached(state) { 0.0 } else { 1.0 }
},
}
}
///|
/// The least-cost sequence of action names that reaches `goal` from `start`, or `None` when no
/// sequence does.
///
/// The search is A* over the state space: the frontier is ordered by the cost so far plus the
/// goal's estimate, and a state reached more cheaply replaces the one recorded. A state is keyed
/// by the value itself, so the state type has to be comparable — for a world state that means a
/// record of flags or a small map, not a mutable object.
pub fn[S : Eq + Hash] search(
actions : Array[GoapAction[S]],
start : S,
goal : GoapGoal[S],
) -> Array[String]? {
let far_away = 1.0e18
let so_far : Map[S, Double] = Map([])
let through : Map[S, Double] = Map([])
let previous : Map[S, (S, String)] = Map([])
let frontier : Array[S] = [start]
so_far[start] = 0.0
through[start] = (goal.estimate)(start)
while frontier.length() > 0 {
let mut best = 0
let mut index = 1
while index < frontier.length() {
if through.get(frontier[index]).unwrap_or(far_away) <
through.get(frontier[best]).unwrap_or(far_away) {
best = index
}
index = index + 1
}
let current = frontier[best]
frontier.swap(best, frontier.length() - 1)
frontier.unsafe_pop() |> ignore
if (goal.reached)(current) {
let names : Array[String] = []
let mut node = current
while previous.get(node) is Some((from, name)) {
names.push(name)
node = from
}
return Some(names.rev())
}
for action in actions {
if !(action.applies)(current) {
continue
}
let next = (action.effect)(current)
let candidate = so_far.get(current).unwrap_or(far_away) +
(action.cost)(current)
if candidate < so_far.get(next).unwrap_or(far_away) {
so_far[next] = candidate
through[next] = candidate + (goal.estimate)(next)
previous[next] = (current, action.name)
frontier.push(next)
}
}
}
None
}