jeffmcbride.net

I’ve been working on some electronics and software to do precisely timed photography setups. One of the issues I encountered was that I seemed to have a lot of unpredictability in the delay between when I fired the shutter signal and when the shutter opened. I took some measurements to find out what range of shutter lag I needed to account for when calculating trigger times, and once I got setup it quickly became clear that there were two delay modes I was seeing: a short, very predictable delay, and a much longer and much more varied delay. It didn’t take much longer to realize what the difference was between these mode, and that this was what was causing my problems:

The D90 has a very predictable shutter lag; When it is ready to go. When the display is still active showing the image from the previous shot, there is a much longer shutter lag, and it varies a lot. So, when precisely controlled timing is required, you need to make sure the display is off before triggering. This can be done by either waiting for the shooting info display to turn off, or half-pressing the shutter button. In my setup, I wired the half-press and full-press together, because I didn’t think I’d have any reason to command a half-press. In the future, I think I will wire them both to be controlled separately, so that part of the sequence can be to send the half-press command early enough to ready the camera before sending the full-press shutter command.

The Setup

I controlled the camera via the remote shutter cable input. I had both the half-press and full-press wires connected together, so that both were shorted at the same time to the common wire with a FET. I used a microphone to detect the shutter, and connected both the trigger signal and the audio signal from the microphone to an oscilloscope to measure the delay.

The Results

When the display was still on, the shutter delay was around 210 ms. It varied a lot. At least 20 ms, probably more, but to be honest once I figured out what was going on I didn’t really record measurements for this case.

When the display had turned off, the delay was 70.2ms, +/- 0.5ms.

The capture below shows the sequence. The camera was set for 1/5 shutter time, or 20ms. I’m fairly sure that the first long sound is the mirror opening, and then the is a quick sharp sound which is the first shutter blade opening, followed 20ms later by the second shutter blade following it to block the sensor. The time between these two pulses varies as it should with exposure time.

As you can see here, the bulk of the shutter appears to be taken by the mirror movement, which takes around 40ms. It is possible that there is something else going on that the camera would have to wait for anyway, but I have to wonder why they don’t have a mode to hold the mirror open to begin with. Even in live-view, where the mirror is normally up, the D90 closes the mirror when you press the shutter button, then opens it again to take the shot. I’ve no idea why they would do that.

I was playing a this silly flash game last night, when I decided that it was not much fun to play, but I wondered if the right algorithm could keep it going forever, and it shouldn’t be that hard to write an application to play it, right? I figured if I was bored enough to play flash games, I was bored enough to write an application to play flash games for me, and it would probably be more fun. So, I did, and here is where I ended up: Now I have the framework in place to play the game, but my first attempts at algorithms to play them failed miserably.

How

To play the game, I really only needed to do two things:

1. Do a screen grab of the flash app and interpret it into game state
2. Send mouse click events to the flash app

Like most tasks in C#, these were fairly straightforward, with a bit of googling, so I won’t go into details (I used Graphics.CopyFromScreen() for screen grab, and the mouse_event() API call for mouse input). The hardest part, actually, was getting the right screen coordinates to grab from. For this, I created a semi-transparent template form, with some shapes for the bubble positions on it. So, you just put up the template form (which is always on top), position it so it aligns with the flash app, and you’re good to go.  As for screen captures, I capture:

1. A single pixel on each of the “coming up” bubbles at the top-right
2. Four horizontal strips along each play line of bubbles
3. One vertical strip which covers the region the cannon can be in

I use the hue of a pixel to determine which bubble type (if any) it belong to.

Why

Because I was curious, really, and I thought it would be fun to try and find the optimum way to play. The game gives you a preview of the next 7 upcoming bubbles, way more information than a human can process quickly, and I figured if I made use of that I could do much better than the simple rules I could use in my head for playing. Unfortunately, so far, I have been proving myself dead wrong, and the simple heuristic rules, which use only the next color, and are basically how I would play myself, works much better than my other attempts. This is not cool. So, I invite anyone to come up with a better algorithm to play. The code is written in such a way that you just have to create a new class which inherits from  IBubbleAlgorithm, and provides a function to take the current game state as arguments and return the next lane to play on. Alternatively, if you have any ideas, but don’t want to code it, let me know and I may try it myself.

Algorithm 1: The Simple Rule

First, I did what I call the MatchColor Algorithm. It uses only the next bubble color, and pays no attention to the other 6 upcoming colors.

