I Created a Politically Corrupt AI

(This was originally posted in Squeaky Wheel’s website.)

I’ve been using Genetic Algorithm as an aide for game design and development. It fills me with excitement that I can simulate natural selection to help me look for the best solutions to problems. Now I’ll tell you the story of how I used it to improve our AI.

My GA knowledge is still somewhat limited. I learned how to write code for it using this website (Go read it. It’s awesome! So unlike smarty academic papers.) To give you an idea in casual speak, GA is basically simulating the theory of evolution to look for the most “fit” solution. In this simulation, the species or “individuals” are the solutions to the problem. At the start, a certain number of individuals are spawned with random configurations. As such, most of them are dumb solutions at the beginning. Each of them are then assessed and given a fitness score. The ones with higher score means they are closer to the solution. Based from this initial population, we spawn the next generation. To do that, we either mutate or let them breed (Yes, solutions can mate) with a rule that those with higher fitness score has a higher chance of being selected for mutation or breeding. With this new generation, we repeat the process of assessment and spawning the new generation until we can find that one individual that solves our problem.

When coding a GA, you need some important pieces. These are the individual representation, the fitness assessment function, mutation function, and crossover function. If you have these four, you can run a GA. Individual representation is a bit tricky. How do you represent a solution that can also be mutated and bred? One of the most common is a list of bits. This can be represented by a list of booleans or just integers and use bit manipulation. Mutation is just then flipping a random number of bits. Breeding or crossover is simply exchanging a certain number of bits from two individuals.

Representation by bits is the only representation I know of. It’s what AI Junkie taught me and I sticked with it. That’s until I’ve read a book called “Essentials of Metaheuristics”, a highly recommended book. The contents are written in an informal way, not in an academic bullshit way. It’s a primer on different algorithms in the field of metaheuristics. Most of it, though, is GA. From there, I learned that you can represent an individual with anything. It can be lists, trees, graphs, your own data structure. Mutation and crossover can be any made up alteration of your representation. It can be adding a child, removing a child, changing a value, swapping nodes and edges. Anything! I realized how dumb I was for not going to that thought.

That gave me an aha moment. What if I automate the creation of our AI using GA. Our AI configuration is very simple. At the same time, AI is also the most neglected part of our game. We haven’t touched it for a long time. We have a working AI that I configured by hand. But then, our mechanics have already changed too much that we don’t know if it’s still competitive. Configuring a new AI would take time.

My team gave me a week to work on this, May 2-8, 2016. I’m not so sure if it would work. What if looking for a better AI takes time, like it would take days running the simulation. I certainly thought so because the assessment function is to let two AI players pit against each other. The one who wins has a bigger fitness score. Now, a single playthrough takes time, even if I speed it up. The point is, making the GA could be a waste of time.

The first thing I did is I made a fast mode of our game. No animations, movement becomes teleportation, removed the standby/wait times, etc. It wasn’t easy. I don’t have time to write another version of the game solely for GA. Instead, I’m using what we have now and provided a mode that it can be played extremely fast. Finally, I have a mode where AI vs AI takes around 1 minute to complete 15 turns. Still not fast enough, but quite good already.

Then I made something called a “multi frame” GA. Basically, it’s GA that is spread in multiple frames. Note that the assessment function is for AI to play the game. So the GA must wait for such game to end before it can move to the rest of the algorithm. In fact, if there are 10 indiduals in a generation, 10 games must be played before moving on to spawn the next generation.

Our AI configuration is all code. We use a utility based AI, by the way. It is represented as a set of “task scorers”. Each scorer has an arbitrary set of “considerations”. These considerations are classes that help compute the score for the task. The AI generates all the possible tasks, scores them using the scorers, and picks the one with the highest value.

My plan is to use GA to generate different combinations of these scorers and considerations until we get the one that beats the current best configuration. Before anything else, I needed my configuration to be saved in a file. Every time the GA finds a better AI, it should save the configuration in a file. So I turned the AI configuration into XML. I used the class names and variables of consideration classes in this file. I load them back using reflection. It looks like this now:

