U.S. Pat. No. 10,918,943

The figures depict various embodiments of the present disclosure for purposes of illustration only. One skilled in the art will readily recognize from the following description that alternative embodiments of the structures and methods illustrated herein may be employed without departing from the principles, or benefits touted, of the disclosure described herein.

DETAILED DESCRIPTION

In the following description of embodiments, numerous specific details are set forth in order to provide more thorough understanding. However, note that the embodiments may be practiced without one or more of these specific details. In other instances, well-known features have not been described in detail to avoid unnecessarily complicating the description.

Embodiments relate to hexagonal fragmentation of terrain. Terrain data including locations on a terrain and corresponding hex identifiers of hexagonal terrain tiles of a three-dimensional topology to be placed at the locations are received at a computing device. Hex definition data corresponding to a hexagonal terrain tile includes a constraint condition imposed on an adjacent hexagonal terrain tile so that it can be placed adjacent to the hexagonal terrain tiles. A representation of the terrain is generated by instantiating the hexagonal terrain tiles at the locations indicated in the terrain data with faces of one or more of the hexagonal terrain adjoined to each other in compliance with the constraint condition.

Among other advantages, embodiments enable efficient transfer of terrain data with low latency. Furthermore, embodiments enable flexible terrain design and implementation, enabling greater customization and variety throughout the terrain. As such, both computing device performance and user experience may be improved. Hexagonal fragmentation of terrain also reduces demarcations between adjacent tiles, leading to a more organic and immersive terrain, further improving user experience.

Embodiments are described herein with reference to the figures where like reference numbers indicate identical or functionally similar elements. Also in the figures, the left most digit or digits of each reference number correspond to the figure in which the reference number is first used.

FIG. 1is a block diagram of a system100in which the techniques described herein may be practiced, according to an embodiment. The system100includes a content creator110, a server120, client devices140, and a network144. In other embodiments the system100may include additional content creators110or servers120, or may include a singular client device140.

The content creator110, the server120, and the client devices140are configured to communicate via the network144. The network144includes any combination of local area and/or wide area networks, using both wired and/or wireless communication systems. In one embodiment, the network144uses standard communications technologies and/or protocols. For example, the network144includes communication links using technologies such as Ethernet, 802.11, worldwide interoperability for microwave access (WiMAX), 3G, 4G, code division multiple access (CDMA), digital subscriber line (DSL), etc. Examples of networking protocols used for communicating via the network144include multiprotocol label switching (MPLS), transmission control protocol/Internet protocol (TCP/IP), hypertext transport protocol (HTTP), simple mail transfer protocol (SMTP), and file transfer protocol (FTP). Data exchanged over the network144may be represented using any suitable format, such as hypertext markup language (HTML) or extensible markup language (XML). In some embodiments, all or some of the communication links of the network144may be encrypted using any suitable technique or techniques.

The content creator110is a computing device, such as a gaming system, a personal computer, a mobile phone, a tablet, or so on, which includes and can execute a game level editor112. The game level editor112is a software application for designing terrains for one or more games. Terrains include one or more three-dimensional (“3D”) hexagonal terrain tiles (“hexes”) in a specific arrangement. The hexes, when positioned in the specific arrangement, form a particular 3D topology. Hexes and terrains are described in greater detail below with reference toFIG. 4.

A user of the content creator110uses the game level editor112to create terrains. For example, the user may use the game level editor112to piece together a variety of hexes into a desired arrangement to form a custom terrain. The user may use the game level editor112to rotate and/or move hexes, copy hexes, or so on while piecing together the hexes into the desired arrangement. The game level editor112may monitor one or more constraint conditions associated with each hex and prevent placement of a hex at a location if it breaches at least one constrain condition of at least one adjacent hex. The game level editor112may indicate the prevention and/or the at least one constraint condition to the user, such as at a user interface of the game level editor112displayed at a display of the content creator110. The user may use the game level editor112to specify other aspects of the game that involve the terrain, such as one or more objectives that occur at various locations upon the terrain, or objects to be included at various locations upon the terrain.

