A* Algorithm implementation in Python

pathfinding

Lately I’ve had the idea of creating a text-based Roguelike in C++. This lead me on to think about the game AI experiments that I worked during my degree in Computer Science and A.I.. Essential to game AI is the notion of pathfinding, or finding a path from ‘A’ to ‘B’, past any obstacles that get in the way. One way to do this is to use the A* algorithm. I decided to implement an A* pathfinding algorithm for possible use in a Roguelike later, and chose the pseudocode from the Wikipedia example to implement.

The program finds a path from the top right hand corner to the top left, avoiding impassable ’7′ obstacles. The ‘*’ are the steps along the path. The algorithm is guaranteed to find the shortest path between the goal and the start, which means it can optimally solve any solvable maze, given time.

This is a sample board with obstacles setup:

00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000777000000000000000
00000000000000000000000000000000777000000000000000
00000000000000000000000000000000777000000000000000
00000000000000000000000000000000777000000000000000
00000000000000000000000000000000777000000000000000
00000000000000000000000000000000777000000000000000
00000000000000000000000000000000777000000000000000
00000000000000000000000000000000777000000000000000
00000000000000000000000000000000777000000000000000
00000000000000000000000000000000777000000000000000
00000000000000000000000000000007777000000000000000
00000000000000077777777777777777700000000000000000
00000000077777777777777777777777700000000000000000
00000077777777777700000000000000000000000000000000
77777777777000000000000000000000000000000000000000
77777777000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
77777777777777777707777777777777777777777777777777
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
70777777777777777777777777777777777777777777777777
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
77777777777777777777700000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000777777777777777777777707777777
00000000000000000000700000000000000000000000000000
00000000000000000000700000000000000000000000000000
00000000000000000000700000000000000000000000000000
00000000000000000000700000000000000000000000000000
00000000000000000000700000000000000000000000000000
00000000000000000000700000000000000000000000000000
00000000000000000000700000000000000000000000000000
00000000000000000000700000000000000000000000000000

This is the path found (the ‘*’s):

**000000000000000000000000000000000000000000000000
0***********************************00000000000000
00000000000000000000000000000000777*00000000000000
00000000000000000000000000000000777*00000000000000
00000000000000000000000000000000777*00000000000000
00000000000000000000000000000000777*00000000000000
00000000000000000000000000000000777*00000000000000
00000000000000000000000000000000777*00000000000000
00000000000000000000000000000000777*00000000000000
00000000000000000000000000000000777*00000000000000
00000000000000000000000000000000777*00000000000000
00000000000000000000000000000000777*00000000000000
00000000000000000000000000000007777*00000000000000
00000000000000077777777777777777700*00000000000000
00000000077777777777777777777777700*00000000000000
00000077777777777700000000000000000*00000000000000
77777777777000000000000000000000000*00000000000000
77777777000000000000000000000000000*00000000000000
00000000000000000000000000000000000*00000000000000
00000000000000000000000000000000000*00000000000000
00000000000000000000000000000000000*00000000000000
00000000000000000000000000000000000*00000000000000
00000000000000000000000000000000000*00000000000000
000000000000000000******************00000000000000
777777777777777777*7777777777777777777777777777777
000000000000000000*0000000000000000000000000000000
0******************0000000000000000000000000000000
7*777777777777777777777777777777777777777777777777
0*****************************00000000000000000000
00000000000000000000000000000**0000000000000000000
000000000000000000000000000000**000000000000000000
0000000000000000000000000000000*000000000000000000
0000000000000000000000000000000***0000000000000000
000000000000000000000000000000000*0000000000000000
000000000000000000000000000000000**000000000000000
0000000000000000000000000000000000**00000000000000
77777777777777777777700000000000000***000000000000
0000000000000000000000000000000000000**00000000000
00000000000000000000000000000000000000*00000000000
00000000000000000000000000000000000000**0000000000
000000000000000000000000000000000000000****0000000
000000000000000000007777777777777777777777*7777777
000000000000000000007000000000000000000000**000000
0000000000000000000070000000000000000000000*000000
0000000000000000000070000000000000000000000***0000
000000000000000000007000000000000000000000000**000
0000000000000000000070000000000000000000000000*000
0000000000000000000070000000000000000000000000***0
000000000000000000007000000000000000000000000000*0
000000000000000000007000000000000000000000000000**

