标签: algorithm

Well, things have been bouncing along with regard to my Caveman Diorama since last we spoke (see Caveman Cam ). My chum Mike -- the model railway enthusiast -- and I meet up in my office on Saturdays to work on the cave and other hobby projects.   Take the waterfall and the pool, for example. The image below shows a very early incarnation of this (the two cutout figures are just there to provide a sense of the 1:32 scale we're using).     Actually, now I come to think about it, I really need to write another column to bring you up to date with everything. We recently finished the underlying structure for the cave roof; you will not believe your eyes when you see it.   Since much of this is new to both Mike and me, we're spending a lot of time experimenting with different effects. Take the pool, for example; we've created a series of mockups with various colorings and depths, and we've filled them with clear epoxy to simulate the water. I don’t want to boast, but I think the final version is going to look pretty spectacular.   This past weekend, we added a hidden tri-colored LED under one of the pools to decide if it brought anything to the table. In fact, just having the water dimly glow blue or green turns out to be surprisingly effective. Also, when we add other effects like lightning outside the cave entrance during a storm, we could flicker this LED in time with the lightning to make it look as though the lightning was reflecting off the pool.   In the fullness of time, some cavemen miniatures are going to be sitting around a fire, along with a figure in a Hawaiian shirt representing myself (an H.G. Wells-esque time machine will be seen in one corner of the cave). I'll be lighting this fire with a number of tri-colored LEDs of course.   While I was ruminating on this on the way into work, I started to think about the tunnel feeding the waterfall. We're going to have a couple of Morlock characters with glowing orange eyes hiding on the ledge spying on the scene below. So I started to wonder about having some tri-colored LEDs mounted at the back of the tunnel. I'm thinking of a low red flicker with occasional flares of orange and yellow.   All of which leads me to the point of this column. What sort of algorithm would be best to simulate flickering flames? Should I just mix combinations of random numbers with different amplitudes and periods, or should I overlay my random values on top of a more regular underlying "envelope"? Is there a preferred technique for this sort of thing? If you know anything about this, or just have some ideas of your own, please share them with the rest of us in the comments below.

Happy Friday (or whatever day it happens to be when you read this)! I recently spent a jolly happy weekend programming some new test-pattern lighting effects into my Bodacious Acoustic Diagnostic Astoundingly Superior Spectromatic (BADASS) Display.   As I mentioned in my previous column on this topic -- BADASS Display: It has now come to life! -- my chum Duane Benson has taken the circuit for my original spectrum analyzer breadboard prototype and replicated it as a custom shield. I'm currently waiting for this little rascal to come back from the board shop. In the meantime, as you can see in This Video , I'm having a lot of fun just playing around with different effects.   I have a couple of ideas for additional algorithms that might look rather tasty. For example, I'm thinking of a "raindrops" effect where we pick a column at random and a short trail of white dots falls from top to bottom ending in a "splash." We could have several of these falling at the same time. We could even tie it to the Internet such that this effect automatically comes on whenever it's raining outside.   Another idea is a "fireworks" effect. In this case, we'd pick a column at random and a short trail of white dots would rise from the bottom to some random height, at which point there would be an "explosion" of colored pixels radiating out in different directions. The color and size of each explosion could also be random.   And yet another idea is to have one or more snake-like creatures meandering their way around the pixel array. Ooh! Ooh! Now I come to think about it, what about implementing a version of Conway's Game of Life ? Do you have any ideas for additional effects? If so, it would be great if you could post them in the comments below.   Now, I must admit to being quite proud of myself because I'm a hardware design engineer by trade -- when it comes to programming, I pretty much make things up as I go along; which leads me to the fact that I wouldn’t mind a bit of help in the form of someone who actually knows what they are doing taking a look at my code and offering some advice on how I can make it leaner, meaner, and more efficient.     If you Click Here , you'll be presented with an ASCII text file containing the program running in the video above (in fact there are three "rainbow" effects in this code -- vertical (column-by-column), horizontal (row-by-row), and diagonal -- but I only activated the diagonal version in the video).   Now, I'm using NeoPixel Strips from Adafruit to power my display. In fact, I have 16 strips, each boasting 16 NeoPixel elements, thereby giving me an array of 256 pixels.   On the off-chance you haven't used these little scamps yourself; it might be a good idea for me to explain a couple of things before you start dissecting my code. First we use the following #include statement to access Adafruit's NeoPixel library.   #include   Next, we might a statement like the following to declare (instantiate? I'm not sure what the right word is here) a NeoPixel strip called "strip":   Adafruit_NeoPixel strip = Adafruit_NeoPixel(16, 25,...   The first parameter -- 16 in this example -- specifies the number of NeoPixel elements in the strip. The second parameter -- 25 in this example -- specifies the number of the Arduino's digital output pin we intend to use to drive the strip. We don’t need to worry about any remaining parameters here.   The important thing to note at this stage is that the act of instantiating a NeoPixel strip automatically creates an array in memory. This array has the same number of elements as the number of NeoPixels in our strip -- 16 in our example -- numbered from 0 to 15. Each of these elements has three byte-sized sub-elements, which are used to store that pixel's red, green, and blue (RGB) values. Now consider the following command:   strip.setPixelColor ( 6, 255, 127, 63);   This loads the seventh element of our array in the Arduino's memory with RGB values of 255, 127, and 63, respectively. but it doesn't actually change the values that are currently being displayed. This means that we can happily take our time deciding what values we wish to display and loading them into our array using a series of "strip.setPixelColor()" commands. When we are ready to actually display these values, we use the following command:   strip.show();   This causes the Arduino to stream the RGB values associated with all 16 pixel elements out of the associated pin (the neoPixels forming the strip are daisy-chained together).   OK, returning to My Code , you will see that I've instantiated 16 NeoPixel strips called strip0, strip1, strip2... strip15 as follows:   Adafruit_NeoPixel strip0 = Adafruit_NeoPixel(16, pinsStrips … Adafruit_NeoPixel strip1 = Adafruit_NeoPixel(16, pinsStrips ... Adafruit_NeoPixel strip2 = Adafruit_NeoPixel(16, pinsStrips ...        : Adafruit_NeoPixel strip15 = Adafruit_NeoPixel(16, pinsStrips ...   As you'll see, this makes my lowest-level functions look a tad ungainly, because I have to do things like the following:   strip0.setPixelColor(row,R,G,B); strip1.setPixelColor(row,R,G,B); strip2.setPixelColor(row,R,G,B);        : Strip15.setPixelColor(row,R,G,B);   What I would prefer is to declare my strips in such a way that I could re-write the above code snippet as follows:   for (int i = 0, i 16; i++)   strip .setPixelColor(row,R,G,B);   The problem is that I don't have a clue how to do this. Furthermore, although it seems to me that this new version should end up occupying less space in the Arduino's memory, I do wonder if it might be slower than my current incarnation. Do you have any thoughts on this?   Another big one for me is my diagonal rainbow effect. My pixels are numbered in the lower left-hand corner to in the upper right-hand corner. My 16 x 16 array has 31 diagonal "slices" -- the first has just one element at ; the second has two elements at and ; the third has three elements at , , and ; and so forth. As you'll see in my code, I created a three-dimensional array called "xyDiagCells" to hold these values as global variables.   The problem here is that this has sucked up a lot of my available global variable space. Ideally, I'd like to be able to generate the XY coordinates of the cells forming each diagonal algorithmically, but I'm finding it difficult to wrap my brain around the way in which I might achieve this.   I could go on and on, but I think you get the drift. If you have a moment and you are up for a challenge, I'd love for you to take a look at My Code and offer any advice on how you would improve on it so as to consume less memory and fewer clock cycles. Any suggestions will be very gratefully received.

I have recently been thinking about the future of augmented reality (AR). I really believe this technology is racing toward us faster than most people think.   Just today, for example, my chum Jay Dowling sent me a link to something called iOnRoad , which turns your smartphone into a personal driving assistant that can tell you what you are doing wrong. That will be handy for those times when my wife can't be there to perform this task for me.     This comes as an app that you can download to your iPhone or Android phone. Using the phone's camera, augmented by machine vision algorithms, the iOnRoad app provides a range of personal driving assistance functions, including augmented driving, collision warning, and black box-like video recording.   As per my previous columns, suppose this sort of AR capability -- showing the time gap between you and the car in front -- didn't require a smartphone or a heads-up display on the windscreen. Suppose it were projected directly on to one's retina?   I don't know about you, but I think that having a wealth of AR data available at one's fingertips (or on one's eyeballs) could be an incredible experience. It seems like the sort of thing that you can't imagine when you haven't got it, and that you can't imagine living without once you have it.   When I started writing my first book in 1992, I spent just about every evening and weekend for a year at my local library using the hard-copy Encyclopedia Britannica as my main reference source to check facts like the year George Boole invented Boolean algebra and when he was born and died. This was before the first popular web browser, Mosaic, appeared on the scene and before the vast majority of folks had heard the term "Internet."   Today, we all have unbelievable amounts of information available at our fingertips. While watching House Hunters with my wife, for example, I will use Google Earth on my iPad to get additional information about where our hopeful house hunters are hunting. I would guess that no more than 10 minutes typically passes -- at work or at home -- without my consulting the Internet about something or other. Way back in 1887, in his autobiographical Souvenirs d'Enfance et de Jeunesse , Ernest Renan (1823-1892) famously noted: "The simplest schoolboy is now familiar with facts for which Archimedes would have sacrificed his life." Goodness only knows what Ernest would have said about the information available to us today.   And I think we have only seen the tip of the iceberg. I don't think most of us can conceive of the way things will be in the not-so-distant future.   I do have a question. What happens if we get used to relying on all this stuff, and a disaster like a mega-computer virus brings down all our systems? What will we do if the data stops flowing?

I've just been struggling with a mind-bending conundrum. This is all part of my ongoing Inamorata Prognostication Engine project. I'm currently working on the code to calculate how many days it is until the next full moon, a time that—experience has shown—can be somewhat troublesome with regards to one's Inamorata.   The problem was that my code was producing unexpected results. I was starting to pull my hair out. By yesterday, I was contemplating posting a blog asking for your help. But I was mulling things over in the wee hours of this morning when I thought, "Hang on just a minute. Could it be that...?" It could indeed! The bottom line is that I've tracked down the root of my problem and everything is once again running smoothly in "The House of Max," but for a moment there I thought I was losing my mind. What? You think you could have sorted this out faster than I? Well, let's see, shall we? The remainder of this blog reflects my musings from yesterday, February 20, 2014, before I'd worked out what I was doing wrong... Remember that I'm working with an Arduino, so my float variables have only around 6 to 7 decimal digits of precision. The output from my real time clock shows me that today's date (at the time of this writing) is February 20, 2014. Since today is indeed the February 20, I'm happy so far. I use this date to calculate today's Julian day number and obtain a value of 2456709. I bounce over to the USNO website to confirm that they are in agreement with me and that today does indeed correspond to a Julian day number of 2456709. I'm still smiling. Next, I go to the MoonPhases.Info website and look up the full moon dates for 2014 as illustrated below.   Purely for the sake of a quick test, I use the date of the most recent full moon—February 14, 2014—as my reference point (any full moon in the past 1,000 years would do, so later I intend to replace this reference with something more appropriate, like a full moon that fell on April 1, or one that occurred on the day that something interesting or relevant happened—do you have any suggestions?). But we digress... I enter February 14, 2014 as the date of the reference full moon into my code, which calculates that this corresponds to a Julian day number of 2456703. Since this was only six days ago, and since 2456709 – 2456703 = 6, I think we can safely say that we're still on track. But this is where my smile turns upside down into a frown, because my Arduino now tells me that—after performing some heroic calculations—it has determined that there are 21 days until the next full moon and that the date of that full moon will be March 13, 2014. I would say "Close, but no cigar," except that this is not even particularly close. The actual date, as shown in the image above, should be March 16, 2014, which is 24 days in our future. "Oh dear," I said to myself (or words to that effect). In a moment I'll show you the code I'm using to calculate how many days there are to the next full moon. From there, we can calculate the actual date of the next full moon. But first, let me walk you through the reasoning process I went through to determine what algorithm to use (remember that, as for most things in life, I'm making all of this up as I go along). Purely for the sake of a starting-point example, let's assume that our universe has only been in existence for a little over 100 days. Let's also assume that a full moon occurs every 10 days on the dot—that is, there was full moon on days 10, 20, 30, 40, etc. Let's pick one of these full moons as our reference full moon—say the one that occurred on day 100. Now, let's assume that we are currently on day number 134 in our hypothetical universe. So, the number of days (the "difference" or 'd') between today and our reference full moon is 134—100 = 34. We know that the period ('p') of our moon's orbit is 10 days. What we want to do is to divide the number of days 'd' by the period 'p' and keep the remainder. In computer terms, when performing integer math, we have two types of divide operation available to us: // Standard divide operation; remainder is lost d / p = 34 / 10 = 3 // Modulo divide operation; returns the remainder d % p = 34 % 10 = 4 In our terms, this remainder of 4 equates to 4 days. Thus, since the period of our moon's orbit is 10 days, the number of days to the next full moon is p—4 = 6. Furthermore, since we know that today's number is 134, we therefore know that the next full moon will occur on day 134 + 6 = 140. Tra la! Of course, our test as described above was based on integer math operations. If we had been dealing with real numbers, then d / p = 34 / 10 = 3.4. If we now throw away the integer part of this result to leave a remainder of 0.4, we have to multiply this by the period to obtain the number of days; that is, 0.4 x p = 0.4 x 10 = 4 days. Now, let me show you the code I'm using to generate the number of days to the next full moon and, from there, the actual date of the next full moon. Then we'll see how long it takes you to spot where I went wrong.   I pass my Julian day numbers (both are of type long) as parameters into this function—"jNow" and "jRef" are the Julian day numbers for today and for the day of my reference full moon, respectively. You'll just have to take my word that these values are 2456709 and 2456703 as discussed above. The first thing I do is to declare a variable called 'd' of type long and assign it the result of today's Julian day number minus the Julian day number of my reference full moon. In the case of the example values I'm using, the result is 2456709—2456703 = 6. When I was a kid, I was always told that the Moon took 28 days to orbit the Earth. Of course, I know that this is only an approximation, so I performed a Google Search "How long does it take the moon to orbit the earth?" and received the following response: "The sidereal month is the time it takes to make one complete orbit of the earth with respect to the fixed stars—it is about 27.32 days." The "about" part of this answer raised a small "red flag," so I Googled further and obtained a more accurate value for a sidereal month of 27.321661 days. This is why I declare a float 'p' (for "period") and assign it to a label I defined earlier. Once again, you'll just have to trust me that I did define "siderealMonth" as having a value of 27.321661. Now, I want to get the remainder from dividing the number of days 'd' by the period of the lunar month 'p,' but the modulus ("%") operator doesn't work with floats. The solution is to perform the operation "((d/p)—floor(d/p))." The idea here is that the "floor()" function throws away the remainder from a floating point value. The "(d/p)" operation gives me the full result from the division in the form of both the integer and fractional parts, and from this I subtract the integer part provided by "floor(d/p)," which therefore leaves me with the fractional part; i.e., the remainder. Since I come from the days when a division was a computationally "expensive" operation—and since "((d/p)—floor(d/p))" requires me to perform the division "(d/p)" two times—I decided to pre-calculate this using the "float dDp = (float) d / p;" statement. Obviously I know that this saving is miniscule in the scheme of things, but "old habits die hard," as they say. The rest of the code is pretty much self-explanatory; "(((dDp – floor(dDp)) * p)" is the remainder multiplied by the period, which gives me the number of days since the previous full moon, so subtracting this from 'p' gives me the number of days to the next full moon. Of course, this result is currently stored in the "tmp" variable, which is a float, but I want to cast this (and return it) as an int. The problem is that this casting operation will simply truncate any fractional value, but I would prefer to perform a round operation instead. This explains the reason for my adding 0.5 to the result. As an aside, if you are unsure what I mean, by the previous point, then think of it this way... If I have a float result of 6.x, for example, then casting this to an int will truncate it to 6. This would be OK if my original number was 6.4, but not OK if my original number was 6.6. In this latter case, I would prefer my final value to be 7. The way to achieve this is to add the 0.5. In the case of 6.4 + 0.5 = 6.9, the cast to an int will still truncate this to 6; by comparison, in the case of 6.6 + 0.5 = 7.1, the cast to an int will truncate this to 7, which is what I want. So, returning to the problem at hand, when I run the above function, supplying it with values of 2456709 for today's Julian day number, 2456703 for the Julian day number of my reference full moon, and 27.321661 as the value of the sidereal month, my function returns a value of 21 days to the next full moon. I then use this value to calculate that February 20 + 21 days = March 13. But, as we said, the actual date of the next full moon should be March 16, 2014, which is 24 days in our future. First of all I worked the problem through by hand, but I obtained exactly the same result as my function. On the one hand this made me happy (I hadn't made a stupid coding mistake—you can end up with all sorts of unexpected results if you fail to cast things the right way); on the other hand it made me sad (I still didn't have a clue what was going wrong). By this time I was "clutching at straws," because I started to wonder if there was any chance the creators of the MoonPhases.Info website had made a mistake, so I bounced over to TimeAndDate.com to check out their version of the 2014 calendar . Bummer; they also have full moons occurring on February 14 and March 16 as shown below. My brain hurts.   So, that's where I left things when I retired to my bed yesterday evening. In the wee hours of this morning, I was lying in bed running through things in my mind, dissecting my algorithm operation by operation, trying different test values to see what would happen, and generally getting nowhere fast. And then came the breakthrough; it gradually dawned on me that there was only one place where the error could be originating, and that place was... . So, what do you think? Please post your thoughts in the comments below.  

I recently read an article about something called the EyeWriter Project . This involves an international team that is working together to create a low-cost, open source eye-tracking system that will allow Amyotrophic Lateral Sclerosis (ALS) patients to draw using just their eyes ( Click here to see the full article). This is something that is close to my heart, because one of my very dear friends, Steve Pesto, was a victim of ALS – he shrugged off this mortal coil several years ago now. As an aside, you might be interested in Steve's last joke on me. Throughout most of the year (Spring, Summer, Fall), I am well known for wearing nothing but shorts and Hawaiian shirts – generally speaking I wear the same clothes for home, the office, church, and parties. Of course there are always exceptions to every rule. Thus it was that on the occasion of Steve's funeral I dusted off my black suit and tie (the one I keep for emergencies) and headed off to the ceremony. You can only imagine my surprise when I entered the church and discovered that everyone else was dressed in their brightest, most colourful garments, including many Hawaiian shirts. It seems that Steve had requested that everyone attending the funeral wore their "brightest and best" ... but somehow he and his wife had "neglected" to let me know about this plan. The end result was that the person who never wears a suit was the only person in one, whilst everyone else was sporting my usual attire. As I sat through the ceremony, I could imagine Steve looking at me with his expressive eyes (the only thing he could still move towards the end) twinkling at me. But we digress, one of the things that Steve introduced me to was the Dasher Project ( Click here for more details). This is an information-efficient text-entry interface for wherever a full-size keyboard cannot be used – for example, when operating a computer without using one's hands (this is, by head-mouse or by eye-tracker). For the final year or so, Steve largely communicated by means an eye-tracking camera mounted on top of a notebook computer attached to his wheelchair. Using the camera and Dasher software, Steve could build up words and sentences, which could subsequently be emailed or passed to a speech synthesiser. But sometimes Steve was too fatigued even for this. This is why Steve invented something he called his "Letter Board". This was a sheet of paper, on one side of which was a coloured binary-tree type diagram as shown below:   Steve Pesto's Letter Board   Being an engineer, Steve had based this board on a binary search algorithm that achieves optimum efficiency by utilising the frequency of occurrence of letters in the English language. Assuming the disable person has any motion at all (Steve could blink once for Yes, while the absence of a blink meant No), Steve's letter-board can be used with the caregiver just pointing to letters starting with the most frequently used letters which are at the top. An even more efficient way to use this tool is for the caregiver to call out colours, and then light or dark, and then left or right, and so on. As you may notice, one of the options on this sheet says to "Turn Over" . Printed on the back is another colour-coded binary tree in textual form covering common requirements like adjusting various portions of the body to relieve pain, required medications, and so forth. After you have experimented with this tool for a few minutes, you come to realise just how much thought went into it and also how incredibly useful it can be. Steve really wanted to make his Letter Board available for anyone else to use, so you can Click here to download a compressed ZIP file containing a PDF, which you can print out directly. Also, the ZIP file contains an Excel version that you can customise along with a Word document containing the questions that you print on the back of the Letter Board (which you can also customise). Please pass this information on to anyone you know who is disabled (or to their caregivers).