Three Hundred :: Mechanic #161

Squidi.net Sites: Webcomics | Three Hundred Mechanics | Three Hundred Prototypes

Three Hundred

- Index Page

- About...

- By Year

Collections

- Comp-Grid

- Procedural

- Tactics

- Tiny Crawl

- Misc

Mechanic #161

Mechanic #161 - PGC: Keyword Sets

Posted: Oct 12, 2012

Use sets made up of keywords in order to narrow down possibilities using a simple notation.

Keyword Sets

While I was looking through Blind Mapmaker articles to see what needed to be moved over to the Three Hundred, I realized that two upcoming entries I wanted to write both depended on keyword sets. I figured that, while a simple construct, it would be beneficial to give it an entry of its own to create a reference point for further discussion.

Sets are a surprisingly important part of the procedural generation ideas I come up with. If you think of a set as a group of all the valid choices, using unions, complements, and intersections, you can narrow down your valid choices to a very specific subset. This is easily described using a succinct notation, and due to sets typically being implemented as hash tables, relatively speedy.

Fig 161.1 - MALE + RICH.

Keyword sets is a way identifying properties of elements using a list of keywords and then using those keywords to create a set of possibilities. For instance, if you had keywords for MALE, FEMALE, OTHER, BEAUTIFUL, UGLY, MEAN, NICE, RICH, and POOR, you'd be able to describe a set of every element that is both MALE and RICH by taking the intersection of the MALE set and the RICH set. Similarly, you can just as easily find a set of every element that is RICH and Not FEMALE (MALE + OTHER).

This makes it possible to declare relationships between objects implicitly (not hard coded). As far as procedural generation is concerned, this means that you can add/remove/change the pool of elements easily. In other words, if you drop a few NPCs into the game, they'll automatically be incorporated into new random dungeons without you having to do a thing.

Defining Keyword Sets

The way this works is simple. Each object that you want to track will have a group of keywords associated with it. Then you create set operations based on those keywords in order to declare the specific set you are interested in.

I've adopted a somewhat bastardized S-expression style call, personally. Here's the example from above:

(intersectSet (keyword-set RICH) (keyword-set MALE))

To make things a little easier to parse, I've designated a sort of shorthand for set declarations, like this:

[RICH MALE]

Basically, the brackets represent a intersectSet call, with the identifiers within it being shorthand for the set based on that keyword. This means that the set returned will be the elements which contain all the specified keywords. You can perform further operations on the set returned:

(unionSet [RICH MALE] [BEAUTIFUL])

This will return a set which contains all the BEAUTIFUL people and all the RICH MALE people who aren't beautiful.

Sometimes, you want to create the intersection of a set of objects which do not contain a keyword. This is included in the shorthand with the programming-like '!' operator, like so:

[RICH MALE !BEAUTIFUL]

This will return all the RICH, MALE elements that do not have the BEAUTIFUL keyword. The ! operator basically returns the set of all elements with the set of elements with the specified keyword subtracted. Or, to put it another way:

[!BEAUTIFUL] == (subtractFromSet [ALL] [BEAUTIFUL])

Implementing Keyword Sets

Implementation is rather simple in practice. You need some sort of element manager that keeps track of all the elements, along with the sets of elements. When you add a new element to the manager:

1. Add new element to ALL set.

2. For each keyword associated with element.

2.1 Acquire set for keyword. If set does not exist, create one.
2.2 Add element to keyword set.

That's pretty much it. When I've implemented this approach, I used an associative array using the keyword string as key to keep the various sets. It should also be noted that this will only work if the elements are immutable, as changing/adding/removing keywords from elements would invalidate the integrity of whatever keyword sets they are put in.

Now that you have the sets, just break down each S-expression into a series of operations. Presumably, you have created a tree during the parsing phase, but if that proves beyond the scope of your project, you can simply use reverse polish notation by reversing the order of calls:

(unionSet [RICH MALE] [BEAUTIFUL])

Can be turned into:

[BEAUTIFUL] [RICH MALE] unionSet

Then you can evaluate each call linearly, as you come to it by storing the results of each call on a simple stack. If this looks weird to you, go spend some quality time with FORTH and prepare to be amazed.