This blog has moved!!

I've decided to move the blog, as well as a description of all my projects to a dedicated site: FrozenFusion.net

Come check it out!

Testing for line segment intersection in 2D - a pedestrian approach

For the collision engine in a 2D game I've been working on, I often find myself needing to know whether or not two line segments intersect. A quick google search showed plenty of fancy approaches, but since I just want something quick, understandable and reliable, I went the high school math route.

First, the problem: given two line segments L1 and L2, (a) do they intersect? (b) if so, where?

Before the algorithm we have to choose how we represent our lines. I prefer defining a line segment by two points:
$p_1=\left(x_1,y_1\right)$ $p_2=\left(x_2,y_2\right)$
This is a totally fine way of representing a line or a line segment. Another way of writing a line is:
$y = mx+b$
where the slope m and intercept b are related to our points as in the diagram below.

A disadvantage of writing the line as a function of y is that a vertical line (with equation x=const) can not be represented in this manner. If we're working with this form we have to consider vertical lines separately, which is a bit of a bummer, but amounts to a mere if statement or two.

Simple example: infinite lines

It helps to first consider the case of two lines. As drawn below, if the slopes of the two lines are equal, they always intersect at a unique point. If the slopes are equal, the lines do not intersect unless they are the same line, in which case (almost by definition), they intersect everywhere.

The algorithm for finding the intersection is then as follows:

// Simplest case:
double m1 = (L1.x2-L1.x1)/(L1.y2-L1.y1)
double m2 = (L2.x2-L2.x1)/(L2.y2-L2.y1)
double b1 = (y1-m1*x1)
double b2 = (y2-m2*x2)
// If the slopes are equal, they only intersect if the lines are equal
if(m1==m2)
{
   if(b1==b2) return L1;
   else return false;
}
else
// otherwise the lines intersect at a point 
{
   double xI = (b1-b2)/(m2-m1);
   double yI = m1*xI+b1; // or m2*xI+b2 … same thing.
   return return new Point(xI,yI);
}

Modifying for segments

Modifying for line segments is a straightforward extension: first, we check for the collision coordinates as above, then see whether or not the the point is on one of these lines. This amounts to asking if the x-point of collision xI is within the region of x points of either line segment:

// Modify for segments
if(lineCollision) // as before
{
   if ((xI >= lx1 && xI <= rx1) && (xI >= lx2 && xI <= rx2))
   {
      collision == true;
   }
}

Crossing the t's and dotting the ... lower case j's

If we're dealing with floating point numbers, I find it best not to use strict equality because successive mathematical operations can lead to slight round-off error and you wind up with things like (49.99999999999999999999 == 50) = false, which in our program, should be true. This can be easily accounted for by checking if values are within some small threshold delta. To do this replace:

if(L1.x1 == L1.x2) 

… with:

if(Math.abs(L1.x1 - L1.x2)<delta) 

The code above will fail either of the line segments are vertical. This is easy to fix, but takes a few extra lines of code before the previous case:

// First check for vertical lines
if(L1.isVert()&&L2.isVert())
{
   if(Math.abs(L1.x-L2.x)<delta) // they're the same line
   {
      if(L1.y2 > L1.y2 && L1.y1 < L2.y2) // they intersect
      {
         collision = true;
         // xI,yI are on L1,L2
      }
   }
}

else if (L1.isVert())
{
   xI = L1.x1;
   yI = m2*xI + b2;
}
else if (L2.isVert())
{
   xI = L2.x1;
   yI = m1*xI + b2;
}

where,

public boolean isVert(Line L1)
{
   return(L1.x1-L2.x2 < delta)
}

Finally, int the case of collinear segments, the intersection occurs not at a point, but over a smaller line segment itself. For my purposes I only care that the segments overlap at least at a point, but we can easily extend the code to give the segment of overlap:

public boolean isVert(Line L1)
{ // This assumes that x1<x2, y1<y2. 
// If not, define x1s = Math.min(x1,x2);x2s = Math.max(x1,x2); etc…
// if colliding and collinear as before
double xL = Math.max(L1.x1,L2.x1);
double xR = Math.min(L1.x2,L2.x2);
double yL = m1*XL+b1;
double yR = m1*XR+b1;
return new LineSegment(xL,yL,xR,yR);
} // and similarly for horizontal and vertical lines

The Code in Action

I wrote a quick demo program for this code which can be found here. An executable jar file for the code is here if you want to play around with it. A video of the demo program is displayed below.

Arduino Round V: Light Seeking Robot

Having received a stepper motor in the mail the other day, I started playing around with the built in stepper motor library, "stepper.h". Using a dual H-Bridge drive that can source and sink current

Stepper motor(768, in1Pin, in2Pin, in3Pin, in4Pin); // These pins are the outputs from the arduino. '768, refers to then number of steps per full motor rotation
motor.setSpeed(speed); // After about a speed of 20, it barfs
motor.step(N); // With a bipolar driver, a positive or negative N can be used for clockwise/counter clockwise rotation

The project I decided on to have a little fun with the motor was a "light-seeking robot". The robot would have a left and right eye (photoresistors) and would rotate via the stepper motor until both eyes measured equal brightness.

To accomplish this, we can subtract the right-eye's voltage from the left-eye's voltage to for an error signal. If there is more light to the right than to the left, a positive error signal results and the motor turns right. If the left side is brighter, the difference is negative and the motor turns left. At some point, the difference goes to zero at which point the motor doesn't turn at all. Furthermore, as the balance gets better, and the difference gets smaller, the robot slows down and smoothly approaches the Goldie-Locks amount of light on each eye. On the other hand, when the balance is way off, the error signal is huge and the motor corrects more strongly, a situation known as proportional feedback. If the motor had some inertia we'd have to add a little lag (integration) to the loop so that the robot didn't overshoot when it got to zero and oscillate back and forth but for a stepper motor, which is heavily damped, this is not a problem.
 
The eyes of the circuit are shown here: the photodiodes each are part of a voltage divider which go to separate arduino inputs. The eyes are attached to a decapitated lego figure (you gotta use what you got) whose rectangular feet fit nicely into the stepper motor.

The motor is driven by the following code:

#include "stepperh.h"

int in1Pin = 4;
int in2Pin = 5;
int in3Pin = 6;
int in4Pin = 7;

const int LEFT = A0;  // Analog input pin
const int RIGHT = A1;  // Analog input pin
int vL = 0;
int vR = 0;

int j = 1;
int m = 1; // polarity. If turning the wrong way, switch sign
int speed = 20;

Stepper motor(768, in1Pin, in2Pin, in3Pin, in4Pin);

void setup()
{
  Serial.begin(9600);
  pinMode(in1Pin, OUTPUT);
  pinMode(in2Pin, OUTPUT);
  pinMode(in3Pin, OUTPUT);
  pinMode(in4Pin, OUTPUT);
  pinMode(LEFT, INPUT);
  pinMode(RIGHT, INPUT);  
  
  motor.setSpeed(speed);
}

