|
|
Rudolph P. Darken*, John L. Sibert**
As important as these issues are to human performance in virtual environments and the eventual acceptance of virtual environment solutions to real problems, currently, only ad hoc remedies and case studies are available for guidance.
The overall objective of our research program is to develop design principles which can be incorporated into a methodology for the design of wayfinding augmentations to virtual worlds and which will facilitate expert-like navigation performance in novice users. This paper presents an analysis of searching behaviors observed in an experiment applying real-world wayfinding and environmental design principles to the design of virtual worlds. Our intent is to show that these same principles will produce skilled wayfinding behavior(1) in virtual worlds.
Survey knowledge is map-like in nature. Accordingly, it can be acquired directly from map use. However, survey knowledge acquired from a map tends to be orientation-specific. In contrast, prolonged exposure to navigating an environment directly is more likely to result in survey knowledge which is orientation-independent.
The relative inflexibility of spatial knowledge acquired only from maps led Levine [6] to study the effect of this phenomenon on map design. He found that in order to facilitate efficient map use, the map must be congruent with the environment it represents. This is illustrated in the forward-up equivalence principle which states that the upward direction on a map (assuming it is perpendicular to the floor) must always show what is in front of the viewer.
Survey knowledge is hierarchical in nature [9]. Rather than encode the absolute positions and directions to every place encountered, fewer large, general, logically selected places (e.g. Washington, D.C.) are encoded with subnetworks of smaller, more specific places (e.g. The White House) being defined within each.
Passini [8] expands on these ideas applying them to architectural design. A space should have a basic organizational principle underlying it. For example, Manhattan's streets are organized in a grid. We use this information directly to structure spatial knowledge. Most importantly, a space must have in it a number of "places" which are easily discernible to any wayfinder. A "place" is most simply defined as a distinct, recognizable location or region of a larger space often associated with a landmark. Passini also notes that if a map is to be used, it should show the organizational principle of the space as well as the design elements described by Lynch. The observer's position must always be shown and Levine's forward-up principle must be adhered to.
The classifications of wayfinding tasks are mutually exclusive. However, they are often compounded into sequences. In cases where the navigator has general knowledge of the target's position without enough precision to find it directly, a primed search is performed to the target's general proximity followed by a naive search within that area. The opposite ordering of tasks is equally common.
Although purely naive searches are rare in the real world, in virtual worlds, spatial naivete is common in first-time explorers of a space; even the world builder. A scientist visualizing data sets may have no preconceived idea as to the shape or organization of the data. Therefore, wayfinding aids must support both exhaustive and non-exhaustive searches and must facilitate survey knowledge acquisition.
An optimal exhaustive search requires that the navigator traverse the entire space once (in the worst case). To facilitate this, there must be a method of organizing the space to eliminate multiple passes or skipping entire areas. A primed search, on the other hand, requires only that the navigator know a path to the target. If movement is unrestricted (as it often is in virtual worlds), the navigator need only know the direction and distance to the target. Minimal survey knowledge is required relating the navigator's present position to the target's position. Lastly, exploration is the basic task of spatial comprehension. Its objective is to develop survey knowledge. Maps can be used and, similarly to naive searches, the space should be explicitly organized.
These requirements lead to the conclusion that survey knowledge is the key to successful wayfinding in any environment. Based on the literature previously introduced, we present the following set of design principles for wayfinding augmentations to virtual worlds.
Although map use is not an appropriate tool for every situation, the ability to quickly extract spatial knowledge directly from a map often makes it a powerful navigation aid. Ideally, this knowledge should be flexible, as if the observer had obtained it from direct experience. Therefore, map design principles are intended to present spatial information in such a way as to produce a flexible, orientation-independent representation of the environment. The basic principles are:
Note that the two latter principles are difficult to apply in the real-world when the observer is moving. In the virtual world they can be applied equally easily to a stationary or moving observer.
In order to capture the subjects' behavior we asked each subject to sketch a map [5, 7] showing the location of land forms and targets after each treatment. We asked subjects to think aloud and recorded each treatment with video and audio tape. Finally, we sampled (once per second) the path of each subject through each treatment and superimposed it on a map of the environment (See below, Figure 4). In addition to visual comparison to the actual environment, we analyzed the sketch maps using a metric incorporating target distances and directions and land mass shapes developed for this particular purpose [3]. We analyzed the audio and video tape using a verbal protocol analysis [1] and captured observed behavior in the same notation used in CMN-GOMS [2].(2)
The viewpoint was restricted to movement above the terrain but below a maximum altitude of 400 meters. This is necessary to allow some vertical movement without allowing the subject to gain enough altitude to be able to look down on the entire environment from a "bird's eye view." Movement was constrained horizontally so that when an edge was encountered, there would be no distinguishable features by which to navigate. Contact with the virtual edge resulted in an audible "click" cue combined with immediate clamping of the viewpoint's movement at the point of contact.
The radial grid used in the grid treatment was constructed from a red center post and four different colored posts in each cardinal direction. The outer posts each have a "flag" which points inward toward the red inner post. There are three concentric rings marking range. The red, yellow, and white rings are placed at 10000m, 20000m, and 40000m radius respectively. The outer posts are placed on the white ring. Black radial lines are placed every 45 degrees and extend beyond the white ring.
The map used in the map treatment was identical to the actual environment except that the blue sea texture was replaced by a grey background for contrast with the environment. A red sphere was moved along the map surface to identify the viewpoint position during navigation. The map is presented flat and in the same orientation as the environment itself in conformance to the map principles. The map was placed relative to the viewpoint during movement such that it was visible at all times. The intent was for subjects to feel that the map was in front of their chest.
The map/grid treatment was implemented by placing the grid over the map and the world simultaneously. In the examples in Figure 1, the viewpoint in each case is near the home target facing the center of the world. The target is identified as target zero with a white numbered cube directly above it. The red center post is shown in both the grid and map/grid treatments.
This experiment is intended to study the validity of the design principles and spatial behaviors associated with environmental information rather than the effectiveness of these specific environmental cues. Although we have chosen representative cues for each treatment that adhere to the design principles, there are certainly many other ways to provide the same information.
The treatments were implemented on a Silicon Graphics Onyx Reality Engine 2 workstation. The only peripheral device used was a Fakespace Inc. BOOM3C display and tracker. The BOOM3C is a full color, high resolution (1280x1024 pixels) CRT-based display mounted on a counter-balanced mechanical arm. The display is held to the eyes with one hand which controls a single button and a thumb-operated joystick. The position and orientation of the head are tracked through the mechanical arm. Motion is controlled via an acceleration metaphor by which the subject accelerates forward in the virtual world by pushing up on the joystick and backward by pulling down. Velocity is bounded by a maximum speed of approximately Mach 3 (993m/s or 2223mph). Movement is always in the direction of view. The subject may stop at any time by pushing the button on the hand controller.
The wayfinding task performed for all treatments required the subject to execute five naive searches followed by one primed search. The subject starts at the home target and proceeds to search the environment for each of the five ships which have been numbered and shown to the subject in the instructions. No a priori information is given as to their whereabouts. Once the last target has been located, the subject is required to return to the home target. Subjects were given as much time as needed to complete the task. However, the trial could be discontinued at the subject's request. This was allowed only in cases when either the subject felt unable to make any progress toward task completion after an extended period of time (always at least 15 minutes) or the subject became unable to continue for physical reasons(3).
During task execution, subjects were asked to "think aloud" [1] as a method of knowledge elicitation specifically aimed at understanding search strategies. Following each trial, subjects were required to draw a map of the environment in as much detail as possible. Subjects were free to sketch the environment at will starting from a blank piece of paper.
For the purpose of this study, the wayfinding tasks have been broken into their primary components (See Figure 2). Subjects must first ground themselves in the virtual world by acquiring their orientation and position. Then, they begin to undertake the explicit tasks of the five naive searches followed by one primed search. If at any time they lose their orientation or position, they must reacquire it before proceeding. Also, during task execution, actions may be taken which are specifically meant to help the subject maintain orientation and position and consequently, to develop a better cognitive representation. Finally, as targets and objects of interest are located in the world, they are explicitly placed into memory so that they may be recalled later for the map drawing exercise.
This linear description does not completely show the flow of execution. During a single task sequence, subjects may choose more than one method to achieve a goal. For example, when using a word processor, there are typically at least two ways to change the style of the selected text; either via the pull-down menu or using accelerator keys. Either method is acceptable but the subject will never execute both in a single task sequence. In the type of tasks described here, there are also several acceptable methods available to complete any task, but it is feasible to choose more than one method for any given instance. This type of reinforcing or repetitive behavior is the rule rather than the exception in this analysis. Many subjects used several strategies during any one trial as they discovered better alternatives or found their current approach ineffective. Most commonly, subjects selected a method based on intuition restricted by the cues and information currently perceived or available.
The overall goal of the task is to execute an efficient, organized search locating all five targets and afterwards, the home target. The subject must also accumulate survey knowledge in order to draw an accurate map of the environment after completion of the task. Our interest here lies in the notable differences in behavior and in search strategies based on the differences in navigation aids provided (or not provided as the case may be).
The lack of suitable orientation cues in the control treatment caused subjects to use relatively weak grounding techniques which proved to be error prone. Most subjects tried to use the orientation of the home target or the initial view direction as a default "north." This failed, however, when the subject moved away from the start position because adequate reference information was no longer available if and when disorientation occurred. Some subjects tried to use targets and land features as reference points, and attempted to infer distance and direction by moving between them. However, this method was not very successful because of the large distances between targets. One subject even created an external reference by grounding one foot in physical space. The viewpoint was easily reoriented based on the subject's body posture. However, this method was not useful in extracting positional information. Subjects most often used a dead reckoning(4) technique with the home target as a reference point to determine position. This was a difficult task considering the lack of alternative reference points throughout the environment. However, it was often the only viable alternative. During navigation, subjects would frequently retrace their recent path or move between targets to estimate distances between them.
These same techniques were also observed in the grid treatment. However, the grid markings were frequently used as the predominant reference points for distance and direction inference. The four outer posts were used as compass points with any one arbitrarily chosen as "north." Reorientation could be performed by simply returning within view of any outer post. Alternatively, subjects also used the grid markings to divide the space. The colored rings specify range from the center post. Subjects were evenly divided between those who used the posts to divide the space into quadrants and those who used the radial lines to divide the space into wedge-shaped octants. Subjects also used the grid to maintain orientation and position by determining which bounded area they were currently in. These methods were more effective because the grid represented an absolute frame of reference.
The map provides a geocentric perspective to the environment. Consequently, many of the difficulties in acquiring and maintaining orientation and position are eliminated. The map shows the shape of the space and allows for the effective use of geographical landmarks(5) and world edges as reference points. The orientation of the map itself indicates the viewpoint orientation with respect to the world. Viewpoint position is available at a glance. The addition of the grid superimposed on the map in the map/grid treatment allows methods from both the map and grid treatments to be used together.
| Spatial Memory | Naive Search | Primed Search |
| Graph | Local Search | Retrace Steps |
| Square Grid | Lawnmower | Manhattan |
| Anchor | Coastline | Direct, Landmark |
| Radial Grid | Area, Paths | Approximate, Direct |
The amorphous nature of the control treatment allowed subjects to apply any structure to the environment. The targets could be connected in the form of a graph with the targets as nodes and the paths between them as edges. A square grid structure could also be applied dividing the space into smaller regions. Most commonly, targets were represented as anchored relative to the land masses.
In the grid treatment, the graph and anchoring methods are still utilized. However, the square grid method does not coincide with the shape of the radial grid and is consequently replaced by a radial grid structure.
The map does not impose any structure on the environment beyond that of the control treatment. Accordingly, the same conceptual structures were used in the map treatment as in the control treatment. In the map/grid treatment, however, subjects were not observed to use the graph method; presumably because the grid markings and geocentric perspective provided enough reference points to make this method inferior to others.
When the grid was provided, it added two primary methods to those of the control treatment. The grid markings can be used as paths. The path trail line in Figure 4B clearly shows both the radial lines and the range rings which were used to guide the search. This was seen as a more comfortable alternative to searching open spaces. Also, the world could be divided into areas bounded by the grid lines, each to be searched sequentially.
The map allowed the search techniques of the control treatment to be executed more effectively and with optimizations. Heuristic searches were often used to initially visit places which subjects guessed would hide a target such as an inlet or bay. They can be used with any of the spatial memory representations. Also, the lawnmower method was optimized to eliminate searching over land. The addition of the grid to the map enabled combinations of methods. For example, heuristics were used to improve area searches.
The grid markings were used in one of two ways. If a post or line crossing was within view of the home target, that location was used as an approximate target from which the primed search could be completed easily. The alternative was to place the home target in the world relative to the grid and search for it directly.
When the map is used, the home target is placed relative to some predetermined geographical landmark. To relocate the target, the subject moves back to the general area and conducts a local search until successful. If the grid is added to the map, the grid markings are usually preferred over geographical landmarks for reference points.
In all treatments, dead reckoning was used extensively as a way to structure movement during a search (naive or primed). It was used frequently in the control and grid treatments but only intermittently in the map and map/grid treatments when not navigating from the map directly.
A measure of total time to complete each trial (adjusted for incomplete attempts) showed significant effects across treatments (Friedman test statistic=15.96, p<=.001)(7) indicating that subjects in the control treatment tended to execute ineffective searches and were unable to structure the space. This is further illustrated in the distance travelled during each treatment which also showed a significant effect (Friedman test statistic=17.4, p<=.001). As seen in Figure 5, subjects repeatedly traversed the same space in the control treatment. Distances and times for the grid treatment were lower than the control treatment but higher than the map and map/grid treatments. Although the grid supplies enough information to structure a search, a significant amount of effort and reinforcing actions must be executed to maintain orientation.
A ratio of the percentage of space searched to total time is a coarse indicator of search effectiveness. This ratio was shown to be significant across treatments (Friedman test statistic=13.8, p<=.005). In general, subjects were not able to coordinate an effective search in the control treatment due to disorientation. The grid significantly increased performance and ability to extract spatial information but the map and map/grid treatments supported the most effective searches.
A metric was developed to objectively evaluate the map sketches (See [3] for details) in terms of directional accuracy, relative distance estimation, and land form (shape, placement, and relative scale of the land masses). There were significant effects for directional accuracy across treatments (Friedman test statistic=14.52, p<=.005) as well as land form (Friedman test statistic=18.84, p<=.0001). However, distance estimation did not show a significant effect (Friedman test statistic=6.93, p>.05). Error in directional accuracy (range from 3%-60%) was significantly higher than error in distance estimation (range from 1%-10%). The ability of most subjects to efficiently dead reckon regardless of treatment is dependent on their ability to determine distance and speed. Therefore, it is not surprising that subjects were much more adept at estimating distance than direction in light of the prevalence of dead reckoning across treatments. Furthermore, disorientation often caused subjects to draw incomplete map sketches of the control treatment because they were unable to do more than randomly place targets on the map which were located while they were disoriented.
The disorientation most commonly associated with the control treatment is evident in a number of ways. A typical diagram of the route followed during an average control treatment shows significant confusion and a general inability to organize the space (See Figure 5). In this example, a coastline following method was used. The weaving motion during navigation is a behavior associated with widening the field of view. The subject looks back and forth while moving to compensate for the narrow view of the display. The path shows that this subject traversed each land mass multiple times with a single thread joining A to the others. There is no point in this environment from which A can be seen simultaneously with B or C. Consequently, most of the search was confined to familiar areas near the home target (labelled #0). This subject drew a map which shows a basic inability to extract spatial information from the space. The map is roughly a horizontal reflection of the actual environment.
The presence of the radial grid was shown to significantly improve directional accuracy. Map sketches of both the grid and map/grid treatments were more accurate in target placement than the control and map treatments. This is shown in Figure 6. This subject used an area search method in the grid treatment. The map shows that although the subject placed the targets very accurately, the land mass structure is incorrect. Due to the geocentric view provided, the map and map/grid treatments showed the most accurate land forms on the map sketching exercise.
The fact that we were able to discern reasonable cognitive representations (Figure 3), even in the control treatment indicates that structure was imposed on the environments whether or not it was supported by the environment itself. This structure is a necessary precondition to execution of a searching task. Those subjects who did not conceptually organize the environment were unable to conduct an efficient search and in many cases, did not successfully complete the task.
Thorndyke [10] describes survey knowledge in part as configurational knowledge, often acquired via a map, allowing short-cuts and the ability to infer new paths. The optimizations to the control treatment search methods observed in the map treatment illustrate this point exactly. The path shown in Figure 7 is cut short around target 5 rather than cross a land mass of known shape. This path can be compared to Figure 4A which shows the same search technique used in the control treatment. The subject is unsure of the shape and size of the land masses and therefore does not deviate from the pattern.
Behavior observed during all four treatments indicates that organizational structure and restriction of movement are an essential part of navigation. Subjects were uncomfortable with completely free and unrestricted movement in sparsely populated space because it led to disorientation much of the time. When the grid was added, this discomfort subsided as subjects found structure to guide and direct their search and consequently, avoid disorientation. The importance of paths as described by Lynch [7] indicates that in virtual and physical spaces alike, navigators need structured movement for effective navigation and spatial knowledge acquisition. This should not be interpreted as a recommendation of rigid movement restriction in virtual worlds. A lack of freedom in movement and choice inhibits exploration. Rather, we advocate the augmentation of large virtual worlds with directional cues and a simple, well-defined structure that facilitates subjects' construction of their own paths.
The frequent use of dead reckoning across treatments was not an anticipated behavior. Effective use of this technique requires three necessary components:
We are encouraged that the observations reported in this paper support the application of environmental design principles to virtual world design. We expect to broaden our investigation in the future to include environments with vastly different spatial characteristics. As environments become more complex and abstract, we will need to determine whether or not a human's conception of an abstract space is analogous to that of a physical space. Early indications are that this is the case, but a definitive statement at this time requires us to speculate as to the nature of virtual environment representations of the future.