selene tan

Author Archive

Optimization – Choosing the right algorithm

by on Feb.12, 2013, under Blog

I was working on performance optimizations for a turn-based tactical RPG. There was a noticeable hang when showing the movement highlights after clearing a level, when characters could move freely over the whole map. After fixing the graphics bottleneck in movement highlighting, performance was greatly improved, but there were still occasional hiccups. I also received reports that sometimes ranged unit AIs would cause the game to hang for a while, sometimes long enough to trigger the Flash “unresponsive script” warning. Digging into the AI issue, I realized that both issues were caused by the pathfinding–or rather, how the pathfinding code was used.

A* is the gold standard algorithm for finding a path from one point to another point. We were using the A* library, which is a nice solid implementation. The AI and highlighting shared a subsystem we called the Searcher. The Searcher let you specify criteria for tiles and would then find all tiles which matched those criteria. Many of the criteria were simple, like “Within X range of tile Y,” or “Contains an enemy.” One of the more complex criteria was “Can be reached from tile X within Y steps.” These were the criteria used by the move highlighting. The criteria were applied like filters, in this order:

  1. Within range X of unit’s current tile
  2. Can be walked on (not a rock or other barrier)
  3. Can be occupied (allied units can pass through each other while moving, but can’t end their move on a tile occupied by another unit)
  4. Can be pathed to within X steps from unit’s current tile

#4 used A* to find a path, then confirmed if the path length was short enough. When checking for a path from one tile to another, this makes perfect sense. The problem came from using it in aggregate.

This animation shows what happened when using the Searcher with the above criteria:

Get Adobe Flash player

Orange highlights show path progress, beige highlights show candidate tiles, and green outlines show known-pathable tiles. Filter #1 limits the grid to all tiles within 5 steps of the center. Filters #2 and #3 find that all tiles in range can be walked on and occupied, which is the worst case for this algorithm. Finally, Filter #4, the pathfinding test, is applied to every tile from left to right, top to bottom. Since the filter was written in a way that considers just one tile at a time, when it looks at a new tile it forgets the intermediate paths it found for previous tiles.

So the problem is that the code is doing a lot of extra work when we want to check pathability all tiles within a range. If we were only checking a few tiles, testing for paths one tile at a time would make sense. With the average movement range of 5, we’re checking 120 tiles, and that goes up drastically at the end of a level when the movement range restrictions are lifted. We need to revise the code so that it checks pathability for all tiles at once.

A* has a close cousin called Dijkstra’s algorithm. Where A* is designed to find the single shortest path from X to Y, Dijkstra’s is designed to find all the shortest paths from X to everything else. That’s exactly what we want! Even better, you can quickly turn an A* implementation into Dijkstra’s by making the heuristic always return 0. I also changed the loop end condition so that instead of finishing when it reached the “goal” tile, it finished when it ran out of tiles to consider. I then had the algorithm cache all the intermediate paths it found in a two-dimensional array for easy lookup and return that cache with the results. Finally, I rewrote the Searcher’s pathability filter so it would check for the path cache, and either generate it or use it.

This animation shows the result of the changes:

Get Adobe Flash player

The cache of known paths starts from the center and grows outwards in a rough circle, taking a fraction of the time needed by the old implementation. As a bonus, the caching sped up the AI when considering multiple goal types from the same starting location. It went from sometimes triggering the 15-second “unresponsive script” notice to a barely noticeable pause. A quick profiling check confirmed that the game was taking a tenth of the old time to calculate possible paths.

This kind of situation is why it’s so important to understand algorithms. It’s easy to look up pathfinding techniques online and conclude “A* is the best,” without considering the context and usage. It also highlights the benefit of caching. Modifying the A* to cache all partial and complete paths, and look them up during its search, would get many of the performance improvements I saw. The benefit to using Dijkstra is that we don’t waste time checking paths to areas that have been blocked off, saving CPU cycles.

Leave a Comment full post

Simple Optimization – Finding Graphics Bottlenecks