void loop()
{
  vL = analogRead(LEFT); // 0-5v <-> 0-1023
  vR = analogRead(RIGHT); // 0-5v <-> 0-1023
  Serial.print("Left = ");Serial.print(vL);  // Log the measured values for debugging
  Serial.print(", Right = ");Serial.print(vR); 
  Serial.print(", Difference = ");Serial.print(vR-vL);
  Serial.print("\n");
  motor.step(m*(vR-vL));
  delay(250);    // update at 4 Hz
}

The circuit layout is sketched here:

... and here's a video of the light seeking robot seeking light:

Arduino Round IV: A Simple Character LCD

Right after I got my clutches on the Arduino, I ordered a bunch of stuff to connect it to, including a few stepper motors and an LCD. Well, today the LCD came and I whipped together a very simple, and somewhat stereotypical project - a light/temperature sensor. The circuit monitors the light incident on a photoresistor much like the python GUI a couple posts back, as well as the temperature via a Analog devices TMP36 sensor that I got from Adafruit industries.

The LCD I used was a HD44780 compatible 4x20 character LCD that I got on the cheap from an overseas shop called seeed studia bazaar. It shipped from China so it took a couple weeks and shaved a few bucks - in the future I'd probably spend another $2 and get it overnight from somewhere a little more local.

The first chore is to hook up some solder pins to the LCD board which allows you to stick the LCD module into a solderless breadboard. With my $10, 10 year old soldering iron that I got from Walmart back in the day this was more painful than it needed to be.

Now that we can access the pins, the pin layout is as follows:

