The Evolution of Alphonse

Quite a while ago I came by this web forum called Avalon. It was a roleplaying forum, where your board account was your character and you’d be able to collaboratively write a story with other members. You’re only allowed to control your own character or NPCs and there were other restrictions such as having to purchase an item form the shops before you can use it.

Invisionfree (now Zetaboards) provided the board that I joined, which was actually the case for a significant amount of similar sites. There were so many that IF had a separate section in their board directory just for them. The development forum was also full of little javascript snippets that could be used on sites to add profile fields (class, race and others) or display the amount of gold a user had (in our case, 5 x post_count) and many other functions.

One day when trying to access the site, members discovered that the board was no more. The ‘owner’ had deleted it because she no longer had time to run it properly, but one of the ex-members decided to start it up again and we reconstructed the site as best we could. I helped out in the reconstruction because I had some basic knowledge of html and javascript at the time. My help eventually earned me the position of Admin and that is when I came to realise exactly how much time it actually took to run a board like this.

You see, everything that happens on the board is a manual process. Every time a user wants to buy something from a shop, someone with the appropriate privileges has to alter the user’s post count in order to remove their gold and then place the item image in their signature. The same manual process must be done for name changes, gold transfers between characters, custom item requests and so on. Then you get the inevitable disagreements and reported posts that have to be policed and eventually you find that you don’t post any roleplays because all of your time is spent just running the site.

That is when I came up with the idea for Alphonse. It was to be a bot written entirely in Perl and built upon my experiences of coding MSN, Yahoo, AIM and IRC bots. It would have administrator privileges and could be commanded via private message. The bot could take care of almost everything that would otherwise be left to the admins and mods. You could message it with a set of instructions and it would perform specific actions. Alphonse overall seemed to be a good idea and reasonably well executed. There were some hiccups but on the whole it performed as desired. Unfortunately some posts have been removed from the board but the bot grew to encompass almost the entire functionality set of the admin panel for the board. It could prune the member list of inactive members, detect spam and then flag the topic and all contributors. Some contributors could reply with a safe word to de-flag the post otherwise the poster would be permanently ip-banned and the topic removed. It even sent out a mass PM of a survey that some admins had come up with and anonymously logged the responses to provide statistics.

All of this automation was in some ways quite scary. Alphonse was editing a live website after all and if something went wrong, it could be a disaster. This did occur and led to the demise of the bot, but I’ll get to that later. Along the way, some small hiccups also came to light. One such was when changing people’s usernames. It should be common knowledge to developers that you can never trust any input provided by the client. Client-side checks are simple to bypass and if they are the only things verifying your data then you have designed your system very wrong. That point was apparently lost on the Invisionfree developers who would accept name change requests after only client-side validation. The trouble Alphonse faced was that it didn’t have any client-side validation. It could (and did) send empty strings as the new name and since Invision were trusting the client to ensure the name was valid and Alphonse was trusting the server with the same task, the user ended up without a name.

Thinking back on the code for Alphonse, I am actually quite surprised myself at how well it worked. The idea was simple – http requests are very straightforward in Perl, but with all of the string matching and regexs in order to pull messages from the html, so much could have gone wrong. With that being the case I actually opened a support ticket with IF and explained the bot, then asked for their permission to continue running it. The response I got said that they were certain I couldn’t create such a thing, but if I could then it was okay to use. That moment was a proud one for me. These developers working on production quality code said it wasn’t possible but I’d already created it. Thinking back on that moment, I don’t actually know why they claimed it wasn’t possible. With a basic understanding of sockets, anyone could have done the same.

I suppose you can’t quite make out the ascii art title there, but it says “Alphonse v2″.

Now we get to the unfortunate part. One terrible morning Alphonse went down and there was major trouble. Part of the code had somehow been corrupted and I hadn’t made a backup, so I had to code it again from memory. That took roughly 2-3 weeks but during that time people had sent it requests and then got frustrated when they hadn’t worked. Subsequently they had got the moderators to perform their request manually. When Alphonse was fixed I could have done a very simple thing and just cleared the inbox before starting it again, but I neglected to do so and the result was that 2 or 3 weeks worth of requests were all processed twice – once by the mods and once by the bot. It caused no end of trouble and unfortunately signaled the end of Alphonse.

At least I thought it was the end, but it wasn’t. First though, let us diverge a little.

Some time after the end of Alponse I started up a new roleplaying forum of my own. Avalon was nice, but I’m not a great fan of fantasy; I prefer science fiction. I’d had this idea for a Sci-Fi site that I had seen nowhere else. It was to be as limited as your imagination, or the combined imagination of all its members. There would be no set weapons, there would be modules that you can use to craft a weapon, with rules governing the structure but otherwise left to the user. If you couldn’t find a module you wanted, you could invent one. Your character was customisable and, since it was set in the future, that included replacement body parts that were more durable or enhanced in some other way, like night vision eyes. The setting was a dystopia where a walled-in city kept its inhabitants captive and oppressed, save for those few who rebelled. Each section of the city could be controlled by enforcers or rebels and fought over for control at any time. The city had rules that dictated whether a citizen could be in any one zone at a time. For example, the commercial zones were all out of bounds during the night. Any citizen caught in this zone during restrictions should be prepared for a fight.

