<![CDATA[Calum McMinn - Game Programmer - Blog]]>Mon, 16 Mar 2020 00:21:20 -0700Weebly<![CDATA[Breakout!]]>Fri, 25 May 2012 11:02:57 GMThttp://www.calummcminn.co.uk/blog/breakoutThere's a new demo on the site! A simple clone of Breakout. When I say simple I really mean simple. This is another programming test and the instructions specifically said not to go above and beyond the requirements since they just wanted to see how I approached the problem so I kept the bells and whistles to a bare minimum. This was pretty handy because I was doing this at the same time as trying to sell all my worldly belongings and get my flat sparkling clean before the landlord's final inspection so I didn't really have time to do much more than the requirements anyway.

Functionally it's pretty much the same as the original Breakout (according to Wikipedia). There's 8 rows of bricks in 4 different colours, one projectile, and one paddle. The projectile's speed increases after the 4th and 12th brick is destroyed and also when the first orange and red bricks are destroyed. The paddle also shrinks to about half it's size when the projectile hits the top edge of the play area. My version is a bit shorter than the original version and only has one level. Since it's just a demo project I want the player to be able to reach the win state fairly quickly. You only get one life in version (as opposed to three in the original) since my version is shorter and multiple lives would make it too easy.

I finished the game in about a day or so and, while the instructions said not to add anything over and above the specification, I wanted to add something to make mine stand out a bit. I remembered playing a version of Breakout years ago on the TV Boy where instead of a ball it was a little man and instead of a paddle it was a see-saw. When the man collided with the paddle it flipped so it looked like the man had catapulted his companion instead of just bouncing. I decided I would skin my game to look like this. It doesn't show anything extra code wise but it will hopefully make it a bit more memorable. Also the only art is stick men which is, thankfully, within my artistic ability. I made a stick man who flailed his arms and replaced the projectile square with him. I also added a fail animation to him where he was upside down with his head all flattened out and arms still flailing since this was always the funniest part of the TV Boy game. I tested it and it looked pretty good and the man colliding with the paddle made the paddle look like a trampoline. I decided that, rather than having a see-saw, I would have 2 men holding a blanket which would bounce the projectile man. This was easy to make and I added some extra animation for the bounce and used a tween for the paddle shrinking to make things a bit smoother. 

Overall, I think it turned out really well. It's a little basic but I guess that was the point. I didn't know when I added it to the site that the background would show up transparent. I could have fixed that but I decided to leave it the way it is. I thought the white background looked a bit rubbish anyway and it looks better with the transparent one.]]>
<![CDATA[Sudoku part 6: The End]]>Fri, 11 May 2012 16:26:53 GMThttp://www.calummcminn.co.uk/blog/sudoku-part-6-the-endSo the sudoku solver is finished. You can download the executable and the project folder from the Demos section of this site. I think it turned out pretty good. It got me into the technical interview stage but, sadly, that's as far as I got. It's all a learning process though so here are a couple of things I think I learned from creating it. 

Robot legs is cool
I'd never heard of Robot Legs before I did this project but, now I know about it, I'll probably use it for most if not all of my ActionScript projects from now on. It was dead easy to use once I got the hang of it and I think it gave my code much better structure than it would have had without it.

Test things. For science.
In future projects, if I can unit test something, then I will. It's a good idea, particularly for working on isolated features that you can strip back to just data in/data out. The parser in Sudoku Solver would have taken me so long to do without unit tests. I did make 2 mistakes in writing the unit tests for Sudoku Solver though, the first was that each test should only have one assert in it. I'd grouped my tests into features so I had one test for the parser that would test the whole thing in one go. This was a mistake, I should have written several tests that each tested one specific part of the parser. This would have made it clearer which part of the parser was causing failures. The other mistake I made with the tests was less a mistake with the test, and more a mistake with the program in general. According to the feedback I received, the solver algorithm wasn't as efficient as it should have been. This probably wouldn't have been very noticeable when running the program normally since the UI will only allow you to solve one puzzle at a time but having a unit test that solved 145 puzzles consecutively really highlighted this inefficiency. I guess it would be a good idea in this sort of situation to have the test output some performance data so I could see where and when it was being slowed up. It's not just about whether the test passes or not. ]]>
<![CDATA[Sudoku part 5: Solve ALL THE PUZZLES!]]>Mon, 07 May 2012 18:12:58 GMThttp://www.calummcminn.co.uk/blog/sudoku-part-5-solve-all-the-puzzlesFirst thing I needed to do today is solve the bug from yesterday. I followed it through the debugger again, now bright and alert in the new day, and discovered that sleepy stupidity was indeed a problem last night. I had my trace statement saying which puzzle the program was solving on the wrong side of the solve call so I was following through puzzle 5 when it was puzzle 6 that was crashing. That explains the mysterious transforming worksheet.

