Simulation systems and methods

• US 10,025,892 B2
• Filed: 11/28/2016
• Issued: 07/17/2018
• Est. Priority Date: 08/24/2016
• Status: Active Grant

• Current Assignee: Improbable Worlds Ltd.
• Original Assignee: Improbable Worlds Ltd.
• Inventors: Whitehead, Robert James Frederick, Tang, Hanying, Lewis, Matthew John Reveley, Lipka, Peter Richard
• Primary Examiner(s): JONES, HUGH M
• Application Number:
  US15/361,874
• Publication Number:
  US 20180060461A1
• Time in Patent Office: 596 Days
• Field of Search: 703 6
• CPC Class Codes: G06F 30/20 Design optimisation, verification or simulation optimisation, verification or simulation of circuit designs G06F30/30
• CPC Class Codes: G06F 9/4856 resumption being on a different machine, e.g. task migration, virtual machine migration G06F9/5088 takes precedence
• CPC Class Codes: G06F 9/5061 Partitioning or combining of resources
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system
• CPC Class Codes: G06F 9/541 via adapters, e.g. between incompatible applications

Abstract

Methods, systems, computer-readable media, and apparatuses for performing, providing, managing, executing, and/or running a spatially-optimized simulation are presented. In one or more embodiments, the spatially-optimized simulation may comprise a plurality of worker modules performing the simulation, a plurality of entities being simulated among the plurality of worker modules, a plurality of bridge modules facilitating communication between workers and an administrative layer including a plurality of chunk modules, at least one receptionist module, and at least one oracle module. The spatially-optimized simulation may be configured to provide a distributed, persistent, fault-tolerate and spatially-optimized simulation environment. In some embodiments, load balancing and fault tolerance may be performed using transfer scores and/or tensile energies determined among the candidates for transferring simulation entities among workers. In some embodiments, the plurality of bridge modules may expose an application programming interface (API) for communicating with the plurality of worker modules.

Claims

1. A spatially-optimized simulation system comprising:

at least one computer processor controlling some operations of the system; and

memory storing computer-readable instructions that, when executed by the at least one computer processor, configure the system to run a spatially-optimized simulation comprising;

a plurality of entities being simulated, wherein each entity of the plurality of entities comprises one or more components, and wherein each of the one or more components comprises one or more properties;

a plurality of worker modules distributed over one or more computer servers, wherein each worker module of the plurality of worker modules performs a subset of the spatially-optimized simulation, wherein each worker module of the plurality of worker modules is configured to instantiate a subset of the plurality of entities and is further configured to update the one or more properties of at least one component of the one or more components of each entity in the subset of the plurality of entities instantiated by the worker module of the plurality of worker modules, wherein the plurality of worker modules comprises a first worker module and a second worker module, wherein the first worker module of the plurality of worker modules corresponds to a first game engine that simulates rigid-body physics for the spatially-optimized simulation, and wherein the second worker module of the plurality of worker modules corresponds to a second game engine that provides client-side rendering for the spatially-optimized simulation;

a plurality of chunk modules, wherein each chunk module of the plurality of chunk modules is configured to monitor a subset of entities assigned to the chunk module of the plurality of chunk modules, wherein the subset of entities assigned to the chunk module of the plurality of chunk modules are located within a chunk region assigned to the chunk module of the plurality of chunk modules, and wherein the plurality of chunk modules executes on at least one server different from the one or more computer servers on which the plurality of worker modules are distributed;

a plurality of bridge modules corresponding to the plurality of worker modules, wherein each bridge module of the plurality of bridge modules is configured to facilitate communications between a worker module of the plurality of worker modules and one or more chunk modules monitoring one or more entities being simulated on the worker module of the plurality of worker modules;

at least one receptionist module, wherein the at least one receptionist module is configured to receive, from a plurality of client modules, at least one request for connecting to the spatially-optimized simulation system and is further configured to assign a corresponding bridge module of the plurality of bridge modules for communicating with each client module in response to receiving the at least one request for connecting to the spatially-optimized simulation, wherein at least one client module of the plurality of client modules executes on a device different from the one or more computer servers on which the plurality of worker modules are distributed and different from the at least one server on which the plurality of chunk modules executes; and