In some ways it was a complicated idea but I was much younger and more creative back then. The reception to the idea was very positive, but I had given myself a heck of a burden. This site was even more interactive than Avalon and there was no Alphonse to relieve any of that. As such, it fell into neglect and eventually closed down.

Meanwhile, the legend of Alphonse was not dead. A member of Avalon had proposed creating a new version of the bot (this was some time after the original) and the project went ahead. The administrators were not as pleased about the idea of a bot now as they had been originally. Here is a quote from one:

Lantana

To be honest, one of the only problems I had with Alphonse back then was the sheer fact that his existence meant I, as a then-admin, didn’t… really have anything to do anymore. So I’m behind the “but we don’t really need it” argument.

In some way this is the ultimate praise for Alphonse. The fact that after its creation the admins had no tasks to do is a huge statement about the ability that the bot had. Unfortunately after numerous attempts, the successor to Alphonse never appeared and the board continued to be manually administered.

That is how things stayed for many years. One day, though, the admins decided to make a new board. It would be phpBB based and because they would have full source access, a lot of the boring manual process could be automated. The board could also be more feature-rich and interactive than the IF/Zetaboard setup that is presently in use. So the new board was created and some development began, but the project was never finished and eventually became abandoned.

After I completed the TeeFury app that I described in my last post I was looking for something else to do, and I had a suggestion to remake my old roleplaying site. I probably wouldn’t use the site myself, but I asked a lot of old members and they all agreed that they liked the idea and would probably join it if it existed again. I went back to Avalon for some ideas and noticed the discussion about creating their own custom board. I’d planned to do that for my site, so I offered a partnership. We would work together on a core board and would branch the project into our own individual sites. That would allow Avalon to have the custom board they wanted whilst also relieving some of the coding burden from me. The deal was done, some code was laid down and features planned out. The whole project will be created from scratch, because phpBB is GPL licensed and we want to avoid that.

This is the natural progression of Alphonse. Once it took over all admin duties for Avalon, it could only either die or evolve into a board of its own. In actual fact it did both. The new board will be as automated as possible so that the site can be run by very few staff members. It will be modular in nature, containing a core board and an event system that modules can register with. A module will be invoked when any event occurs that it wants to know about, and it can then affect the board as it needs to. The client and server code are loosely coupled, so that the server never tells the client how to display anything. The aim is for a board that can be very easily extended with self-contained modules, which will allow me to have the territory system that exists on my roleplaying site but some other system entirely (or no system) on Avalon. To add or remove the system is as simple as placing the code in the plugins directory. It will be a little bit like WordPress for forums.

There is a large feature list to work through, which will probably be announced when the project is more complete. What is working at present is the ability to register and create board sections and forums. Development is happening quite slowly, because much research is being done into security best practices for a forum.

This has been a nice stroll down memory lane. I was going to post some things about CSRF attacks that I recently researched and verified as an issue for Zetaboards, but the post didn’t really go toward that subject. I’ll save that for a later post about how Alphonse all works together and what it does to protect against this and other types of attack. As for Alphonse, I hope we live up to its legend.

TeeFury

TeeFury is a really nice website. If you’re not familiar with it the basic concept is that there is a T-shirt available for sale on there each day. The tee is available for 24 hours and then never again, so you have to buy it or miss out. One problem I have is that I sometimes forget to check the site and miss out on some cool tees.

To combat this I thought about making an Android app that would alert me about new shirts each day. It should provide an easy way to take a look at the shirt and buy it if I want it. I searched the marketplace and to my surprise there are no TeeFury apps available at all. Well that’s just not on.

So I took a look at their site and discovered they actually have a mobile version available at http://m.teefury.com. It is laid out really well and kind of made my app idea moot, with the exception of the alerts. I could have just set a daily alarm telling me to check the site but I decided to continue with the app.

One thing the mobile site has is access to artist bios, comments and the gallery. There is no API for the site but they do provide an RSS feed. This is limited to the daily tee information only though and doesn’t even give access to comments. Because of this I went down a slightly different route.

My idea was to use a WebView control to display the actual mobile site but add some additional details and the all important alert. It actually made things much easier and faster to develop and I completed the project in a weekend.

I knew in advance that I would have to process the page and remove some elements such as the link to view the full site and the navigation bar. I’d also have to ensure that external links opened in the default browser instead of in the WebView. Something I really wanted to avoid was writing a socket class and pulling in all the data, stripping out the parts we don’t want and then passing it to the WebView. I’ve done that before with my Criticker app and it came with all kinds of problems. It is possible to set the url that the WebView should load and in standard desktop browsers typing in javascript as a url normally works. So I tested it with the WebView control and, after enabling javascript, it also worked. That meant it would be relatively easy to hide the unwanted page elements after the page was loaded.

The javascript I settled on was this

javascript:(function()
{
	var i=document.getElementsByTagName('header');
	i[0].style.display='none';
	i[i.length-1].style.display='none';
	document.getElementById('navigation').style.display='none';
	document.getElementsByClassName('back-to-top')[0].style.display = 'none';
})()

