U.S. Pat. No. 12,403,394

DETAILED DESCRIPTION

This specification describes methods and systems for selecting actions in a video game using an intent-based model. Methods and systems described in this specification enable players to reach a desired outcome without having to manually perform each of the individual actions used to reach the desired outcome. For example, in many video games, players may have to choose from a large number of different actions, which actions may differ depending on the entity/character they are controlling and the current state of the entity/character. An outcome may be reached in different ways, with outcomes reached from particular states being more valuable (e.g. more strategically beneficial) than those reached from other states. In addition, some actions from states may only be available in a few game contexts, which players may not be aware of. As such, players may face difficulties in selecting which actions to perform to reach the best outcome and/or the closest outcome.

The methods and systems described in this specification enable players of the video game to select a small number of controls (e.g. a button press and/or moving a stick in a particular direction) corresponding to an intent to reach a desired outcome, by determining a sequence of actions which takes into account any contextual actions that may become available over time. The methods and systems described in this specification may also be used in a tutorialized system which teaches players which controls they should have selected to perform the actions used to reach the desired outcome. In addition, the methods and systems described in this specification may be used by entities which are not controlled by players (e.g. an AI of the video game) in order to select actions.

The described systems and methods may be implemented in any appropriate video game. For example, the described systems and methods may be used in a fighting game to select grappling movements from various grappling positions and for various characters. A grappling position of a character may be represented by a state, with the actions that a player may choose at a point in time being the various grappling movements available for the character from the current grappling position. Contextual actions may be actions that are only available when other factors are taken into account, such as how close two fighters are, and the stamina of the fighters.

In this example, the different outcomes may be outcomes such as those reached from performing a “submission” action, a “ground and pound” action, or a “get up” action. As these outcomes may be reached from a number of different grappling positions available from the current grappling position, and certain outcomes may be more effective in winning the fight than others, a desired outcome might be the best outcome or the closest outcome. For example, the player may select controls to indicate an intent to reach the best “ground and pound” outcome, and a sequence of actions may be determined to reach the best “ground and pound” outcome from the current grappling position. Similarly, the player may select further controls to indicate an intent to reach the closest “submission” outcome, and a sequence of actions may be determined to reach the closest “submission” outcome from the current grappling position.

As another example, the described systems and methods may be used in action-adventure games which may involve, for example, a player driving to different destinations in a city. An intersection of two or more roads may be represented by a state, with the actions that a player may choose at a point in time being the various roads available from the current intersection. Contextual actions may be those available when shortcuts are available, such as when an obstacle clears a path that may be used to reach a destination.

In this example, the different outcomes may be outcomes such as those reached from driving to different destinations, e.g. police stations, banks, and safehouses. As these destinations may be reached by a variety of routes, and certain destinations may be more valuable than others, a desired outcome might be the best outcome or the closest outcome. For example, the player may select controls to indicate an intent to reach the best police station, and a sequence of roads may be determined to reach the best police station from the current intersection. Similarly, the player may select further controls to indicate an intent to reach the closest safehouse, and a sequence of roads may be determined to reach the closest safehouse from the current intersection.

This specification also describes systems and methods for generating intent-based models for use in selecting actions in a video game. For example, an intent-based model may be generated by performing a path-finding algorithm on a graph. The described systems and methods may enable the generation of computationally efficient intent-based models and obviate the need to perform path-finding algorithms at runtime. For example, the graph may comprise transitions corresponding to actions that are always available for an entity. Values determined from performing the path-finding algorithm on the graph (such as scores of states, scores of best outcomes on paths from states, distances to best outcomes on paths from states, and/or distance to closest outcomes on paths from states) may be stored as part of the intent-based model for use in runtime when a player is playing the video game. At runtime, actions may be selected by comparing these values for states which are currently available from the current state, which may include states reached by contextual actions in addition to states reached by actions that are always available for the entity. By obviating the need to perform path-finding algorithms at runtime, actions can be selected by a linear time algorithm that determines which states can be reached from the current state.

