0
$\begingroup$

In the paper Using Cyclic Scheduling to Generate Believable Behavior in Games, Richard Zhao and Duane Szafron describe a tool that is able to generate schedules for NPCs.

The tool

The tool offers a visual interface were the designer can set several constraints.

  1. The designer can set an objective for an specific hour in the timeline;

  2. The designer can set the number of hours required by an specific objective. Also it's possible to add a transitional hour;

  3. The designer can separate the objective hours into groups;

  4. The designer can set several roles for each objective;

  5. The designer can set the probability for each role.

  6. Based on the constraints set, the tool generates the schedule

The algorithm

To generate the schedule, it is used a greedy depth-first search algorithm, describe in pseudocode as the following:

schedule = []
itemList = sort(itemList) // longest objective block first
CyclicSchedule(itemList)

bool CyclicSchedule(itemList)
    if itemList is empty, return true
    item = pop(itemList)
    for each location L in schedule
        if satisfiable(L, item)
            schedule[L] = item
            returnValue = CyclicSchedule(itemList)
            if (returnValue == true)
                return true
            else
                schedule[L] = ""
    return false

bool satisfiable(location L, obj block Item)
    if (length of obj block > available obj blocks at L)
        return false
    else if (non-consecutive obj block requirement is violated)
        return false
    else if (currently assigned obj hours > specified max obj hours)
        return false
    else
        return true
    

My question

For studying purpouse, I'm trying to reproduce this algorithm in JavaScript, but I'm completely stucked... here's what I managed until now:

var schedule = [];
var itemList = [];

cyclicSchedule(itemList);

function cyclicSchedule(itemList) {
    if (itemList.length == 0) {
        return true;
    }        

    var item = itemList.pop();

    for (const l of schedule) {
        if (satisfiable(l, item)) {
            schedule[l] = item;
            returnValue = cyclicSchedule(itemList);
            if (returnValue) {
                return true;
            }   
            else {
                schedule[l] = '';
            }
        }
    }

    return false
}

function satisfiable(l, item) {
    return true;
}

Does anyone know how can implement it using JavaScript?

Thanks!

$\endgroup$
3
  • $\begingroup$ Please, ask one question per post. If you have multiple questions, ask each of them in their separate post. But, more importantly, put your main specific question in the title. "I need help understanding Cyclic Scheduling Tool's algorithm" is not a question. If you're not able to do it, it's a good sign that this post has several problems, i.e. it's too broad. So, I suggest that you try to focus on a single problem at a time. $\endgroup$
    – nbro
    Dec 28 '20 at 0:32
  • $\begingroup$ @nbro, post updated according to suggestions. Thanks for the orientation. $\endgroup$
    – Viana
    Dec 28 '20 at 11:22
  • $\begingroup$ But still, what exactly is your problem? Where do you get stuck? Is there an error? $\endgroup$
    – Kokodoko
    Aug 3 at 10:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.