The main reason for getting all elements by tag name is that the markup for the site is slightly off. It contains two header tags which both have the same id, so getElementById doesn’t work as it should. I could remove all header tags but for the gallery page some of the required information is inside these. On every page the first and last header tag always have to be removed, so that is what is done here. In addition, the navigation and back to top link are also removed.

In testing this worked well, but there was a skip between the page loading and the elements being removed from view, so I had to hide that. I came up with the idea of a loading screen for every time the WebView has to load a different page. That hid the visual disappearance of the elements and made it look much more slick.

Finally, I created a BroadcastReceiver that would be invoked on phone boot, so that restarting the device doesn’t cause the alerts to cease. Once per day the rss feed is accessed and if it has changed, an alert is shown on the device. Pressing this alert loads up the app and shows the new tee.

Controlling video with QR codes

One of the worst things about applying for jobs with demos is that you have no idea if it is going to work on the computer of the recipient. You can make a good guess by ensuring that you package it up properly with all dependencies, but how do you know which platform they will be running it on, what their hardware supports etc? Well, it’s possible to create a cross platform demo and implement fallbacks to ensure that it works with almost all hardware, but what I found when making demos for my applications is that I barely had enough time to actually implement the game for my own system before I needed to start either sending out CVs or look for a box to live in.

So I had this idea for a different solution. Why not just send them a whole PC with your demo stuff on? Then you can leave a video CV on there and help yourself stand out against all those paper CVs. Now when I say PC, I am talking about something similar to a Nano or Pico ITX board. Small, reasonably cheap and low power. It wouldn’t be too much of a stretch to put it in a nice little box and have the video play automatically when the lid is opened.

I’d sat on this idea for a while, imagining that one day when I am apply for my “dream job” I will use this method. Assuming they don’t instantly think I’ve sent them a bomb, It should work quite well.

Recently I’d had a different idea along the same lines though. I was daydreaming about a gift I would like to give a friend as a birthday present, where the same boxed computer is used but I would place a set of small gifts in as well, and the video would describe the items and their significance. I ran with that idea, but all in all it didn’t present me with anything of a challenge. Having VLC auto play when the computer boots and display a video is a trivial 10 second project. What could I do to occupy myself and enhance this project? Well, QR codes of course. Instead of having the video simply play, I could attach QR codes to each item and scan them with a webcam. Then a video description of that item would play and so the order in which the items are taken from the box wouldn’t be dependent on the order in which they were recorded in the video.

So, first things first I set about trying to make a little program to play an AVI video. Not as easy as I had imagined it would be. LibVLC seemed like the most sensible option but I could not for the life of me figure out how to actually implement it. So I tried OpenCV, knowing from past experience that it could stream from AVI files. About 5 lines of code later I had a video on the screen but disaster! There was no sound. Not feeling disheartened enough to just rip the audio and add FMod to the project, I went down the route of DirectShow. There are some good samples that come with the Windows SDK and I based my implementation on one of those, “VMR9“.

Having spent about an hour ripping out anything from the sample that I didn’t need, I went through the code and pieced together what it was doing to achieve video playback, then implemented it myself in a separate project. That went reasonably well and I ended up with a window that could play an episode of House, with hotkeys to skip to set points in the video.

Next up was QR scanning. I took a look at how QR codes work with the help of some online documentation and made a little program to generate codes from text data

Following the reverse of that principle I should have been able to read QR codes back in and extract their string data. I never actually got around to trying that though because it was too rigid a solution. The scanned image would have to be positioned exactly right in order to scan it properly. Image processing isn’t something I’ve had a whole lot of experience with, so I looked for a library that could help me out.

ZXing was suggested to me and I took a look at that but the closest implementation was Objective-C for the iPhone. To be totally honest, It’d taken me 8 hours to get AVI working and I’d lost a lot of patience by now, so I was looking for an easier solution. After trying a few different libraries I found libdecodeqr. It sounded perfect for what I needed but of course things were not going to be that easy. The website has long ago disappeared, so I googled around and found another project. Alex Karpus has this project for iPhone and WinMo that can scan QR codes using OpenCV. I knew from a little tinkering with WinMo in the past that it would be very easy to convert that to run on Windows, but to my surprise the solution provided on the website includes a Windows version already. The only issue I had with the provided solution was that it loads the QR code from a file whereas I wanted to take mine from a webcam. OpenCV makes that easy though and in fact it was about 5 extra lines of code in the end.

I implemented QR code scanning in my existing AVI solution referencing the project from Alex’s website and soon had the ability to “reset” the video by scanning a QR code. I won’t say it went off without any hitches but those I did have were relatively easy to overcome. What I ended up with was this:

The QR in the picture, if you can’t read the text beneath, is the encoded string “RESET”. Any string can be used and if it’s not in the list of usable keywords it is simply ignored. I was actually very impressed at the speed of the decoding library and how well it coped with my low quality webcam, usually picking out the code while I was still moving the paper into position.

At this point I started a new project. What I had was working but was by no means good code. I’d hacked it together from samples and my own ideas but I had always intended that to only be a proof of concept and to rewrite it when I had it working. For the final project the QR code words should be loaded from a file, as well as the filename of the video to play. That way new markers can be added without having to recompile, or thing can be changed to show a different video.