In one embodiment, the user can use the game level editor112to leave one or more locations upon the terrain empty, as gaps in the arrangement of hexes. In such an embodiment, the game level editor112, the server120, or the client device140uses a hex matching technique to automatically fill each empty terrain location with an appropriate hex. In this context, a hex is appropriate if it complies with the constraint conditions of each adjacent hex. Furthermore, in one embodiment, the game level editor112places wedges at appropriate locations about the hexes. Wedges are described in greater detail below with reference toFIG. 5. The game level editor112may save the custom terrain and/or send it to the server120and/or client devices140. The game level editor112may prevent the saving and/or sending of the custom terrain if the custom terrain includes one or more hexes breaching one or more constraint conditions of one or more adjacent hexes.

The server120is a computing device that includes a processor128and a memory130connected by a bus127. The memory130includes a hex data store122, a game level generator124, and a data object generator126. The server120may receive and route messages between the content creator110and the client devices140. Additionally, the server120may store in memory130one or more terrains, such as a terrain received by the server120from a content creator110, and send one or more terrains to the client devices140.

The processor128is capable of executing instructions, sequential or otherwise, that specify actions to be taken, such as performance of some or all of the techniques described herein. The bus127connects the processor128to the memory130, enabling data transfer from the one to the other and vice versa. Depending upon the embodiment, the server120may include additional elements conventional to computing devices, as known to a person having ordinary skill in the art.

The hex data store122stores hexes and terrains. For example, the hex data store122may store a template of each hex, as well as each permutation of the hex, as described below with reference toFIG. 4. The hex data store122also stores terrains received from content creators110or created by a creator of the game or administrator of the server120. The hex data store122may also store metadata associated with a hex or terrain, such as a hex identifier or a terrain identifier, an identifier of the creator of the hex or terrain, a size of the hex or terrain (as measured, for example, in megabytes (“MB”)), or so on. The hex data store122may also store information such as game objectives, objects, or so on that relate to the hex or terrain but are not necessarily part of the hex or terrain.

The game level generator124generates hexes and/or terrains. For example, the game level generator124generates a terrain using a hex matching technique that factors for constraint conditions. The hex matching technique may account for various other factors, depending upon the embodiment, such as a terrain size (e.g., a number of locations or hexes), a type of terrain (e.g., a “desert night” versus a “rainy jungle”), a game objective (e.g., “defeat 15 enemies”), or the like. The various other factors may be randomly generated, or received as input from an outside source, such as the game creator or the administrator of the server120.

In an embodiment, the game level generator124may generate new hexes. For example, the game level generator124may generate a new hex randomly, or based on input received from an outside source, or to fill a gap in a terrain that cannot be appropriately filled by an existing hex. The game level generator124generates a new hex by determining one or more constraint conditions for the hex, as well as a set of objects, e.g., graphical elements, audio assets, or interactive game components, to include within the hex. Based on the constraint conditions, the game level generator124generates a 3D topography for the hex, and situates each object in the set of objects at an appropriate position within the hex, based on constraint conditions of the objects and the hex. For example, in one embodiment, a “tree” object may be placed upon a “forest” portion of a hex, but not upon a “waterfall” portion of a hex.

The data object generator126generates data objects, such as JSON documents, for transmitting terrains. Terrains often include a large amount of data, large enough that uploading, transmitting, and downloading the data involves significant latency. Techniques described herein, including those pertaining to the data object generator126, address this latency by lessening the amount of data involved in transmitting a terrain.

Each hex, as described below with reference toFIG. 4, is associated with a hex identifier that distinguishes the hex from other hexes. When generating a data object, the data object generator126includes in the data object terrain data that includes one or more hex identifiers, where each hex identifier corresponds to at least one hex in the terrain described by the terrain data. The terrain data also includes a graph or other data structure describing the locations with respect to one another such that the terrain data represents the overall underlying structure of the terrain. Furthermore, the terrain data includes a mapping of locations to hex identifiers, such that the terrain can be properly reconstructed based on the terrain data by correctly associating each hex with a particular location within the terrain.

The data object generated by the data object generator126includes hex identifiers, locations, and so on, as described above, but not the full hex data of each hex. As such, the data object is much smaller than it would be if it contained the hex data of each hex. The data object is therefore conducive to more efficient, lower latency use, e.g. upload, transmittal, or download, than a full terrain is, and involves the use of fewer computing resources, e.g. processor cycles and active memory. The client devices140receive the data object and use locally stored hex data to reconstruct the terrain represented by the data object.

