tag:blogger.com,1999:blog-35454765131929786282018-01-17T20:25:51.895-08:00LEGO Mindstorms Projectsdwalton76http://www.blogger.com/profile/01231435969332456287noreply@blogger.comBlogger14125tag:blogger.com,1999:blog-3545476513192978628.post-30102290663244988232017-07-29T19:32:00.001-07:002017-07-29T19:32:50.050-07:00Rubiks Cube SolverLast Thanksgiving I started working on my CraneCuber robot. <br /><br /><div class="separator" style="clear: both; text-align: center;"><iframe width="320" height="266" class="YOUTUBE-iframe-video" data-thumbnail-src="https://i.ytimg.com/vi/3HjKxTlLDLw/0.jpg" src="https://www.youtube.com/embed/3HjKxTlLDLw?feature=player_embedded" frameborder="0" allowfullscreen></iframe></div><br />By January it could solve 2x2x2, 3x3x3, 4x4x4 and 5x5x5 but I was unable to find solvers for anything larger. Only the solvers for 2x2x2 and 3x3x3 can run on something with as little horsepower as an EV3 (300Mhz with 64M of RAM). The <a href="https://github.com/cs0x7f/TPR-4x4x4-Solver">4x4x4 solver</a> can run on a beaglebone black but it takes about 2 minutes to calculate the solution on that platform. The 5x5x5 solver (written by xyzzy, it is not publicly available) takes several gigs of RAM, I have to run it on my laptop and it takes about 50s to find a solution. The search for 6x6x6 and 7x7x7 solvers was a dead end. A few solvers have been written for these larger cubes but none of the code is open source and binaries have never been made available.<br /><br /><h2>Goals</h2>Building a robot that could solve up to a 5x5x5 was pretty cool and I am very appreciative of the solvers that I was able to find and use. The combination of not being able to run all solvers on the EV3 along with the lack of solvers for anything larger than 5x5x5 motivated me to write my own solver. My goals were:<br /><br /><ul><li>open source...I hope that no one else has to reinvent this wheel again. It would be especially nice if I can get others to contribute to it because there are a lot of people out there who know far more than I do about solving Rubik's cubes</li><li>Run on something as small as an EV3</li><li>Produce a solution quickly....telling a room of 4th graders to chill for 2 minutes while the robot figures out the solution is a bit awkward</li><li>Produce a solution that takes some reasonable number of moves. A solver that gives you 400 moves to solve a 4x4x4 would seem kinda silly</li><li>Python Python Python</li></ul><br />If you stop reading before you get to the end (which is very likely) but are interested in the code for the solver it is available at <a href="https://github.com/dwalton76/rubiks-cube-NxNxN-solver">https://github.com/dwalton76/rubiks-cube-NxNxN-solver</a><br /><br /><h2>Problems</h2>I started writing a 4x4x4 solver by following <a href="http://mensinmotus.com/rubik/rubik.html">this guide</a>. I got it working but was disappointed that the solutions it produced where 200+ moves. I then moved on to solving 5x5x5 by following the same guide, I got it working but was again disappointed as my solutions were ~390 moves. The 4x4x4 solver that I used originally could typically solve a cube in about 50 moves and xyzzy's 5x5x5 solver took about 90 moves so my solutions were way way high in terms of move count. I was probably 4 to 6 weeks into this adventure before it dawned on me to actually talk to some people who have done this before and get some ideas on how one writes a solver that produces a solution with a super small number of moves. I was naive in thinking that an algorithm used by a human to solve a cube would do so in an impressively small number of moves.<br /><br />I met two people online who have been a huge help. The first person was Hagin Onyango, Hagin introduced me to the concept of lookup tables. What is a "lookup table" you ask? Let's walk through how to solve a 2x2x2 cube using a lookup table to nail down this key concept.<br /><br /><h2>2x2x2 Lookup Table</h2>Some basics<br /><br /><ul><li>Rubik's cubes have 6 sides, they are labeled U L F R B D. </li><li>Moves in a solution describe which side of the cube to turn and in which direction. U means turn side U one quarter turn clockwise. U' means turn side U one quarter turn counter clockwise. U2 means turn side U two quarter turns (direction does not matter). </li><li>We'll assume a standard color scheme of white on U, green on L, red on F, blue on R, orange on B and yellow on D</li><li>The squares of each cube can be described via their color (red, green, blue, etc) or via the side that they belong to. I always put white on top (side U) so you can just label each white <span style="background-color: white;">square as </span>U, each yellow <span style="background-color: white;">square as </span>D, etc. It takes far fewer characters to describe the state of the cube using ULFRBD than it does using color names so from here on out we'll use the former. </li><li>A cube can be described via a string of characters for each square. The string for a solved 2x2x2 would be UUUULLLLFFFFRRRRBBBBDDDD. </li></ul><br />Now pretend that you had a lot of time on your hands and about 3 million solved 2x2x2 cubes sitting around your house. You pick up the first cube and do a U turn which puts the cube in state UUUUFFLLRRFFBBRRLLBBDDDD. So now whenever you are walking down the street and find a cube that looks like UUUUFFLLRRFFBBRRLLBBDDDD you know that you can do a U' to put it back to solved...presto you have the first entry on your lookup table!! Now repeat this process for moves L, F, R, etc (starting with a solved cube each time) and whenever you find a cube state that isn't in your lookup table you add it along with the inverse of the steps you took to get the cube to that state...we inverse the steps so that you can get from the scrambled state back to the solved state.<br /><br />Now we've done all single move sequences, time to move on to sequences that consist of two moves and then three moves and so on. Eventually we will have added all 3,674,160 possible states for a 2x2x2 cube, to our lookup table along with the steps to get from each state back to solved. In computer science terms we did a breadth first search to find all possible cube states. <br /><br />That my friends is a very basic lookup table. A 2x2x2 solver can simply lookup the cube state in the lookup table to get the solution.<br /><br /><h2>Binary Search </h2>There are 3.6 million entries in our 2x2x2 lookup table, if we were to compare the current cube state vs all 3.6 million entries until we found a match that would take a while. Worst case the entry we are looking for would be the very last one. This would be O(n) for all the computer science geeks reading this.<br /><br />That sounds pretty crappy but alas there is a better way to find the entry we are looking for. If we sort the entries in the lookup table then we can jump to middle of the list and compare that entry vs. the entry we are looking for. If the one we are looking for is "less" than the one in the middle of the file then we know that we need to be looking in the first half of the file...we just eliminated half the file in a single lookup. At this point we can cut the first half of the file in half and figure out if we should be looking in the first quarter of the file or the second quarter. We repeat this process until we find the entry we are looking for. This is called a Binary Search and it is very efficient, it is O(log n).<br /><br />Many Rubik's cube solvers store their lookup tables in a compressed format in a file and load them into memory for fast searching. If you have plenty of memory this is fine but one of my goals was to run on an EV3 with 64M of RAM so I will be storing my looking tables in plain text files where the content is sorted so I can do a binary search. This doesn't take much memory at all because we are simply moving a filehandle around in a file and is fast enough for my needs.<br /><br /><h2>3x3x3</h2>Now we want to solve a 3x3x3 so we just do the same basic thing where we crank through increasingly longer sequences of moves until we have all cube states in our lookup table...that's all we need to do right?? WRONG!! Unfortunately there are 43,252,003,274,489,856,000 (43 quintillion) possible permutations that a 3x3x3 can be in so this is far too large for us to do via a single lookup table. Google threw 35 years of CPU time at solving all 43 quintillion states back in 2010. If Larry Page wants to build a lookup table for 3x3x3 he has the resources to do so but the rest of us do not. Google didn't actually build a lookup table (not to my knowledge at least), they just proved that all 43 quintillion 3x3x3 cube states could be solve in 20 moves or less.<br /><br />Now the good news is the 3x3x3 was invented in 1974 and a lot of really smart people have spent the last 40 years figuring out how to solve it very efficiently. If you google "Rubik's cube kociemba solver" you will find all kinds of papers on how the best 3x3x3 solvers work.<br /><br />Solving the 3x3x3 is a problem that has been solved and there are open source solvers out there, I use <a href="https://github.com/muodov/kociemba">this one</a>.<br /><br /><h2>4x4x4</h2>For all cubes larger than a 3x3x3 we will solve them by "reducing" them down to a 3x3x3 by<br /><br /><ul><li>solving all of the centers</li><li>pairing all of the edges</li></ul><br />At this point in the journey I felt like I understood lookup tables fairly well so I started building a lookup table that would solve the centers of a 4x4x4. I let my lookup table builder code run for a few days but it still wasn't finished and didn't appear to be anywhere close to finished (it was still adding new entries like crazy). I started wondering just how large of a lookup table this would be. Remember earlier I said that I met two people who were a huge help in teaching me how folks typically write solvers? This is where the second person, xyzzy, a math major who wrote the initial 5x5x5 solver I used, comes into the picture. xyzzy taught me all kinds of things and one of the big ones was how to calculate how many entries will be in a lookup table.<br /><br />Assume you have 12 marbles that are each a different color, how many ways can you arrange those 12 marbles? The answer is 12! or 479,001,600 which is a pretty big number given only 12 marbles. Now what if you had 4 red, 4 green and 4 blue marbles, how many different ways could you arrange those? The formula for that is 12!/(4! * 4! * 4!) or 34,650.<br /><br /><h3>4x4x4 Centers</h3>A 4x4x4 cube has 6 sides with 4 centers per side so my lookup table was going to have 24!/(4! * 4! * 4! * 4! * 4! * 4!) or 3,246,670,537,109,999 entries!!! That is one great big number :( I knew how many entries I was adding to my table per hour so I did some calculations to figure out how long it was going to take...3700 years :( That is more than 4x longer than Yoda lived, that's a really long time. I promptly walked over to my computer and hit ctrl-C on my builder.<br /><br />I needed to break down solving 4x4x4 centers into some smaller problems whose lookup tables are much much smaller. I tried a few different approaches and settled on:<br /><br /><ul><li>stage the UD centers to either sides U or D. This table will have 24!/(8! * 16!) or 735,741 entries, that is much more manageable. To build the "stage UD centers" table we take a solved cube and</li><ul><li>change all of the D centers to a U</li><li>change all of the LFRB centers to an "x". For me x means I don't care about that square. </li><li>walk through increasingly longer sequences of moves until we have added all 735,741 possible states </li></ul><li>stage the LR centers to either sides L or R. This it turn stages the FB centers to sides F or B. While staging the LR centers you must make sure to not not unstage the UD centers...more on this later. The "stage LR centers" table will have 16!/(8! * 8!) or 12,870 entries. </li></ul><br />Building the "stage LR centers" is a very similar process to what we did to build the "stage UD centers" table with the added restriction that we cannot undo the UD centers that we just staged. When building the lookup table we must avoid all moves that destroy the UD centers, those moves are Rw, Rw', Lw, Lw', Fw, Fw', Bw, and Bw, all other moves are fair game. The w in those moves means "wide", this is the notation used to describe turning more than one layer of a cube. So Rw means turn the two layers on side R one quarter turn clockwise. Later when we get to 6x6x6 cubes you'll see moves like 3Rw which means turn the three layers on side R one quarter turn clockwise.<br /><br />We have now "staged" all centers, to solve them our lookup table will be (8!/(4! * 4!))^3 or 343,000. We must further restrict the moves that are allowed when building the table to solve the staged centers because we do not want to undo the "stage LR centers" work that we just did. We add moves Uw, Uw', Dw, and Dw' to the list of moves we are no longer allowed to use. Adding more moves to the list of restricted moves is how a new lookup table avoids undoing the work done by previous lookup tables.<br /><br />I should mention now that all of the code used to build these lookup tables is available at <a href="https://github.com/dwalton76/rubiks-cube-lookup-tables">https://github.com/dwalton76/rubiks-cube-lookup-tables</a> . It can take quite a while to build them all though so I checked all of the tables in to the <a href="https://github.com/dwalton76/rubiks-cube-NxNxN-solver">https://github.com/dwalton76/rubiks-cube-NxNxN-solver</a> repository to save users the hassle of building them.<br /><br /><h3>4x4x4 Centers Example</h3>We start with the following scrambled 4x4x4 cube<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-cEkPwQ4f5o4/WX0CHXrv2CI/AAAAAAAABQ0/mMOXJjA7Az4im8ZNil76Dnk3hNhfJ3PAACEwYBhgL/s1600/444-pic1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="207" data-original-width="253" src="https://1.bp.blogspot.com/-cEkPwQ4f5o4/WX0CHXrv2CI/AAAAAAAABQ0/mMOXJjA7Az4im8ZNil76Dnk3hNhfJ3PAACEwYBhgL/s1600/444-pic1.png" /></a></div><br /><br />We do not care about the corners or edges for now to lets x those out to make things a little easier to visualize<br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-rkMcpr5wgjg/WX0CZo8M88I/AAAAAAAABQ4/nQTCAJFEDqoqeRrMaNWcwmcNmUma9Tc5wCEwYBhgL/s1600/444-pic2.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="217" data-original-width="253" src="https://1.bp.blogspot.com/-rkMcpr5wgjg/WX0CZo8M88I/AAAAAAAABQ4/nQTCAJFEDqoqeRrMaNWcwmcNmUma9Tc5wCEwYBhgL/s1600/444-pic2.png" /></a></div><br /><br />The first thing we want to do is put the UD centers on sides U or D. We take the current state of the centers and find the line in lookup-table-4x4x4-step01-UD-centers-stage.txt for the centers state (we used binary search) that tells us what moves to use to go from our current state to having all UD squares on sides U or D. After performing those moves we have<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-FDkxvT7XGBo/WX0p5ekoXCI/AAAAAAAABR0/j2U4Ci70SJkP0Go_a7zeA05Lq5cwE0qvwCLcBGAs/s1600/444-pic3.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="214" data-original-width="251" src="https://4.bp.blogspot.com/-FDkxvT7XGBo/WX0p5ekoXCI/AAAAAAAABR0/j2U4Ci70SJkP0Go_a7zeA05Lq5cwE0qvwCLcBGAs/s1600/444-pic3.png" /></a></div><br /><br />UD centers are staged to sides U or D, now we need to do the same for the LR centers and FB centers. When we stage the LR centers it will in turn stage the FB centers. We lookup the current state of our centers in our lookup-table-4x4x4-step02-LR-centers-stage.txt table, perform the moves listed and now we have<br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-0B0yMFejXOI/WX0DxesEYCI/AAAAAAAABRA/rQrs_F20_-w3C7JC3qHvUmcSkqvODkulQCEwYBhgL/s1600/444-pic4.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="217" data-original-width="254" src="https://2.bp.blogspot.com/-0B0yMFejXOI/WX0DxesEYCI/AAAAAAAABRA/rQrs_F20_-w3C7JC3qHvUmcSkqvODkulQCEwYBhgL/s1600/444-pic4.png" /></a></div><br />We have now staged all of the centers so now we can lookup the current state of our centers in lookup-table-4x4x4-step03-ULFRBD-centers-solve.txt and perform those moves to solve the centers:<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-Jwt4Wc51o_g/WX0EFVRmnDI/AAAAAAAABRE/XnPXkBdj1Pgrooi4xRcYHRHfECwUGexdQCEwYBhgL/s1600/444-pic5.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="211" data-original-width="256" src="https://4.bp.blogspot.com/-Jwt4Wc51o_g/WX0EFVRmnDI/AAAAAAAABRE/XnPXkBdj1Pgrooi4xRcYHRHfECwUGexdQCEwYBhgL/s1600/444-pic5.png" /></a></div><br /><br /><h3>4x4x4 Pairing edges</h3>Pairing edges is tricky, I have yet to find a good way to build a lookup table for doing so that doesn't destroy the centers we just solved. The way I pair the edges is to try to pair three on a Uw "slice forward", move those out of the way and pair three more on a Uw' "slice back". When we slice back we restore the centers. Hopefully we do this sequence twice to pair all 12 edges but it doesn't always work out that way. A good rule of thumb is that once you have solved the centers it takes 2 1/2 moves to pair an edge.<br /><br />So in a nutshell lookup tables are not used for pairing edges, the solver pairs edges much like a human would do.<br /><br /><h3>4x4x4 Edges Example</h3>Continuing with our example, our cube now looks like<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-6AoCl8oLXio/WX0F7ZTbJpI/AAAAAAAABRI/AM9MGek_-Bc8pF9fAOqS04N8nxYgmx56wCEwYBhgL/s1600/444-pic6.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="215" data-original-width="255" src="https://1.bp.blogspot.com/-6AoCl8oLXio/WX0F7ZTbJpI/AAAAAAAABRI/AM9MGek_-Bc8pF9fAOqS04N8nxYgmx56wCEwYBhgL/s1600/444-pic6.png" /></a></div><br /><br />Once we have paired all of the edges we have<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-fiqUKQKMeRs/WX0GJF2XuiI/AAAAAAAABRM/FEwVBmR5BfYKp8fmqjaSkhnIphLreIbuACEwYBhgL/s1600/444-pic7.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="222" data-original-width="255" src="https://3.bp.blogspot.com/-fiqUKQKMeRs/WX0GJF2XuiI/AAAAAAAABRM/FEwVBmR5BfYKp8fmqjaSkhnIphLreIbuACEwYBhgL/s1600/444-pic7.png" /></a></div><br /><h3>4x4x4 Reduced to 3x3x3</h3>Now our 4x4x4 looks like this<br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-OH56Ux9fTiQ/WX0H1sNpNmI/AAAAAAAABRQ/_RwAxKxFJF0cWcKoKG0c3phkPSexnR3QACEwYBhgL/s1600/444-pic8.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="212" data-original-width="252" src="https://2.bp.blogspot.com/-OH56Ux9fTiQ/WX0H1sNpNmI/AAAAAAAABRQ/_RwAxKxFJF0cWcKoKG0c3phkPSexnR3QACEwYBhgL/s1600/444-pic8.png" /></a></div><br /><br />It can been reduced to the following 3x3x3<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/--xdS7vGYfCA/WX0IEnwDfMI/AAAAAAAABRU/fRUUYrgoiSQNR8i-fWMgH3yELmKO7Z4bQCEwYBhgL/s1600/444-pic9.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="173" data-original-width="198" src="https://1.bp.blogspot.com/--xdS7vGYfCA/WX0IEnwDfMI/AAAAAAAABRU/fRUUYrgoiSQNR8i-fWMgH3yELmKO7Z4bQCEwYBhgL/s1600/444-pic9.png" /></a></div><br />We use the kociemba 3x3x3 solver to compute the solution for the 3x3x3 above which gives us the remaining moves needed to solve the 4x4x4.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-cRIbmxgbCWU/WX0ISYpfgtI/AAAAAAAABRY/lbE5Wxc-LiIMjlwgm9BcacimOAJ9O_5OACEwYBhgL/s1600/444-pic10.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="228" data-original-width="249" src="https://1.bp.blogspot.com/-cRIbmxgbCWU/WX0ISYpfgtI/AAAAAAAABRY/lbE5Wxc-LiIMjlwgm9BcacimOAJ9O_5OACEwYBhgL/s1600/444-pic10.png" /></a></div><br />This cube took 59 moves to solve<br /><br /><ul><li>17 steps to solve centers</li><li>25 steps to group edges</li><li>17 steps to solve 3x3x3</li></ul><br /><br /><h2>5x5x5 Centers</h2>We want to use the same basic strategy for solving the centers of a 5x5x5 so let's calculate how large the lookup table will be for staging the UD centers. A 5x5x5 has 9 center squares per side but the one in the center doesn't move so we can ignore that one. The remaining 8 can be divided into two groups of four:<br /><br /><ul><li>"T-centers" are the ones that are directly above, below, left and right of the center squares. They form a T shape thus the name</li><li>"X-centers" are the remaining four squares, they form a X shape thus the name</li></ul><br />We divide them into groups because a T-center square and a X-center square can never trade places. That means that there will be (24!/(8! * 16!))^2 or ~540 billion entries in a table to stage all UD squares to sides U or D, that would be a huge table and would take a long time to build.<br /><br />What we can do though is build part of that table and then use this cool algorithm called IDA* (<a href="https://en.wikipedia.org/wiki/Iterative_deepening_A*">Iterative Deepening A*</a>) to find a sequence of moves that will take our scrambled cube to a cube state that is in the partial lookup table for UD staging. More on IDA* in a minute.<br /><br class="Apple-interchange-newline" />Once UD centers are staged we need to stage LR centers. The lookup table for staging LR centers (which also stages FB centers) will be (16!/(8! * 8!))^2 or 165,636,900 entries. Solving all of our staged centers will be (8!/(4! * 4!))^6 or 117,649,000,000 which is too large so instead we will<br /><br /><ul><li>solve UD centers which is (8!/(4! * 4!))^2 or 4,900</li><li>solve LFRB centers which is (8!/(4! * 4!))^4 or 24,010,000</li></ul><br />Woohoo we have solved the centers of a 5x5x5!!<br /><h2>IDA*</h2>So how does IDA* work? We started building the lookup table for staging the 5x5x5 UD centers but stopped long before we built all 540 billion entries, we only built the table 6 moves deep which resulted in 17 million entries. Our goal is to find a sequence of moves that will take the current cube to a state that is one of the 17 million states in that lookup table. How can we do that? Well one way would be pure brute force, just start cranking through longer and longer sequences of moves until we happen to find a sequence that puts the cube in one of those 17 million states. That would work but would be really really slow.<br /><br />We need a way to explore longer and longer sequences of moves but without exploring ALL of them,. We need a way to prune off branches of moves that are taking the cube away from those 17 million states instead of towards them. IDA* gives us a way to do this. With IDA initially you say "I am willing to explore branches of moves where the estimated cost to solve UD centers is 1 move". If you don't find a solution then you increase your threshold to 2 moves, then 3 moves, etc, etc until your threshold is high enough that you can find a solution. That is the "Iterative" part of IDA.<br /><br />Let's talk about the "estimated cost to solve UD centers" component since this is what we are comparing against this increasing threshold. This estimated cost consist of two things<br /><br /><ul><li>The number of moves we have made so far, basically this is how many levels deep we are on the current branch of moves. This is easy to compute.</li><li>The estimated number of moves to reach the solved state, in this case the solved state is "UD centers on sides U or D". This is less easy to compute....how the heck do we estimate how many moves it will take us to reach our goal?</li></ul><br />What if we knew how many steps it would take to solve just the UD T-centers? What if we knew how many steps it would take to solve just the UD X-centers? Each of those lookup tables only has 735,471 entries so those are easy to build. So for any cube state we can lookup just the UD T-centers and know how many moves it will take to solve them and the same for X-centers. Whichever would take the most moves is our "estimate" for the number of moves to go from the current state to our goal state of UD centers on sides U or D. The UD T-centers and UD X-centers tables are known as "prune tables" because they allow us to prune off branches of moves that are taking us in the wrong direction.<br /><br />That is IDA* in a nutshell...hopefully that made a little bit of sense.<br /><br /><h2>5x5x5 Edge Pairing</h2>Just like with 4x4x4 edge pairing, I do not use lookup tables for 5x5x5 edge pairing, instead I pair edges the same way a human might do. I attempt to pair three edges on a 3Uw slice forward and three more on a 3Uw' slice back. The last two edges of a 5x5x5 can be a little ugly, luckily someone put together a cheat sheet for the various states of the last two edges<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://i.imgur.com/wsTqj.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="406" data-original-width="800" height="324" src="https://i.imgur.com/wsTqj.png" width="640" /></a></div><br /><h2>6x6x6 Centers</h2>Staging the UD centers for a 6x6x6 has too many permutations for us to use IDA, there are (24!/(8! * 16!))^4 or 292,591,841,163,066,669,769,281 permutations. Our prune tables would be 24!/(8! * 16!) or 735,741 which divided by 292,591,841,163,066,669,769,281 is only 0.000000000000000002515. The prune tables need to be a much larger percentage of the total size of the table in order for IDA* to work in a reasonable amount of time.<br /><br />Instead what we must do is reduce our 6x6x6 centers so they look like 5x5x5 centers so that we can use our 5x5x5 solver to stage our 6x6x6 centers. IDA and prune tables are used to reduce the 6x6x6 centers to look like 5x5x5 centers:<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-_J4PrppRqoA/WX0Ppj-IbLI/AAAAAAAABRg/A07g6-Rx1yMRkFBs1G4IpEGc48Y54YBbwCEwYBhgL/s1600/666-pic1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="293" data-original-width="366" height="256" src="https://2.bp.blogspot.com/-_J4PrppRqoA/WX0Ppj-IbLI/AAAAAAAABRg/A07g6-Rx1yMRkFBs1G4IpEGc48Y54YBbwCEwYBhgL/s320/666-pic1.png" width="320" /></a></div><br /><br />Where the following is the equivalent 5x5x5 cube, we use this cube with the 5x5x5 solver to find the moves to solve the centers of the 6x6x6.<br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-Gsxs41LDI_E/WX0QK-zrRJI/AAAAAAAABRo/4iozzLsu2fkXT1EeSJ53Oaw6UF1l5SnRgCEwYBhgL/s1600/666-pic3.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="252" data-original-width="313" src="https://4.bp.blogspot.com/-Gsxs41LDI_E/WX0QK-zrRJI/AAAAAAAABRo/4iozzLsu2fkXT1EeSJ53Oaw6UF1l5SnRgCEwYBhgL/s1600/666-pic3.png" /></a></div><br /> And now our 6x6x6 centers are solved<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-uQadQmr1HIw/WX0P1zkTwpI/AAAAAAAABRk/d7vXY0nfZ24iz9y_l16Ekj1axJxyZOGygCEwYBhgL/s1600/666-pic2.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="298" data-original-width="365" height="261" src="https://3.bp.blogspot.com/-uQadQmr1HIw/WX0P1zkTwpI/AAAAAAAABRk/d7vXY0nfZ24iz9y_l16Ekj1axJxyZOGygCEwYBhgL/s320/666-pic2.png" width="320" /></a></div><br />The practice of taking some subset of the current cube and producing a smaller cube from it so we can use the solver already written for the smaller cube is a strategy that is used a lot for the 6x6x6 and 7x7x7 solvers.<br /><br /><h2>6x6x6 Edge Pairing</h2>Very little new code is needed to pair the edges of a 6x6x6, we take the inner "orbit" of squares on each edge to create a 4x4x4 cube and use the 4x4x4 solver to generate the solution for pairing these edges. We can then do the same basic thing for the outer "orbit" but this time we reduce to a 5x5x5 and use the 5x5x5 edge solver, we do this by treating each inner paired "orbit" as a single square.<br /><br /><h2>7x7x7</h2>Solving the centers and edges for a 7x7x7 is more of the same strategies discussed above. There is lots of IDA and lots of reducing parts of the cube down to some smaller cube to use the solver of the smaller cube. There are many steps to solving the 7x7x7 and this blog post is already pretty long so I won't go in depth on 7x7x7. If you are curious as to what the steps are take a look at the 7x7x7 code <a href="https://github.com/dwalton76/rubiks-cube-NxNxN-solver/blob/master/rubikscubennnsolver/RubiksCube777.py#L833">here</a>.<br /><br /><h2>NxNxN</h2>In theory once you have the lookup tables needed to solve up to a 7x7x7 you do not need to build any more lookup tables to solve 8x8x8 and larger. I have started working on making the solver NxNxN capable, meaning it can solve any size cube, but this work is not complete yet.<br /><br /><h2>Final Stats</h2><div><ul><li>2x2x2 average solution is 9 moves</li><li>3x3x3 uses the kociemba solver, 20 moves on average</li><li>4x4x4 average solution is 65 moves</li><li>5x5x5 average solution is 119 moves</li><li>6x6x6 average solution is 214 moves</li><li>7x7x7 average solution is 304 moves</li></ul></div><h2>Conclusion</h2>It ended up taking me about 5 months to write my solver. I had no idea it would take me that long when I started, I'm not sure I would have tackled it had I known what I was in for :) I don't give up easily though so I kept chugging along and finally got it all working.<br /><br />In the beginning I spent a lot of time learning what not to do, which I guess is normal when you are jumping into something you know nothing about. I also spent a lot of time experimenting with different lookup tables to solve various phases of the cube in different ways. I wanted the lookup tables to be small enough to check into github, github restricts files to a max size of 100M and the repository has to be under 1G. So a lot of work went into finding strategies that worked AND resulted in lookup tables that were under 100M. There are about 700M of gzipped lookup tables in the repository.<br /><br />There is a thread at <a href="https://www.speedsolving.com/forum/threads/5x5x5-6x6x6-7x7x7-or-nxnxn-solvers.63592/">https://www.speedsolving.com/forum/threads/5x5x5-6x6x6-7x7x7-or-nxnxn-solvers.63592/</a> where I first posted looking for large cube solvers. The thread shows my solver evolve over several months as I got more and more working.<br /><br />I learned a ton working on this project, I had never heard of IDA* and it felt downright magical when I first got it going. It was also interesting to see just how many people have worked on solving rubiks cubes over the years and all the cool strategies they have come up with to solve them in fewer and fewer moves. This is especially true for 3x3x3 solvers, the algorithms for solving it have been getting better and better for several decades.<br /><br /><br /><br /><br /><br /><br /><br /><br />dwalton76http://www.blogger.com/profile/01231435969332456287noreply@blogger.com4tag:blogger.com,1999:blog-3545476513192978628.post-69104904290833820792017-02-15T21:17:00.000-08:002017-02-15T21:17:01.564-08:00Rubiks Cube Tracker using OpenCVI've been working on my own Rubiks Cube solver for the past few months, it is a mashup of the <a href="http://brickset.com/sets/42009-1/Mobile-Crane-MK-II">Lego 42009 Mobile-Crane-MK-II</a> and an <a href="http://brickset.com/sets/31313-1/Mindstorms-EV3">EV3 Mindstorms</a> and can solve from 2x2x2 up to 5x5x5. The robot is called CraneCuber, it uses a USB webcam to see the cube and extract the colors for each square. I'll do a post on CraneCuber soon but I wanted to do a separate post about what is involved with finding a rubiks cube in an image and extracting the colors.<br /><br />Here is a quick video showing all this in action.<br /><br /><div class="separator" style="clear: both; text-align: center;"><iframe width="320" height="266" class="YOUTUBE-iframe-video" data-thumbnail-src="https://i.ytimg.com/vi/3tWnl9rLnfE/0.jpg" src="https://www.youtube.com/embed/3tWnl9rLnfE?feature=player_embedded" frameborder="0" allowfullscreen></iframe></div><br /><h2>Cube Location</h2><div>The robot uses a webcam to take a picture of each side, we'll focus on this photo of a 4x4x4 cube. I use python opencv2 for all of the image processing.</div><div><br /></div><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-_msPVbg-0B8/WKUXVlb1z6I/AAAAAAAABM8/7u26VMqlgzcw6M9iHEaFEi71loy7eD9EQCLcB/s1600/rubiks-side-F.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="240" src="https://2.bp.blogspot.com/-_msPVbg-0B8/WKUXVlb1z6I/AAAAAAAABM8/7u26VMqlgzcw6M9iHEaFEi71loy7eD9EQCLcB/s320/rubiks-side-F.png" width="320" /></a></div><div class="separator" style="clear: both; text-align: center;"><br /></div><h3 style="clear: both; text-align: left;">Canny Edge Detection</h3><div class="separator" style="clear: both; text-align: left;">The first steps are to load the image, gray it, blur it a little and then use Canny edge detection to locate all of the edges.</div><div class="separator" style="clear: both; text-align: left;"><br /></div><div class="separator" style="clear: both; text-align: left;"><span style="font-family: Courier New, Courier, monospace;"> self.image = cv2.imread(filename)</span></div><div class="separator" style="clear: both; text-align: left;"><span style="font-family: Courier New, Courier, monospace;"> gray = cv2.cvtColor(self.image, cv2.COLOR_BGR2GRAY)</span></div><div class="separator" style="clear: both; text-align: left;"><span style="font-family: Courier New, Courier, monospace;"> blurred = cv2.GaussianBlur(gray, (3, 3), 0)</span></div><div class="separator" style="clear: both; text-align: left;"><span style="font-family: Courier New, Courier, monospace;"> canny = cv2.Canny(blurred, 20, 40)</span></div><br /><table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody><tr><td style="text-align: center;"><a href="https://2.bp.blogspot.com/-iarvnVgZdiE/WKUXILysYRI/AAAAAAAABNA/wkSh39kFD_wmscb-a8y2xBbLiP9ThbNeQCEw/s1600/rubiks-10-canny.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" src="https://2.bp.blogspot.com/-iarvnVgZdiE/WKUXILysYRI/AAAAAAAABNA/wkSh39kFD_wmscb-a8y2xBbLiP9ThbNeQCEw/s1600/rubiks-10-canny.png" /></a></td></tr><tr><td class="tr-caption" style="text-align: center;">Canny Edges</td></tr></tbody></table><h3>Dilate</h3>The next step is to dilate the lines a little, this makes the lines thicker which will make it easier to find the contours of the squares.<br /><br /><span style="font-family: Courier New, Courier, monospace;"> kernel = np.ones((3,3), np.uint8)</span><br /><span style="font-family: Courier New, Courier, monospace;"> dilated = cv2.dilate(canny, kernel, iterations=2)</span><br /><span style="font-family: Courier New, Courier, monospace;"><br /></span><table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody><tr><td style="text-align: center;"><a href="https://3.bp.blogspot.com/-TA94FHg-aHM/WKUXIBnTNrI/AAAAAAAABNA/Czj4pgFcXNUzS4aUR7UB6MSpFBjuZG7KACEw/s1600/rubiks-20-dilate.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" src="https://3.bp.blogspot.com/-TA94FHg-aHM/WKUXIBnTNrI/AAAAAAAABNA/Czj4pgFcXNUzS4aUR7UB6MSpFBjuZG7KACEw/s1600/rubiks-20-dilate.png" /></a></td></tr><tr><td class="tr-caption" style="text-align: center;">Dilated Canny Edges</td></tr></tbody></table><h3>Contours</h3>At this point we have a black and white image with nice thick lines around each square. opencv has the ability to find all of the contours in an image where a contour is defined as "<i>a curve joining all the continuous points (along the boundary), having same color or intensity</i>". <br /><span style="font-family: Courier New, Courier, monospace;"><br /></span><span style="font-family: Courier New, Courier, monospace;">(contours, hierarchy) = cv2.findContours(dilated.copy(), </span><br /><span style="font-family: Courier New, Courier, monospace;"> cv2.RETR_TREE,</span><br /><span style="font-family: Courier New, Courier, monospace;"> cv2.CHAIN_APPROX_SIMPLE)</span><br /><span style="background-color: white; font-size: 14px;"><span style="font-family: Helvetica, Segoe UI, Arial, freesans, sans-serif;"><br /></span></span><table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody><tr><td style="text-align: center;"><a href="https://4.bp.blogspot.com/-77Hj2a2TVM4/WKUXIJOGeRI/AAAAAAAABNA/BkwWunasj_wO-cyQgRRxzyHThUFIHfXgwCEw/s1600/rubiks-30-contours.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" src="https://4.bp.blogspot.com/-77Hj2a2TVM4/WKUXIJOGeRI/AAAAAAAABNA/BkwWunasj_wO-cyQgRRxzyHThUFIHfXgwCEw/s1600/rubiks-30-contours.png" /></a></td></tr><tr><td class="tr-caption" style="text-align: center;">Contours<br /></td></tr></tbody></table><h3>Contour Approximations</h3>It looks like someone spilled a plate of blue spaghetti noodles all over the cube doesn't it? We need to reduce the complexity of the shapes of the contours. We can do this via opencv's approxPolyDP which in a nutshell approximates the shape of a contour. In the image below the contours are again in blue but their approximations are in red.<br /><br /><table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody><tr><td style="text-align: center;"><a href="https://2.bp.blogspot.com/-coDD7w5OKIg/WKUXIu79JRI/AAAAAAAABNA/vPdIQS96UasCmAkBb8tPy8RyaIw6zwRIACEw/s1600/rubiks-40.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" src="https://2.bp.blogspot.com/-coDD7w5OKIg/WKUXIu79JRI/AAAAAAAABNA/vPdIQS96UasCmAkBb8tPy8RyaIw6zwRIACEw/s1600/rubiks-40.png" /></a></td></tr><tr><td class="tr-caption" style="text-align: center;">Contours (blue) with approximations (red)</td></tr></tbody></table><h3>Square Contour Approximations</h3><div>The approximations look much easier to work with in terms of figuring out which ones are squares. We look at each approximation and use the following three rules to determine if it is a square:</div><ul><li>There must be four corners</li><li>All four lines must be roughly the same length</li><li>All four corners must be roughly 90 degrees</li></ul><div>In the image below the contour is green instead of blue if the approximation for that contour satisfies our rules for being a square.</div><br /><span style="font-family: Helvetica, Segoe UI, Arial, freesans, sans-serif;"><span style="background-color: white; font-size: 14px;"></span></span><br /><table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody><tr><td style="text-align: center;"><a href="https://3.bp.blogspot.com/-AVKR0ZC9PL4/WKUXIi7lBKI/AAAAAAAABNA/gqIuwmvykmwt-QfJ70aievZEWoEZaUfuACEw/s1600/rubiks-50-contours-with-approx.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" src="https://3.bp.blogspot.com/-AVKR0ZC9PL4/WKUXIi7lBKI/AAAAAAAABNA/gqIuwmvykmwt-QfJ70aievZEWoEZaUfuACEw/s1600/rubiks-50-contours-with-approx.png" /></a></td></tr><tr><td class="tr-caption" style="text-align: center;">Contours with square approximations are green</td></tr></tbody></table><div><br /></div><div>At this point we can eliminate all of the contours that are not squares, that cleans things up a lot</div><div><br /></div><table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody><tr><td style="text-align: center;"><a href="https://1.bp.blogspot.com/-Ebif7Vo5L0Y/WKUXIr3uGcI/AAAAAAAABNA/aopHGHX63UgQIDiw1h3jfIk3pLjKRQXrgCEw/s1600/rubiks-60-non-squares-removed.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" src="https://1.bp.blogspot.com/-Ebif7Vo5L0Y/WKUXIr3uGcI/AAAAAAAABNA/aopHGHX63UgQIDiw1h3jfIk3pLjKRQXrgCEw/s1600/rubiks-60-non-squares-removed.png" /></a></td></tr><tr><td class="tr-caption" style="text-align: center;">Removed non-squarish contours</td></tr></tbody></table><h3>Squares within squares</h3><div>Things are looking better but we have three squares in the middle where there is a square around the square. This happens from finding the contours of the black sections between each square. We eliminate these outside squares which leaves us with:</div><div><br /></div><table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody><tr><td style="text-align: center;"><a href="https://2.bp.blogspot.com/-YbHamh3tVBM/WKUXIrYXqnI/AAAAAAAABNA/4QUFMoCPSIw7q0ofGXyWOptpgo1QTONjACEw/s1600/rubiks-70-fix-square-within-square.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" src="https://2.bp.blogspot.com/-YbHamh3tVBM/WKUXIrYXqnI/AAAAAAAABNA/4QUFMoCPSIw7q0ofGXyWOptpgo1QTONjACEw/s1600/rubiks-70-fix-square-within-square.png" /></a></td></tr><tr><td class="tr-caption" style="text-align: center;">Removed squares around squares</td></tr></tbody></table><h3>Cube dimensions and boundries</h3><div>We can now analyze the remaining contours and figure out two key pieces of information</div><div><ul><li>We are dealing with a 4x4x4 cube</li><li>We can find the boundries of the cube</li></ul></div>Since we know know the boundries of the cube we can throw away any contours outside the boundries which leaves us with<br /><br /><table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody><tr><td style="text-align: center;"><a href="https://3.bp.blogspot.com/-_XOhlo02y1I/WKUXIvbsPqI/AAAAAAAABNA/U7aLN2L4itwi5XTMtbTLAs5f-eCZ54ytQCEw/s1600/rubiks-80-removed-outside-cube-boundry.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" src="https://3.bp.blogspot.com/-_XOhlo02y1I/WKUXIvbsPqI/AAAAAAAABNA/U7aLN2L4itwi5XTMtbTLAs5f-eCZ54ytQCEw/s1600/rubiks-80-removed-outside-cube-boundry.png" /></a></td></tr><tr><td class="tr-caption" style="text-align: center;">Removed contours outside cube boundry</td></tr></tbody></table>Presto we have identified the 16 squares in this image!! We compute the mean RGB (Red, Green, Blue) values for each of the 16 contours and later on we hand this data off to the rubiks-color-resolver (more on that in a minute).<br /><br /><h3>Handling Errors</h3>Sometimes the squares of a cube are dented or the sticker is peeling off or there is some really bad glare or it is in the shadows or there is some other crazy problem that makes the contour approximation fail one of our three "is it a square" rules when in fact it is a square. This happened in the image below, the square that is in the 3rd row, 5th column has a contour approximation that doesn't look like a square (the contour is blue, the approximation is red). Here we see the approximation is a triangle so it clearly failed the "There must be four corners" check.<br /><br /><table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody><tr><td style="text-align: center;"><a href="https://1.bp.blogspot.com/-1ihTTCm_wgk/WKUj_Az4ysI/AAAAAAAABNk/_fB_52yqB6EZlK8AAiCX1jvT1zliNr1BwCEw/s1600/rubiks-90.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" src="https://1.bp.blogspot.com/-1ihTTCm_wgk/WKUj_Az4ysI/AAAAAAAABNk/_fB_52yqB6EZlK8AAiCX1jvT1zliNr1BwCEw/s1600/rubiks-90.png" /></a></td></tr><tr><td class="tr-caption" style="text-align: center;">Non-square approximation for a square</td></tr></tbody></table>There were enough good squares for us to determine that this is a 6x6x6 cube though and that we are missing one square<br /><table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody><tr><td style="text-align: center;"><a href="https://2.bp.blogspot.com/-Iw94WTCjtN0/WKUj_Kb9IsI/AAAAAAAABNo/5lxsYuDgOB0W5sp8Lu0Jo461MkSlb4YBgCEw/s1600/rubiks-100.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" src="https://2.bp.blogspot.com/-Iw94WTCjtN0/WKUj_Kb9IsI/AAAAAAAABNo/5lxsYuDgOB0W5sp8Lu0Jo461MkSlb4YBgCEw/s1600/rubiks-100.png" /></a></td></tr><tr><td class="tr-caption" style="text-align: center;">Missing One Square</td></tr></tbody></table>We then look at all of the non-square contours inside the boundries of the cube and see if any of them are in a location that will give us six squares in the 5th column and 6 squares on the 3rd row. The contour in yellow below (approximation in light blue) satisfies that condition.<br /><table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody><tr><td style="text-align: center;"><a href="https://4.bp.blogspot.com/-7ckM7c9vo8s/WKUj_Flq3CI/AAAAAAAABNo/kt9zbMZk4pMW9m8JD24gLikmEBGywNLjgCEw/s1600/rubiks-110.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" src="https://4.bp.blogspot.com/-7ckM7c9vo8s/WKUj_Flq3CI/AAAAAAAABNo/kt9zbMZk4pMW9m8JD24gLikmEBGywNLjgCEw/s1600/rubiks-110.png" /></a></td></tr><tr><td class="tr-caption" style="text-align: center;">All Squares Located</td></tr></tbody></table><br /><h2>Color Extraction</h2><div>Once we've processed the images for all six sides we have the RGB (Red, Green Blue) value for each square. The 4x4x4 image from our example is side F in the cube below, the colors shown are the mean RGB values as extracted from the images. Notice how much variation there is...40 is a good bit darker than 17 but these are both yellow squares.</div><table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody><tr><td style="text-align: center;"><a href="https://3.bp.blogspot.com/-vBgi1x3y0SY/WKUsezqzxSI/AAAAAAAABN8/a51P_kT6f_stnunjHCtY9J0h0aWFZ1XvACLcB/s1600/RGB-raw.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="500" src="https://3.bp.blogspot.com/-vBgi1x3y0SY/WKUsezqzxSI/AAAAAAAABN8/a51P_kT6f_stnunjHCtY9J0h0aWFZ1XvACLcB/s640/RGB-raw.png" width="640" /></a></td></tr><tr><td class="tr-caption" style="text-align: center;">Raw RGB values</td></tr></tbody></table><br />The next step is to take those RGB values and identify which side (U, L, F, R, B, or D) the square belongs to. We do this because all rubiks cube solvers need to know the exact state of the cube.<br /><br />The actual mechanics of how this works isn't terribly exciting to write about in a blog but in a nutshell it does the following:<br /><br /><ul><li>Identify the six colors used by the cube. In this case the colors are red, orange, green, blue, yellow and white.</li><li>Create a list of the color combinations used by all edges (red/blue, yellow/red, etc)</li><li>Create a list of the color combinations used by all corners (white/orange/green, red/blue/white, etc)</li><li>Create a list of centers color squares</li><li>For each edge (say U5 L18 for example) compute the color distance of that edge vs. all of the edges that in the "list of edge color combinations that we need" and find the one that is the closest match. The distance between two colors is calculated using the <a href="https://en.wikipedia.org/wiki/Color_difference">CIEDE2000</a> algorithm. For the U5 L18 example the needed color combination that matches with the lowest color distance is white/orange so we assigne white/orange to U5 L18 and remove white/orange from the needed list (since this is a 4x4x4 there is one more white/orange left on the needed list).</li><li>Repeat the process for the corners and centers</li></ul>The end result is that we can nail down exactly which side each square belongs to. We then redraw the cube with some brighter colors so we can sanity check against the "Raw RGB values" image above to make sure we got everything correct.<div><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-iPH1-_2hZEs/WKUse2zKF_I/AAAAAAAABOA/D2iB_gKegfgclYF__FjTfidwX7qW26RQQCLcB/s1600/RGB-resolved.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="481" src="https://3.bp.blogspot.com/-iPH1-_2hZEs/WKUse2zKF_I/AAAAAAAABOA/D2iB_gKegfgclYF__FjTfidwX7qW26RQQCLcB/s640/RGB-resolved.png" width="640" /></a></div><div><br /></div><div>And finally we print out a big string that represents the state of the cube. This string is what is passed to various <a href="https://github.com/dwalton76/rubiks-cube-solvers">rubiks cube solvers</a> so they can compute a solution. For the cube above the state string is </div><div>RRBBURURBULLLBBUFFFRRRFLFBFDRDFDDRRLFBDDBBLRRLUBFDLUDLDRDRUUBBUFDLUBDDRLUBDLLFFUDDUFBLULBFFRLFUU</div><div><br /></div><div>The color resolver code is available at <a href="https://github.com/dwalton76/rubiks-color-resolver">https://github.com/dwalton76/rubiks-color-resolver</a></div><div><br /></div><h2>The Code</h2><div>If you have a linux box, webcam and a Rubiks cube you can install the software that I used in the video. It is available at <a href="https://github.com/dwalton76/rubiks-cube-tracker">https://github.com/dwalton76/rubiks-cube-tracker</a>...just follow the install instructions in the README.</div><div><br /></div><h2>References</h2><br /><ul><li>http://www.pyimagesearch.com/2015/04/06/zero-parameter-automatic-canny-edge-detection-with-python-and-opencv/</li><li>http://www.pyimagesearch.com/2016/02/08/opencv-shape-detection/</li><li>http://docs.opencv.org/trunk/d9/d8b/tutorial_py_contours_hierarchy.html</li><li>http://www.alanzucconi.com/2015/09/30/colour-sorting/</li><li>https://en.wikipedia.org/wiki/Color_difference</li></ul></div>dwalton76http://www.blogger.com/profile/01231435969332456287noreply@blogger.com3tag:blogger.com,1999:blog-3545476513192978628.post-7120249843855923532016-10-16T14:44:00.002-07:002016-10-16T15:05:54.057-07:00SeanBot 2.0 - smartphone web interface for lego tank robots<h2>SeanBot</h2>Two years ago I did the <a href="http://programmablebrick.blogspot.com/2014/11/seanbot-ev3-robot-controlled-via-web.html" target="_blank">SeanBot</a> robot which was the <a href="http://www.lego.com/en-us/mindstorms/build-a-robot/ev3d4" target="_blank">EV3D4</a> build but with ev3dev running under the covers and a basic web interface for driving. The implementation was a bit clunky though as it used an apache web server to serve the web pages, images, etc but used a second web server for the REST API. Despite being a bit clunky to get going I've seen several projects use the seanbot code to provide a web interface for their robot. pandaeatsbamboo was the most recent project to do so, they have a nice <a href="http://pandaeatsbamboo.blogspot.hk/2016/07/using-web-and-cisco-spark-to-control.html" target="_blank">blog post</a> on their build.<br /><br />Since there were several projects using the seanbot code and since many of the basic lego mindstorms builds are tank style robots (EV3D4, TRACK3R, GRIPP3R, EV3RSTORM, ete are all tank robots) I decided to revamp the seanbot code to make it a little easier to use. Here it is in action, details after the video.<br /><br /><div class="separator" style="clear: both; text-align: center;"><iframe allowfullscreen="" class="YOUTUBE-iframe-video" data-thumbnail-src="https://i.ytimg.com/vi/x5VauXr7W4A/0.jpg" frameborder="0" height="266" src="https://www.youtube.com/embed/x5VauXr7W4A?feature=player_embedded" width="320"></iframe></div><br /><h2>Goals</h2><br /><ul><li>Only run one web server</li><li>Implement the web server in python</li><li>Take advantage of the Tank class in ev3dev-lang-python's <a href="https://github.com/rhempel/ev3dev-lang-python/blob/develop/ev3dev/helper.py">helper.py</a></li><li>Provide a desktop interface and a touch based smartphone interface</li><li>Make it easy for someone to modify the existing code for their own robot</li></ul><h2>Web Interface</h2><div>The web server listens on port 8000 so go to http://x.x.x.x:8000/ where x.x.x.x is the IP address of your EV3. The main interface will present you with a choice between a desktop interface or a mobile interface.</div><div><br /></div><div class="separator" style="clear: both; text-align: center;"></div><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-mb88UkC5KTs/WAPVMKjnSUI/AAAAAAAABHo/VgCKgKBqYkkPZOhRhhE2eVvSqJWdmAOBwCEw/s1600/IMG_4706.PNG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="223" src="https://1.bp.blogspot.com/-mb88UkC5KTs/WAPVMKjnSUI/AAAAAAAABHo/VgCKgKBqYkkPZOhRhhE2eVvSqJWdmAOBwCEw/s400/IMG_4706.PNG" width="400" /></a></div><div class="separator" style="clear: both; text-align: center;"><br /></div><h3 style="clear: both; text-align: left;">Desktop Interface</h3><div class="separator" style="clear: both; text-align: left;">The desktop interface looks very similar to the original seanbot interface. There are two sliders, one to control the speed of the medium motor and one to control the speed of the tank's movements. This page supports touch events so you can use the desktop interface from your smartphone if you like.</div><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-zev8VRhgrhw/WAPVO8wuNyI/AAAAAAAABH0/dcVEl5w211sCVZsk0S_ruQ3rx5D5Zm2AgCEw/s1600/IMG_4708.PNG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="222" src="https://1.bp.blogspot.com/-zev8VRhgrhw/WAPVO8wuNyI/AAAAAAAABH0/dcVEl5w211sCVZsk0S_ruQ3rx5D5Zm2AgCEw/s400/IMG_4708.PNG" width="400" /></a></div><div class="separator" style="clear: both; text-align: center;"><br /></div><h3 style="clear: both; text-align: left;">Mobile Interface</h3><div class="separator" style="clear: both; text-align: left;">The mobile interface uses a virtual joystick, if you drag the black dot towards the top of the gray circle the robot will move forward. Drag it to the right to turn clockwise, drag it to the left to turn counter clockwise, etc. </div><div class="separator" style="clear: both; text-align: left;"><br /></div><div class="separator" style="clear: both; text-align: left;">The closer the black dot is to the edge of the gray circle the faster the robot moves.</div><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-oxPGUKaS4Ko/WAPVO5U1qhI/AAAAAAAABHs/vDhpxKoVVgAqwkTEcW7KgId_HO1Hdi3OQCEw/s1600/IMG_4709.PNG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="223" src="https://4.bp.blogspot.com/-oxPGUKaS4Ko/WAPVO5U1qhI/AAAAAAAABHs/vDhpxKoVVgAqwkTEcW7KgId_HO1Hdi3OQCEw/s400/IMG_4709.PNG" width="400" /></a></div><div><br /></div><h2>The Code</h2><br />The code is available at <a href="https://github.com/rhempel/ev3dev-lang-python/tree/develop/demo/EV3D4" target="_blank">ev3dev-lang-python</a> in the demo/EV3D4 directory, just run EV3D4WebControl and off you go (I am assuming that you are running <a href="https://pypi.python.org/pypi/python-ev3dev">python-ev3dev 0.7.0</a> or later). WebControlledTank lives in ev3dev/helper.py so take a look at that if you want to see the details on what is going on behind the scenes.<br /><br />If you want your own tank class robot with a web interface you could do something similar to this:<br /><br /><span style="font-family: "courier new" , "courier" , monospace; font-size: x-small;">#!/usr/bin/env python3</span><br /><span style="font-family: "courier new" , "courier" , monospace; font-size: x-small;"><br /></span><span style="font-family: "courier new" , "courier" , monospace; font-size: x-small;">import logging</span><br /><span style="font-family: "courier new" , "courier" , monospace; font-size: x-small;">from ev3dev.auto import OUTPUT_A, OUTPUT_B, OUTPUT_C, OUTPUT_D</span><br /><span style="font-family: "courier new" , "courier" , monospace; font-size: x-small;">from ev3dev.helper import WebControlledTank, MediumMotor</span><br /><span style="font-family: "courier new" , "courier" , monospace; font-size: x-small;"><br /></span><span style="font-family: "courier new" , "courier" , monospace; font-size: x-small;">log = logging.getLogger(__name__)</span><br /><br /><span style="font-family: "courier new" , "courier" , monospace; font-size: x-small;">class MyTankRobot(WebControlledTank):</span><br /><span style="font-family: "courier new" , "courier" , monospace; font-size: x-small;"><br /></span><span style="font-family: "courier new" , "courier" , monospace; font-size: x-small;"> def __init__(self, </span><br /><span style="font-family: "courier new" , "courier" , monospace; font-size: x-small;"> medium_motor=OUTPUT_A, </span><br /><span style="font-family: "courier new" , "courier" , monospace; font-size: x-small;"> left_motor=OUTPUT_C,</span><br /><span style="font-family: "courier new" , "courier" , monospace; font-size: x-small;"> right_motor=OUTPUT_B):</span><br /><span style="font-family: "courier new" , "courier" , monospace; font-size: x-small;"> WebControlledTank.__init__(self, left_motor, right_motor)</span><br /><span style="font-family: "courier new" , "courier" , monospace; font-size: x-small;"><br /></span><span style="font-family: "courier new" , "courier" , monospace; font-size: x-small;"> self.medium_motor = MediumMotor(medium_motor)</span><br /><span style="font-family: "courier new" , "courier" , monospace; font-size: x-small;"> self.medium_motor.reset()</span><br /><span style="font-family: "courier new" , "courier" , monospace; font-size: x-small;"> # code specific to your robot (sensors, etc) goes here</span><br /><span style="font-family: "courier new" , "courier" , monospace; font-size: x-small;"><br /></span><span style="font-family: "courier new" , "courier" , monospace; font-size: x-small;">if __name__ == '__main__':</span><br /><span style="font-family: "courier new" , "courier" , monospace; font-size: x-small;"> mybot = MyTankRobot()</span><br /><span style="font-family: "courier new" , "courier" , monospace; font-size: x-small;"> mybot.main()</span><br /><div><br /></div><br /><span style="font-family: "courier new" , "courier" , monospace; font-size: x-small;"><br /></span><span style="font-family: "courier new" , "courier" , monospace; font-size: x-small;"><br /></span>dwalton76http://www.blogger.com/profile/01231435969332456287noreply@blogger.com0tag:blogger.com,1999:blog-3545476513192978628.post-28579243477166847632016-08-09T19:06:00.003-07:002016-08-09T19:06:56.943-07:00Save the Clock Tower!!I am way behind on posting recent projects...and by recent I mean last Halloween. One of my friends goes all out for his annual Halloween party, there is always a theme and some elaborate prop. A couple of years ago there was a pirate theme so he built a partial pirate ship in his garage.<br /><br />The theme for last Halloween was Back to the Future and the prop was going to be a large clock tower. I volunteered to build a clock motor out of an EV3. The goals were:<br /><ul><li>Run until 10:04 and then freeze</li><li>Signal an arduino to trigger a lightning strike (white rope lights)</li><li>After five minutes of sitting at 10:04 start back up but spin extra fast so that we get back to 10:04 in 15 minutes</li></ul><div>I found a pretty cool <a href="http://robotics.benedettelli.com/lego-clock/" target="_blank">analog clock</a> design online. It used technic parts and the instructions were only a few bucks. The gear ratios are such that for every full rotation of the long hand the short hand makes 1/12 of a rotation. Here is a test run of the clock being driven by a power functions motor.<br /><br /></div><div><div class="separator" style="clear: both; text-align: center;"><iframe allowfullscreen="" class="YOUTUBE-iframe-video" data-thumbnail-src="https://i.ytimg.com/vi/fYNTeairxeA/0.jpg" frameborder="0" height="266" src="https://www.youtube.com/embed/fYNTeairxeA?feature=player_embedded" width="320"></iframe></div><div class="separator" style="clear: both; text-align: center;"><br /></div><div class="separator" style="clear: both; text-align: center;"><br /></div><div class="separator" style="clear: both; text-align: left;"><span style="text-align: start;">And the finished clock tower with a lightning strike at 10:04</span></div><div class="separator" style="clear: both; text-align: center;"><br /></div><div style="text-align: center;"><iframe allowfullscreen="" class="YOUTUBE-iframe-video" data-thumbnail-src="https://i.ytimg.com/vi/dfyf8zEoTiE/0.jpg" frameborder="0" height="266" src="https://www.youtube.com/embed/dfyf8zEoTiE?feature=player_embedded" width="320"></iframe></div><br /></div><div><br /></div><div><br /></div><div><br /></div>dwalton76http://www.blogger.com/profile/01231435969332456287noreply@blogger.com1tag:blogger.com,1999:blog-3545476513192978628.post-2689449008543239312015-10-20T19:59:00.001-07:002015-10-20T19:59:53.584-07:00MindCuber EV3 in Python<h2 style="clear: both; text-align: left;">MindCuber</h2><div class="separator" style="clear: both; text-align: left;">If you have an EV3 you have probably watched a video of the awesome <a href="http://mindcuber.com/mindcub3r/mindcub3r.html" target="_blank">MindCub3r</a> robot solving a Rubiks cube. I too built this robot and made a video :). One twist is that mine is running <a href="http://www.ev3dev.org/" target="_blank">ev3dev</a> (Linux) and all of the code is written in Python. I am a big Python fan and would much rather program crazy lego robots in it than I would the graphical programming language provided by lego.</div><div class="separator" style="clear: both; text-align: center;"><br /></div><div class="separator" style="clear: both; text-align: center;"><iframe width="320" height="266" class="YOUTUBE-iframe-video" data-thumbnail-src="https://i.ytimg.com/vi/oPtDPtUbnks/0.jpg" src="https://www.youtube.com/embed/oPtDPtUbnks?feature=player_embedded" frameborder="0" allowfullscreen></iframe></div><div class="separator" style="clear: both; text-align: center;"><br /></div><h2 style="clear: both; text-align: left;">The Code</h2><div>cavenel on github wrote the original MindCuber python implementation based on a release of ev3dev from early 2014. It no longer worked on the latest ev3dev though so I started fixings bugs and got the basics working. I also rewrote most of the code that does the color analysis.</div><div><br /></div><div><div>The code is available here:</div><div><a href="https://github.com/cavenel/ev3dev_examples">https://github.com/cavenel/ev3dev_examples</a></div></div><div><br /></div><h3>Color Analysis</h3><div>The lego color sensor can scan something and return one of a few basic colors (blue, green, yellow, red, etc) but for scanning a Rubiks cube this doesn't work very well. The reason being certain colors on the cube are too similar, Red vs. Orange are really close, even Blue vs. Green can confuse the sensor because they are both so dark.</div><div><br /></div><div>There is hope though, you can tell the color sensor to return the raw RGB (Red, Green, Blue) value instead of trying to guess at the color. I take the RGB values for all 54 squares and figure out which of the six possible colors each square is. I learned a lot about <a href="https://en.wikipedia.org/wiki/Color_difference" target="_blank">Color Difference</a> and <a href="http://www.ryanheise.com/cube/cube_laws.html" target="_blank">Rubiks Cube Parity</a> :)</div><div><br /></div><h3>Solution Code</h3><div>Once you know what color each square is you can feed that data to one of many rubiks cube solving programs out there on the web and they will return a list of instructions that tell you how to solve the cube. This is some pretty complex stuff, people have done their PhD thesis on algorithms for solving Rubiks cubes.</div><div><br /></div><div>I did not dive into this in depth, this problem was solved in depth long ago by people a lot smarter than me. I wanted to keep everything in python though so I grabbed a copy of the following and am using that:</div><div>https://github.com/muodov/kociemba</div><div><br /></div><div><br /></div><div class="separator" style="clear: both; text-align: center;"><br /></div><div class="separator" style="clear: both; text-align: center;"><br /></div><br />dwalton76http://www.blogger.com/profile/01231435969332456287noreply@blogger.com1tag:blogger.com,1999:blog-3545476513192978628.post-41360126375224872072014-11-09T14:32:00.002-08:002014-11-09T14:32:37.975-08:00SeanBot - An EV3 robot controlled via a web interfaceI built a cool little robot recently and even managed to convince myself that it was somewhat work related. Sean, one of my co-workers at <a href="http://cumulusnetworks.com/" target="_blank">Cumulus Networks</a>, and his wife were expecting their first child so Sean wasn't going to risk making the trip to California for a quarterly meeting since it was too close to their due date. I hadn't done a cool mindstorms project recently so I offered to build a little robot that he could control via the web and drive around the offices at headquarters. The idea was to have the robot hold an iPhone running Skype so that Sean could drive around the desk during the meetings and chat with everyone.<br /><div><br /></div><div>I decided to use one of the EV3 bonus models, EV3D4, as the robot. It is small but very mobile so it seemed like a good choice. That and it is based off of the Star Wars robot R5-D4 (the little red robot the Jawas were selling along with R2-D2 and C-3PO in Episode IV) so that just makes it extra cool. Originally I told my 5-year old that it was R2-D2 but he called me out with "Daddy that isn't R2-D2, it needs to be white and blue to be R2-D2, not white and red". Outsmarted by a 5-year old...</div><div><br /></div><table cellpadding="0" cellspacing="0" class="tr-caption-container" style="float: left; margin-right: 1em; text-align: left;"><tbody><tr><td style="text-align: center;"><a href="http://1.bp.blogspot.com/-Pmr4oQhLbyw/VF_cjSAw5bI/AAAAAAAAA4I/7GlBpGIpEiQ/s1600/RotaCaster1.jpg" imageanchor="1" style="clear: left; margin-bottom: 1em; margin-left: auto; margin-right: auto;"><img border="0" src="http://1.bp.blogspot.com/-Pmr4oQhLbyw/VF_cjSAw5bI/AAAAAAAAA4I/7GlBpGIpEiQ/s1600/RotaCaster1.jpg" /></a></td></tr><tr><td class="tr-caption" style="text-align: center;">HiTechnic's Rotacaster</td></tr></tbody></table>In terms of the hardware the main change I made was to use an omniwheel, officially I used a <a href="http://www.hitechnic.com/cgi-bin/commerce.cgi?preadd=action&key=HRC2148" target="_blank">Rotacaster from HiTechnic</a>. An omniwheel rotates like a normal wheel but can also slide from side to side...they are handy if you have robot that needs to spin in circles. I also used a very small wifi dongle called '<a href="http://www.amazon.com/gp/product/B009FA2UYK/ref=oh_aui_detailpage_o07_s00?ie=UTF8&psc=1" target="_blank">The Pi Hut</a>' but be warned you can't use this with the standard EV3 software...more on that in a bit.<br /><div><br /></div><div><br /></div><div class="separator" style="clear: both; text-align: center;"><a href="http://1.bp.blogspot.com/-Oa9q45MnFuc/VF_cqy0QpyI/AAAAAAAAA4Q/bCLzG2iqklI/s1600/SeanBot1.JPG" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" src="http://1.bp.blogspot.com/-Oa9q45MnFuc/VF_cqy0QpyI/AAAAAAAAA4Q/bCLzG2iqklI/s1600/SeanBot1.JPG" height="300" width="400" /></a></div><div><br /></div><div>You can see the robot in action here with the omniwheel front and center, iphone mounted, etc. Sean used Skype to dial the iphone from his desk so that is him on the phone there.</div><div><br /></div><div>For the hardware I didn't change much from the stock Lego instructions but for the software I took a very different approach. I needed the robot to run a web server that would allow Sean to control the robot via a web browser. I couldn't find a way to do this via the standard software that ships with the EV3 but good news, there is a great little project call <a href="http://www.ev3dev.org/" target="_blank">ev3dev</a> that built a debian linux distribution that will run on the EV3. In other words you just boot debian linux on your EV3!! This gives you tons of flexibility<span style="font-family: Times New Roman, serif; font-size: medium;"><span style="line-height: 19.2600002288818px;"> </span></span>and it means that you no longer have to use the graphical programming language provided by Lego. Python is my favorite language and it turns out that with ev3dev you can program the EV3 in python...perfect!!</div><div><br /></div><div><div>All of the code for this project is available on github, feel free to use it:</div><div><a href="https://github.com/dwalton76/LegoEV3D4">https://github.com/dwalton76/LegoEV3D4</a></div></div><div><br /></div><div>How does the code work? The /var/www/ content is served by the main webserver (apache, etc). LegoR2D2.py runs a REST API on port 8000. When the user clicks on a button on the web page served by apache, AJAX is used to send a HTTP GET to LegoR2D2.py's REST API (it is listening on port 8000) to tell it to move forward, backward, etc. When the user releases the button we send another HTTP GET to tell it to stop.</div><div><br /></div><div>The Star Wars page on the left of Sean's screen is the web page served by the robot. You just click the arrows to make the robot move.</div><div class="separator" style="clear: both; text-align: center;"><a href="http://2.bp.blogspot.com/-QWGZQf0fjw8/VF_iIoe66HI/AAAAAAAAA4g/SVqLShlvx-E/s1600/SeanBot2.JPG" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" src="http://2.bp.blogspot.com/-QWGZQf0fjw8/VF_iIoe66HI/AAAAAAAAA4g/SVqLShlvx-E/s1600/SeanBot2.JPG" height="480" width="640" /></a></div><div><br /></div><div><br /></div><div><br /></div><div><br /></div><div><br /></div><div><br /></div><div><br /></div><div><br /></div><div><br /></div><div><br /></div><div><br /></div><div><br /></div><div><br /></div><div><br /></div><div><br /></div><div><br /></div><div><br /></div><div><br /></div><div><br /></div><div><br /></div><div><br /></div><div><br /></div><div><br /></div><div><br /></div><div><br /></div><div><br /></div><div><br /></div><div><br /></div><div><br /></div><div>Here is SeanBot in action for the quarterly meeting, SeanBot is in Mountain View, CA but Sean is driving it from Apex, NC...cool stuff.</div><div><br /></div><blockquote class="twitter-tweet" lang="en">Starting team qbr with Seanbot 3000... <a href="https://twitter.com/seanx820">@seanx820</a> <a href="http://t.co/mamBdEQ0yE">pic.twitter.com/mamBdEQ0yE</a><br />â€” Jason Martin (@jaymonsf) <a href="https://twitter.com/jaymonsf/status/519226715420106753">October 6, 2014</a></blockquote><br /><br /><script async="" charset="utf-8" src="//platform.twitter.com/widgets.js"></script> <div><div class="separator" style="clear: both; text-align: center;"><a href="http://4.bp.blogspot.com/-IyQJEBhOeEY/VF_komRSFlI/AAAAAAAAA4s/IiK_qxBnNzQ/s1600/baby.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" src="http://4.bp.blogspot.com/-IyQJEBhOeEY/VF_komRSFlI/AAAAAAAAA4s/IiK_qxBnNzQ/s1600/baby.jpg" height="400" width="300" /></a></div><br /></div><div>And last but not least here is Sean's beautiful daughter :) She was born a few weeks after the meeting in California ended and is keeping Sean and his wife plenty busy.</div><div class="separator" style="clear: both; text-align: center;"><br /></div>dwalton76http://www.blogger.com/profile/01231435969332456287noreply@blogger.com18tag:blogger.com,1999:blog-3545476513192978628.post-24850067708521441362014-06-27T10:56:00.001-07:002014-06-27T10:56:28.081-07:00Lego Digital Clock<div>I built a copy of an awesome lego clock designed by Hans Andersson:</div><div><a href="http://tiltedtwister.com/timetwister.html">http://tiltedtwister.com/timetwister.html</a></div><div><br /></div><div class="separator" style="clear: both; text-align: center;"><object width="320" height="266" class="BLOGGER-youtube-video" classid="clsid:D27CDB6E-AE6D-11cf-96B8-444553540000" codebase="http://download.macromedia.com/pub/shockwave/cabs/flash/swflash.cab#version=6,0,40,0" data-thumbnail-src="https://i1.ytimg.com/vi/Er_Qg53FdUY/0.jpg"><param name="movie" value="https://www.youtube.com/v/Er_Qg53FdUY?version=3&f=user_uploads&c=google-webdrive-0&app=youtube_gdata" /><param name="bgcolor" value="#FFFFFF" /><param name="allowFullScreen" value="true" /><embed width="320" height="266" src="https://www.youtube.com/v/Er_Qg53FdUY?version=3&f=user_uploads&c=google-webdrive-0&app=youtube_gdata" type="application/x-shockwave-flash" allowfullscreen="true"></embed></object></div><div><br /></div><div><br /></div><div>Mine is a little different in that it uses a Raspberry Pi to control the motors instead of two NXT bricks. Dexter Industries makes a Pi add-on board called BrickPi which allows you to control lego mindstorms motors, etc from a Pi:</div><div><a href="http://www.dexterindustries.com/BrickPi/">http://www.dexterindustries.com/BrickPi/</a></div><div><br /></div><table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody><tr><td style="text-align: center;"><a href="http://3.bp.blogspot.com/-01saW91gpso/U62vTWaNvqI/AAAAAAAAA1o/cASZuPQ_MHY/s1600/brickpi.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" src="http://3.bp.blogspot.com/-01saW91gpso/U62vTWaNvqI/AAAAAAAAA1o/cASZuPQ_MHY/s1600/brickpi.jpg" height="235" width="320" /></a></td></tr><tr><td class="tr-caption" style="text-align: center;">Raspberry Pi + BrickPi<br /><br /></td></tr></tbody></table><div>All of the code is written in python and is available on github:</div><div><a href="https://github.com/dwalton76/LegoDigitalClock">https://github.com/dwalton76/LegoDigitalClock</a></div><div><br /></div>dwalton76http://www.blogger.com/profile/01231435969332456287noreply@blogger.com3tag:blogger.com,1999:blog-3545476513192978628.post-69715288403364907752013-09-22T11:00:00.001-07:002013-09-22T11:00:23.528-07:00Remote Controlled EV3 Lego Excavator 42006<h2>Remote Controlled Excavator</h2><div class="separator" style="clear: both; text-align: left;">I got the LEGO Excavator a few months ago but the controls on it were way too difficult for my kids to use. Heck I had a hard time remembering what combination the three switches had to be in to make it open/close the claw or raise/lower the arm. I found some videos on youtube where people used a lot of power functions gear to make their excavators remote controllable. The way they did it was cool but I don't own tons of power functions parts so I decided to make mine remote controllable by combining it with my EV3.</div><div class="separator" style="clear: both; text-align: left;"><br /></div><div class="separator" style="clear: both; text-align: left;">The hardest part was figuring out how to control six movements with only four motors. I built a <a href="http://programmablebrick.blogspot.com/2013/09/lego-technic-two-input-four-output.html">motor multiplexer</a> that uses two motors to control four movements. This is used to control the claw, arm, rotating the platform,etc. I used the other two motors to control the tracks.</div><div class="separator" style="clear: both; text-align: left;"><br /></div><div class="separator" style="clear: both; text-align: left;">It is a big hit with my kids :)</div><div class="separator" style="clear: both; text-align: center;"><br /></div><div class="separator" style="clear: both; text-align: center;"><iframe allowFullScreen='true' webkitallowfullscreen='true' mozallowfullscreen='true' width='320' height='266' src='https://www.youtube.com/embed/E50GSgUGkqQ?feature=player_embedded' FRAMEBORDER='0' /></div><div class="separator" style="clear: both; text-align: center;"><br /></div><h2>Instructions</h2><br /><ul><li><a href="http://www.wallofbricks.com/blogger/EV3-42006.lxf">LDD Instructions</a> - I didn't include instructions for the arm/boom since they are the exact same as the standard 42006. When you build it turn the mux so that it is engaging the gear at the top.</li><li><a href="http://www.wallofbricks.com/blogger/Excavator.ev3">EV3 Software</a> - There is a program called RunFirst that you need to run one time when you first build the excavator. This program creates a text file that is used to remember where the multiplexer is located. This way if you turn the EV3 off and turn it back on, we know which gear is currently engaged by the mux.</li></ul><br /><br />dwalton76http://www.blogger.com/profile/01231435969332456287noreply@blogger.com11tag:blogger.com,1999:blog-3545476513192978628.post-15602175675823242202013-09-10T13:10:00.002-07:002013-09-10T13:10:45.782-07:00Lego Technic Two Input, Four Output Motor Multiplexers<h2>Motor Multiplexers</h2><div class="separator" style="clear: both; text-align: center;"><a href="http://1.bp.blogspot.com/-7FmqzEjNaSU/Ui96dgkPLtI/AAAAAAAAAu4/vn7ZJBtmdDw/s1600/lego-42006.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" height="320" src="http://1.bp.blogspot.com/-7FmqzEjNaSU/Ui96dgkPLtI/AAAAAAAAAu4/vn7ZJBtmdDw/s320/lego-42006.jpg" width="320" /></a></div><br />I bought the Lego Excavator 42006 a few months ago (for the kids of course) along with the power functions add-on so you could motorize moving the boom up & down along with opening and closing the claw. The controls are pretty bad though, there are three switches that you have to toggle in just the right combination to get the movement that you want. It takes me several tries to find the combo I'm looking for, for my 4-year old it is really frustrating.<br /><br />I also got an EV3 kit recently so I've been working on combining the two so that I end up with a remote-controlled excavator. I figure that will be much more enjoyable for the kiddos. The challenge is the EV3 brick only supports 4 motors but I need to be able to control six movements on the excavator.<br /><br /><ul><li>Opening and closing the claw</li><li>Moving the boom up and down</li><li>Moving the boom in and out</li><li>Rotating the entire platform clockwise and counter clockwise</li><li>Moving the left track forward and backwards</li><li>Moving the right track forward and backwards</li></ul><div>I need to run both tracks at once in order to move forwards, backwards and steer so that leaves me two motors to control the claw, boom up/down, boom in/out and platform rotation. I started working on a hardware based motor multiplexer that would let me control four functions from two motors. </div><div><br /></div><div>It took me a few iterations to get something compact enough to fit in the excavator. The turntable mux at the beginning of this video is the one I'm using for the Excavator. The other two work, they were just too bulky. The two at the end are a little different in that they will let you enable two outputs at once unlike the turntable mux which only enables one output at a time. Someone else may find them useful though so I included them in the video.</div><div><br /></div><div class="separator" style="clear: both; text-align: center;"><br /><iframe allowFullScreen='true' webkitallowfullscreen='true' mozallowfullscreen='true' width='320' height='266' src='https://www.youtube.com/embed/dkdBeTA8ztQ?feature=player_embedded' FRAMEBORDER='0' /></div><div class="separator" style="clear: both; text-align: center;"><br /></div>I'm still working on the Excavator but it shouldn't be much longer now that I have the mux figured out.<br /><br /><h3>Build Instructions</h3><div>Here are the LDD (LEGO Digital Designer) files:</div><div><ul><li><a href="http://www.wallofbricks.com/blogger/motor-mux-turntable.lxf">Turntable Mux</a></li><li><a href="http://www.wallofbricks.com/blogger/motor-mux.lxf">Two outputs in the front, two outputs in the back mux</a></li><li>I forgot to create a LDD file for the "Four outputs on one side" mux but it is very similar to the two in the front, two in the back mux. </li></ul></div><div><br /></div><div><br /></div>dwalton76http://www.blogger.com/profile/01231435969332456287noreply@blogger.com3tag:blogger.com,1999:blog-3545476513192978628.post-46798561101178622242013-08-23T20:36:00.001-07:002013-08-23T20:36:21.251-07:00LED Photo Drawing Robot<h2>LED Photo Drawing Robot</h2><div><br /></div><div class="separator" style="clear: both; text-align: center;"><a href="http://1.bp.blogspot.com/-H3BTI-dQKjQ/UhgLRtEHIFI/AAAAAAAAAtI/Is4kTMFYu0Y/s1600/headlamp-pacman.jpg" imageanchor="1" style="float: right; margin-left: 1em; margin-right: 1em;"><img border="0" height="248" src="http://1.bp.blogspot.com/-H3BTI-dQKjQ/UhgLRtEHIFI/AAAAAAAAAtI/Is4kTMFYu0Y/s320/headlamp-pacman.jpg" width="320" /></a></div><div>A few years ago on a camping trip my friends and I started playing around with drawing shapes with our headlamp while someone else took a 30-second exposure with the camera. I drew Pac-Man chasing a ghost and it came out fairly well for blindly waving a flashlight around in the dark.</div><div><br /></div><div>I thought it might be cool to build a robot that could draw a picture like this. I built a robot that moves a LED around a grid and then turns on the LED to the desired color at each location on the grid. I used my DLSR to take a very long exposure while the robot is moving the LED around the grid. The end result is a photo of the LED at all of the various points in the grid which (hopefully) looks like the image the robot is trying to reproduce.</div><div class="separator" style="clear: both; text-align: center;"><br /></div><h3>LED Photos</h3><h4>Pac-Man</h4><div>Given the photo that gave me the idea for the robot I had to try a Pac-Man image first. This was a nice photo to start out with because there was a lot of black in it so it only took the robot about 10 minutes to draw it. That made it nice for troubleshooting because I only had to wait 10 minutes to see if it worked.</div><div><br /></div><div class="separator" style="clear: both; text-align: center;"><a href="http://3.bp.blogspot.com/-_3DCrdjoNMo/UhgM6BMpeHI/AAAAAAAAAtQ/tmT3x1MoApw/s1600/6469_pacman_cutters_on_black1.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="136" src="http://3.bp.blogspot.com/-_3DCrdjoNMo/UhgM6BMpeHI/AAAAAAAAAtQ/tmT3x1MoApw/s320/6469_pacman_cutters_on_black1.jpg" width="320" /></a></div><div><br /></div><div class="separator" style="clear: both; text-align: center;"><a href="http://4.bp.blogspot.com/-3K535RbWiak/UhgM71ShmRI/AAAAAAAAAtc/c05wF8x-iRs/s1600/IMG_8358.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="123" src="http://4.bp.blogspot.com/-3K535RbWiak/UhgM71ShmRI/AAAAAAAAAtc/c05wF8x-iRs/s320/IMG_8358.jpg" width="320" /></a></div><div class="separator" style="clear: both; text-align: center;"><br /></div><h4>The Starry Night</h4><div>Next on the list was The Starry Night. This was a big jump in complexity over the pac-man photo. It took me a few attempts to get all of the kinks worked out. There aren't many all black pixels in this one so it took about 30 minutes to complete. It is a long shot from a perfect replica but at least you can tell what it is :)</div><div class="separator" style="clear: both; padding-top: 30px; text-align: center;"><a href="http://1.bp.blogspot.com/-vW9GDJul2WY/UhgM8qAxhII/AAAAAAAAAtk/WA6wpuJXK6M/s1600/The-Starry-Night.jpg" imageanchor="1" style="float: left; margin-left: 1em; margin-right: 1em;"><img border="0" src="http://1.bp.blogspot.com/-vW9GDJul2WY/UhgM8qAxhII/AAAAAAAAAtk/WA6wpuJXK6M/s320/The-Starry-Night.jpg" width="280" /></a></div><div class="separator" style="text-align: center;"><a href="http://2.bp.blogspot.com/-uF85UuIEt8M/UhgM9U4J6uI/AAAAAAAAAt0/csPiBp1DRhE/s1600/IMG_8391.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://2.bp.blogspot.com/-uF85UuIEt8M/UhgM9U4J6uI/AAAAAAAAAt0/csPiBp1DRhE/s320/IMG_8391.jpg" width="310" /></a></div><div class="separator" style="clear: both; text-align: center;"><br /></div><h4>Lego Mona Lisa</h4><div>I stumbled across this image and it seemed too fitting for this project :)</div><div><br /></div><div class="separator" style="clear: both; text-align: center;"><a href="http://3.bp.blogspot.com/-Vzqs_At2iWw/UhgM9Fe1_BI/AAAAAAAAAts/TrVvlU6G_-A/s1600/lego+Mona+Lisa.jpg" imageanchor="1" style="float: left; margin-left: 1em; margin-right: 1em;"><img border="0" height="320" src="http://3.bp.blogspot.com/-Vzqs_At2iWw/UhgM9Fe1_BI/AAAAAAAAAts/TrVvlU6G_-A/s320/lego+Mona+Lisa.jpg" width="231" /></a></div><div class="separator" style="text-align: center;"><a href="http://3.bp.blogspot.com/-XGbpsAcZS-s/UhgM98MhD8I/AAAAAAAAAt8/CySUjnsl-xQ/s1600/IMG_8393.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="320" src="http://3.bp.blogspot.com/-XGbpsAcZS-s/UhgM98MhD8I/AAAAAAAAAt8/CySUjnsl-xQ/s320/IMG_8393.jpg" width="318" /></a></div><div class="separator" style="clear: both; text-align: center;"><br /></div><div><h3>In Action</h3></div><div class="separator" style="clear: both; text-align: center;"><iframe allowFullScreen='true' webkitallowfullscreen='true' mozallowfullscreen='true' width='320' height='266' src='https://www.youtube.com/embed/SQ8CTbKLbeM?feature=player_embedded' FRAMEBORDER='0' /></div><div><br /></div><h3>How It Works</h3><div><h4>The LED</h4><div class="separator" style="clear: both; text-align: center;"><a href="http://3.bp.blogspot.com/-KWS285lVebc/UhgWbnzsEFI/AAAAAAAAAuI/y5G1wWQC63M/s1600/dLight014.JPG" imageanchor="1" style="float: left; margin-left: 1em; margin-right: 1em;"><img border="0" height="240" src="http://3.bp.blogspot.com/-KWS285lVebc/UhgWbnzsEFI/AAAAAAAAAuI/y5G1wWQC63M/s320/dLight014.JPG" width="320" /></a></div><br />The color sensor from lego can also produce light of various colors but it is pretty limited. You can only tell it basic colors like "red", "green", "yellow", etc. I needed a way to produce a larger range of colors so I bought a <a href="http://www.dexterindustries.com/dLight.html">dLight</a> from <a href="http://www.dexterindustries.com/">Dexter Industries</a>. It comes with four LEDs but I only ended up using one of them. Most of the time you see these used in robot cars so people can add turn signals and/or headlights.<br /><br />The LED was a little bright though so I punched a small hole in a piece of black construction paper and taped that over the LED. That gave me a smaller light source which meant that I could squeeze in more pixels.<br /><br /><br /><h4>Robot Hardware</h4><div class="separator" style="clear: both; text-align: center;"><a href="http://4.bp.blogspot.com/-R0NPvM7Szhk/UhgZiIgnP_I/AAAAAAAAAuU/odQs3ooquzs/s1600/010.JPG" imageanchor="1" style="float: right; margin-left: 1em; margin-right: 1em;"><img border="0" height="320" src="http://4.bp.blogspot.com/-R0NPvM7Szhk/UhgZiIgnP_I/AAAAAAAAAuU/odQs3ooquzs/s320/010.JPG" width="240" /></a></div>I needed the position of the LED to be very accurate so that I could draw the right color pixel in the exact spot where I needed it. I've tried doing super accurate movements like this before with a robot that drives around on rubber wheels but at some point the wheels always slip a little and that throws everything off. To get the accuracy I needed I built a platform with two rows of gear-racks on top. The LED sits on top of a motor which has gears for wheels, these gear wheels drive along the gear racks. This is how the LED moves up and down.<br /><div class="separator" style="clear: both; text-align: center;"><br /></div><div class="separator" style="clear: both; text-align: center;"><a href="http://2.bp.blogspot.com/-lIyTmv0Mo3o/Uhga-jdemAI/AAAAAAAAAug/igp1tQJ05G4/s1600/012.JPG" imageanchor="1" style="float: left; margin-left: 1em; margin-right: 1em;"><img border="0" height="240" src="http://2.bp.blogspot.com/-lIyTmv0Mo3o/Uhga-jdemAI/AAAAAAAAAug/igp1tQJ05G4/s320/012.JPG" width="320" /></a></div><br /><br />Getting the left to right movement was a little trickier. I put wheels at the ends of my "up/down" platform and attached a long arm of beams to the platform. I put gear-racks on top of the really long arm and used a 2nd motor to turn a gear that joined with those gear racks. This gave me a way to slide the "up/down" platform left and right.<br /><div class="separator" style="clear: both; text-align: center;"><br /></div><h4>Robot Software</h4>I wrote small program in PERL reads an image file and gets the color for each pixel in the image. This ends up being information like "Pixel 10x50 has Red=57, Green=140, Blue=200". I just printed all the information about what color each pixel should be into a simple text file. I then copied that text file over to the robot where the robot would read the text file to learn how much Red, Green, and Blue for the LED to output at each location. Then you just have it move to every location listed in the text file and tune the LED to the correct color.<br /><br /><br /><br /></div>dwalton76http://www.blogger.com/profile/01231435969332456287noreply@blogger.com6tag:blogger.com,1999:blog-3545476513192978628.post-90217512923496391652013-08-20T20:04:00.002-07:002013-08-20T20:51:32.297-07:00Lego Technic iPhone Tripod<div class="separator" style="clear: both; text-align: left;"></div><br /><div class="separator" style="clear: both; text-align: center;"><object class="BLOGGER-youtube-video" classid="clsid:D27CDB6E-AE6D-11cf-96B8-444553540000" codebase="http://download.macromedia.com/pub/shockwave/cabs/flash/swflash.cab#version=6,0,40,0" data-thumbnail-src="http://i1.ytimg.com/vi/t_wHnZDTOlA/0.jpg" height="266" style="float: right; margin-left: 20px;" width="320"><param name="movie" value="http://www.youtube.com/v/t_wHnZDTOlA?version=3&f=user_uploads&c=google-webdrive-0&app=youtube_gdata" /><paramle name="bgcolor" value="#FFFFFF" /><param name="allowFullScreen" value="true" /><embed width="320" height="266" src="http://www.youtube.com/v/t_wHnZDTOlA?version=3&f=user_uploads&c=google-webdrive-0&app=youtube_gdata" type="application/x-shockwave-flash" allowfullscreen="true"></embed></object></div><h3><span style="text-align: start;">The Motivation</span></h3><div class="separator" style="text-align: left;"><span style="text-align: start;">I downloaded the </span><a href="https://itunes.apple.com/us/app/lego-movie-maker/id516001587?mt=8" style="text-align: start;">LEGO Movie Maker</a><span style="text-align: start;"> app for my iPhone a few days ago so my daughter could try her hand at making stop motion videos. It is really easy to use, it only took a few minutes and my 6-year old was reenacting Luke rescuing Leia from the Death Star. My daughter couldn't hold the phone in the same spot though so the movie ended up being a mix of Star Wars and The Blair Witch Project. I didn't get green watching it but that is only because it was about 4 seconds long. It was still really cool to see her make a movie on her own though :)</span></div><div class="separator" style="text-align: left;"></div><div class="separator" style="clear: both; padding-top: 40px; text-align: center;"><iframe allowFullScreen='true' webkitallowfullscreen='true' mozallowfullscreen='true' width='320' height='266' src='https://www.youtube.com/embed/ryAVnZ249z0?feature=player_embedded' FRAMEBORDER='0' /></div><div style="text-align: left;"><h3>The Tripod</h3>Anyway, we didn't have a tripod for an iPhone so I started building one out of technic parts. The only parts I used that were not from my Mindstorms kit were the three technic turntables. These cost about $1.50 each on ebay so the entire thing is probably $7 or $8 in parts.<br /><br />There are two turntables on the sides so that you can tilt the phone forwards and backwards. There is another turntable underneath that lets the phone twist left and right.<br /><br />And yes I know that this isn't technically a tripod but I figure "iphone tripod" is probably googled about a billion times more often than "iphone bipod" :)<br /><br /><div class="separator" style="clear: both; float: left; padding-top: 30px; text-align: center;"><a href="http://1.bp.blogspot.com/-BLqkvh5TYeU/UhQvbY6FdsI/AAAAAAAAAso/01HP81tgJD0/s1600/pic1.JPG" imageanchor="1" style="margin-bottom: 1em; margin-right: 1em;"><img border="0" height="240" id="lego-technic-iphone-tripod-1" src="http://1.bp.blogspot.com/-BLqkvh5TYeU/UhQvbY6FdsI/AAAAAAAAAso/01HP81tgJD0/s320/pic1.JPG" width="300" /></a></div><br /><div class="separator" style="padding-top: 10px;"><a href="http://3.bp.blogspot.com/-MFScfywKqFU/UhQvh7uGooI/AAAAAAAAAsw/jjjSnkC0oEk/s1600/pic2.JPG" imageanchor="1" style="margin-bottom: 1em; margin-left: 1em;"><img border="0" height="240" id="lego-technic-iphone-tripod-2" src="http://3.bp.blogspot.com/-MFScfywKqFU/UhQvh7uGooI/AAAAAAAAAsw/jjjSnkC0oEk/s320/pic2.JPG" width="300" /></a></div><br /><br /><h3>Parts List</h3><div><a href="http://www.wallofbricks.com/blogger/iphone_tripod.xlsx">Parts Spreadsheet</a>.</div><div><table><tbody><tr><td style="text-align: center;"><a href="http://www.brickset.com/parts/search/?query=4210751"><img src="http://cache.lego.com/media/bricks/5/2/4210751.jpg" width="60px" /></a><br />QTY: 1</td><td></td><td style="text-align: center;"><a href="http://www.brickset.com/parts/search/?query=4495932"><img src="http://cache.lego.com/media/bricks/5/2/4495932.jpg" width="60px" /></a><br />QTY: 8</td><td></td><td style="text-align: center;"><a href="http://www.brickset.com/parts/search/?query=4297202"><img src="http://cache.lego.com/media/bricks/5/2/4297202.jpg" width="60px" /></a><br />QTY: 2</td><td></td><td style="text-align: center;"><a href="http://www.brickset.com/parts/search/?query=4522939"><img src="http://cache.lego.com/media/bricks/5/2/4522939.jpg" width="60px" /></a><br />QTY: 4</td><td></td><td style="text-align: center;"><a href="http://www.brickset.com/parts/search/?query=4172457"><img src="http://cache.lego.com/media/bricks/5/2/4172457.jpg" width="60px" /></a><br />QTY: 2</td><td></td><td style="text-align: center;"><a href="http://www.brickset.com/parts/search/?query=4210753"><img src="http://cache.lego.com/media/bricks/5/2/4210753.jpg" width="60px" /></a><br />QTY: 4</td><td></td><td style="text-align: center;"><a href="http://www.brickset.com/parts/search/?query=4142865"><img src="http://cache.lego.com/media/bricks/5/2/4142865.jpg" width="60px" /></a><br />QTY: 4</td><td></td><td style="text-align: center;"><a href="http://www.brickset.com/parts/search/?query=4121715"><img src="http://cache.lego.com/media/bricks/5/2/4121715.jpg" width="60px" /></a><br />QTY: 46</td><td></td></tr><tr><td style="text-align: center;"><a href="http://www.brickset.com/parts/search/?query=4206482"><img src="http://cache.lego.com/media/bricks/5/2/4206482.jpg" width="60px" /></a><br />QTY: 2</td><td></td><td style="text-align: center;"><a href="http://www.brickset.com/parts/search/?query=4211639"><img src="http://cache.lego.com/media/bricks/5/2/4211639.jpg" width="60px" /></a><br />QTY: 2</td><td></td><td style="text-align: center;"><a href="http://www.brickset.com/parts/search/?query=4211775"><img src="http://cache.lego.com/media/bricks/5/2/4211775.jpg" width="60px" /></a><br />QTY: 4</td><td></td><td style="text-align: center;"><a href="http://www.brickset.com/parts/search/?query=4107085"><img src="http://cache.lego.com/media/bricks/5/2/4107085.jpg" width="60px" /></a><br />QTY: 2</td><td></td><td style="text-align: center;"><a href="http://www.brickset.com/parts/search/?query=4211865"><img src="http://cache.lego.com/media/bricks/5/2/4211865.jpg" width="60px" /></a><br />QTY: 8</td><td></td><td style="text-align: center;"><a href="http://www.brickset.com/parts/search/?query=4121667"><img src="http://cache.lego.com/media/bricks/5/2/4121667.jpg" width="60px" /></a><br />QTY: 1</td><td></td><td style="text-align: center;"><a href="http://www.brickset.com/parts/search/?query=4211889"><img src="http://cache.lego.com/media/bricks/5/2/4211889.jpg" width="60px" /></a><br />QTY: 4</td><td></td><td style="text-align: center;"><a href="http://www.brickset.com/parts/search/?query=4296059"><img src="http://cache.lego.com/media/bricks/5/2/4296059.jpg" width="60px" /></a><br />QTY: 4</td><td></td></tr><tr><td style="text-align: center;"><a href="http://www.brickset.com/parts/search/?query=4624645"><img src="http://cache.lego.com/media/bricks/5/2/4624645.jpg" width="60px" /></a><br />QTY: 3</td></tr></tbody></table><br /><h3>Instructions</h3></div><div>I used <a href="http://ldd.lego.com/en-us/">LEGO Digital Designer</a> to create the build instructions that are in the video. If you don't feel like pausing the video every 5 seconds you can download the LDD file for the tripod <a href="http://www.wallofbricks.com/blogger/iphone_tripod.lxf">here</a>. </div><div><br /></div><div><br /></div></div>dwalton76http://www.blogger.com/profile/01231435969332456287noreply@blogger.com0tag:blogger.com,1999:blog-3545476513192978628.post-37260528947666332992013-03-09T18:26:00.002-08:002013-03-09T18:26:45.121-08:00Build Instructions for Drop7 Robot<h2>Hardware</h2>I tried out the <a href="http://ldd.lego.com/">Lego Digital Designer</a> software to create some build instructions for the Drop7 robot. It was very easy to use and works really well. If only the NXT-G software were as solid as the LDD software :)<br /><div><br /></div><div>Here is a <a href="https://docs.google.com/file/d/0Bxs_DERbqYM6ME12Z0U4cC1kWHc/edit?usp=sharing">zip file</a> with the .lxf file that you view in Lego Digital Designer. LDD wouldn't let me attach the gear racks and it wouldn't let me attach the sliding platform to the track. Other than that the instructions should be accurate.</div><div><br /></div><div class="separator" style="clear: both; text-align: center;"><a href="http://3.bp.blogspot.com/-W3dmF5Y7mqQ/UTvpYGwkPKI/AAAAAAAAAp0/CmbWJO8xmcY/s1600/Step89.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="480" src="http://3.bp.blogspot.com/-W3dmF5Y7mqQ/UTvpYGwkPKI/AAAAAAAAAp0/CmbWJO8xmcY/s640/Step89.png" width="640" /></a></div><div><br /></div><pre class="prettyprint"></pre><h2>Software</h2>Here is the BricxCC code that tells the robot which way to move and how long to pause after touching the iPad.<br /><br /><pre class="prettyprint">task main() {<br /> // This sequence will get you to the x29 chain at the end of Level 2.<br /> unsigned char column_drop[] = {1,3,3,2,3,5,5,6,3,7,6,5,4,2,3,1,7,4,1,6,5,2,7,1,2,3,2,3,2,4,6,6,3,2,4,3,1,4,3,7,4,5,5,6,6,3,1,5,2,3,2,7,2,7,5,3,7,5,6};<br /> unsigned int column_delay[] = {1600,1600,1600,0,0,1000,0,0,0,0,0,0,17600,0,0,0,0,0,0,0,3200,0,18500,4100,0,0,0,0,0,2500,1000,0,0,0,0,1600,1600,0,0,0,0,1000,1600,1000,0,1600,1600,0,0,0,1600,0,0,1600,0,0,0,1600};<br /><br /> unsigned int i;<br /> unsigned char prev_column = 4;<br /> unsigned char curr_column = 0;<br /> unsigned int degrees = 0;<br /><br /> for (int i = 0; i < ArrayLen(column_drop); i++) {<br /> curr_column = column_drop[i];<br /> degrees = 0;<br /><br /> TextOut(0, LCD_LINE1, "DROP: ", true);<br /> NumOut(50, LCD_LINE1, curr_column);<br /><br /> if (prev_column) {<br /> if (curr_column > prev_column) {<br /> degrees = (curr_column - prev_column) * 120;<br /> TextOut(0, LCD_LINE2, "RIGHT: ");<br /> NumOut(50, LCD_LINE2, curr_column - prev_column);<br /> TextOut(0, LCD_LINE3, "DELAY: ");<br /> NumOut(50, LCD_LINE3, column_delay[i]);<br /> RotateMotor(OUT_B, -50, degrees);<br /><br /> } else if (curr_column < prev_column) {<br /> degrees = (prev_column - curr_column) * 120;<br /> TextOut(0, LCD_LINE2, "LEFT: ");<br /> NumOut(50, LCD_LINE2, prev_column - curr_column);<br /> TextOut(0, LCD_LINE3, "DELAY: ");<br /> NumOut(50, LCD_LINE3, column_delay[i]);<br /> RotateMotor(OUT_B, 50, degrees);<br /> } else {<br /> // Same column...do nothing<br /> }<br /> }<br /><br /> // Touch the iPad, (motor, power, degrees)<br /> RotateMotorEx(OUT_C, 40, 25, 0, 0, 1);<br /> Wait(100);<br /> RotateMotorEx(OUT_C, 20, -25, 0, 0, 1);<br /><br /> if (column_delay[i]) {<br /> Wait(column_delay[i]);<br /> }<br /> prev_column = curr_column;<br /> }<br />}<br /></pre>dwalton76http://www.blogger.com/profile/01231435969332456287noreply@blogger.com0tag:blogger.com,1999:blog-3545476513192978628.post-77688896470864624682013-03-08T10:42:00.003-08:002013-03-08T10:42:50.276-08:00Drop7 with Lego Mindstorms NXT<style>table.drop7_table { font-family: "Lucida Sans Unicode", "Lucida Grande", Sans-Serif; font-size: 12px; width: 480px; text-align: left; border-collapse: collapse; margin: 10px; } table.drop7_table th { font-size: 13px; font-weight: bold; background: #2C3D82; border-bottom: 1px solid #fff; color: white; padding: 8px; } table.drop7_table td { background: #6F83D6; border-bottom: 1px solid #fff; color: white; border-top: 1px solid transparent; padding: 8px; } table.drop7_table tr:hover td { background: #d0dafd; color: #339; } div#permutations_wrapper { width: 300px; margin-left: auto; margin-right: auto; } table#permutations { width: 300px; } table#sequence_mode_discs { font-size: 10px; } table#sequence_mode_discs td { padding: 3px; } div#chain_scores_wrapper { width: 300px; margin-left: auto; margin-right: auto; } table#chain_scores { width: 300px; } table#chain_scores td { padding: 3px; padding-left: 8px; } </style>I posted a <a href="http://www.youtube.com/watch?v=vTnzgPBGnnQ">video</a> on youtube of a Lego Mindstorms NXT robot of mine, playing Drop7 in sequence mode to a score of 5,205,955. Some of my friends told me I should blog about it to explain how I did it, so here is a rather lengthy explanation of everything that went into the video. The robot plays to the end of Level 71, it clears the board 23 times, the longest chain is x29 and is worth 367,087 points. There are also chains of x26, x25, x24, two x23s, two x22s, etc, etc.<br /><br /><div class="separator" style="clear: both; text-align: center;"><iframe allowFullScreen='true' webkitallowfullscreen='true' mozallowfullscreen='true' width='320' height='266' src='https://www.youtube.com/embed/vTnzgPBGnnQ?feature=player_embedded' FRAMEBORDER='0' /></div><br /><h2>The Inspiration</h2>I started playing Drop7 on my phone a few months ago and eventually stumbled across a video of someone who scored <a href="http://www.youtube.com/watch?v=-ayGfvyBxKU">5,000,000 points on Drop7</a> in sequence mode. For those of you that have never played Drop7 is it sort of like a math based version of Tetris. You have a 7x7 grid where you select which column to drop a disc in. You earn points by making discs explode, preferably in a long chain which earns more points. Making a disc explode is easy, if you place a disc with a 4 in a column with 4 discs, all of the 4s in that column explode. The same rule apples to having 4 discs in a row, when that happens all of the 4s in the row explode.<br /><div><br /></div><div>Anyway, I started thinking about how the person that made the video figured out what sequence to play the discs in to get such a high score. They were playing in sequence mode which means that the same discs are played every time you play the game. I was sure they wrote a program to figure out how to get such a high score and I like to do geeky little projects so I wrote my own program that simulates Drop7. I figured I would have it run through a few million permutations that one could play the discs in and see which permutation produced the highest score.</div><div><br /><h2>Permutations</h2></div><div>Just how many permutations can the discs be played in? Let's say you only know what the first four discs will be in sequence mode. There are 7 different columns you can drop each disc in so the permutations will be as follows (the numbers represent which column to place a disc in):</div><div id="permutations_wrapper"><table class="drop7_table" id="permutations"><thead><tr><th>Count</th><th>Permutation</th></tr><tr></tr></thead><tbody><tr><td>#1</td><td>1 1 1 1</td></tr><tr><td>#2</td><td>1 1 1 2</td></tr><tr><td>#3</td><td>1 1 1 3</td></tr><tr><td></td><td>. . . .</td></tr><tr><td>#2399</td><td>7 7 7 5</td></tr><tr><td>#2400</td><td>7 7 7 6</td></tr><tr><td>#2401</td><td>7 7 7 7</td></tr></tbody></table></div><div><br /></div><div>This comes out to 7^4 or 2401 permutations. OK 2401 isn't such a huge number for a computer but let's expand this and assume you know what the first 100 discs are in sequence mode. 7^100 is a GIGANTIC number of permutations, 3.2344765096247579913446477691002e+84 to be exact. That number is so huge it is hard to wrap your head around it. To put it in perspective if you stacked up 3.2344765096247579913446477691002e+84 sheets of printer paper the stack of paper would be about 3.29 light years tall! Needless to say I don't have access to enough computing power to crunch through that many permutations of Drop7 within the next few billion years.</div><div><br /></div><div>I decided to break the first 100 discs down into groups of 8. I could run through every permutation that one could play the first 8 discs in, find the permutation that resulted in the best score and then move on to the next batch of 8 discs, etc. This wouldn't give the absolute best possible score one could get out of the first 100 discs but it would spit out a sequence to play the discs in that would produce a very high score.<br /><br /><h2>Drop7 Simulator</h2>At this point the little simulator program I wrote was in a language called PERL which is an easy language to program with but is slow compared to a complied language like C. It took my PERL program quite a while (days) to crunch through the first 100 discs in groups of 8 so I rewrote my simulator in C which is much much faster, in this case the C version was 74x faster than the PERL version!! I then moved from analyzing the discs in groups of 8 to groups of 12.<br /><br />I was doing all of this on my home PC which has four 2.8Ghz cores. Crunching through the discs in groups of 12 took a long time, each group of 12 was 13.8 billion permutations (7^12) to simulate. I knew I wouldn't be able to do move up to groups of 13 on my home machine, not unless I was willing to let it run for months. The larger the groups of discs you analyze the higher scoring sequences the program is able to find so I wanted to move from 12 to 13 if not higher. I was chatting about this little project with a co-worker and he gave me access to one of his machines at work that has 32 cores. It is a Linux machine running on a <a href="http://www.cisco.com/en/US/products/ps12288/index.html">Cisco UCS B200-M3</a> to be exact. It isn't often that one maxes out 32 cores for days on end...here is a screen capture that shows them all pegged at 100% :)<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://1.bp.blogspot.com/-K_HLaa9-tLU/UTPG1z6OETI/AAAAAAAAAok/GqzWPveyeCM/s1600/image001.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="353" src="http://1.bp.blogspot.com/-K_HLaa9-tLU/UTPG1z6OETI/AAAAAAAAAok/GqzWPveyeCM/s640/image001.png" width="640" /></a></div><br /></div><div>In the end I was able to crunch through the discs in groups of 14, each group of 14 has 678 billion permutations. I knew what the first 680 discs were in sequence mode which means there were ~49 groups of 14 discs to analyze. So 678 billion permutations per group x 49 groups x 14 discs per group = 465 TRILLION discs were "dropped" in my Drop7 simulator. Even with 32 cores running 24 hours a day it took weeks for it to produce the sequence I used for the video.<br /><br />I posted all of my code for the Drop7 simulator on github. If anyone wants to tweak it to find a better Drop7 algorithm you have my permission to use my code.<br /><a href="https://github.com/dwalton76/Drop7-Sequence-Mode">https://github.com/dwalton76/Drop7-Sequence-Mode</a><br /><br /><h2>Sequence Mode Discs</h2><div>I found a post on a forum somewhere that listed all of the discs that would come in sequence mode for the first 10 levels. To figure out the future disc beyond level 10 I would play to level 10, then record a video of myself playing, then watch the video to figure out what the new discs were. The only problem with this approach was that I had to keep playing from the beginning of the game up to Level 10, or 11, or whatever level I was stuck on at the time, in order to figure out what the next discs were. This was taking a while and either my wife or I jokingly said that we should build a Lego robot to play it for us. I'll go into the robot more in second but here is a table of all discs (a disc with a "?" means it is a solid disc) for the first 71 levels of sequence mode. Should someone else ever decide to do a project like this they shouldn't have to analyze game film of themselves playing Drop7....that part was pretty boring.</div><div><br /><div><table class="drop7_table" id="sequence_mode_discs"><thead><tr><th>Lvl</th><th colspan="8">Level Up Discs</th><th colspan="30">One-By-One Discs</th></tr></thead><tbody><tr><td>1</td><td>6?</td><td>4?</td><td>5?</td><td>7?</td><td>5?</td><td>1?</td><td>3?</td><td class="spacer"></td><td>2</td><td>1</td><td>1</td><td>6?</td><td>4</td><td>5</td><td>5?</td><td>5?</td><td>1?</td><td>6</td><td>1</td><td>5</td><td>7</td><td>5</td><td>3</td><td>6</td><td>3</td><td>2?</td><td>6</td><td>4?</td><td>2</td><td>5</td><td>7</td><td>1</td><td>2?</td><td>5</td><td>1?</td><td>3?</td><td>2?</td><td colspan="100%">4</td></tr><tr><td>2</td><td>1?</td><td>3?</td><td>6?</td><td>3?</td><td>3?</td><td>4?</td><td>4?</td><td class="spacer"></td><td>5</td><td>5</td><td>2?</td><td>1?</td><td>6?</td><td>2?</td><td>3</td><td>2</td><td>3</td><td>2?</td><td>3?</td><td>6</td><td>2</td><td>7</td><td>7</td><td>6</td><td>3?</td><td>2?</td><td>6?</td><td>4</td><td>7</td><td>4</td><td>5</td><td>4</td><td>3</td><td>6</td><td>1</td><td>6?</td><td colspan="100%">1</td></tr><tr><td>3</td><td>6?</td><td>4?</td><td>5?</td><td>7?</td><td>3?</td><td>3?</td><td>4?</td><td class="spacer"></td><td>5</td><td>7?</td><td>4</td><td>6</td><td>3</td><td>5?</td><td>7</td><td>4</td><td>3</td><td>5</td><td>2</td><td>6?</td><td>2</td><td>7</td><td>2</td><td>1</td><td>4</td><td>7</td><td>4?</td><td>4</td><td>2</td><td>7</td><td>3</td><td>5?</td><td>5</td><td>5</td><td>1?</td><td colspan="100%">7?</td></tr><tr><td>4</td><td>2?</td><td>2?</td><td>7?</td><td>1?</td><td>7?</td><td>1?</td><td>5?</td><td class="spacer"></td><td>7</td><td>7?</td><td>2</td><td>7?</td><td>2</td><td>3?</td><td>2</td><td>3</td><td>2?</td><td>2</td><td>6?</td><td>5?</td><td>4?</td><td>6?</td><td>5</td><td>7?</td><td>2</td><td>6</td><td>7?</td><td>7?</td><td>5?</td><td>4</td><td>2</td><td>3?</td><td>7</td><td>2</td><td colspan="100%">3</td></tr><tr><td>5</td><td>2?</td><td>3?</td><td>7?</td><td>1?</td><td>5?</td><td>4?</td><td>1?</td><td class="spacer"></td><td>2?</td><td>1</td><td>3?</td><td>4</td><td>1</td><td>3?</td><td>1?</td><td>1</td><td>6</td><td>1?</td><td>5</td><td>7</td><td>5?</td><td>2</td><td>5</td><td>5</td><td>6?</td><td>3</td><td>5?</td><td>4?</td><td>5</td><td>7</td><td>4</td><td>1</td><td>3?</td><td colspan="100%">5</td></tr><tr><td>6</td><td>5?</td><td>2?</td><td>3?</td><td>6?</td><td>2?</td><td>7?</td><td>1?</td><td class="spacer"></td><td>1</td><td>6</td><td>4</td><td>7?</td><td>3</td><td>7</td><td>3</td><td>7</td><td>7?</td><td>4</td><td>4?</td><td>1</td><td>5</td><td>1?</td><td>5</td><td>1</td><td>4?</td><td>4</td><td>3?</td><td>4</td><td>7</td><td>4</td><td>3</td><td>1</td><td colspan="100%">4?</td></tr><tr><td>7</td><td>3?</td><td>6?</td><td>7?</td><td>1?</td><td>3?</td><td>7?</td><td>3?</td><td class="spacer"></td><td>5</td><td>5?</td><td>7?</td><td>5?</td><td>5?</td><td>1</td><td>3</td><td>6?</td><td>2?</td><td>2</td><td>3</td><td>7</td><td>5</td><td>4</td><td>5</td><td>6</td><td>1</td><td>6</td><td>7?</td><td>1</td><td>1</td><td>2?</td><td>7</td><td colspan="100%">3</td></tr><tr><td>8</td><td>1?</td><td>5?</td><td>4?</td><td>1?</td><td>6?</td><td>3?</td><td>3?</td><td class="spacer"></td><td>7</td><td>2</td><td>2?</td><td>7?</td><td>7</td><td>4?</td><td>6?</td><td>5</td><td>7</td><td>5</td><td>7</td><td>6?</td><td>7</td><td>4</td><td>6</td><td>5</td><td>1</td><td>6?</td><td>3</td><td>4</td><td>7?</td><td>7</td><td colspan="100%">5</td></tr><tr><td>9</td><td>3?</td><td>7?</td><td>3?</td><td>1?</td><td>1?</td><td>1?</td><td>4?</td><td class="spacer"></td><td>2</td><td>6</td><td>1</td><td>3</td><td>7?</td><td>6</td><td>4</td><td>7</td><td>3</td><td>7</td><td>6?</td><td>5</td><td>5?</td><td>6</td><td>2</td><td>4</td><td>3</td><td>3</td><td>5?</td><td>7</td><td>4?</td><td colspan="100%">7</td></tr><tr><td>10</td><td>2?</td><td>1?</td><td>6?</td><td>3?</td><td>2?</td><td>3?</td><td>7?</td><td class="spacer"></td><td>1?</td><td>5?</td><td>4</td><td>3?</td><td>6</td><td>5</td><td>1?</td><td>7?</td><td>7</td><td>1</td><td>5</td><td>6</td><td>1</td><td>7</td><td>4?</td><td>6</td><td>3</td><td>6</td><td>1</td><td>1</td><td colspan="100%">1?</td></tr><tr><td>11</td><td>5?</td><td>3?</td><td>4?</td><td>5?</td><td>4?</td><td>5?</td><td>3?</td><td class="spacer"></td><td>5</td><td>6</td><td>4</td><td>7</td><td>7</td><td>4</td><td>4?</td><td>2?</td><td>5?</td><td>3?</td><td>4?</td><td>4?</td><td>4?</td><td>3?</td><td>4</td><td>3?</td><td>3</td><td>2?</td><td>1</td><td colspan="100%">4?</td></tr><tr><td>12</td><td>6?</td><td>1?</td><td>6?</td><td>6?</td><td>7?</td><td>3?</td><td>3?</td><td class="spacer"></td><td>7</td><td>2</td><td>7</td><td>5?</td><td>3?</td><td>6</td><td>3?</td><td>2?</td><td>4</td><td>6</td><td>2</td><td>2</td><td>5</td><td>7</td><td>1</td><td>7</td><td>5?</td><td>3</td><td colspan="100%">7</td></tr><tr><td>13</td><td>6?</td><td>4?</td><td>2?</td><td>5?</td><td>7?</td><td>7?</td><td>5?</td><td class="spacer"></td><td>1</td><td>4</td><td>3?</td><td>2</td><td>2</td><td>7?</td><td>3</td><td>2</td><td>4</td><td>2?</td><td>6</td><td>7</td><td>1</td><td>3</td><td>4</td><td>6</td><td>2?</td><td colspan="100%">4?</td></tr><tr><td>14</td><td>7?</td><td>7?</td><td>4?</td><td>2?</td><td>5?</td><td>1?</td><td>1?</td><td class="spacer"></td><td>3?</td><td>2?</td><td>2</td><td>7</td><td>5?</td><td>5</td><td>6</td><td>7?</td><td>1?</td><td>1?</td><td>4</td><td>3?</td><td>4</td><td>3?</td><td>1</td><td>6</td><td colspan="100%">5?</td></tr><tr><td>15</td><td>5?</td><td>1?</td><td>3?</td><td>3?</td><td>5?</td><td>3?</td><td>5?</td><td class="spacer"></td><td>2</td><td>2?</td><td>5?</td><td>3</td><td>1?</td><td>7</td><td>2</td><td>2</td><td>1</td><td>1</td><td>7</td><td>7</td><td>7?</td><td>1</td><td>4</td><td colspan="100%">4</td></tr><tr><td>16</td><td>4?</td><td>7?</td><td>4?</td><td>5?</td><td>7?</td><td>6?</td><td>7?</td><td class="spacer"></td><td>1</td><td>1?</td><td>4?</td><td>4</td><td>4</td><td>4</td><td>4</td><td>1</td><td>4</td><td>5</td><td>7?</td><td>2</td><td>2</td><td>4?</td><td colspan="100%">7</td></tr><tr><td>17</td><td>1?</td><td>4?</td><td>3?</td><td>3?</td><td>5?</td><td>2?</td><td>3?</td><td class="spacer"></td><td>4</td><td>5</td><td>3</td><td>2</td><td>3?</td><td>7</td><td>1</td><td>4?</td><td>7?</td><td>7?</td><td>3</td><td>2?</td><td>6</td><td colspan="100%">2</td></tr><tr><td>18</td><td>1?</td><td>5?</td><td>1?</td><td>3?</td><td>6?</td><td>4?</td><td>3?</td><td class="spacer"></td><td>3?</td><td>2</td><td>2</td><td>5?</td><td>6?</td><td>4</td><td>6</td><td>2</td><td>7</td><td>3?</td><td>7</td><td>6</td><td colspan="100%">1</td></tr><tr><td>19</td><td>1?</td><td>5?</td><td>7?</td><td>4?</td><td>1?</td><td>7?</td><td>6?</td><td class="spacer"></td><td>2?</td><td>3</td><td>5</td><td>4</td><td>6</td><td>5?</td><td>6?</td><td>1</td><td>3</td><td>4</td><td>1</td><td colspan="100%">1</td></tr><tr><td>20</td><td>7?</td><td>3?</td><td>6?</td><td>7?</td><td>1?</td><td>6?</td><td>2?</td><td class="spacer"></td><td>1?</td><td>1</td><td>3</td><td>6</td><td>4?</td><td>1?</td><td>1?</td><td>6</td><td>7</td><td>7</td><td colspan="100%">3?</td></tr><tr><td>21</td><td>3?</td><td>2?</td><td>1?</td><td>2?</td><td>5?</td><td>5?</td><td>6?</td><td class="spacer"></td><td>5</td><td>3</td><td>3</td><td>4</td><td>6</td><td>3</td><td>4</td><td>2?</td><td>1</td><td colspan="100%">1?</td></tr><tr><td>22</td><td>6?</td><td>4?</td><td>2?</td><td>2?</td><td>5?</td><td>5?</td><td>2?</td><td class="spacer"></td><td>4</td><td>5?</td><td>3?</td><td>6</td><td>6</td><td>5?</td><td>6</td><td>2</td><td colspan="100%">4</td></tr><tr><td>23</td><td>6?</td><td>2?</td><td>7?</td><td>3?</td><td>7?</td><td>3?</td><td>2?</td><td class="spacer"></td><td>1</td><td>7</td><td>7</td><td>1</td><td>5</td><td>2?</td><td>2</td><td colspan="100%">7?</td></tr><tr><td>24</td><td>2?</td><td>3?</td><td>6?</td><td>6?</td><td>4?</td><td>6?</td><td>1?</td><td class="spacer"></td><td>5</td><td>3</td><td>2</td><td>3?</td><td>2</td><td>1</td><td colspan="100%">2</td></tr><tr><td>25</td><td>4?</td><td>5?</td><td>4?</td><td>7?</td><td>5?</td><td>6?</td><td>2?</td><td class="spacer"></td><td>1?</td><td>5?</td><td>6?</td><td>3</td><td>5</td><td colspan="100%">6?</td></tr><tr><td>26</td><td>4?</td><td>4?</td><td>6?</td><td>6?</td><td>2?</td><td>5?</td><td>5?</td><td class="spacer"></td><td>2</td><td>7?</td><td>6</td><td>1</td><td colspan="100%">5?</td></tr><tr><td>27</td><td>1?</td><td>3?</td><td>3?</td><td>5?</td><td>4?</td><td>4?</td><td>7?</td><td class="spacer"></td><td>4?</td><td>4</td><td>3</td><td>7</td><td colspan="100%">1</td></tr><tr><td>28</td><td>3?</td><td>4?</td><td>5?</td><td>2?</td><td>2?</td><td>3?</td><td>3?</td><td class="spacer"></td><td>2</td><td>2</td><td>7</td><td>7</td><td colspan="100%">3</td></tr><tr><td>29</td><td>2?</td><td>5?</td><td>1?</td><td>4?</td><td>5?</td><td>5?</td><td>6?</td><td class="spacer"></td><td>6</td><td>2</td><td>1</td><td>6?</td><td colspan="100%">7</td></tr><tr><td>30</td><td>3?</td><td>3?</td><td>4?</td><td>6?</td><td>1?</td><td>2?</td><td>4?</td><td class="spacer"></td><td>2</td><td>3</td><td>5?</td><td>1</td><td colspan="100%">4</td></tr><tr><td>31</td><td>2?</td><td>5?</td><td>1?</td><td>2?</td><td>6?</td><td>2?</td><td>5?</td><td class="spacer"></td><td>4</td><td>7</td><td>3</td><td>1</td><td colspan="100%">1</td></tr><tr><td>32</td><td>5?</td><td>1?</td><td>1?</td><td>5?</td><td>4?</td><td>2?</td><td>3?</td><td class="spacer"></td><td>7</td><td>1</td><td>4?</td><td>4</td><td colspan="100%">5</td></tr><tr><td>33</td><td>7?</td><td>2?</td><td>6?</td><td>4?</td><td>7?</td><td>3?</td><td>3?</td><td class="spacer"></td><td>6?</td><td>4</td><td>4?</td><td>3</td><td colspan="100%">4</td></tr><tr><td>34</td><td>6?</td><td>3?</td><td>7?</td><td>2?</td><td>5?</td><td>6?</td><td>3?</td><td class="spacer"></td><td>4</td><td>6</td><td>1</td><td>7</td><td colspan="100%">2?</td></tr><tr><td>35</td><td>5?</td><td>4?</td><td>1?</td><td>6?</td><td>7?</td><td>4?</td><td>6?</td><td class="spacer"></td><td>5</td><td>2</td><td>5?</td><td>5</td><td colspan="100%">1</td></tr><tr><td>36</td><td>4?</td><td>6?</td><td>3?</td><td>7?</td><td>3?</td><td>3?</td><td>5?</td><td class="spacer"></td><td>1</td><td>5</td><td>1?</td><td>6</td><td colspan="100%">3</td></tr><tr><td>37</td><td>4?</td><td>7?</td><td>7?</td><td>6?</td><td>3?</td><td>7?</td><td>7?</td><td class="spacer"></td><td>6</td><td>7</td><td>3</td><td>7</td><td colspan="100%">4</td></tr><tr><td>38</td><td>1?</td><td>5?</td><td>1?</td><td>1?</td><td>6?</td><td>5?</td><td>5?</td><td class="spacer"></td><td>5</td><td>2</td><td>2</td><td>4?</td><td colspan="100%">7</td></tr><tr><td>39</td><td>2?</td><td>2?</td><td>6?</td><td>4?</td><td>2?</td><td>1?</td><td>2?</td><td class="spacer"></td><td>4</td><td>4</td><td>4</td><td>4</td><td colspan="100%">5?</td></tr><tr><td>40</td><td>1?</td><td>6?</td><td>5?</td><td>4?</td><td>1?</td><td>2?</td><td>5?</td><td class="spacer"></td><td>6</td><td>5</td><td>3</td><td>4</td><td colspan="100%">6?</td></tr><tr><td>41</td><td>1?</td><td>1?</td><td>2?</td><td>2?</td><td>6?</td><td>1?</td><td>1?</td><td class="spacer"></td><td>1?</td><td>6</td><td>6</td><td>7?</td><td colspan="100%">2</td></tr><tr><td>42</td><td>7?</td><td>4?</td><td>3?</td><td>7?</td><td>3?</td><td>3?</td><td>2?</td><td class="spacer"></td><td>7?</td><td>6</td><td>1</td><td>3</td><td colspan="100%">4?</td></tr><tr><td>43</td><td>2?</td><td>6?</td><td>2?</td><td>6?</td><td>5?</td><td>2?</td><td>4?</td><td class="spacer"></td><td>2</td><td>7</td><td>7?</td><td>4?</td><td colspan="100%">6</td></tr><tr><td>44</td><td>6?</td><td>4?</td><td>6?</td><td>3?</td><td>4?</td><td>4?</td><td>3?</td><td class="spacer"></td><td>5</td><td>3</td><td>6</td><td>3?</td><td colspan="100%">5?</td></tr><tr><td>45</td><td>7?</td><td>2?</td><td>3?</td><td>4?</td><td>5?</td><td>4?</td><td>6?</td><td class="spacer"></td><td>1</td><td>4</td><td>4</td><td>7</td><td colspan="100%">2</td></tr><tr><td>46</td><td>2?</td><td>3?</td><td>1?</td><td>7?</td><td>3?</td><td>7?</td><td>6?</td><td class="spacer"></td><td>6</td><td>5?</td><td>7</td><td>2</td><td colspan="100%">2</td></tr><tr><td>47</td><td>3?</td><td>7?</td><td>7?</td><td>5?</td><td>2?</td><td>1?</td><td>1?</td><td class="spacer"></td><td>4</td><td>1</td><td>7?</td><td>3?</td><td colspan="100%">7</td></tr><tr><td>48</td><td>7?</td><td>4?</td><td>5?</td><td>6?</td><td>3?</td><td>3?</td><td>6?</td><td class="spacer"></td><td>6</td><td>5</td><td>4?</td><td>2</td><td colspan="100%">1</td></tr><tr><td>49</td><td>2?</td><td>2?</td><td>5?</td><td>1?</td><td>5?</td><td>7?</td><td>7?</td><td class="spacer"></td><td>5</td><td>5</td><td>3</td><td>6</td><td colspan="100%">2?</td></tr><tr><td>50</td><td>5?</td><td>6?</td><td>1?</td><td>7?</td><td>2?</td><td>7?</td><td>4?</td><td class="spacer"></td><td>3</td><td>6?</td><td>5</td><td>2</td><td colspan="100%">3</td></tr><tr><td>51</td><td>2?</td><td>4?</td><td>7?</td><td>3?</td><td>2?</td><td>6?</td><td>7?</td><td class="spacer"></td><td>6</td><td>4</td><td>1</td><td>7?</td><td colspan="100%">7</td></tr><tr><td>52</td><td>5?</td><td>3?</td><td>5?</td><td>7?</td><td>5?</td><td>4?</td><td>6?</td><td class="spacer"></td><td>2?</td><td>1</td><td>7</td><td>7</td><td colspan="100%">4?</td></tr><tr><td>53</td><td>4?</td><td>2?</td><td>6?</td><td>6?</td><td>1?</td><td>5?</td><td>7?</td><td class="spacer"></td><td>4</td><td>3</td><td>1</td><td>1</td><td colspan="100%">4?</td></tr><tr><td>54</td><td>1?</td><td>1?</td><td>6?</td><td>3?</td><td>1?</td><td>6?</td><td>2?</td><td class="spacer"></td><td>3?</td><td>7?</td><td>3</td><td>1?</td><td colspan="100%">5</td></tr><tr><td>55</td><td>4?</td><td>2?</td><td>6?</td><td>4?</td><td>7?</td><td>1?</td><td>6?</td><td class="spacer"></td><td>6</td><td>2</td><td>4?</td><td>1</td><td colspan="100%">6?</td></tr><tr><td>56</td><td>1?</td><td>3?</td><td>4?</td><td>1?</td><td>3?</td><td>2?</td><td>3?</td><td class="spacer"></td><td>7?</td><td>7</td><td>1?</td><td>4?</td><td colspan="100%">7</td></tr><tr><td>57</td><td>6?</td><td>4?</td><td>7?</td><td>7?</td><td>6?</td><td>5?</td><td>4?</td><td class="spacer"></td><td>7</td><td>3</td><td>1?</td><td>1</td><td colspan="100%">1</td></tr><tr><td>58</td><td>4?</td><td>5?</td><td>6?</td><td>7?</td><td>6?</td><td>7?</td><td>3?</td><td class="spacer"></td><td>1</td><td>3</td><td>6</td><td>7?</td><td colspan="100%">2</td></tr><tr><td>59</td><td>5?</td><td>2?</td><td>4?</td><td>7?</td><td>5?</td><td>3?</td><td>6?</td><td class="spacer"></td><td>4</td><td>7</td><td>7</td><td>4</td><td colspan="100%">1?</td></tr><tr><td>60</td><td>4?</td><td>5?</td><td>2?</td><td>6?</td><td>5?</td><td>1?</td><td>5?</td><td class="spacer"></td><td>2?</td><td>3?</td><td>7?</td><td>7</td><td colspan="100%">5</td></tr><tr><td>61</td><td>1?</td><td>6?</td><td>3?</td><td>5?</td><td>4?</td><td>7?</td><td>3?</td><td class="spacer"></td><td>2</td><td>3</td><td>7?</td><td>1</td><td colspan="100%">7</td></tr><tr><td>62</td><td>1?</td><td>7?</td><td>5?</td><td>2?</td><td>5?</td><td>6?</td><td>5?</td><td class="spacer"></td><td>5</td><td>2</td><td>4?</td><td>4</td><td colspan="100%">4</td></tr><tr><td>63</td><td>7?</td><td>6?</td><td>1?</td><td>4?</td><td>3?</td><td>4?</td><td>5?</td><td class="spacer"></td><td>7</td><td>1</td><td>2</td><td>5</td><td colspan="100%">2?</td></tr><tr><td>64</td><td>3?</td><td>2?</td><td>7?</td><td>6?</td><td>1?</td><td>5?</td><td>7?</td><td class="spacer"></td><td>4?</td><td>4</td><td>6</td><td>4?</td><td colspan="100%">4</td></tr><tr><td>65</td><td>6?</td><td>6?</td><td>7?</td><td>5?</td><td>4?</td><td>2?</td><td>2?</td><td class="spacer"></td><td>2?</td><td>5</td><td>7</td><td>1</td><td colspan="100%">3</td></tr><tr><td>66</td><td>3?</td><td>6?</td><td>3?</td><td>3?</td><td>2?</td><td>4?</td><td>7?</td><td class="spacer"></td><td>3</td><td>3?</td><td>4</td><td>5</td><td colspan="100%">2?</td></tr><tr><td>67</td><td>4?</td><td>2?</td><td>7?</td><td>5?</td><td>4?</td><td>6?</td><td>2?</td><td class="spacer"></td><td>3</td><td>1</td><td>4</td><td>5</td><td colspan="100%">1</td></tr><tr><td>68</td><td>4?</td><td>3?</td><td>5?</td><td>5?</td><td>3?</td><td>3?</td><td>3?</td><td class="spacer"></td><td>1</td><td>3?</td><td>1</td><td>7?</td><td colspan="100%">5?</td></tr><tr><td>69</td><td>2?</td><td>7?</td><td>3?</td><td>1?</td><td>4?</td><td>5?</td><td>2?</td><td class="spacer"></td><td>3</td><td>6?</td><td>4?</td><td>3</td><td colspan="100%">3</td></tr><tr><td>70</td><td>2?</td><td>3?</td><td>1?</td><td>3?</td><td>3?</td><td>3?</td><td>3?</td><td class="spacer"></td><td>5</td><td>2</td><td>4?</td><td>7</td><td colspan="100%">3</td></tr><tr><td>71</td><td>4?</td><td>7?</td><td>5?</td><td>5?</td><td>5?</td><td>6?</td><td>7?</td><td class="spacer"></td><td>1</td><td>7?</td><td>4?</td><td>1</td><td colspan="100%">6</td></tr></tbody></table></div><h2>Scoring</h2>You get 7,000 points for each level and 70,000 points every time you clear the grid. You also get points when discs explode but the number of points depends on the "chain" length of your explosions. The formula for determining the value of a chain explosion is 7*n^2.5 where 'n' is the chain length.<br /><br />Here is a table that shows the value of a disc for a given chain length along with the total score for that chain...assuming only one disc exploded at each level of the chain. The longest chain I have been able to find is x29.<br /><br /><div id="chain_scores_wrapper"><table class="drop7_table" id="chain_scores"><thead><tr><th>Chain<br />Length</th><th>Disc Score</th><th>Total Score</th></tr></thead><tbody><tr><td>1</td><td>7</td><td>7</td></tr><tr><td>2</td><td>39</td><td>46</td></tr><tr><td>3</td><td>109</td><td>155</td></tr><tr><td>4</td><td>224</td><td>379</td></tr><tr><td>5</td><td>391</td><td>770</td></tr><tr><td>6</td><td>617</td><td>1387</td></tr><tr><td>7</td><td>907</td><td>2294</td></tr><tr><td>8</td><td>1267</td><td>3561</td></tr><tr><td>9</td><td>1701</td><td>5262</td></tr><tr><td>10</td><td>2213</td><td>7475</td></tr><tr><td>11</td><td>2809</td><td>10284</td></tr><tr><td>12</td><td>3491</td><td>13775</td></tr><tr><td>13</td><td>4265</td><td>18040</td></tr><tr><td>14</td><td>5133</td><td>23173</td></tr><tr><td>15</td><td>6099</td><td>29272</td></tr><tr><td>16</td><td>7168</td><td>36440</td></tr><tr><td>17</td><td>8341</td><td>44781</td></tr><tr><td>18</td><td>9622</td><td>54403</td></tr><tr><td>19</td><td>11014</td><td>65417</td></tr><tr><td>20</td><td>12521</td><td>77938</td></tr><tr><td>21</td><td>14146</td><td>92084</td></tr><tr><td>22</td><td>15891</td><td>107975</td></tr><tr><td>23</td><td>17758</td><td>125733</td></tr><tr><td>24</td><td>19752</td><td>145485</td></tr><tr><td>25</td><td>21875</td><td>167360</td></tr><tr><td>26</td><td>24128</td><td>191488</td></tr><tr><td>27</td><td>26515</td><td>218003</td></tr><tr><td>28</td><td>29039</td><td>247042</td></tr><tr><td>29</td><td>31702</td><td>278744</td></tr><tr><td>30</td><td>34506</td><td>313250</td></tr><tr><td>31</td><td>37454</td><td>350704</td></tr><tr><td>32</td><td>40548</td><td>391252</td></tr><tr><td>33</td><td>43790</td><td>435042</td></tr><tr><td>34</td><td>47184</td><td>482226</td></tr><tr><td>35</td><td>50730</td><td>532956</td></tr><tr><td>36</td><td>54432</td><td>587388</td></tr><tr><td>37</td><td>58291</td><td>645679</td></tr><tr><td>38</td><td>62309</td><td>707988</td></tr><tr><td>39</td><td>66490</td><td>774478</td></tr><tr><td>40</td><td>70835</td><td>845313</td></tr><tr><td>41</td><td>75345</td><td>920658</td></tr><tr><td>42</td><td>80024</td><td>1000682</td></tr><tr><td>43</td><td>84872</td><td>1085554</td></tr><tr><td>44</td><td>89893</td><td>1175447</td></tr><tr><td>45</td><td>95088</td><td>1270535</td></tr><tr><td>46</td><td>100459</td><td>1370994</td></tr><tr><td>47</td><td>106008</td><td>1477002</td></tr><tr><td>48</td><td>111738</td><td>1588740</td></tr><tr><td>49</td><td>117649</td><td>1776389</td></tr></tbody></table></div><br /></div><h2>The Robot</h2>I should be clear here that the robot I built doesn't make any decisions on its own about where to play the disc, the robot can't see the screen and therefore can't play the game by itself. My Drop7 simulator figured out what sequence to play the discs in to achieve a high score, I just programmed the robot to touch the screen in a specific pattern so that the discs would be played in that sequence.<br /><br /><h3>The Stylus</h3><div>One tricky part of this project was figuring out how to get the robot to touch the screen in a way that would register with the iPad. iPad screens aren't pressure sensitive, they are capacitive screens so you can't just stick a stylus in a robot's hand and have it work. I tried grounding a stylus but that didn't work either. After a bit of googling I found where some people had used frozen sausages as a stylus and that made me wonder if that would work for a robot since it is made of flesh like your finger. I was all out of those little breakfast sausages but I did have some hot dogs in the fridge so I gave one of those a try and BINGO!</div><div><br /></div><div><div class="separator" style="clear: both; text-align: center;"><a href="http://2.bp.blogspot.com/-5JXssfMH1fM/UTa32YhM5kI/AAAAAAAAAo0/WuAfiBpycZk/s1600/hotdog.JPG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="480" src="http://2.bp.blogspot.com/-5JXssfMH1fM/UTa32YhM5kI/AAAAAAAAAo0/WuAfiBpycZk/s640/hotdog.JPG" width="640" /></a></div><br /></div><div><br />Now there are a few downsides here<br /><ul><li>Hot dogs touch a large part of the screen at once compared to a normal stylus</li><li>Hot dogs dry out and the touch doesn't always register</li><li>Your iPad smells like a hot dog at the end of the day</li><li>If you think little kid fingers can make your iPad screen disgusting, try touching it with a hot dog a few hundred times.</li></ul></div>I eventually figured out that when I had tried grounding a regular stylus I wasn't grounding it properly and that is why it didn't work. You have to take the little rubber tip off the end of the stylus, wrap some wire around the metal there, then put the rubber tip back on. Ground the wire and that should do the trick.<br /><br /><h3>Hardware</h3><div>I went through a few different styles of robots before settling on the one used in the video. My original robot is the one you see in the hot dog photo. It had problems consistently dropping discs in column 1 and column 7 though because the angle was so narrow by the time the motor moved the stylus that far to one side.</div><div><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://2.bp.blogspot.com/-etHkYOkwuyY/UTlo2Rdbm3I/AAAAAAAAApU/tc5edcevxAY/s1600/962.JPG" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" height="300" src="http://2.bp.blogspot.com/-etHkYOkwuyY/UTlo2Rdbm3I/AAAAAAAAApU/tc5edcevxAY/s400/962.JPG" width="400" /></a></div>Next I tried building a little rover that would drive forward and backwards to the appropriate column. This wasn't accurate enough though because if the wheels slipped at all it would end up dropping the disc on the wrong column.<br /><br /><br /><br /><br /><br /><br /><br /><br /></div><div><br /><br /><br /><br /><br /><br />I decided I needed a platform that moved on a track so I could get the stylus exactly over the middle of a Drop7 column. I'll post some instructions later on how to build the robot. The only parts I used that did not come with the Lego Mindstorms kit were the gear racks. These were used to move the platform from side to side.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://2.bp.blogspot.com/-V-WJnXBQvFY/UTlpcxC7S3I/AAAAAAAAApc/bgYr_mJVBJw/s1600/976.JPG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="393" src="http://2.bp.blogspot.com/-V-WJnXBQvFY/UTlpcxC7S3I/AAAAAAAAApc/bgYr_mJVBJw/s640/976.JPG" width="640" /></a></div><br /></div><div><br /><br /></div><div class="separator" style="clear: both; text-align: center;"></div><div><div class="separator" style="clear: both; text-align: center;"><a href="http://1.bp.blogspot.com/-0HbL7eTwc7E/UTlp24UxThI/AAAAAAAAApk/wxCb3xiDgqE/s1600/977.JPG" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="300" src="http://1.bp.blogspot.com/-0HbL7eTwc7E/UTlp24UxThI/AAAAAAAAApk/wxCb3xiDgqE/s400/977.JPG" width="400" /></a></div>Here you can see the gear racks underneath the platform. A motor turns a gear which moves the gear rack which in turn slides the platform to the left or right on the track depending on which way I tell the motor to turn. Once the platform is centered over the right column, the motor on top of the platform turns a few degrees to touch the screen with the stylus then reverses direction to pick the stylus up.<br /><br /></div><h3><br /></h3><h3><br /></h3><h3><br /></h3><h3><br /></h3><h3><br /></h3><h3><br /></h3><h3><br /></h3><h3>Software</h3><div>I am completely new to the world of Lego Mindstorms but I have to say it is amazing they are as popular as they are given how horrific the NXT-G software is that Lego provides. It is slow as Christmas, it locks up, it crashes, things that once worked randomly stop working, etc. Needless to say I didn't use it for very long until I started googling for an alternative. I settled on <a href="http://bricxcc.sourceforge.net/">BricxCC</a> which allows you to program Lego Mindstorm in NXC "Not eXactly C". If you have any programming experience at all I would say go with BricxCC over NXT-G, it will save you a lot of frustration.<br /><br />My <a href="https://github.com/dwalton76/Drop7-Sequence-Mode/blob/master/Drop7.nxc">BricxCC code</a> for this project is also on github.</div><div><br /></div><h2>The End</h2>This was a lot of fun. I hadn't written a line of C in 6 years and had never used Lego Mindstorms so I learned a lot via this little project :)<br /><br /><br /></div><div><br /></div>dwalton76http://www.blogger.com/profile/01231435969332456287noreply@blogger.com7tag:blogger.com,1999:blog-3545476513192978628.post-42485285402569943992013-02-26T09:45:00.003-08:002013-02-26T09:45:48.281-08:00I like to do random tech projects and some friends convinced me that I should blog about a lego mindstorms project that I've been working on lately. I'm still working on the mindstorms project but wanted to go ahead and start a blog as a placeholder. More to come later...dwalton76http://www.blogger.com/profile/01231435969332456287noreply@blogger.com0