To do a basic test of operations, we can start by powering the module up and verifying that it works. Pins 1 and 2 power the unit, 15 and 16 power the back light, and pin 3 sets the LCD contrast. The datasheet for the LCD recommends a 5k potentiometer between pins 2 and 3 to set the contrast, but this could be replaced with a voltage dived from the voltage pin or a PWM output, directly from the Arduino. I found that a good value to sent to pin three was around 900mV. Here a picture of the"first light" of the project. The inset is what the screen looks like with 900mV contrast setting (my poor photography couldn't capture the bright backlight and the circuit simultaneously.)

Next, we need to hook up the data bus: for regular 4 bit operation, pins 11-14 receive information, which we can hook up to Arduino outputs 9-12. We also need to tell the LCD module three things:

1. Whether the data being received are instructions or data to be displayed. This is selected via the register select (RS) pin 4. The Arduino Liquid crystal library which is to be used takes care of that, but for now, send an Arduino output port (4, say) to RS.
2. Whether we are writing data to (5V) the chip or reading from it (GND). This is pin 5, R/W. Since we're only writing to the chip, we'll just clamp pin 5 to ground.
3. Data enable (pin 6) which gates the unit for receiving data. Connect this to Arduino pin 5.

 Once this is done, we're ready to write a quick lil' arduino program to display some text. The program, shown here loads teh liquid crystal library, initializes the LCD and draws some text. That's it.

#include 

// Connections:
// rs (LCD pin 4) to Arduino pin 4
// enable (LCD pin 6) to Arduino pin 5
// LCD pins d4-d7 to Arduino pins 9-12
LiquidCrystal lcd(4, 5, 9, 10, 11, 12);
void setup()
{
  lcd.begin(20,4);              // Initialize a 20x4 HD44780-compatible LCD
  lcd.clear();                  // clear the screen
  lcd.setCursor(0,0);           // set cursor to column 0, row 0 (the first row)
  lcd.write("The Rules:");      // Write text, starting here
  lcd.setCursor(0,1);  
  lcd.write("1. Don't harm humans");
  lcd.setCursor(0,2);  
  lcd.write("2. Obey human orders");
  lcd.setCursor(0,3);  
  lcd.write("3. Protect yourself");
}

void loop()
{
} 

The result, as well as the wired circuit being:

OK, now that we can write to the device, let's make it slightly more interesting by adding some real time data. We'll monitor the voltage across a photoresistor by placing it in voltage divider configuration and sending it to Arduino input pin A0. The luminosity is in arbitrary units since I have no idea what either the spectral content of the light in my living room is or what the spectral response of the photoresistor happens to be. We will then just output the brightness in arbitrary units with the understanding that the bigger the number, the brighter the environment. I also placed a capacitor in parallel with the second resistor to ground to smooth out the readings a bit. Not really necessary but it makes the look and feel a little nicer. As for the temperature, when pins 1 and 3 have 5V across them, pin 3 holds a voltage which is linearly related to temperature. The datasheet gives a graph which seems to state: $V_{out} = 10\frac{mV}{^\circ C}T+500mV$.

We can then invert this equation to find the temperature in Celcius is $T_C=50\left(2V_{out}-1\right)$ where $V_{out}$ is measured in Volts. The wiring for the sensors is sketched here:

In the Arduino code, we simply poll the input pins each loop and display the converted quantities. One final quirk - there is no degree sign that I could find in standard ascii. Luckily, the LCD allows you to program your own characters. This is a relief since it allows me to avoid using Fahrenheit. To build your own character, you just treat each row of 5 as a 5-bit binary number, with 1's where you want a pixel lit. There is a nice tool on the web which allows you draw your own character and it gives you the resultant binary number array. That's all we need. The code is:

#include 

// Connections:
// rs (LCD pin 4) to Arduino pin 4
// enable (LCD pin 6) to Arduino pin 5
// LCD pins d4-d7 to Arduino pins 9-12
LiquidCrystal lcd(4, 5, 9, 10, 11, 12);
// Input pins
const int LIGHT = A0;
const int TEMP = A1;
// Varibales to store temperature value
int tmp = 0;
// To hold text strings
char tVal[4];
char lVal[4];
// Create custom "degree" character pixelmap
byte deg[8] = {B110,B1001,B1001,B110,B0,B0,B0};
void setup()
{
  // Set up input pins
  pinMode(LIGHT,INPUT);
  pinMode(TEMP,INPUT);
  // initial custom character(s)
  lcd.createChar(1, deg);
  lcd.begin(20,4);              // Initialize a 20x4 HD44780-compatible LCD
  lcd.clear();                  // clear the screen
}

void loop()
{
// Static display text
  lcd.setCursor(0,0);
  lcd.print("Light Sensor:");
  lcd.setCursor(0,2);          
  lcd.print("Temperature (TM36)");

// Converst the voltage accross the thermistor to a temperature.
  tmp = ((675.0*analogRead(TEMP)/1280)-50.0);
// Read the value of the photoresistor, in arbitrary units into a string.
  sprintf(lVal,"%d",5*analogRead(LIGHT));
// and print to the LCD  
  lcd.setCursor(0,1);
  lcd.write(lVal);
  lcd.write("mV");
// I had to insert a delay, otherwise the display looked flickery.
  delay(200);
  lcd.clear(); // Prabably best to clear() directly after the delay
  sprintf(tVal,"%d",(int)tmp);
  lcd.setCursor(0,3);  
  lcd.write(tVal);
//  lcd.setCursor(2,3);  
  lcd.write(byte(1));
//  lcd.setCursor(3,3);
  lcd.write("C");
} 

Finally, here is the end result - and opto-temperature sensor:

Next, to toy with the motors and to try and built a python based oscilloscope.

Arduino Round III: Trying to Listen to the Computer

Having read data from the Arduino to a computer, the next step was to figure out how to send data from a computer to an Arduino. Again, the Arduino framework made this a much easier task than I thought. The mini project that I chose to implement this was a simple GUI which controls the RGB values of a three colour LED. Really, this is identical to independently controlling three LEDs and would work the same way.

Given that I don't know Python worth a dang, the most challenging part was the Python. First, I searched google for Python GUI, and found a plethora of packages. After a brief browse I went for the "native package" TkInter. Starting with a few lines of example code, I got the buttons, slider bars and everything on the screen. Writing to serial was as simple as writing to a console via serial.write().

The GUI, show above, was to have buttons to connect to the Arduino via the serial port, three sliding scrollbars for red green and blue LED intensity, and a 'disco mode' button which cycles through the colours. The program window is shown here:

There were a few nuisances. One of them was in naming. What I wanted was a sliding widget which was a scrollbar returning an interger withing a specific range. In Java, it's called a Scrollbar. In tKinter, a Scrollbar is a separate object, which is attached to other objects. What I really wanted was a "Scale". Next, in Java, there is a function called whenever the Scrollbar is updated, so that when the user slides from 12 to 25, you can automatically run code. As far as I could tell, this is not the case in TkInter. There are several quick workarounds: one is to have a button run a function which polls the Scales. A slightly better solution is binding which allows you to run code every time some pre-determined thing (releasing the right mouse-button for example) in a widget.

The code I used is here:

from Tkinter import *
import serial
import time

class Application(Frame):
# Store LED brightness, stored as integers, sent as bytes
    rBrightness = -1
    gBrightness = 0
    bBrightness = 0
# Slight delay between sending serial data so as not to miss a char
# Possibly unnecessary.    
    delay  = 0.01
# Strictly for keeping track of what label to put on buttons
    on = False;
    discoOn = False;
# GUI action Function definitions        

# Open or close the serial port connection. For now hardwired to COM3
    def toggle_connect(self):
        if self.ser.isOpen():
            self.ser.close()
            print("Closed COM 3")
            self.COM["text"] = "Open",
        else:
            self.ser = serial.Serial('COM3', 9600, timeout=0)
            print("Opened COM 3")
            self.COM["text"] = "Close",
# Shuts down the python interpreter. Last resort for port closing
    def shut_down(self):
        self.ser.close()
        exit()
# Send a code to Arduino to switch LED off.        
    def send_on_off(self):        
        self.ser.write('0')
        if self.on:
            self.on = False
            self.LED["text"] = "Turn On LED"
        else:
            self.on = True
            self.LED["text"] = "Turn Off LED"
# Disco light show baby.            
    def disco_on_off(self):
        self.ser.write('d')
        if self.discoOn:
            self.discoOn = False
            self.disco["text"] = "Start Party"
        else:
            self.discoOn = True
            self.disco["text"] = "Stop Party"        
# Sends RGB values to the arduino encoded as a 'char' 
# Method is bound to mouse clicks on the slider        
    def update_LED(self,event):
        self.rBrightness = self.scaleRed.get()
        self.gBrightness = self.scaleGreen.get()
        self.bBrightness = self.scaleBlue.get()
        print("(R,G,B) = (%i,%i,%i)") %(self.rBrightness,self.gBrightness,self.bBrightness)
        self.ser.write('1')
        time.sleep(self.delay)
        self.ser.write(str(unichr(self.rBrightness)))
        time.sleep(self.delay)
        self.ser.write('2')
        time.sleep(self.delay)
        self.ser.write(str(unichr(self.gBrightness)))
        time.sleep(self.delay)
        self.ser.write('3')        
        time.sleep(self.delay)
        self.ser.write(str(unichr(self.bBrightness)))
# GUI stuff        
    def createWidgets(self):
# First, create buttons        
        self.QUIT = Button(self)
        self.QUIT["text"] = "QUIT"
        self.QUIT["fg"]   = "red"
        self.QUIT["command"] =  self.shut_down

        self.COM = Button(self)
        self.COM["text"] = "Open",
        self.COM["command"] = self.toggle_connect

        self.LED = Button(self)
        self.LED["text"] = "Turn On LED"
        self.LED["command"] = self.send_on_off
        
        self.disco = Button(self)
        self.disco["text"] = "Start Party"
        self.disco["command"] = self.disco_on_off        
# Sliders (if this were java, I'd say scroll bars. In python, scrollbar is another thing altogether)        
        self.scaleRed = Scale(self,from_=0, to=255)
        self.scaleRed["bg"] = "red"        
        
        self.scaleGreen = Scale(self,from_=0, to=255)
        self.scaleGreen["bg"] = "green"        
        
        self.scaleBlue = Scale(self,from_=0, to=255)
        self.scaleBlue["bg"] = "blue"
# Add widgets to the screen                        
        self.QUIT.pack({"side": "left"})
        self.COM.pack({"side": "left"})        
        self.LED.pack({"side": "left"})
        self.scaleRed.pack({"side": "left"})
        self.scaleGreen.pack({"side": "left"})
        self.scaleBlue.pack({"side": "left"})
        self.disco.pack({"side": "left"})    
# Bind scrollbars to mouseclicks        
        self.scaleGreen.bind('',self.update_LED)
        self.scaleBlue.bind('',self.update_LED)
        self.scaleRed.bind('',self.update_LED)
# initialize GUI
    def __init__(self, master=None):
        Frame.__init__(self, master)
        self.pack()
        self.createWidgets()
        self.ser = serial.Serial('COM3', 9600, timeout=0)
        self.ser.close()

root = Tk()
app = Application(master=root)
app.mainloop()
root.destroy()

The Arduino code was next. The idea was to have have the Arduino constantly looking for a new char sent through the COM port. If it receives a particular character, it will change state accordingly. For example, a '0' will toggle the LED output on or off. A 'd' will start disco party mode. A '1', '2', or '3' will put the chip in a listening state for red, green or blue respectively. In this state, the next char received is assigned to the corresponding LED's brightness. The code shown here:

// Accept commands from serialComm.py Python script
// Controls the RGB values of a 3-color LED.
// Optional 'disco mode' which cycles through the colours
// Author: Andrew MacRae (macrae@berkeley.edu)

// PWM output ports
const int RLED = 9;
const int GLED = 10;
const int BLED = 11;
// Device states
const int LISTEN = 0;    // Accepting data.
const int READ_RED = 1;  // next char read assigned to RED.
const int READ_GREEN = 2;// Same, but for green.
const int READ_BLUE = 3; // ditto, for blue.

boolean on = false;     // Outputing to the LED?
boolean disco = false;  // Disco mode
// Stores the RGB values recieved from the GUI
int rBright = 28;        
int gBright = 128;
int bBright = 68;
// For disco mode. These will be automatically adjusted
int iR = 0;
int iG = 0;
int iB = 0;

byte byteRead = 'x'; // current byte read from serial
int state = LISTEN;  // Initially, wait for instructions

// Setup ports for input and start the serial connection
void setup()
{
  pinMode(RLED, OUTPUT);
  pinMode(GLED, OUTPUT);
  pinMode(BLED, OUTPUT);
  Serial.begin(9600);
}
// main loop
void loop()
{
  if (Serial.available())
  {
// is a byte has been sent, store it    
    byteRead = Serial.read();
// If previously recieved instruction to read in colour,
// set the value to that of the byte and reset state to LISTEN
    if(state == READ_RED)
    {
      rBright = byteRead;
      state = LISTEN;
    }
    else if(state == READ_GREEN)
    {
      gBright = byteRead;
      state = LISTEN;
    }
    else if(state == READ_BLUE)
    {
      bBright = byteRead;
      state = LISTEN;
    }
// Otherwaise, check if state change is needed:

// 'd' means toggle disco mode
    else
    {
      if(byteRead == 'd')
      {
        disco = !disco;
      }
// '0' means toggle output on/off
      if(byteRead == '0')
      {
        on = !on;
        byteRead= 'x';
      }
// '1'/'2'/'3' means prepare to read in red/green/blue
      if(byteRead == '1')
      {
        state = READ_RED;
      }
      if(byteRead == '2') // Toggle On/Off
      {
        state = READ_GREEN;
      }
      if(byteRead == '3') // Toggle On/Off
      {
        state = READ_BLUE;
      }      
    }        
  }
// if the LED is on  
  if(on)
  {
// loop disco mode variables    
    iR+=3;
    iG+=5;
    iB+=7;    
    if(iR>255) iR=0;
    if(iG>255) iG=0;
    if(iB>255) iB=0;
// and use these variables if in disco mode    
    if(disco)
    {
      analogWrite(RLED,iR);
      analogWrite(GLED,iG);
      analogWrite(BLED,iB);
      delay(30);
    }
// otherwaise use the variables set by the user
    else
    {
      analogWrite(RLED,rBright);
      analogWrite(GLED,gBright);
      analogWrite(BLED,bBright);
    }
  }
// if off, set all outputs low  
  else
  {
    digitalWrite(RLED,LOW);
    digitalWrite(GLED,LOW);
    digitalWrite(BLED,LOW);
  }
}

The circuit is simplicity itself. Three separate PWM outputs are sent to the led which is grounded through a 100 Ohm resistor. The green and blue chanels get an extra 220 Ohms to set the relative brightness of each LED about equal. A sketch is included below:

Finally, here's a  very crappily shot video of the circuit in action! To reduce the brightness and display the colour more uniformly, I used a high-tech solution known as a Perforated Fibrous Diffusive Membrane. Paper towel to the layperson.

http://www.youtube.com/watch?v=MZN09ancg_U

Arduino Round Two: Trying to Talk to the Computer

The next thing I wanted to do with the Arduino is: get some real-time data, and plot it in a nice looking graph on screen. For this, I pieced together a simple example of reading an analog voltage from a photo-resistor and pushing it to the serial port. As another testament to Arduino's simplicity, this was a 3 minute job. As a testament to my ineptness, plotting the data was a 3 hour job. The Arduino code and circuit are shown below: The code is fairly straightforward and taken from an example I found online:

const int PHOTO = A0;  // Analog input pin
int voltage = 0;        

void setup()
{
  Serial.begin(9600);
}

void loop()
{
  voltage = analogRead(PHOTO); // 0-5v <-> 0-1023
  Serial.println(voltage);     // Plain ASCII
  delay(250);                  // update at 4 Hz
}

 The circuit is even more simpleminded: the photoresistor's resistance varies from about 10k when dark, to just under 1k when I have my phone's flashlight on it. Placing the analog in port between this and a 10K resistor makes a nice voltage divider which goes from about 50% to 95% of whatever you feed it, which in this case, is 5V:

Actually, if you just want to see data sent from an Arduino chip over the serial port, the built in serial monitor works right away.

However, if you want a nice plot, you have to deal with that yourself. I know Java pretty well, so that was my first instinct. I keep hearing about Python though and how amazing it is. I decided to give it a shot and downloaded Python 3.x for windows. Then I read up on connecting to a COM port and apparently, the best bet is to install a module known as pySerial. I went an got ahold of that, and ... it didn't work. I was having trouble with loading the python module and after a brief search, concluded that I'd better downgrade to Python 2.x. I got that and after dome fiddling, could read from the COM port, albeit with some lag. To fix the lag, it turns out that you have to poll the arduino faster than the arduino is writing out, otherwise you get a backbuffer. I believe you can also solve this with a flush of the serial port.

OK, but I still haven't plotted anything. To get going on that , I read about MatPlotLib for Python for which I needed numPy. I went to download that, and as it turns out, I should have installed a Scientific Python distribution instead of plain old Python. Again, I uninstalled Python and installed EndThought Canopy - a gargantuan download/install which in the end, had major trouble with pySerial. At this point, what was another uninstall, so I dumped it and went for Continuum Anaconda. Using this, I could get a plot up and running - well up, but not running.
Long story short, if you want to plot things in real time with MatPlotLib, you need to give the graphics library to sort itself out, or the window will hang. This can be done via a simple 'sleep' command. The program that eventually worked is shown below:

# Poll a COM port for Serial data and plot real time
# Thanks to http://www.lebsanft.org/?p=48 for the code idea

import sys
sys.path.append('C:\\Python27\\lib\\site-packages')
import serial
import time
import numpy as nm
from matplotlib import pyplot as plt

ser = serial.Serial('COM3', 9600, timeout=0)

yData = [0]*50

ax1=plt.axes()

line, = plt.plot(yData)

plt.ylim([800,1100]) 
while 1:
# First, read from the device
    try:
        currVal = ser.readline()
        print(currVal)
        time.sleep(.1);
    except ser.SerialTimeoutException:
        print('Error acquiring data')
# Check if the data was a valid number ...
# may be blank in asynchronous mode
    try:
        cV=float(currVal)
        runnit = True
    except:
        runnit = False
# If the value was a legit number, plot it.
    if runnit:
        ymin = float(min(yData))-10 # Set the y-scaling
        ymax = float(max(yData))+10
        plt.ylim([ymin,ymax])
        yData.append(currVal) # tag on newest point
        del yData[0] # and bump oldest point
        line.set_xdata(np.arange(len(yData)))
        line.set_ydata(yData)  # update the data
        plt.show() # update the plot
        plt.pause(.01)
# Doesnt exit nicely here ... need to fix

 Finally, real time monitoring of, well ... of my shadow here. But I see it as a next step to bigger and better projects:)