FIG.1shows an example of a portion of a graph100used for generating an intent-based model for use in selecting actions in a video game. The graph100shown inFIG.1shows an example of a graph determined during the method described in relation toFIG.2. The graph100represents which actions, or transitions, can be taken from different states of the video game, and the value in reaching different outcome states. Although graph100shows a directed graph, it will be appreciated that the methods described herein may be applied to undirected graphs. For example, an undirected graph may be converted into a directed graph by replacing undirected edges with parallel directed edge pairs.

The graph100comprises a plurality of nodes102-1,102-2,102-3,102-4. Each node102-1,102-2,102-3,102-4of the graph100represents a state of an entity in a video game. The entity may be a character, a vehicle, or any other appropriate component of a video game.

The graph100further comprises a plurality of edges104-1,104-2,104-3,104-4,104-5. Each edge104-1,104-2,104-3,104-4,104-5from a node represents a transition from a first state to a second state. For example, edge104-1represents a transition from a state corresponding to node102-1to a state corresponding to node102-2. Each edge104-1,104-2,104-3,104-4,104-5is weighted, for example edge104-1has a weight of 0 and edge104-2has a weight of 1. A weight of an edge may be determined based on whether the transition can be blocked, e.g. by another player. For example, a weight of 1 may indicate that the transition can be blocked, whereas a weight of 0 may indicate that the transition is an instant transition. The weight of an edge corresponds to the distance between the two nodes connected by the edge.

Edges104-1,104-2,104-3,104-5represent transitions which are always available for the entity. Edge104-4represents a contextual transition. Contextual transitions are transitions that depend on a current context of the video game and are ones that are not always available for the entity from a state. At runtime, if certain conditions are satisfied, an entity in the second state corresponding to node102-2may be able to transition directly to the fourth state corresponding to node102-4without first transitioning to the third state corresponding to node102-3. Contextual edge104-4may be removed from the graph100(or alternatively, not added to the graph100during building of the graph100) during the method described in relation toFIG.2.

FIG.1also shows a plurality of outcome nodes106-1,106-2,106-3,108-1,108-2,110-1,110-2for the graph100. The plurality of outcome nodes represent outcome states which are immediately available from the state to which the outcome node is connected. For example, outcome node108-1being connected to node102-1represents that an outcome state is immediately available from a first state corresponding to node102-1. Outcome nodes106-1,106-2,106-3represent outcome states for a first outcome denoted by a triangle inFIG.1, outcome nodes108-1,108-2represent outcome states for a second outcome denoted by a square inFIG.1, and outcome nodes110-1,110-2represent outcome states for a third outcome denoted by a pentagon inFIG.1. Outcome nodes may be terminal nodes, e.g. endpoints.

Each outcome node has a respective score, for example outcome node106-1has a score of 2, and outcome node110-2has a score of 4. Each outcome node may be scored on a function that is specific to that outcome node. For example, an outcome node may be scored based on a level of the entity/character. As shown inFIG.1, different outcome states for the same outcome may have different scores. For example, the triangle outcome state of outcome node106-1immediately available from the second state corresponding to node102-2has a score of 2 whereas the triangle outcome state of outcome node106-3immediately available from the fourth state corresponding to node102-4has a score of 5. The scores of outcome nodes are used to determine scores for the states from which an outcome node is immediately available, as will be described in relation toFIGS.2and3.

In the example of a fighting game, the nodes102-1,102-2,102-3,102-4may correspond to grappling positions of a fighter. For example, node102-1may represent a fighter being in a guard position, node102-2may represent the fighter being in a half-guard position, node102-3may represent the fighter being in a side control position, and node102-4may represent the fighter being in a full mount position.

A set of three outcomes may be given with the first outcome of outcome nodes106being a ‘ground and pound’ outcome, the second outcome of outcome nodes108being a ‘submission’ outcome, and the third outcome of outcome nodes no being a ‘get up’ outcome. In this example, outcome node108-1is a ‘submission’ outcome state representing a ‘submission’ outcome being immediately available from the dominant role of the guard position for the fighter, and outcome node110-2is a ‘get up’ outcome state representing a ‘get up’ outcome being immediately available from the full mount position for the fighter. The score of an outcome node may represent a value of the entity reaching the outcome state of the outcome node.

