Hosted Pages



Pathfinding Benchmarks



Grid-Based Path Planning Competition



AAAI 2019 Student Activities


AAAI 2017 Job Fair


AAAI 2017 Workshop on what's next for AI in games


Archived Pages


AAAI16 Student Activities

AAAI15 Student Activities

MAPF 2012 Workshop

AIIDE 2011

GIGA 2011

SoCS 2010

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:

Although there are many ways to enumerate states, for our purposes generator often requires: 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;
}


© Nathan Sturtevant, All rights reserved.