Mariner--A 3-dimensional navigation language.

In recent years, virtual reality (VR) has become an increasingly powerful and inexpensive tool for developing interfaces for a variety of applications. Even though there has been an increase in the use of virtual reality (VR), there is a lack of software that bridges the gap between existing application programs and VR. This type of middleware is needed to manage the navigational interaction between existing application programs and VR. This article describes a language for describing navigation behaviors in 3-dimensional worlds that could potentially serve as middleware. The formal language described in this article permits precise navigation path specification and can be used as the means of mediation with application programs. The language can be used in achieving tasks such as exploring virtual worlds, programming the navigation and routing strategies for avatars, simulating the trajectories of virtual objects, and providing a formal description language for documenting user navigation in VR environments.

**********

In recent years, virtual reality (VR) has become an increasingly powerful and inexpensive tool for developing interfaces to applications such as architectural modeling, computer-aided design, data visualization, telecommuting, and environments for simulation and entertainment. Interaction in applications that incorporate VR as an interface is dynamic by nature. Users immerse themselves in 3-dimensional (3D) environments using specialized peripheral devices including head-mounted displays, data gloves, 3D-trackers, and body suits. These devices enable users to experience rich stimuli and give them control over where they go and what they do within the confines of an application. This freedom is enabled by the ability to navigate in the world.

Navigation is an aspect of behavior that causes an object to change its location, orientation, and/or relationship to other objects in its environment (Matsuba & Roehl, 1996). User interface designers have previously investigated navigation in 2-dimensional (2D) spaces and developed design principles that guide them in the development of effective and efficient interfaces (Beasley & Vila, 1992; Beccue & Vila, 1994). As designers work with 3D worlds, it will be useful to know whether the principles and findings of research related to two-dimensional navigation can be applied and extended. Since virtual worlds represent real worlds, the impact of real world navigational behaviors on interface design must also be studied.

A review of the literature related to navigation patterns in human computer interfaces indicates that research on navigation in 3D environments focuses on three areas: (a) navigational awareness, (b) spatial ability, and (c) wayfinding (purposeful, oriented movement during navigation) (Satalich, 1995). Darken and Sibert (1995) found that the organization of elements in a virtual world and the provision of an absolute frame of reference improved navigation performance. In a subsequent study, Darken and Sibert (1996) also reported an improvement in the performance of navigation tasks in virtual worlds that had been created using environmental design principles. Among their observations were that (a) path following (a form of wayfinding) is a natural spatial behavior, (b) the lack of adequate directional cues inhibited wayfinding performance, (c) a structure must be imposed on large complex worlds in order to navigate in them, and (d) a conceptual coordinate system is often imposed on the world in an attempt to structure it. Each of these studies required that the researcher track the users' navigational patterns in a virtual world. Vila, Beccue, and Furness (1997) reported on a tool that provided a template and efficient data collection capabilities for studying the navigational behaviors of users. Additional efforts to improve navigation performance by addressing issues such as the psychology of navigation, the use of navigational aids (e.g., maps), the effects of different types of worlds on navigation, and the design of an environment for navigability were the subject of discussions at the 1997 ACM Computer Human Interaction Conference (Fumas, 1997). In reviewing the literature, the authors found virtually no reports on tools for connecting an existing application program to a virtual world. This could be resolved with the development of middleware to manage the navigational interaction between an application program and a virtual world.

The purpose of this article is to describe the prototype for a language for navigating in 3D worlds that has the potential to serve as a mediator between an application and a virtual world. Mariner, the language discussed in this paper, was designed using formal language specification techniques and implemented in a web environment using Javascript and Virtual Reality Modeling Language (VRML).

Virtual worlds provide a forum for developing simulations of real world situations for education and training that are less costly than real experiences. Applications like these need to be able to interact with a virtual world. Mariner provides an initial step in connecting existing applications and VR worlds. Because Mariner provides a formal method for specifying navigation, it may also prove useful to researchers in the field of human computer interaction who are interested in describing and studying navigation behaviors in 3D worlds by documenting how users navigate in VR environments.

DEVELOPMENT OF THE MARINER LANGUAGE

The authors' objectives in the design and implementation of Mariner were to:

* define the specific navigation behaviors in a 3D virtual world that need to be modeled;

* use formal language specification techniques to define the syntactic and semantic structure of Mariner;

* implement a prototype for an interpreter using standard compiler design techniques that would translate Mariner language statements into VRML statements allowing the visualization of an object as it navigates in a 3D world; and

* determine the effectiveness of Mariner by evaluating the accuracy of programs in Mariner that generate navigation actions for an object defined in a VRML world.

Defining Behaviors

The first step in developing Mariner was to determine what type of navigation behaviors occur in 3D worlds. The authors identified movement, rotation, collision detection, conditional behavior, and repetitious behavior as the behaviors to model in the language.