An attempt at Arduino

I've always wanted to fool around with electronics. Particularly, I've been wanting to fool around with microcontrollers since it seems awesome to program things that don't live entirely within a RAM chip, but directly interact with "the outside world". The problem is, I never know where to start.  I actually programmed some basic ATMEGA stuff when I was a student, but it was under a rushed research environment and I had time enough only to get things thrown together, put it in a box, and move on without thinking too much about it.

I kept hearing about this thing called Arduino. which seems to be a good place to start. Utilizing an upcoming birthday, I hinted heavily to my wife that the perfect gift for a geek like me was a "get your feet in the water" Arduino kit. My pressing hints payed off and I've just started fooling around with my new Arduino Uno.

Upon first glance, Arduino seems pretty awesome. It is a composite microcontroller/programming board which gives you easy access to a number of digital/analog i/o pins. Despite the convenience of this, I was initially put off by this. During my brief stint with AVR programming, I could remove my little ATMEGA chip, and stick it in a small box containing a 9V battery and a tiny breadboard and have my device. If I wanted to make a couple, I just needed the ICs, and not several copies of the programmer, which scales up the size and cost of a duplicate project.

I have this dream of placing a bunch of ICs on a breadboard for individual projects, rather than chunking together a bunch of Arduinos. However, discussions such as this one have convinced me that under the hood, an arduino is simply a special  a AVR programmer, and if I wanted to, I could use the arduino board to program AVR chips just the same. So for now, I'm sold, and am excited to get started.

