System and method for enabling users to interact in a virtual space
The present invention provides a highly scalable architecture for a three-dimensional graphical, multi-user, interactive virtual world system. In a preferred embodiment a plurality of users interact in the three-dimensional, computer-generated graphical space where each user executes a client process to view a virtual world from the perspective of that user. The virtual world shows avatars representing the other users who are neighbors of the user viewing the virtual word. In order that the view can be updated to reflect the motion of the remote user's avatars, motion information is transmitted to a central server process which provides positions updates to client processes for neighbors of the user at that client process. The client process also uses an environment database to determine which background objects to render as well as to limit the movement of the user's avatar.
1. A method for enabling a first user to interact with a plurality of second users in a virtual space, the virtual space comprising a first avatar and a plurality of second avatars, the first avatar being associated with a first client process, each second avatar of the plurality of second avatars being associated with a different second client process of a plurality of second client processes, the method comprising:
receiving from each second client process of the plurality of second client processes a second received position of a second avatar associated with said each second client process, thereby obtaining a first plurality of second received positions;
selecting a second plurality of N second received positions from the first plurality of second received positions, the second plurality of second received positions being smaller than the first plurality of second received positions; and
transmitting the second plurality of second received positions to the first client process, wherein the first client process does not receive at least one second received position of the first plurality of second received positions;
wherein the step of selecting the second plurality comprises:
subdividing a bounding box around a first position of the first avatar into a plurality of cells;
assigning said each second avatar to a single cell of the plurality of cells based on second received position of said each second avatar; and
scanning the plurality of cells in an outwardly expanding wave from the first position of the first avatar until at least N second avatars are found.
2. A method according to claim 1 , wherein said each second client process executes on a different second client computer of a plurality of second client computers, and the first client process executes on a first client computer.
3. A method according to claim 2 , wherein:
the steps of receiving and transmitting are performed by a server computer coupled through a network to the first client computer and to each second client computer of the plurality of second client computers.
4. A method according to claim 3 , further comprising:
receiving by the server computer the first position from the first client computer.
5. A method according to claim 3 , wherein the network is a wide area network.
6. A method according to claim 3 , wherein the network is the Internet.
7. A method according to claim 6 , wherein the step of selecting is performed periodically.
8. A method according to claim 6 , wherein the bounding box is two-dimensional.
9. A method according to claim 6 , wherein the bounding box is two-dimensional and square.
10. A method according to claim 9 , wherein the bounding box is two-dimensional and square, and the step of subdividing is performed so that each cell of the plurality of cells is square.
11. A method according to claim 6 , wherein the step of selecting is performed by the server computer.
12. A method according to claim 6 , wherein the first avatar is associated with the first user, and said each second avatar is associated with a different second user of the plurality of second users.
13. A method according to claim 6 , wherein the virtual space is a three-dimensional space further comprising a plurality of rooms, the first avatar is three-dimensional comprising M panels, and said each second avatar is three-dimensional comprising M panels, M being greater than two.
14. A method according to claim 13 , wherein M is equal to eight.
15. A method for enabling a first user to interact with a plurality of second users in a virtual space, the virtual space comprising a first avatar and a plurality of second avatars, the first avatar being associated with a first client process, each second avatar of the plurality of second avatars being associated with a different second client process of a plurality of second client processes, the method comprising:
receiving from each second client process of the plurality of second client processes a second received position of a second avatar associated with said each second client process, thereby obtaining a first plurality of second received positions;
step for using a bounding box to select a second plurality of N second received positions from the first plurality of second received positions, the second plurality of second received positions being smaller than the first plurality of second received positions; and
transmitting the second plurality of second received positions to the first client process wherein the first client process does not receive at least one second received position of the first plurality of second received positions.
16. A method according to claim 15 , wherein said each second client process executes on a different second client computer of a plurality of second client computers, and the first client process executes on a first client computer.
17. A method according to claim 16 , wherein:
the steps of receiving and transmitting are performed by a server computer coupled through a network to the first client computer and to each second client computer of the plurality of second client computers.
18. A method according to claim 17 , further comprising:
receiving by the server computer the first position from the first client computer.
19. A method according to claim 17 , wherein the network is the Internet.
20. A method according to claim 19 , wherein:
the step for using the bounding box is performed by the server computer; and
the virtual space is a three-dimensional space further comprising a plurality of rooms, the first avatar is three-dimensional comprising M panels, and said each second avatar is three-dimensional comprising M panels, M being greater than two.
21. A server computer for enabling a first user to interact with a plurality of second users in a virtual space, the virtual space comprising a first avatar and a plurality of second avatars, the first avatar being associated with a first client process, each second avatar of the plurality of second avatars being associated with a different second client process of a plurality of second client processes, the server computer being coupled by a network to a first client computer and to a plurality of second client computers, the server computer being configured to perform steps comprising:
receiving from each second client process of the plurality of second client processes a second received position of a second avatar associated with said each second client process, thereby obtaining a first plurality of second received positions;
selecting a second plurality of N second received positions from the first plurality of second received positions, the second plurality of second received positions being smaller than the first plurality of second received positions; and
transmitting the second plurality of second received positions to the first client process, wherein the first client process does not receive at least one second received position of the first plurality of second received positions;
wherein the step of selecting the second plurality comprises:
subdividing a bounding box around a first position of the first avatar into a plurality of cells;
assigning said each second avatar to a single cell of the plurality of cells based on second received position of said each second avatar; and
scanning the plurality of cells in an outwardly expanding wave from the first position of the first avatar until at least N second avatars are found.
22. A server computer according to claim 21 , wherein said each second client process executes on a different second client computer of the plurality of second client computers, and the first client process executes on the first client computer.
23. A server computer according to claim 22 , wherein the steps further comprise:
receiving by the server computer the first position from the first client computer.
24. A server computer according to claim 23 , wherein the network is a wide area network.
25. A server computer according to claim 23 , wherein the network is the Internet.
26. A server computer according to claim 25 , further configured to perform the step of selecting periodically.
27. A server computer according to claim 25 , further configured to perform the step of subdividing so that the bounding box is two-dimensional.
28. A server computer according to claim 25 , further configured to perform the step of subdividing so that the bounding box is two-dimensional and square.
29. A server computer according to claim 28 , further configured to perform the step of subdividing so that the bounding box is two-dimensional and square, and each cell of the plurality of cells is square.
30. A server computer according to claim 25 , wherein the first avatar is associated with the first user, and said each second avatar is associated with a different second user of the plurality of second users.
31. A server computer according to claim 25 , wherein the virtual space is a three-dimensional space further comprising a plurality of rooms, the first avatar is three-dimensional comprising M panels, and said each second avatar is three-dimensional comprising M panels, M being greater than two.
32. A server computer according to claim 31 , wherein M is equal to eight.
33. An article of manufacture comprising one or more memory devices storing computer code for enabling a first user to interact with a plurality of second users in a virtual space, the virtual space comprising a first avatar and a plurality of second avatars, the first avatar being associated with a first client process, each second avatar of the plurality of second avatars being associated with a different second client process of a plurality of second client processes, the code comprising computer instructions for performing steps comprising:
receiving from each second client process of the plurality of second client processes a second received position of a second avatar associated with said each second client process, thereby obtaining a first plurality of second received positions;
selecting a second plurality of N second received positions from the first plurality of second received positions, the second plurality of second received positions being smaller than the first plurality of second received positions; and
transmitting the second plurality of second received positions to the first client process, wherein the first client process does not receive at least one second received position of the first plurality of second received positions;
wherein the step of selecting the second plurality comprises:
subdividing a bounding box around a first position of the first avatar into a plurality of cells;
assigning said each second avatar to a single cell of the plurality of cells based on second received position of said each second avatar; and
scanning the plurality of cells in an outwardly expanding wave from the first position of the first avatar until at least N second avatars are found.
34. An article of manufacture according to claim 33 , wherein said each second client process executes on a different second client computer of a plurality of second client computers, and the first client process executes on a first client computer.
35. An article of manufacture according to claim 34 , wherein:
the steps of receiving and transmitting are performed by a server computer coupled through a network to the first client computer and to each second client computer of the plurality of second client computers.
36. A method according to claim 35 , further comprising:
receiving by the server computer the first position from the first client computer.
37. A method according to claim 35 , wherein the network is a wide area network.
38. A method according to claim 35 , wherein the network is the Internet.
39. A method according to claim 38 , wherein the step of selecting is performed periodically.
40. A method according to claim 38 , wherein the bounding box is two-dimensional.
41. A method according to claim 38 , wherein the bounding box is two-dimensional and square.
42. A method according to claim 41 , wherein the bounding box is two-dimensional and square, and the step of subdividing is performed so that each cell of the plurality of cells is square.
43. A method according to claim 38 , wherein the step of selecting is performed by the server computer.
44. A method according to claim 38 , wherein the first avatar is associated with the first user, and said each second avatar is associated with a different second user of the plurality of second users.
45. A method according to claim 38 , wherein the virtual space is a three-dimensional space comprising a plurality of rooms, the first avatar is three-dimensional comprising M panels, and said each second avatar is three-dimensional comprising M panels, M being greater than two.
46. A method according to claim 45 , wherein M is equal to eight.