Friday, November 4, 2016

Random Number God - Introducing A.I. into P.C.G.

In all cases of Procedural Content Generation (P.C.G.) that I have come across, the use of random numbers is ubiquitous.  I believe that this lies at the core of the 'sameness' issue of P.C.G, and can be significantly mitigated by the use of artificial intelligence techniques.

Consider the difference between a sequence of random numbers and a sequence of numbers following a mathematical pattern.   This is the same as the difference between a random content generator and a smart one.

A common algorithm in A.I. is to create a tree of possible successive choices that it could make, and then choose the sequence of choices with the best outcome.  A brute force approach to this algorithm is generally extremely intensive in processing and memory, so the depth of the tree is usually artificially limited and heuristics are used to focus processing on the more promising choices.

However, for the purposes of P.C.G, the A.I. doesn't need to be particularly smart; even a weak A.I. can do better than just making random choices.  If one limits the A.I. to thinking one move ahead, one could easily upgrade an existing P.C.G. algorithm to include A.I. features.

To demonstrate, view this piece of pseudo-code:
feature = chooseRandomFeature();

The above will be found in many places in even the simplest P.C.G. algorithms.  Replace it with:

for each (feature in possibleFeatures)
    value = evaluateContent();

    if (value > currentBestValue)
        currentBestValue = value;
        currentBestFeature = feature;


This is of course still slower and using more memory than a random number generator, but will already give more pleasant results.  And this is only the beginning!

If one has the processing to spare, one could upgrade the above algorithm to think two moves ahead: generate two features before evaluating the content, and then apply only the first of these two.

In a P.C.G. algorithm that generates more than one kind of feature, there will be more than one of the above replacements, and hence, more than one A.I.  To improve the results even more, one could interleave the actions of the various A.I.s; making them take turns.  With judicious placement of the various evaluation functions and reversions one could even make the A.I.s predict what the others will do and then compete or cooperate as necessary.

If A.I. is adopted widely into P.C.G, I see a bright future for computer games.  Carmack's statement that P.C.G. is merely a very lossy compression algorithm will no longer be true.

No comments:

Post a Comment