Method and apparatus for maintaining information about users sharing the cells partitioning a computer-generated environment

• US 6,801,930 B1
• Filed: 09/15/2000
• Issued: 10/05/2004
• Est. Priority Date: 02/26/2000
• Status: Expired due to Term

• Current Assignee: Harmonix Music Systems Incorporated (Epic Games, Inc.)
• Original Assignee: Quazal Technologies, Inc. (Ubisoft Entertainment S.A.)
• Inventors: Lavoie, Martin, Dionne, Carl
• Primary Examiner(s): LIN, WEN TAI
• Application Number:
  US09/662,470
• Time in Patent Office: 1,481 Days
• Field of Search: 709/204, 709/205, 345/757, 463/7, 463/32, 463/42
• US Class Current: 709/205
• CPC Class Codes: H04L 41/00 Arrangements for maintenance, administration or management of data switching networks, e.g. of packet switching networks
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies

Abstract

A computer network is configured to define and update a shared computer-generated environment. A serving computer divides a computer-generated environment into a plurality of cells. A plurality of user computer terminals have display devices, storage, processing capability and a connection to the network. A first user computer terminal defines an entry in the computer-generated environment in one or in a plurality of adjoining cells. The network connection receives notification data about other users sharing cells occupied by the first user. A list of users are stored that share or have shared cells occupied by the first user. The processing capability generates a message for another user identified in the list and generates a local representation of the environment in response to data received from other users and in response to user movements. In this way, it is possible for a very large number of users to share a common computer-generated environment using available networking and processing capabilities.

Claims

1. A computer network configured to define and update a shared computer-generated environment, said network comprising:

a serving computer configured to divide a computer-generated environment into a plurality of cells; and

a plurality of user-computer terminals having display means, storage means, processing means and network connection means, wherein

a first user-computer-terminal is configured to define an entry in said computer-generated environment in one cell or in a plurality of adjoining cells;

said user-computer terminal network connection receives notification data about other users sharing cells occupied said first user;

said user-computer terminal storage means is configured to store a list of users that share or have shared cells occupied by said first user; and

said user-computer terminal processing means is configured to generate a message for another user identified in said list and to generate a local representation of said environment in response to data received from other users and in response to other user movements.

2. A network according to claim 1, wherein said processing means is configured to predict movements by position history-based dead reckoning.

3. A network according to claim 1, wherein said message is generated in response to an unpredicted user movement.

4. A network according to claim 1, including a plurality of serving computers wherein each of said serving computer maintains a copy of the lists of nearby users for all users within a region, wherein said region encompasses a plurality of said cells.

5. A computer network according to claim 4, wherein said serving computer comprises a plurality of processing nodes, wherein each of said processing nodes is responsible for the maintenance of a region of said computer-generated environment, and each of said regions comprises a plurality of said cells.

6. A computer network according to claim 1, wherein said processing means is configured to generate an update request via said network connection and said serving computer is configured to transmit position data in response to receiving said request.

7. A computer network according to claim 6, wherein said serving computer is configured to transfer responsibility for a user from a first node to a second node when the user'"'"'s previous region is no longer occupied by the user.

8. A network according to claim 6, wherein said processing means determines whether to issue an update request by comparing server-held copies of a user'"'"'s list of nearby users and a list of other users that have previously entered a cell occupied by said user.

9. Apparatus according to claim 1, wherein said serving computer is configured to divide said computer-generated environment into a plurality of overlapping cells.

10. A computer network according to claim 1, including input means configured to supply movement data to said processing means to effect movement of an entry in said computer-generated environment.

11. A method of updating a computer-generated environment shared between users connected via computer terminals connected to a network, said computer-generated environment being divided into cells, wherein a user'"'"'s computer terminal performs the method comprising:

receiving notification of other users sharing the same cell or cells;

updating a list of users that share or have shared the same cell;

generating a message for at least one user in said list;

updating an environment generated on the computer terminal in response to other user data; and

updating said list in response to user movements.

12. A method according to claim 11, wherein said user movements are predicted by position history-based dead reckoning.

13. A method according to claim 11, wherein said message is generated in response to an unpredicted user movement.

14. A method according to claim 11, wherein a network server maintains a copy of the lists of nearby users for all users within a region, said region encompassing a plurality of said cells.

15. A method according to claim 14, wherein said network server comprises a plurality of processing nodes, each responsible for maintenance of a region of said computer-generated environment, each region comprising a plurality of said cells.

16. A method according to claim 14, wherein said server transmits position data in response to a need for user update.

17. A method according to claim 16, wherein said need for user update is determined by a comparison between server-held copies of a user'"'"'s list of nearby users, and a list of other users that have just entered a cell occupied by the user.

18. A method according to claim 11, wherein said cells are overlapping.

19. A method according to claim 15, including transferring responsibility for a user when the user'"'"'s previous region is no longer occupied by the user.

20. A method according to claim 11, wherein movement data is defined by manually operable devices.

21. A computer-readable medium having computer-readable instructions executable by a computer such that, when executing said instructions, a computer will perform the method comprising:

receiving notification of users sharing cells, wherein a network of computer have generated an environment divided into a plurality of cells;

updating a list of users that share or have shared the same cell;

generating a message for at least one user in said list;

updating an environment generated on the computer terminal in response to other user data; and

updating said list in response to user movements.

22. A computer-readable medium having computer-readable instructions according to claim 21, such that when executing said instructions a computer will also perform the step of predicting user movements by position history-based dead reckoning.

23. A computer-readable medium having computer-readable instructions according to claim 21, such that when executing said instructions a computer will also perform the step of generating said message in response to an unpredicted user movement.

24. A computer-readable medium having computer-readable instructions according to claim 21, such that when executing said instructions a computer will also perform the step of responding to input data defining the position of a user within the computer-generated environment.