at least one oracle module, wherein the at least one oracle module is configured to assign worker modules and bridge modules in response to requests received from chunk modules and from bridge modules for simulation of one or more entities not assigned to a worker module,

wherein the at least one receptionist module and the at least one oracle module each execute on a different server from at least one worker module of the plurality of worker modules, and

wherein the at least one oracle module is further configured to;

determine that a new worker module is needed based on a change in simulation workload; and

in response to determining that the new worker module is needed, instantiate and provision a new worker module on at least one server of the one or more computer servers on which the plurality of worker modules are distributed, wherein instantiating and provisioning the new worker module causes a bridge module associated with the new worker module to add one or more entities to an interest region associated with the new worker module and delegate write authority of one or more components within the interest region associated with the new worker module to the new worker module on the at least one server of the one or more computer servers on which the plurality of worker modules are distributed.

2. The spatially-optimized simulation system of claim 1, wherein the spatially-optimized simulation further comprises:

a data store module, wherein the data store module is configured to create and maintain a snapshot comprising a current state of each entity of the plurality of entities, and wherein the current state of each entity of the plurality of entities comprises a current value for each property of the one or more properties associated with the one or more components associated with the entity of the plurality of entities.

3. The spatially-optimized simulation system of claim 2, wherein the plurality of chunk modules are further configured to restore an entity using state information maintained by the data store module for the entity to be restored.

4. The spatially-optimized simulation system of claim 1, wherein the plurality of chunk modules are further configured to migrate an entity of the plurality of entities from a first chunk module of the plurality of chunk modules to a second chunk module of the plurality of chunk modules.

5. The spatially-optimized simulation system of claim 4, wherein migrating the entity of the plurality of entities from the first chunk module of the plurality of chunk modules to the second chunk module of the plurality of chunk modules comprises:

forwarding, by the first chunk module of the plurality of chunk modules and to the second chunk module of the plurality of chunk modules, state information of the entity;

causing, by the first chunk module of the plurality of chunk modules, the second chunk module of the plurality of chunk modules to receive state change notifications from the entity; and

stopping, by the first chunk module of the plurality of chunk modules, to receive state change notifications from the entity.

6. The spatially-optimized simulation system of claim 4, wherein migrating the entity of the plurality of entities from the first chunk module of the plurality of chunk modules to the second chunk module of the plurality of chunk modules is responsive to a determination made by the first chunk module of the plurality of chunk modules based on a load balancing algorithm.

7. The spatially-optimized simulation system of claim 4, wherein migrating the entity of the plurality of entities from the first chunk module of the plurality of chunk modules to the second chunk module of the plurality of chunk modules is responsive to a determination made by the entity based on a determination of a current spatial location of the entity.

8. The spatially-optimized simulation system of claim 1, wherein the at least one receptionist module is further configured to instantiate a bridge module prior to assigning the corresponding bridge module of the plurality of bridge modules.

9. The spatially-optimized simulation system of claim 1, wherein the at least one oracle module is further configured to maintain a first database comprising data indicative of a state of each worker module of the plurality of worker modules and is further configured to maintain a second database comprising data indicative of a state of each bridge module of the plurality of bridge modules.

10. The spatially-optimized simulation system of claim 1, wherein the at least one receptionist module is further configured to publish a predetermined network address for communicating with the receptionist module.

11. The spatially-optimized simulation system of claim 1, wherein the at least one oracle module is further configured to assign a worker module of the plurality of worker modules to a chunk module of the plurality of chunk modules in response to receiving a request from the chunk module of the plurality of chunk modules for a worker module.

12. The spatially-optimized simulation system of claim 1, wherein the at least one oracle module is further configured to instantiate a new worker module and assign the new worker module to a chunk module of the plurality of chunk modules in response to receiving a request from the chunk module of the plurality of chunk modules for a worker module.