Now that I was looking in the right place, I found that my search algorithm wasn't bailing out when it failed to assign a value. I added a simple null catch to do this and was rewarded with an endless loop instead of a crash. Baby steps. 

The endless loop was caused, unsurprisingly, by the while loop. I had thought that the search algorithm would always find a value to put in the cell it was searching but this is not the case. Sometimes it just doesn't know enough about the puzzle yet to eliminate all the possibilities. In this situation the search is meant to fail and the program should move on to the next cell. The cell it failed on will be filled later as a result of the constraint propagation. My search method was running a while loop until it found a value for that cell, which was never happening.

I fixed this problem by scrapping the method that was attempting to assign all values to the cell and moved that loop into the main search function. I created an array and, for each possible value of the cell, I ran the search method passing in a copy of the worksheet with that value assigned to it. The result was pushed into the array. If the program failed to find a definite value then the search function would return null and that would be pushed into the array. Since this was a fixed loop there was no danger of getting stuck. Once it had the array of solutions, it passed them into another method which would return the first non-null element of the array. The cell in this Puzzle object will have the correct value assigned and so is returned. If there was no valid solutions in the array then the search fails and returns null. This cell will be filled in later with constraint propagation.

Now that I'd fixed my bug I was ready to run my mega, 145 puzzle long, unit test again. I did, and it passed. I take this as proof that I have solved ALL THE SUDOKU PUZZLES IN THE WORLD!

With the main algorithm finished, I went back to working on the UI and wrapper stuff. I added a save button which would run let the user pick a save destination and write the export JSON to a file there. Nothing new here since it worked pretty much the same as the load button. I added some error handling to stop it crashing if it reads in something that isn't a sudoku puzzle and also to stop it crashing if the sudoku puzzle is deliberately invalid (for example one with given values that conflict with each other). This works by simply failing out if the pure string representation of the puzzle doesn't have 81 characters. The parser already strips out all characters that aren't numbers so if it were to come across a sudoku puzzle with letters or something instead of numbers the resulting string would be shorter than it would expect. The solver method already has several places where it will fail out if it finds conflicts between the numbers themselves so that will handle any deliberately invalid puzzles. I also moved all the calls to Alert.show() out of the PuzzleModel and into a Command since I felt it would be good practice not to have the PuzzleModel doing anything the user can see. I moved the buttons around a bit and lined them up with each other. I picked a nice background colour. To be honest I think I'm running out of things to do. 

I hesitate to call the program finished. It's only 8pm on Monday and I don't have to hand it in until Thursday. It's true I did crunch pretty hard over the last few days working on this but I think there must be other things I can do, I'm just not sure what. The interface is as polished as it can be when it's so simple and the algorithm itself is as efficient as I can see how to make it. I think I'll get someone else to look at the code and the application and see if anything occurs to them that it's lacking. If not then I guess I'll just hand it in. Maybe there's bonus points for handing it in early. ]]>
<![CDATA[Sudoku Part 4: Attack of The Clones]]>Mon, 07 May 2012 00:39:09 GMThttp://www.calummcminn.co.uk/blog/sudoku-part-4-attack-of-the-clonesNow that my program can solve simple puzzles, I need to make it solve more difficult ones. I'm going to do this by implementing a search function that will go through all the cells that don't have a definite value yet, and try assigning each of the possible values to that cell and see what sticks. This sounds like it would be incredibly inefficient but its actually not if I use the assign/eliminate methods from before. 