Each client device140is a computing device that includes a game or other software that uses a terrain. The client device140receives data objects from the server120and uses the data objects to construct terrains for use, for example, in the game. Different client devices140can request different data objects from the server120. For example, client device140A can request a first terrain from the server, client device140B can request a second terrain from the server120, and so on; client device140N can request an Nthterrain from the server120.

The server120may send a data object to a client device140that corresponds to the terrain requested by the client device140. For example, client device140A may receive a first data object corresponding to the requested first terrain, and so on. Client devices140include, for each hex, full hex data used to fill out a terrain when reconstructing the terrain based on its corresponding data object. Client devices140are further described with reference toFIGS. 2-4below.

FIG. 2is a block diagram of the client device140ofFIG. 1, according to an embodiment. Depending upon the embodiment, the content creator110and/or server120may comprise a computing device that includes some or all of the hardware and/or software elements of the client device140described herein. The client device140, content creator110, and/or server120are any machine capable of executing instructions, and may each be a standalone device or a connected (e.g. networked) set of devices. For example, in one embodiment, the content creator110is a client device140.

The client device140includes a central processing unit (“CPU”)202, a graphics processing unit (“GPU”)204, a primary memory206, a secondary memory214, a display controller208, a user interface210, and a sound controller212that are connected by a bus216. While only a single client device140is illustrated, other embodiments may include any collection of client devices140that individually or jointly execute instructions to perform any one or more of the methodologies discussed herein.

The primary memory206is a machine-readable medium that stores instructions (e.g., software) embodying any one or more of the methodologies or functions described herein. For example, the primary memory206may store instructions that, when executed by the CPU202, configure the CPU202to perform a process700, described below in detail with reference toFIG. 7. Instructions may also reside, partially or completely, within the CPU202and/or GPU204, e.g., within cache memory, during execution of the instructions.

The term “machine-readable medium” should be taken to include a single medium or multiple media (e.g., a centralized or distributed database, or associated caches and servers) able to store instructions. The term “machine-readable medium” shall also be taken to include any medium that is capable of storing instructions for execution by the device and that cause the device to perform any one or more of the methodologies disclosed herein. The term “machine-readable medium” includes, but is not limited to, data repositories in the form of solid-state memories, optical media, and magnetic media.

The secondary memory214is a memory separate from the primary memory206. Similar to the primary memory206, the secondary memory214is a machine-readable medium that stores instructions (e.g., software) embodying any one or more of the methodologies or functions described herein. For example, the primary memory206may be a hard drive of the client device140, and the secondary memory214may be a game disc for the game that uses the terrain. As a specific example, the primary memory206may store a game system300that uses hex data stored on the secondary memory214. Primary memory206and secondary memory214are described in greater detail with reference toFIG. 3below.

The CPU202is processing circuitry configured to carry out the instructions stored in the primary memory206and/or secondary memory214. The CPU202may be a general-purpose or embedded processor using any of a variety of instruction set architectures (ISAs). Although a single CPU is illustrated inFIG. 2, the client device140may include multiple CPUs202. In multiprocessor systems, each of the CPUs202may commonly, but not necessarily, implement the same ISA.

The GPU204is a processing circuit specifically designed for efficient processing of graphical images. The GPU204may render objects to be displayed into a frame buffer (e.g., one that includes pixel data for an entire frame) based on instructions from the CPU202. The GPU204may include one or more graphics processors that may execute graphics software to perform a part or all of the graphics operations.

The display controller208is a circuit that generates a video signal using graphical data from the GPU204. For example, the display controller208drives a display device (e.g., a liquid crystal display (LCD) and a projector). As such, a game, including terrain, can be displayed as images or a video sequence through the display controller208.

The sound controller212is a circuit that provides input and output of audio signals to and from the client device140. For purposes of a terrain, the sound controller212can provide audio signals that align with actions and objects in the terrain, e.g. at particular hexes, or parts of hexes.

The user interface210is hardware, software, firmware, or a combination thereof that enables a user to interact with the client device140. The user interface210can include an alphanumeric input device (e.g., a keyboard) and a cursor control device (e.g., a mouse, a trackball, a joystick, a motion sensor, or other pointing instrument). For example, a user uses a keyboard and mouse to control a character's action within a game environment that includes a terrain rendered by the client device140. The game environment includes a simulation and rendering of the terrain, within which the user's game character operates.

