Shortest Path

October 7, 2011

My Apple II/c

Filed under: non-technical — dharabor @ 01:27

Steve Jobs passed away today. A profoundly influential man, his work touched the lives of millions. Including mine. I wanted to reflect on his passing and, since I don’t really have an alternate forum, I’ll share my story here.

In late 1991 I received my first machine: an Apple II/c. I remember a feeling of intense disappointment as my father proudly started unpacking and connecting up the little cream-coloured device. This was nothing like the IBM PCs and Amigas I’d spent so many weeks reading and dreaming about. There was no hard drive, no sound card, nowhere to insert a CD. Just a 5.25″ drive and a box of ancient software. Hand written labels adorned the upper-right portion of most disks, each title more cryptic than the last: “MousePaint”, read one; “Logo”, another. Instead of a 14″ monitor and glorious colour graphics, I found myself staring at a 9″ monochrome green display. The thing made funny beeping noises when you switched it on. For goodness sake, it had a handle. What could he have been thinking?

I never uttered these thoughts out loud. The look on my father’s face then was one of sheer triumph and delight. How could I break his heart? I feigned excitement and soldiered on, determined to make the best of it. Then, something happened: I fell in love.

Over the weeks and months that followed I became obsessed with knowing my Apple II/c. I explored every disk. I pored over every manual. I spent countless hours with friends adventuring in Daventry, guiding Captain Goodnight through the Islands of Fear and helping a little spider reach the attic of a cider factory. I also started programming.

20 GOTO 10

I was never a child prodigy; I didn’t write my own games from scratch or teach myself assembler. I copied thousands of lines of BASIC from reference books so I could play Lunar Lander. I drew patterns in Logo. It wasn’t much, but it was enough. The Apple II/c sparked my curiosity and fired my imagination as no contemporay machine ever could. There was a simple elegance to the way everything worked that encouraged exploration. The BASIC interpreter, for example, didn’t come on a disk: it was built in and started automatically. “Here I am” it would say, blinking its little green cursor encouragingly whenever you’d forget to insert a boot disk, “Take me for a spin. Let’s do something amazing together”.

I didn’t know it then but those early fumbled efforts were the first flirtatious steps of a life-long romance with computing and Computer Science. I eventually graduated to larger and more powerful machines: a 486 PC some years later, a Pentium thereafter. From BASIC I went to Pascal then C and now to… everything. Yet despite all those changes it was that little machine, that Apple II/c, which helped me discover a passion that continues to shape who I am even to this day.

Now, 20 years removed from those halcyon days, I once more find myself the happy owner of an Apple computer. Its form may have changed in the intervening period but its role in my life has not: It helps connect me. It entertains me. It turns my imagination into reality.

Thank you father, thank you Apple, and thank you Steve.


July 11, 2011

The Paper

Filed under: conference,non-technical — dharabor @ 16:34

I wanted to share this small piece of creative writing. It was cobbled together earlier this year while I was turning myself inside out trying to meet various submission deadlines. It’s a change of pace for this blog, but I hope you enjoy it nonetheless. I call it, The Paper:

Tick, Tock. Tick, Tock.

Steadily forward march the hands of the clock.
The paper needs writing, results must be got;
Forget about sleep or all is for naught!
With each passing second the conference draws nearer,
To obtain tenure you must publish here.

Tick, Tock. Tick, Tock.

Redouble your efforts ye graduate student,
And condense into pages no greater than six,
The sum of your efforts these many long weeks.
Spell out in sections, as short as can be,
The problem you solve and your neat novelty.
Whether by theory or experimental design,
Argue the case that your approach is sublime!
Cite all prior work and conclude on a high,
Then compile your sources one final time.
Press upload and hope for the best,
In six weeks you find out if your work’s passed the test!

Tick, Tock. Tick, Tock.

With the deadline past and the system now closed,
The program commitee take up their roles.
On secretive forums, in groups of three,
They meet to discuss what will and won’t be.
The schedule is short and there’s lots of bidding,
Each submission receives only a few hours reading.
Each reviewer’s position: your paper’s rejected;
Your job was to prove that it should be accepted!
The standards are high and acceptance rates low,
The hopes of some authors will suffer a blow.
Yet should worst come to worst, you need never fear;
If you don’t make it now, there’s always next year!

January 5, 2009

Hello world!

Filed under: non-technical — dharabor @ 12:51

Hi! Welcome to little corner of the web.

I decided to start this blog for a few reasons. Firstly, I’m really interested in AI and secondly, in recent times I’ve become fascinated with pathfinding techniques and in particular their application to games.

If you’re an outsider to this field you might be under the impression that pathfinding is a solved problem. While it’s true that the classical A* algorithm has provided us with a nice method for efficiently finding shortest paths in a graph it does not address many of the bigger problems we encounter in modern video games. For example, group movement and formation-based pathfinding are both open problems which require attention to many variables: do all the agents in a group move at the same speed? are they all the same shape? can they all traverse the same kind of terrain? should the group stay together or is dispersion OK? 

Other problems involve finding paths in apriori unknown environments (for example, pathfinding with fog-of-war turned on), dynamic environments with changing terrain, and real-time environments where our units must respond in a (usually very small) timeframe. When we increase the complexity of the prototypical pathfinding problem in these ways we often also increase the amount of computation that is required to produce a solution. This calls for different techniques to be employed of which A* is often only a small part of. 

I hope to discuss these problems and other related issues on this blog; more for myself I think than for any particular audience. If this happens to be useful to others however, then so much the better!

Blog at