anpshawn

[anpshawn]

Torchlit Columns

As we work on Soda Dungeon 2, our goal is to improve the experience from the first game in almost every possible way. This usually means more robust content, but visuals are important too. Since I’m working in Unity now I have more options available to me. After a few days of research and deliberation, I put together a torchlight shader that produced an effect like this:

Pox had originally sent me a draft of some cavern art that featured this stone column:

I loved the lighting, but it would require that he hand-animate the lighting any time we wanted to use that effect. I was pretty bad with shaders (and still am), but I was sure I could accomplish something at least close to that.

The first step was to see what Unity’s built-in lighting system could give me. So I put a sprite into the scene, added an orange light, and got this:

It’s... okay, but not even close to what we wanted. The effect has no depth to it, the outer edges of the sprite are darkened, and the glow is too smooth. So next up, I tried generating and adding a normal map to the image:

The column now took shape with actual crevices for the light to spill into. But the other problems still persisted, not to mention that the final result adopted a somewhat metallic look to it.

At this point I knew I had to bite the bullet and actually try to write a shader. I knew the basics of how one operated, but rarely could I get it to do what I really wanted. Turns out Unity still does a lot of work for you- such as pre-populating your shader program with information regarding the lights you have set up in the scene. I mapped out an example image of what I wanted to accomplish:

It was a lot less painful that I expected, so after some more tinkering I set up two textures- one of the base column, and one of what it would look like fully-lit by a torch. The first iteration of my shader was basically just a circular mask that revealed the underlying texture depending on where the light was.

Although it was incredibly simple looking, it was already closer to what I wanted than the first tries with Unity’s default shaders. The next challenge was extruding some height information about each pixel. Luckily, this column was already created with lighting information naturally embedded. You can look at the column and tell which areas are supposed to be light and which should be dark. All I really needed to do was re-sample the original texture, convert the color to grayscale (thanks, internet), and use that to represent height. White pixels were “highest” up and received light first, darker pixels were “lower” and received light last. A few multiply operations later I was able to apply this concept to the light, and make a hard cut-off for alpha values to maintain that harsh look.

It’s far from perfect- you can see in pox’s original concept that the light incorporates a better sense of direction and depth. It’s not just that some areas of the column are always lighter, but they’re also lighter if they are closer to the source. I’m still happy with the effect though, and I think it will be suitable for the game even if I can’t nail down the exact look. 

At first I was incredibly scared of shader code and was overthinking what I wanted to accomplish in terms of lighting, normals, height maps, etc. Once I dug in though, the result came together easier than I expected. Shaders seem to require an endless void of esoteric knowledge to navigate, but I’m at least 1% closer to understanding them.

Oh, and it comes in green too:

[anpshawn]

Encoding, Decoding, Serializing, and Timestamps

Every now and then I like to do a write-up on something code-related. The issue I faced recently was probably one of the most convoluted programming rabbit holes I’ve ever been down, so it seemed to be a fitting subject. The problem I faced revolved around the Save File Transfer System that I created for my game, Soda Dungeon. In particular, when I used the system to transfer a file to an iOS device, the application crashed. First, a quick overview of the existing system: When the game saves, it writes a long list of values into a string using a Serializer. Values like gold, dungeon level, items collected, etc. That value is stored to disk, then deserialized and cast back to its native format when the game loads. The transfer system just builds on this concept. Although the serialized string is semi-obfuscated, parts of it still read as plain text. I was also concerned that it may internally contain some instances of “special characters,” and I get paranoid about packing up and transporting those around. I decided to encode the serialized string into Base64- meaning that the result would essentially only be comprised of plain, alphanumeric characters. This also meant that the resulting string would be larger, but I thought it was a fair trade-off for “safety.” In hindsight Base64 was probably complete overkill and probably not necessary because I wasn’t sending the file as a url parameter or anything, but it’s what I locked myself into. So we have this file that crashes when loaded on an iOS device. At first glance, there could be a lot of culprits. Was the file getting corrupted? Was iOS unable to process the encoding/decoding in the same way the other platforms did? This led me through a lot of false-starts and red herrings before I found my way to the root of the problem. Soda Dungeon is programmed in HaXe, and at first I thought maybe iOS had an issue with HaXe’s dynamic typing system. So I updated the code and made sure all variables relating to the transfer were strictly-typed. No luck. I did a lot of print-outs of both the serialized string and the Base64 encoded string on different platforms, searching for a way in which the data differed. Everything seemed to match up. Another fumble occurred when I was sure that I had discovered extra whitespace in one of the files. But it turned out that my text editor’s auto-format had simply done this behind the scenes because I forgot to turn the feature off. I wasted a lot of time down that path, too. Eventually I got the crazy idea to do something I should have tried much sooner: uploading and downloading the same save file without leaving the iOS ecosystem. Unsurprisingly, it worked. Also, as I had found previously, files transferred from iOS to any other platform still loaded fine. So here was definitive proof that the file was changing somehow, to a format that iOS could just not process. I was convinced that the issue now related to the difference in how Windows and iOS encoded their line endings- Windows using carriage return + line feed (CR+LF), while iOS must be using what OSX used, which was borrowed from UNIX: line feed only (LF). This led to more wasted hours of trimming the files for various kinds of whitespace, which is what the line ending characters were considered. Again, no luck.