The client device140executes computer program modules for providing functionality described herein. As used herein, the term “module” refers to computer program instructions and/or other logic used to provide the specified functionality. Thus, a module can be implemented in hardware, firmware, and/or software. In some embodiments, program modules formed of executable computer program instructions are loaded into the memory206, and executed by the CPU202or the GPU204. For example, program instructions for the process700describe herein can be loaded into the primary memory206and/or secondary memory214, and executed by the CPU202and GPU204.

FIG. 3is a block diagram of software modules in a memory of the client device140ofFIG. 1, according to an embodiment. In particular,FIG. 3illustrates software modules in the primary memory206and the secondary memory214of the client device140. The primary memory206may store, among other modules, a game system300and an operating system (“OS”)380. The secondary memory214may store, among other modules, a content source312. The primary memory206and secondary memory214may include other modules not illustrated inFIG. 3. Furthermore, in other embodiments, the primary memory206and secondary memory214may each store software modules and data represented herein as stored in the other.

The game system300includes a level manager320, a physics system330, a sound module340, a terrain generator350, an animation module360, and a graphics rendering module370. These modules collectively form a “game engine” of the game system300.

The game system300performs operations312A through312N (collectively referred to as “the operations312”) to generate the game environment, including the terrain. Specifically, the game system300performs these operations312to construct the terrain, instantiate various objects upon the terrain (e.g., the user's game character), and simulate interactions between the objects. The operations312refer to computing operations that result in changes in various parameters (e.g., states of objects and user status) based upon certain events (e.g., user interactions, expirations of time, and triggers occurring in the game).

Some operations312are associated with one or more objects, hexes, or positions within hexes in the game environment, and/or one or more actions associated with the objects, hexes, or positions within hexes. Examples of operations include a catapult launching a rock, a character running, fluid flowing, an arrow flying, a door opening, and so on. While some operations312have relatively simple responses (e.g., door opening), other operations may need to be simulated by the physics system330(e.g., movement of connected bodies). When executing the operations312, the game system300may communicate with the components of the game engine (e.g., physics system330) through application programming interfaces (APIs). At least one of these operations312involves constructing the terrain from terrain data and hex data.

The level manager320receives data objects, i.e., level data322, from the server120and stores the level data322in the primary memory206. Other modules of the game system300can request one or more levels from the level manager320, which responds to the requests by sending the level data322corresponding to the requested level to the module of the game system300that sent the request. Alternatively, the level manager320may construct a terrain template from the level data322. The terrain template is a terrain without hex data. For example, the terrain template is a graph of locations, where each location in the graph is associated with a hex identifier. The terrain template or other terrain data324may be sent, for example, to the terrain generator350, such as in response to a request from the terrain generator350for the terrain data324. Terrain data324may include any level data322, depending upon the embodiment.

The terrain generator350generates a complete terrain based on terrain data324and hex data. The terrain generator350receives terrain data324from the level manager320and hex and object data from the content source312in the secondary memory214, as described in greater detail below. In one embodiment, the terrain generator350uses hex data to fill in a terrain template. For example, for each location within the terrain template, the terrain generator350uses the associated hex identifier to retrieve hex data for the hex identified by the hex identifier. The terrain generator350uses the retrieved hex data to construct the terrain, combining the retrieved, full hex data to turn the terrain template into a complete terrain that includes the full hex data (rather than just hex identifiers).

The physics system330models and simulates the dynamics of objects in the game environment. After an operation312is initiated in the game system300, the physics system330models how the action affects the object associated with the operation312. For example, the physics system models a rock as it rolls down a hill. Depending on the action and object, other objects and actions may become associated with the action or object. For example, a thrown rock may knock over another object. This may trigger a new operation312where the object is hit by the rock. The physics system330uses terrain information, e.g. data pertaining to a terrain generated by the terrain generator350, when modeling and simulating the dynamics of the objects in the game environment. For example, returning to the rolling rock example, the physics system330may determine that the rock must roll down the hill by identifying that the rock is positioned within the terrain such that it is on a slope of the hill.

The animation system360is a module that performs kinematic animation of objects or the game environment based on the operations312from the game system300. For example, if an operation312specifies that a robotic arm is moving, the animation system animates the kinematics of the arm movement. The animation system360may include any number of specialized modules which perform specific animation tasks. The animation system360may use information pertaining to a terrain generated by the terrain generator350as a factor in the performance of kinematic animation of objects or the game environment.

The sound module340generates sounds corresponding to actions occurring in the game environment or to hexes or portions of hexes. For example, a portion of a hex including a “river” object may correspond to a “flowing water” sound. Animation data from the animation system360or terrain information from the terrain generator350may be sent to the sound module340to enable the sound module340to produce sound. The sound module340sends sound data to the sound controller212.

The graphics rendering module370renders graphics from the animation system360and terrain generator350to generate an image of the game environment. For example, the graphics rendering module370receives a scene file from the animation system360and a generated terrain from the terrain generator350. The graphics rendering module370sends graphical data to the GPU204to render images on a display, e.g. a display of the client device140or a display connected to the client device140, via the display controller208.

The OS380manages computer hardware and software resources. Specifically, the OS380acts as an intermediary between programs and the computer hardware. For example, the OS380can perform basic tasks, such as recognizing input from the user interface210and sending output to the display controller208.

The content source312includes various hex data and object data, including a hex definition module260, an object information module262, a patch hex definition module264, and a patch object information module266. The content source312sends hex data to the terrain generator350upon receiving a request for the hex data from the terrain generator350. For example, upon receiving a request for hex data corresponding to a particular hex identifier, the content source312sends the hex data (and/or object data) corresponding to the particular hex identifier (and any object identifiers associated with the hex identifier) to the terrain generator.

The hex definition module260includes hex definition data for each hex and each permutation of each hex. As described below with reference toFIG. 4, each hex has one or more permutations that are alternative ways of using the hex, such as various rotations of the hex, various lighting conditions of the hex, or so on. The hex definition module260includes this permutation data as well as the full hex data for each hex. The full hex data is the complete set of data pertaining to the hex referred to by a hex identifier. For example, the full hex data may include data describing the 3D topography represented by the hex, various features of the hex, various lighting permutations, and so on. Features of the hex may include geographic elements, such as roads, forests, rivers, hills, and so on, that are included within the hex at particular locations within the hex.

The object information module262stores object information. Object information is data pertaining to objects within the game environment, such as the user's game character, non-player characters (“NPC' s”), and other interactive game elements (e.g. weapons, tools, clothes, rocks, doors, etc.). Objects can be associated with hexes or positions within hexes. For example, a user of the game level editor112may add a tool to a position within a hex when designing a terrain. This information is included in the data object when the server120sends the terrain to the client device140. For example, each object may be associated with an object identifier, and the data object may include the object identifiers of each object included in the terrain such that the terrain generator350can reconstruct the terrain from the data object and data from the content source312.

