First Entry: I acquire a Destiny, or it, me
For several months now, Bill and I have been having lunches together and going on one-hour walks afterward. During these walks, our discussion has frequently examined various aspects of his dream project: a game engine sufficiently rich and robust that the non-player characters are indistinguishable from the player characters (NPCs are characters managed by the game engine, rather than by a human player). The conversation has turned to the representation of what an NPC can be said to "know", how to generate conversation so that exchange of knowledge is believable, the nature of what constitutes an event, and considerations arising from the "observability" of that event by NPCs. I seem to have become a partner in the project by virtue of being a good and intelligent sounding board.
Recently, the subject of how NPCs should plan their paths through their world came up, both in a "dungeon" setting (i.e. atrifically constructed, lots of square corners, and with obstacles that are absolute in the sense that no progress can be made through them) and in the larger setting of a planetary surface (natural, lots of rounded or fractal shapes, with continuous obstacles [many kinds of terrain and other environmental factors that affect travel in continuously-variable ways which might be different for different modes of travel]).
Bill explained some current algorithms, apparently gleaned from the October / November 1996 issue of Game Developer magazine.
Dijkstra's algorithm starts from the initial point, then constructs a graph by attaching to that point all its neightboring points. The expansion of the graph procedes stepwise. At each step, the point chosen to expansion is the leaf node with the lowest accumulated cost. If that point was the goal, then the path to that point represents the minimum-cost path to the goal.
The A-Star algorithm is a modification of Dijkstra's in which the determination of which node to expand is based on the total of the cumulative cost and the estimated cost from that point to the goal. The extimated cost essentially indicates which paths are most likely to be in the right direction. If the estimate is zero, the algorithm is Dijkstra's. If the estimate is always lower than the actual cost, then A-Star is guaranteed to find the minimum-cost path (if there is one), and will usually find it faster than Dijkstra's. If the estimate is higher than the actual cost, then A-Star will be "reluctant" to explore possibilities that are off of a direct path (direct in estimate space). In this latter case, the path found may be more direct, but is no longer guaranteed to be the least-cost path.
The first thing that struck me about these pathfinding algorithms was the enormous number of paths that they evaluated, whereas the human eye-mind combination quickly established which paths were most promising, and usually correctly identified a shortest-distance path after considering only a few possibilities.
I examined various ways of getting "over-all" cost from 2 x 2 and 3 x 3 aggregations of map grid locations. None were satisfactory. In particular, I wanted something that would preserve the low cost of traveling on a road (for example) even if surrounded by difficult terrain.
The notion of directional cost seemed promising: East-West travel might be difficult through a map region, but North-South travel might be significantly easier because of the availability of a road in that direction. For example:
NS cost = min ( A, B ) + min ( C, D )
EW cost = min ( A, C ) + min ( B, D )
NS cost could be minimum cost from any of (A, B, C) to any of (G, H, I), or could restrict to pass through the middle cell.
A fundamental problem is that if the technique preserves the minimum possible cost, it can not also preserve maximum cost. In other words, if taken at a sufficiently coarse scale, the barriers (mountain ranges, walls of rooms, etc.) tend to disappear, while a pass through the mountains can end up replacing the entire mountain range.
It also became clear that to deal efficiently with a typical "dungeon" setting (where each grid location is either entirely passable or an insurmountable barrier, e.g. stone wall) would require different path finding algorithms than those needed for a typical "surface world" setting ( where terrain provides a continuously-variable degree of passability).
Bill had several ideas about dungeon path finding, so I decided to tackle the surface world problem.
I decided that to preserve directional cost more accurately, I needed the cost from any side of the region to any other side: not just NS and EW, but also NE, NW, SE, and SW. This gave an absurd result for 2 x 2 regions: 6 numbers replaced 4. Even 6 numbers for 9 (3 x 3 region) didn't seem worth the effort. 4 x 4 regions looked promising, though. NS travel cost can be defined to be the minimum cost through the region from any of ABCD to any of MNOP. For diagonals, I had to eliminate the corners as being unrepresentative of diagonal travel through the region, so SW (for example) was the minimum cost path from any of AEI to any of NOP. It may readily be seen that this face- (or side-) oriented notion has an equivalent body-centered form.
Graph class & Cartesian vector class
Bill thinks that maps will best be implemented using some form of a directed graph, which he just happens to have a C++ implementation of. I have gotten to the point where I need some sort of testbed for trying out path finding and map abstraction ideas. I must also admit that the question of how to design a class to represent map information is becomming interesting to me.
Bill gave me a copy of his graph code to get me started on a map class. It seems clean and efficient, but is somewhat flawed (to modern eyes) in that it is based on some personal / proprietary array classes, vectors, and queues. Since the time it was written, those constructs have been supplied by the Standard Template Library (STL), now a part of the C++ standard. Accordingly, I have not leapt right into the map problem, but have studied Bill's code and translated it to use the STL container classes and algorithms.
Now that I have an STL-based graph class, my thoughts have turned to what sort of information to keep with the graph nodes (map cells) and the graph arcs (connections of paths between map cells). For the nodes, terrain type and location seem obvious choices, though location does not itself have any obvious universal representation. (To keep things general, I have derived a Cartesian Vector class from the STL vector, with operators and functions to allow convenient vector math including several magnitude functions: root sum of squares, mailman distance, and the "radar" approximation of the larger component plus on-half of the smaller.
(see Feigenbaum for better list)
Labeling of inference paths or knowledge items
|T||true from direct inference|
|t||true from 'default' inference (i.e. defeasible)|
|F||false from direct inference|
|f||false from 'default' inference (i.e. defeasible)|
Tweety -- (1) T --> bird -- (0.7) t --\ flying -- (0.9) f--> afraid of heights Fred -- (1) T --> ostrich -- (1) F --/
Treating all links similarly, Fred->flying is either .7 or -1. Treating links defeasibly, i.e. with non-defeaasible links overriding defeasible links, Fred->flying is -1.
Combined with some sort of certainty factor, could use -1 = false, 0 = no certainty, 1 = true and a defeasibility marker. (Pretty standard, and works well with neural networks, too.)
In general, any reasoning chain that relies on a defeasible link is itself defeasible.
Because any knowledge item may be arrived at via multiple paths (chains of reasoning), a knowledge item may have a variety of possibly inconsistent (i.e. contradictory) markers both defeasible and not.
Because paths use knowledge items as their starting points, any path might have multiple labels as well.
In general, one might prefer a non-defeasible label over a defeasible one. On the other hand, if the non-defeasible label is very weak then the use of the defeasible label may lead to more useful conclusions.
In general, one can aggregate labels of one kind (all defeasible or all non-defeasible) by selecting the label which is most certain (has greatest absolute value).
Object layer -- Layer with list of objects and entities present at each map node. In the case of bagged objects, only the outer bag will appear in the object layer.
List of objects in proximity (proximity list) -- Return a list of all objects within a given range of a given location. For use with spells, explosions, noises, etc.
Hot zones -- Object entering or leaving a map node which has been designated this way will generate an event. Event types and parameters may be established when the zone is established and modified thereafter. Hot zones can be established and rescinded on the fly as the game progresses.
Collision layer -- Certain objects or entities are not permitted to co-locate, and an attempt by one to occupy the space of another is something that generates an event. Also useful in dungeon path planning, as walls can be put in the collision layer, thus preventing entities from trying to go through them.
Distance functions -- should depend on the connectivity of the map: mailman metric for 4-connect, special function for 8-connect, etc.
Mediate radial effects -- sound, light, explosion. Listen for events (or are called directly to manifest the effect), use the map to check for possible observers, use observer detection thresholds in conjunction with information about the power of the event, and range or path information (from map?) to determine whether observer detects event and at what power level the effect reaches the observer. Or, threshold application could be left to the observer. As a practical modification, an effect can have a limit (w/ some relation to power) beyond which the map need not be searched for observers.
Stationary sound sources could have an area of effect. Any observer within the area of effect observes the effect. Area of effect could be implemented as a thin circular (as modified by walls, etc.) hot zone.
Sounds have objects as sources. Stationary sound sources that emit continuous or intermittent sounds can be specially processed (e.g. compute area of effect and keep it for later use).
Quests are entities that attempt to get hosts (player characters) to perform some task (i.e. to bring about some event). Quests need to be able to plan, and also need some evaluation function to indicate whether its host(s) are making sufficiently rapid progress toward accomplishing the task. In addition, quests (somewhat like a semi-divine parasite) have the ability to affect their host's characteristics, environment and / or experiences to reward or punish the host for making or not making progress toward the quest's goals.
Has knowledge of a current time
Has an event queue (priority queue by time)
Has a registry of pre-event listeners
Has a registry of post-event listeners
Could have a list of cancelled events. Don't want to search through event queue to cancel events, so just check against the cancelled event list when an event is popped from the event queue.
If event queue not empty look at next event current time advances to event time (or wait for current time to catch up, i.e. don't process an event before its time) if event not in cancelled event list check through list of pre-event listeners for the type of event in most-recently- entered-first order, processing pre-event actions (treat id as just another property) tell event to process itself may change object attributes, create events or event listeners, etc. notify affected entities and objects (any observers?) (notification is by methods built into entity and object base classes) process all post-event listeners listening for event of same id process all post-event listeners listening for event of same type
|Event Property List||Listener Property Matching List|
|name or id||name or id|
|value||value or range of values or disjunction of conjunctions (with negation) of value or value range expressions|
Caster generates begin_cast event for the current time.
Caster schedules end_cast event according to appropriate casting duration.
When caster receives end_cast event, caster creates spell object. On instantiation, spell object schedules spell_trigger event with itself as post-event id listener or registers itself as listener for external triggering event.
If waiting for external trigger event, upon receiving such an event, spell object schedules spell_trigger event and fills in missing properties if any (e.g. target location, if tied to an object id).
When it receives spell_trigger event, spell object processes spell effects, incl. scheduling events for effects (explosions, etc.), and object attribute modifications. Entities or objects affected by effects are notified via methods built into the entity and object base classes, incl. ChangeOfStats, etc.
These spell attributes are available to listeners in the begin_cast event.
A possible casting limitation is that target must be willing.
When attribute changes over a duration, spell needs to schedule update_spell_effect events.
Complexity has relation to casting time, in conjunction with power.
cast time is proportional to power / complexity
User holds down mouse button (or similar interface element) to build spell power. Power (bright blue line in diagram) builds at rate determined by spell complexity until released by user, cancelled by user, or max. power (9 o'clock in diagram) attained. The user may release as soon as the desired power level is attained to cast the spell at that power level.
When max. power attained, hold for a few ticks, then oscillate power between max. and zero (6 o'clock in diagram) at fixed rate (no longer dependent on complexity). In this phase of the interaction, the user may choose to release at any power level; if released below the minimum power (boundary between orange and yellow areas in diagram) the spell casting will be cancelled.
If a technology sufficiently advanced implies that the technology is not distinguishable from magic, then a technology distinguishable from magic implies that the technology is not sufficiently advanced.
Event managers assigned to (possibly overlapping) areas and/or contexts, e.g. town, surrounds, "dungeon". Event managers need not be entirely in synch.; could be a day ahead of or behind other event regions. In multiprocessor environment, could assign processors to event managers and their regions.
Explanation of a sequence of events. Stories can mutate, propagate, and virtually acquire a life of their own.
State description of a locale. Like key frames in an animation; a sequence of key frames can be used to establish way-points for the plot developent. Planners could then be applied to plan the events that would take the action from one scene to the next, and may have to re-plan to accommodate unpredicted player activities.
Back to the Destiny documents
Onward to the Next Folio of the Notebook