Apparently, the equivalent of "hello world" in the microcontroller world is to blink an LED, so that was my first step. I found a quick tutorial on this and, as is my habit, tried to modify it a little from the get go. As a first selling point to Arduino, it was about three minutes from opening the box to getting a simple program running.

The first step was to download the Arduino software which allows you to either debug, or upload your program with the click of a button. The next step was to wire up a simple circuit board to do my bidding. The idea for this first program is simple: When the user clicks a button, slowly ramp up the voltage to an LED from whatever it was to a maximum value. When the button is pressed again, it slowly ramps down to 0.

The code for this is simple: A button press toggles the state of the device between on and off. When its on(off) the device increments(decrements) the brightness (which is just a PWM voltage) and delays for 10 ms. That's pretty much it. There is a bit of weirdness of the switch bouncing which can be remedied by introducing a slight delay after switching states:

const int aLED = 9;        // Analog LED
const int BUTTON = 7;      // Push Button
boolean buttVal = 0;       // True if button pressed
boolean buttValOld = 0;    // Value from last cycle

boolean on = false;        // Stores the state' of the device

int brightness = 0; // Stores the brightness value from 0 to 255

void setup()
{
  pinMode(aLED, OUTPUT); // Set pin9 for output
  pinMode(BUTTON,INPUT); // Set pin 7 for input
}

void loop()
{
// Handle a button press. If the state has changed, delay for 5ms 
// to avoid bouncing
  buttVal = digitalRead(BUTTON);
  if(buttVal&&!buttValOld)
  {
    on = !on;
    delay(5);
  }
  buttValOld = buttVal;
  
  if(on)  // If state is on, ramp up voltage each cycle, then delay
  {
    if(brightness<255)
    {
      brightness++;
      delay(5);
    }
  }
  else  // If state is off, ramp down voltage each cycle, then delay
  {
    if(brightness>0)
    {
      brightness--;
      delay(5);
    }
  }
// Finally, set the LED voltage to the current value of 'brightness'
  analogWrite(aLED,brightness); 
}

The circuit itself is also is exceedingly simple: depressing the switch routes 5V to the input pin 7, which causes digitalRead(BUTTON) to return a "HIGH" state. The LED voltage is run through a 270 Ohm resistor to ground to limit the current drawn from output pin 9.

The result .... is pretty much what you'd expect:

I had a lot of fun with this one and am looking forward to the next mini project-ling.

Tick Counter for Slow Computers

Normally when making a game/animation loop which should run at a realistic looking speed, I do the following:

while(Playing)
{
    updateGame();
    System.pause(delayTime);
}

which is fine as long as the game code executes in a time much less than the refresh period (i.e. 1/(refresh rate)). However, when the game loop takes a longer time so that the delay you need to give is quite small, then the computer optimized for a slower computer (as I have at home) will run way too fast on a less ancient computer (as I have at work.)

This can be partially overcome (assuming that you computer can at least run the program with zero delay) by implementing a feedback loop which adjusts the delay time to keep a fixed number of cycles per second.

This is actually quite easy to do: say we want x cycles/s and we get y cycles/s -

int t = getCurrentTime();
int tickCounter = 0;
while(Playing)
{
    tickCounter++; 
    time = getCurrentTime()-t; 
    if(time > 1000ms) 
    { 
        delay = updateDelay(tickCounter); 
        t = getCurrentTime(); // reset time 
        tickCounter=0; 
    } 
    updateGame(); 
    System.pause(delay) 
} 
 
public int updateDelay(int y) 
{ 
    return delay*y/x; 
}

... and that's it.

A simple implementation of this can be found here: basically, it is an Applet which runs a stopwatch (it has to do something) and adjusts the delay per loop so that the program executes a specified number of iterations per second. The functionality of the stopwatch is unaffected by the background feedback loop as desired.

... and the source code is here.

Side Scrolling Fun V: Music, Levels, Bosses, and Media Managers

The next iteration of the side-scroller engine is up and running, and is almost starting to resemble an actual game. The first thing I did was find out why the game took so long to load. The answer was simple - I was being stupid: each instance of image and sound in the game was being loaded each time it was needed. In other words, I had roughly 3000 tiles consisting of one of 3 distinct images. When the level was loaded I loaded each image separately from the server, i.e. I downloaded ~3000 image per level, while in fact I needed to download three. To get around this, I wrote a ImageManager (iMan) class. Each time an Image is needed you ask the iMan for it and give it only the filename. The iMan checks its database to see if that file has been loaded yet. If it has, it returns a copy of the image, only if it has never loaded that image does it request it from the server. This lead to a tremendous speed-up in loading time and seems to work fine.

The next fish to fry was sound - both sound effects and soundtracks. I started by making a sound manager (sMan) similar to the image manager. Next I had some struggle with sound formats. Java doesn't care much for wav files. I basically had to tinker with the bit-rate, depth, etc. to get it to play, and I still don't know why some play and some don't. All I can say is that the java native sound engine is good, but finicky. As for sound track, I went for straight up midi which was a lot easier to work with. Currently, all the songs are ripped off from an awesome repository of nes roms that I came accross and I am starting to try to "compose the original score" :)

The next task was to create game states that allowed specific tasks to occur (ex. loading, player just died, player is playing, etc.) This allowed for an intro screen when the game was loading and cut-scenes between levels. This also allowed for animations and sound clips to run when the player dies or beats a level. The paint and run methods are then if-else statements based on the current state. The states are:

1. Intro
2. LoadIntro
3. LoadLevel
4. Playing
5. JustDied
6. Boss
7. JustPassed

The next improvement was the addition of levelguys, i.e. bosses. In boss mode a life-meter pops up displaying the boss' health as the gameState is set to "Boss". The screen also locks and the music changes. After the boss' energy reaches -1, the gamestate goes to justpassed and some celebratory music (currently from Duper Mario Bros.) plays. In order to mediate the timing of the cut-scenes, there is a variable tickCounter which is set when the game enters a given mode. When in this mode, each tick of the game loop reduces the tick-counter by one so that when it reaches zero, a new game state may be entered.

The boss can be seen here. He's (it's a dude) pretty easy and used for debugging purposes.



Here's screen shot of the the game in action: Click it to play!