Each edge104-1,104-2,104-3,104-4,104-5may represent a grappling movement between two grappling positions. The weight of the edge may be determined based on whether the grappling movement can be blocked by an opponent. For example, edge104-2having a weight of 1 indicates that the grappling movement from the half-guard position to the side control position can be blocked by an opponent. Edge104-4is a contextual edge representing a contextual transition from the half-guard position to full mount position. Edge104-4may become available to the fighter in certain contexts of the fight, for example if the stamina of the opponent is sufficiently low.

FIG.2shows a flow diagram of an example method200of generating an intent-based model for use in selecting actions in a video game. The below description will refer to elements ofFIG.1for illustrative purposes.

In step2.1, a graph comprising a plurality of nodes is initialized. Each node of the plurality of nodes represents a state of an entity in the video game. For example, the plurality of nodes may comprise the nodes102-1,102-2,102-3,102-4described in relation toFIG.1.

In step2.2, one or more edges are added to the graph. Each edge of the one or more edges represents a transition from a first state to a second state. The method200may comprise determining that each transition of the one or more edges is a transition that is always available for the entity. The method200may comprise determining a weight for each edge in dependence on whether the transition can be blocked (e.g. blocked by another player). For example, the one or more edges may comprise the edges104-1,104-2,104-3,104-5described in relation toFIG.1. Edges corresponding to contextual transitions such as edge104-4described in relation toFIG.1may be absent from the one or more edges added to the graph.

In step2.3, for each node of the plurality of nodes, a distance to each other node is determined. The method200comprises performing a path-finding algorithm on the graph. The graph may only include nodes102-1,102-2,102-3,102-4and not outcome nodes106-1,106-2,106-3,108-1,108-2,110-1,110-2when performing the path-finding algorithm on the graph. The path-finding algorithm may use Dijkstra's algorithm to calculate distances between nodes. Dijkstra's algorithm is a known algorithm for finding the shortest paths between nodes of a weighted graph. The path-finding algorithm may use determined weights of edges in order to calculate distances between nodes. The path-finding algorithm may be used to determine paths from each node to each other node of a minimal distance.

In step2.4, one or more outcome nodes are determined. Each outcome node corresponds to a state of the entity at an outcome out of a set of outcomes. For example, the one or more outcome nodes may comprise the outcome nodes106-1,106-2,106-3,108-1,108-2,110-1,110-2described in relation toFIG.1.

In step2.5, the one or more outcome nodes are scored. The method200comprises, for each outcome node, determining a score based on the outcome of the outcome node. Each outcome node may be scored using a function that is specific to that outcome node. The score of each outcome node represents a value of the entity reaching the outcome state of the outcome node.

In step2.6, the plurality of nodes are scored. The scoring method comprises, for each node of the plurality of nodes, and for each outcome out of the set of outcomes: determining whether one or more outcome nodes for the outcome are immediately available from the node; and when one or more outcome nodes for the outcome are immediately available from the node, scoring the outcome for the node using the scores of the one or more outcome nodes.

Using the example described in relation toFIG.1, a square outcome with a value of 4 is immediately available from node102-1. Node102-1may be scored with a 4 for the square outcome. However, a triangle outcome is not immediately available from node102-1, and so node102-1may be assigned a score of 0 for the triangle outcome. Similarly, node102-1may be assigned a score of 0 for the pentagon outcome as there is no pentagon outcome immediately available from node102-1.

In step2.7, for each node, and for each outcome out of the set of outcomes, a distance from the node to a highest scoring outcome node for the outcome is determined. The method200may further comprise, for each node of the graph, and for each outcome out of the set of outcomes, determining a distance from the node to a closest outcome node for the outcome. A distance from a node to an outcome node may be determined as the distance of a minimal distance path from the node to a node to which the outcome node is connected.

For example, the path-finding algorithm may be used to determine, for each node, a set of minimal distance paths beginning from the node and ending at another node. In order to determine a highest scoring outcome node for each outcome for the node, the scores of the nodes at the end of minimal distance paths may be compared. A highest scoring path for an outcome for the node may be selected as the path that ends in a node that is attached to an outcome node for the outcome with the highest score. A distance from the node to a highest scoring outcome node for the outcome may thus be determined as the distance along this highest scoring path.

