newstalk

newstalk

:: like newspeak, minus the ungood bits. ::

newstalk RSS Feed
 
 
 
 

Using tags for metadata and lookup.

This is a part of "Free Sky: Objects in Space".

Series contents:

  1. Free Sky: Objects in Space
  2. Enabling data-driven object construction.
  3. Building for persistence at a fundamental level.
  4. Using tags for metadata and lookup.

With my object system prototype, I wanted to explore the possibilities of tagging. An article in AI Game Programming Wisdom 2 (”A Flexible Tagging System for AI Resource Selection”, by Paul Tozor) spurred my imagination: the article poses the scenario of a first-person sneaker. The player sneaks up on two guards and overhears them complaining about the cold. The straightforward way to program this scenario is to assign each guard instance a list of sound files to play through, either randomly or in sequence. However, any time you want to add another sound file to the possibilities, you have to edit that guard’s list, and the lists of any other guards which need that sound file. Mr. Tozor proposes another way.

A tagging solution assigns tag metadata (i.e. descriptive words) to each sound file. Then the level designer assigns each guard a set of tags (quip, complaint, cold, night) to use to select an appropriate sound file. The guard, when preparing its speech action, then queries a database to find a sound files that best match its tag criteria, favoring resources that haven’t been used recently. To add a new sound file to the guard’s repertoire, simply add it to the tag database with the appropriate tags. Voila: specific sound files are decoupled from guard instances.

I propose to extend this technique to the entire object system, not only in order to ease resource selection, but to help enable my grandiose plans for dynamic plot generation. (More on than in another series.) My real hope is to foster “emergent” behaviors by programming game entities to build object queries based on context. Of course, the whole thing could explode in combinatoric nuttiness, but I suspect (and Chris Crawford might back me up on this) that this is just a tuning problem.

It turns out that this sort of tagging system is fairly simple to implement. You just need a IOBTree (tags get assigned integer IDs) that maps a tag to an OOSet of game objects. Looking up objects identified by a single tag is a breeze. Selection by multiple tags isn’t much harder: find the set union of the results of single tag queries. This is all built in to ZODB’s BTree package.

The difficulty came with implementing a “best match” multiple tag selection scheme. Mr. Tozor’s description of his tag selection algorithm was immensely helpful, though I found it maddeningly vague. It works like this:

  1. Begin with the set of all available resources.

  2. Rule out any resources that do not include all of the required tags in the query set.

  3. Rank the remaining resources in terms of those that match the greatest number of optional tags.

  4. Rank the remaining resources from step 3 in terms of those with the least number of additional tags (that is, tags on the resource that are not specified as required or optional tags in the query).

  5. If more than one resource is ranked highest at this point, select the least recently used resource. If there is more than one resource that has never been used, select Randomly from among the highest-ranked resources.

My prototype implementation looks like this (with some sanity assertions removed):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
    def getObjectByTags(self, required=(), optional=(), unwanted=()):
        required = set(required)
        optional = set(optional)
 
	# Get all objects matching the required tags
        objects = [self.getObject(oid) for oid in self.queryTagsIntersectionByString(required)]
 
        rankings = []
        for obj in objects:
            rank = 0
            for tag in obj.tags:
                if tag in unwanted:
                    rank -= 50
                if tag in optional:
                    rank += 1
                else:
                    if tag not in required:
                        rank -= 1
            rankings.append(rank)
        ranks_objs = zip(rankings, objects)
        ranks_objs.sort(reverse=True)
        try:
            toprank = ranks_objs[0][0]
        except IndexError:
            raise ObjectError, "No object matches req: %s, opt: %s" \
                % (required, optional)
        how_many = rankings.count(toprank)
        top_contenders = [robj[1] for robj in ranks_objs[:how_many]]
 
        if how_many == 1:
            winner = top_contenders[0]
        else:
            by_access = [(cntndr.last_picked, cntndr) for cntndr in top_contenders]
            by_access.sort()
            winner = by_access[0][1]
 
        winner.last_picked = time.time()
 
        return winner

That probably needs to be cleaned up an optimized, but it works.

While it isn’t SQL, this provides a tidy lookup interface for selecting objects, so long as you plan ahead by assigning the critical tags. This may be the hardest part, actually: assigning good tags. Too many tags will bloat the system. Too few and you lose granularity in using the best-match algorithm.

Possibly related:

    None Found

Like what you see?

Don't forget to subscribe via RSS or email to receive updates when I post new material. Thanks!

Comments are closed.

Feedback: I'd love to hear what you have to say!
  1. I don't have time to manage or moderate a live comments forum, but I'd love to hear from you.
  2. (required)
  3. (valid email required)
 

cforms contact form by delicious:days


subscribe