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.

Moving onto a new mobile game project and a new set of goals

My first mobile game on the iOS apple store, Play the Field, was a great learning experience in many ways, but to be honest the number of downloads was quite below my expectations, especially considering it was free. I knew the mobile game market was dog-eat-dog, but nevertheless I think I was still a bit too naive.

I still feel the game is a lot of fun, and at least one person who tested the game for me (who had experience with RTS games) said he felt it was enjoyable to play. But it’s pretty clear to me neither the gameplay nor the difficulty was the main factor in the small number of downloads. I’m pretty sure the game’s simple, unrefined visuals, was the real culprit. Although I tried to market those as “retro” or “minimalistic”, the actual number of games with visuals that simple that become popular seems pretty small. The game’s unfamiliar genre (“casual” RTS) may also have been a factor in the lack of popularity.

While I have recently done some experimental advertising for PTF, and may continue to do so in the future, I have decided on spending the biggest chunk of my time on a new mobile game. It’s something along the lines of a puzzle game influenced by classic games.

This time around I have a different set of priorities, the most important being to spend a greater amount of effort and time on polishing the visual and UI aspects of the game. In all my game projects up until now I’ve always went the path of least resistance (meaning I spent the most time of my time on other elements such as gameplay, AI, level design, difficulty, etc.), but this time I will shift that balance.

Since my lack of artistic ability isn’t likely to change anytime soon, I’m making the best of what I have – still trying to keep to simple visuals while adding things here and there to please the eye. In particular I’m trying to add more animations to the game, for the background as well as at the start of each level. In between each player’s turn there is also a special animation I’ve spent some time refining.

Besides this emphasis on visuals, I’m hoping my decision to make a more standard puzzle game will give it better chances at popularity, while acknowledging that genre is extremely competitive.

The final thing I’m planning on putting more effort into is making an enticing preview video, since I feel that’s one of the most important things determining whether a user makes the jump to actually download an app or not. Of course the screen shots are also important, and since animations won’t show up in these I’ll have to pick what to showcase wisely.

I’m aiming at the somewhat arbitrary figure of 2x over my previous game’s downloads, though part of me is hoping I can get at least 10x. Even 100x wouldn’t result in a famous game, but if I can see concrete progress in some form it will motivate me more to keep along this route. Otherwise, I may chose to devote my time elsewhere.

Programming is great fun, but there’s nothing quite like the thrill of real users around the world downloading your mobile game, with a great degree of unpredictability around what will be popular and what won’t.

Prototypes: an integral part of software development

This time I’d like to talk about the process of creating prototypes. Though this blog is about mobile gaming, prototypes can be a valuable tool for almost any time of software development.

What is a prototype?

A prototype is an limited version of a program which is intended to test something, such as a new game idea. It’s definition is fairly open-ended, but it contrasts from a production version which is something designed to be used by customers, as a complete game or application.

When do I need a prototype?

Creating a prototype is typically warranted when there is some uncertainty the project which needs to be worked out, essentially de-risked, before taking on the full production project. Prototypes are usually appropriate when the full version will take quite a long time, possibly months or longer with a team of several developers and other staff.

The idea is that you want to avoid expending too many resources (money, time, etc.) until you have some level of confidence the project will succeed. Success is defined differently for each project, but it can involve making a certain amount of money, or just making a game that is fun to play.

The idea of prototypes also assumes the developer(s) have the capacity to work on more than project over time. If you compare working on a single project for a year, with a 50% chance at failure, as opposed to developing 10 prototypes during that time to find which idea(s) have the most potential, the latter could be considered a more efficient use of time.

How do I make a prototype?

The most important thing about prototypes is deciding exactly where is the risky part of your project, or the element(s) you want to validate. As an example, let’s say I have this great idea for a game that is a cross of checkers and a word game, and it seems really fun to imagine how it would work. In this case, the purpose of the prototype would be to see how enjoyable such a game would actually be, and to work out some of the gameplay elements.