<ScorerSet id="IndividualZero" fitness="1" timestamp="">

 <Scorer taskId="Bribe">
   <Consideration name="BlockadedDistrictConsideration" />
   <Consideration name="TerrorizedConsideration" />

   <Consideration name="MinimumBudgetConsideration">
     <Variable type="NamedInt" name="minimumBudget" value="1000" />
   </Consideration>

   <Consideration name="ReachableConsideration">
     <Variable type="NamedFloat" name="multiplierIfUnreachable" value="0" />
   </Consideration>

   <Consideration name="MustHaveMatchingPlatformConsideration" />

   <Consideration name="ReachReputationConsideration">
     <Variable type="NamedFloat" name="populationPercentage" value="0.85" />
   </Consideration>

   <Consideration name="BonusTuningConsideration">
     <Variable type="NamedFloat" name="bonusToSet" value="1.0" />
   </Consideration>

   <Consideration name="CommandPointsConsideration" />

   <Consideration name="NeighborCountConsideration">
     <Variable type="NamedInt" name="desirableCount" value="4" />
   </Consideration>

   <Consideration name="OpponentStaffCountConsideration" />

   <Consideration name="BribeBetterThanCampaignConsideration">
     <Variable type="NamedInt" name="minReputationGainDifference" value="1000" />
     <Variable type="NamedInt" name="rankIfMet" value="17" />
     <Variable type="NamedInt" name="bonusIfMet" value="10" />
     <Variable type="NamedFloat" name="multiplierIfMet" value="5" />
   </Consideration>

   <Consideration name="ScandalCountReachedConsideration">
     <Variable type="NamedInt" name="scandalCount" value="4" />
     <Variable type="NamedFloat" name="multiplierIfMet" value="0" />
   </Consideration>
 </Scorer>

 <Scorer taskId="RaiseFunds">
   <Consideration name="BlockadedDistrictConsideration" />
   <Consideration name="TerrorizedConsideration" />

   <Consideration name="ReachableConsideration">
     <Variable type="NamedFloat" name="multiplierIfUnreachable" value="0" />
   </Consideration>

   <Consideration name="HasSignificantFundsConsideration">
     <Variable type="NamedInt" name="preferredAmountToRaise" value="1000" />
   </Consideration>

   <Consideration name="BonusTuningConsideration">
     <Variable type="NamedFloat" name="bonusToSet" value="1.0" />
   </Consideration>

   <Consideration name="LowFundsConsideration">
     <Variable type="NamedFloat" name="fundsThreshold" value="0.3" />
   </Consideration>

   <Consideration name="CommandPointsConsideration" />
   <Consideration name="HigherReputationConsideration" />

   <Consideration name="NeighborCountConsideration">
     <Variable type="NamedInt" name="desirableCount" value="4" />
   </Consideration>

   <Consideration name="NearBailiwickConsideration" />
 </Scorer>

 <!-- ... Rest is ommitted -->
</ScorerSet>

The mutation function then is just a matter of:

  • Add random consideration
  • Remove random consideration
  • Change some random variables

Crossover between two individuals is simply swapping a random number of considerations.

For the initial population, I used our existing AI as a starting point. I called it “Individual Zero”. The first population are individuals that are mutated versions of him. Now with all the pieces together, I have a GA that looks for a better AI.

First Runs

When I was about to finish, I was too excited to run it. I know it will take time so I plan to run the simulation overnight when I’m asleep. It was Saturday night. I’m sleepy and tired. I fixed some errors that would potentially halt the simulation. I set the settings for the fast mode. Every game lasts only 15 turns. The population size is set to only 10. Then finally I let the baby run. I watched the first few AI matches. After a while, nothing goes wrong, I locked the laptop and went to bed.

When I woke up, I checked it immediately. The simulation had hung. I looked at the Task Manager. 90% RAM usage. So I closed it. But lo and behold, it generated 10 AI configurations, each one better than the last one before it. So I was like “that went well”. I pushed my work and restarted my laptop. Then my laptop won’t start. It only said “Diagnosing Your PC”. But I wasn’t worried. I know I didn’t do anything stupid. The simulation just probably messed up the memory. An hour later, my laptop was alive again. I immediately fixed the memory leak. Lesson learned when writing a resource intensive GA like this one.

After coffee, I decided to play a game against the new AI and see if it’s really indeed better. Maybe it’s just better against other AI but not humans. So I used my usual strategy. Bribed supporters on the first few turns. I acquired districts as soon as I can. I was winning. Every 5 turns, the game shows this graph about how many supporters each candidate has. I beat his numbers every time. I even have more acquired districts than him. Am I really playing against a better AI? On the last turn, I’ve made my actions. I knew I was gonna win. I controlled more districts than him. That dread that I probably just wasted time returned again. Election came… the AI won an unbelievable landslide. Jaw dropped. Turns out he didn’t care about the voters and was befriending more patrons than me. Well, I guess I created a monster.

New Stuff and a Tip on Starting Coding Momentum

Development of Party Animals has been hanging around for over a year already (or years) but the truth is that the game’s mechanics are not yet zoned in. We’re still looking for the fun part. We’re at the stage when we are adding new mechanics and testing them out as soon as we can then decide whether to keep them, change, or discard. If we’re not having fun with it, our target players most probably won’t. While we unanimously agree that what we have is fun enough, something is still missing. This post will be enumerating what we’ve done so far. As a bonus, if you stay a while, you’ll get a tip on how I start my coding momentum.

Command Points

As context, Party Animals is a game about winning an election. The main mechanic unit of the game are the Staff which the player can move around in different districts and make them execute actions. The game is basically an attrition with an opponent through Staff actions.

We introduced the concept of Command Points (CP) to control the movement of Staff such that players are forced to strategize on which district to move next as usage of such units now have cost. CP cost is simply defined as the shortest district distance of a Staff from its Candidate (a Candidate is just another Staff with special abilities). If a Staff is in the same district as its Candidate, then CP cost for the Staff is zero. CP resource is assigned to each candidate at the start of the turn. It is increased when certain campaigning days are reached. In real life, we’d like to think of this as the cost of planning with your Staff that is in another city or province.

During playtesting, Command Points had a direct effect on Staff movement. During early game, players only move their Staff along one adjacent district distance from their Candidate.

Pay CP first before you can use your Staff
Pay CP first before you can use your Staff

New Meaning of Reputation

