Consider a game about obtaining items. For each item, obtaining it requires having already obtained its set of prerequisite items. This kind of mechanism is seen, for example, in games in which gaining an ability (skill, technology) requires first gaining other abilities. Or completing some quests opens up other quests.
We consider randomly generating such a collection of prerequisite dependencies. First, (totally) order the items. For each item, select a subset of items before it in the total order as the prerequisites. Some items might have no prerequisites (so they are easy to obtain); some may have many. All the prerequisites in a set must be satisfied in order to obtain the item (Boolean conjunction).
At this point, because we started with a total ordering, there are no cycles among dependencies, so every item is reachable. It could be drawn as a directed acyclic graph, but that representation becomes less useful for what we are doing next. (If all the prerequisite sets contain exactly one item (except the root, which has an empty prerequisite set), then that graph would be a tree. If every prerequisite set has zero or one items, then the graph would be a forest.)
Next, for every item, give it zero or more alternative prerequisite sets. Each alternative prerequisite set is an alternate way (Boolean disjunction) of satisfying the prerequisites for getting the item. This resembles Disjunctive Normal Form in Boolean logic (sum of products), except there are no negated literals (never a penalty for having an item). These alternative prerequisites can include items coming after the item in the total ordering established above. It is OK to create cycles because we've previously ensured an acyclic way to reach every item.
To simplify computation, restrict the possible prerequisite items of a given item to within a window (forward and backward) of the given item in the total ordering. Items with no prerequisites must be within the window around the beginning of the total ordering. This allows answering the question "given the items I currently have, what can I immediately access?" without having to search too far forward in the total ordering. This restriction allows the number of items to be infinite, with prerequisites generated on the fly as they fall within the windows of items you already have. The prerequisites for an item can be generated using a pseudorandom number generator seeded by the item's unique identifier. (An easy such an identifier would be its number in the total ordering.) Despite an infinite number of items, generating and doing queries against such a seemingly complicated infinite collection of prerequisites requires very little space, probably logarithmic. (However, keeping track of the items a player has already obtained requires n log n space.) The factors of log n are for the size of each item's unique identifier or label.
What should be the probability distribution of the number items in a prerequisite set? What should be the distribution of the number of alternative prerequisite sets? Although the items for the alternate prerequisite sets can be from anywhere within an item's window, what should be the distribution within the window from which prerequisites are selected? Perhaps items nearer in the total ordering are required more frequently. Similarly, what should be the distribution of prerequisites in each item's first prerequisite set, the one which obeys the total ordering?
Avoid creating impossible alternative prerequisite sets. Avoid creating prerequisite sets which are monotonically more difficult than a different prerequisite set for the item; that is, satisfying the more difficult set necessarily satisfies the easier one. Without introducing another constraint, testing for these situations might be difficult or impossible because of paths of arbitrary length among infinite items: go forward then back in the total ordering.
It is an abstract maze (perhaps the goal is to reach a certain item), but there isn't a need for the kind of backtracking seen in solving SAT in CNF with negated literals. The penalty for choosing to get the "wrong" item is resources wasted making no progress toward the goal. What choices to the above questions tend to make it an entertaining maze?
EmoticonEmoticon