In order to determine a closest outcome node for each outcome for the node, the distances of minimal distance paths may be compared. A closest path for an outcome for the node may be selected as the path with a least distance that ends in a node attached to an outcome node for the outcome with a non-zero score. A distance from the node to a closest outcome node for the outcome may thus be determined as the distance along this closest path.

The method200may comprise storing, for each node of the graph, and for each outcome out of the set of outcomes: (i) the score of the node, (ii) the score of the highest scoring outcome node for the outcome, and (iii) the distance from the node to the highest scoring outcome node for the outcome. The method200may comprise storing, for each node of the graph, and for each outcome out of the set of outcomes, the distance from the node to the closest outcome node for the outcome.

FIG.3shows an example method of selecting actions in a video game using an intent-based model300.

For illustrative purposes, the example ofFIG.3corresponds to the example ofFIG.1, with the states302-1,302-2,302-3,302-4ofFIG.3corresponding to the nodes102-1,102-2,102-3,102-4ofFIG.1, transitions304-1,304-2,304-3,304-4,304-5ofFIG.3corresponding to the edges104-1,104-2,104-3,104-4,104-5ofFIG.3, and shows the same set of outcomes as shown inFIG.1. As described in relation toFIG.1, transition304-4is a contextual transition which may only be available in certain contexts of the video game.

The intent-based model300comprises a plurality of states302-1,302-2,302-3,302-4and transitions between states304-1,304-2,304-3,304-4,304-5. The intent-based model300comprises, for each state-outcome pair, a score for the pair denoted by ‘Score’, a value of a highest-scoring outcome node for the pair denoted by ‘BestOnPath’, a distance of a closest outcome node for the pair denoted by ‘ClosestDist’, and a distance of a highest scoring outcome node for the pair denoted by ‘BestDist’. The values for state-outcome pairs may be determined using the method200described in relation toFIG.2.

Transitioning into a Highest Scoring Outcome State

The intent-based model may be used to select actions, or transitions, based on a received indication of an intent to transition the entity into a highest scoring outcome state for the outcome.

For example, the entity may currently be at state302-1. If an indication of an intent to transition the entity into the highest scoring triangle outcome is received the following steps are performed.

The score of state302-1for the triangle outcome is compared with the score of the highest scoring outcome node (“BestOnPath”) for the triangle outcome that can be reached from state302-1. In this case as 0 is less than 5, a determination is made that the entity is not currently at a state from which the highest scoring outcome node for the triangle outcome is immediately available. Subsequently, one or more transitions that are available from state302-1are determined.

In general, a transition is selected when a transition distance (in this case denoted by ‘BestDist’ of the triangle outcome for the state transitioned to by the transition) is less than or equal to a current distance (in this case denoted by ‘BestDist’ of the triangle outcome for the current state). When multiple transitions may be selected (e.g. if multiple transitions have a transition distance less than or equal to the current distance), the transition with the lowest transition distance may be selected. Ties may be broken in any suitable manner, e.g. by random choice.

In this case, only transition304-1is available, and so transition304-1is selected, with the entity transitioning into state302-2. With the entity in state302-2, the score of state302-2for the triangle outcome is compared with the score of the highest scoring outcome node for the triangle outcome that can be reached from state302-2. As 2 is less than 5, another determination is made that the entity is not currently at a state from which the highest scoring outcome node for the triangle outcome is immediately available. Subsequently, one or more transitions that are available from state302-2are determined.

If the context of the game is such that contextual transition304-4is not available then only transitions304-2and304-5are available from state302-2, and the above described steps are repeated. Transition304-2is selected as its transition distance (which equals 1), is lower than the transition distance of transition304-5(which equals 2), followed by transition304-3so that the entity is at state302-4.

At state302-4, the score of state302-4for the triangle outcome is compared with the score of the highest scoring outcome node for the triangle outcome that can be reached from state302-4. As these values are equal (having a value of 5), a determination is made that the entity is currently at the state from which the highest scoring outcome node for the triangle outcome is immediately available and the transition corresponding to the triangle outcome from state302-4is selected.

However, the context of the game may be such that when the entity is at state302-2, contextual transition304-4is also available. In this case, determining one or more transitions from state302-2comprises determining contextual transition304-4in addition to transitions304-2and304-5as previously described.

