Mike Grundvig's Blog o' Stuff

Marshmallow Madness

2009-05-24T20:21:00.003-06:00

To give me a break from all the remodeling we've been doing I decided to come up with a fun project to waste some time. That project is not the topic of this post :)

As a precursor to that project, I wanted to get a little experience with pneumatic cannons and the like. To that end, I picked up the plans to build the "Ultra Magnum Marshmallow Gun" from here.

The plans are good, I found only a single real issue and that was in the material list. I went ahead and emailed the creator about it for any of you that buy the plans later. It only took me about an hour to put everything together. Honestly, it took me more time to find all the plumbing parts at the local Home Depot. The only thing they didn't have was a stem fill valve and the tire shop at Walmart just gave me a couple out of the goodness of their hearts. Once you get all the pipe cut and glue it together you need to wait forever (24 hours) for the PVC cement to completely cure.

I can only say one thing about it: WOOHOO! It's a lot more fun than I expected. The power at 50 PSI is surprising. By the time I could test it, it was already dark outside so I didn't get to see the full range but the little mini-marshmallows it shoots were smacking into the wall quite loudly from twenty feet. Tomorrow morning I'll put it though it's paces at higher pressures and see the real range.

Expect to see an update in the next day or so with maybe even a video once I get it all painted up. In the meantime, go buy the plans and build one yourself :)

Binary Maps and Data in AS3

2008-01-29T09:30:00.000-06:00

When talking about maps for games, XML comes up all the time. XML makes great sense with it's readibility and ease of parsing. Then I see people use XML to define their map but to save space, they condense everything heavily inside of it. This makes little sense to me. You lose the readability and the ease of parsing in favor of a smaller file size. The trick is that if file size matters and readability doesn't, lose XML entirely and go for something better suited to small file sizes.

With these requirements, I recomend using a binary file format directly and to heck with human readable at that point. Our next project uses this everywhere and it has turned huge maps into tiny files we just load via HTTP. Very clean, simple and incredibly fast. It also has the advantage of taking very little memory because converting from binary to AS3 data types has so little overhead (unlike string --> number parsing).

So let's say you have a 10x10 map. For simplicity, "X" is rock, "O" is grass, and "=" is path. An ASCI version might look like this:

X X X X X = X X X X
X O O O O = O O O X
X O O O O = O O O X
X O O O O = O O O X
X O O O O = O O O X
= = = = = = O O O X
X O O O O O O O O X
X O O O O O O O O X
X O O O O O O O O X
X X X X X X X X X X

This map lets you walk anywhere in the area but you can only leave via the path that enters on the left and exists at the top. Rocks surround everything with grass filling in the gaps. Boring, but a very real-world example.

Now you need to represent that with parsable data. The map data needs to contain two entries per tile, a tile type ID and a boolean for walkable/non walkable. In this case, rock is 1, grass is 2, and a path is 3. The 0/1 next to it indicates if the tile is walkable or not.

Here is an XML version I snagged from a thread on FlashKit game developers forum (sorry Mr. Malee).

Pretty big, even when using the condensed row format. This comes out to 579 bytes. Fall_X (another FlashKit poster) suggests to just use text if you are going to make your XML still require string.split style parsing. I agree, the format can then be:

1:0 1:0 1:0 1:0 1:0 3:1 1:0 1:0 1:0 1:0
1:0 2:1 2:1 2:1 2:1 3:1 2:1 2:1 2:1 1:0
1:0 2:1 2:1 2:1 2:1 3:1 2:1 2:1 2:1 1:0
1:0 2:1 2:1 2:1 2:1 3:1 2:1 2:1 2:1 1:0
1:0 2:1 2:1 2:1 2:1 3:1 2:1 2:1 2:1 1:0
3:1 3:1 3:1 3:1 3:1 3:1 2:1 2:1 2:1 1:0
1:0 2:1 2:1 2:1 2:1 2:1 2:1 2:1 2:1 1:0
1:0 2:1 2:1 2:1 2:1 2:1 2:1 2:1 2:1 1:0
1:0 2:1 2:1 2:1 2:1 2:1 2:1 2:1 2:1 1:0
1:0 1:0 1:0 1:0 1:0 1:0 1:0 1:0 1:0 1:0

But even that is still pretty large. Saved as a text file, it is 408 bytes. While this seems small, this is just a 10x10 grid with almost no data. When you make it a 20x20 grid (still quite small) the file size jumps to 1618 bytes.

How would you represent this with binary? You would first need to define the width and height (in tiles) of the map using the smallest logical data type. In this case, we would use a short. A short is a whole number represented by two bytes that goes to a max of 65k or so. The format would look something like this ([ ] indicates many - ie, iterating over them):

<Map Width (short)><Map Height (short)>[<Tile Type ID (short)><Is Walkable (boolean)>]

Since we know the exact length in bytes of shorts and booleans (1 byte) then we can easily determine how large this will be for any given map. The header is 4 bytes, each tile is 3 bytes. The 10x10 map above has 100 tiles defined. Final size? 304 bytes for a 10x10 map. What about our 20x20 example? 1204 bytes.

Now you might think that this is a trivial gain, and it is UNTIL you start to realize the more subltle differences. The example map has 3 tile types. Let's say your game has 20 tile types and you decide to replace 2 (grass) with 18 (snow covered grass), 1 (rock) with 19 (snow covered rock) and 3 (path) with 20 (snow covered path). What is the impact on your file size if you are using the text format? The 10x10 map becomes 508 bytes and the 20x20 becomes 2,018 bytes. A 40x40 map would be 8,038 bytes while an 80x80 would be 32,078 bytes.

How big is the binary map? It's exactly the same size as it was before. This is because the "short" we are writing is already capable of holding up to 65k+ tile types without changing. In fact, if you were going to have 256 or less tile types, you could even use a single byte to represent them. If you were going to have 128 tile types or less, you could use a single byte to represent both the tile type AND the walkable state of the tile. This is done by simply taking the most significant bit in the byte and toggling it on or off as needed then ignoring it when determining the number. Thus saving even more space!

