U.S. Pat. No. 8,095,881

The drawings are merely schematic representations, not intended to portray specific parameters of the invention. Moreover, the drawings are intended to depict only typical embodiments of the invention and therefore should not be considered as limiting the scope of the invention.

DETAILED DESCRIPTION OF THE INVENTION

FIG. 1depicts a block diagram depicting illustrative components for an autonomous teleport network system according to the invention. By way of example the system consists of a number (plurality) of locations110,120with teleport source stations112,114,116, and122,124,126, where an avatar may go to select one desired target out of a plurality of several (1 to n) teleport target station140,150, and160at specific teleport target locations, each equipped with a list of known nodes142,152, and162, i.e., other target locations.

The source locations110,120may be compared to a bus-stop—one moves there to catch a bus and let oneself transport to a target destination. The various bus stops one can reach from the starting bus stop are similar to teleport source stations112,114,116, of the first location110and teleport source stations122,124, and126of the nth location120. The station where one leaves the bus is similar to a teleport target location140,150,160.

The teleport target station140,150,160is an object in the virtual world running data processing software (a script). The teleport target station object can be anything—an invisible 1×1×1 cm3object, a big stage, etc. The avatar will always be teleported to the coordinates of that teleport target station object, preferably to the coordinates of the center of the teleport target station object.

A process performed by the script executed in a teleport target station can include:(1) determining the coordinates of the teleport target station object it is running in;(2) listening to broadcasts of other nearby teleport target station objects;(3) building a list of known teleport target stations140,150,160from the data gathered in (1) and (2); and(4) broadcasting the list of the known teleport target stations140,150,160to neighboring teleport target station objects.

Thus, by way of example, a broadcast originated by teleport target station140, i.e., the teleport target station's object, would contain location information of teleport target stations150and160. Similarly, a broadcast of the teleport target station150would contain location information related to the teleport stations140and160and a broadcast of the teleport target station160would contain location information related to the teleport stations150and160. A broadcast can be understood as the transmission of a message sent on a shared medium to be intercepted and processed by a plurality of receivers.

The teleport source stations112,114,116,122,124, and126are also objects in the virtual world running data processing software (a script). The script executed in a teleport source station listens to the broadcasts emitted by the teleport target stations140,150,160. Each script of a teleport source station112,114,116,122,124,126determines which of the multiple broadcasted messages it receives is target to its particular instance and contains data which is related to the target of the teleport function of specific teleport source station112,114,116,122,124,126.

By its particular design the method and system according to the invention advantageously ensure thatthe accurate coordinates are configured;only the most recent data is configured, i.e., no overwriting happens of recent up-to-date data by old data from messages straying around;teleport target stations which are out of service are automatically removed from the auto configuration of the teleport source stations; andsource stations and target stations which do not have direct communications exchange their data via one or more intermediate repeaters.

Each teleport target station can send its own coordinates, i.e., the teleport target station object's coordinates, on a regular basis in a message that can contain, for example, the virtual-world-internal key of the teleport target station object, the coordinates of the teleport target station object, and a timestamp. The teleport source station can configure itself by linking its own name or identifier with the names of teleport target station objects contained the broadcast messages. It can derive the target name by translating the target identifier key transmitted in the message into a name. The name of the teleport target station can have a prefix, e.g., “Source4”. The teleport source station can compare the name or identifier in the broadcast message with its own name or identifier. If the match is successful, the teleport source station can configure itself with the coordinates in the message as sent by the teleport target station, i.e., it updates the target settings of its teleport function with the new coordinates of the teleport target location.

FIG. 2exemplifies a layout of such a broadcast message210referred to inFIG. 1. The broadcast message210can include a header212, which identifies the message and the version of the message protocol used; a target identification214, which is a virtual world internal key identifying the teleport target location, whose position is broadcasted; in-world target coordinates216of the teleport target station; a sequence number218which identifies the most recent version of a broadcast message and as such avoids old messages straying around and avoids invalidating actual, recent ones; and a sender identification220.

Referring now toFIG. 3, the logic of the teleport target stations140,150,160(FIG. 1) in determining the own coordinates and building and broadcasting the known nodes list142,152,162(FIG. 1) is presented as a flow chart showing a process performed by a teleport target station when it broadcasts its known location. Broadcasting in virtual worlds is comparable to broadcasting of telecasts in the real world: the signal is aired and is received by a multitude of receivers. For teleport target stations this means to send position related data on a communication channel without knowing how many receivers they actually reach.

The broadcast is triggered by a timer, which regularly starts the execution of the process shown in the flowchart inFIG. 3. A timed approach is taken to detect stations which are no longer in service and remove them from the list of auto-configured stations. Following a start310, the expiration of the timer is indicated in312. In314, the script running in the environment of a teleport target station object determines the coordinates of that object, constructs a broadcast message210as indicated inFIG. 2and broadcasts the message on a known channel in the virtual world. The sequence number218(FIG. 2) of the broadcast message210is monotonously increasing compared to the last one sent. The message enables all receiving teleport source stations to inspect the broadcast and eventually, if the message applies to the source station, set the teleport target coordinates in their teleport function. A higher sequence number218of a given broadcast message of one particular teleport target station object invalidates a lower one.