When multiple transitions may be selected from a state, the distance to the highest scoring outcome nodes are compared for the states that are transitioned to by the transitions, as described above. In this case, transition304-2transitions the entity to state302-3with a distance of 1 to the highest scoring outcome node for the triangle outcome that can be reached from state302-3. On the other hand, contextual transition304-4transitions the entity to state302-4with a distance of 0 to the highest scoring outcome node for the triangle outcome that can be reached from state302-4. In this case as 0 is less than 1, contextual transition304-4is selected instead of transition304-2, and the entity transitions directly to state302-4.

As before, at state302-4, the score of state302-4for the triangle outcome is compared with the score of the highest scoring outcome node for the triangle outcome that can be reached from state302-4. As these values are equal, a determination is made that the entity is currently at the state from which the highest scoring outcome node is immediately available and the transition corresponding to the triangle outcome from state302-4is selected.

Transitioning into a Closest Outcome State

Additionally, the intent-based model may be used to select actions, or transitions, based on a received indication of an intent to transition the entity into a closest outcome state for the outcome.

For example, the entity may currently be at state302-2. If an indication of an intent to transition the entity into the closest square outcome is received the following steps are performed.

The score of state302-2for the square outcome is determined. As the score for the square outcome for state302-2is 0, a determination is made that the entity is not currently at a state from which an outcome node for the square outcome is immediately available. Subsequently, one or more transitions that are available from state302-2are determined.

In general, a transition is selected when a transition distance (in this case denoted by ‘ClosestDist’ of the square outcome for the state transitioned to by the transition) is less than or equal to a current distance (in this case denoted by ‘ClosestDist’ of the square outcome for the current state). When multiple transitions may be selected (e.g. if multiple transitions have a transition distance less than or equal to the current distance), the transition with the lowest transition distance may be selected. Ties may be broken in any suitable manner, e.g. by selecting a transition which transitions to a state with the highest score for the outcome, or by random choice.

If the context of the game is such that contextual transition304-4is not available then only transitions304-2and304-5are available from state302-2. Transition304-5is selected as its transition distance (which equals 0), is lower than the transition distance of transition304-2(which equals 1) and the entity transitions to state302-1.

At state302-1, the score of state302-1for the square outcome is determined. As this value is non-zero (in this case, 4), a determination is made that the entity is currently at a state from which an outcome node for the square outcome is immediately available and the transition corresponding to the square outcome from state302-4is selected.

However, the context of the game may be such that when the entity is at state302-2, contextual transition304-4is also available. In this case, determining one or more transitions from state302-2comprises determining contextual transition304-4in addition to transitions304-2and304-5as previously described.

In this case, transition304-2transitions the entity to state302-3with a distance of 1 to the closest outcome node for the square outcome that can be reached from state302-3. On the other hand, contextual transition304-4transitions the entity to state302-4with a distance of 0 to the closest outcome node for the square outcome that can be reached from state302-4. Similarly, transition304-5transitions the entity to state302-1with a distance of 0 to the closest outcome for the square outcome that can be reached from state302-1. Therefore, in this case, both transitions304-4and304-5have the same transition distance. However, state302-4has a higher score for the square outcome than state302-1and so transition304-4is selected instead of transition304-5. Ties may be broken in any suitable manner, e.g. by random choice.

At state302-4, the score of state302-4for the square outcome is determined. As this value is non-zero (in this case, 5), a determination is made that the entity is currently at a state from which an outcome node for the square outcome is immediately available and the transition corresponding to the square outcome from state302-4is selected.

FIG.4shows a flow diagram of an example method400of selecting actions in a video game using an intent-based model. The method400shows a general overview of the methods described in relation toFIG.3.

In step4.1, an indication of an intent to transition to an outcome state is received. Receiving an indication of an intent to transition to an outcome state may comprise receiving an input from a player of the video game. The intent may be an intent to transition the entity into a highest scoring outcome state from the current state. Additionally or alternatively, the intent may be an intent to transition the entity into a closest outcome state from the current state.

In step4.2, a current state of an entity is determined.

In step4.3, one or more transitions that are immediately available from the current state are determined. The method400may comprise determining one or more transitions that are always available for the entity. The method400may further comprise determining one or more transitions that are available based on a current context of the video game.

