Programming Trick: Speeding up your recursive loops with a creative technique

Lately, I’ve been working on a new game project which is very different than all the other ones I’ve done so far. I’m planning on waiting until it gets a little further before I write about it in detail on this blog, but I ran into an interesting technical challenge and I’d like to discuss how I solved it.

To implement the game mechanics I need a graph of nodes, with various connections between each node. I have a need to find the shortest path between two nodes, where the path is calculated by the sum of the length of all connections as part of the path.

I started out with a simple recursive algorithm that started from each node and worked backwards to find all possible paths to get to it, and used a map to store the best connection to move, given a certain intermediate node and a certain destination node. This worked really well, although after around 13-14 iterations on a graph with many connections it started taking over a second to compute and them getting exponentially worse.

One option was for me to search for a more proper algorithm to find the shortest path, and I am sure this has been perfected by  programmers over the last few decades. But I had a secondary requirement to also store all non-optional paths as well, so some of those algorithms probably wouldn’t suffice.

Looking at my recursive function, I realized that there really wasn’t much going on in terms of sub-functions it called that do any significant calculation. If there was, I could try to optimize those or cache up some result. But the question remained – what was taking up all the time?

Looking at the function again I saw that I was passing four different arguments into it. If you have ever studied assembly, you probably know that there are several instructions just to push and pull each of these to and from the stack, and since the function is called so frequently I thought that maybe this added up to a big chunk of the total time.

I decided to test my hunch by making all the parameters into global variables. I purposefully didn’t use class variables since I knew there would be extra lookups required, translating to extra work for the CPU.

It was a bit of work to make this transformation, since for non-pointer variables I had to manually save the state before calling the recursive function, and then re-set it. But this was only for two of the variables since the other two were pointers anyway which were supposed to change (one was the map which stored the nodes that had already been traversed so far, and I already had code to adjust that when returning from the recursive function).

The resultant code was a bit harder to follow, but the performance was significantly better. For the test case I was using I was able to get several more iterations before it got significantly slow (>1 second), if I remember correctly to at least 19-20 iterations.

If I keep adding nodes and connections eventually it still gets slow again, but I will probably put limits on these anyway so I may be safe with this solution for the time being.

Although I enjoy designing games from a high level, after many years of coding I still enjoy these types of algorithmic challenges, and the satisfaction of a well-tuned function.

Advertisements

Mobile Game Development: learn your weaknesses and strive for consistent quality in all areas

Having taking a few iOS projects from conception to release on the Apple Apple Store, I’m starting to discover patterns in how I go through the development process. I plan to use this information to tune how I handle future projects, resulting in efficiency improvements as well as a higher quality result, hopefully leading to a larger user count.

I recently became more aware of the stages I go through in a typical project. I start development in what I would call a “creative” stage, where I am thinking of new ideas and enjoying the implementation process, as well as the iterative design that goes along with that. At some point when the project far along enough, I start to feel the need to just release something – what I’ll call the “get it done” stage.  I think this stems from my fear that other things will come up in my life and not have time to finish the project, or that I’ll just get bored of it and quit partway through, similar to why I would be hesitant to start reading a long novel.

The “get it done” stage is dangerous because the remaining tasks are done quickly, with lower quality than things done in the “creative” stage. For example, I usually create my app’s icons near the end of the project, and rush to just get something that looks reasonable enough. This is a bad idea since an icon is an extremely important part of the overall marketing presence of an app, and some people have even claimed changing only a game’s icon resulted in a major change in the download rate. Another example of this is creating a tutorial, as well as general visual polish.

For my next project, I’m going to try to get myself to think more long-term, and not jump into the “get it done” stage until the product is nearly ready to be released with high all-around high quality. It may be appropriate to rush to the finish line if there is a hard release date you are aiming for, for example to coincide with the release with a new OS version. But in cases where no such deadline exists, there isn’t much value in pushing things.

I am not sure if it is an appropriate comparison, but this reminds me of when I used to train in running to shave time off my mile. I measured how long it took for each 1/10th of a mile, and I found I got the best result when I had a good balance between these times. As opposed to having one or two areas where I sprinted and exhausted all my energy, a consistent good speed gave the best result. I feel that app development is similar, in that a consistent push through all areas is the best way to get a well-rounded product.

If I feel like I am too busy to make proper progress on a hobby project, rather than rushing it to release I’m going to try to just take a break. Odds are that I can just continue where I left off, whether it is a week or a month later.

