Finding External Tangent Points for Two Circles

September 12, 2012

[Update: 10-21-2012: The geometry discussed in this post has been superseded by the discussion about path planning for Dubin’s Cars:] I recently had a geometry problem I needed to solve involving finding tangent lines to two circles. If you’re like me, you don’t remember all the geometry you learned in school. And if you’re like me, you prefer searching the internet for answers versus turning to your books. I looked and looked online, but couldn’t really find a satisfying guide on finding the tangent points for two circles. Right now, even the Wikipedia page is a mess. How exactly does one “equate theta” and then “add x-y coordinates of a triangle” to a point? Perhaps in the future this will improve, but for now, here’s how I figured it out. I’m only going to run through finding one external tangent point. Figuring out the others as well as the tangent lines should become trivial afterwards.

Read the rest of this entry »


Decision Tree Learning

March 3, 2012

Which one is edible?

(Image from

Let’s say you want to learn how to classify something, but the ‘rules’ behind the classification are not obvious. For example, given some measurements about a person’s heart, can we tell if they have heart disease? What if you are hiking through the woods and want to know if a mushroom you see is edible or not? Perhaps the stem has a certain color, the head is a certain width, or it has a ‘curtain’ around it. Instead of spending years mastering which mushrooms are edible based on sight, how about you simply get a computer to tell you? Well, with decision trees you can!

Read the rest of this entry »

Solving Sudoku, Revisited

June 16, 2011

Thanks to Scott Y’s comments in my article regarding a Sudoku Solver I wrote as part of an AI project, I decided to write a real solver that not only can solve any Sudoku puzzle, but can do it in just a few milliseconds.

Long story short: I represented Sudoku as an exact cover problem, then used Donald Knuth’s Algorithm X and Dancing Links implementation to solve that exact cover problem. Still here? Good, it’s time for me to explain a few things.

(Update October 2013: This project is available on GitHub!)

Read the rest of this entry »

Think You’re Good At Mario?

March 10, 2011

Update: I will be presenting the results of this research at MAICS 2011 as well as UD’s Stander Symposium 2011!

In August 2009, Sergey Karakovskiy and Julian Togelius held a competition on behalf of the ICE-GIC (IEEE Consumer Electronics Society Games Innovation Conference) for contestants to build a soft-bot that played Super Mario.

The Super Mario Engine they used was a modified version of one built in Java by the one and only Markus Persson , a.k.a. “Notch” of Minecraft fame. The Engine is named Infinite Mario Bros., and is still playable online for free. Entrants into the competition had to build an agent who would tell the engine Mario’s next move every 40 milliseconds.

The competition was held in 2009, and again in 2010. Robin Baumgarten won this competition with his bot, AStarAgent, both years. I stumbled upon this competition in late August 2010 and was immediately intrigued. I had wanted to build an agent that played a known game –any game, really—for some time. A modern first person shooter like Halo or RTS like Starcraft would be mind-blowing, exciting, and most of all, recognizable to family and friends.

Read the rest of this entry »

Using Profile Information on a Base Page in ASP.NET

December 8, 2010

Recently I was attempting to code a base page in an ASP.NET project because I decided it would make future upkeep easy, and it was good practice to learn. What I wanted to do actually was set a page’s theme based on an entry in their profile, PreferredTheme. The thing is, I kept getting slammed by System.Configuration.SettingsPropertyNotFoundException errors and for the life of me couldn’t find much good information on the web. After piecing together things here and there, I’ve figured it out and thought I’d share it here in case somebody else has the same problem.

Read the rest of this entry »

Why You Should Embrace the Principle of Locality

November 22, 2010

The principle of locality states that in computer systems, data that has been used recently will likely be used again soon, or if a particular location in memory was needed recently, it will likely be referenced again soon. In more general terms, we could state the principle of locality as “What has happened recently will likely happen again.”

But how does this help you?

Read the rest of this entry »

Discount Stack Overflows

July 20, 2010

If you’re sick of paying through the nose at your local Wal-Mart or Best Buy on ways to overflow your stack, you could be saving hundreds by just doing it yourself! While working on a recent project I accidentally made a very rookie mistake when creating a recursively called Depth First Search function that resulted in overflowing the stack from too many function calls.

Read the rest of this entry »

A Robot to Solve Rubik’s Cube

May 3, 2010


For a fun little final project in my AI course, the class was split into teams that were to take a Lego Mindstorms NXT 2.0 robot kit and build a creative robot to do…something! Really, it was a cool way to finish a really interesting course. There were robots that could walk to a bucket and sort colored balls, one to traverse a maze, one that transforms from a rover into a walker…. and ours, which solves Rubik’s Cubes.

Read the rest of this entry »

What’s Wrong With This Code?

March 29, 2010

I meant to include this in my post about Building a DNS Resolver, as it is a small, yet significant bug that took me a little while to find. What the code should be doing, is reading a string from a file (where all strings in the file are guaranteed to be 255 characters or less), then pushing that string into a Queue. So before you jump to the whole article, can you see what’s wrong with the code?

Read the rest of this entry »

ASCII Hangman

March 29, 2010

Back in late 2007 I was fresh out of my freshman year of a computer science degree, and thought I knew C++ well enough to build another game. The “Haunted House” game took forever to build and was full of bugs at first, but that was a full semester of classes ago. Now I was ready to make another game, also I was bored and wanted to stay sharp, so I built an ASCII-art Hangman game.

(Update June 2013: The original source code is now available on GitHub! Feel free to download and play with it!)

Read the rest of this entry »