The source code for this version can be found here. The "game" can be "played" here.

Side Scrolling Fun IV: Enemies, Mortality and Backgrounds

For the next small step in the side-scroller engine, I wanted to tidy the look up just a bit, add drone-type enemies, and have it so the player could die. For tidying it up, I first added a parallax background which consists of a layer of sprites and a depth into the screen. The larger the depth, the slower it scrolls, so a depth of 1 would scroll faster (twice as fast) than a layer with a depth of 2m and a depth of infinity would be stationary. This was a cheap attempt at a pseudo 3-D (circa 1982) feel. The background itself could be made in a level editor, or loaded as a random array of background elements upon start-up. For now the only objects are clouds placed at random, at two separate depths.

Another "look and feel" kind of effect was to have a clear-cut beginning and end to the level. You notice in the old Super Mario Bros. series (and most side-scrollers) the screen follows Mario unless he's at the beginning or end (or top or bottom) of the level at which the screen stops moving and Mario move with respect to the screen. To accomplish this, I just checked if the current screen would be more left than the leftmost tile or more right than the rightmost tile. If so, then the screen was fixed at the extreme point, i.e.

double screenX = 0;

if(xCX)

{

screenX = CX;

}

else if(x>levelMaxX-CX)

{

screenX = levelMaxX-CX;

}

else screenX = x;

... and similarly for y. Also, to make things more efficient I only computed collisions, drew tiles, and processed enemy behavior if they were visible. Since each of these elements are sub-classes of and abstract "Square Object" class, or Squob, this is really simple. At each iteration get all squobs within a half screen width distance from the player and update and draw those objects alone. Right now the speed-up in unnoticeable but for larger levels with more advanced processing, this could become significant.

Next step was getting enemies on the screen. This was done by making a generic Enemy class which extends Squob. No opponent in the game is directly from this class, but each individual enemy extends these properties. Then I just created an array of enemies and updated the array on each game iteration. Each enemy has a sprite manager which handles its animation and a function called iterate() which defines its behavior. Right now, the "behavior" is just to walk in a straight line and turn around if its next step will bring it over a ledge or if it bumps into another enemy or a wall. Whether or not a collision occurs is passed to the enemy from the main program.

The two prototype monsters are the "grunt":

and the "peon":

which basically do the same thing now: walk back and forth, and hope to bump into "smiley":

... who is not currently smiling.

In order to conveniently add the array of enemy monsters to the game in just the right place. I modified the level editor to allow for monster placement, as well as player start point. The level file now contains player start coords, enemy positions, and tiles:

clicking on the picture will give you the zipped source code.

To make it so the player could die, I just check for special cases in the collision detection. For example if the player collides with a spike, he dies. If the player collides with an enemy from below or the side, he dies, but if he collides from above, the enemy dies. Here the player dying means that his 'lives' get reduced by one, and he's warped to the beginning of the level. Now, nothing happens if he runs out of lives he just has a negative amount of lives. The philosophical implications are mind boggling!

Here is a screen-shot of the program in action. Click on the pic to try the game. One problem is that the loading time is brutal. At first I thought that it was the server but after writing a simple test program which loads a single image and text file from the server I noticed that this was not the case, as the test program ran instantly. Upon closer inspection I think it's just that I was being stupid. When the level is loaded it loads each tile as an image from a URL which is ridiculous. For next iteration of the program I'll just load each item once (via a LoadManager?) and store these images as global type files.

In the next programming run, the goal is to make a polished, 2 level game that doesn't make any sense. The game will have sounds, cut-scenes, intro, game-over screens, 1-up, nicer graphics, level bosses. In addition I'll try to debug all the little problems like slow loading times. This all needs to happen before the final stage of game design - that is; a story, characters, and lots of levels and variety.

Side Scrolling Fun III: Sprites & Tiles

With the level editor complete, I added some code to read in a level file, allowing the player to roam free in a bigger world. The next step was to pretty things up a little by drawing each tile from an image (instead of a red, green, or blue square.)

Since the level could be, in principle quite large, it didn't make sense to draw the entire level each "tick," but to at the very least draw only what is visible on the screen at the time. Given that the blocks from the level file are already sorted by x-position, and since the levels are long but not tall, this wasn't too hard. I just searched through the array of "Squobs" until I got to the first one which had an x-component greater than the leftmost screen point minus the block width and marked that as the starting point. From there I kept going through the list until I got to the first brick which had an x-coordinate greater than the rightmost screen-point and marked that as the ending point and drew all of the blocks in between.

The next task was to draw the player as an animated sprite. Normally sprites are a collection of images which animate in sequence to make the appearance of moving. Since you don't necessarily want to make one animation frame per clock cycle, you can incorporate a frame rate by counting up each clock cycle to a certain number before flipping frames. For the purposes of making a character look like he's walking, I counted distance traveled instead of clock cycles. This makes it look a little (but not too much) more natural and keeps the character from walking on the spot when his velocity is little or zero.

In order to get the player to face the right way and to look like he's jumping when he's jumping, I gave the Sprite class a set of states:

1. s: Standing and facing right
2. S: Standing and facing left
3. j: Jumping and facing right
4. J: Jumping and facing left
5. r: Running and facing right
6. R: Running and facing left

... and each is sorted out in the code via a switch(state) statement.

Here is a screenshot of the code in action:

In order to circumvent Java's (admittedly necessary) security measures, all the files are loaded as URLs from the server where they reside. As a result, loading the level takes a really long time. However I couldn't convince Java to read files from a browser so until I find a better way, I'm stuck doing it this way.

The code can be found zipped here or directly here.

You can play the game here (all you need is a little patience.)

Side Scrolling Fun II: The Level Editor

In the very basic side-scroller engine that I started, I needed obstacles for the character (or circle) to walk on. This was done by manually typing in the coordinates and dimensions of the obstacles directly in the code. This is ridiculous and should be done with a level-editor type program, so I decided to take a stab at one. I decided to try to learn the nice-looking Java Swing layout editor. To simplify things such as file i/o, I made a stand-alone program instead of an Applet. At first, learning Swing was a huge mistake since I spent hours trying to make things work. After a while I learned the basics: the main window is a JFrame, which contains a number of JPanels which can be addressed individually. The frame can have a menu, a toolbar, and a drawing area, among other things.

The main program, which contains a menu, a toolbar and a drawing area (MapPanel which extends JPanel) is MainFrame (extends JFrame.) This contains all the event listeners and handles the "save" and "open" operations. The MapPanel is a grid of characters, each of which determine a block of a given size on the map.

The map may be saved into a text file consisting of a header telling the size of the map etc, followed by a list of coordinates of block types sorted by x.

A typical file is: (level1.txt)

200,50,636

0,0,b

0,1,b

0,2,b

1,17,b

1,18,b

2,1,r

2,13,g

...

You can open saved files. The open function first check for a logical header and then attempts to read the blocks into an Array of type "MapPoint" which is just a container for data of form (int x,int y, char type). If anything goes wrong with any of the points, the map loader jumps ship and returns false. Only if every point makes sense and the number of points is consistent with the header file does the map get loaded on screen and the method returns true.