As a test of the final project I had to think about what I had that I could record and settled on the idea of some books. A video with an introduction that explains to the user they must scan a QR code, then a set of idle clips. These idle clips would play whilst the program is waiting for a QR code to be scanned. The switch in state from a main clip to an idle clip would trigger the start of the scanning process and would continue until a code was found. A group of QR codes would be put on a set of books and I would record myself describing the books. One additional video clip is needed for when an invalid QR code is scanned, so that I can alert the user of the error.

It took some experimentation but eventually I made a small test where I recorded myself holding up each of the books in turn. After that I scanned each of them to see if it would scan properly and cut to the correct clip. For the majority it worked, but one or two didn’t scan correctly and cut to the “unknown” clip. Repeated scanning of these eventually yielded results, with the exception of the code for “How To Live Safely In A Science Fictional Universe”. The string I encoded for this book was “HTLS” and for some reason the library just couldn’t pick it up. I’m not sure if it is due to the pattern on the cover or just a particularly difficult code to pick out of the image but I haven’t managed to successfully scan this code yet.

Here is a short video of the first test:

Knowing that the idea was now working, I recoded some more detailed video clips that describe the book, or some memory I associate with it.

On the whole I think this project turned out well and should be sufficient for both of the use cases I envisage for it. In the future I may work on some extensions, such as some universal commands for volume and playback control or a set of codes that correspond to individual shows/films, which can be scanned to begin playback of those.

The code is available under a MIT license and can be accessed along with the Windows binaries at http://code.google.com/p/qrhere.

And just for fun here’s an outtake of the last video:

Building an intelligent car

I was going to dedicate this blog solely to software projects but I’ve changed my mind so it will now be quite a general spread of things I’m doing that I want to share. Most of that is software anyway, so it’ll not be too much of a change.

For quite some time now I have been planning to build and install a Car PC. I frequently browse forums such as Digital Car or MP3Car to see what ideas other people have come up with but I tend to find that people are happy with audio, video and web browsing functionality. To me, that’s what a basic Car PC should be, but I don’t want mine to be basic.

I’d come up with some ideas like voice recognition and ANPR that doesn’t tend to be widely implemented into car PCs, but then something skewed my direction of thought quite significantly. One day during my commute to work, I was involved in quite a severe car crash. Fortunately there were no fatalities, but it really got me thinking about what I could do to help this be avoided in the future.

That was back in 2008 and since then I’ve had to keep this system only in my mind, because I still had to finish University and work for some time until I’d be able to afford to build the system. That may actually have worked to my advantage because I’ve been getting ideas from the new features implemented in luxury cars, which tend to have all the fancy safety features. It’s also allowed the development of some other technology that may not initially seem to be relevant to car safety, like the seemingly ubiquitous Kinect. I’ll come back to that later.

One thing to be aware of when reading the descriptions is that no part of this system is designed to actually take control of the car. That is because of a few factors; I’m not experienced enough with hardware to be able to create such a system reliably. Even if I did have the technical knowledge, I don’t have the budget to implement a failsafe system. Even if I had both of those, I’m pretty sure my insurance company wouldn’t be too happy with me building a semi-autonomous car in my garage and would financially punish me accordingly. Because of these factors, the system is designed purely to alert the driver and give them the maximum amount of information they need to make a decision, but all decisions that directly affect the vehicle must be manually carried out by the driver. This type of system falls somewhere in the middle ground between a car PC and an intelligent car.

So now I will write an overview parts list and then explain in some more detail about the features I will be attempting to implement in my own Car PC. I’m not going to list the obvious things like power adapters.

• Mainboard (type undecided)
• 7-inch transflective touch-screen
• Slot-load DVD drive
• Kinect x2
• HD Webcam x4
• Standard webcam x2
• Rangefinder x8 (type undecided)
• Noise cancelling microphone
• Pressure sensor x5 or x2
• OBDII adaptor/reader
• GPS receiver
• GSM module
• Tri-axis accelerometer
• Magnetometer
• Temperature sensor

Main Computer
The main computer spec is not completely decided on just yet. I’m not certain on how much processing power I will need to run the entire system. It may be some sort of mini-itx board or it may be a larger multiple core system. It might even end up being two separate systems; one for processing the sensor data and another for media and user presentation, with some communication method in between. Another consideration is the fact that the computer can be switched off, so a decision will have to be made as to what happens to the sensors in that case. In all cases, the sensor data should be recorded to a hard drive in a rolling buffer.

The space in the dashboard for the stereo is double-din, which should be fine for a 7 inch screen. It should be transflective, which is a fancy way of saying you can still see it in direct sunlight. It’s not very often I play things from a CD in the car (maybe because it only has a tape drive. Ford, what were you thinking?) but for such an eventuality there will be a slotloading DVD drive. The dash has a column of button blanks which looks to be a perfect size and location for the drive. I may add an additional small screen on the top of the dash for important information or the sat nav, to make easier to glance at when the vehicle is in motion.

OBDII
My current car has a very easily accessible OBDII slot right under the steering column. I haven’t done a great deal of work on reading these, but my first few years of programming were spent deciphering the MSNP protocol in Perl, so I’m pretty sure I can have a good go at it. Understanding protocols is actually something I find very interesting, for some reason. On the dashboard I have quite an array of indicator lights, a digital fuel gauge and a digital temperate gauge. I would assume that these are all routed through the diagnostics computer, so I should be able to gain access to them.