Reputation is one of the most important metric in our game. It directly tells whether or not people will vote for a candidate in a certain district. It used to be a percentage of the population in the district that is willing to vote for you. It’s a value between 0 – 100. Not anymore. It’s now the actual count of people that will vote for a candidate. This implies that districts with more population is now harder to own (get at least 50% of voters).

Due to this change, we introduced the concept of Reputation Decay. A percentage of a candidate’s reputation in a district is deducted if the Candidate has no Staff stationed in that district. The message is that voters are fickle. They won’t vote for someone unless they constantly stick around, or the candidates give them money.🙂

Raise Funds

We finally have this Staff action. It’s in the game design papers ever since. We designed it such that the more Reputation a candidate has in a district, the more money it can raise. That’s how it is in real life. People are willing to give you money if they like you.

Now players can use the people they've convinced to give them money
Now players can use the people they’ve convinced to give them money

Patrons

I had a direct hand in introducing this mechanic and I’m happy with it. Before this change, each district has a Kapitan which Candidates can have a relationship with (in a friendly way). The only effect it had was during elections. If you’re closer to the Kapitan, then people will vote for you in that district.

As a strategy gamer, I feel that the game doesn’t have much avenue in acquiring ‘things’ that generates resources, which I really like in such games. Mechanics like building an expansion in Starcraft to exploit new resources, building that Bank to generate gold in Civilization, etc. I suggested what if there are patrons or sponsors that players can court. They could be an influential family in the district, a business man, celebrity, or another politician. You gain some effects if you can get them to support you like giving you funds per turn, or slowing Reputation Decay.

Our game designer, Tristan, came up with Patrons. Kapitans were discarded. There are now 3 Patrons in each district. Each Patron has a distinct effect depending on a player’s relationship with such. One Patron had an effect when Raising Funds, another one for CP cost (reduced or increased), and last one had an effect when doing Sortie (increases or decreases the amount of reputation gained). A player can decide to make a good relationship with one or more of these Patrons using the Gift action.

Patronage politics at its best!
Patronage politics at its best!

Scandals

Everybody loves scandals… as long as you’re not implicated. Our political climate is rife with it, even during elections. I’ve heard in an interview with a local election campaign consultant that there’s this one politician who didn’t win but spent so much. He was running for Senator. When he was asked to compute his expenses divided by the votes he got, he spent around Php5000 per voter. The election campaign consultant then said “Imagine if he bought votes instead. That’s only Php500 per voter. He would have gotten ten times more votes.” Vote buying is a big scandal, but if you’re the one running the election, it could be very tempting.

Given such fact, the concept of Scandals is a vital mechanic in Party Animals. Of course the representation is rather simplified. Scandals in our game is just a number of scandalous acts that a candidate has done in a district. Actions like Bribe and Smear Campaign increases the Scandal Count. Other neutral actions like Campaign, Sortie, Gift can become scandalous (increases the Scandal Count) if a bigger amount of money was used to carry out such actions. If you didn’t know, COMELEC has a prescribed amount of election money to be spent. It differs per location and position. You can get sued if you’re found spending more.

Red means "scandalous"
Red means “scandalous”

At the start of the next turn, each “unchecked” Scandal are then “checked” if it is revealed or not. We are running a formula to this. If it gets revealed, the game imposes harsh penalties for the candidate on that district. The penalties are in the form of reduction of Patron relationship, Reputation and increased CP cost on the district. The higher the Scandal Count, the higher the probability of it getting revealed.

As simple as it looks, implementing Scandals gave us a lot of headache. There were a lot of design issues that we’ve encountered; there were some cases that we needed to consider. As of writing, I’m still working on the final touches of the mechanic.

The Tip

As promised, the tip I’m sharing is about how do I start my coding momentum. It may not work for everybody but it certainly worked for me. Programmers are peculiar creatures. They need to be in a certain state so that they can work productively. But reaching that state is hard because programmers must be working to reach it. It’s kind of like an “almost” chicken-egg problem. Reach that state to get work done but work to reach that state.

As I ponder upon this, I thought about working out. People hate it. It’s tiring. The time used for it could have been used for something else. To make things worse, the main benefit of working out is kind of an abstract bullshit: health. Then I thought of myself. I go to a martial arts gym but how could I do it? I know I need to do it but what really gets me to go there and tire myself? The answer is really quite simple. “I packed up my gym stuff.” Packing up gym stuff is easy. It doesn’t take a lot of will. But it starts there. Next, I go out and commute to the gym. While I’m at a bus, it’s already hard for me turn back and change my mind.

Back to programming work, I can ask the same analogous question, “What’s the least and simplest thing that I can do to start coding?” My answer is “write one line of code”. It works for me like sorcery. It might be different for you, so go find yours.

One AI is Easy, but FOUR?!?!?

I have implemented my own FSM and Behavior Tree systems for AI in games. I know how to properly use them in most cases. They’ve worked really well. I honestly think I already have the working knowledge for the AI of the kind of games I’d like to make… until Party Animals came. I felt stupid and incapable.