Movements in a 2D world are usually expressed using a grid coordinate system. Movements can either be direct (e.g., move to 138,34) or relative (e.g., move forward 10). Some parameters to commands may be implied; "move forward l0" implies that the object is facing in a specified direction and will continue to move in that direction when it moves. In a 3D world, some 2D concepts have the same meaning. For example, movements may also be expressed using a grid (now a 3D grid) and the concept of moving forward a specified number of units remains the same. However, the movement of objects is no longer defined in a plane; objects have the freedom to move (and rotate) in all of the directions that can be defined by a 3D space.

Whether in a 2D or 3D world, objects have relationships to other objects in the world. An object may be to the right of another object or in front of another object. As an object navigates, its relationship to other objects changes. Correct and incorrect behaviors must be defined. In navigating within a world with multiple objects, for example, it would not be correct for an object to move forward "through" another object as if it did not exist. An object should be able to detect and avoid an impending collision with another object.

Objects in virtual worlds often exhibit repetitive behavior or behavior that is based on conditions that must be evaluated before performing the behavior. For example, not to move if there is an object directly in front of the object to be moved. Hence, control structures that allow for conditional or repetitious behavior are also needed.

Syntax and Semantics

After defining the behaviors to model, the syntax and semantics of the Mariner were specified. Because languages that have been unambiguously defined using Backus Naur Form (BNF) can often be easily implemented using recursive, top down analysis techniques, and automatic compiler development tools, the syntax for Mariner was specified using BNF (Alblas & Nymeyer, 1996). The BNF for Mariner appears in Figure 3.

The semantics were implemented as paragraphs of text describing the behavior of each statement. For the most part the meaning of program statements can be inferred from their syntax. While developing the semantics, it proved useful to identify potential errors in syntax and behavior so that error-handling routines could be later developed.

Currently, the syntax represents a language in which small programs can be written to manipulate a limited number of objects in a 3D world. The objects that can be manipulated include a sphere, cone, cylinder, and cube. The current syntax and semantics will form the base for implementing the language as a form of middleware to interact with other applications. An example of a small Mariner program is shown in Figure 1. Note that the object that has been defined is a cone and all subsequent movements apply to that object. In its current form, there are no variables in Mariner, so there is no way to reference the cone in later segments of code that are separated from its initial definition.

THE MARINER LANGUAGE DEVELOPMENT ENVIRONMENT

The Mariner language development environment, shown in Figure 2, has two components, the Mariner code generator and the Mariner interpreter. The Mariner code generator allows the user to define objects and their navigation paths within a virtual world through a user-friendly interface. The user can select predefined options for each object for which Mariner statements will be generated and displayed in the text area, or he/she can type Mariner language statements directly in the text area. The language development environment was constructed as a web page using Javascript and VRML 2.0.

The code generator permits the user to define an object geometry that includes traditional VRML nodes such as cones and cubes. In addition, the user can define navigational movements for each defined object using translation and rotation transformations. All object dimensions and movement distances are specified in pixel units. After completing a Mariner program, the user can choose to have it interpreted into VRML statements which can be executed in a web browser.

SUMMARY

A prototype for a 3D navigational language, Mariner, was described in this article, which has the potential to serve as a link between 3D worlds and software applications. The language, written in Javascript and VRML, currently generates VRML code which can be viewed within a web browser. Future development includes the transformation of the language into code segments that can be embedded within an existing 3D world and act upon existing or newly created objects within the world.

Figure 1. Program example

Cone:

Size = 2

Height = 4

Color = 120 0 0

Movement 1

Move 5 Units Along X Axis

Move 0.0 Units Along Y Axis 

Move 0.0 Units Along Z Axis

Rotate Counter ClockWise Along Z Axis by 90

Degrees

Movement 2

Move 0 Units Along X Axis

Move 5 Units Along Y Axis

Move 0.0 Units Along Z Axis

Rotate ClockWise Along Z Axis by 90 Degrees

References

Alblas, H., & Nymeyer, A. (1996). Practice and principles of compiler building with C, Prentice-Hall.

Beasley, R., & Vila, J. (1992). The identification of navigation patterns in a multimedia environment: A case study, Journal of Educational Multimedia and Hypermedia, 1(2), 209-222.

Beccue, B., & Vila, J. (1994). AIT: An analytic tool for identifying user-preferences in a multimedia environment, International Conference Proceedings of PRIISM-94 (pp.24-31). Maui, Hawaii,.

Darken, R.P., & Sibert, J.L. (1995). Navigating in large virtual spaces, Journal of Human-Computer Interaction.

Darken, R.P., & Sibert, J.L. (1996). Wayfinding strategies and behaviors in large virtual worlds, Proceedings of the ACM Special Interest Group Conference on Human-Computer Interfaces Conference.

Furnas, G. (1997). Workshop on navigation in electronic worlds, ACM Computer Human Interaction Conference.

Matsuba, S.N., & Roehl, B. (1996). Using VRML, Que Corporation. Satalich, G.A. (1995). Navigation and wayfinding in virtual reality: Finding the proper tools and cues to enhance navigational awareness. (Thesis: Washington University)

Vila, J., Beccue, B., & Furness, G. (1997). User interface design for virtual reality: A research tool for tracking navigation, Proceedings of the Hawaii International Conference on System Science.