To enable teleport source stations112,114,116, and122,124,126(FIG. 1) outside the range of the broadcast from a specific teleport target station140,150,160(FIG. 1) to join the auto-configuration, each teleport target station140,150,160(FIG. 1) acts as a repeater. The repeater function can be implemented, for example, as described below.

In316, each entry in the known teleport target stations list142,152,162(FIG. 1) is examined. The list may contain nodes (teleport target stations) which are taken out of operation. In320, this situation is detected by comparing the expiration timer of the entry in question with the current time in the virtual world. If the entry has timed out, it is deleted from the list in330and, as a consequence thereof, gradually taken out of the auto-configuration network.

If the entry is still valid, a broadcast message as described inFIG. 2is constructed in322, and the message is sent out in324. The process then advances in326to the next entry in the list and continues the broadcast at label318. In328, it is determined if broadcast messages have been sent for all known and valid target stations. If so, the process ends in332. If not, further respective broadcast messages are sent until the messages of all known target stations have been broadcasted.

FIG. 4illustrates a flow diagram which describes how a teleport source station112,114,116, and122,124,126depicted inFIG. 1receives and interprets the various broadcast messages of teleport target stations.

In414, an incoming broadcast message210of a particular teleport target station is received. The target identification214is translated into a name in416. The name is used to compare it against the name of the receiving teleport source station112,114,116,122,124,126. In418, it is determined whether the determined name, for example, prefixed by a fixed string value, equals the teleport source station's own name. If this is the case, the message is considered to be targeted to this particular teleport source station112,114,116, and122,124,126and ignored otherwise in428.

In420, it is determined if the received message is the first one received for this teleport source station. The first message is always taken as most recent as there is no further data held in the teleport source station to compare to. If this broadcast message is not the first message received, in422, the sequence number in the received message is verified. This allows the teleport source station112,114,116, and122,124,126to avoid the overwriting of more recent messages with older ones. As the teleport target station140,150,160(FIG. 1) increases the sequence number with each broadcast, only the broadcast with the highest sequence number is considered valid. All others are ignored. If the message passes the test, the particular teleport target station's coordinates are retrieved from the broadcast message (424) and the teleport function is configured such that an avatar wishing to be teleported will be moved to the coordinates found in the just received broadcast message (426).

The flow diagram depicted inFIG. 5describes the receiving part of the repeater function of a teleport target station140,150,160(FIG. 1). After the start512, an incoming broadcast message210(FIG. 2) is received in514. In516, the target identification214is translated into a name. If the teleport target location140,150,160has the same name as this name in the broadcast message, the message is ignored in518. This message is an “echo” of a message once sent already by this teleport target location140,150,160.

If the name is different, in520, it is determined whether this message is the first seen for the teleport target location140,150or160identified by the message's target identification214. If it is a repeated message by the respective teleport target station140,150or160, it is checked in522, similar to the procedure inFIG. 4,422, if it carries a higher sequence number214as the already known entry in the known nodes list142,152or162. If the message is new (N-exit of520) or passes522, it will be added in524to the known nodes list142,152,162with the actual location, which will be broadcasted after expiration of the broadcast timer as explained inFIG. 3. If the message is not new (Y-exit of520), it is checked if the sequence number is higher than the already known. If yes, the teleport target station is added to the list of known nodes in524with its new location data. If no, the process jumps to end528.

Referring now toFIG. 6, a virtual world example of teleport source stations and target stations is shown. The area in question contains three targets640,650,660an avatar want or must regularly move to. Each of the targets640,650,660contains one object (not shown) in the virtual world, which defines the location of the respective teleport station. In the example, these objects are called “Home”, “Pub” and “Work” accordingly. Each of these objects runs a script which regularly gets the object's location and broadcasts it.

The avatar uses teleport source location610,620,630, which are symbolized e.g., by a rectangle with two circles, like buttons in an elevator. Each circle implements a teleport source station612,614,622,624,632,634. The circles614,632labeled “Work” in the drawing are objects in the virtual world named “Source4Work”, likewise the circles624,634labeled “Home” are called “Source4Home” and the circles612,622labeled “Pub” are called “Source4Pub”. The occurrence of the teleport source locations610,620,630is free to a designer—it needs only just to carry a script to setup the target coordinates and allow an avatar to interact with it.

Each of these teleport source station objects runs a script which listens to the broadcasts and, as soon as they match their part of their own name after the initial “Source4”, they set the target location of the teleport to the coordinates carried in the message.

If a teleport source station614,632called “Source4Work” receives a message like e.g. “Work;”, it will set the target of its teleport function to “.” As the avatar interacts in an intended way with a teleport source station object, the avatar will be moved to the target location indicated by the object's label.

With this principle in place, it is possible to create rather complex teleport networks without concerns that the target coordinates of each teleport source station may be wrongly configured.

The usage of repeater nodes700introduces a data consistency issue: As the data of a teleport target location are held in multiple nodes of the teleport network a method needs to ensure that all data records stay consistent all times.