Patches are updates or additions to software modules or data that are typically applied to the software modules or data after it is loaded into a memory. For example, a patch may be applied to a software module several weeks after the release and downloading of the software module by client devices140in order to address one or more bugs in the software module, or to add new content to the software module. As a specific example, a patch to the content source312may add new hex data or object data, such as a new “jungle” hex, a new permutation for each extant hex, or a new object, such as a hat.

The patch hex definition module264and the patch object information module266incorporate patch information that involves hex data and object data, respectively. For example, the client device140may download a patch over the network144, such as a patch provided by the server120or the content creator110. The client device140may then send the patch to the content source312. The patch hex definition module264incorporates hex data included in the patch, such as a new hex, into the hex definition module260, and the patch object information module266incorporates object data included into the patch, such as a new object, into the object information module262.

FIG. 4Ais a block diagram of level data322used by the software modules in the memory of the client device ofFIG. 1, according to an embodiment. The level data322represents a terrain and includes terrain data324describing the terrain. The level data322may also include other information, such as game objectives or objects associated with the terrain. In an embodiment, the level data322is the data object sent by the server120to the client device140. The level data322includes a graph or other data structure describing the locations within the terrain with respect to one another such that the terrain data324represents the overall underlying structure of the terrain. In an embodiment, locations are numbered, beginning with a central location, and then spiraling outward clockwise; the terrain generator350may use this information to properly construct the terrain such that each hex is at the proper location, and each location is situated properly within the terrain with respect to one another. For example, as in the figure, the locations may be labeled “location 0,” “location 1,” and so on, to a Zthlocation.

