Blog - selene tan
selene tan

Blog

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 Dauntless.be 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%)
BitmapFill.as3isolib.graphics:BitmapFill 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

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;
  6.  
  7. while (notDone())
  8. {
  9.     doThingAt(x, y);
  10.    
  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.     }
  26.    
  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

and

  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

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

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.

(more…)

1 Comment :, , , full post

Prototype: Sideliner

by on Feb.14, 2010, under Blog, Lab

One thing I noticed about the Ludum Dare Flash entries was that most of them were done with flixel. For the competition, I decided not to use it because I didn’t want to learn a new library in the same 48 hours I had to make a game.

Anyway, I’ve finally gotten around to trying flixel out. I cast around a bit for a game idea that I thought would suit flixel’s strengths. It’s a game with 3 tracks where rocks come at you and you have to switch tracks to dodge them. The longer you stay on a track, the faster it gets. Also, as you get closer to the right side, the track speeds up and you gain a score bonus. Pick up ore for points, and red orbs for more time.

Get Adobe Flash player

Previous version (0.5)

Unfortunately, it’s not really fun. The graphics were also a pain. Rocks I can do; the drill took me at least twice as long.

Leave a Comment full post

Fixed bugs in SEEK*TOR

by on Dec.20, 2009, under Blog

I finally tracked down the bug in SEEK*TOR that sometimes makes the red enemy square (and some of the ally turrets) unclickable. While I was at it, I squashed a few more bugs I found along the way.


Play SEEK*TOR v 1.2

Changes in this version:

  1. Fixes bug where the upper-left turret is unclickable
  2. Fixes bug where sometimes the red enemy square is unclickable
  3. Fixes bug where on very high levels, the level never starts
  4. Turns off debug flag so turret layouts are randomized between 4 choices instead of just one
  5. Background music now loops

So what caused the unclickable-things bug, and how did I track it down?

With the help of debug output, I discovered that when a turret or enemy was unclickable, it was because something else on the screen “stole” the click event. In the unclickable upper-left turret bug, the click event was going to the flare display in the upper-left. In the unclickable enemy square bug, the click event was going to an object with a name like SpriteXXX. XXX was a number that was larger the later in the game the bug appeared.

The object name was my biggest clue. The number meant that it was a sprite that was created every level. The turrets are created anew every level, but they show up as TurretXXX. So I combed through the code until I found a sprite that was being created every level.

The sprite I found was the little explosion graphic that shows when you click on the enemy turret. In my competition-driven haste, I’d written code that created a new sprite every time the explosion went off, and didn’t bother to make it unclickable, or remove it from the stage afterward.  To fix the bug, I modified the code so that it created the explosion sprite only once and reused it every level, and I made sure the sprite was unclickable. That fixed the bug.

Leave a Comment :, full post

Post-Mortem: SEEK*TOR

by on Dec.15, 2009, under Blog

So this was my first Ludum Dare. I did the Global Game Jam back in February, so I had some idea of what to expect, although the GGJ was teams rather than solo. One thing I do regret is not interacting more with the community–IRC, Twitter, etc. I could have used more feedback than I got, instead of relying almost entirely on my husband’s comments.
Friday night I spent brainstorming ideas and thinking over mechanics. Saturday morning I started coding. By late afternoon / early evening, I had the major mechanics implemented, but it wasn’t fun. At that point the turrets were just yellow diamonds (and they were warp portals which your cyan circle teleported between), and the hint circle always disappeared before you could fire again.

Screenshot of older version of SEEK*TOR
Screenshot of older version of SEEK*TOR

The best thing that happened for the game occurred when I sent my Saturday prototype to a friend for feedback. He told me two very important things:

  1. He had the most fun figuring out where the hint circles intersected
  2. He wanted to know why you had to aim and fire to reveal the map instead of just placing light bulbs around the “platforms” (yellow diamonds)

So I made the hints persist but fade over time. That means you can see the hint circle intersections, but the screen doesn’t become overly-cluttered with old hint circles. It also means the aiming mechanic is important, since if you take too long, the previous hint will have faded away. I also changed the theming of the game so that the portals became turrets and you selected a turret to fire from, rather than teleporting between them.
Sunday was mostly a day of polish. The big feature changes were implementing multiple levels, scoring, and flare limits. I also added the start, game over, and between-level screens, made the graphics, (such as they are–hooray for GlowFilter!) composed a background track, and created the sound effects.
In the end, I was successful in terms of having a pretty-much finished game at the end. On the other hand, seeing some of the other entries, I kind of wish I’d done something a little more ambitious…
Things that worked out:

  1. Using abstract glow-y vector graphics instead of trying to draw. (I spent about 20 minutes attempting to draw a single turret before deciding my time was better spent elsewhere.)
  2. The game selects from 4 (hand-crafted) turret layouts and randomizes the enemy and player locations. That turned out to be enough randomization that I didn’t need to make a turret layout generator. In fact, I only just realized that I left the game in debug mode where it always chooses the same turret layout.

Things that didn’t work out:

  1. When I started, I implemented everything in one file just to see if the core mechanic would work. I made such a mess of my code that I spent hours late Saturday night moving code around so I could add levels. Spending hours working on code without actually adding new functionality–even regressing at times–was very hard on my morale.
  2. I spent too long trying to make my git history tidy. I’d keep forgetting to add a file to the commit or not commit for a while and wind up with a gigantic commit that involved 3 features and all the source files. Then I’d try to figure out how to break up or revise the commits. (And how to use vim, since that’s the default git editor…) Given that I never had to revert to a previous version, it was kind of silly of me.

Tools and Libraries Used:

  1. FlashDevelop
  2. TweenLite
  3. git
  4. ACID Music Studio
  5. Free VSTi soft synths: Crystal, LazySnake, and ErsDrums
  6. Audacity
  7. sfxr

(cross-posted from Ludum Dare)

Leave a 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!