FSMs and Behavior Trees are good for single agent AI. Single agent here means that the simulated behavior is only responsible for itself. It doesn’t see other agents and try perform tasks together more effectively. For example, let’s describe a single agent behavior of an enemy unit guarding a gate:

  • Unit stands still near the gate
  • If it sees a player unit within its range,
    • Chase and attack that player unit
    • If player unit dies or goes out of range, go back to gate

Now let’s say we assign two enemy units on that gate with this behavior. It will still work but probably not the best strategy to defend the gate. Both of them will chase the target as soon as it sees one. They could have decided that one of them chases the player’s unit while the other one remains on guard. This is no longer single agent. Multiple agent behavior is another beast with its own set of complexities.

AI vs AI in Action!

In Party Animals, a player controls 4 units. They are called “Staff”. One is the candidate character himself and the other 3 could be any combination of Police, Accountant, Investigator, PR Manager, or Goon (we’ll add more). Each staff has a common and unique sets of abilities. The game is turn based. Each Staff can execute one action and can also move to an adjacent district once in every turn. The player may choose to move then execute an action or execute first then move to another district for each staff. Aside from this, the player also has to assign budget for each action. The budget allocated affects the effect of the action.

Here’s the college project: implement an AI opponent that controls 4 Staff units that should pose a challenge to the player. It may not play the best moves, but should at least be smart enough to pick and order its actions sensibly. Sounds easy? (If yes, email me your solution please.)

I think the main difference between single agent AI systems and multiple agent AI ones is the concept of planning. There’s no planning in FSMs or Behavior Trees. You can simply pick which branch to choose based on some conditions and let the agent perform the behavior described in that branch. You can’t simply pick a branch of behavior for a multiple agent AI. There are questions to be answered before letting agents do their tasks:

  • Are the agents assigned the best task for them in the current situation?
  • Is the order of execution of agents’ tasks give the highest benefit?
  • Are the selected actions sensible enough in the player’s perspective? Is the AI playing the game right?

Single agent systems just can’t answer these questions. I had to look for other ways.

Solution 1: Genetic Algorithm

I love brute force solutions. A genetic algorithm could certainly be used for Party Animals. Since the game is turn based, there’s no pressure for the AI to run as fast as possible. I don’t need the best answer either. I was thinking that I could run 1000 generations for each turn and select the best gene as the set of actions that the AI would take in that turn. In the end, I decided against it because I’m not so sure how long 1000 generations would take. I mean sure the game is turn based but we don’t want the player to wait too long for the AI to execute. The chromosome encoding/decoding itself would take too much time to implement as there are lots of possible actions. The fitness scoring would be quite complicated, too. There are lots of variables to consider.

Solution 2: SHOP Planning System

Here’s the link to the paper of the algorithm. It looks simple but I’m not quite sure how to implement it. I don’t even know if it’s a multi agent solution. It’s more like a distant cousin of GOAP.

Solution 3: Resource Assignment Algorithm

I found this one in Gamasutra. I liked this one because it’s really easy to understand and convert to code. It’s very straightforward. I implemented it as soon as I understood it. The current AI actually uses this solution. The algorithm is somewhat brute force but wouldn’t take as much time as in Genetic Algorithm. These are the major steps:

  1. Generate all possible tasks
  2. Generate all possible assignments (all possible agent-task pair)
  3. Assign a score to each possible assignment (this is based on game rules)
  4. Sort possible assignments by score in descending order
  5. Assign tasks to agents from the sorted possible assignments until all agents has a task

The hardest part of this solution is step 3. There’s no one rule how to compute the score for each task. It highly depends on the rules and the current conditions of the agents of the AI. In a way, you’re like turning the quality of a task that is to be assigned to an agent into a number. This value should at least be comparable for all types of tasks since they are all treated the same way when sorted in step 4. Coming up with these computations is not easy. I think I need to study a special math for this.

For instance, the Campaign task has various factors like population, the platform value of the candidate, the concern value of the target district, and the distance of Staff that will carry out the task. Another task called Gift has another set of factors. These are population, inverse of platform value of the candidate (meaning the lower the value, the more likely the task should be done), and distance. Campaign has 4 factors while Gift only has 3. How do I come up with a formula or system of scoring such that it gives reasonable values among these two tasks? There’s also the case of precedence. Campaign should be a more important task than Gift but because it has more factors, it could happen that it has a much lower score. The scoring system should be able to compensate for this.

Resource Assignment main function
Resource Assignment main function

Solution 4: Dynamic Task Allocation

This is a lengthy Master’s Thesis material. I did not understand it the first time I read it. I learned to appreciate it when I ran it through again. It’s actually very clever. The algorithm was inspired from swarm colonies like ants, bees, and wasps. It turns out that colonies don’t have a central command that assigns tasks, not even the queen. How does the colony know which tasks to prioritize then when certain circumstances arise?

The individuals of the colony emit pheromone stimuli. Larvae emit pheromone to signal their hunger, sentries emit pheromones to signal intruders, etc. Each caste in the colony has a set of thresholds associated to each stimulus. When a stimulus becomes greater than an individual threshold, that individual will answer to that stimulus with great probability. Answering to that stimulus will in turn lower the stimulus. For example, worker ants would have a low threshold for a task say “gather food” but has a high one for “defend colony” task. This way, worker ants will respond to hunger stimuli more than to intruder alert stimuli. You can probably imagine by now what a soldier ant’s threshold values looks like.