Here is source code

Amit’s A* pages were incredibly useful in developing this.

(Perhaps one day I will do a flashy JavaScript version!)

Current Music Setup

I like to dabble in making and playing music. Here is the equipment and setup that I use.

Ableton Live Intro

This is the DAW I use. I have been using Ableton Live for several years now, and I know my way around it. I have tried others but they never really felt as comfortable. Live comes in three flavours, ‘Intro’ is the most basic paid-for version. I was surprised how cheap the ‘Intro’ version was, and how little I find myself needing the features of the more expensive versions. I only have one paid-for VST plugin, and that is the KORG Legacy Cell MS-20, which I use on almost all the music I’ve made.

ableton live example

KORG Electribe R-1 MK2 Analog Modelling Drum Synthesiser

This is what serves as my drum machine. I picked it up on the cheap, but I’m really happy with it. I really like the built in step sequencer, and the drum synth itself. The sounds you can make from it are quite varied, and I really like the way you can put together live compositions on the fly. I’d be interested in getting some more KORG boxes, such as the EMX Electribes or the Volcas.

korg-electribe-er1-mk2

Waldorf Rocket Monophonic Analogue Sythnesiser module

This is my analogue synthesiser, which I use mainly for leads. In practice I find it quite annoying not being able to play real chords, and the lack of a sequencer is difficult because it means I can’t put together patterns away from the PC, or even really play it without a keyboard. I do like the sound, and the filter is great. The ‘fake chords’ option is great fun I just wish you could more easily change between the chords on the fly. The arp is pretty cool also. I think this will become a lot more awesome when I get a hardware sequencer, I already have my eye on the cheap BeatStep to pick up when it is released.

WALDORF+ROCKET-1

KORG Monotribe Analogue Sythesiser and Drum Machine

I don’t really use this for anything, unfortunately. It was my first synthesiser and although I liked it at the time, nowadays I find the lack of MIDI and the ribbon keyboard a major problem. I might either sell it or get a MIDI mod and install it. I find it quite noisey when recording anyway, so maybe I’ll just try and sell it. It does has some nice acid style sounds though. A shame.

monotribe

Yamaha P35 Digital Piano

I was looking for a decent MIDI out keyboard that would allow me to put together more complex melodies and learn how to play keyboards for possibly joining a band in the future. The Yamaha NP31, which was my original choice, was out of stock and so it got me looking at others. I thought it would be interesting to learn to play the piano, as we had one growing up but I never really learned before. In the store I really liked the feel of the P35′s hammer action keys, so decided to buy it. I can play some simple tunes with it but want to get piano lessons so I can improve. This will also function as my main MIDI controller for my other hardware.

717aZc6BIwL._SL1500_

Line 6 Mobile Keys 25 USB Keyboard Controller

This is a nice little keyboard controller that I use with Ableton. Unfortunately it does not have MIDI out, only MIDI via USB, but I can run it through the MIDISport to control audio hardware. The keyboard action is very nice, much better than the M-Audio Keystation 49 which I had before and would not recommend.

controller

M-Audio MIDISport Anniversary Edition 2×2 MIDI/USB Interface

This is a fairly standard cheap MIDI to USB interface. I used to use the M-Audio Uno, but that has only one input/output and it has problems with some audio hardware.

midisport

Setting up Kindlefire HDX for Development under Ubuntu 12.04

amazon_kindle_fire_hdx1

I wanted to get a Kindlefire HDX running under Ubuntu 12.04 with adb.

First I needed to setup the udev rules:

1. Edit /etc/udev/rules.d/51-android.rules as root, and add the following line (create this file if it does not exist):

SUBSYSTEM=="usb", ATTRS{idVendor}=="1949", MODE="0666"