Then, I realized I had glossed over a very important detail: When I compared the different file strings from each platform, I was only ever examining the original one generated on Windows. Sure, I compared it to the file that was downloaded onto iOS. But it still came from Windows. I never compared it to one that was generated on iOS. Sure enough, they differed.

When converted to their regular, serialized format, each string was almost identical, save for a few random sections. So this ruled out the line ending theory. The problem was that I had no idea what kind of data these differing chunks of text actually represented. But like I mentioned before, the serialized format was only partially obfuscated. Any time I stored a value as plain text in the game’s save file, it would read as plain text here. As it turned out, one of these mystery chunks landed right before some plain text values I could recognize: the list of enemies seen in the bestiary. I loaded up the code that was responsible for the initial serializing of the save file, and answer was very clear: right before I serialized the bestiary information, I serialized two date objects.

Knowing this, I could map the mystery chunks 1:1 with a corresponding date object. I discovered that the crux of the issue was that on Windows the dates were being encoded as a raw timestamp: “1459545643000.” On iOS, this value was encoded as a formatted string: “2016-04-01 17:20:43.” Looking at it now it seems pretty obvious that the data I was trying to inspect was a date, especially considering that “2016″ showed up. But it’s not quite as obvious when surrounded by hundreds of other characters. Also it was late at night.

So now I had to find a way to convert the timestamp to a formatted string so that the file would be accepted on iOS. Seeing that the timestamp was just a series of numbers I assumed it was a UNIX timestamp, aka the number of seconds that had passed since January 1st, 1970. This would be very ironic, considering it was Windows that had chosen to adopt the UNIX file endings, not the other way around. But after plugging that number into a UNIX timestamp converter, the resulting date was completely different from the formatted one that iOS was encoding with. I turned to the HaXe documentation to try and figure out the nature of the timestamp. It didn’t explain anything, but as luck would have it, HaXe lets you generate a new Date object by passing in a timestamp. Surely it was the same timestamp format it was using to serialize with on Windows? Sure enough, it was. After creating the date object and printing it as a formatted string to the console, it matched the iOS date exactly. Down to the very second.

I was in the homestretch. The problem was solved, but now I needed to perform this conversion automatically whenever a file was loaded on iOS. First, I noticed that whenever a date was serialized, regardless of platform, it was always preceded with a ‘v.’ On Windows, that ‘v’ was always followed by the 13 digit timestamp. Based on the surrounding serialized values, it seemed safe to assume that a ‘v’ followed by at least 13 digits was a date. From here it was pretty straightforward: use a Regular Expression to capture all instances of the timestamp patttern, strip off the ‘v,’ cast the digits to a number, feed it to a date object, output that as a formatted string, and swap it back in for the original value that was found. As such, here is the code snippet that saved the file transfer system on iOS:

var dateMatch:EReg = new EReg("v[0-9]{13,}", "g"); nativeSaveFileString = dateMatch.map(nativeSaveFileString, mapTimestampToFormattedString);

function mapTimestampToFormattedString(match:EReg):String { var timestamp:String = match.matched(0); timestamp = timestamp.substr(1); var numericTimestamp = Std.parseFloat(timestamp); var date = Date.fromTime(numericTimestamp); return "v" + date.toString(); }

There was only one catch: nothing prevented this timestamp pattern from showing up inside of another string value. So if for some reason I named an enemy “v1234567890123,” that name would be captured and converted to a date string. With a little more work I could come up with a way to preemptively filter out strings like this, but it seemed unnecessary. If we ever decide to name an enemy in that fashion then I think we deserve it. At least iOS would still parse the file correctly.

[anpshawn]

Rewriting the Liquidate Algorithm, Part 2.