I would have used this algorithm had I understood it earlier. I was almost finished with the implementation of Resource Assignment Algorithm. I could not afford to tear it down and start again. We need a working AI soon. Either way, I could still add this algorithm in another AI profile in the future, if there’s still time.

The Party Base Code

After implementing some of the basic features of the game, I could definitely say I’m now an official Party Animals programmer. There’s no turning back now. I’ve invested huge amounts of time, effort, and code already. Might as well make a blood oath that I’m going to code for this game until it is released.

Starting a code base is both challenging and exciting. I have to learn new stuff and unlearn some things that I used in my previous game. I have to reset my mindset that the project is still in its early stage. Lots of tools and systems are still missing. It’s unlike the code base of a built game where the systems are already in place and I have the thought process on how to change things. This time, I’m also not a lone programmer anymore. I have to take that into consideration.

In this post, I’ll show you what I’ve done so far.

Camera Settings and Resolution

I’d like my camera and 2D Toolkit settings to be consistent. I want the orthographic size of my cameras to be 1 because it feels more consistent rather then specifying some other number. It also helps with resolution independence. We’ve also decided to use 1366×768 as the base resolution. In short, I have to rip apart the current settings (sorry Julius). I’ve requested Ryan to resize the assets to make it suitable for the new resolution. 2D Toolkit sprite collections have to be regenerated. With this, fixing the positions and colliders of the districts was also inevitable.

IslandResized
Resized districts. Still used Julius’ clouds and wave simulator. They’re cool!

uFrame

Party Animals is a systems heavy game where game rules could change a lot. I’ve decided that I should incorporate some form of framework to it so we could at least have some structure to where code goes. Julius used StrangeIoC. Then I was able to buy uFrame because it was on sale. I found uFrame to be superior than Strange. So I had to rip apart the current code base (sorry again Julius).

I’ve got to say don’t buy this product if you’re not a programmer or even a newbie coder. It’s hardcore code framework rather than a utility extension like most other asset store products. I wonder how they sell this thing. Only programming nerds are excited by this.

I really like it, though. It forces me to adhere to MVVM and have some kind of structure and separation on where the appropriate code goes. It forces me to follow the rule that views should react to changes in models. Only controllers can mutate models. I had a really hard time understanding it at first. Data initialization is not that straightforward. I even asked dumb questions to their forums. One reply said “Ugh, awkward questions… but here’s what you do…” I’m starting to get used to it now. I’ve implemented the features so far using uFrame.

uFrame
Models in uFrame are code generated. They are authored like this.

Staff Movement

The Staff and Districts are the main movers of the game. Obviously, these two had to be implemented first. The first action I’ve done is movement. Things have to be implemented a little different when using uFrame. If I had done it like I always do, I just move the staff avatar then change its current district. Not anymore. In uFrame, you have to go through a controller. I have a command called ChangeDistrict() which updates the current district in the model. The avatar (view) has been bound to the current district. It is notified whenever the current district changes. When it does, that’s the only time that I could move the avatar to the new district. See the difference there? The direction of execution is always Model changed then View reacts to it, not the other way around.

Staff Campaign and Unity UI

Party Animals is so UI heavy. I haven’t played with Unity UI yet because Warrior Defense’ UI was still using 2D Toolkit. I have no escape now. Julius is using it and highly recommends it. I hate to say that I do like it after trying it out. RectTransform is freaking awesome! I hope it won’t bite us later. I’m still not sure how to go about atlasing, hi-res assets replacement, and draw calls.

Campaign is one of the basic Staff actions. This action has a lot of parameters so I decided to use a uFrame model for it. I’m glad I did because I learned a lot of the uFrame flow when I implemented it. The major one is UI catch cases. There were lots of these. Since I have to implement in uFrame mindset, working around it is also very different. I always say “update model then UI, update model then UI…”

My first complex uFrame and Unity UI combo!
My first complex uFrame and Unity UI combo!

Generally, I’m happy with the base code right now. I’ve got two basic actions implemented. I now have prior knowledge on how to implement the next ones. Can’t wait to show you minimum playable version of the game!

How I was able to finish Warrior Defense

As of writing, Warrior Defense is not really finished. Software is never finished. I’m still updating it. I haven’t released for iOS yet. Right now, I’m completing a web version. But the game is out there. Some people are probably playing it as you read this. I’m quite proud of that.

There’s a phrase in the game development world that says something like “It’s easy to start a game but finishing one is very hard.” This is very true. Just ask any game jam (our term for hackathon) participants. I’m writing this post in the hopes that it will help or at least inspire game developers to push on and finish their games.

Why?

I think the main driving force for finishing a game is the answer to the question “Why should I?” I always ask myself this every time I encounter a stumbling block be it technical problem, laziness, boring feature to implement, or loss of motivation. The answer to this question should be profound enough to make you jump up and feel motivated again.

“I should finish Warrior Defense because I want to prove that I can finish a mid sized strategy game on my own.” That was my reason. I want to present myself as a game developer in the strategy or action genre. My first game should probably be one.

Very early version. Naked dudes slugging it out.
Very early version. Naked dudes slugging it out.

Pressure

