Goal-oriented Action Planning is an AI technique used to let computer-controlled actors make realistic decisions when placed in a specific environment.

recursive_goap.lua

function plan_action(model, depth, action_index, best_action, best_value)
    assert(type(model) == "table", "Model must be a table. Got "..type(model).." instead.")
    depth = type(depth) == "number" and depth or 1
    action_index = type(action_index) == "number" and action_index or 1
    --best_action doesn't need to be initialized; nil is a valid result.
    best_value = type(best_value) == "number" and best_value or model:evaluate()
    if depth > 0 then
        local next_action = model:get_action(action_index)
        if next_action then
            -- The only part that isn't tail-recursive, and at least we're
            -- putting the stack to good use tracing our steps.
            local sub_action, next_value = plan_action(model:apply_action(next_action), depth-1)
            if next_value < best_value then
                return plan_action(model, depth, action_index+1, next_action, next_value)
            end
            return plan_action(model, depth, action_index+1, best_action, best_value)
        end
    end
    return best_action, best_value
end

local test_model = {
    evaluate = function(self) return 0 end,
    get_action = function(self, index)
        if index > 3 then return nil end
        print("Action:"..index)
        return "Do Stuff"
    end,
    apply_action = function(self, action) 
        print(action)
        return self 
    end,
    plan_action = plan_action
}

print (test_model:plan_action(3))