You can work iteratively, trying one idea until you determine it doesn’t quite work, at which point you can add or change an element and do some more play testing. For example, in our checkers-word game example, you can play around with different scoring systems to see which is fair and offers the most challenge.

Tips for making a fast prototype 

The prototype creation process helps guide you what order you do your activities in. If you are testing the gameplay of the checkers-word game, there is no need to spend any time on the main menu system, the credits page, or the sound effects. You should be spending most of your time in the risky or uncertain element you are trying to test.

With games, graphics assets are one area which can take a long time to produce, whether you are doing it yourself or with the assistance of graphic artist(s). For many prototypes, you can skimp on graphics and keep things very minimal and simple. Rather than a photo-realistic game tile, you can stick with a simple single-colored square, and so on. Of course, if your idea involves creating a game with a certain atmosphere (like a horror game), the graphics and sound might be more important than the gameplay, in which case your prototype would require more effort on those assets.

One nice thing about prototypes is that you have much more freedom. For example, you can potentially leverage a test license for a game engine which you couldn’t otherwise use for a commercial project without paying big bucks. You can do the same for other assets which are legal for non-commercial purposes, though if you switch to a more serious commercial project, you’ll have to purchase the proper licenses for everything being utilized.

Prototype coding practices

When developing a prototype, you also have some more freedom regarding how you write your code. You can probably get by with spending significantly less time on things like commenting, proper modular design, and efficient algorithms. However try and avoid taking things too far, since adopting horrible practices like stuffing all code into a single giant function would make modifications of the prototype difficult.

Also, some things which you typically try to avoid in production code, such as global variables and cryptically named variables, would probably be OK in a prototype. Proper memory deallocation can also be put off, since you can always restart the app as often as you like during test.

Levels of grey in prototyping

Prototyping isn’t all or nothing, in the sense that you don’t have to throw all your code away after a prototype. You have the option of reusing parts of your code in the production version, probably after some refinement, or even in another project.

After writing many prototypes, I’ve gotten into the habit or always writing “TODOs” in my code so that if I do get to make a production version, I know what I need to fix. I also always think about whether it’s worth the few minutes to write a block of code properly, or decide to leave it in a quick, “hacky” state. Spending the few extra minutes to write proper code also makes you a better developer in the long run.

Prototypes need planning too

If your coding is just as a hobby in your free time you can do whatever you like, but if there is a chance you will try to go commercial or enlist the help of other people, it’s good to have a plan even for your prototyping.

First, decide roughly on how you are going to measure the success of the prototype. Will you just play it yourself for a few hours and see if it feels fun enough? Or will you show it around to your friends to get their feedback? You could even target an app store (mobile or desktop) as an end goal to your prototype. You probably won’t get too many downloads because of the lack of polish, but the process of getting on a store is always a learning experience.

Second, get a general idea of how long you think the prototype should take. Generally, I would say a few days to a few weeks is a good range. If your prototype is taking more than a few months then I wouldn’t really consider it a prototype anymore.

For new developers

For those new to software development or game design, your first few projects will probably all be prototypes, whether you think of them that way or not. In that sense, the goal of your effort doesn’t have to be to make a great app or game, but instead just learn something.

As your coding skills improve, you’ll be able to write a rough prototype in a shorter span of time. Saving code you’ve written in the past and reusing it when possible is a great time saver.

A real life example

Recently I had an idea for a casual mobile game which I felt had great potential, so I tried to make a quick prototype to vet the idea. By surgically ripping out parts of a previous project, I managed to make a working prototype in only two hours, and then added a computer AI player in another two.

The idea turned out to be a little less interesting than I imagined, so I’m glad I didn’t try writing everything from scratch. But at the same time, I feel with a few tweaks the gameplay might be taken to a new level, so I’m going to try a few more things when I get a chance.

All prototyping is essentially an experiment, so have fun!