If you’re really committed to finishing a game, it shouldn’t be a problem if you let yourself to be in some pressure, right? Because if you don’t, then you’re not really committed. Guess what, you can impose pressure by yourself. I call them self imposed pressure.

The first in my list of self imposed pressure is joining the One Year Game Challenge last year with 5 times the minimum pledge value. 1YGC is a one year program by IGDA Manila to help developers finish their games. Each participant hands in a monetary value not less than 1000 to IGDA Manila. They get their money back if they released their game with a certain number of downloads within a year. If they don’t, the money is considered donation. I pledged 5000 for fun!

Another self imposed pressure is to tell people a release date consistently. Choose at least an exact month and year so you have an answer ready every time someone asks you. Believe me, a lot will ask you. Mine was June 2014 (but the game was released on August). What it does is it sets a deadline for yourself. You already told people, you better work on it or risk the perceived embarrassment.

Spending a lot for the game is another self imposed pressure. I bought lots of Unity Asset Store products that I could use in my game. Some of them are quite expensive. I also spent a big amount of my budget for artists and music. What this does is it tells you that there’s no turning back now. You’ve already spent this much, better finish that damn game!

Last of my list is posting the progress of the game to everywhere. I uploaded the game to Gamejolt then posted the game to various tech or gaming groups in Facebook. What you’re really doing is you put expectation to people that you’re making a game and you’re bound to show them a polished version eventually.

With these multiple self imposed pressure stacked on me, I should get my shit together and work on the game every time I can. If all fails, I go back to “Why should I?”

Release version. Looks spiffy.
Release version. Looks spiffy.

Luck

I can’t deny that I got lucky at times. Luck does have a hand in finishing my game. I was able to get really awesome artists to work with me for a “friendly” price. I’m very grateful to Robot with a Smile (Marvin and Shelly). I’m lucky enough to know Kane Aoki and the guys at Dualist. He makes awesome music for a very reasonable price. I hope you guys get more gigs after Warrior Defense.

I feel lucky that I found out about Full Mana Studios (Mars, Jaica, Mandy). They’re the reason that I was able to quit my full time job. They gave me a part time job so I could spend more time on my game. They also eventually funded the game and I was able to pay my artists in full.

To conclude, I hope this post gave you ideas on how to go about finishing your game. It’s hard I know, but it’s doable. Answer your “Why should I” and think of clever ways to impose pressure on yourself. Let’s finish more games!

A Generic Duration Timer Class

In game development, there are a lot of instances where you would like to do the following:

  • Wait for X seconds
  • Fly for X seconds
  • Fire for X seconds
  • Move forward for X seconds

The common element in these actions is the concept of a time duration. The most common solution that I see in tutorial pages looks like the following:

public class SomeComponent : MonoBehaviour {
    [SerializeField]
    private float durationTime; // the time to wait or go through

    private float polledTime;

    void Awake() {
        this.polledTime = 0;
    }

    void Update() {
        this.polledTime += Time.deltaTime;

        if(this.polledTime >= this.durationTime) {
            // time's up
            // maybe reset or do something since duration is up
            return;
        }

        float ratio = this.polledTime / this.durationTime;
        // do something with ratio like interpolation (lerp)
    }
}

This is good enough, but we can do something better. Imagine if you are maintaining more than one duration time. You’d probably do something like this:

public class SomeComponent : MonoBehaviour {
    [SerializeField]
    private float waitDurationTime;

    private float waitPolledTime;

    [SerializeField]
    private float fireDurationTime;

    private float firePolledTime;

    void Update() {
        UpdateWait();
        UpdateFire();
    }
    
    private void UpdateWait() {
    	this.waitPolledTime += Time.deltaTime;

        if(this.waitPolledTime >= this.waitDurationTime) {
            // time's up
            // maybe reset or do something since duration is up
            return;
        }

        float ratio = this.waitPolledTime / this.waitDurationTime;
        // do something with ratio
    }
    
    private void UpdateFire() {
    	this.firePolledTime += Time.deltaTime;

        if(this.firePolledTime >= this.fireDurationTime) {
            // time's up
            // maybe reset or do something since duration is up
            return;
        }

        float ratio = this.firePolledTime / this.fireDurationTime;
        // do something with ratio
    }
}

We can see here that the floating point arithmetic is repeated for each timed duration domain. A simple solution to manage this is to refactor and create a reusable DurationTimer class.

using UnityEngine;

/**
 * Generic class for implementing timers (specified in seconds)
 */
public class DurationTimer {
    private float polledTime;
    private float durationTime;

    /**
     * Constructor with a specified duration time
     */
    public DurationTimer(float durationTime) {
        Reset(durationTime);
    }

    /**
     * Updates the timer
     */
    public void Update() {
        this.polledTime += Time.deltaTime;
    }

    /**
     * Resets the timer
     */
    public void Reset() {
        this.polledTime = 0;
    }

    /**
     * Resets the timer and assigns a new duration time
     */
    public void Reset(float durationTime) {
        Reset();
        this.durationTime = durationTime;
    }

    /**
     * Returns whether or not the timed duration has elapsed
     */
    public bool HasElapsed() {
        return Comparison.TolerantGreaterThanOrEquals(this.polledTime, this.durationTime);
    }