by on Jan.28, 2013, under Blog

This post is about a time when I was able to use a profiler to very quickly find and fix the cause of a noticeable frame hiccup.

I was working on an isometric Flash game with turn-based battles on a grid. When you mouse over or select a movement or ability, the game highlights valid target tiles. After each battle, units can move freely about the battle map before continuing, without the per-turn movement limits. On larger maps, especially with ranged units or at the end of battle, there was a noticeable pause before the highlights appeared.

Since the symptoms were straightforward and easy to trigger, I broke out the Flash Builder profiler to see what exactly was going on. I loaded up a large map and defeated the enemies. I started capturing profiling data, then switched the active character–which recalculates the movement highlights–and stopped the capture after the highlights appeared.

Sorted by cumulative time, these were the first few results:

Method Calls Cumulative Time (ms)
[enterFrameEvent] 1 9855 (23.44%)
Grid.highlightForAbility() 10 6668 (15.86%)
Animation.update() 1960 5051 (12.01%)
PSprite.update() 1764 5048 (12%)
[render] 1 4846 (11.52%)
Tile.highlight() 770 4829 (11.48%)

[enterFrameEvent] and [render] are internal Flash constructs, as indicated by the bracketed names. [enterFrameEvent] is the root for all listeners attached to Event.ENTER_FRAME . [render] is what it sounds like, and is when objects on the display list are drawn to the screen.

Animation.update() and PSprite.update() are related functions that play through the sprite animations. They’re pretty high on the cumulative time list, but they’re a constant load–not what we’re looking for, which is a noticeable pause.

Grid.highlightForAbility() and Tile.highlight() are clearly relevant, and they’re ranked very high in terms of time usage. A closer look at Grid.highlightForAbility() reveals that it’s spending most of its time in various highlighting functions.

Method Cumulative Time (ms)
Grid.highlightWalkableTiles() 3316 (49.73%)
Grid.highlightAttackMoveTiles() 2823 (42.34%)
Grid.unhighlightAll() 317 (4.75%)
Grid.highlightAbilityTargetableTiles() 212 (3.18%)

Drilling down further, each of those highlighting functions seem to be spending most of their time in Tile.highlight()

  • Grid.highlightWalkableTiles() – 3316 ms
    • Tile.highlightWalkable() – 2598 ms (78.35%)
      • Tile.highlight() – 2596 ms(99.92%)

Time to take a look at Tile.highlight(). Here are all its callees with more than 10 ms cumulative time:

Method Cumulative Time (ms)
Node.addChild() 693 (26.69%)
IsoRectangle.as3isolib.display.primitive.IsoRectangle() 397 (15.29%)
AssetManager.createInstanceFromAsset() 303 (11.67%) 45 (1.73%)
IsoPrimitive.set stroke() 18 (0.69%)
IsoPrimitve.set fill() 16 (0.62%)

All of these methods except AssetManager.createInstanceFromAsset() come from as3isolib, the graphics library we use for isometric display. It looks like every time a tile’s highlight is set, a new isometric object is created for the highlight and added to the scene. The instantiation and adding account for about 50% of the total time spent in Tile.highlight(). Multiplied over our 770 calls to Tile.highlight(), that adds up! Looks like we found our culprit.

My solution was to remove instantiation entirely. I created a single isometric object for the overlay, with one BitmapFill. When highlighting a tile, I used BitmapData.copyPixels() to update the relevant section of the BitmapFill. Since I now only needed one master instance of each of the tile highlight textures, I had them pre-load during initialization. After these changes, the highlight functions spent a tiny fraction of their time in BaseTile.highlight():

  • Grid.highlightAttackMoveTiles() – 1064 ms
    • Tile.highlightAttackMoveable() – 3ms (0.28%)
      • Tile.highlight() – 3 ms (100%)
1 Comment :, , full post

Dungeons and Dragons: Warbands

by on Nov.15, 2012, under Portfolio