The final time consuming part was making the program behave like a normal program. For example, if the user has already saved the file and chosen a file location, a new file dialog menu shouldn't pop up when he saves again, it should just save - something I never really thought about. Also, if the user saves then exits, he shouldn't be asked to save again, but if a save is needed, a polite program would ask of he wants to save first. To this end, boolean values for were created to denote whether a filename has been selected yet and whether a save is required.

Other challenges were making the functional part of the program convenient to use. It would be very annoying to have to draw the map by clicking each block individually. To circumvent this, a click-drag feature was implemented by checking whether the user is holding the mouse down. Also, it is essential to clear mistakenly placed blocks and to know what type of block is currently selected. I found that the best way to show this was to have an outline of the current block type hover along with the mouse cursor. Finally, for the "big picture," the user can toggle a mini map on and off by pressing m. The end result looks like this:

This now allows me to continue along with the side-scroller engine and test it out on a few simple maps. The next iteration of this program (if it comes to be) will extend the functionality of the UI by adding features like "undo" and remembering the current file directory so the user doesn't have to constantly navigate there.

The program+source code can be found zipped here, or straight out the gate here.

Thanks to Java Swing, the end results doesn't look too bad and almost resembles a real program that one might find on the internet.

Side Scrolling Fun

I always wanted to make a Mario Bros. style side scroller. I tried once long ago but I had such a hard time dealing with things like; "how does the player know not to fall through bricks but to fall when he's at the end of them" that I just gave up. Today however, I decided that maybe in my old age, I've acquired the wisdom and patience to accomplish such a feat. The feat will be attempted in Java.

I've also been itchin' to do some programming on my new macbook pro, so I downloaded the latest version of eclipse, slid the icon to the application thingy and blasted out a preliminary engine. Now, this engine is very preliminary, but it's a start.

Basically, the player is a circle which falls under gravity and can stand on square objects (Squobs) which he can't pass through. He (it's a dude) experiences drag and will grind to a halt if you let go of the controls. Also, he can jump.

The code is very simple: The whole thing runs on a thread which:

1. calculates his next position
2. checks for collisions at this position against a list of squobs
3. handles collisions and applies drag

over and over again. The squobs are held in an array-based data structure and at every step they are all check. This isn't terrible efficient and will be fixed in version 2. Also the sqoubs are manually added in the code which is ridiculous.

The next step will be a level editor to efficiently construct obstacle courses built of squobs that will be loaded on the fly. After that, graphics. Then ...

For now, here's a screenshot:

The code can be found here (zipped), or here.

You can run the applet here.

Why Do Planes Get Lift?

When someone asks: why does a plane fly, I'd say: "because the shape of the wings, the plane gets pulled up, it's called the Bernoulli force ..." But is this force really enough to overcome the force of gravity for a Boeing 747? The aerodynamics involved are actually extremely complicated, but you can get a "back of the envelope" figure by considering a wing, as drawn below.