    /**
     * Returns the ratio of polled time to duration time. Returned value is 0 to 1 only
     */
    public float GetRatio() {
        if(Comparison.TolerantLesserThanOrEquals(this.durationTime, 0)) {
            // bad duration time value
            // if countdownTime is zero, ratio will be infinity (divide by zero)
            // we just return 1.0 here for safety
            return 1.0f;
        }

        float ratio = this.polledTime / this.durationTime;
        return Mathf.Clamp(ratio, 0, 1);
    }

    /**
     * Returns the polled time since it started
     */
    public float GetPolledTime() {
        return this.polledTime;
    }

    /**
     * Forces the timer to end
     */
    public void EndTimer() {
        this.polledTime = this.durationTime;
    }

    /**
     * Returns the durationTime
     */
    public float GetDurationTime() {
        return this.durationTime;
    }

}

What we did here is we simply contained the duration timer variables and routines in a separate class. Take note of the usage of Comparison functions in HasElapsed() and GetRatio(). Read here for the reason why.

Let’s look at the basic usage using of this class:

public class SomeComponent : MonoBehaviour {
    [SerializeField]
    private float duration; // the time to wait or go through

    private DurationTimer timer;

    void Awake() {
        this.timer = new DurationTimer(this.duration);
    }

    void Update() {
        this.timer.Update();

        if(this.timer.HasElapsed()) {
            // time's up
            // maybe reset or do something since duration is up
            return;
        }

        float ratio = this.timer.GetRatio();
        // do something with ratio like interpolation (lerp)
    }
}

By using this class, we reduce the clutter of floating point arithmetic (increment, check, compute ratio). We use the functions of the class instead, making it more readable. See how it looks like when it’s used for more than one timed duration:

public class SomeComponent : MonoBehaviour {
    [SerializeField]
    private float waitDuration; // the time to wait or go through

    private DurationTimer waitTimer;
    
    [SerializeField]
    private float fireDuration;
    
    private DurationTimer fireTimer;

    void Awake() {
        this.waitTimer = new DurationTimer(this.waitDuration);
        this.fireTimer = new DurationTimer(this.fireDuration);
    }

    void Update() {
        UpdateWait();
        UpdateFire();
    }
    
    private void UpdateWait() {
    	this.waitTimer.Update();

        if(this.waitTimer.HasElapsed()) {
            // time's up
            // maybe reset or do something since duration is up
            return;
        }

        float ratio = this.waitTimer.GetRatio();
        // do something with ratio like interpolation (lerp)
    }
    
    private void UpdateFire() {
    	this.fireTimer.Update();

        if(this.fireTimer.HasElapsed()) {
            // time's up
            // maybe reset or do something since duration is up
            return;
        }

        float ratio = this.fireTimer.GetRatio();
        // do something with ratio like interpolation (lerp)
    }
}

We can also reuse this class if we’re making other frameworks that uses time.

public class WaitAction : FsmAction {
    private DurationTimer timer; // pretty cool huh?
	
    ...
}

Level Design Process of Warrior Defense

I put out a poll on Facebook asking people whether I should write about the level design process; or optimizations done for Warrior Defense. Level design process won. I think it won because I mentioned that I used a genetic algorithm in making levels. Maybe it sounded cool to them, but really, genetic algorithms are just glorified brute force. So don’t be impressed when someone brags that they can code a genetic algorithm. Here goes:

Let me begin by describing the level data model. A level is simply a collection of wave sets. Each wave set is a collection of spawn sessions. Here’s a level with 3 waves represented in XML:

<Level initialResource="400">
  <Waves>
    <WaveSet notification="">
      <Spawn unit="Critter" time="0" number="22" rate="1.1" startGroup="START_1" goalGroup="GOAL_1" />
      <Spawn unit="Critter" time="10" number="22" rate="1.1" startGroup="START_2" goalGroup="GOAL_2" />
    </WaveSet>
    <WaveSet notification="">
      <Spawn unit="Runner" time="10" number="1" rate="1" startGroup="START_1" goalGroup="GOAL_1" />
      <Spawn unit="Critter" time="0" number="25" rate="1.2" startGroup="START_1" goalGroup="GOAL_1" />
      <Spawn unit="Runner" time="25" number="1" rate="1" startGroup="START_2" goalGroup="GOAL_2" />
      <Spawn unit="Critter" time="15" number="25" rate="1.2" startGroup="START_2" goalGroup="GOAL_2" />
    </WaveSet>
    <WaveSet notification="">
      <Spawn unit="Critter" time="0" number="27" rate="1.2" startGroup="START_1" goalGroup="GOAL_1" />
      <Spawn unit="Runner" time="11" number="1" rate="1" startGroup="START_1" goalGroup="GOAL_1" />
      <Spawn unit="Critter" time="13" number="27" rate="1.2" startGroup="START_2" goalGroup="GOAL_2" />
      <Spawn unit="Runner" time="24" number="1" rate="1" startGroup="START_2" goalGroup="GOAL_2" />
    </WaveSet>
  </Waves>
</Level>

Note that this is only a simplified version. The actual level XML contains a lot more tags. I just left what’s relevant for this article.

