Literature Review
Playing strategy games like chess and checkers couples intellectual activity with competition. By playing games, we can exercise and improve our intellectual skills. The competition adds excitement and allows us to compare our skills to those of others. The same motivation accounts for interest in Computer Game Playing as a testbed for Artificial Intelligence. Programs that think better should be able to win more games, and so we can use competitions as an evaluation technique for intelligent systems. Unfortunately, building programs to play specific games has limited value in AI.
(1) To begin with, specialized game players are very narrow. They can be good at one game but not another. Deep Blue may have beaten the world Chess champion, but it has no clue how to play checkers.
(2) A second and more fundamental problem with specialized game playing systems is that they do only part of the work. Most of the interesting analysis and design is done in advance by their programmers. The systems themselves might as well be tele-operated. All is not lost. The idea of game playing can be used to good effect to inspire and evaluate good work in Artificial Intelligence, but it requires moving more of the design work to the computer itself. This can be done by focussing attention on General Game Playing [6][7][8]. General game players are systems able to accept descriptions of arbitrary games at runtime and able to use such descriptions to play those games effectively without human intervention. In other words, they do not know the rules until the games start. Once the game begins, they receive a game description; and, based solely on this description, they must figure out how to play the game legally and effectively. Unlike specialized game players, such as Deep Blue, general game players cannot rely on algorithms designed in advance for specific games. General game playing expertise must depend on intelligence on the part of the game player and not just intelligence of the programmer of the game player. In order to perform well, general game players must incorporate results from various disciplines, such as knowledge representation, reasoning, and rational decision making; and these capabilities have to work together in a synergistic fashion.
Each game takes place in an environment with finitely many states, with a distinguished initial state and one or more terminal states. In addition, each game has a fixed, finite number of players; each player has finitely many possible actions in any game state, and each state has an associated goal value for each player. The dynamic model is discrete update: on each step, there is one player in control, that player performs an action, and the environment updates only in response to the action taken by the player in control. Unfortunately, it is impractical to use such explicit representations to communicate game rules to game players. Even though the numbers of states and actions are finite, these sets can be extremely large; and the corresponding graphs can be larger still. For example, in chess, there are thousands of possible moves and more than 1030 states. Fortunately, we can do better.
Using Logic Programming, we can exploit the regularities in the game to produce more compact compact encodings of game rules as logic programs. Consider the case of Tic Tac Toe (Noughts and Crosses). We use datasets to describe states of the game. Here we use a ternary relation named cell (that captures data about which cells contain which marks and which cells are empty) together with a unary relation control (that indicates which player is in control, i.e. next to play).
cell(1,1,b) cell(1,2,b) cell(1,3,b) cell(2,1,b) cell(2,2,b) cell(2,3,b) cell(3,1,b) cell(3,2,b) cell(3,3,b) control(x)
We use Prolog-style [13] view definitions to define various properties of states. The row relation holds of a row number and a player if and only if all three cells in the row have that player’s mark. The column and diagonal relations are defined analogously. A player has a line of marks if and only if the player has a row or a column or a diagonal. A game is terminal if and only if one of the players has a line of marks or if there are no remaining empty cells. The game rules also specify constraints and goals, i.e. the actions that are legal in each state and a characterization of the states satisfy the goal of each player.
row(M,Z) :- cell(M,1,Z) & cell(M,2,Z) & cell(M,3,Z) column(N,Z) :- cell(1,N,Z) & cell(2,N,Z) & cell(3,N,Z) diagonal(Z) :- cell(1,1,Z) & cell(2,2,Z) & cell(3,3,Z) diagonal(Z) :- cell(1,3,Z) & cell(2,2,Z) & cell(3,1,Z)
line(Z) :- row(M,Z) line(Z) :- column(M,Z) line(Z) :- diagonal(Z) terminal :- line(x) terminal :- line(o) terminal :- ~open open :- cell(M,N,b) legal(mark(M,N)) :- cell(M,N,b) goal(x) :- line(x) goal(o) :- line(o)
Given a state and an action, the next state is determined uniquely by the corresponding Epilog-style [9] operation rules. If a player in control marks a cell, the result is a state in which that cell is no longer blank and instead contains the player’s mark. Furthermore, control changes hands. mark(M,N) :: control(W) ==> ~cell(M,N,b) & cell(M,N,W) mark(M,N) :: control(x) ==> ~control(x) & control(o) mark(M,N) :: control(o) ==> ~control(o) & control(x) These few rules are all that we need to fully describe a game of thousands of states. That’s a significant saving over the state graph. The improvement in more complex games can be even more dramatic. For example, it is possible to describe the rules of Chess in just three or four pages of rules like these. As this example illustrates, Logic Programming is well-suited to game description. Conversely, game description is well-suited to teaching Logic Programming. The datasets are simple; the relations and operations are well-defined; and the specifications are precise. Students learn about modeling worlds in terms of objects and relations and operations. And they get to explore tradeoffs between different representations. Should we explicitly say that a cell contains a blank, as in the rules above, or should we represent ”blankness” as the absence of a mark? Should we write view definitions to define relations in terms of others or should we represent our relations explicitly in our datasets and use operations to keep them up to date?
http://logicprogramming.stanford.edu/readings/ggp_killer_app_for_lp.pdf
Significance of the Study
The Legend of Zelda: Breath of the Wild is Nintendo’s newest entry in a franchise that started in 1986. In this chapter, Link wakes to find himself in a high-tech sleep chamber with no memories of his past. The player learns that Link was asleep for 100 years after a failed battle with Calamity Ganon. As a result, Link must now complete this fight in order to save Hyrule. The player gets to explore a massive open-world video game full of adventure, monsters, and puzzles. Because the game encourages experimentation and exploration, each player can shape the story according to their own pace and skills. The game received an E10+ rating for fantasy violence, mild suggestive themes, and use of alcohol. While we find Breath of the Wild‘s content largely inoffensive, younger children may find parts of the game too difficult to complete alone. As always, we suggest parents sit down and play along with their kids.
The Legend of Zelda: Breath of the Wild helps kids practice and improve the following skills:
Focus
Getting started and then maintaining attention and effort to tasks.
Breath of the Wild provides ample opportunity for a variety of focus thinking skills. The game is comprised primarily of quests: main, shrine, and side quests. The player discovers these quests by talking to people found all over Hyrule. However, it is up to the player to actually track down and complete the quest elements. This provides great practice for the task initiation thinking skill. Without initiating the quests, the player will never move the game forward. The variety of tasks also provides the perfect opportunity to practice sustaining attention on short-term tasks (many side and shrine quests fall under this category), sustaining attention on long-term tasks (the main quests must always be kept in mind even while on the side quests), and shifting attention between tasks (there are times when the player must move back and forth between multiple quests in order to complete them). Failure to practice any of these focus thinking skills will slow and even halt the progress of the player. Finally, Breath of the Wild also gives chances to ignore external distractions every minute of game play. Even though there are quests that guide a player through the storyline, there are also distracting monsters and treasure chests all over Hyrule. It is common to stumble across two or three more side quests while working on the first. If a player doesn’t ignore these external directions, they will wind up with a large list of quests and none of them completed. Story progress will slow, weapons will break without being replaced, and Link’s armor and materials will never get stronger.
Flexibility
Adapting and adjusting to changing conditions and expectations.
Flexibility thinking skills are a vital part of Breath of the Wild, and are especially noticeable in shrine quests. In order to accomplish shrine quests, the player will first have to find the shrines. This takes a variety of techniques, from simply stumbling upon them, to being led to them by in-game characters, to solving riddles to make them appear. Once the player has entered a shrine they will face different puzzles and fights. Every one of the 120 different shrines requires a different approach. If the player is not flexible by adapting to the new set of obstacles and trying new things, they will not be able to complete the shrines. Without the shrines, the player cannot gain more stamina, more hearts, or better armor and weapons. Of course, the many different monsters, potion recipes, and non-shrine quests also require a player to continue to use their flexibility thinking skills or fail the game.
Organization
Arranging and coordinating materials in order to complete a task.
The Legend of Zelda: Breath of the Wild also uses the cognitive thinking skill of organization. At the beginning of the game, Link has a set number of spaces for his weapons, bows, and shields. Each weapon has different strengths, magical attributes, and durability. When the player has used up all of a weapon’s durability, the weapon breaks. The player has the opportunity to expand the number of spaces eventually, but until then, the player’s success can be linked directly to how well they organize their weapons, bows, and shields. Keeping a weak item rather than dropping it and picking up a stronger one could cause the player to have a weapon break in the middle of the fight or to run out of weapons all together. The same holds true for bows and shields.
Planning
Developing a systematic approach for setting and achieving goals.
Planning skills are another important part of Breath of the Wild. The player needs a long-term plan for how to conquer the main quests. It’s important to know which order they will complete the quests, what items they will need to complete them, and how to get the needed items. There is some flexibility to what must be included in the plan, but the existence of a plan is most definitely required in order to beat the main quests. The player will also need to create a short-term plan every time they decide to go after a side quest or main quest.
Self-Awareness
Understanding our own actions, thoughts and feelings.
With the open world and flexible order for completing quests, Breath of the Wild allows plenty of chances for the player to get self-awareness practice that spans the subskills of self-assessment, reflection, social awareness, and empathy. Players must analyze Link and his materials, weapons, and armor, as well as their own strengths and weaknesses as a player. They must determine if Link has the proper materials, weapons, armor, and shields, but also whether they are a better fighting from a distance or in close-quarters, or if they have a chance at defeating a difficult monster.
Additionally, Breath of the Wild adheres to the traditional RPG aspect of questing. Of course, there is an epic overarching storyline, but along the way there are small jobs from ordinary people that call Link into service, too. Part of what makes Link a legend in his own right is that he does for others. This emphasis on being an everyday hero is excellent social awareness practice, teaching your child the importance of being a citizen of the world.
Self-Control
Managing our actions, thoughts, and feelings.
Self-control may not be an obvious thinking skill in this game, but it is definitely necessary. More and more difficult monsters and puzzles will require the player to use control in managing anger and frustration. The less the player engages in other thinking skills, such as planning and organization, the more likely they are to be frustrated. If the player doesn’t keep this frustration under control, they are likely to give up the game. At the very least, they will be unable to complete that specific challenge or even fail to advance in the game as a whole. The Legend of Zelda: Breath of the Wild also has plenty of chances for a player to exhibit impulse control. The first time a character finds a monster, shrine, or treasure chest, or the first time that they hear of a side quest, is not always the best time to complete it. They may already be in the middle of an important quest, or they may need different materials. If they impulsively chase after whatever new thing they have stumbled across, the player will fail to complete their original quest. This could even keep the player from beating the main quests and, consequently, the game.
Time Management
Being efficient and aware of our use of time and effort.
While not all of the quests have specific time requirements, there are many side quests and shrines that have time components to them. These will require the player to use various amounts of time management skills, both with keeping pace and the cognitive skill of estimating time and meeting deadlines. Some quests will have a literal timer that the player has to maintain awareness of. A few have a varying “timer” based on how strong Link’s armor is and how many hearts or how much stamina Link has when the player attempts the quest. The only way a player can beat these quests is by being efficient with his supplies and movements, and by looking for materials and potions that can increase Link’s efficiency.
Working Memory
Recalling and retaining information in our minds while working.
With so many quests, puzzles, and riddles to be found all over Hyrule, the player will practice the cognitive thinking skill of working memory every time they play. One quest requires the player to gather 30 bundles of wood. Another requires three specific ingredients for a special meal. Being able to follow the directions and remember what they are searching for will save the player time and effort. In a big world like Breath of the Wild, which is twelve times bigger than The Legend of Zelda: Twilight Princess, players can loose ten and twenty minutes every time they have to go back and forth between two locations. It’s not fun having to do this because of simple forgetfulness or an inability to follow directions.
Finally, it is important to note that there is a lot of reading and reading comprehension skills used to successfully play Breath of the Wild. Every skill learned, every person met, and every quest triggered, will require the player to read. A large number of these interactions will also have clues to how to answer the riddles and solve the quests, making reading comprehension important. There are also classic riddles that require the player to read between the lines in order to solve them. If a player’s reading skills are not up to the level of the game, they will need support from a stronger reader to beat the game. Even a strong reader might need help unraveling some of the riddles. This, however, provides the perfect opportunity for a parent to get involved along with their child.
World and Actors
The core idea in Prolog-based game programming is to utilize relations as the most primitive building blocks of the system, just like basic circuit components (e.g. resistors, transistors, capacitors, inductors, etc) are the most primitive building blocks of an electric circuit. It is sensible, therefore, to start this journey by considering the most rudimentary relations (e.g. unary and binary) first, and see if these elements can serve as the most essential nuts and bolts of the game.
Screenshot
Suppose that we are designing a game, and that the game consists of two major parts – world and actors (see the image above). The world is a scene in which everything is supposed to happen, and actors are objects which belong to the world. Examples of actors include “players”, “enemies”, “obstacles”, “items”, and pretty much any discrete entities which have their own names and attributes. Actors are able to interact with each other (as well as with themselves), from which various events occur. What we refer to as “gameplay” is a chain of such events.
We will begin formulating a gameplay system based off of this conceptual backbone. All you need to remember is that there is a world, and that the world contains a number of actors, each of which possesses its own state and behavior.
Tags
First of all, let us identify each individual actor with a unique name. If there are two actors in the world, for instance, we will simply assume that the name “actor1” and “actor2” will be used to indicate the first and second actors, respectively.
Screenshot
The first piece of logic I will illustrate is the idea of tags. A tag is a keyword which, when attached to an actor, describes what the actor stands for. When an actor has the tag “bread” attached to it, for example, we should be able to tell that the actor is a piece of bread.
The Prolog code below assigns the tag “bread” to both actor1 and actor2, in the form of unary predicates (The tag “bread” itself is an unary relation, and “bread(actor1)” & “bread(actor2)” are two separate instances of it). This implies that both actor1 and actor2 are pieces of bread.
bread(actor1).
bread(actor2).
Screenshot
An actor can have multiple tags as well. However, one may feel that it is a bit too tedious to manually assign a bunch of tags to each individual actor. For example, let us say that every piece of bread must also be labeled as flammable and decomposable. This means that, whenever an actor is associated with the tag “bread”, we are obliged to always ensure that it is also associated with the tag “flammable” and “decomposable”. Manually attaching these two additional tags to every “bread” actor is way too cumbersome and error-prone. Fortunately, the following pair of horn clauses neatly solve this problem. They enforce the following two rules:
(1) Whenever tag “bread” is assigned to actor X, tag “flammable” will automatically be assigned to actor X.
(2) Whenever tag “bread” is assigned to actor X, tag “decomposable” will automatically be assigned to actor X.
flammable(X) :- bread(X).
decomposable(X) :- bread(X).
Screenshot
These horn clauses, therefore, serve as part of the game’s “config data” – a list of data entries in the game’s technical design document (like the ones you would see on a spreadsheet) telling us the characteristics of each individual character type, skill type, mission type, and so forth. The tags called “flammable” and “decomposable” in our case, for instance, are characteristics which belong to the type-specifier called “bread”, meaning that any actor which can be identified as “bread” is a composition of two properties called “flammable” and “decomposable”.
A decent analogy can be found in Unity game engine, where we may create a prefab called “Bread” with two components in it – “Flammable” and “Decomposable”. Or, in a general object-oriented programming environment, “Bread” may stand for the name of a class which implements two interfaces called “IFlammable” and “IDecomposable”.
In a way, therefore, horn clauses in Prolog play the role of data type definitions.
Screenshot
Aside from these pre-configured tags (which all rely on the presence of the tag “bread”), one may as well attach a custom tag to an actor as needed. For example, imagine that a wizard happened to enchant actor2 (i.e. the second piece of bread). This means that, unlike actor1 which is an ordinary piece of bread, actor2 must be an “enchanted” piece of bread which is required to have the tag “enchanted” attached to it for the purpose of showing us that it has been enchanted. The code below ensures that this is the case.
enchanted(actor2).
Screenshot
The tags “flammable” and “decomposable” are characteristics of all pieces of bread, whereas the tag “enchanted” is a characteristic of only special pieces of bread which have been enchanted by a wizard.
Relationships
So far, we have been using tags for specifying the characteristics of each individual actor. In a gameplay system, however, we also need to specify relationships between actors, such as ways in which they interact, etc.
In an ecosystem, predators chase preys and preys run from predators. In a dating simulator, a guy tries to flirt with girls and girls reject him. In a social simulator (such as The Sims), people are either friends or enemies of each other, or somewhere in between. In the game of chess, a bishop devours a rook diagonally and a rook devours a bishop orthogonally. These are all relationships out of which the game’s dynamics emerge.
Defining actor-to-actor relationships in Prolog is pretty straightforward. Just like an unary predicate can be used to characterize a single actor, a binary predicate can be used to characterize a relationship between a pair of actors. And by means of a horn clause, such a relationship can be dynamically deduced from a set of requisite conditions.
The following code is an example of a relationship. Suppose that there is a third actor called “actor3”, and that we have declared it as a human (by attaching the tag “human” to it). Since a human is able to eat a piece of bread, we can confidently assert that “X can eat Y if X is a human and Y is a piece of bread”. Here, “X can eat Y” is a relationship which holds whenever X is associated with tag “human” and Y is associated with tag “bread”.
human(actor3).
canEat(X, Y) :- human(X), bread(Y).
Here is another example. Since a piece of bread is decomposable (because anything which is identified as “bread” must also be identified as “decomposable”), we know that microbes such as fungi are capable of spoiling it. If there is an actor with the tag “fungus” attached to it, therefore, we will be able to tell that it must be able to spoil any other actor which is “decomposable”. This is yet another case of a relationship between two types of actors; it is a relationship which says, “X can spoil Y if X is a fungus and Y is decomposable”. The following code shows its definition.
fungus(actor4).
canSpoil(X, Y) :- fungus(X), decomposable(Y).
Screenshot
There is something still missing here, though. While I have demonstrated that it is possible to assign characteristics to individual actors as well as their mutual connections (i.e. relationships), I have not shown yet how to make these characteristics change over time. They all have been static so far, and the declarative nature of Prolog does not seem to offer an easy solution to make things dynamic.
If we want to create a game rather than a fixed landscape of how things are shaped permanently, we better let them move and interact as time goes by. In the next part of the series, I will explain how the game loop shall be conceptualized in Prolog.
So far, I have been demonstrating ways in which we can assign tags and relationships to each of the gameplay agents (aka “actors”). The key takeaway is to use predicates to specify them, as well as leverage the power of logical relations for letting the program automatically instantiate such predicates.
By the same spirit, we are also able to assign a numerical attribute to an actor. Suppose that an actor called “actor3” is tagged “human”, and that we would like to ensure that every human actor has an attribute named “numLegs” which indicates the person’s number of legs (i.e. 2). The following horn clause, then, will fulfill this objective.
numLegs(X, 2) :- human(X).
The binary predicate, “numLegs”, is a numerical attribute of every human actor which tells us that the actor’s number of legs is 2. This differs from a simple tag (i.e. keyword) in the sense that it also contains a number. This allows us to specify different “numLegs” values to different species of actors, like the ones shown below.
numLegs(X, 2) :- human(X).
numLegs(X, 4) :- dog(X).
numLegs(X, 4) :- cat(X).
numLegs(X, 3) :- martianTripod(X).
Screenshot
If every martian tripod were a faithful reader of George Orwell and happened to interpret every single phrase of his novel “Animal Farm” in the most blatantly literal manner, it would be reasonable to conclude that a martian tripod is likely to protect four-legged creatures and kill two-legged creatures (“Four Legs Good, Two Legs Bad”). These behavioral patterns can be implemented using horn clauses, which are illustrated below.
shouldProtect(X, Y) :- martianTripod(X), numLegs(Y, 4).
shouldKill(X, Y) :- martianTripod(X), numLegs(Y, 2).
And of course, it is equally feasible to devise a numerical attribute which involves multiple actors, similar to the concept of relationship I have demonstrated before. For instance, imagine that a dog’s degree of loyalty to a human being is 6, while a cat’s degree of loyalty to a human being is only 2. These two numerical relationships can be modeled as two slightly different ternary relations, like the ones shown below.
loyalty(X, Y, 6) :- dog(X), human(Y).
loyalty(X, Y, 2) :- cat(X), human(Y).
Screenshot
This sort of reasoning can be expanded indefinitely. For example, one may as well define a numerical attribute which carries not just a single number, but multiple numbers (i.e. vector quantity). One may also define a relationship which involves not just two actors, but three or more actors, such as: “This girl hates her boyfriend for showing too much affection to the other girl”, etc.
State and Time
Things have been looking good so far. We know how to create attributes and relationships, as well as how to assign them to our gameplay agents, and so forth. However, we cannot make a game out of these building blocks alone.
What has been missing here is a sense of change over time. We want actors to move, interact, and make impacts upon the world as well as upon themselves. What we’ve got so far, instead, is a mere snapshot of how things are related to each other; there is no moving part at all.
So, how to turn this static world into something dynamic? First of all, let us recall the way in which an imperative programming language would approach this problem. In a typical imperative language such as C, C++, or Java, creating a sense of change is simple and straightforward.
Suppose that there is a clock which ticks at regular intervals. Every time it ticks, it calls a function called “Update”. If there is an actor who is supposed to get hungrier and hungrier as time passes by, all we have to do in an imperative language is to access the actor’s state variable called “hunger” and increase its value whenever the “Update” function runs (See the code below).
void Update(Actor x)
{
x.hunger = x.hunger + 1;
}
This kind of logic is possible because the variable we are dealing with (i.e. hunger) is a state variable; we are allowed to assign a new value to it at any moment.
In a declarative language such as Prolog, unfortunately, we cannot just declare a state variable and modify its value whenever we want to. Logical relations are timeless beings; they exist outside of the realm of time, which means that it is nonsensical to try to associate them with variables which are bound to certain points in time.
What do we do, then? In order to mimic state transition in logic programming, we must approach the concept of time from a different angle. Rather than trying to directly manipulate the current state of the game while it is running, we ought to instead define a set of time-invariant statements which tell us how the past and present are related.
Screenshot
The figure above illustrates the core difference between the imperative and declarative means of running the game. Suppose that the game’s state is being recorded in the computer’s memory space (e.g. RAM), which is just an array of data slots.
In the imperative case, there is one chunk of data called “state”. The game looks up this chunk of data, computes the new state, and overwrites this new state on top of the original chunk of data. This is what the assignment operator (i.e. “=”) does in an imperative language.
In the declarative case, on the other hand, direct mutation of data is prohibited. At the beginning of each frame, the game first accesses the chunk of data at which the previous state was located. It computes the new state based on the previous state, and allocates this new state to a location which is currently not being used. The system does not tamper with the previous state; it simply appends the new state to the history of states without erasing or modifying the existing data.
Screenshot
The main advantage of this approach is that it gracefully prevents race conditions. Since it does not “change” any existing piece of data, it never has to worry about inadvertently disrupting another computational process which may have been accessing the same location in memory.
Of course, continually adding new copies of the game’s state without deleting anything is too wasteful. Such an ever-growing list of states (which altogether constitute the game’s “history”), unless the gameplay is either turn-based or very short in duration, is likely to eat up too much space in memory. This is clearly not desirable.
Such a problem, however, can easily be mitigated by limiting the maximum duration of time through which an event’s effect is able to propagate. For example, if the game’s current state is entirely determined by events which happened only up to N steps back in time, it will imply that the system only needs to retain the memory of N previous states (which corredpond to the N previous time steps) and nothing older than that. As you can see in the image below, this means that memory slots which are sufficiently old can simply be recycled for other purposes.
Screenshot
State Transition
So, how do we implement such a declarative state transition mechanic in the language of Prolog?
Let us first examine how the functional paradigm would approach this problem. In functional programming (e.g. LISP), the game’s “Update” function simply needs to take the previous state of the game as the input, instantiate the new state based off of the given previous state, and return this new state as the output. The returned output will then be appended to the game’s state history as the most recent state, and the game loop (which is another function which is responsible for calling the “Update” function) will call the “Update” function once again, and again, and again, and so on, thereby periodically updating the game (For more details, please read: Functional Programming for Game Development).
In logic programming (e.g. Prolog), on the other hand, we cannot use such a functional methodology because functions are not a thing here. Instead, we must specify relations between the current and previous states, in a manner which resembles that of the so-called “difference equations” in mathematics.
In order to demonstrate how it works, let me first augment the syntax of Prolog a bit by introducing a number of additional symbols. These are not part of the standard Prolog (which means whichever Prolog interpreter you use won’t be able to recognize them), so please keep that in mind. Any Prolog code you are going to see from now on should be taken as pseudocode, meant to serve as a mere proof of concept.
The snippet below is a list of notations which will be used to illustrate the game’s temporal relations.
n = (current time step)
n-1 = (previous time step)
X[n] = (X at the current time step)
X[n-1] = (X at the previous time step)
X = (X at any time)
Suppose that the game loop keeps track of time in discrete time steps, beginning with n = 0 and periodically incrementing it one by one (i.e. n = 1, n = 2, n = 3, etc). The symbol ‘n’ refers to the game’s current time step, which means that ‘n-1’ refers to the previous time step, ‘n-2’ refers to the previous-previous time step (i.e. two steps back in time), and so on.
What’s important here is the bracketed notation (e.g. “X[n]”). So far, I have only shown Prolog statements which involved timeless entities. Things like “actor1”, “actor2”, and “actor3”, for instance, involved no concept of time whatsoever. Thus, there was no need to state their associations with respect to time.
When it comes to indicating an actor at a specific point in time, on the other hand, we can no longer just stick to a simple notation such as “X” because, if we do, we will be referring to the presence of the actor throughout the entirety of time. So in this case, we ought to attach an additional time parameter to the actor’s identifier (e.g. “X[n]” for current X, “X[n-1]” for previous X, etc).
Screenshot
Before elaborating further, let me first introduce a couple of arithmetic relations which I will be using quite frequently from now on (See the snippet below). The “equal(…)” relation holds whenever its parameters are equal in value, meaning that “equal(3, 3)” and “equal(5, 5)” are TRUE, whereas “equal(1, 2)” and “equal(3, 5)” are FALSE. The “add(…)” relation holds whenever the sum of its first two parameters yields the value of its last parameter, meaning that “add(2, 2, 4)” and “add(3, 4, 7)” are TRUE, whereas “add(1, 2, 5)” and “add(4, 0, 6)” are FALSE. The “multiply(…)” relation works in a similar fashion.
equal(A, B) = (TRUE if A = B)
add(A, B, C) = (TRUE if A + B = C)
multiply(A, B, C) = (TRUE if AB = C)
I will now explain how time-dependent relations can be used to implement gameplay dynamics. Imagine that there is an actor which is tagged as “human”. Also, let us assume that this actor was spawned at some point in time. What we want here is to let this actor have its own state variable called “hunger”, which starts at 0 (when the actor spawns) and increments itself by 1 every time the clock ticks.
The code below shows how it can be formulated in terms of executable rules.
hunger(X[n], 0) :- human(X[n]), spawnTime(X, n).
hunger(X[n], Curr) :- hunger(X[n-1], Prev), add(Prev, 1, Curr).
Screenshot
The first horn clause says that, if there is a human actor who just spawned right at the present moment (i.e. “n”), we must initialize its hunger to 0. This clause gets executed only once when the actor spawns, since it is the only moment at which “spawnTime(X, n)” can be evaluated as TRUE (Note: “spawnTime(X, n)” basically asks the question, “Is the current time the same as X’s spawn time?”).
The second horn clause says that, if there was an actor which had a state variable named “hunger” during the previous time step, its current hunger must be 1 greater than the previous hunger. This clause gets executed each time the clock ticks (i.e. whenever the time step increments by 1). It does NOT get executed during the moment at which the actor spawns, since “X[n-1]” is nonexistent during that time.
The first clause initializes the hunger, and the second clause periodically increments the hunger (because a human being is supposed to get hungrier and hungrier as time goes by).
But of course, the game will be pretty boring if all we can do is watch a human character starve. If we are to design a life simulator (like The Sims), for instance, there better be a way to quench the person’s hunger by letting him/her eat some food.
Here is a bit of a trouble, though. We already have a rule which tells us that the hunger must increase by 1 each time the clock ticks. If we add a new rule which describes how much the hunger must go down when the actor eats food, this new rule will be incompatible with the existing one because it is logically contradictory to have two different horn clauses which are both trying to define the same piece of data (i.e. “X[n]”) simultaneously.
There is a pretty neat solution to this, fortunately. All we have to do is separately compute the amount of natural increment in hunger (aka “naturalChangeInHunger”) and the amount of reduction in hunger due to the act of eating (aka “digestiveChangeInHunger”), and then combine them together into a single differential. Their implementations are shown below.
naturalChangeInHunger(X[n], 1) :- hunger(X[n], _).
digestiveChangeInHunger(X[n], ChangeInHunger) :- hunger(X[n], _), eat(X[n], Food[n]), calories(Food[n], NumCalories), multiply(NumCalories, -1, ChangeInHunger).
digestiveChangeInHunger(X[n], 0) :- hunger(X[n], _), !eat(X[n], Food[n]).
Screenshot
The first clause is easy to understand; it simply states that the natural change in hunger is always 1 (i.e. If the actor doesn’t do anything, it naturally gets hungrier by the degree of 1 after each time step). The meaning of the second/third clauses is that, if an actor is currently eating some food, its hunger must be going down by the number of calories in the food (or 0 if the actor is not eating anything. This negatory relation is denoted by “!eat(…)”).
One of the notable benefits of such mutually independent clauses is that they can run in parallel (by means of multi-threading or even GPU-based programs such as “compute shaders”). This provides us with yet another reason why logic programming is a great paradigm for gameplay engineering.
Anyways, once the application obtains the results of “naturalChangeInHunger” and “digestiveChangeInHunger”, the only remaining step is to sum up these two results (which will be carried out by the predicate called “netChangeInHunger”) and then add this sum to the actor’s hunger, just as shown below.
netChangeInHunger(X[n], NetChange) :- naturalChangeInHunger(X[n], Change1), digestiveChangeInHunger(X[n], Change2), add(Change1, Change2, NetChange).
hunger(X[n], Curr) :- hunger(X[n-1], Prev), netChangeInHunger(X[n-1], NetChange), add(Prev, NetChange, Curr).
Screenshot
(Will be continued in Part 3)
Game development is often being done in a highly object-oriented mindset. This is not only because the vast majority of gameplay engineers program in object-oriented languages (such as C++, C#, Java, etc), but also because the way a videogame operates can easily be modeled as a collection of discrete, independent objects.
A videogame comprises a number of gameplay elements, such as individual game mechanics, narrative elements, dialogues, agents, boids, actors, impacts, cutscenes, scenarios, and so on. And these are all distinct, highly separable entities which are based off of different faculties of mind. A dialogue and an explosive effect, for example, may be related with each other via a segment of conversation such as, “NPC 1: Hey, look! There is an explosion!”, yet they both can be implemented independently of each other because the articulation of neither of them requires the full avilability of the other. A writer doesn’t require an actual, functioning explosion to be able to mention that there is an explosion, and a VFX artist doesn’t require an NPC’s description of the explosion’s narrative implications in order to be able to implement an explosive impact.
And because of this nature of high modularity during the course of game development, a game’s underlying software framework is almost always being modeled under the principles of object-oriented programming. Every “thing” inside a videogame is essentially an object, each of which is a state machine operating on its own (as a standalone system). When combined with one another via loose chains of causality, these objects give rise to all sorts of interesting phenomena based upon their mutual interactions.
However, the object-oriented approach also creates plenty of rooms for countless bugs and glitches, which may arise from the fact that a state machine’s inner workings heavily depend on the exact timing of when something happens (which means the order of input values must be precise), as well as that there are multitudes of encapsulated bodies of state existing in a concurrent fashion, whose actions may contradict with each other (e.g. Conservation of energy being violated due to two explosions spawning out of a single bomb because of bad timing, etc). One might be able to prevent such scenarios by introducing some kind of buffer to the overall decision-making process by means of message-passing, queueing, and so forth, yet these methodologies add additional layers of complexity to the architecture.
A neat solution to this is to switch one’s programming paradigm to an entirely different one. Take functional programming, for example, in which modifiable states are almost completely excluded from the computing environment’s data management scheme.
Inside a purely functional framework, any changes in the state of the application simply undergo the process of being “appended” on top of the state’s history (similar to how append-only databases work, such as a blockchain), which nicely solves the problem of race conditions. Since the system never tampers with existing state objects (which are, in a functional programming language, nothing more than function calls sitting inside the application’s stack memory), external references which are still pointing to past instances of the state do not have to worry about their procedures making an unexpected turn due to sudden in-between data modifications.
One of the biggest challenges in the adoption of a declarative programming paradigm in game development is the conceptualization of time. The exclusion of the concept of time in a non-imperative language such as LISP, for instance, is both a blessing and a source of confusion. When we are making a game, we are essentially creating a virtual world which has its own timeline. As time passes by, various events happen inside the game’s own environment at designated points in time, based upon their own time-dependent schedules. Such a temporal aspect of gameplay is what typically leads engineers to simply fall back to imperative programming when developing the core mechanics of the game, even if they may be great advocates of declarative syntax when implementing modules that are time-independent (e.g. interpretation of data, procedural generation, etc). However, it is my personal conviction that such a multi-paradigm approach is not necessarily the best solution.
In an imperative programming language such as Java, one can easily implement time-related gameplay mechanics by creating an Actor object, letting it have a queue of pending actions (e.g. represented as an array of tuples, each of which is made out of the expected time of occurrence and a function body that must be executed when the time is reached, etc), and then updating this queue whenever the Actor’s update-function gets called at each frame of the game loop. This way of implementation, while it is highly intuitive and handy, often leads to a wide spectrum of bugs which may be too subtle to even find out before releasing the final product. The existence of tens or even hundreds of such time-dependent queues, all potentially interacting with one another in real time, is prone to give birth to countless unimaginable scenarios due to race conditions, co-occurrence of mutually contradictory events, and many other ensuing complexities.
Functional programming comes to our rescue when dealing with such difficulties. Since it avoids modifiable states as much as possible, it nicely prevents us from having to worry about our sources of computation (e.g. variables) unexpectedly being corrupted in the middle of computational processes. One might argue that the principle of encapsulation circumvents such a concern, yet it should be noted that having to decide which pieces of data should be public and which of them should be private is in itself a cumbersome and error-prone process.
If only we can represent gameplay in terms of a cascade of function calls instead of a group of independent objects, wouldn’t it be great? That way, we will have the advantage of keeping everything in the game application as part of one large hierarchy of procedures, each of which only has access to its local state (e.g. variables that are either passed in as its function parameters or are locally declared) and nothing else. This means that all dependencies will have to be injected by means of arguments, which inevitably turns the overall syntax to be a bit verbose, yet nevertheless gets rid of any chance of interference which may otherwise be exerted to/from outside entities.
Let us start with a simple game loop. Any real-time game engine, as far as common sense goes, contains at least one “update” procedure which runs itself on a periodic basis. A typical object-oriented way of implementing it goes like this:
class Game
{
private State state;
Game()
{
state = new State();
Thread.start(updateLoop);
}
void updateLoop()
{
while (true)
{
state.update();
Thread.waitForNextFrame();
}
}
}
new Game();
It is conventional of an OOP-centered programming language, such as Java or C#, to start embodying a game application by first making a class that represents the game as a whole. Inside this “home class”, where everything related to the game is supposed to begin its life, we create the game’s state object and then run a thread which periodically updates it on a per-frame basis. This is a pretty neat way of running the game, except that here we are already introducing quite a degree of complexity to the whole system despite not having done anything substantial yet. The “Game” class in the above example has its own constructor method, an “updateLoop” method which runs within its own thread, as well as an internal state object which requires extra care for encapsulation so as to only let it be modified from within the update loop and nowhere else. The “updateLoop” method’s internal “while” loop must make sure to execute its internal procedures in the right order, while also making sure that their execution can be carried out safely along with things that are happening in other threads (e.g. networking thread, rendering thread, etc). Furthermore, the instantiation of the “Game” class must be done in the right order (i.e. after all of the external systems to which it depends have been initialized, yet before systems which depend on it are yet to be initialized). The peril of object-oriented programming is that it has a tendency of giving birth to a complex web of interdependencies, no matter how much we try to simplify our system.
A purely functional equivalent of the game loop system, on the other hand, could be written as below (in LISP).
(defun update-loop (state)
(wait-for-next-frame)
(update-loop (update-state state)))
As you can see, there is no such thing as a class here. The entire game loop is just a single function call (namely, “update-loop”), which calls itself at the beginning of each frame by means of tail recursion. The game’s state object is simply a parameter which repeatedly gets passed into the update-loop function as the only dependency, and by this, we can guarantee that the update loop is a purely functional system which does not interact with anything outside of its body. The “(update-state state)” function call returns the updated version of the current game state, and its definition is shown below.
(defun update-state (state)
(make-state (update-actors (get-actors state))))
The “make-state” function, as you may have already guessed, creates a newer instance of the game’s state and uses it as the input state of the next “update-loop” call instead of just modifying the existing state object. The reason behind this is that we want to prevent any potential race condition which may occur if other systems happen to be accessing/modifying the same exact instance. The “update-actors” function, just like the “update-state” function, returns the updated version of the current state of the game, but only the portion which pertains to its collection of actors (aka “characters”, “sprites”, or “agents”) and nothing else.
(defun update-actors (actors)
(cons (update-actor (car actor)) (update-actors (cdr actors))))
The chain of “cons” nodes, as shown above, is more or less a LISP construct which may not apply to other languages. The overall idea, however, applies quite universally. Every time we update the list of actors, we build a brand new list by cons-ing the newer instances of the actor objects in a recursive manner instead of just modifying the existing list.
This, again, is for the sake of preserving the entire history of state changes instead of tampering with the past remnants which may be still waiting to be visited by extraterrestrial beings (aka “external systems”) whose present moment in time could have been delayed by as much as a few milliseconds, due to the nature of time dilation (special relativity) which oftentimes inadvertently gets simulated by the lack of perfect parallelism in modern computing devices.
The “update-actor” function checks to see if the “actor” argument it received is just the end of the list (i.e. nil). If so, it won’t do anything. If not, it will proceed to search for the actor’s own update function by means of “(get-actor-update-func actor)” and then execute it in order to get the updated version of the actor object. This newer instance of the actor, just like the aforementioned ones, is something that is completely separate from its past copy.
(defun update-actor (actor)
(cond ((= actor nil) nil)
(else ((get-actor-update-func actor) actor))))
And in order to run the game as a whole, we must start the game’s loop somewhere. This involves the creation of the initial state, as well as the manual invocation of the update loop based upon that initial state.
(update-loop (make-state initial-actors))
But of course, the game itself consists of not just a list of actors but also many other things. This is not too complex a problem to solve, though. All we have to do is implement additional data types and their corresponding “get” and “update” functions, and then insert them into the game loop as additional function parameters.
(defun update-state (state)
(make-state
(update-actors (get-actors state))
(update-cells (get-cells state))
(update-events (get-events state))
(update-particleEffects (get-particleEffects state))
(update-soundClips (get-soundClips state))))
One major advantage of using this purely functional, append-only approach to the implementation of a game loop is that, since we are preserving the history of the game’s state instead of constantly overwriting it with more recent bits of data, the game’s update functions can have full access to the state’s past instances and therefore make decisions based upon the differential characteristics that can be derived by comparing the past and present (which means it opens up the gateway to the realization of first-order, second-order, and even higher order systems which often occur in physics/engineering and are represented in terms of differential equations). This is easily done by passing the copy of the state from the previous frame (aka “past instance”) into the update loop as an additional argument.
(defun update-loop (currState prevState)
(wait-for-next-frame)
(update-loop (update-state currState prevState) currState))
(defun update-state (currState prevState)
(make-state
(update-actors
(get-actors currState)
(get-actors prevState))
(update-cells
(get-cells currState)
(get-cells prevState))
(update-events
(get-events currState)
(get-events prevState))
(update-particleEffects
(get-particleEffects currState)
(get-particleEffects prevState))
(update-soundClips
(get-soundClips currState)
(get-soundClips prevState))))
(defun update-actors (currActors prevActors)
(cons
(update-actor (car currActors) (car prevActors))
(update-actors (cdr currActors) (cdr prevActors))))
(defun update-actor (currActor prevActor)
(cond
((or (= currActor nil) (= prevActor nil))
nil)
(else
((get-actor-update-func currActor prevActor) currActor prevActor))))
…
One of the specific use-cases of such a temporal stream of data lies on the area of kinematics. For a quick demonstration, let me first suppose that the “get-actor-update-func” function returns the “update-kinematic-actor” function if the type of “currActor” is equal to “kinematic”. This means that, if the actor we are updating is of type “kinematic”, the “update-kinematic-actor” function will be used update it. This function takes both the current and previous instances of the actor as its input parameters, and computes/updates the actor’s current position based on the comparison of its two instances in time (which reveals its current velocity).
(setf actor-update-func-table () ‘(
(‘static update-static-actor)
(‘kinematic update-kinematic-actor)
(‘dynamic update-dynamic-actor)
(‘abstract update-abstract-actor)
))
(defun get-actor-update-func (currActor prevActor)
(get-actor-update-func-iter currActor actor-update-func-table))
(defun get-actor-update-func-iter (actor table)
(cond
((= (caar table) (get-actor-type actor))
(cdar table))
(else
(get-actor-update-func-iter actor (cdr table)))))
(defun update-kinematic-actor (currActor prevActor)
(let ((currVelocity (- (get-position currActor) (get-position prevActor))))
(make-kinematic-actor
(+ (get-position currActor) (* currVelocity 0.8)))))
(defun make-kinematic-actor (position)
‘(‘kinematic position))
One might argue, “Well, why bother introducing such a bloated system, just to update the positions of the individual actors? Why not just let each actor have its own ‘velocity’ property, so that it can simply update its position at any moment in time base off of the explicitly specified velocity value?”
For a simple problem of kinematics, such a solution is sound indeed. It is when we start dealing with more complex, implicit kinds of problems that we seriously begin to face inevitable rise in complexity. Let us consider, for example, that each actor is not a kinematic point mass but a self-conscious animal (i.e. living thing) which has its own set of memories, desires, feelings, metabolic states, and other biological processes whose causal relations are not necessarily instantaneous in time (as opposed to atomic events in Newtonian mechanics such as application of force or displacement of a particle), but rather prone to emit delayed influences upon points in time that are quite far apart from one another. The constructor of such an organic entity will have to look like this:
(defun make-animal-actor (physicalTraits mentalTraits physicalMemory mentalMemory)
‘(‘animal physicalTraits mentalTraits physicalMemory mentalMemory))
“physicalTraits” and “mentalTraits” are both fixed lists corresponding to the intrinsic physical/mental characteristics of the animal, whose contents are not meant to be changed under usual circumstances. These two lists, therefore, can be said to be time-invariant. “physicalMemory” and “mentalMemory”, one the other hand, indicate the most recently added elements of the two streams of data (which represent the history of the animal’s physiological state and the history of the animal’s psychological state, respectively) which continuously circulate their elements as time passes by in the form of a queueing system. At each update loop of the game, newer memory elements enter these streams via the animal’s sensory organs (i.e. external stimuli), while memories that are sufficiently old get discarded becasue these streams cannot keep growing forever (unless the computer is endowed with infinite memory space). The animal makes decisions based on both its most recent memories as well as past memories that are extracted from its past self, and produces a newer copy of itself which corresponds to its future self.
(defun update-animal-actor (currActor prevActor)
(let ((physicalTraits (get-physical-traits currActor))
(mentalTraits (get-mental-traits currActor))
(currPhysicalMemory (get-physical-memory currActor))
(prevPhysicalMemory (get-physical-memory prevActor))
(currMentalMemory (get-mental-memory currActor))
(prevMentalMemory (get-mental-memory prevActor)))
(make-animal-actor
physicalTraits
mentalTraits
(make-physical-memory currPhysicalMemory prevPhysicalMemory)
(make-mental-memory currMentalMemory prevMentalMemory))))
The example shown here, however, only allows the animal’s memory to refer to only 1 step (frame) back in time, which suppresses its ability to make long-term decisions based upon long-term memories. If we want to simulate realistic physiological/psychological phenomena, we will need streams of memory elements that are sufficiently long so as to allow each animal to look up not only its most and second most memories, but also memories that were created minutes ago, hours ago, days ago, or even months ago.
The realization of long-term memory streams can easily be done by adding additional references to the game’s past, as shown below. “prevState2” refers to the past instance of the game’s state that was made 2 steps back in time instead of just 1.
(defun update-loop (currState prevState prevState2)
(wait-for-next-frame)
(update-loop (update-state currState prevState prevState2) currState prevState))
And if we want the game to be able to refer to up to 3 steps in time instead, we will need something like:
(defun update-loop (currState prevState prevState2 prevState3)
(wait-for-next-frame)
(update-loop (update-state currState prevState prevState2 prevState3) currState prevState prevState2))
This, of course, starts to become too verbose as we keep elongating the game’s memory stream. Therefore, a much more realistic implementation would be to represent the history of the game’s state as a single list variable rather than a sequence of manually specified function arguments.
(defun update-loop (stateHistory)
(wait-for-next-frame)
(update-loop (cons (update-state stateHistory) (without-last stateHistory))))