13. The spatially-optimized simulation system of claim 1, wherein the memory stores additional computer-readable instructions that, when executed by the at least one computer processor, configure the system to connect to a plurality of client devices, and wherein the plurality of client devices connecting to the spatially-optimized simulation system are located in a plurality of different geographic locations.

14. The spatially-optimized simulation system of claim 1, wherein the plurality of bridge modules are configured to communicate with the plurality of worker modules through an application programming interface (API) exposed by each bridge module of the plurality of bridge modules.

15. A method comprising:

at a spatially-optimized simulation system comprising at least one computer processor and memory storing computer-readable instructions;

simulating a plurality of entities, wherein each entity of the plurality of entities comprises one or more components, and wherein each of the one or more components comprises one or more properties;

running a spatially-optimized simulation using a plurality of worker modules distributed over one or more computer servers, wherein each worker module of the plurality of worker modules performs a subset of the spatially-optimized simulation, wherein each worker module of the plurality of worker modules is configured to instantiate a subset of the plurality of entities and is further configured to update the one or more properties of at least one component of the one or more components of each entity in the subset of the plurality of entities instantiated by the worker module of the plurality of worker modules, wherein the plurality of worker modules comprises a first worker module and a second worker module, wherein the first worker module of the plurality of worker modules corresponds to a first game engine that simulates rigid-body physics for the spatially-optimized simulation, and wherein the second worker module of the plurality of worker modules corresponds to a second game engine that provides client-side rendering for the spatially-optimized simulation;

monitoring the plurality of entities using a plurality of chunk modules, wherein each chunk module of the plurality of chunk modules is configured to monitor a subset of entities assigned to the chunk module of the plurality of chunk modules, wherein the subset of entities assigned to the chunk module of the plurality of chunk modules are located within a chunk region assigned to the chunk module of the plurality of chunk modules, and wherein the plurality of chunk modules executes on at least one server different from the one or more computer servers on which the plurality of worker modules are distributed;

facilitating communications between the plurality of worker modules and one or more chunk modules using a plurality of bridge modules corresponding to the plurality of worker modules, wherein each bridge module of the plurality of bridge modules is configured to facilitate communications between a worker module of the plurality of worker modules and one or more chunk modules monitoring one or more entities being simulated on the worker module of the plurality of worker modules;

processing connection requests using at least one receptionist module, wherein the at least one receptionist module is configured to receive, from a plurality of client modules, at least one request for connecting to the spatially-optimized simulation system and is further configured to assign a corresponding bridge module of the plurality of bridge modules for communicating with each client module in response to receiving the at least one request for connecting to the spatially-optimized simulation, wherein at least one client module of the plurality of client modules executes on a device different from the one or more computer servers on which the plurality of worker modules are distributed and different from the at least one server on which the plurality of chunk modules executes; and

assigning worker modules and bridge modules using at least one oracle module, wherein the at least one oracle module is configured to assign worker modules and bridge modules in response to requests received from chunk modules and from bridge modules for simulation of one or more entities not assigned to a worker module,

wherein the at least one receptionist module and the at least one oracle module each execute on a different server from at least one worker module of the plurality of worker modules, and

wherein the at least one oracle module is further configured to;

determine that a new worker module is needed based on a change in simulation workload; and

in response to determining that the new worker module is needed, instantiate and provision a new worker module on at least one server of the one or more computer servers on which the plurality of worker modules are distributed, wherein instantiating and provisioning the new worker module causes a bridge module associated with the new worker module to add one or more entities to an interest region associated with the new worker module and delegate write authority of one or more components within the interest region associated with the new worker module to the new worker module on the at least one server of the one or more computer servers on which the plurality of worker modules are distributed.

16. The method of claim 15, wherein the plurality of chunk modules are further configured to restore an entity using state information maintained by a data store module for the entity to be restored.

17. The method of claim 15, wherein the plurality of chunk modules are further configured to migrate an entity of the plurality of entities from a first chunk module of the plurality of chunk modules to a second chunk module of the plurality of chunk modules.