A spawn session describes how a series of a number of a certain enemy units are spawned into the level. Think of it as a specification of a magical portal where enemies come in. It has the following properties:

  • unit – What enemy unit to spawn
  • time – The time to start spawning the enemies from the starting time of the wave
  • number – Number of units to spawn
  • rate – Spawn rate of the units. It’s in spawn/second. It determines how fast the enemies are spawned. Higher number means faster spawn.
  • startGroup – The area where the spawned units start. It is named as ‘group’ here because it is a tile group.
  • goalGroup – The area where the spawned units are headed.

This is how a single level in Warrior Defense is described, at least the meat of it. We now head to the actual level designing. One important question that need to be answered was “How do we make waves that are ensured to have increasing difficulty?” Digging deeper, putting it in another way is “How do we quantitatively measure how difficult a wave is?” If we have the answer to this question, then it’s just a matter of increasing this value.

How do we quantitatively measure how difficult a wave is?

What I did is I assigned a hypothetical value measuring how tough a single enemy unit is. It’s the same as setting a difficulty level for each unit. The following are XML element description of three enemy units in the game:

<Unit name="Critter" type="Crawler" value="1" size="Small">
    ...
</Unit>

<Unit name="Runner" type="Crawler" value="2" size="Small">
    ...
</Unit>
    
<Unit name="Roach" type="Crawler" value="3" size="Small">
    ...
</Unit>

The value attribute represents the difficulty value of the unit. The higher the value, the more difficult it is.

With this, calculating for a wave’s difficulty is just a matter of addition and multiplication. For example, for this wave set:

<WaveSet notification="">
    <Spawn unit="Critter" time="0" number="22" rate="1.1" startGroup="START_1" goalGroup="GOAL_1" />
    <Spawn unit="Runner" time="10" number="15" rate="1.1" startGroup="START_2" goalGroup="GOAL_2" />
</WaveSet>

The difficulty value of this wave set can be calculated as:

difficultyValue = Sum of all spawn session difficulty
difficultyValue = (numberOfCritter * difficultyValueOfCritter) + (numberOfRunner * difficultyValueOfRunner)
difficultyValue = (22 * 1) + (15 * 2)
difficultyValue = 52

It’s a rather simple quantitative measure and probably not representative enough of the actual difficulty, but it works enough for my purposes for level designing. Choosing how to increase the difficulty value is easy. I could use linear, logarithmic, quadratic increase, etc… anything to my liking.

Combinations of enemies

The next hurdle I encountered is where I used some programming. “How do I make combinations of enemies that total to a certain difficulty value?” For example, I want to make a wave set that has a DV of 100. What combination of units and how many of them should I include to make this wave set? What if I don’t want Critters to be in this wave? I want Tanks and Runners in this wave. How many of them should I use?

I turned to computer science. This particular problem can be best solved by a simple genetic algorithm. The idea is to generate random spawn session combinations and breed them to find better ones until the one with the exact difficulty value emerges. The code is also not that hard to make as I imagined it. So I decided to put a little time to make this little tool I call Wave Set Generator.

Forgive the UI. It's long.
Forgive the UI. It’s vertically long.

Continuation from previous image
Continuation from previous image

This tool generates a set of spawn sessions that matches a number of criteria:

  • Spawn Data Count – Number of spawn sessions
  • Target Unique Count – The number of unique units. Spawn sessions may or may not have the same enemy types.
  • Target Total Value – The difficulty value of the whole set in a certain range
  • Target Unit Count – Overall number of units in a certain range
  • Exception Set – Units that should not be included in the set. In later waves, easier enemy types might no longer be necessary. Or I would want waves with no flying units.
  • Required Set – Units that should be included in the set. In some waves, I may want only flying units, or only heavy units.

When the Start button is clicked, the tool generates random combinations at first then interbreeds them until the combination that meets all criteria has been generated. The tool stops as soon as one combination is found. There are more than one possible combination. If I don’t like the generated one, I can just press Start again to look for another combination. How cool is that? This is the most time saving tool I’ve ever made. After a good combination is generated, I’ll just have to put them to the level xml.

Just imagine what I was doing without a tool for this. I choose some units, then I would assigned an arbitrary number to one unit and calculate for the rest. If I didn’t like the resulting combination, I’d have to recompute for other units, or worse, start all over again. In short, it takes a lot of time just to compose waves.

The genetic algorithm I used goes like this:

  1. Represent the spawn session set as a list of bytes (also known as ‘chromosome’).
  2. Provide a fitness calculator that checks if a chromosome meets all the criteria. If not, it assigns a fitness score to a single chromosome.
  3. Generate a fixed number of random chromosomes. Say this is N.
  4. Using the fitness calculator, check each chromosome if it is already the fittest candidate. If one is found, stop the process. Else, assign the fitness score to each chromosome.
  5. Generate a new generation of N chromosomes by mating the current ones. Ensure that the fitter chromosome have more chances of mating.
  6. Repeat step 4 until the fittest chromosome is found.

Implementation details is already out of scope for this post. I’ll write about that in another one. The concept of the algorithm is it looks for the best solution by culling the unfit solutions to generate better solutions in every generation. It’s kind of like how evolution works. I say it’s a glorified brute force because there’s not even an actual solution. It looks for it blindly.