In step4.4, an intent-based model is used to determine: (i) a score for the current state, (ii) a current distance, and (iii) for each of the one or more transitions, a transition distance. The current distance is a distance from the current state to an outcome state corresponding to the intent. The transition distance of a transition is a distance from a state transitioned to by the transition to an outcome state corresponding to the intent.

In step4.5, a transition is selected such that the transition distance of the transition is less than or equal to the current distance. When multiple transitions may be selected (e.g. if multiple transitions have a transition distance less than or equal to the current distance), the transition with the lowest transition distance may be selected. When multiple transitions have the same lowest transition distance, the transition which transitions into a state with the highest score for the outcome may be selected. Ties may be broken in any suitable manner, e.g. by random choice.

The method may be implemented in a fighting game. The current state of the entity may represent a current grappling position of the entity. Each of the one or more transitions may represent a movement of the entity from the current grappling position to a subsequent grappling position. The intent may comprise one of: a get up intent, wherein the get up intent is to transition to the closest get up outcome state; a submission intent, wherein the submission intent is to transition to a highest scoring submission outcome state or a closest submission outcome state; or a ground-and-pound intent, where in the ground-and-pound intent is to transition to a highest scoring ground-and-pound outcome state or a closest ground-and-pound outcome state.

FIG.5shows a schematic example of a system/apparatus for performing any of the methods described herein. The system/apparatus shown is an example of a computing device. It will be appreciated by the skilled person that other types of computing devices/systems may alternatively be used to implement the methods described herein, such as a distributed computing system.

The apparatus (or system)500comprises one or more processors502. The one or more processors control operation of other components of the system/apparatus500. The one or more processors502may, for example, comprise a general purpose processor. The one or more processors502may be a single core device or a multiple core device. The one or more processors502may comprise a central processing unit (CPU) or a graphical processing unit (GPU). Alternatively, the one or more processors502may comprise specialised processing hardware, for instance a RISC processor or programmable hardware with embedded firmware. Multiple processors may be included.

The system/apparatus comprises a working or volatile memory504. The one or more processors may access the volatile memory504in order to process data and may control the storage of data in memory. The volatile memory504may comprise RAM of any type, for example Static RAM (SRAM), Dynamic RAM (DRAM), or it may comprise Flash memory, such as an SD-Card.

The system/apparatus comprises a non-volatile memory506. The non-volatile memory506stores a set of operation instructions508for controlling the operation of the processors502in the form of computer readable instructions. The non-volatile memory506may be a memory of any kind such as a Read Only Memory (ROM), a Flash memory or a magnetic drive memory.

The one or more processors502are configured to execute operating instructions508to cause the system/apparatus to perform any of the methods described herein. The operating instructions508may comprise code (i.e. drivers) relating to the hardware components of the system/apparatus500, as well as code relating to the basic operation of the system/apparatus500. Generally speaking, the one or more processors502execute one or more instructions of the operating instructions508, which are stored permanently or semi-permanently in the non-volatile memory506, using the volatile memory504to temporarily store data generated during execution of said operating instructions508.

Implementations of the methods described herein may be realised as in digital electronic circuitry, integrated circuitry, specially designed ASICs (application specific integrated circuits), computer hardware, firmware, software, and/or combinations thereof. These may include computer program products (such as software stored on e.g. magnetic discs, optical disks, memory, Programmable Logic Devices) comprising computer readable instructions that, when executed by a computer, such as that described in relation toFIG.5, cause the computer to perform one or more of the methods described herein.

Any system feature as described herein may also be provided as a method feature, and vice versa. As used herein, means plus function features may be expressed alternatively in terms of their corresponding structure. In particular, method aspects may be applied to system aspects, and vice versa.

Furthermore, any, some and/or all features in one aspect can be applied to any, some and/or all features in any other aspect, in any appropriate combination. It should also be appreciated that particular combinations of the various features described and defined in any aspects of the invention can be implemented and/or supplied and/or used independently.

Although several embodiments have been shown and described, it would be appreciated by those skilled in the art that changes may be made in these embodiments without departing from the principles of this disclosure, the scope of which is defined in the claims.