Each location within the terrain data324is associated with a hex identifier, a hex orientation, and a set of game play parameters. The hex identifier associated with the location indicates the hex that the terrain generator350should place at the location. The hex orientation indicates a particular permutation of the hex to use. Hexagons have six sides, and hexes, which are 3D, are hexagonal prisms with a top, a bottom, and six faces. As such, there are six possible rotation permutations for each hex, each where a different face of the hex faces the same direction (i.e., the hex is rotated a multiple of 60 degrees). The hex orientation indicates which rotation permutation is associated with the location. The set of game play parameters may include, depending upon the embodiment, a lighting permutation, various object identifiers associated with the location or the hex represented by the hex identifier, or so on. Lighting permutations are discussed below with reference toFIG. 4B. Object identifiers included in the set of game play parameters indicate objects that the terrain generator350is to place within the terrain at the hex represented by the hex identifier. The set of gameplay parameters may further include information specifying where each object should be placed within the hex. In other embodiments the set of game play parameters may include additional or different data, such as data pertaining to one or more game play objectives. In an embodiment, rather than having a hex identifier, a hex orientation, a lighting permutation, and so on, every possible overall permutation of a hex has a different hex identifier, and the terrain data324simply includes, for each location, the hex identifier and a set of game play parameters.

FIG. 4Bis a block diagram of hex data used by the software modules in the memory of the client device ofFIG. 1, according to an embodiment. In particular,FIG. 4Billustrates hex definition data260, according to one embodiment. The hex definition data260includes full hex data for each hex, which, in one embodiment, is indexed by hex identifier. Each hex is associated with a hex identifier, edge constraints, vertex constraints, placement information, lighting solutions, and permutation information. As described above, the hex identifier distinguishes the hex from other hexes. For example, the hex identifier may an alphanumeric string.

Edge constraints are constraint conditions relating to one or more faces of a hex. Edge constraints may include a constraint upon a type of face, such that a face of a hex may only be placed within the terrain such that it borders a face of an adjacent hex that has the same type of face. For example, a first hex has a first face with a first type of face. The first hex may be placed within a terrain only at locations where the first face borders a second face of a second hex that also has the first type of face. As a specific example, if the first face of the first hex is a “river” type of face, then the first hex may be placed adjacent to the second hex with the first face and the second face bordering one another only if the second face is also a “river” type of face. Each face of a hex may include one or more edge constraints, which may restrict the type of face the face can border. However, for some types of faces, faces with those types of faces may border other hexes with any of a set of types of faces. For example, in an embodiment, a face with a “grassland” type of face may border a face of an adjacent hex that has either a “grassland” type of face, or a “forest” type of face. Depending upon the embodiment, hex faces may have additional edge constraints. Edge constraints are further described below with reference toFIG. 6B.

Vertex constraints are constraint conditions relating to the six vertices of a hex. Each vertex of the hex has a height level, such as “low,” “medium,” and “high.” More or fewer than three height levels may be used. The height level of a vertex corresponds to the topography of the hex at the vertex. For example, if two vertices on either side of a face of the hex are “high,” then that face of the hex, from the one vertex to the other, may be a peak of a hill, or so on. If one of the two vertices is “high” and the other is “medium,” the topography of the hex at that face of the hex may be a slope, such as a side of a hill or a staircase, or may include a cliff that changes the topography from “high” to “medium” along the face of the hex.

In an embodiment, vertex constraints limit which height levels a vertex of a particular height level may be adjacent to. For example, in one embodiment, adjacent vertices cannot be more than one height level different from one another, e.g. a “low” cannot be next to a “high” but can be next to a “low” or a “medium.” Vertex constraints may differ depending upon whether an adjacent vertex is within the same hex or is in an adjacent hex. For example, a vertex constraint may be that adjacent vertices in adjacent hexes must be of the same height, but adjacent vertices within the same hex may vary by up to one height level. Vertex constraints are further described below with reference toFIG. 5.

Placement information is additional information pertaining to where a hex may be placed. Some hexes may have constraint conditions in addition to edge constraints and vertex constraints. For example, in an embodiment, hexes of a particular lighting permutation may only be placed adjacent to other hexes with the same lighting permutation, or hexes with a lighting permutation of a subset of the set of lighting permutations. Other constraint conditions included in placement information may have to do with game objectives, objects within tiles, or so on.