2. Change the permission of this file by executing the following command as root:

chmod a+r /etc/udev/rules.d/51-android.rules

3. Reload the rules by executing the following command as root:

udevadm control --reload-rules

4. Run these commands to restart adb:

adb kill-server
adb start-server

5. Now when I run

lsusb

I can see the device listed.

6. Next I needed to enable adb access on the Kindlefire HDX device itself by going to Settings -> Device -> Enable ADB.

7. Finally I could run:

adb devices

within Ubuntu and have it recognise the Kindlefire HDX.

My Aeron Chair

A good ergonomic chair is a wise investment if you’re going to spend a lot of time at your computer. One of the better known ergonomic models is the Herman Miller Aeron Task Chair.

Picture of Aeron Chair

What Other People Say About the Aeron

Jeff Atwood (from Coding Horror) says:

In fact, after browsing chairs for the last few years of my career, I’ve come to one conclusion: you can’t expect to get a decent chair for less than $500. If you are spending less than that on seating – unless you are getting the deal of the century on dot-bomb bankruptcy auctions – you’re probably making a mistake.

I still believe this to be true, and I urge any programmers reading this to seriously consider the value of what you’re sitting in while you’re on the job. In our profession, seating matters:

Chairs are a primary part of the programming experience. Eight hours a day, every day, for the rest of your working life – you’re sitting in one. Like it or not, whatever you’re sitting in has a measurable impact on your work experience.

Cheap chairs suck. Maybe I’ve become spoiled, but I have yet to sit in a single good, cheap chair. In my experience, the difference between the really great chairs and the cheap stuff is enormous. A quality chair is so comfortable and accommodating it effortlessly melts into the background, so you can focus on your work. A cheesy, cheap chair constantly reminds you how many hours of work you have left.

Chairs last. As I write this, I’m still sitting my original Aeron chair, which I purchased in 1998. I can’t think of any other piece of equipment I use in my job that has lasted me ten full years and beyond. While the initial sticker shock of a quality chair may turn you off, try to mentally amortize that cost across the next ten years or more.

Joel Spolsky (from Joel On Software) says:

Let me, for a moment, talk about the famous Aeron chair, made by Herman Miller. They cost about $900. This is about $800 more than a cheap office chair from OfficeDepot or Staples.

They are much more comfortable than cheap chairs. If you get the right size and adjust it properly, most people can sit in them all day long without feeling uncomfortable. The back and seat are made out of a kind of mesh that lets air flow so you don’t get sweaty. The ergonomics, especially of the newer models with lumbar support, are excellent.

They last longer than cheap chairs. We’ve been in business for six years and every Aeron is literally in mint condition: I challenge anyone to see the difference between the chairs we bought in 2000 and the chairs we bought three months ago. They easily last for ten years. The cheap chairs literally start falling apart after a matter of months. You’ll need at least four $100 chairs to last as long as an Aeron.

There was a post with a large set of comments on Hacker News about chairs and cheap alternatives to Aeron Chairs, with a lot of people saying that there is no cheap alternative to a good chair.

What I Say About the Aeron

I just got a refurbished Aeron chair for Christmas. I am really pleased with it. It comes in three base sizes, being larger than normal I went for the Size C. Once it arrived it was a good fit, but it was easily configurable to make it into an excellent fit. I prefer my chair not to recline, so I can’t comment on whether it is not a good chair for reclining, as Jeff Atwood says, but I will say it felt comfortable and stable reclining.

The real benefit so far has been on my posture; I did not know how much back pain I was having before with my really cheap office chair. Only when I got up from a 4 hour session on my Aeron chair did I notice how much better my back was feeling. It moulds your back into a good position, and I have noticed my back clicking and popping into its proper shape, after using the chair for a couple of days.

I ordered my chair from simplyaeron.co.uk, who I am very happy with, as they provided an MK2 Size C chair with lumbar support for less than £400, which is an absolute bargain compared to the retail price of a new chair. This also included delivery! It seems like new – there are no scuff marks and everything works perfectly.