The exception to this discussion is if you are working on your first mobile app or game. In that case I think it’s OK to just get something on the store, since you’ll gain valuable knowledge going through the entire process for the first time. For your second project, you can slow down and properly plan things out using your newfound knowledge. If you are worried about a low-quality app giving you a bad reputation, you can always pull it off the store at any time.

Hobby Game Developers: to use version control or not?

Version control, sometimes called source control, is the process of using a program to manage multiple versions of a software project, typically saving things in a remote database or similar structure. There are many version control packages available, including CVS, ClearCase, Perforce, and Git, the last of which has risen to great popularity in the last few years.

There are several advantages to using a version control package, with some of the major ones being:

  • All changes are backed up, so if data is lost or accidentally erased on your machine you can recover it.
  • By looking at the various revisions in the system, you can follow the flow of changes. This can really help out in triaging bugs for complex projects.
  • You can work on several different versions in parallel and do an automated merge at some point to join the code from two or more versions. This comes in handy if you have a stable version that you are submitting to the app store, and a an experimental one with unfinished changes. In team projects where a single source file or module can be worked on by several people at once, this is even more important.

For any project that has more than two or three people, I’d say that source control is a necessity that can save hours if not days or work, especially for complex projects. Most of the projects I worked on in my day job used some form of version control.

However, for a hobby developer that is working on a game by him or herself, the advantages are much less. I’ve tried to use Git for one of my hobby projects, but ended up never needing it. This may be because of some habits I have developed over time. For instance, when I am going to make a major change to a function I often will copy that function, and keep the original one. This makes it easy to go back to the original if I end up breaking something, or decide the refactor I was attempting is not worth it after all. Also, I typically make sure my code is buildable every few minutes, as opposed to writing hundreds of lines of code for hours, and then trying to build. If you get a compile-time failure in that scenario, it can take quite a while to figure out where things are broken, and source control can potentially help there.

Instead what I do is simply zip my entire project directory and email myself once a day, so I have both a basic backup and ability to check previous versions. But I’ve almost never needed that, I do it primarily for peace of mind just in case my machine’s HD crashes – something that has happened more than once.

If you are on a Mac, you can use the Time Machine feature which will allow you to look at older versions to see what changed. However, unless you buy something like an AirPort Time Capsule or similar external storage solution, you are not protected against data lost. I just bought one of the capsules the other day, and it was pretty easy to setup.

If you are doing hobby game development by yourself, you’ll have to weight the pros and cons and decide what is best for you. If you don’t have experience with a software version control system, it’s probably a good idea especially if you consider making software development your career. I’d recommend Git since it’s popular, free, and you can set it up initially using just one machine (and expand to a remote machine later if needed).

Even if you are working on a hobby game with a handful of people, depending on how well segmented the work is you may not need a source control. For example, if one person is working on art, one on coding (implementation), and one on testing and story, then you may be able to craft a workflow which doesn’t require source control.

One more advantage of using source control even if you are working alone, you always have the option of easily sharing your code with people around the world, especially if you are using an internet-based system such as GitHub. This makes it easy to grow your team if things go well.

Are you hobby game developers out there using source control?

Hobby game developer vs career game developer

At the present time, I am doing game development purely as a hobby, meaning I work on it in my spare time and don’t earn any profit from it. And yet, some time in the future (could be several years from now, or longer), I think about what it would be like to be a career game developer, meaning that I make my living developing games.

While the fact of whether one gets his or her primary income from game development is black or white, I feel that it is possible to have a grey area where your are designing as a hobbist, but thinking like a career dev. To that end, I’ll try and illustrate the differences between these two mindsets in a little more detail.

Hobby game developer

Because there is little to no income involved, a hobby game developer has total freedom over what and how it is developed. This means that you can jump from project to project at any time. What tends to happen, at least in my own experience, is that most games that are produced are something similar to one played before and enjoyed.

For example, since I enjoy Starcraft I’ve made several games which bear at least a minor resemblance to it, and I’ve seen many other hobbists that have done the same.

Put another way, “I enjoy this type of game” plus “I enjoy programming” translates to “I enjoy programming this type of game”. Even if the game pales in comparison to the original, some of the happy memories from that will be revisited when playing the “homemade” version. This can be seen to be a bit like cover songs, since listening to them reminds one of the original version. If others feel the same nostalgia about the game, it can contribute to it’s success in the market.

A hobbyist developer doesn’t really have any deadlines or obligations, so generally there is less motivation to finish a project. As a result, many projects end  in a half-complete state when other more interesting things come up.