Assume that the air flow is non-turbulent, (basically, this means that two air molecules next to each other at the front of the wing will meet at the back of the wing if one takes the upper path and the other takes the lower path. If this is not the case, air would be accumulating above or below the wing and at the back, you'd get vortex effects - i.e. turbulence.)

Note that the wing is slightly longer on top then on the bottom. The bottom is of length L, and the top is of length L + dL, where dL is small compared to L. To emphasize this, lets say:

d = dL/L ... (1)

Since the flow above the wing has to travel a farther distance than the that of the bottom path in the same amount of time (non-turbulent flow), the air on the top is going faster than the air on the bottom.

Since velocity = distance/time, we have:

velocity on bottom = vb = L/t ... (2)

and on top = vt = (L+d)/t = vb + d/t = vb + L/t*d/L = vb(1+d) ... (3)

where in that last step, I used (1).

Now it's time for Bernoulli's equation: it says that, assuming non-turbulent flow, the pressure P, velocity v, and height h, of a fluid with density ρ at points htop and hbot are related by:

Ptop + 1/2 vtop^2 + ρ g htop = Pbot + 1/2 ρ vbot^2 + ρ g hbot ... (4)

The first thing to note is that htop~ hbot, so the lift due to these terms (buoyancy) can be neglected:

ρ g htop ~= ρ g hbot ... (5)

To be convinced of this, the density of air is around 1 kg/m^3 and a wing is about 0.1m thick. Since g is about 10 m/s^2, the differential pressure is on the order of 1 Pascal. For a 10 m^2 wing, this could lift about 1kg, which is much less than the wing itself would weigh.

Next note that the quantity that we're interested in is Force due to the differential pressure. Since Force = Pressure x Area, this is, for wings of area A:

Flift = (Pbot - Ptop)*A ... (6)

Combining (4) through (6), we get:

Flift = 1/2 ρ (vtop^2 - vbot^2)*A ... (7)

We can now use (2) and (3) to get:

(vtop^2 - vbot^2) = vbot^2 (2d -d^2) ~ 2dvbot^2 ... (8)

In the last step, we used the fact that d << 1bot = v, the velocity of the plane, we get:

Flift =ρ A d v^2 ... (9)

... the force of lift due to the wings.

Let's say that the top path of the wing is 5% longer (d=0.05) and that each wing is 10 m^2. Using ρair = 1 kg/m^3, we get:

Flift = v^2, with Flift in Newtons and v in meters/second. In order for the plane to fly upwards, the force of lift must be greater than the force of gravity Fg = m g.

A typical jet can fly at around 200 to 250 m/s, so the force of lift is then about: 62,500 N (now we see why the ρ g h terms could be ignored.) This can lift a mass of 6,250 kg, but a jet weighs in at a few 100,000 kg, so why does it fly?

First off, this is an oversimplified picture: this would work well for a glider or bird (a bird with 10cm x 40cm = .04 m^2 wings and d = 10% would have to go about 30 m/s to glide if it weighed a pound - any slower and it'd have to flap its wings.) A jet on the other hand, has propulsion which pulls it upward, in addition it gets an upward lift from the normal force of the wind. This is the same force that you feel when you stick your hand out of the window while driving down the highway. For a large jet such as a Boeing 747 this actually contributes to most of the lift force.

The point of this was to do a back of the envelope calculation of the "popular" idea of lift, and show that this simplified picture alone doesn't really explain why a jumbo jet flies way up in the sky. For a more details, the complexity of the problem goes up exponentially and you soon have to resort to numerical simulations. However, a really nice (slightly less simplified) discussion is found here!

The Jog Mapper

Sometimes, when I've watched to much "The biggest Loser", I decide to go for a run. I put on my shorts and runners, start my watch and go. Roughly 30 minutes later, I stop my watch and keel over. I look at my time and realize that I don't know if it's good or not, because I have no idea just how far I've run. I decided to go on to mapquest to trace out my root, but this was awkward since I don't usually run along roads. I then just grabbed the image of the map and found out how many 'pixels' I ran, and then converted it from there, but that took a long time. Finally, while running today, I thought "why not just make a basic program to do this: You give it a map and tell it the scale and then draw your path, and it'll tell you how far your went?" - I didn't actually say this out loud. I was conserving every precious bit of oxygen I could.

Here's a screenshot of the program in action. The calibration is done at the beginning where you type in the scale and then drag across the scale-bar to define a conversion fact of meters/pixel. Then you click out your path in line-segments and the program keeps track of the total distance.


Right now, the program is very bare-bones. First off, you have to acquire the map image first, put it into bmp format, and make sure the scale is visible. What would be nice would be to dynamically load the map from mapquest. Second, the user interface is usable, but not friendly. However it does what it does well enough. Thirdly, it would be nice to be have segments that aren't lines, but as long as you don't mind a lot of clicking, it's not a problem.

The guts of the program are as follows: The program starts out in calibration mode. You type in the physical reading from the map's scale, and then click the mouse at the start and end of the scale to get the conversion factor of physical length per pixel. then the program is in the main mode. A display on the top left corner gives you the mileage (kilometerage actually.) When you click at your starting point the program is in draw mode, and a line follows the mouse cursor. Click again and the line segment formed is added to the Path() class. Each click thereafter adds a line segment and the distance continuously updates.

As of now it's a quick and dirty program. If I were to make some changes, it would be (in this order:)

1. Make the program, resettable.
2. Design the UI properly, including a file dialog box for the map.
3. Make the window scrollable to allow for bigger maps.
4. Get the maps real-time off the information super-highway. (I have no idea how to do this)

For now, the code and zipped visual c# project is accessible here!

Capture the Flag II

I've finished the first programming run for "capture the flag." Right now two teams compete eternally and a counter keeps score of who wins more often.

The field itself consists of four regions:
1. The flag zone: The defending team can't go into it's own flag zone, and is a safe haven for an attacking player.
2. The defending zone: The defender and rescuers hang out here. When the enemy attacker is not in this zone, they just track his y-position, when he is, they go after him.
3. The attacking zone: Here, the attacker forms a vector which is the sum of vectors towards the flag, with vectors away from the defender and attacker, with given weights attached to each.
4. The safe zone: In the safe zone, the defender can not capture the attacker, so the attacker no longer tries to avoid anyone and goes straight for the flag. Once he has it, he makes a dash for it to his own zone.

As of now, the rescuer does absolutely nothing - he has the same instructions as the defender, except he isn't allowed to capture. Instead, when an attacker is captured, he has to do a strange sort of dance: first he has to go to the corner of his own zone, then he has to touch his own flag-holder, and then he starts again.

The system often gets into a "deadlock scenario" in which both players eternally get captured, do their dance, and get captured at the exact same place. This problem could be avoided by imposing a time limit on each round and resetting after it expires (the positions of the players are randomized at the start of each round.)

Here's a video of the program in action:



Before doing the really hard part - the genetic algorithm part, one more programming run is needed, to iron out the kinks. This means:

1. Make the program more modular (i.e. variable number of players for each team)
2. Make a jail (to give the rescuers something to do)
3. Clean up the player logic (there's a lot of ad hoc stuff in there right now to make it work)
4. Add timers etc. and pretty it up a little.
   

For now, the C# code and zipped Visual Studio C# project is located here!

Twinkling Streetlights

If you ever look out over a city on a clear night, like on one of those 'make-out points' from cheesy 80's movies, you notice that distant streetlights seem to flicker and dance around a little, whereas closer ones don't. If your not making out with Winnie Cooper at the time, you inevitably start to wonder why that is the case. Notice that the same thing is seen in the sky: stars twinkle, but planets don't (the ones that wee can see, that is.)

The reason for the "twinkling of the stars" is what is called "atmospheric seeing": the atmosphere has layers of turbulent air of varying density and temperature, which leads to a time-varying index of refraction (The speed of light in a vacuum (outer space, say), divided by the speed of light in the material (air here.)) To see why this would make a star twinkle, recall that a lens is just a material of certain index of refraction, shaped in a certain way so as to focus (or diverge) light. The pockets of air blowing around the atmosphere, means that light from a star would rapidly become focused and unfocused as the air above blows around. This is kind of like the pattern you see on the sand, underneath shallow water: the light jumps around like crazy from being randomly bent at the surface. For water the effect is way more pronounced, since the index of refraction of water is about 1.33, whereas for air it's 1.0003 - just barely different than for a vacuum for which, by definition, it's 1. You can check how bad the current "seeing" is here.

So that's why stars twinkle, but then what about planets? The same "seeing effects" would be present for both planets and stars, but we only notice it for planets (actually, if you look through a telescope at Saturn or the Moon, you really start to notice the effects of seeing on a good night vs. a bad night.) The reason is that to us, stars come from a point in the sky - we can't resolve with our eyes what shape they are or what they look like. All our eyes know is that light is coming from one specific direction. When we see an object, say Winnie Cooper, her left ear is focused to one point on our retina, and her right ear is focused to another. That is, we can resolve the shape of the image. For stars, this is not the case: they're so far away that the left part of the star is totally smeared over with the right part of the star. Because light is wave, it can't be focused to an infinitely small point, the focus is limited (by diffraction) to a certain size, and for stars, this size is much bigger, that the size that they would be focused to on our retina. For planets however, we can make out the shape of them and although each point of the planet is experiencing this seeing effect, all of the combined effects average out into a steady (slightly blurred, if you look through a telescope) image. To verify this, we can to a rough calculation.

The minimum resolvable angular distance between two objects which are sent though a lens with diameter D is: sin(θ) = λ/D times some constant which is close to 1 and depends on the type of wave and the exact shape of the lens. For a plane wave through a perfectly circular lens, it is 1.22. For us, D is the diameter of our pupil, say 5 mm, at night. The wavelength of visible light is on the order of 600nm, so λ/D is about 10^(-4) which means that the minimum angle is about θ = 0.0001 (since sin(θ) is pretty much equal to θ when θ is so small.) Now by definition, sin(θ) = Dia/dist, where Dia is the diameter of the object and dist is the distance to it. We now have a test to see if an object is resolvable or not: if Dia/dist is bigger than 0.0001, it should be, if Dia/dist is much less that 0.0001, it's not (keeping in mind the roughness of the calculation.)

Several cases:

Mars: Dia = 6800 km, dist = 55000000 km, Dia/Dist = 0.00012
i.e It should just be resolvable.

Jupiter: Dia = 140000 km, dist = 700000000 km, Dia/Dist = 0.0002
i.e. Again, in the window of resolvability

α-Centauri (nearest star): Dia: 10^6 km, dist = 2*10^13 km, Dia/Dist = .0000005
=> much less that that of the planets.

Now, bringing this back to the original discussion, say that a street lamp has a diameter of about 10 cm. The distance at which it takes up about the same angle as a planet is: dist = Dia/θ = 1 km. Much farther than this, and the lights become point sources, like the stars. From where I live, the lights at the train-station 1 km from my place don't twinkle, but the lights on the ski-hill, 5 km away do. However, the giant billboards by the hill do not - they have a bigger Dia. and therefor are resolvable. These calculations were pretty rough, but they sketch out the main point - that the "twinkling" of stars and distant lights, stems from them being "point-sources" of light to our eyes.