warbands_title_croppedDungeons and Dragons: Warbands is a mobile, social, turn-based squad tactics collectible miniatures game based on the tabletop Dungeons and Dragons: Warbands 4th edition rules. Players collect miniatures which they can assemble into squads and use to fight battles versus other squads. Players can fight versus AI opponents, or asynchronously against other players. Monetization revolves around collecting miniatures or purchasing consumable items for use during battles.

I worked on both the client-side front-end and server-side back-end. The front-end was created in Unity3D, using a mix of Unityscript and C#. The server backend used PHP, MySQL, and memcached and was structured similarly to the Heroes of Neverwinter backend. I came onto the project midstream to help overhaul the AI, which at the time was unsatisfyingly dumb. We improved the AI enough that we later had to tone it down for beginning players.

My major contribution to the project involved multiplayer functionality. The game was initially intended to be single-player only, and much of the code relied on that assumption. We embarked on an ambitious revision of the code that untangled that assumption, and streamlined and optimized the result. I adapted several systems, including the AI. I also wrote the server code necessary for multiple players, exposed the server-side API, and integrated that into the client.

The game was released for a soft-launch/beta in Canada on November 15, 2012 but has not yet seen a world-wide release.

Leave a Comment full post

Spiral Code Snippet

by on Jun.27, 2012, under Blog

I recently needed to make something spiral outwards on a grid. With a bit of experimentation, I found that the steps taken by the spiral always have a pattern like Left Up RightRight DownDown LLL UUU etc. Here’s the snippet I came up with. You can change the starting direction and spiral direction by changing the values in the switch statement.

  1. var currDir:int = 0;
  2. var stepsPerSide:int = 1;
  3. var currSteps:int = 0;
  4. var x:int = startX;
  5. var y:int = startY;
  7. while (notDone())
  8. {
  9.     doThingAt(x, y);
  11.     switch(currDir)
  12.     {
  13.         case 0:
  14.             x += 1;
  15.             break;
  16.         case 1:
  17.             y += 1;
  18.             break;
  19.         case 2:
  20.             x -= 1;
  21.             break;
  22.         case 3:
  23.             y -= 1;
  24.             break;
  25.     }
  27.     currSteps++;
  28.     if (currSteps >= stepsPerSide)
  29.     {
  30.         currDir = (currDir + 1) % 4;
  31.         if (currDir == 0 || currDir == 2)
  32.         {
  33.             ++stepsPerSide;
  34.         }
  35.         currSteps = 0;
  36.     }
  37. }
Leave a Comment full post

Array shuffling

by on May.27, 2012, under Blog

Array shuffling or randomization is one of those things that’s easy to get wrong in subtle ways.

The naive way looks something like this (Actionscript):

  1. for (var i = 0; i < myArray.length; i++)
  2. {
  3.     var swap = Math.random() * (myArray.length-1);
  4.     var temp = myArray[i];
  5.     myArray[i] = myArray[swap];
  6.     myArray[swap] = temp;
  7. }

Understanding what’s wrong with it requires a little bit of basic probability. Let’s say you have a deck of 3 cards, ABC. How many ways can you arrange them? If we write them out, we find a total of 6 arrangements:

  1. ABC
  2. ACB
  3. BAC
  4. BCA
  5. CAB
  6. CBA

Writing them all out is fine for 3 cards, but what if you have a full deck of 52? Even 5 cards will be a headache. So let’s use a bit of math. Here are the 5 card slots we have:

__ __ __ __ __

For the first slot, any of the 5 cards, ABCDE, can go in it. There are 5 choices for the first slot:

5 __ __ __ __

Once we’ve put a card in the first slot, there are 4 cards left. Any of them can go in the second slot. If we drew A first, then the second slot could be any of BCDE. If we drew B first, then ACDE are all possible, and so on:

5 x 4 __ __ __

Similarly, the third slot has 3 possible cards that can go in it:

5 x 4 x 3 __ __

And we can fill in the rest:

5 x 4 x 3 x 2 x 1 = 120