18. The method of claim 17, wherein migrating the entity of the plurality of entities from the first chunk module of the plurality of chunk modules to the second chunk module of the plurality of chunk modules comprises:

forwarding, by the first chunk module of the plurality of chunk modules and to the second chunk module of the plurality of chunk modules, state information of the entity;

causing, by the first chunk module of the plurality of chunk modules, the second chunk module of the plurality of chunk modules to receive state change notifications from the entity; and

stopping, by the first chunk module of the plurality of chunk modules, to receive state change notifications from the entity.

19. The method of claim 17, wherein migrating the entity of the plurality of entities from the first chunk module of the plurality of chunk modules to the second chunk module of the plurality of chunk modules is responsive to a determination made by the first chunk module of the plurality of chunk modules based on a load balancing algorithm.

20. One or more non-transitory computer readable media storing computer executable instructions that, when executed by a spatially-optimized simulation system comprising at least one computer processor, cause the spatially-optimized simulation system to:

simulate a plurality of entities, wherein each entity of the plurality of entities comprises one or more components, and wherein each of the one or more components comprises one or more properties;

run a spatially-optimized simulation using a plurality of worker modules distributed over one or more computer servers, wherein each worker module of the plurality of worker modules performs a subset of the spatially-optimized simulation, wherein each worker module of the plurality of worker modules is configured to instantiate a subset of the plurality of entities and is further configured to update the one or more properties of at least one component of the one or more components of each entity in the subset of the plurality of entities instantiated by the worker module of the plurality of worker modules, wherein the plurality of worker modules comprises a first worker module and a second worker module, wherein the first worker module of the plurality of worker modules corresponds to a first game engine that simulates rigid-body physics for the spatially-optimized simulation, and wherein the second worker module of the plurality of worker modules corresponds to a second game engine that provides client-side rendering for the spatially-optimized simulation;

monitor the plurality of entities using a plurality of chunk modules, wherein each chunk module of the plurality of chunk modules is configured to monitor a subset of entities assigned to the chunk module of the plurality of chunk modules, wherein the subset of entities assigned to the chunk module of the plurality of chunk modules are located within a chunk region assigned to the chunk module of the plurality of chunk modules, and wherein the plurality of chunk modules executes on at least one server different from the one or more computer servers on which the plurality of worker modules are distributed;

facilitate communications between the plurality of worker modules and one or more chunk modules using a plurality of bridge modules corresponding to the plurality of worker modules, wherein each bridge module of the plurality of bridge modules is configured to facilitate communications between a worker module of the plurality of worker modules and one or more chunk modules monitoring one or more entities being simulated on the worker module of the plurality of worker modules;

process connection requests using at least one receptionist module, wherein the at least one receptionist module is configured to receive, from a plurality of client modules, at least one request for connecting to the spatially-optimized simulation system and is further configured to assign a corresponding bridge module of the plurality of bridge modules for communicating with each client module in response to receiving the at least one request for connecting to the spatially-optimized simulation, wherein at least one client module of the plurality of client modules executes on a device different from the one or more computer servers on which the plurality of worker modules are distributed and different from the at least one server on which the plurality of chunk modules executes; and

assign worker modules and bridge modules using at least one oracle module, wherein the at least one oracle module is configured to assign worker modules and bridge modules in response to requests received from chunk modules and from bridge modules for simulation of one or more entities not assigned to a worker module,

wherein the at least one receptionist module and the at least one oracle module each execute on a different server from at least one worker module of the plurality of worker modules, and

wherein the at least one oracle module is further configured to;

determine that a new worker module is needed based on a change in simulation workload; and

in response to determining that the new worker module is needed, instantiate and provision a new worker module on at least one server of the one or more computer servers on which the plurality of worker modules are distributed, wherein instantiating and provisioning the new worker module causes a bridge module associated with the new worker module to add one or more entities to an interest region associated with the new worker module and delegate write authority of one or more components within the interest region associated with the new worker module to the new worker module on the at least one server of the one or more computer servers on which the plurality of worker modules are distributed.