DISCLAIMER: This is a rather long post on the topic of random numbers, so …uh, sorry for that.
I want to talk about a couple of interesting things related to randomness and its many nuisances especially when applied to games. But before we get to that I guess I’ll introduce the basic notions for those of you who are not familiar with this whole thing. You can skip the first two sections if you know what a PRNG is, and how it works.
What is Random
Random is commonly defined as “unpredictable“. In general, when we are unable to find a pattern that would allow us to anticipate the outcome or occurrence of an event, we call it “unpredictable” and there’s a chance we will consider the event “random”.
You’ll also hear of “true randomness”, and things like natural atmospheric noise, lightning bolts, or particles falling from the space being used as sources and examples of it. But while we can’t currently predict when and where lightning will hit, events in the universe like electric discharges in clouds are most likely just a massively complicated function of a number of different factors, and not really something that happens with no rhyme or reason. It’s quite possible that if we were able to simulate each particle and sub-particle inside a group of storm clouds and their relevant vicinity, lightning would be trivial to anticipate with accuracy. This makes its “unpredictability” debatable, I guess.
Having said that, let’s not forget that “predictable” and “unpredictable” are relative to an “observer”. What we consider true random events could totally have a logic behind, but what matters is that from our -and our system’s- point of view, they are impossible to predict, and if the machine (or person) is unable to anticipate the occurrence of an event, the definition applies, regardless of the event’s “actual” predictability.
So in a previous post I’ve discussed how to communicate with a custom HID device using libhid and a Raspberry Pi running linux.
This post is a sort of sequel. I’ll talk about some of the issues and nuances I found when working on a more complex (but related) project; In this case a Composite USB Device that I had to implement on a PIC 18F4550 microcontroller.
If you follow me on Twitter, you might have seen this 1 year ago:
Although I think I never ever posted anything after that, I was definitely working on such a tool, focusing particularly on Gameboy Color development (and as you can see I got it working).
So I’m writing a program in C that needs to interact with a custom HID device I built. This program will be running on a Raspberry Pi. This isn’t a massively complicated task but it can be daunting when there’s not a single “barebone” example or tutorial out there on how to do this. So I decided to write this sort of guide in case it may come in handy for anyone (including myself, in a future).
Libhid is an open source library designed on top of libusb to deal with HID devices, so the first step is compiling libhid. I’d say this is relatively straight-forward except for the fact that “as-is”, the library fails to build in the Pi. Luckily the problem is a single line of code in one of the examples (yes, and that prevents the whole library from being compiled and installed).
Ok, so this is probably the last post I’ll make about my Brainfuck-on-Arduino project, basically because it has reached a point where I’ve already tried all the things I wanted to try and I’ve decided that there’s no point in taking it out of the breadboard and build a board for it. At least not for Brainfuck. And I’ll explain why.
The Performance Issue
I previously said that I was expecting the performance to “drop” a bit when reading directly from a SD card instead of the internal RAM, but I was hoping to mitigate that with a sector/block cache similar to the one I wrote for the SPI RAM.
And that’s completely reasonable and actually true. Where I made a mistake however, was in also assuming that doubling the SPI clock would result in a noticeable performance boost. That’s definitely false. Reading a whole 512bytes sector currently takes between 1 and 2 milliseconds at 4Mhz, and RAM access is done at the same speed, so being the RAM pages half the size of the SD sectors it probably takes half that much to get a whole RAM page.
Since we are caching so many bytes in advance, the number of page reads (both from RAM and SD) is not really that high, so even if we were to double the SPI bus speed we will only cut around 1ms from each access. Most programs I’ve tested don’t normally cross the RAM page boundaries nor require more than one SD sector to be stored, so the speedup won’t even be noticeable for most cases. It will be barely 1 or 2 ms, so if we run into performance issues, they are somewhere else. They are NOT in the SPI Bus speed.
DISCLAIMER: Over the course of this post I’ll be dealing with parsing, programming practices, code refactoring, SPI bus oddities, caching techniques,etc. It’s a mixed bag of things and it’s far from being serious analysis on the topic of optimization. Please don’t expect anything particularly smart in this post like branch prediction, overlapping cache windows, partial block reads, etc. This is just a chronicle of sorts, of the things I’ve done over the past few hours to improve the performance of my Brainfuck-on-Arduino interpreter, which was being painfully slow.
So in my previous post you hopefully got a glimpse of my current project: a Brainfuck interpreter running completely on Arduino. Something that I forgot to mention is that all the input/output (for testing purposes) currently happens through a serial connection. I’m using the “Serial Monitor” console that’s part of the Arduino IDE to “talk” with the board and run the code.
I’d also like to point out that I’m using an external 23K256 chip for the Brainfuck data space, This is basically a 32KB RAM IC that is accessed via SPI (Serial Peripheral Interface). This is relevant for some of the optimizations I’ll do next.
Long ago (like… REALLY long ago) I made this program called SpritED, which was basically a humble sprite editor for TI-calc* developers. While it didn’t attain worldwide fame like other programs I made at the time, it was a tiny useful tool for a handful of developers and that was more than enough to make me quite happy. I love to make software that helps people in any way or it’s of any use to other developers.
Since I’m no longer maintaining nor updating SpritED you will find it on Damnsoft’s museum now. The program -however- doesn’t run out of the box on any Windows platform after XP (it actually required an external runtime library even on XP) so it’s bit of a wasted piece of software you would only be able to run on a virtual machine or a very outdated computer.
That was until now…
To my surprise I received a special request today, from one of the oldest users of this software, asking me if it was possible to make SpritED run on newer versions of Windows. According to his report and a quick check I made there was only a single (and very ancient) component missing, no longer available from the MS archives, so I added it to the install script, repacked the whole thing and tested the new setup on my machine aaand…. now SpritED installs and runs perfectly on Windows 7.
Despite being “updated” to install on “modern” machines, I will probably maintain SpritED in the museum because I don’t think I’ll add more functionality or features anytime soon (or if I’ll ever “port it” to newer frameworks) but I’m at ease for the time being because those who still want to use it can actually run the program on their computers now.
I’ll probably update the installer on the ticalc.org site soon, which was probably one of the places that helped people discover SpritED in the first place.
PhoneGap allows you to create apps for a wide range of devices from a single web-based (HTML+CSS+JS) project. Once you code your content in web format (a HTML5 game for instance) PhoneGap creates an app out of it. How is that done? Well, PhoneGap makes a project for your target platform that consists of a native app that launches a webview and loads your web-content there, providing also a JS bridge to some device-specific features (GPS, accelerometers, gallery, etc) creating what’s essentially called a “hybrid” app.