Moving AI Lab

EPCG

Exhaustive Procedural Content Generation (EPCG) describes approaches for generating procedural content where all possible content is methodically generated and evaluated. Algorithms that are capable of methodically generating all content, but that choose to to skip some content are semi-exhaustive.

EPCG can easily be built on top of combinatorial algorithms. That is, once you know exactly how many possible states there are, you can usually use a mix of combinations/permutations to generate/index all possbile content.

EPCG is defined by:

• Evaluator - Evaluates the utility of a given state
• Generator - Enumerations all possible states

Although there are many ways to enumerate states, for our purposes generator often requires:

• A ranking function rank(s) -> hash, which converts a state into a hash or index.
• A unranking function unrank(hash) -> s, which convers a hash or index into a state.
• A maxRank() function which provides the maximum valid index/hash for the state space.

Research projects related to EPCG:

• Search and Game Design
• The Witness levels (static)
• The Witness Interactive levels (single levels)
• The Witness Interactive levels (simultaneous levels)
• Snakebird
• Hexagon Tangram

---

Sample code for generating combinations can be found here. This code is free to use and re-distribute.

The following function is an example that uses EPCG to generate puzzles for The Witness using the linked combinatorial code.

void ExamineMustCross(int count)
{
    Timer t;
    t.StartTimer();
    std::vector<WitnessState<puzzleWidth, puzzleHeight>> allSolutions;
    GetAllSolutions(allSolutions);

    uint64_t minCount = allSolutions.size();
    int *items = new int[count];
    Combinations<w.GetNumMustCrossConstraints()> c;


    Witness<puzzleWidth, puzzleHeight> w;
    WitnessState<puzzleWidth, puzzleHeight> s;

    uint64_t maxRank = c.MaxRank(count);
    for (uint64_t n = 0; n < maxRank; n++)
    {
        if (0 == n%50000)
            printf("%llu of %llu\n", n, maxRank);
        c.Unrank(n, items, count);
        for (int x = 0; x < count; x++)
        {
            w.SetMustCrossConstraint(items[x]);
        }

        int pathLen = 0;
        int result = CountSolutions(w, allSolutions, pathLen, minCount+1);
        if (result > minSolutions)
        {
            // ignore
        }
        else if (result < minCount && result > 0)
        {
            minCount = result;
            best.clear();
            best.push_back(n);
        }
        else if (result == minCount)
        {
            best.push_back(n);
        }

        for (int x = 0; x < count; x++)
        {
            w.ClearMustCrossConstraint(items[x]);
        }
    }

    printf("\n%lu boards with %llu solutions; %1.2fs elapsed\n", best.size(), minCount, t.EndTimer());
    if (best.size() > 0)
    {
        currBoard = 0;
        Load(currBoard, count, 0);
    }

    delete [] items;
}