Depending on the person’s interests, he or she may learn new technologies just because they seem powerful or interesting, or for the purpose of buffing up their resume. There may be no connection to the quality of the resultant game produced using said technologies.

Career game developer

Because the career game developer makes a living from their job, possibly supporting a spouse and children, he or she generally has a much more serious attitude to things.

The attitude of the developer can change significantly depending whether the developer is self-employed or not. The focus of this article is mostly on the self-employed case, but I’ll talk about the company-employed one as well.

Company-employed (not self-employed)

A developer in this position typically has to follow the organizational structure and rules of the company who they are employed by.

For lower level positions, the employee’s main focus is just following orders from their direct boss. Quality may or may not be stressed, depending on the environment. Getting along with one’s boss, both socially and politically, can be important factors to promotions and other perks.

A key element here is that the developer’s salary, bonuses, and other benefits may not be tied to the game’s success in the market, apart from the fact that a failing game makes them a target for restructuring.

For higher level positions, there is typically more freedom as well as more responsibility to create a quality end product. The higher up, the more likely to profit from a successful game.

Self-employed

This category includes those developing and selling games by themselves, or part of a small team. The compensation of the developer in question is very strongly related to the game’s sales, so there is a very high level of importance put on making a “successful” game.

The key here is that as long as the game sells, the fact of whether it is “fun” to play by the developer(s) creating it isn’t relevant. In fact, you could end up working on a game that you would never play yourself, because market research has shown that it is likely to profit. Of course, it is ideal for developers to align the game they are producing with their own interests, but that isn’t always possible.

For the self-employed developer, abandoning a project midway through is a major sacrifice, because there was no direct profit achieved from those “wasted” hours. However, if there was some new market research indicating this game will no longer sell, it may make sense to cut losses. This is one reason the longer a game takes, the more risk there is to cancel it or redesign major parts of it. The upside is that the skills learnt, including knowledge of frameworks, programming languages, and OSes, may be a consolation since they can be leveraged for future projects.

Because of these things, there is more times that a career game developer has to put up with some tedious or unpleasant task – whether that is writing tricky code or trying to fix a tough bug. Even though it would be OK for the hobbyist to just give up at times like these, this is not acceptable for a career dev.

In exchange for these (hopefully) short-term struggles and compromises, the career developer has the chance of both increased rewards, as well as the satisfaction that their game did well in the market. Whether you coded a certain routine right or made a nice graphical asset is less important than the overall sales of the game.

===

Even if it’s only gradual baby steps, I’m going to try to gradually make this shift of mindset in the hopes of making the jump someday.

Let me know your thoughts on this stuff, especially if you are  acareer developer. Is there anything important I forgot?

Game development as an act of creation, and learning to step outside oneself

Despite the fact that game development can involve many roles (story designer, art designer, gameplay designer, etc.) which can be filed by many people, ultimately the game produced is a creative work influenced from the individuality of each of the people involved. This means things like biases, world views, and what makes a fun or interesting game to each person all factor into the end result.

I believe we all have blind spots when thinking creatively, whether that is game design, a visual art, novel writing, or even musical composition. For example, something which we feel is obvious or logical may not be the same to another person, or even to most people. That’s why in all these creative arts, it’s good to have someone to bounce ideas off of and get feedback: “Does this make sense?”, “How does this sound?”, or “How does this look?”.

Herein lies a problem, because all these things are inherently subjective. We could ask 100 people to review a creative work, and they might all give different opinions and suggestions. This is why it’s best to be very picky about our reviewers, and in the domain of game development this means being picky about who tests our games, and what weight we give their opinion. We also can use basic statistics, like putting more weight to any feedback that was given by a certain percentage of people. If 80% of people say the UI is hard to use, then it would be pretty unwise to ignore that feedback.

As with all things, budget comes into play here since if we are not willing to spend money, our best bet is to be lucky and make friends with someone very experienced in playing and/or designing games, who also possesses the communication skills to clearly communicate what works and what doesn’t. Another option is to just get as many people as we can to help out, gather their feedback, and then worry about how to value it later. If your budget for your indie game is 0$, then you’re options are pretty limited here.

Fortunately, there is one more thing we can do to help – become our own best beta testers. That is the art of stepping out of our everyday thoughts and trying to act like a third party. This can involve playing devil’s advocate (“is this feature really easy to understand?”), or trying to think in detail about what the “average” person would think (“so-and-so game is popular, so many people would quickly grasp this element”).