Of particular interest to me is reading the current fuel level because I would like to determine average MPG and factor this in to a route planning algorithm. I’m rather surprised that manufacturers don’t already do this with their built in navigation software, but my plan is to determine the distance from the start and end point, then determine if we have enough fuel to actually get there. If we don’t, then we can search a POI list of fuel stations that lie on or close to the route and factor them in. There would also be some lower threshold so that we don’t arrive at the destination on our last drop of fuel.

Webcams
Now we’re getting away from the generic car pc stuff and into the items used for safety. I figure 6 webcams are sufficient for my needs. What you should know about my car is that it’s technically a LGV. That means it was created as a car, but later had all of the rear interior removed and replaced with a flat platform. The passenger seats, parcel shelf, seatbelts and everything else, all removed. Even the glass is removed from the rear side windows and replaced with metal panels. It is basically a small van and has the advantage of lower insurance costs.

It’s not all rosy for LGV drivers, because the road tax would ordinarily be £60 and instead is a blanket £200 for LGVs of all types regardless of engine size. The other, far more significant disadvantage is that it is nearly impossible to tell if changing lanes is safe in certain situations. Where ordinarily you would look through the rear side window to cover that blind spot, all you see is a metal panel.

To combat these situations, there will be a webcam mounted beneath the car, on the side edges pointing upward and slightly behind. That way I can switch the screen to show either or both of these webcams and verify if there is a vehicle there. These will be the standard quality cameras as the image doesn’t need to be sharp, it just needs to show if the way is clear or not.

The other four, high definition cameras will have two purposes. One pair will be mounted in the centre of the car horizontally, one at the front and one at the rear. These will record into a rolling buffer that begins at 5 minutes long. In the event that a crash is detected, the 5 minute buffer will be stored on a hard drive and will continue to capture footage of the aftermath. That means all events will be captured from 5 minutes before the crash until as long as possible afterward

The other purpose of these cameras is for periodically capturing snapshots of cars in front or behind and picking out their number plate. These extracted plates will be checked against a database of user-entered car details and if a match is found, the relevant information will be displayed to the driver. Initially I thought of this as a fun way of being notified if I am close to people I actually know, if I put all of my friend’s car number plates into the database. I had other ideas as well, such as making a community-maintained database of celebrity cars. I’m not entirely certain of the legality of storing and distributing a database of celebrity car number plates though.

The other set of webcams will be mounted at the front and rear as well, but this time on the far right of the car. These will also use the rolling buffer system to take a second perspective of any accidents and to provide a backup if the centred camera is destroyed. Its other use will be an aid for seeing past vehicles directly in front of the car. This is particularly useful in situations like congested motorway driving, where it is an advantage to see further down the line for advanced warning of drivers braking. It also helps for situations like overtaking a stopped bus, where the driver would ordinarily have to place the right of the vehicle near to the centre line if they wish to see into oncoming traffic clearly. Having a camera mounted on the far right of the vehicle would allow them to see past the bus without having to be as close to the line.

Rangefinder
The range finders will work in conjunction with some of the webcams to achieve a similar goal. This is one of the first safety ideas I had for the car and I was surprised recently when I saw a Ford advertisment that showed off the same feature, referred to as a “blind-spot monitoring system“. In my system, a sensor angled on the front and rear corners of the car detects if there is another vehicle next to ours. If we tap into the indicator lights on the dashboard we can tell if the driver is attempting to change lane or turn into another road. So combining these two factors we should be able to alert the driver if it is actually safe or unsafe to pull out. Due to the blind spot I mentioned earlier that is difficult to see with no rear windows, my system will contain an additional side sensor to cover this spot and provide more immediate feedback to the driver than the webcam equivalent.

The final two sensors will be mounted centrally on the front and rear. These will measure the distance to cars in the same lane as us, which will be tracked over time. We can determine the speed of the cars in front and behind us by taking our own speed reading from the OBDII sensor and change in distance between our vehicle and theirs. That should allow the system to determine if we are too close to the vehicle in front and warn the driver to back off. If the two cars are decelerating, or if the vehicle in front is even stopped, we can determine if the driver is slowing down enough to avoid a collision. In the same vein, we can determine the same for the driver behind us and cause an alert if the system thinks they are going to cause a rear end collision. The driver can then try to move out of the way. In fact with the other sensors on the vehicle, the system itself could more quickly determine the best way to move out of the approaching vehicle’s path. It is not too far removed from adaptive cruise control

The temperature sensor can also play a part in this feature of the system, by determining if the weather is likely to cause ice it can alter the stopping time that we are using in determining if our distance is safe. Ideally we would also have an internet connection that we could use to query an actual weather website and check for more detailed weather information, such as fog and rain.

Pressure Sensor
These exist in many vehicles. I have most recently witnessed them in a coupe model Mercedes where they are used to detect if a passenger is present and extend the seatbelt arm if they are. Additionally the car provides an alert to the driver if a passenger is present but the seatbelt has not been fastened. The same feature is what the pressure sensors will be used for in my system. I have noted either two or five sensors above because due to the vehicle being an LGV, it only has one passenger seat. Before I build the system into my daily car I will be testing it on a project car which has five seats though.