So realistically, you probably will have 128 or less tile types in the average Flash game but you could have a map >256x256, so the header should still use "shorts" unless you want to go beyond 65k of tiles in each dimension. With this in mind, the new binary format becomes:

<Map Width (short)><Map Height (short)>[<Tile Type ID and walkable state(byte)>]

Now let's try those sizes again:

10x10 map - 100 tiles
Text (not XML) = 508 bytes
Binary (1 byte/tile) = 104 bytes
Binary (2 bytes/tile = 204 bytes
Binary (3 bytes/tile) = 304 bytes

20x20 - 400 tiles
Text (not XML) = 2,018 bytes
Binary (1 byte/tile) = 404 bytes
Binary (2 bytes/tile = 804 bytes
Binary (3 bytes/tile) = 1,204 bytes

40x40 - 1600 tiles
Text (not XML) = 8,038 bytes
Binary (1 byte/tile) = 1,604 bytes
Binary (2 bytes/tile = 3,204 bytes
Binary (3 bytes/tile) = 4,804 bytes

80x80 - 6400 tiles
Text (not XML) = 32,078 bytes
Binary (1 byte/tile) = 6,404 bytes
Binary (2 bytes/tile = 12,804 bytes
Binary (3 bytes/tile) = 19,204 bytes

As you can see, there is a massive size difference and it gets better and better as the map grows larger. In case someone is interested, the reason for this is simply that text in a file takes several bytes under the covers to represent it (depending on the encoding, etc). But when you read/write binary directly, you don't have this issue. You know exactly what will be created and how large it will be. Additionally, all the tricks used to make strings smaller work here too, run-length encoding, compression, etc. are all viable options. Flash even has built-in support for compressing/decompressing a byte array!

For more information on binary and how bytes break down into bits and how you can use em to store information: http://www.freesoft.org/CIE/Topics/19.htm

Now all this is well and good, but how do you use binary in Flash? Assuming you have AS3, it's a piece of cake. You simply need to load your data via HTTP using the appropriate loader class and use it to get at the ByteArray object. Then accessing bytes is trivial:

// Get the initial data array
var inputArray:ByteArray = ... // Data loaded externally into a byte array

// Read all the available parameters
var mapWidth:int = inputArray.readShort();
var mapHeight:int = inputArray.readShort();

// Iterate over the map
for(var y:int = 0; y < mapHeight; y++) {
     for(var x:int = 0; x < mapWidth; x++) {
          // Assuming the 3-byte per tile model
          var tileTypeId:int = inputArray.readShort();
          var isWalkable:boolean = inputArray.readBoolean();
     }
}

Piece of cake. Now how do you save binary in the first place - you go in reverse. You build your ByteArray up and then have to fight with Flash a bit. Since Flash can't directly save data, you need to use something else. I'm betting you could do it with AIR, but I know you can do it with PHP. Easiest solution is to use Base64Encoder in Flash and encode the byte array to a string, then send that string to PHP and have it decode using the built-in decode (link) then simply have PHP save the binary data to the file system.

Now, if you don't want to do the "true" binary file format but you want some of the other advantages binary gives you, you can still just use the Base64 encoded string. It is text and totally usable as such. Just copy it out of a text field and throw it into a text file. Instant binary-ish file format

Nice, clean, and powerful. With binary being finally supported properly, there is very little reason not to take advantage of it. Anyways, enough from me. Have fun!

Austin Game Developer's Conference!

2007-08-17T07:56:00.000-06:00

Hi all, sorry I've not been blogging much lately. I've been super busy on some big projects. I'll start blogging a lot more soon. This is just a quick post to let everyone know that Electrotank is going to be showing off a lot of new stuff at our killer booth at the Austin Game Developer's Conference. This will be the first time anyone has seen our new truss-based booth with a 77" projected screen. Yes, that's 77" of projected image goodness. I'm so happy about how the booth turned out that I'll probably post some pictures of it in a few days.

I'll also be presenting at the conference as well. My presentation is on Web Client Development Issues - Best Practices. The presentation is split into two parts. Michael Bayne (CTO of Three Rings, the guys that made Puzzle Pirates) will be handling the second half. The talk will cover the main technologies used to build web games (Flash, Java, etc), discuss pros and cons of each, and provide tips and tricks on how to avoid the most common development issues. Should be fun. If anyone is going, please let me know and we can meet up at some point.

-=-=-
Update: Now that the talk is over, I can give the URL out:
http://samskivert.com/work/2007/agc/web_client_dev.pdf

Thanks for everyone that came and saw it or met up with us at the show!

ElectroServer 4 Feature Request

2007-06-05T22:06:00.001-06:00

As some of you know, we have been working on ElectroServer 4 for a while. We have now reached a point where we can start added user-requested features. Now is your chance to speak up and tell us anything you'd like to see in a socket server.

If you were sitting down to make the multi-player game of your dreams, what would the server need to support to make your job easier or even possible? What would it need to do to ensure your success? What would make it easier for you to keep the game running or deploy it?

Basically, anything you can think of that might be good to see in a socket server. Don't worry if you have never played with one before or if you think it might already be there, just let the ideas come. I can't promise we will get them all in the next release but I suspect we can get most.

Feel free to contact me directly with mike@electrotank.com or just post a comment below.

Thanks!

AI and Emergent Behavior Examples

2007-06-03T07:57:00.000-06:00

Jobe Makar has put together a great set of posts about AI and emergent behavior on his blog. They are well-worth looking at if you have an interest in this sort of thing.

Game of Life
Boids
Boids in an Actual Game (this one is pretty cool - shows how boids can actually be used to simulate a crowd).

Have fun!

The Pitfalls of Polling and How to Avoid Them

2007-05-30T10:18:00.000-06:00

The topic of polling has come up frequently on the FlashKit Games forum so I figured I'd do a bit of a post on it.

Polling is the process by which a client application can repeatedly contact the server to get updates and simulate real-time behavior. Some AJAX systems use polling in places. For example, you could build a chat on a website by having a Flash client call the server once per second asking if any messages have arrived for the current user. It's pretty simple to implement a basic poll-based chat or game. There are a lot of downsides to polling though and being aware of them can help you avoid the worst problems.

The problem with polling is that under any significant load at all you will be crushing your web server and database. Lets assume each client polls the server every 1000 milliseconds or 1 second. This is quite slow in terms of responsiveness for a game but will work for our example. If you had 100 users, a trivial load overall, you would be generating a hit to your site every 10 milliseconds on average. At 500 users, it would be every 2 milliseconds. At 2500 users it's every 0.4 milliseconds.

As you can see, this will become a crippling load very quickly. You can use a load balancer to help but then you need to use clustered sessions or the database to share data between instances. This will in turn decrease performance across the board.

Another thing to consider is the tremendous bandwidth requirements of that many HTTP requests. Unlike a socket server (like ElectroServer) that is event-driven and doesn't have a heavy protocol to begin with; HTTP contains a great deal of header information that gets sent with each and every request. This, in turn, dramatically increases your bandwidth requirements for both clients and the server. How big is the header? Here is a simple "GET" request header for my browser to my blog server. So this is what a client sends with every page request:

GET / HTTP/1.1[CRLF]
Host: mikegrundvig.blogspot.com[CRLF]
Connection: close[CRLF]
Accept-Encoding: gzip[CRLF]
Accept: image/gif, image/x-xbitmap, image/jpeg, image/pjpeg, application/x-shockwave-flash, application/x-ms-application, application/vnd.ms-xpsdocument, application/xaml+xml, application/x-ms-xbap, application/msword, application/vnd.ms-excel, application/vnd.ms-powerpoint, */*[CRLF]
Accept-Language: en-US[CRLF]
User-Agent: Mozilla/4.0 (compatible; MSIE 7.0; Windows NT 6.0; SLCC1; .NET CLR 2.0.50727; Media Center PC 5.0; .NET CLR 3.0.04506; .NET CLR 1.1.4322)[CRLF]
Referer: [CRLF][CRLF]

While it's just text, it adds up very quickly. Overall polling looks like it would work well but in practice it's often too expensive and slow for most applications.

Alright, assuming you are sticking with polling then there are some things to keep in mind. The main idea is to keep the script you call as fast as humanly possible. Also, the code on the server must be clean and rock solid. In practice, you should avoid hitting the database at all costs for better performance.

You also need to make your code on the client AND the server a bit smarter then you might think. The server code should queue up messages that should be delivered to the client in memory rather then on disk. Then when a client sends anything to the server, the messages should be attached to the response. This way if the client sends a "chat message", the response to that request can contain anything queued up for delivery.

With our previous example, we said the poll call would occur every 1000 milliseconds. That should be thought of as the longest the client will wait before polling. If you use the last approach I suggested, you can make your polling algorithm much more intelligent. As an example:

Time Action
0 poll
1000 poll
1500 send chat message
2000 poll

Should instead be:

Time Action
0 poll
1000 poll
1500 send chat message
2500 poll

In the first block, we poll every 1 second no matter what. In the second block, the code is smart enough to realize that since anything queued for delivery would have come back on the "chat" message request then we can delay another 500 milliseconds before polling again. This way you make the least number of requests to the server and still have just as timely updates.

Likewise, you should have code that prevents the client from sending data to the server too quickly. If you must let them do it, queue up actions to send just like the server is queuing them up to you. This allows you to send multiple requests at the expense of only one header.

Finally, the server should attempt to disregard messages as aggressively as it can. For instance, what if someone joined and then left the room in between a user receiving updates? Ideally the users in the room shouldn't even be told because it doesn't matter. The server should just delete that data and not tell the users. Likewise, if people send several movement updates quickly, the client really only cares about the last one in many cases so just disregard the rest. By culling the data set before it gets to the client, you can decrease the bandwidth needed.

Anyways, I hope this gives you an idea of the pitfalls involved in polling and the techniques you can use to dodge them. Have fun!

CopyPixel is faster then Sprites?

2007-05-23T21:32:00.000-06:00

As soon as you think you've come up with a pretty good way to do something you always find something better. So the other day I post a pretty fast AS3 example here on my blog and on the FlashKit forum. The example takes advantage of a couple performance techniques and seemed to work quite well.

Soon after my post, someone suggested giving it a shot using the copyPixels method on BitmapData to see if it gets faster. I wasn't sure of the results as the copyPixel examples I'd seen were generally really specific to tile engines or some such and not to lots of moving sprites.

So I figured I'd give it a shot. I ran into some trouble with the alpha channels initially but it's all working now and you can see it here:

http://www.electrotank.com/junk/mike/flash/copyPixel/

The performance is so much better and uses less code that it makes me sad. In short, I have arrow objects in memory to represent every arrow. In the render loop (onEnterFrame event) I update their positions/status and create new ones as needed. Once that's done, I create a new BitmapData, loop over all the arrows and use copyPixels from my sprite sheet onto the correct position of the new BitmapData. Finally, I take the new BitmapData, convert it to a bitmap and replace the old bitmap with the new one. That's it. No tricks for performance or anything and it flys.

One thing I don't understand though, in the previous engine (located here) the time spent in the onEnterFrame event is less (look at the "render" field on the right) but the frame rate is lower too. In the new model, the time in onEnterFrame is higher but the frame rate is higher as well. My thought, and this is a total guess, is that the copyPixels method has more code-execution overhead but produces something easily rendered while the pooling sprite approach is the opposite; small code overhead but lots of objects to render.

Sadly, this would mean that you need to choose your approach on what you are trying to do. If you need lots of available horsepower for code, then use pooling. If you need lots of objects then use copyPixels. Obviously this is a generalization but you get the picture. Anyways, have fun!

AS3 is FAST!

2007-05-21T21:28:00.000-06:00

I'm usually the one complaining about ActionScript performance but I have to give credit where it's due. AS3 is just plain fast.

I'd been kicking around some AS3 ideas I had and ran into some pretty nifty performance tricks. You can see them in action at the URL below - (open it full screen as the swf is 1024x768 - no wimpy resolutions for this!):

http://www.electrotank.com/junk/mike/flash/objectpool/

The controls on the left are simple.
Frames -how many frames to run the simulation.
Arrows per frame - how many arrows are to be generated per each frame.
Use pool - should the object pool be used for this simulation run.
Start - start the simulation, turns to stop when the simulation is running.

The stats on the right are a little trickier.
Arrows - the number of arrows currently on the screen.
Render - how many milliseconds the enterFrame event has taken to process.
Total Arrows - the number of arrows used in the simulation thus far.
Total Render - how many milliseconds for all the enterFrame calls in the simulation.

A combination of tricks were used to make it perform as well as it does.

1) Sprite sheets + scrollrect
This is the same trick VengenceMX is using for his Invasion game. In fact, I'm using his sprite sheet (thanks!). Basically, to handle an object + rotation, you simply have a sheet of images that contains all rotations/angles in a row. Then a little math is used to determine which image of the strip is to be shown. You then use scrollrect to show just that image. Think of it like a film strip you can slide back and forth to see only the image you want.

2) Object pooling
Object pooling is the process of storing objects in a pool when they are not in use so as to avoid the overhead of creating them again and again. In AS3, objects that are tied to the library are expensive to create. By storing them in a pool for later use you can greatly reduce memory usage and save a handful of milliseconds every frame.

To see the pooling in action, simply run the simulation with "use pool" checked and note the "total render" time. Then run it again with out and note the difference. The results vary quite a bit but pooling is always faster. Some times it can be as much as 2x faster. In short, pooling burns less time per frame to create the sprites. The effect is even larger with movie clips. You might not see this as a frame rate increase but it still gives you more time to do code that matters (like AI or pathfinding).

One other subtle difference occurs with pooling. You can see a slight "jerkiness" to the simulation if pooling is off. The "jerks" will occur every 1/2 - 1 second or so. I'm reasonably sure they are caused by garbage collection runs inside the Flash VM. Pooling uses a great deal less overall memory and so it experiences a lot less garbage collection all around - ie. smoother animation. This is really visible in scrolling tiles.

3) Utilizing the scene graph arrays
This is simple, but all the little bits count. I needed to store a collection of arrows so I could iterate over them each enter-frame. Traditionally, I'd create an array of arrows to do this. In AS3 though, there is no need. If you simply create a new empty sprite, and add it as a child to the stage, you have your array already.

Anything added as a child can be retrieved and accessed easily. For instance, with my arrows, I had some code that looked like this:

for(var i:int = 0; i < arrows.numChildren; i++) ...

That's it. That gives me my array already with no extra overhead. As I said, not a big deal, but the less work you do per frame the better.

I'll be posting a lot more detail on points one and two in the next day or so. My object pooling code is actually a generic framework that works great as it is and can be dropped into any AS3 project without too much trouble. Have fun!

Encrypting Variables in Memory to Prevent Hacking

2007-05-18T16:14:00.000-06:00

Previously I talked about how hackers can use memory tools to find and directly update crucial game variables on the fly. The solution to this is to encrypt those values. This means that if a hacker searches for a known value (like score) they will fail to find the right one because the score is encrypted in memory.

I felt like dabbling in Flash a bit today so I went ahead and created a little utility to make the in-memory encryption easy. It's written as a pair of AS3 classes. One of them is the TEA implementation from the ASCrypt3 library while the other is the utility itself. This type of system isn't useful if it isn't simple to use so that was the main goal. All methods are implemented as static to avoid needing to instantiate the utility. You can see pretty much every method below:


// Create a handle for the variable
var scoreName:String = "score";


// Set the initial score to 100
MemoryCrypto.setValue(scoreName, 100);

// Increment the score by 100, new value = 200
MemoryCrypto.incrementValue(scoreName, 100);

// Decrement the score by 50, new value = 150
MemoryCrypto.decrementValue(scoreName, 50);

// Multiply the score by 4, new value = 600
MemoryCrypto.multiplyValue(scoreName, 4);

// Divide the score by 2, new value = 300
MemoryCrypto.divideValue(scoreName, 2);

// Get the score
var score:Number = MemoryCrypto.getValue(scoreName);

// Display the score, 300
trace(score);

Pretty simple. Internally it creates an instance of the TEA cipher and a pair of random numbers become the key. This key is then used for all encryption. The variable values are only unencrypted long enough to change and then re-encrypted for storage.

This solution is NOT infallible. A dedicated hacker will be able to actually tear the code apart in memory as opposed to just doing value-based searches but this will make it an order of magnitude harder then otherwise. It will stop many of the script-kiddies dead in their tracks.

The code is available here and free for any use. Have fun!

Ensuring Data Integrity Between a Client and Server

2007-05-16T15:55:00.000-06:00

In my last post, I talked about how to secure a Flash high score board. One of the steps included SSL. Several people immediately mentioned that they don't have access to SSL. To that end, I'm putting together this little post to explain how it can be done without it.

In the case of a high score board entry the data itself isn't secure. You just need to make sure it hasn't been modified. It doesn't matter if someone sniffs the HTTP data as long as they can't change it, right? To that end, there is no need to go overboard with a true encryption system when you can simply use a "digital signature" to get the same result. Basically, the client will "sign" the data and the server will verify that the signature and data match.

Most digital signature techniques can get pretty complicated and involve using public/private key pairs. In our case, we are going to get the same effect with a ghetto approach. We are going to use a "cryptographic hash" to do this. A cryptographic hash function will take a block of data and turn it into a fixed length "fingerprint". The results of a hash function are reproducible. This means that it's output will always be the same for a given input. Another property of a good hash function is that a tiny change in the input will produce a dramatic change in the output.

For the sake of this discussion, we will use MD5 as the hash of choice. There are better ones (like SHA1) but MD5 is supported by just about every language out there and is pretty simple. For example, PHP, JavaScript, ActionScript 1, ActionScript 3, and Java.

Now we need to apply our hash function to the data itself. Say you need to submit a new score for user "Mike" with a value of "12345". The easiest approach is to simply concatenate those together and run the hash, IE "Mike12345" results in "3658279626b5ed3cd137bef212640144". Then you take the name, score, and hash and send it all to the server. The server duplicates the process to generate a hash and compares them. If the hash from the client matches the hash on the server then the data came across unmodified. If the hashes fail to match, you fail the submission. Nice and simple.

You're not quite done though. If you stop here, you are still vulnerable to someone hacking the data. They could look and guess what you are doing (or inspect the SWF code) and duplicate the hash by hand, submitting a fake score. The way to prevent this is to append one more piece of data before you generate the hash. Specifically, a pass phrase or key.

For the sake of argument, lets say you pass phrase is "password". You take the name, score and pass phrase and come up with this "Mike12345password". When you hash it, you get "a0501c5f1276af9b5be999b980a1e18a". Notice how this is totally different then the previous hash? Then, you send the same data to the server as before; name, score, and hash. The server knows the password already and attempts to duplicate the hash. If it can, the score submission is good.

If you obfuscate your SWF, this might be good enough. The problem is that the password itself is contained in your SWF file and the enterprising hacker might decompile the SWF to figure it out. If this occurs, that will be able to easily duplicate the process and create the hash. The solution to this is for another blog post I'll do in a day or two.

As you can see, each layer of security makes things that much harder for the hacker. While some of this seems complicated, much of it only needs to be created once and then reused as needed. A little library could be created that hides all these details from the developer and makes things nice and clean. If someone is interested in doing this, post a comment. I'd be willing to help out if there is interest. Have fun!

Preventing High Score Board Hacks

2007-05-15T13:46:00.000-06:00

Preventing hackers from ruining high score boards seems to come up all the time on the Flash forums. I end up posting some of this over and over again so I figured I'd blog about it to avoid having to re-post it.

In short, there are four steps needed to hinder or possibly stop any casual or semi-casual hacking.
1) Use SSL to prevent hackers from manipulating the data being sent over the wire
2) Encrypt all important variables in memory to protect from memory hacks
3) Use a Flash obfuscator to prevent easy decompilation and patching of the code
4) Validate anything possible on the server (score vs. length of play, etc)

Step 1)
Many of the easiest high-score hacks involve simply packet sniffing the data sent from the Flash client to the server and re-submitting it back to the server with a modified score. Using SSL stops this dead as packet sniffing SSL traffic won't reveal anything useful to the hacker. Super cheap SSL certificates can be purchased from GoDaddy. If SSL is not an option, it's possible to use other security techniques to encrypt or ensure the integrity of the data stream. I've covered this process in detail here.

Step 2)
UPDATE: I've created the utility I suggest below. You can see the post on it here. Encypting the variables in memory seems odd but is a crucial technique to ensure that the memory hacks out there can't actually manipulate the game state directly. For instance, if you have an unencrypted score variable a memory tool would actually let the hacker find that value and update it to something else directly. Then when they submit their score, the game will send the new value as though it were correct. There is no easy way for the game to really know otherwise. Likewise, if you have stats or character abilities, all are easily hackable the same way.
The fix for this is to store the value encrypted. So while the game shows you have 3 lives left, in memory it looks totally different. There is no easy pattern for the hacker to use to find the number of lives. In practice, updating your score by 1 would work something like this:


var rawScore:Number = decrypt(score);
rawScore++;
score = encrypt(rawScore);

In practice, you would probably want to make it even cleaner with some sort of "decryptUpdateAndEncrypt" type methods, something full-service in a single call.

The other trick to this is that the encryption scheme needs to use a "rotating" key. Every time the game is played, the encrypted value in memory should be different. This prevents any clever hacker from determining the key and writing a little tool to duplicate the encryption scheme - thus breaking your protection. Since the key is internal only, you can simply use a random number and it should work fine. You will want to use a nice and fast encryption scheme as well. Something like TEA would be idea. A good JavaScript implementation can be found here. As mentioned above, I've created a version of this utility and posted it here.

Step 3)
This is a general hardening step. If you obfuscate your SWF file, it will be very hard for hackers to decompile it and determine what's going on under the covers. It's always a good practice if you are concerned about security, but try hard to never rely on this as your primary technique because it isn't prefect. While I haven't used SWF Encrypt, I know and respect the owner of Amayeta and have no doubt his product will be an excellent choice.

Step 4)
This is another general step and it's specific implementation depends on the game. Try and validate everything on the server if possible. For instance, if their game session started 2 minutes ago, there should be no way they can submit a very high score. Likewise, track the time of all score submissions, it's not possible to submit high scores with tiny intervals between them. Try and think about how long it takes to play a game and use that as a guide. Also, when you fail a score, don't tell them why. Just say the score submission failed. OR, don't even tell them it failed, just ignore it. This makes the hacker have to work to figure out what went wrong. Don't make it easy for them.

This post doesn't cover everything, it only covers the things many developers forget when trying to harden a game. Also keep in mind that there are lots of exploits in the games themselves. Tricks like slowing down the game timer (thus slowing down movement), exploiting bugs, etc. Make sure you have those covered as well.

Finally, this isn't a way to perfectly protect a game. It simply makes it much harder for a casual hacker. They will have to really work at it if they want to cheat and in practice, that is generally good enough. Have fun!

Data Structures for Flash Games

2007-05-14T21:37:00.000-06:00

I'm very happy to see that a nice set of data structures used for game development has been created using AS3. This collection includes many useful structures like hashtables, BSTs, queues, graphs, linked lists and many more. You can find it here:
http://lab.polygonal.de/ds/

Have fun!

Scripting in Java is now EASY!

2007-05-13T06:51:00.000-06:00

There are a lot of parts of the Java API that I don't like so much. Some feel clumsy or ackward (java.util.zip - try TrueZip to see it handled cleanly) and some are just poor in general (java.net.URLConnection - HttpClient in Jakarta Commons shows how it should be done). But then they come out with a great API that makes you forgive the other irritations. For instance, I've always been impressed with the power of JDBC, the simplicity of JMS, and now, the capability of JSR 232's scripting API which is included with Java 1.6.

For a current project, we need to support multiple scripting languages inside an application. This was a real headache previously. Every language was handled differently and BSF (Bean Shell Framework from Apache) never seemed to work very well.

With the advent of JSR 232, It's be downright easy to add scripting to the system. We wanted to allow developers to use scripts to extend the product. Internally the product uses interfaces at these points so it's easy for developers to use. They simply create a class that implements the interface and register it with the server. Nice and clean. This same approach can be done with scripting languages too!

As an example, consider this interface:


public interface Calculator {
    public int square(int number);
}

This little snippet of code includes everything you need to meet that interface using JavaScript and invoke it with Java. Check it out:


// Build the script itself
StringBuilder script = new StringBuilder();
script.append("function square(numberIn) { \n");
script.append("    return numberIn * numberIn; \n");
script.append("} \n");

// Create the engine manager and get the correct engine
ScriptEngineManager engineManager = new ScriptEngineManager();
ScriptEngine engine = engineManager.getEngineByName("ECMAScript");

// Get an "invocable" version of the engine
Invocable invocableEngine = (Invocable) engine;

// Have the engine parse and load the script
engine.eval(script.toString());

// Use the invocable engine to wrap the script with the interface
Calculator calculator = invocableEngine.getInterface(Calculator.class);

// Call it
int numberToSquare = 2;
int numberSquared = calculator.square(numberToSquare);
System.out.println(
    String.format("%1$d * %1$d = %2$d",
        numberToSquare,
        numberSquared));

Slick huh? The key is the Invocable interface. Any scripting engine that meets that interface provides the ability for you to invisibly treat a script just like a class. You simply give it the interface you want to use and internally a wrapper will be created for your script. It even handles type conversion of all primitives nice and cleanly. For all intents and purposes it IS a class as it will retain scope and variables between invocations.

With a little work, any application that needs it could easily be set up to support scripted extensions. A big thanks to the members involved in JSR 232 for pulling off such a clean approach to a messy problem.

A good article that goes into this in more detail is available here.

Batch Image Compression Utility

2007-05-09T19:13:00.000-06:00

A few years ago, Electrotank had a project that involved literally hundreds of images that were loaded in dynamically. These images were generated out of a 3D application as single frames with an alpha channel (PNGs). One of the problems we ran into was compression. Re-rendering the huge set of images took many hours and we were never sure how much compression was needed up front.

To that end, I created a tool in C# that can go through a directory tree, take every JPG and PNG image and save it out to another directory tree with a given compression level. Nothing too sexy but useful at times. It also supports dragging and dropping the directories to make it a little easier.

Feel free to use it if it might be useful. You can get the tool here:
http://www.electrotank.com/junk/mike/blog/ImageSquisher.zip

Have fun!

I've Had Enough of Hibernate

2007-05-08T06:14:00.000-06:00

Alright, I know it sounds like sacrilege but I'm fed up with Hibernate. I know it seems to be the Java developers tool of choice when dealing with a database but I've had enough.

I've had misgivings about it before. The number of jars and dependencies makes me cringe every time I see the list. Also, I've always found debugging errors with it to be very cumbersome. Personally, I've never liked it's weird hybrid SQL syntax either. Some people love it, but I've always found it a hassle and never quite got my head around it.

The final straw though was when we tried to integrate it into our newest project. We are using a rather deep set of classloaders to isolate parts of the application and keep things clean. Overall it's working very well. The only real issue we've run into is when we use a framework that has it's own classloader hierarchy. Even then, a little tap dancing around with Thread.currentThread().setContextClassLoader(); has solved the issue.

Until Hibernate that is. For some reason we just can't get Hibernate to work properly in our classloader scenario. CGLib (one of the plethora of jars needed) throws a NoClassDefFound exception. The irritating thing is that right before the call to Hibernate, we can use any of the available classloaders (both current class and thread context) and find the needed class. So somewhere inside of CGLib or Hibernate (or a combination of both) it's doing something screwy and breaking. We know our code works because we can drop Spring (which uses classloaders too) and everything works.

So, after googling classloader issues with Hibernate (and there are a LOT out there) and finally posting on Hibernate forums with no response I gave up. I decided to give iBatis from Apache a try. Wow. I love it. Simple, clean, easy. It has only one required jar for much of the functionality too, always a perk. Even better is that it has the nice Apache 2.0 license which is very corporate friendly. The best part? iBatis solves the whole classloader mess by letting you simply pass in the classloader you want to use when you set it up. It doesn't get any better then that ;)

In the end, I'll still use Hibernate for things (mostly with Spring, which hides some of the hassle) but I think when I need something quick and easy or more control of the SQL I'll be using iBatis from now on.

Patent a Number? Never!

2007-05-05T13:14:00.000-06:00

I don't believe it's possible to patent a number yet that's precisly how lawyers are interpreting the whole HD-DVD key release. I won't go into detail on it here, this article covers it fully:
http://www.macworld.com/weblogs/editors/2007/05/digg/index.php

I'll just add my two cents:
13256278887989457651018865901401704640
and for those of you who prefer it in hex:
09-F9-11-02-9D-74-E3-5B-D8-41-56-C5-63-56-88-C0

This blog has lots of other uses for that number too:
http://www.enigmacurry.com/2007/05/01/my-new-favorite-number-is-being-censored/

Have fun!

Read The Bills Act

2007-05-05T12:51:00.000-06:00

Ha, I stumbled across this while surfing and thought it was too good to pass up:

http://www.downsizedc.org/read_the_laws.shtml

In short, it's a proposal for that ensures that everyone who votes on a law has actually read and hopefully understands it. It's well worth the read. I feel this would really help as it would force, in part, for legislation to be both simpler, cleaner, and more "public". All are very good things.

The Constitution and Bill of Rights are both quite short and to-the-point in addtion to being elegantly phrased. They can be understood without too much difficulty by even school children. At what point did laws get so complicated that people have become unable to easily understand them? If you think laws arn't that bad, take a look at the Patriot Act, a relatively straightforward piece of legislation:
http://fl1.findlaw.com/news.findlaw.com/cnn/docs/terrorism/hr3162.pdf

That single act is 132 pages of dense text and verbiage. I doubt anyone not a lawyer has seen anything that bad since they last read the loan agreement when buying a house. I challenge any layman or average citizen to really dig in and grasp it all.

If you think the Patriot Act looks hard to follow, try the tax code at 10,000 pages!

Beta Testers needed for Docunator - ActionScript Documentation Tool

2007-05-04T20:02:00.000-06:00

We've been working on a pretty slick tool for generating HTML documentation from AS2 or AS3 classes. It is called Docunator and will be commercially available very soon (probably 2 weeks). We need a few beta testers to help us test some real-world code. If interested then contact Jobe at jobe@electrotank.com.

Here are some of the features:

Create a project that saves your settings.
Point to one to many class paths.
Ignore specific packages or classes.
JavaDocs style tag support
Generates docs that look similar to the Flash CS3 AS3 docs (fully customizable with css) by default
Supports totally custom documentation formats via XML templates and a pseudo-scripting language
Cross linking of data types (go class/property/method surfing)
Syntax-highlighted source code optionally included in output
And more!
..other features to come are automatic UML diagrams and command line support

Converting AS2 to AS3 Automatically

2007-05-04T19:29:00.000-06:00

Jobe and I have a big project that involved a huge ActionScript API that needed to be in both AS2 and AS3. To that end, I created a simple little Java tool that rips through a directory structure and does some migration for ya. It's not perfect at all but it does a good job on the fundamental changes (adding packages, Void to void, and others.). It also has some nifty "annotation"-style functions that give you extra functionality if you need it.

Jobe goes into all this in a lot more detail (providing the download, instructions, etc.) on his blog here.

Have fun!

Preventing SQL Injection Attacks

2007-05-02T17:17:00.000-06:00

This is a big post I made a year ago on the FlashKit Games Forum. I'm posting it again here so it won't get lost as it's still reasonably accurate.

This post was created due to a rash of high-score board hacks (not necessarily SQL injection specific) and some general interest in security. That's why the example is based around a high-score board.

-=-

The Problem

SQL Injection is the process by which someone sends a snippet of SQL code in place of a real value and it gets executed. Let's say you have a "Scores" table that looks like this (in column name - data type format):

ScoreId - int (pk), Score - int, Username - varchar, Date - datetime

And lets say you support the ability to load all the scores for a specific person. The SQL for that would look something like this:

select ScoreId, Score, Username, Date from Scores where Username = '#name#'

Assume that #name# is the data coming from the client, just posted in directly. So in practice, the query might look like:

select ScoreId, Score, Username, Date from Scores where Username = 'webgeek'

Now a clever hacker (or a script kiddie with the right tools) will attempt to inject malicious SQL as their name. Something like this:

' or '1' = '1

At first glance, that seems like a silly little snippet but when it gets combined with your original SQL statement, it now does this:

select ScoreId, Score, Username, Date from Scores where Username = '' or '1' = '1'

And presto, they just returned every score in the system. This might cause huge performance problems or not, but it's something you didn't want them to do.

Now for the bigger problems. Based on our existing table and query, the evil hacker can go farther. They could drop your table and thus delete all your high scores:

'; drop table Scores; --

Becomes:

select ScoreId, Score, Username, Date from Scores where Username = ''; drop table Scores; --'

The semi-colon tells the SQL engine that it's the end of a query. Most engines will let you run queries back to back like that. The -- is a comment. So they just commented out your closing ' mark.

And for the best one?

'; update Scores set Username = 'HAXXOR' where ScoreID in (Select top 1 ScoreId from Scores order by Score desc); --

This becomes (Formatted for readability):


select
     ScoreId,
     Score,
     Username,
     Date
from
     Scores
where
     Username = '';

update
     Scores
set
     Username = 'HAXXOR'
where
     ScoreId in
     (
          Select top 1
               ScoreID
          from
               Scores
          order by
               Score desc
     );
--'

The "top 1" command says return only the first record. That's specific to SQL Server and Access but there are equivalent statements for all databases. That query will simply update the highest score in the system with a new username. The name could be a real user and you would never know that your board is being hacked.

SQL Injection attacks can be used like a sledgehammer or a scalpel and they are VERY difficult to track down. A good hacker can take the "email my password" form and update an admin email address with his own, run the form, get the password, and update the email back. Presto, he now has admin access and no one is the wiser.

I won't go into more details on what can be done with SQL injection attacks because this isn't a guide for hackers.

The Solution

Input Validation
This is crucial. Every form on every web application needs server-side validation. This goes for data submitted from Flash to the server as well. Just think of that as a form without an HTML front-end. Validation on the client (Flash or JavaScript) is excellent and should be done but even if you have the greatest client-side validation you MUST also have server-side validation. Remember, the user has the client in their hands. It CAN and WILL be hacked. The server is MUCH harder to hack.

If you know that "username" can't be more then 30 characters then validate the fact that it's <= 30 characters before you think of using it in a query. If it's too long, just throw it out. Many of the sophisticated SQL injection attacks depend upon large SQL statements. If you know "score" should be a number greater then 0 and no more then 5 digits, validate that it's a number and between > 0 and <= 99999. If you validate before you process then you can help limit the type of attack they can do right off. Error Handling/Reporting
This is another crucial step. In many web application frameworks or languages you get pretty error messages to help developers debug properly. These are good things in development but terrible in production. You want to ALWAYS use generic error messages when something goes wrong. Something like "failed to save score" would be good. This will avoid giving the hacker any information they can use to interpret the success or failure of their attacks.

If your application is stable (doesn't break too much) then I suggest going one step farther. Every time an error occurs, have it log that to a file or (even better) send an email with all the pertinent error details. This will help you debug it AND give you a heads up when someone is attempting to crack the application. This practice is used by many development shops out there and always pays off in the end.

Quote Escaping
It is possible to escape quotes and characters in the incoming data to prevent attacks. I DON'T recommend this though as it's a very difficult process to do properly (very database specific). You can't simply make ' become ''. That will NOT prevent attacks as there are many ways to escape and allow quotes in a given database. Sadly, this is just not a good approach to even attempt. It will provide a false sense of security and not make the app any more difficult to hack.

Prepared Statements
Believe it or not, there is a silver bullet (mostly) for SQL Injection attacks. Simply use "Parameterized Statements" (often called "Prepared Statements" as well). A prepared statement is one where you create a query with placeholders for your parameters and you ask the database to simply bind your values to those placeholders. What makes it so nice is that you don't have to worry about the quotes or anything else at all. To use our example from above, here is the parameterized version.

select ScoreId, Score, Username, Date from Scores where Username = ?

When you bind the parameter, the database will automatically quote it as needed. This will escape any invalid characters. The injection examples above will all fail with prepared statements. Additionally, prepared statements are significantly faster for repeat queries as the database internally optimizes them. If you use a prepared statement over and over again you will see a huge performance increase over concatenated string SQL statements (this is assuming you have appropriate statement caching enabled in your connection pool or on the database). This isn't an article on databases so we won't go into detail here.

The language/database you use dictates how you interact with prepared statements. In general it's quite simple. Both Java and .NET have database-neutral techniques that you use so your code is the same for Oracle, DB2, SQL Server, MySQL, etc. PHP has that if you are using Pear DB but not if you are going against MySQL (or other databases) directly without Pear.

Java with any database
http://www.theserverside.com/tt/articles/article.tss?l=Prepared-Statments

.NET with any database
http://msdn.microsoft.com/library/default.asp?url=/library/en-us/vbcon/html/vbconparametersindataadaptercommands.asp

PHP w/Pear DB (database abstraction layer)
http://www.codepoets.co.uk/doc/php_pear_quickstart_database_web_applications

PHP w/MySQL
http://www.webdesignforums.net/archive/index.php/t-18762.html

In lieu of prepared statements, you could also use stored procedures. They are a type of parameterized query. I don't go into them here though as most game developers seem to steer clear of them.

Database Security
No matter how good you are, it's very likely you will make mistakes. The catch-all for these mistakes is to lock down access to the database. In the high score example, the user account accessing the database only needs the ability to run insert and select statements against the "scores" table. If you restrict the account properly then it would be impossible for them to delete the scores table or even update records in the table. The way to do this is to simple create a few new accounts for your application. NEVER use your admin account to the database as the username/password in your applications. This step will dramatically reduce the damage that an enterprising hacker could do even if they do find a vulnerable form.

Dynamic Class Instantiation with Generics

2007-05-01T16:12:00.000-06:00

I've been working on a project that required a great deal of dynamic class instantiation lately and this little piece of code caused me a bit of a headache until I figured it out with the help of Peter Royal from the MINA project.

Normally, you instatiate a class dynamically using something like this:

Class mapClazz = null;
try {
mapClazz = Class.forName("java.util.HashMap");
} catch(Exception e) {
e.printStackTrace();
}
Map map = (Map) mapClazz.newInstance();

All the classloader-ish methods like loadClass, forName, etc. return Class<?> as of 1.5. This little piece of code works fine BUT while this doesn't give you a compiler warning with -Xlint:unchecked enabled, it should.

The problem comes when you actually try to use generics properly in this case. The final solution ends up looking like this:

Class<? extends List> listClazz = null;
try {
Class<?> clazz = Class.forName("java.util.ArrayList");
listClazz = clazz.asSubclass(List.class);
} catch(Exception e) {
e.printStackTrace();
}
List list = listClazz.newInstance();

Notice that you use "? extends" even if it's an interface? You also need to use the asSubclass method to handle the cast. That method takes the place of the explicit cast used in the first example. It's important to note though that the ClassCastException is still thrown if necessary, just from inside that method instead.

Maybe it's just me, but I didn't find this whole thing very intuitive which is why I'm posting it. Maybe now others can find the solution without bugging their friends.

New Electrotank Game

2007-04-30T15:23:00.000-06:00

Electrotank has just finished up a game for MTV. Crowd Magnet is an interesting little game for the show Pimp My Ride. Jobe talks about it in a lot more detail here. Have fun!

Jobe Makar's Blog

2007-04-25T13:55:00.000-06:00

Just a heads up but my good friend and business partner, Jobe Makar, has created a blog here. If you head over there you can read all about his travels in Flash and the seedy underbelly of online commercial game development.

Hello!

2007-04-20T13:50:00.000-06:00

Hello! I've been meaning to create a blog for a long time and figured I might as well get it over with. I plan on using this to post anything I find interesting or fun. In general, it will be Java or Flash code/techniques but sometimes it will be something a bit less geeky. No promises on that ;)