This is a continuation from Part 1, where I discuss the need to write a proper liquidate algorithm for Soda Dungeon. So let’s jump right in.

Problem Statement: Given a list of items of varying quantities and levels, liquidate (sell off) all but the maximum amount of each that can be equipped, while making sure those kept are also the most valuable. Do not remove any items that are currently equipped by a character, regardless of value.

You can check out the full code over on Pastebin.

There are a lot of extra details in the class itself, but I’m just going to focus on the main function here: calculateLiquidateValue(). It’s worth noting that the Liquidator class had to be designed to work in two parts. First, calculate the liquidate- then actually do it. This is because when the user clicks the ‘Liquidate’ option, we simply tell them how much they will receive, without actually enacting the liquidation until they give us the go-ahead. 

Let’s look at a quick test case:

ItemLevelQuantityEquip CountDagger1032Dagger910Dagger811Dagger731Dagger620

We’ll want to keep three of the level 10, one level 9, and one level 8. We’ll also keep one level 7 because it’s equipped, and none of the level 6.

 First, we start by resetting and declaring some variables.

liquidateValue = 0; liquidatedQuantities = new StringMap<Int>(); var numToKeepOfBaseId:Int; var numKeptOfBaseId:Int; var baseIdsCovered:Array<String> = []; var curBaseIdGroup:Array<Item> = []; var tempItem:Item; var numKeptOfCurItem; var numLiquidatedOfCurItem;

First we reset the liquidate value and quantity list, which belong to the class itself. These are used later to actually enact the liquidation. The rest of the variables are local to this function only. As we loop through and examine each item, we need to be aware of how many we are keeping, and also how many we are keeping for any item that shares that same base id. In the table above, each type of Dagger has its own unique id, but they all share the same base id.