So, if all the given values have been assigned to the worksheet and the puzzle still isn't solved, it executes a search. The search algorithm took me a long time to get my head round, again because I struggled to understand the Python examples, but now that it's written it's actually pretty simple. Well actually I don't think it's simple, just short. Who would have thought 20 lines of code would give me such a headache!

It starts by getting the key of an unsolved cell. This could be any cell but it's more efficient if it uses the one with the fewest possible values since then there's a better chance of getting it right. I added a method to Puzzle (my extended dictionary class that I use to store the values) that would return the key of the cell with the lowest number of possibilities. If a few have the same number it just returns the first one it finds. Once the search function has its key, it runs another function which, for each possible value, creates a clone of the worksheet and tries assigning that value to it to see if it works. If it doesn't find any conflicts, it returns that clone of the worksheet. It then passes that clone into the search function (Whee! More recursion!) and does it all again. The clone it passed in has had one of its cells solved so the getUnsolvedCell method will bring back a different answer from the first time. The function keeps drilling down until the getUnsolvedCell method brings back nothing, which means there are no unsolved cells left. At this point the most up to date clone of the original worksheet bubbles all the way back up the stack as the completed solution.

Since this method involves operating on clones of the worksheet I had to go back and alter the assignNumber and eliminateNumber methods so that they take in a worksheet to operate on as a parameter and pass it back out as a return value once they're finished with it. For the first part of the solver (before it starts searching) they just receive a reference to the global worksheet variable.

I must have spent hours trying to figure out exactly how to write this search algorithm. The recursion was just tying my brain in knots. Eventually I just wrote something and ran it with the intention of using the error message to try and understand exactly what it was doing. To my absolute astonishment it solved the puzzle without any problems. I was totally not expecting that and still didn't really have a firm grasp on what exactly was happening in the depths of the recursion. Now that I've written down an explanation of what the algorithm does on here though, I have a much better understanding of how it works. I guess this is one of the reasons people keep blogs about their programming projects. 

Now that I've got a program that can, in theory, solve any sudoku puzzle, I need to put it through its paces. This means more unit tests! I downloaded a list of 50 easy sudoku puzzles and 95 hard ones from the internet and wrote a test that would read them all in and try to solve them. The easy and hard puzzles were in different files and formatted in completely different ways so I needed to write a test for each of them. I've written a the test for the easy one which reads in the file, parses all the puzzles into separate strings, and feeds each one to the solver. Sadly things did not go well. It crashed on puzzle number 5 with a null reference exception that was occurring about 4 recursions deep in the search method. I found that there was a point when the clone being passed into the assignAllValues method was null. Why it was null, I had no idea. I couldn't understand why this would work for the previous 4 puzzles and not this one. I followed it through the debugger and found that, at one point, one cell had "45" as its list of possible values when one of its peers had already been assigned the value 4 as its starting value. This is totally confusing me because this situation should be impossible. The assignNumber and eliminateNumber methods should eliminate a value from all the peers of a cell once that value has been assigned to it. I put in another breakpoint and followed it through again. Luckily the cells that were conflicting were A6 and A8 so i didn't have to wait long for the situation to arise. I followed the debugger as it assigned 4 to A8, as given by the original puzzle, and watched as it eliminated 4 from the possible values of A6. All is in order. I let it run a few more loops and saw that everything was still fine. The possible values for A6 still didn't contain 4. I then stepped out of the initial assigning phase and let it run until it was ready to start the search algorithm. I checked on the worksheet again and found that 4 was back in the possible values list! I also noticed that A8 didn't have a definite value anymore! What the hell is going on here? I watched this thing assign those values! Where did they go? My gut feeling is that something has gone wrong with one of the clones (as so often happens when creating an army of clones). I haven't tried running the puzzle in question through the solver without it being part of my big 50 puzzle unit test yet either so it could even be a problem with the test rather than the solution. This is going to be the first thing I try tomorrow. Hopefully it's something simple and I just can't see it because it's so late at night. ]]>
<![CDATA[Sudoku part 3: Rules are made to be forgotten.]]>Sat, 05 May 2012 23:47:47 GMThttp://www.calummcminn.co.uk/blog/rules-are-made-to-be-forgottenIt works! It solves puzzles! Victory! Well not quite yet but it's a big step in the right direction. 