Now, you may be thinking that I should really only need 4 or 1 sensor because it is fairly obvious the driver will be present. That is true, but the sensors have another useful feature. They can be used to measure the actual amount of pressure placed on them, which can be provide us with the weight of the passenger. If we combine all of the weights we will be able to factor this into the MPG estimation that is fed to the route generating algorithm. A car with 5 people will obviously weigh more than with only 1 person and that will have an effect of how far we can travel with the amount of fuel we have.

GPS and GSM
These two systems work individually to provide positioning data for the routing and directions feature and for communication over the internet to find weather information and any other relevant data we need (congestion information, for example). They can also work together to provide a tracking system that will be useful in the case of theft. My initial idea was to place a hidden button in the car that must be switched before starting the engine. If this switch is not flicked and the engine is started, the system will begin tracking the vehicle’s location and relaying it to a web server which will store and plot the data. At the same time it will send an SMS message to a pre-set mobile phone number to alert the owner that their vehicle is moving without their permission. The driver may respond with some predetermined command words to allow the system to cease tracking in the case that the owner has authorised the car to be driven, but the driver has not flicked the switch.

I had toyed with the idea of building an engine shut-off feature into the system so that the owner can issue a command the car would cut out. If I’m totally honest what I would prefer if someone stole my car is to issue a command that caused electrified flaming razor blades to shoot at whoever was behind the wheel, but unfortunately I have to be both realistic and legal about what I implement. Causing the engine to shut off could endanger the occupants of my car and other cars around it.

Another idea I had was allowing the system to automatically alert the emergency services about the theft, but I came to the conclusion that alerting the owner would be sufficient as they could subsequently alert the police and be much more dynamic about answering questions they have. This idea did evolve into another similar feature which I will come back to in the accelerometer section.

Kinect
Okay so I’ve deliberately put the explanation of this part off until near the end but I will finally explain it. The Kinect seems to be popping up in pretty much everything now, but I do have a reason to include it in this system. I was struck by this idea when writing some demos to get to grips with the Kinect and watched the depth image display so clearly in the pitch black of a midnight coding session. I will mount a Kinect on the front and rear of the vehicle and use it to either pick out pedestrians standing near to the edge of the road (or in fact in the road itself) and alert the driver, or to aid in determining the distance to vehicles in front and behind us. It may also be used as some form of night time driving aid, similar to “automotive night vision systems.

When parking, the Kinect also gives us an advantage because it can map out the space in front and behind the car, displaying it to the driver with colour coded distances. In fact it doesn’t need to be at night, but that is obviously the time where vision is most impaired so would provide the greatest amount of assistance.

As the Kinect also has a colour camera, these may be used in place of the front and rear mounted HD cameras, if the quality is sufficient enough to pick out and read number plates.

Accelerometer & Magnetometer
The accelerometer and magnetometer will be used in the event of a crash, to determine the force of impact, the direction of the car on impact and the final resting position. There is already a standard, known as the “Vehicular Emergency Data Set” (PDF) which describes an automated system for reporting crash data to the authorities and that is what will be implemented by my system. Unfortunately since the UK has no way of communicating this to the authorities, the file will be stored locally. A crash can be detected by hooking up to existing crash sensors in the car as well as looking for spikes in the accelerometer data. This data will be recorded in a rolling buffer that matches the stored video, so can be read side by side to form a complete picture of the entire event.

If a crash is detected, a dedicated LED momentary switch will be illuminated and the driver must push this in order to let the system know that they are conscious. There will be a cut-off time that is yet to be determined and if the button is not pushed before this runs out, a pre-set contact will be informed of the event along with the car’s last known GPS location. In the future if the UK decide to implement an automated crash reporting service, that will also be used to alert the authorities about the incident. Pending legal issues, I may in the mean time include an automated call that uses text-to-speech conversion for relaying the information.

Implementation
I will begin to implement this system into a project car toward the end of August. The first part will be to build the basic PC and integrate it into the car. The system has to look OEM and seamlessly work with the existing dashboard setup. It will also likely require most of the internals to be removed for laying down cables. Finally there are some legal issues I have to look into, so I’m not sure what all of that gives me as a time frame for moving on to the safety aspects but I estimate work will begin toward the end of this year or beginning of next. Obviously the blog will be kept up to date with progress reports, so be sure to subscribe or keep a look out.

Destroy All Vegans (again)!

A little while ago I began a project titled “Space Domination”, which was intended to be a little demo piece that I could place on my portfolio. The ideas kept flowing and it went from a little demo to a much larger project, “Destroy All Vegans”. The trouble with that process is that I hadn’t really planned the game out past the demo process, so I was pretty much making it up as I went along. That can only get you so far, and eventually I moved on from DaV to other projects.

Well that is about to change. The current instance of Dav will no longer be developed and the project is to be started from scratch. Now that it is no longer a demo piece I can spend much more time getting the features right, researching different libraries and hopefully making a much more polished game.

The new game will feature only a single planet in the scene at any one time. The currently viewed planet can be switched, but you will no longer have to move through a seemingly endless amount of empty space in between. I will be testing scene sizes to come up with one that is large enough to give advanced warning of invasion while small enough to stop the player getting lost in the void.