for (item in itemListToLiquidate) { if (idIsInList(item.baseId, baseIdsCovered)) continue; baseIdsCovered.push(item.baseId); if (item.cannotBeSold) continue;

For each item in the list, we stop to see if we have already examined its base id. If so, continue to the next item. Otherwise, mark its base id as ‘examined.’ Lastly, make sure this item can even be sold at all. Unique legendaries like the Soda Stein and Widowmaker can’t be sold, so we skip them entirely. 

if (item.type == Item.SPECIAL_ITEM) numToKeepOfBaseId = 10; else numToKeepOfBaseId = 5; numKeptOfBaseId = 0;

Next, decide how many of the current base id we can keep. Swords/Armor are limited to five, but we can keep ten of any special item since some classes can equip two of them. We then set ‘numKeptOfBaseId’ to 0, because, well, we haven’t kept any just yet.

clearArray(curBaseIdGroup); for (i in 0...itemListToLiquidate.length){ if (itemListToLiquidate[i].baseId == item.baseId) { curBaseIdGroup.push(itemListToLiquidate[i]); } } curBaseIdGroup.sort(compareLevel);

Now that we know what base id we’re working with, we then iterate the full item list one more time to pull out all items that share that same base id. We then sort by each item’s level, descending, so we get a nice ordered list that looks pretty close to the table shown up top. Remember: this operation is going to take care of all items of a particular base id. This inner section will only run once per base id, due to us tracking which ones have already been covered.

for (i in 0...curBaseIdGroup.length) { numKeptOfCurItem = 0; tempItem = curBaseIdGroup[i]; numKeptOfCurItem = tempItem.equipCount; numKeptOfBaseId += tempItem.equipCount;

So now we examine each item in our sublist. We reset numKept to 0 for each new item. We then start with a very easy given: We’re at least going to keep as many as are currently equipped. It doesn’t matter what level the item is, or how many we have, we never want to get rid of something that is already equipped.

for (j in 0...tempItem.getAvailableQuantity()) { if (numKeptOfBaseId < numToKeepOfBaseId) { numKeptOfBaseId ++; numKeptOfCurItem ++; } else break; }

Next is the slightly tricky part. We’ve kept as many as are equipped, but we still need to keep as many as we can until the limit for our base id has been satisfied. We’re safe to do this because our list is sorted by the highest level, descending. That means each item we examine is the highest or next highest level available to keep. We step through the item’s remaining inventory, one at a time, until we satisfy our conditions. The ‘getAvailableQuantity’ function simply returns the total quantity for an item, minus its equip count. So as we step, if we have still not kept enough of this base id, we keep it. If the item doesn’t have a quantity high enough to satisfy our demand, the loop will naturally exit as we reach the end of the item’s available quantity. The loop will continue to the next item: numKeptOfCurItem will reset, but numKeptOfBaseId will remain where we left off at.

The loop will continue to examine every item to make sure we are at least keeping the amount of it that we have equipped.

numLiquidatedOfCurItem = tempItem.quantity - numKeptOfCurItem; liquidateValue += numLiquidatedOfCurItem * tempItem.getResaleValue(); liquidatedQuantities.set( tempItem.id, numLiquidatedOfCurItem);

The last step is to simply record our progress. Since we know how many we are keeping of an item, we also know how many we are getting rid of. So we multiply that by the item’s resale value, and keep a running total of how much the user will earn for their liquidate. We also make note of the current item’s id and how many we are getting rid of in a separate list. If the user confirms their liquidate, we revisit this list so we know what changes we actually can finalize with the item list located in the save file.

There are other small details to cover, such as how the enactLiquidation function carries out its duties. But if you’ve followed along with my clunky little algorithm so far, the enact part should be cake. Also, I just wanted to focus on the core of the liquidate process for this post. I don’t do very many programming write ups, so hopefully I explained myself succinctly while still making sense. Let me know!

[anpshawn]

Rewriting the Liquidate Algorithm, Part 1.

I recently re-wrote the "liquidate" algorithm for Soda Dungeon, and seeing as how I've yet to do a real programming post, I thought it might make for a good subject.

Once upon a time, Soda Dungeon was a simpler game where there existed only one type of each item in the inventory. It was just a matter of storing the item's id and quantity as a pair. Soon after came the liquidate function. As time went on you tended to accumulate a lot of junk loot. Liquidate would simply look at each item, and auto-sell any quantity above the max that could be equipped. For special items this was ten, for the rest it was five. Easy stuff.

But then came leveled items. So no longer was there just a wooden sword, there was wooden sword level 2, 3, 4, etc. Since these levels had different stats, and needed to appear as separate entities in the item menus, it meant each level of each item was now a separate record. Multiple copies of the same item and level could still be stacked, but multiple copies of the same item with different levels could not.

The issue quickly became apparent: Since liquidate only examined unique item ids, that meant we could still end up with five copies of each level of each item. Liquidate would still clear some clutter, but are you really liquidating if you still have 30 extra copies of an item that happen to be low-level?

My naive solution was to introduce a “Liquidate Low” feature. Before calculating a liquidation, I made a quick pass to filter out only the highest available level grouping of each item. So if your highest wooden sword level was 7, any copies of any lower level were automatically liquidated. Then, once we had the highest level of each item, its quantity was still liquidated down to five just like before. So now we have much less clutter, but two new issues arise.

First, what if the user has actually chosen to equip a lower level version of an item? The algorithm decides to keep five copies of the level 7 sword, but the party currently has a Soda Junkie with a level 3 sword equipped. We could liquidate it, but we’d have to make sure the character is unequipped properly. We could also swap it out for the higher item level. Both options introduce hidden behavior into the liquidate function, which is not good for the user. We made a simple promise to the user: liquidate the items you don’t need. If we start toying with equip states the user may become frustrated when they can’t figure out why their team build has changed. My solution here was just to add an extra step to the first pass that ensured that no item could be liquidated below its current equip count, regardless of how low its level was. So liquidate could now result in more than enough copies of any given item, but with no hidden consequences.

The second issue was much more tricky to deal with, and one I procrastinated on until just recently: What if the user only has one or two of the current highest level item? If you had one level 10 sword, and twenty level 9 swords, the algorithm would ditch all level 9′s (unless equipped) and leave you with the single level 10. We want liquidate to leave you with ”top five highest levels of any item,” not just “up to five of the highest level item, if they exist.” The reason this became tricky is because those top five items could be spread among 1-5 different records, with gaps in the levels. So a proper liquidate might need to hold onto two level 6 swords, one level 4 sword, and two level 2 swords. And it still had to account for any that were equipped, whether they fell into the group to keep or not.

I was getting burnt out on messing with the liquidate function, so I left it that way for quite some time. The pseudo-workaround was to just make sure you liquidated after equipping your items so it didn’t toss out anything you needed. It had been nagging me every time I opened the to-do list though, so I finally decided to address it properly.

In Part 2 I delve into the code of how my (probably very inefficient) algorithm works.

[anpshawn]

So Here’s Tumblr

After all the fuss about setting up a custom Wordpress installation and server last year, here I am on Tumblr. Updating Wordpress is a pain anyway.