The article I mentioned in my previous post said that there are 2 rules for solving a sudoku puzzle.
1. If a cell has only one possible value, then eliminate that value from the cell's peers.
2. If a unit has only one possible place for a value, then put that value there.
So, as an example of rule 1, if we know that cell A3 contains a 7, we can eliminate 7 from the possible values of A3's peers (A1, A2, B3, etc). We may find that after eliminating 7 from all those peers that one of them has only one value left so we can then remove that value from all it's peers. We can keep recursing through the puzzle until all the cells have only one possible value in which case the puzzle is solved!

My parser for reading in JSON puzzles stored blank cells as "0" rather than lists of potential values so I needed to change this before I could go any further. Easy enough. After working on the algorithm for a little while though I realised you really need to have the entire puzzle made of blank squares and then assign the certain values afterwards, checking for potential eliminations as you go. I therefore changed my parser back to the way it used to be and added another Puzzle object called worksheet which was filled entirely with blank values (or complete lists of potential values if I'm being precise). Worksheet would be the puzzle I actually change and would be the one that gets exported as the solution.

I then tried to implement the first rule which I found quite a challenge. The example I was following along with was in Python (which I have negligible experience in) and the author really loved his single character variable names. This meant I kept running into phrases like "d2=[s for s in u if d in v[s]]" which made me go "Whaaa?". I wrote out the example on paper in ActionScript style pseudocode to try and get a better understanding of exactly what it was doing and this helped a bit. The end result is 2 methods called "assignNumber" and "eliminateNumber".

The program iterates through the puzzle and, for every cell that isn't blank, calls the assignNumber method and passes it the key of the cell and the value to assign it. The assignNumber method then iterates through all the potential values for that cell (excluding the one looking to be assigned) and attempts to eliminate them one by one by passing them to the eliminateNumber method.

The eliminateNumber method removes the number to be eliminated from the worksheet cell. If this leave only 1 value in that cell then it know for sure that this value is correct for that cell and it will call the eliminateNumber method on all of that cell's peers. A lot of recursion happens here. 

When I fed a simple puzzle into the program it keeled over with a stack overflow. This confused me since it was obviously caused by too much recursion and this whole theory was based on recursion. I stepped through the whole thing with a debugger to try and see where it was getting stuck and I eventually found that it was due to me not updating the worksheet as I went. The python example did all its operations during the elimination method on the worksheet directly. This made me nervous since there were several places the method could bail out if it found something problematic (like finding there was no place on the grid to put a certain number). I didn't want it to remove any numbers from the worksheet before it was sure that was the right thing to do so I had it copy the potential values for a cell into a seperate array, do all its operations on that, then copy them back into the worksheet once it was done. This turned out to be a mistake since it caused this endless loop of recursion. Basically what happened was it would assign the value 5 to cell A1 and would therefore iterate through all the peers of A1 and eliminate 5 from their potential values. While doing this it would discover that after eliminating 5 from the potential values of A3, that it only had the value 2 left. It would then recurse into all the peers of A3 to eliminate 2 from all of their potential values. One of the peers of A3 is A1 which only had 2 and 5 as potential values (5 was still there since I hadn't operated directly on the worksheet and instead operated on a copy). Once 2 was eliminated 5 was the only value left so it recursed into A1's peers again to go and eliminate 5 from all of them meaning it found A3 again and discovered it only had 2 left so it recursed into all of its peers again and so on until it caused a stack overflow. Changing the eliminateNumber method so that it operated directly on the worksheet fixed this problem and, in hindsight, my worry about it removing a value it shouldn't was a silly one. The method will only bail out if there is a fundamental problem with the puzzle that would render it unsolvable, in which case the whole thing would be stopping anyway so who cares?