Lighting solutions are lighting permutations of a hex, and data pertaining to the implementation of the lighting permutations. Lighting permutations exist for each of the six possible rotations of a hex. Furthermore, for each of the six possible rotations of the hex, there are lighting permutations for each lighting condition of a set of lighting conditions, which includes one or more different lighting conditions, such as “morning,” “daytime,” “afternoon,” “evening,” “rainy day,” “nighttime,” and so on. For example, a hex with four different lighting conditions would have 24 total lighting permutations—four for each of the six possible rotations of the hex.

Lighting solutions may be implemented in a variety of ways. In one embodiment, the lighting solutions are implemented using image-based lighting. Image-based lighting (“IBL”) is a 3D rendering technique where omnidirectional representations of light information is captured as an image, which is projected onto a shape, such as a box or a sphere. The shape, a “light probe,” is placed within the terrain and used to simulate the light from the environment. Hexes may contain a plurality of these light probes spread throughout the hex, to provide realistic lighting. In an embodiment, light probes may overlap multiple hexes, e.g. at a border between two hexes. The light probe is split in two, with one half in each hex, each providing light information for the other hex.

Permutation information is data relating to the six possible rotations of a hex. Each rotation of the hex appears different when rendered. As such, the permutation information includes graphical data for each of the six rotations of the hex. For example, for one permutation, the hex includes a river at a Northern part of the hex, while in a second permutation, the river is at an Eastern part of the hex. These permutations are both included in the permutation information. In an embodiment, the lighting permutations are included in the permutation information, with each rotation permutation including data for each lighting permutation. As mentioned above, in one embodiment, each possible overall mutation of each hex has its own hex identifier. In such embodiments, the lighting solutions and/or permutation information includes just one rotation and one lighting condition; other rotations and lighting conditions are associated with other hex identifiers within the hex definition data260.

FIG. 5is an illustration of a hexagonal terrain, according to an embodiment. The terrain includes19hexes placed at19locations within the terrain, arranged in an asymmetric pattern.FIG. 5also includes seven wedges, as well as a plurality of vertices and faces at each hex.FIG. 5includes an occupied hex502, which is a hex occupied by a user's game character.

When rendering the terrain, the client device140may add wedges, such as wedge510, around part or all of the terrain. Wedges are hexes or portions of hexes, e.g. triangular geometries, which bound the terrain based on the vertex constraints of the hexes bordered by the wedges. For example, a wedge that borders a hex face which extends from a first vertex to a second vertex. If the first vertex is “high” and the second vertex is “medium,” then the wedge may include a sloping wall from the first vertex to the second vertex that parallels the change in height from the first vertex to the second vertex and is impassible to objects and game characters, particularly the user's game character. In an embodiment, a module of the game system300, such as the terrain generator350, adds one or more wedges to the terrain when constructing the terrain, rather than at render time. In one embodiment, each wedge vertex that borders a hex vertex is one height level greater than the height level of the hex vertex.

The occupied hex502is a hex occupied by the user's game character. When rendering the terrain, the game system300may render only a portion of the terrain at a time. In one embodiment, the game system300renders the occupied hex502and each hex directly bordering the occupied hex502. For example, the hex between the occupied hex502and hex506would be rendered, but hex506would not be rendered. This may be done to save computing resources, or to accommodate a limitation upon active memory or processing power. In other embodiments, different subsets of the hexes in the terrain may be rendered, such as only hexes within a line of sight of the user's game character, or hexes that border either the occupied hex502or a hex that borders the occupied hex502.

Several vertex constraints are illustrated inFIG. 5. In one embodiment, vertices which converge at a point, such as vertices515A-C, must be the same height level. For example, if the hex containing vertex515B were added to the terrain and vertex515B was “high,” then the hexes containing vertices515A and515C could only be placed if vertices515A and515C were also “high.” In alternative embodiments, the vertices515could border each other only if no vertex515was more than one height level from any other bordering vertex515.

FIG. 6Ais an illustration of a terrain height constraint condition of hex506, according to an embodiment. In particular, several height levels605are illustrated. Each hex has at least two height levels605, and in some embodiments may have more than three height levels605. Height level605A is a “low” height level, height level605B is a “medium” height level, and height level605C is a “high” height level. The 3D topography included within a hex can vary among height levels. A first tile may be a grassland that is entirely at level605A. A second tile may be a series of hills that varies between levels605A-B throughout the hex. A third tile may be a large mountain centered within the hex, where the outskirts of the hex are low, the middle of the hex is high, and the space between is medium.