You may recognize this as the factorial function, written as n!, where n is the first number. An ideal shuffle would have an equal chance of producing any of the n! possible arrangements. How does the naive method I showed above stack up?

For a size 5 array, there’s an equal chance of any of the 5 elements being assigned to the first index:

5 __ __ __ __

For the second index, we pick another element from the whole array, meaning there’s 5 possibilities:

5 x 5 __ __ __

In fact, for every index in the array, every element has an equal chance of being chosen:

5 x 5 x 5 x 5 x 5 = 3,125

3,125 is a lot more than 120, and since 3,125 / 120 = 26.041666…, there’s no way to evenly divide the results. What happens is that multiple sequences of swaps will lead to the same arrangements, with some more common than others. e.g. if we start from ABCDE, both of these will arrive at BCDEA:

  1. Swap 0 and 1 — BACDE
  2. Swap 1 and 2 — BCADE
  3. Swap 2 and 3 — BCDAE
  4. Swap 3 and 4 — BCDEA
  5. Swap 4 and 4 — BCDEA


  1. Swap 0 and 4 — EBCDA
  2. Swap 1 and 0 — BECDA
  3. Swap 2 and 1 — BCEDA
  4. Swap 3 and 2 — BCDEA
  5. Swap 4 and 4 — BCDEA

What we really want is something that gives each arrangement exactly 1 chance of appearing. Here’s some code that does the trick:

  1. for (var i = 0; i < myArray.length; i++)
  2. {
  3.     var swap = i + Math.random() * (myArray.length – i);
  4.     var temp = myArray[i];
  5.     myArray[i] = myArray[swap];
  6.     myArray[swap] = temp;
  7. }

It goes through the array in order from 0 up to myArray.length, picking an element that hasn’t been swapped each time. So the first element has n choices to swap with, the second element has n-1, and so on, just like we calculated. If we go through the array in reverse, we can simplify the calculation for what index to swap with, and get something called the Fisher-Yates shuffle:

  1. for (var i = myArray.length1; i >= 0; i–)
  2. {
  3.     var swap = Math.random() * i;
  4.     var temp = myArray[i];
  5.     myArray[i] = myArray[swap];
  6.     myArray[swap] = temp;
  7. }

If you need to shuffle an array, use the Fisher-Yates shuffle!

This blog post was prompted because I recently came across some shuffling code that produces very skewed results, even worse than the naive method:

  1. for (var i = 0; i < myArray.length; i++)
  2. {
  3.     var swapIndex = Math.random() * (myArray.length-1);
  4.     var temp = myArray[swapIndex];
  5.     myArray.splice(swapIndex, 1);
  6.     myArray.push(temp);
  7. }

Don’t use this. Seriously. Out of curiosity, I wrote a Python script to test how badly skewed the results are. It runs this shuffle, the naive, and the Fisher-Yates 500,000 times on a 4-element array, and outputs what fraction of the time each arrangement comes up. I put up the results in a Google spreadsheet. You can see that Fisher-Yates’ results are pretty much the ideal. The naive is somewhat distributed, but arrangements starting with 2 will come up more than others. And the last shuffle is quite terrible, with 1 having a 34% chance of being the first element. It also takes longer, since it has to rearrange the elements of the array with every swap.

So in conclusion, use the Fisher-Yates shuffle. It’s fast and easy. Better yet, see if your language has a built-in array shuffle. Both PHP and Python do.

Leave a Comment :, , full post

Dungeons and Dragons: Heroes of Neverwinter

by on Sep.18, 2011, under Portfolio

 Dungeons and Dragons: Heroes of Neverwinter was a turn-based RPG on Facebook based on a Dungeons and Dragons 4th edition. Players created a character, choosing one of 4 classes and races. They could then recruit other players’ characters to form a full party and go on adventures. Each adventure consisted of several rooms, most containing a combat encounter. Combat was turn-based on a grid, using a simplified version of the D&D rules. When a character reached level 10, the player gained access to the Dungeon Builder, which allowed them to create their own levels by choosing and populating a dungeon layout. When another player used your character, you had the option to watch their progress as a spectator. You could chat with the player, and had access to some spectator-only buffs you could use to help out. Your character would also gain some gold from you spectating.