I also imagine now that rather than ships and structures simply disintegrating when destroyed, they will instead become inactive and float in space ready to be recovered or scavenged. This is loosely based on the same principle that I witnessed in a Star Trek game I played for research. The difference in DaV will be that broken items will be susceptible to gravitational pulls of nearby celestial objects, so any scavenging or recovering vehicle must be quick to react. It also means I get to create a nice atmospheric burn up shader.

Unfortunately I don’t have much to show for the efforts right now. I have been creating small prototypes of features or ideas and I may release a pack of all prototypes at some point. One I can display screenshots of at the minute is a test for moving from Ogre’s lighting model and simple material files to using a shader for lighting or, in this case, determining if the lit or unlit texture should be used.

The images in this gallery show, from left to right right to left (WordPress doesn’t like me today), my initial test of determining which texture to use and blending between the two. Mars was used until I could find a night time Earth texture. The next image shows Earth in its day and night phases. The final image shows the beginnings of an atmospheric scattering shader that I will hopefully have completed soon.

Now compare that to the Earth in the original version.

You’ll notice that in these versions, the clouds show up even when there is no sunlight touching the surface. That is an issue related to using materials to blend alpha maps and is resolved in the new version. There is also no atmosphere on the old planets either and as I wasn’t using shaders, adding them would have required a second semi-transparent sphere to be created which would double the number of celestial object meshes in the scene.

The next thing to create will be the atmosphere, which should be white at the very edge of Earth, then fade to blue and finally to black. Afterward I will do some research into how far from Earth you can go and still be able to see the city lights. That way I can check the distance to the camera and if it is over the threshold ignore the night texture and instead show solid black, for more realism. The best idea would probably be to fade the texture out or in at the boundary of the visible distance so that is Earth gets nearer the lights should appear to brighten. Finally, I will look at testing particle effects for broken ships; billowing smoke and fire. Then I will make it so that they float toward planets/moons and burn up at a set distance from their surface.

That’s all I have to show for now. If you have any comments, be sure to leave them below.

Pathfinding 1: Short paths

In this and the next few posts I will be working on some simple pathfinding demos. I find pathfinding quite an interesting topic because it allows small alterations to create large visible effects. A little project I did a little while ago was my first look into A* and allowed an NPC agent to navigate a scene by finding waypoints which provided the most amount of cover. I’ll be recreating that as a first demo.

I’m going to try to split these posts into two sections. The first section will show what I have created as an overview, without any code. The second part will show some of the code that makes it work and discuss my reasoning behind some coding decisions.

The App

So to begin with, I needed a base. Just a simple scene containing some obstacles, waypoint nodes and some agents. From that I could implement simple A* pathfinding and verify that everything functioned as it should. I made use of Ogre because I’ve already had some experience with it and it takes care of everything we’re not really interested in for this demo. In addition I utilised the Ogre App Wizard, which saves us time by generating all the code required to get something rendering with Ogre. I’ve also written some code to load a scene from an XML file, so the values for the scene can be altered without needing to recompile everything or use some visual scene editor.

Here’s how it looks with a ground plane, ambient light, some path nodes and path edges:

My preferred method of pathfinding with A* is to place lots of nodes about the scene, as you can see in the above image. These particular nodes are programatically generated in a grid pattern but they don’t need to be. Other people that I know prefer a different method where the nodes are placed by hand only where they are required. That method allows you to place lots of nodes in places where you need fine movement and sparse nodes where movement doesn’t need to be so precise. There are arguments for and against both, but really the best one depends on the individual situation. A grid of nodes should be fine for this particular demo.

For our A* to work we need to set our G and H values. As a heuristic I decided to use the Euclidean distance from the current node to the goal node. As this is simply an estimate it doesn’t need to be exact, so I utilised Ogre’s SquaredDistance function to save us a little computing time. The heuristic is calculated on the fly as we are pathfinding so any time savings we can make will be an advantage to us.

For the G I simply chose a cost of 10 for travelling on vertical or horizontal paths and 14 for travelling on diagonal paths. It is a crude representation of the distance between nodes and ideally we’d precalculate and store these values. The distance to move diagonal is roughly 1.4 times the distance to move horizontally or vertically, so that is why the values are 10 and 14. It is a simplified version of our actual distance (100 and 140, respectively).

Just in case you’re tempted to set all of the edges to the same cost, here is an example. On the left is a grid with all nodes using a cost of 10. On the right, diagonals are 14. The nodes are the blocks and green highlighted ones are the generated path. As you can see, although the start and end nodes are in the same ‘column’, the equally weighted path still moves diagonally. That’s because the diagonal edge is checked first. Even if we randomise the order in which we check (a good idea, because two paths may have equal weight and if we never randomise we’ll always take the same path. That makes our movement predictable), we’re still going to generate a crazy path rather than the straight line that we want.

A flat plane to walk on is nice, but there’s no point in pathfinding if we can walk to any point in a straight line. We need obstacles to navigate around if we want this to actually have any sort of worth. Now, my level design skills are *ahem* lacking at best, but I added some nifty buildings to cause us to have to generate paths around them. In addition, I added a little bit of polish to the scene with a spot light, some shadows and a skybox. The buildings worked out well because they are a perfect size to fit in the space between a group of nodes. That makes our life a whole lot easier, as we would have had to manually tweak the nodes otherwise.