The rules are as follows:

1. If one or more lanes end in two bubbles of the same color as the next bubble to be played, play it on whichever of these lanes is the longest (already contains the most bubbles)
2. Otherwise, if one or  more lanes end in one of the same color bubbles as the next, play it on whichever of these lanes is the longest.
3. Otherwise, play on the shortest lane.

This works surprisingly well, especially when you run it at 10Hz. It is pretty much what I would do myself, but way faster.

Algorithm 2: Most Triplets Search

Next, I figured I would do an exhaustive search of all possible outcomes for the next 7 steps, and find the endpoint which resulted in the most triplets, and choose that branch of the tree for this turn. For each play, there are 4 options, to that leads to 4^7=16,384 possible outcomes to compute. After finding the outcome with the most triplets, work back up the decision tree to whichever lane in the current turn leads to that best case. This worked, surprisingly poorly. For one thing, it was slow, because I did it in a stupid way the first time around. I ended up recreating a lot of data structures for every step through the search, when I really didn’t have to, creating and destroying a lot of objects, which is slow. This will probably work better if I re-code it so it will run at 10Hz like the first algorithm, but I doubt it would be much.

Algorithm 3: Least Bubbles Search

After the second algorithm failed so poorly, I realized that I wasn’t really trying to get the most triplets, I was trying to keep the longest line as short as possible. So, I repeated the search (and re-coded it to use a single state data structure for a big speedup), but this time I found the final outcome with the shortest longest lane. This was a bad idea, because it means that it almost never wants to play on the longest lane, so it fills up the shorter lanes, at the expense of making triplets. So then I re-worked the “fitness” function for each outcome to be <total bubbles in all lanes> + <bubbles in longest lane>, trying to strike a balance. It still didn’t work nearly as well as the first, simple algorithm. Finally, I added a new term in, where I subtracted a 0.3 from the score for each lane that was left with two of the same color on its end (as way to differentiate otherwise equal scores).  No dice.

Final change: I noticed that I often get multiple instances of the same score. At first, I was taking the lowest lane number of these. This seems to lead to a build-up of pieces on the top lanes because they had preferential selection. I changed it so that when two lanes had nearly the same score, the shortest lane was played on. Still no dice.

How To Run It

If you want to try it out, it is kind of fun to watch. If you want to try to come up with your own algorithm, it is pretty easy to add in if you know any C#.

To run it, open the flash game in your browser, and launch the app. First, you have to line up the template. Click on show template to pop-up the template screen, and drag it over until it aligns with the flash app. Unfortunately, the game will go to a pause screen as soon as it loses focus, so I’ve found it is easiest to first do a rough alignment of the template form, then click focus back to the browser window and move it underneath the template for fine alignment. You should see the image capture and color readouts in the “Screen Grab Diagnostics section on the application form. At this point, it is just grabbing data. It won’t try and play until you check the play checkbox. You have to close the template window first, otherwise it will intercept the mouse clicks.

To select the algorith, just use the dropdown combo box. If you want to add a new one, simply create a new class which inherits from IBubbleAlgorithm, and add it to the project. Any class types which inherit from this interface will be automatically found and instantiated, so it will show up as an option the next time you run. Of course, I’ve only tested this on two computers; it will probably fail on yours .

Things to Do

I’ve probably wasted enough time on this, but should I waste more, it could use:

• More validation of the algorithms. I think the control agorithms are running as they should, but it is still possible that it is a bug and not the algorithm at fault for  the poor performance.
• More validation and improved robustness of the screen grabbing. The flash app does a lot of animation, and when playing fast, these animation have not settled and I think sometimes cause bad interpretations of the screen grab.  Except for the new bubbles coming in from the left, I know where I played, so I know how to update line states without the screen grab. This could be used to improve robustness.
• Game simulation. Actually, I don’t care so much about the flash app anymore, and I could test algorithms better and faster by leaving out the flash game and generating my own game states. This would also allow monte carlo style tests of an algorithm.
• A more intelligent, forward looking algorithm that beats he stupid live-only-in-the present one. This has got to be possible.

Download

I’ve zipped up what I’m calling Version 0.1. It includes the Visual Express project, code, and the build executable, which will probably just run on any windows computer (if you trust me enough to run it, that is; if you know me, why would you trust me? And if you don’t, then really, why would you trust me? ).

BubbleLanePlayer_v0.1.zip