skeleton_acidarrow_uiI worked on both the client-side front-end, and the server-side back-end. The front-end was primarily in Flash Actionscript 3, using the Gaia Flash Framework for high-level structure and as3isolib for the dungeon sections. I touched almost every system in the game and, focusing on the dungeons and combat gameplay. I was solely responsible for the abilities system, monsters, AI, adventure scoring, and tutorials, and made revisions to the buffs, looting, and spectator systems. I also did most of the Facebook API integration. When performance problems cropped up, I optimized the graphics and pathfinding. I took over the save/load and spectator systems when the original programmer was moved to another project and was responsible for fixing any synchronizing issues that came up, leading to a deep knowledge of the gameplay systems.

dnd_chestThe server was written in PHP with MySQL, using memcached for caching. I was responsible for setting up the db tables for most systems as well as basic server API functionality for them. This included character status, adventure progress, and monster and other game data definitions. I also worked on the data import tools the designers used to define abilities, monsters, items, etc. I soon became the go-to server expert.

Sadly, the game did not do as well as was hoped, and Atari shuttered it in favor of Dungeons and Dragons: Warbands.


Leave a Comment full post

Guitar toy

by on Aug.22, 2010, under Blog, Lab

I was playing with the Flash Player 10 audio API and made a little guitar toy using Karplus-Strong synthesis.

Get Adobe Flash player

Leave a Comment :, , , full post

Demo – Stixel

by on Aug.18, 2010, under Blog, Lab

For the last Ludum Dare, I started using Flixel, but ran into problems with how it handled rotation and nested sprites. As a result, on Saturday night I tore out Flixel, and started throwing together a quick DisplayObject-based replacement framework, including some basic rigid-body physics. I didn’t finish in time for the end of Ludum Dare, but since then I’ve cleaned it up somewhat and fixed the worst of the bugs.

Here’s a brief bouncing-balls demo. The balls have an elasticity greater than one, meaning they gain energy from collisions. The world wraps horizontally. If you wait a bit, you can see the balls go through a phase transition similar to what happens to photons in a laser.

Get Adobe Flash player

Leave a Comment :, , full post

Instant Jam Flash Version

by on Aug.16, 2010, under Portfolio

Logo for Instant Jam with the words "Instant Jam BETA" on a background of light rays

Instant Jam was an online rhythm game for Facebook. Its major selling point was “play with your music library”–they provided note charts for songs, while you provided the MP3 files. This allowed them to have a vast selection of available songs without paying the usual licensing fees, and meant that users didn’t need to re-buy songs they already owned to play them in Instant Jam.

I worked on the Flash version of the Instant Jam client frontend. It was created for compatibility with Macs, and as a preview for users who did not wish to download the proprietary InstantAction plugin.

I did a lot of UI work for Instant Jam, attempting to match the features of the InstantAction version as closely as possible. I also heavily optimized the main rhythm game component, using profilers to pinpoint causes of frame hiccups and then addressing them.


Unfortunately, InstantAction closed its doors in November 2010, and InstantJam was shut down.

Leave a Comment full post

Simple Sudoku and Modes of Thinking

by on Feb.17, 2010, under Blog

A while back, I found Simple Sudoku, a freeware Sudoku puzzle maker/solver. It generates puzzles for you to solve, and also has a lot of features to make it easier to solve them. After playing way too much Sudoku in it, I realized why it makes things so much easier. On the surface, Sudoku is all about logical deduction–the 9 in this square means you can eliminate 9’s elsewhere in the row and column, and so on. However, at higher levels, Sudoku is actually about pattern recognition, and that is what Simple Sudoku reveals.


1 Comment :, , , full post

Looking for something?

Use the form below to search the site:

Still not finding what you're looking for? Drop a comment on a post or contact us so we can take care of it!