Finally it looks like we’re getting somewhere. An agent could happily wander around this map in the wide open spaces or down the alleyways between buildings. They alleyways will become more useful in the next post, where an agent will seek a path under cover, but for now all the weights for nodes are based solely on their distance to each other and to the goal. I created two agents, a robot and a ninja, with some basic behaviour to pick a random node, walk to it and then repeat.

Here you can see them in action. The first video is a release build, which only shows the scene and the agents creating paths around it. The second video is the same thing in debug mode, where we can see the nodes as grey or green cubes and the edges as blue lines. Toward the end you can just see at the right hand side when the Ninja reaches a goal node and creates a new path, the nodes that are part of the path change from grey to green.

We’re now finding the shortest path around the map to a random point. In the next post I will expand on what has been created here to take into account how much cover a path will provide for the agent and show how it affects the path that is generated.

The Code

The most relevant code at this point is going to be the actual A* implementation. For mine, I created a Graph class which contains functions for generating nodes and edges, as well as calculating the travel cost between nodes and finding paths. Below is the Graph class’ function for finding a path between two nodes.

bool Graph::findPath(PathNode* pStart, PathNode* pEnd, std::stack<PathNode*>* pPath)
{
        if(pStart == NULL || pEnd == NULL)
                return false;

        if(pStart == pEnd)
                return true;

        std::vector<PathNode*> openList;

        openList.push_back(pStart);
        PathNode* pCurrNode = NULL;

        while(!openList.empty())
        {
                //Get best node from open list (lowest F value).
                //Since we sort the list at the end of the previous loop we know
                //the front node is the best
                pCurrNode = openList.front();

                //Exit if we're are the goal
                if(pCurrNode == pEnd)
                        break;

                //Remove the node from the open list and place it in the closed
                openList.erase(openList.begin());
                pCurrNode->setClosed(true); //We use a flag instead of a list for speed

                //Test all of the edge nodes from the current node
                std::vector<Edge*>* pEdges = pCurrNode->getEdges();
                for(std::vector<Edge*>::iterator i = pEdges->begin(); i != pEdges->end(); ++i)
                {
                        PathNode* pEdgeNode = (*i)->pNode;
                        //If it's closed we've already analysed it
                        if(!pEdgeNode->getClosed())
                        {
                                #ifdef _DEBUG
                                        pEdgeNode->setMaterial("Examples/RustySteel");
                                #endif
                                float cost = calculateCost(pCurrNode,(*i));

                                if(!inList(pEdgeNode,&openList))
                                {
                                        openList.push_back(pEdgeNode);
                                        pEdgeNode->setGCost(cost);
                                        pEdgeNode->calcHCost(pEnd);
                                        pEdgeNode->calcFCost();
                                        pEdgeNode->setParent(pCurrNode);
                                }
                                else
                                {
                                        //If this is a better node (lower G cost)
                                        if(pEdgeNode->getGCost() > cost)
                                        {
                                                pEdgeNode->setGCost(cost);
                                                pEdgeNode->calcFCost();
                                                pEdgeNode->setParent(pCurrNode);
                                        }
                                }
                        }
                }

                //Place the lowest F cost item in the open list at the top, so we can
                //access it easily next iteration
                std::sort(openList.begin(), openList.end(),  Graph::compareNodes);
        }

        //Make sure we actually found a path
        if(pEnd->getParent() != NULL)
        {
                while(pCurrNode != NULL)
                {
#ifdef _DEBUG
                        pCurrNode->setMaterial("Examples/GrassFloor");
#endif
                        pPath->push(pCurrNode);
                        pCurrNode = pCurrNode->getParent();
                }

                reset();
                return true;
        }

        return false;
}

The first thing I’d like to point out is that I don’t use a closed list in my implementation. Instead I have a boolean flag that is set on a node to indicate that it has been closed. This simply allows us to query the node directly and saves some time, otherwise we would have to check a potentially large list of nodes to see if our one is contained within. This approach does have some drawbacks in that it requires us to reset the node after every path generation. For a very large set of nodes this method may turn out to be slower, but for this implementation it works well.

The open list in this sample could be greatly improved upon. The requirement of the open list is that it should be sortable and allow values to be pushed and popped. In my sample I use a function that iterates through the vector and sorts every element by F value, but for our A* to work we only actually need the top value to be the lowest F and we don’t care about any others. What we could actually do is sort the list to bring the two lowest F cost nodes to the front. Then we pop the lowest F cost node to analyse it and if the resulting nodes have a lower F cost that the current open list front, we can push_front, else push_back. That will ensure we never have to sort the entire list again.

The final point to make is about shipping off the cost calculation to a separate function. This is purely to make things easier for the next step, where we can factor in optional additional costs to the path. At present, here is the calculateCost function.

float Graph::calculateCost(PathNode* pNode, Edge* pEdge)
{
	float cost = pNode->getGCost();

	cost += pEdge->moveCost;

	return cost;
}

If there are any more points that I haven’t raised already, please do so in the comments.