FIG. 6Bis an illustration of a hexagonal tile, according to an embodiment.FIG. 6Billustrates hex506as well as several features of the hex506. The hex506has a face610with endpoints at vertices615and630, and includes an object425and a river620. The object425is an interactive game component that may be placed within the hex506. For example, the object425may be a rock that the user's game character can pick up, or may be an enemy that attacks the user's game character when approached. Depending upon the embodiment, hexes automatically include one or more objects, objects are added to hexes via the game level editor112, or both.

The river620is a topological feature included in the hex506which extends to a face of the hex506. The river620is an edge constraint of the hex506. A second hex placed such that it borders the hex506at the face intersected by the river620must also have a river feature at its face which borders the hex506. If a wedge is placed bordering the face intersected by the river620, the wedge may include a waterfall or other element which pertains to the river. Similarly, hexes or wedges placed within the terrain must comply with the edge constraints of the hexes which they border. Another example of an edge constraint may be a road.

A border hex placed such that it borders the hex506at the face610must comply with constraint conditions pertaining to the face610and the vertices615,630which bound it. In an embodiment, the border hex has a first vertex which, like vertex615, is “L,” or “low,” and a second vertex which, like vertex630, is “M,” or “medium,” each of which borders the vertex615,630of corresponding height level. As seen in the figure, each vertex has a height level, and no vertex is more than one height level different from a neighboring vertex.

FIG. 7is a flowchart illustrating a process for implementing the techniques described herein, according to an embodiment. The client device140receives702terrain data including locations on a terrain and corresponding hex identifiers of hexagonal terrain tiles of a three-dimensional topology to be placed at the locations. For example, the client device140receives a data object from the server120.

The client device140retrieves704hex definition data corresponding to the hexagonal terrain tiles included in the terrain data, the hex definition data for each of the hexagonal terrain tiles including at least a constraint condition on an adjacent hexagonal terrain tile eligible for placement adjacent to the hexagonal terrain tiles. The constraint condition may be, for example, a vertex constraint or an edge constraint.

The client device generates706a representation of the terrain by instantiating the hexagonal terrain tiles at the locations indicated in the terrain data with faces of one or more of the hexagonal terrain adjoined to each other in compliance with the constraint condition associated with each of the hexagonal terrain tiles. Instantiating the hexagonal terrain tiles may include rendering the terrain.

In an embodiment, the hex definition data further includes a plurality of light solutions, each of the light solutions represented by a collection of light probes for determining appearance of objects in a hexagonal terrain tile in a different lighting condition.

In an embodiment, the hex definition data further includes placement information indicating locations of objects in each of the hexagonal terrain tiles.

In an embodiment, the hex definition data further includes permutation information representing variations applicable to each of the hexagonal terrain tiles.

In an embodiment, the process further comprises determining, by the client device140, compliance of the constraint condition of one or more the hexagonal terrain tiles.

In an embodiment, the terrain data is included in a game level data received from another computing device, such as a content creator110or a server120, and the game level data further includes at least an objective of the game level.

In an embodiment, the terrain data further includes an orientation of each of the hexagonal terrain tiles.

In an embodiment, the terrain data further comprises game play parameters indicating restrictions on objects or characters to appear in each of the corresponding locations. For example, based on a game objective, various restrictions may be placed upon which objects or characters may be placed in a hex, and where in the hex they may be placed.

In an embodiment, the hex definition data comprises original hex definition data stored on a read-only storage medium and a supplemental hex definition data received from another computing device in a patch or an expansion pack.

In an embodiment, the terrain data indicates placing of a wedge adjacent to at least one of the hexagonal terrain tiles.

In an embodiment, responsive to information on a hexagonal terrain tile for a location in the terrain missing from the terrain data, the client device140automatically determines a hexagonal terrain tile for the location with the missing information in compliance with the constraint condition associated with hexagonal terrain tiles adjacent to the location.

Although embodiments described above are explained primarily in reference to a game system, the embodiments may be applied to other applications such as engineering software, navigational software, and educational software, such as a map application or a ride hailing application. Additionally, embodiments can be applied to research applications.

While particular embodiments and applications have been illustrated and described, it is to be understood that the invention is not limited to the precise construction and components disclosed herein and that various modifications, changes and variations which will be apparent to those skilled in the art may be made in the arrangement, operation and details of the method and apparatus disclosed herein without departing from the spirit and scope of the present disclosure.