In the field of music, we can get a good idea of what a third party would hear by recording ourself and listening to that with all our attention, since during the actual performance we are worrying about so many other things it’s hard to really listen to what sound we are putting out and the overall feelings it invokes. For novel writing, you can try to read through a chapter you wrote after waiting a few weeks, since then you’ll be closer to what a new person would experience. At least I found this to be a good practice.

For game development, I think getting into a neutral state where we turn off our biases is very difficult, but actively trying to get into that mode can help us train little by little.

[Image credit: http://www.gratisography.com ]

Game development and the art of wearing many hats

I’ve been thinking about making a new mobile game and have started work on prototyping and basic implementation. I plan to post on that more in upcoming weeks but today I wanted to write some more about game development in general, especially when done as a hobby by yourself or on a small team.

If we look at software development as the practice of writing code to fit a set of detailed requirements, the set of tasks involved is relatively well defined. Define the high level implementation, including modules and how they interact, then gradually drill deeper down until you get to the function level and are writing small chunks of well-defined logic. This is no means an easy job, typically requiring knowledge of one or more technologies or languages (iOS, objective-C, etc.) and possibly third-party frameworks (i.e. Unity). Implementation itself can take a handful of people to hundreds of people anywhere from a few hours to several years, but the point I’d like to make is that you can generally see the road ahead and make gradual progress [Exception: projects that stretch the limits of technology]. Worst case, you reach a testing phase and find out your design doesn’t support an important requirement, at which point you may need to re-design the modules or some algorithm.

Now lets take a step back and look at the scenario where there is no requirements document, or any clear set of things you want to accomplish. As a hobby game developer, you might just “want to make a cool game”, “want to make a RPG like Final Fantasy”, or maybe “just make a game that becomes popular”. Note that I purposefully omitted “want to make money” since that is one of the most difficult goals for a small team.

Here what you are supposed to implement is vague, or at worst totally undefined. If you are the perfectionist type you can take the ivory-tower approach, and write pages and pages of a specification document about what you game is going to be like: the world, game mechanics, interface, etc.

But as a hobby game developer, you have limited time and being an idealist just isn’t going to cut it. The only way you are going to get anything done is by bouncing back and forth between implementation and inspiration (design) modes. This can involve building a set of prototypes, or fine tuning a more fleshed-out implementation, but you can’t avoid jumping back and forth between these two modes. This is because that whether something is fun or easy to use is very subjective and requires someone actually playing the game.

Without design there is nothing to implement, but without implementation you don’t know if what you’ve designed is actually an enjoyable game. In some cases, you may not even know if it’s possible to code in terms of technology and development time. For example, if your game involves natural-language input (like classic adventure games), you need to either develop this technology yourself or find a third-party library. If during prototyping you discover you can’t properly parse the types of language you want the user to be able to input, you might have to go back to the drawing board and re-think the game’s interface.

If you are working by yourself, you’ll have to put on even more hats during this process: visual artist, sound designer, scriptwriter, gameplay balance engineer, QA tester, etc. There is research indicating that, for the average person, multitasking like this takes a toll on productivity, so you have to fine the right granularity of work to minimize this overhead.

Personally, after many years of doing software development as a career I’ve improved my ability to implement quickly and efficiently, and much of this carries over to my hobby game development activities. But I have a great deal to learn as far as design goes, especially the tricky act of juggling the many roles of a game developer.

I’d argue that the art of smart, efficient multitasking – knowing where and how much to spend your time at any phase in the project – is one of the most important skills to learn as a hobby game developer, and one of the hardest to learn. Another one is scoping (maybe a good topic for a future post), which means determining how much stuff you want to fit in a project for a given timeline.

Note: this post was inspired by this post I just read.

Difficulty in gaming

Difficulty of a game, how hard or easy it is and in what way, is an extremely important factor in game development. This is something good to keep in the back of your mind in nearly all stages of game development, including brainstorming, prototyping, implementation, and testing.

It’s easy to think about difficulty in simple terms (e.g. “This game is easy”, or “This game is hard”), but it’s actually much more involved than that. In this article I’ll discuss some of my ideas about difficulty in games.

Types of difficulty

Rather than a purely linear continuum, there are different types of difficulty that are good to be aware of, especially when deciding on your target audience. It’s pretty rare to find a game that just involves one of these – usually you get a mix of two or more.

A common type of difficulty in many games is calculational. These types of games challenge you to think ahead several steps and predict the outcome of a combination of events. A classic example of this is chess, and the ability to calculate ahead a few moves (along with a few other factors) is one of the keys to being a strong player. A related type of challenge is tactical, where players have to think about the relative positions of friendly and enemy units (ships, planes, tanks, whatever), and predict what the outcome of a battle will be.

Reaction time is another type of difficulty which can be seen in many popular mobile games like Mr. Jump or Alto’s Adventure, the latter of which is currently the #1 paid app on iTunes. In these types of games, besides being able to respond quickly to changes in your environment, you also have to estimate things like distances and paths you will take.

Memory difficulty is one that is less common in mobile games, though having a good memory may make it easier to remember common patterns to solve puzzle games. A good example is the class board game “Memory”. A language learning game that tests your knowledge of words using a flashcard-style interface is another example.

Another one is endurance difficulty, which means that you have to survive a long time in order to pass a certain point or level in the game. An example of that is many RPG games where bosses can take 30 minutes or longer to beat. The placement of save points (or some other mechanism to save state) is an important factor here. One of my pet peeves is games where you die after one mistake, putting you back minutes or even longer.

One final one to mention is system difficulty, which can also be called learning curve. By this, I mean the time required to learn the basic rules of the game before you can actually make any progress. A game with good tutorials reduces this type of complexity, otherwise it can take the user much experimentation to figure out what to do. I’ve played a few mobile games that seemed really great at first, but I lost patience and gave up before I got the hang of the system.

There are many others, such as deduction, but I think I covered the most common ones here.

Satisfaction and actual vs perceived difficulty

For a straightforward game like chess, the difficulty is obvious and there is no effort to convince the player otherwise. For other games, like the famous mobile game Candy Crush, there are a lot of distractions to take your mind off the basic gameplay elements. Candy crush has sound effects, exploding animations, and messages that pop up now and then to complement you (for example, “Sweet!”). As a result, you could tap somewhat randomly and feel like you are doing an awesome job. (Confession: I have not played this game for more than a few seconds, so I can’t claim to be an expert on it’s gameplay)

Ultimately, what’s more important than the objective level of challenge is the satisfaction gained by the player when he or she makes progress. If the game can fool you to thinking that you did an awesome job at the “difficult” task of randomly tapping, then great.

Difficulty ramp-up

How difficulty increases in your game is another important factor. Is there a bunch of levels with similar difficulty until you get to transition point when things become suddenly harder? Or do things gradually get harder as you progress? The user will quickly create their own expectations after playing your game for a few minutes, and if you betray those frequently that are liable to give up.

Another important factor is how/if you notify the user about the difficulty for each level or area. Is there a big sticker that says “HARD” on certain levels, or a color scheme? Is hinted at from the name of the level?

When you do increase the challenge level midway through a game, consider giving them several options. For example there could be three stages, from which they only have to beat one to move on. Forcing users to beat a certain stage which is extremely hard, with no other options, is one way to quickly alienate your users.

All or nothing vs optional goals

Rather than requiring perfect performance to complete a level, a common technique is to allow getting through the level somewhat easy while including optional goals that give extra points. For example, some mobile games will show you one, two, or three stars, indicating how well your performance was on a certain level. You can usually replay any level to try and get a better score, and replay value is always a great thing for games. This is another way to reduce the chances of users getting frustrated and giving up on your game.

Interpretation of difficulty

Ultimately, difficulty is a very subjective thing and varies between users. One game I might think is a piece of cake you might think is a nightmare, and vice-versa for a different game. Users may be less inclined to worry about the difficulty if the game has nice visuals and enough feedback (like the Candy Crush example above).

For seasoned gamers, each genre has it’s own expectations dictating what is reasonable. For example, many console RPGs from the 80s were known to have hours without a save point, and those who beat them got bragging rights. Users will be comparing your game to others in the same genre and if you deviate too much it may catch them off guard. For example, a puzzle game where the first few puzzles each take roughly 3-4 hours would be pretty unorthodox and scare away many players.

Because of the subjective nature of challenge, doing proper beta testing with users from your target demographic is extremely important to a successful game. Ideally, you would watch while they play, observing where they got stuck and where they blew through effortlessly. Ask each of them how they felt about the difficulty – was there any surprises and was it satisfying enough?

Using only main developers for gameplay testing is dangerous because they have a very biased view of game, with prior knowledge the basic rules and tricks. Until you show someone outside the team you’ll never really know how difficult and intuitive the game is, and the more people that playtest the better.

In fact, one can get a good feel for the difficulty of a game before the visual polish is complete, so consider making quick prototypes of the basic gameplay and having your testers try those at an early stage in the game’s development.

(Image credit: http://www.gratisography.com)