I highly recommend getting an Aeron chair or an equivalent ergonomic chair recommended in the above resources, as I have really noticed a significant difference.

2013 Career Retrospective

This year has been quite a busy and eventful one for me.

Connected Red Button
At the start of the year, I was working on the Connected Red Button team within the BBC. Connected Red Button is a major ongoing project in the Television and Mobile Platforms department at BBC North. Its aim is to replace the classic Red Button text service (which itself is the successor to Ceefax) with a new updated all-singing all-dancing interactive portal to internet content, available on Smart TVs and modern set top boxes. Currently Connected Red Button is live and accessible by pressing the Red Button on the new Virgin Media TiVo boxes. You can access the latest version of iPlayer, and the BBC News and BBC Sport smart TV apps from within one easy portal.

On CRB, I was working on the Java/Spring services layer, which connects to the various APIs of services like iPlayer that we have at the BBC, and gets all the content ready for the frontend. This data then gets passed to the very nice looking AS2 frontend to display, and that’s how it appears on your TV that is connected to your Virgin TiVo box in your living room.

The next version of CRB is being developed for Smart TVs with HTML browsers (so the frontend is in HTML5/JS instead of AS2). This type of Smart TV includes most of the new smart TVs that have come out recently, and will continue to be released in the future. The BBC (and the wider industry) is really anticipating that most TVs will be smart TVs in 5-10 years, and so the reach of Connected Red Button HTML will increase substantially so that most of the audience can be served by new applications that run on smart TVs.

Smartbridge

Smartbridge is the transitional frontend that is displayed to both 1) users that have smart TVs and internet connected STB (Set Top Boxes) capable of running our latest BBC applications such as Connected Red Button and the latest versions of iPlayer, and also 2) our traditional users that still have normal (un-smart) TVs that can only receive Broadcast Red Button (the service you get by pressing the red button on any BBC channel). Smartbridge is not a branded BBC product, it is the behind the scenes magic that helps ensure that we maintain the availability of traditional Red Button services as we simultaneously launch and develop Connected Red Button.

For several months this year I was working on Smarbridge. On Smartbridge, I was working to get the project released and out the door, which meant Java/Spring/Hibernate work, with MySQL database tinkering and some broadcast work configuring and testing the TVs that worked with Smartbridge. It was successfully released in October.

Device Hive

Device Hive is the working name for an BBC system that is an Android and iOS emulator and physical device testing platform. A server will run the Device Hive software, and mobile developers will be able to plug in their Android mobile or tablet or iPhone or iPad to the server via a USB cable, and choose an application to run on it, such as BBC iPlayer or BBC Radio Player. This application will then automatically be downloaded onto the device, and the automated Cucumber/Calabash test suite will be executed, which will step through every screen of the mobile application, triggering buttons, scrolling up and down and generally exercising every aspect of the mobile application. There will also be an option to run install and run applications on Android or iOS emulators, so we could have 10 emulators running at once, each running different segments of the automated test suite, and uploading the test results to a logging server.

Device Hive will mean, in particular, that we can test BBC mobile applications on the plethora of Android devices available, every make and model that we own of the different OS/hardware combinations can be plugged into a device hive server, and so we can see test runs for BBC iPlayer Android across all the different variations. This will mean we can help target a wider range of Android devices for new BBC iPlayer features, which will help ease the anger that some of our audience members feel because their specific Android iPlayer experience is not as good as the later models.

In October I moved departments from Television and Mobile Platforms to POD Test, and joined the new Device Hive team as lead developer. I am working in Ruby/Rails/Rspec/Cucumber and using Ubuntu Linux VMs and lots of Android and iOS devices to build up the system.

University Engagement

I have been continuing to work with Manchester University’s Ultimate Programming Society to organise and present talks to the students about working practices in software development that the BBC use. We have covered Behaviour Driven Development, Test Driven Development, Editors and IDEs and Agile Development Practices so far.

Generally I feel that I have worked on some pretty challenging projects this year, and I am very happy with being the lead developer on Device Hive, and look forward to making this project as useful and as powerful as I think it can be.

Go to top