By way of example, one can consider this sequence of events:The teleport network has configured itself and is running smoothly.The location of the “Work”-object changes. “Work” detects the location change and broadcasts the new location.The teleport source stations near “Pub” receive the new location of “Work” and reconfigure them.The “Pub” object receives the new location of “Work” and updates the known location of “Work”.Shortly after, “Home” begins its regular broadcast.As “Home” hasn't received the new location from “Work”, because “Work” is too far away and “Repeater” has not broadcasted its list yet, “Home” will send the old location of “Work” to the teleport source stations near “Pub”.The teleport source stations near “Pub” receive the new location of “Work” and reconfigure themselves with the old, now incorrect teleport target station coordinates.“Pub” also receives the old location of “Work”. It will store it in the list of know teleport target stations and send it with the next broadcast, probably making other listening teleport source stations to overwrite the correct location with the old, incorrect one.

As described in the sequence above, it may happen that two messages of a teleport target station carrying different location information are straying in the network overwriting each other. To solve this issue, in an illustrative solution a teleport target station adds a unique increasing value each time it broadcasts its own location coordinates. As the broadcast intervals are preferably multiple of seconds, the current time in seconds since the epoch (Unix-time) is sufficient. Any receiving station discards messages for a particular teleport target location with a sequence counter lower or equal the one stored already in the receiving station's data

An alternative solution could be to immediately broadcast as a repeater a message upon receipt instead in regular intervals. A subsequent “broadcast storm”, i.e., never ending repetition of repeated messages, can be sufficiently prevented by sending at regular intervals as described above.

During re-arrangement of the island in the virtual world, some of the teleport target stations might be removed, but still exist in the lists of the other nodes in the teleport network. Especially the teleport source stations are still configured to teleport avatars to the now nonexistent target.

As the station already maintain the sequence counter (i.e., sequence number) to enforce data integrity, as explained above, and the sequence number is up to date, i.e., corresponds to the time of the last broadcast of the teleport target station at its last location, it is easy to use the time to decide whether a particular entry is valid. If the sequence number indicates a time which is older than the current time minus a time-out value, the according entry is considered to be orphaned and the teleport target station is assumed to be out of service.

Broadcasting stations check their entries before a broadcast whether they are orphaned. If they are orphaned, they delete the entry from the list and consequently do not further broadcast it.

Teleport source stations check on regular intervals or at the start of an interaction with an avatar (if possible), whether the entry is orphaned, and if so, inform the avatar accordingly.

An example of the format of the broadcast messages exchanged between the teleport nodes is as follows: “,”“,”with: “%%%BCSTV3%%%”representing the current protocol version level;: representing the object key in the virtual world of the landing zone object (i.e., the teleport target station object);: representing the vector of the position of the landing zone (i.e., location of the teleport target station object); andInteger:representing the time of the broadcast sent by the originating teleport target station as it is broadcasting its position. This avoids “old” location information to override more recent ones. A location message with a higher value overrides always location information with a lower value and can also be used to time-out orphaned stations.

The invention can take the form of an entirely hardware embodiment, an entirely software embodiment or an embodiment containing both hardware and software elements. In a preferred embodiment, the invention is implemented in software, which includes but is not limited to firmware, resident software, microcode, etc.

Furthermore, the invention can take the form of a computer program product accessible from a computer-usable or computer readable medium providing program code for use by or in connection with a computer or any instruction execution system. For the purposes of this description, a computer-usable or computer readable medium can be any apparatus that can contain, store, communicate, propagate, or transport the program for use by on in connection with the instruction execution system, apparatus, or device.

The medium can be an electronic, magnetic, optical, electromagnetic, infrared, or semiconductor system (or apparatus or device) or a propagation medium. Examples of a computer-readable medium include a semiconductor or solid state memory, magnetic tape, a removable computer diskette, a random access memory (RAM), a read-only memory (ROM), a rigid magnetic disk and an optical disk. Current examples of optical disks include compact disk-read-only memory (CD-ROM), compact disk-read/write (CD-R/W) and DVD.

An illustrative data processing system800as schematically depicted inFIG. 7suitable for storing and/or executing program code will include at least one processor802coupled directly or indirectly to memory elements804through a system bus806. The memory elements804can include local memory employed during actual execution of the program code, bulk storage, and cache memories which provide temporary storage of at least some program code in order to reduce the number of times code must be retrieved from bulk storage during execution. Alternatively, external memory elements can be coupled to the system800and the processor802, respectively.

Input/output or I/O-devices808,810(including, but not limited to keyboards, displays, pointing devices, etc.) can be coupled to the system800either directly of through intervening I/O controllers812.

Network adapters814may also be coupled to the system800to enable the data processing system or remote printers or storage devices through intervening private or public networks. Modems, cable modem and Ethernet cards are just a few of the currently available types of network adapters.

While the foregoing has been with reference to particular embodiments of the invention, it will be appreciated by those skilled in the art that changes in these embodiments may be made without departing from the principles and spirit of the invention, the scope of which is defined by the appended claims.