Once that was fixed I fed in the simple puzzle again and BING! Solved! Awesome! 

But wait... I forgot to implement rule number 2! If my algorithm can solve sudoku puzzles with just one of the rules implemented, what's the point in implementing the second? I wondered if it would maybe solve puzzles more efficiently by using 2 rules rather than just one so I went ahead an implemented the second rule. 

This involved looping through each unit that the cell in being assigned to was a part of, and then for each cell in that unit, seeing if the potential values for that cell contained the number being eliminated. If it did, then that cell was added to an array of potential places to put that value. If, after checking every cell in the unit, there was only 1 element in the potential places array, then the program knows that the number being eliminated belongs in that cell and will assign it there with all the eliminations and whatnot that that involves. 

I wasn't sure exactly how to check if adding the second rule made the program any more efficient. I added a counter to count how many times the eliminate method was being called since that was the only method I thought might get fewer calls if the algorithm was more efficient (the other methods were on fixed loops so wouldn't change). This didn't prove anything however since it actually called the eliminate method more times with 2 rules active than just the first one. I still don't know what advantage the second rule is giving me but I decided to just play it safe and leave it in there. I'm sure it wouldn't be a rule if it wasn't required. 

So far, my program can only solve deterministic puzzles (puzzles with only one solution). If I feed it an non-deterministic puzzle then it will leave a lot of cells with multiple possible values still in them. To make it solve more complex puzzles I need to have it use a form of search once it has exhausted the assign/eliminate method. This will be what I try to tackle tomorrow. 
<![CDATA[Sudoku part 2: Things go loopy!]]>Fri, 04 May 2012 23:53:26 GMThttp://www.calummcminn.co.uk/blog/sudoku-part-2-things-go-loopyThere was less progress than I would have liked today. There was a ton of other stuff demanding my attention so I only managed to squeeze in a few hours on this but stuff is coming along nicely all the same.

Today I was planning to start writing the algorithm that will actually solve the a sudoku puzzle. Before I could do that though, I needed to write the function to export the completed puzzle to JSON and a unit test to make sure that it worked. I need to export the puzzle to JSON before I start the algorithm so that the algorithms unit test has something to read and compare to. Writing the exporter wasn't really complicated since it was just the importer in reverse. There was a bit of faffing about getting it to put commas in the right place but nothing too problematic. 

Next step was really understanding exactly how the algorithm is going to go about solving the puzzle. I read an article describing the process and found it a little mind bending. The article's examples were in python which I have negligible experience in so that probably didn't help. It became clear after I'd had a read of this article that my current method for storing puzzles wasn't detailed enough. I'm still storing it in a dictionary but I need to store a list of units and peers for each cell too. Units and peers are, apparently, the accepted terminology among sudoku enthusiasts. A unit is a row, column, or square where each number (1-9) will appear once. The goal of sudoku is to populate each unit with unique numbers. Peers are the cells contained in the units a particular cell is connected to. For example, the peers of cell F5 would be all the cells in row F, all the cells in column 5, and all the cells in the centre square.

Populating the units and peers was a bit of a headache. I thought it sounded simple, and it sort of was, but I couldn't figure out a way to do it without just going mad with for loops. In the end I just had to take the loopy approach (which involves 4 loops nested inside each other) because I couldn't see any other way round it. I suppose it's not a big deal since none of the loops are particularly long so there wont be a noticeable performance hit, but the test is being marked on efficiency so I was hoping to avoid too many nested loops. The end result is an array of all units and 2 dictionaries to store the units and peers for each cell. I considered not storing the units and cells in separate data structures and instead having getPeers and getUnits methods that would return the peers and units of a specified cell. I soon realised that this would be inefficient since it would mean the program did all the crazy looping every time it ever needed a peer or unit, and from the looks of the theory it will need those quite a lot.

The allUnits array holds all the different units on the grid (all rows, all columns, and all squares) and is populated by looping through each row and making an array of all the columns in each row, then looping through the columns and making an array of all the rows in each column, then looping through 2 extra arrays that define the squares and adding all of those cells to an array (this is the loop that goes 4 nests deep), then putting all those arrays into another array! This gives us an array of 27 unit arrays each containing 9 cells. 
The units dictionary uses cells as keys and stores the 3 units that cell is a part of. It's populated by looping through the keys of the puzzle dictionary and, for each key, looping through all the units in allUnits and storing the ones that contain the key.

The peers dictionary is just the units dictionary again, except each entry only contains 1 array rather than 3 and there are no duplicate cells. For example, F4 will appear in the units for F5 twice (once in the F row and once in the middle square). The peers dictionary removes all the duplicates, and the references to key cell. It's populated by concatenating the 3 arrays from that cells units dictionary entry, filtering them to remove duplicates, then splicing out the key cell. Simple stuff!

The next step is to actually implement the solving algorithm (I know i said that last time too). Now that I've got the units and peers stored in an easy to access way I can use that to eliminate the possible numbers that can go in any given cell. More on that next time!]]>
<![CDATA[First! (and the Sudoku project)]]>Thu, 03 May 2012 19:14:21 GMThttp://www.calummcminn.co.uk/blog/first-and-the-sudoku-projectI have a blog! I've never had a blog before since I suspected I'd never update it. We'll see if I was right!

The Sudoku Project:
I've been asked, as a programming test for a potential employer, to create an ActionScript project that can read in a sudoku puzzle from JSON, solve it, and spit it back out again in JSON. I've got a week to do it so I'm going to try and do a blog post every day until I hand it in.

First thing I needed to do was get my head around Robot Legs. I heard Robot Legs was the way to go for this test but I'd never used it (or even heard of it) before now so I needed to get up to speed on exactly what it does and how I use it. Robot Legs is rather nice MVC framework for ActionScript. It's all about keeping your code modularlised and communicating through events rather than direct interaction. It took me a couple of hours to get my head round exactly what should be sending events and what should be listening for them but I reckon I've got it nailed now.
I've got a Model called PuzzleModel which stores the data for the sudoku puzzle that's currently loaded. PuzzleModel also handles the parsing of the puzzle from JSON and will be the one to do the actual solving of the puzzle (once I've written that). The puzzle itself is stored as a Dictionary with its keys in the format "A1", "A2", "B1" and so on. The Best Practices doc for Robot Legs made it pretty clear that you should never, under any circumstances, let a model listen for events so I've rigged up a couple of Commands to tell it to start parsing and to start solving. The loading is handled by another class IOManager which reads in JSON from a file and hands it over to PuzzelModel for parsing. IOManager will also handle saving the completed puzzle out to JSON. I didn't have to code very much for this since the Scenery Editor tool I wrote for Secret Island had all the file handling I need already so I was able to lift the functionality and pretty much just drop it straight into this.

 I've also got 3 Views written in mxml and corresponding Mediators for each component in the UI. So far that's a button to load a JSON file, a button to solve the puzzle (which currently does nothing), and a nice display for the puzzle. The display is fairly basic and looks more or less like what you'd expect a sudoku puzzle to look like. The numbers are just labels with names like "lblA1" which I populate by iterating through the puzzle dictionary and building their name out of "lbl" + the key.

One more thing, Unit Tests! I claim to have experience in these, and that's true, but it's reluctant experience. I only made them when I had to and really didn't think they were overly useful. This project has changed my mind though! I  have a unit test for the parser and it made things so much easier than having to load in a file every time. If you're reading this Rune, you may say "I told you so". I think I'm finding them more useful here because this is much more of a data-in-data-out type of project where as Secret Island was much more visual and unpredictable which made it hard to test.

Now that I've got the groundwork done and can read in a puzzle and see it I'll start working on the actual meat of this problem: the solving of the puzzle. I'll confess I'm not an avid sudoku player, I'm not even sure if I've even done one before, but I know the theory so I think I'll be fine. I had a look online and got some tips on how you go about methodically solving one and I reckon I'll be able to get my flash program to do the same thing. That's tomorrow's job!

Puzzle looks funny if you type it over and over.]]>