Micromouse 2009

A good day with a bunch of schools competing and some really good runs
in the maze solvers and time trails.

Index Zero

This is a copy of my post in reply to this comment about Tony's hate of starting the use of C arrays at '1':
http://greenstripe.blogspot.com/2009/05/i-recently-read-design-document-which.html

I think you know this, but you are confusing counting the number of something (to find the number in the set) with enumerating each item, thereby giving each one a numerical reference. For enumeration, there is no particular reason why the first reference has to be '0' or '1' or any other number - or in fact a number at all ... think Javascript arrays where the index is a string - this associative array is like a c++ map.

I'm not convinced that losing the memory for element 0 is, in most systems, critical. Except perhaps where you have constructors / destructors - then you are running code on element zero.

However, I do think there is a deeper problem in C with using 1 as the first element 'because it's seen by the user therefore the conceptual gap between problem domain and solution domain is smaller'. The first that comes to mind is that (a) the user display is tied to this ascending number sequence. We don't, I believe, naturally think of things as numbers - or named as numbered. Therefore there is a lost of abstraction that really could do with being hidden. Objects (e.g. with a C++ class) could sort this. Secondly, or (b), in C, at least, where I've seen this, there tend to be -1 and +1 sprinkled randomly around the code (without the help of object oriented design). Thirdly, or (c), (what do you mean I've run out of enumerations?!) if you have to remove an element or make the list bigger in the middle, or do any sorting, then the index (which is what we are talking about) becomes invalid. But the user numbering, apparently, does not. Doesn't that mean that the whole 'fixed sequence' is an artificial construct of the specifier or developer? Where does this leave the user?

I'm sure there are more ...

One last thing: I can hear a bunch of programmers saying "but on small systems"/"my system" it's the most efficient way of showing something. But that's not the argument here. Either: (a) you bit the bullet and go for efficiency and ignore usability or (b) you abstract the user from the internals of the program but make the internal of the program easy to maintain. The third option making it easy by removing abstraction only works in very narrow cases and tends to be fragile to change.

Reply about Zuma and World of Goo

In reply to Tony's blog post: http://greenstripe.blogspot.com/2009/05/computer-games.html

Zuma: I think PopCap is a very interesting company who've been able to capture the puzzle game market by good sales, contacts and marketing. But their games do have annoyingly good but simple game play. Zuma, specifically, is a fast paced arcade game, and as such increases excitement and fun factor (and probably adrenaline - think roller coaster). I wouldn't find them satisfying all the time - but occasionally a game without much plot or exploring is a good change. It's sweet vs. savoury of games.

World of Goo has entrancing graphics, fantastic sound and music and a good game. However, the game play is, mostly, not timed giving a much gentler game. The game also is interesting for a 'explore physics point of view' but is it really better game play? I certainly appreciate the quality, polished 'production' and independent game developers. But do these actually make a better game?

Footnote regarding World of Goo: Additionally, as a programmer, I'm really irritated by how good the graphics and music are. But that's just jealousy.

Encryption, Linux, Programming

Been creating encrypted disk images on the USB key I carry around. I released I had various projects (not all mine) and personal data that wasn't protected. Created encrypted disk images - cross platform ... so it should at least slow people down :-) The thing with disk images is that you don't need to do a seperate encrypt/decrypt cycle, like you do with something like GPG.

I also really want to play properly with an up-to-date Linux. My main machine is a PowerPC box and I do have recent Ubuntu for PowerPC - but really want to run both in parallel. Projects like Mac-on-mac and Mac-on-Linux are pretty much dead. At some point I'll have an Intel Mac - which will make things like VirtualBox/Parallels and VMWare Fusion options. I was looking at things like Thinkpads on ebay and they aren't terribly expensive - certainly cheaper than buying a new netbook - although less portable (X-series maybe excepted). One of my mates has an old ThinkPad ... so that might allow me to run both in parallel at my desk. (He also has an old Tower - but I'm trying to give up non-portable computers for size, storage and portability reasons.) Another mate has just offered my my original Tangerine iBook back. That would be interesting but it's only a 300MHz G3. I wonder which model ThinkPad it is.

I also have been pretty slow at my two programming projects - the importer and the robot. Hopefully I'll get some actual serious work done over the next week. Need to finish the importer so I can get onto the next project that I'm desperate to start!

Subversion finder scripts

Came across these, referenced from macosxhints.com

http://svn-finder.sourceforge.net/

Looks interesting but haven't tried it yet.

MINOS 09 - Saturday Late Afternoon

Garry Bulmer - Kids doing electronics, Embedded Control, Robotics. Existing schools kits, hand outs, breadboards, class PCs. Arduino development board. Various projects around these - including line follower robot.

Ken Hewitt - Overview of the Parallax Propeller Chip

Alan Dibley - More diagonal paths.

MINOS 09 - Saturday Early Afternoon

Martin Barratt - IR-based wall sensing circuits, technical considerations and choice in detail

Martyn Pittuck - Adaptive Control - Mouse overview, and technical overview of details. Sensor FFT. Applying adaptive control to skidding, predictive to next turn. Generating trajectories using Bezier curves. Estimating friction. Controller operation and cornering offset and exit angles.

David Hannaford & Pete Harrison - Flood Algorithms & Route Planning - Discussion of the basic principles of flood algorithms and possible visited cell optimization. Methods of finding diagonal paths. Asynchronous flooding by Alan Dibley.

MINOS 09 - Saturday Morning

Good information this morning.

1. Dave O. in-wall start/end detectors. Also update on accelerometer and gyroscope work.

2. Duncan - "weightless communications" - Transmission of data using same IR LEDs used for wall sensing.

3. Derek - maze solver work. 256 bits. 1 bit/square maze solver... do whole lot again on every single square. bit flood.

Then 2 bits per square... four directions. Same thing.. go out with arrow points towards previous arrow.

Also discussed problems with finding optimal route for all mazes.

Some Wall Detector Problems

The wall detector I've been working on has some pretty serious, but probably fixable, problems.

1. There is not enough overlap between the walls and the detectors. There are three solutions, I think, here:

• a. Probably the detectors need to be wider (simple to do)
• b. The bearing looks like it is sometimes off - so perhaps I need to average using a second bearing line (a little work but possible).
• c. Also the detectors need position tweaking to avoid problems with the camera distortion, etc. This is not difficult but time consuming. This was expected, to be honest, because of the camera distortion and the slight camera rotation (around Z axis).

2. The walls appear to be offset by 180mm (one cell) in 'Z' (front/back direction) from the detectors. Have no clue what this is.

3. When the robot is at an angle other than straight ahead, we need a different set of detectors or extra detectors, on that side. This is a fair amount of work but possible and probably necessary. I can't use a single (large) set of detectors because of 1c above (and it would also be slower... not that I'm worrying about speed at this point). There might be a way of automatically adjusting detectors based on this camera distortion/rotation - but I haven't thought about this yet.

4. The line intersection with detection rectangle code probably needs enhancing to make diagonals more likely to get hit. It looks to me as though this will cause problems without this - although I'm going to do a hack to make sure it's quick, if less accurate.

I haven't actually debugged the wall detector code - this was from the graphical Mac app getting data about the wall detector positions from the robot and overlaying it with data from the rotated plan view.

The enhancements to the graphical app and the robot side collection of data were a fair amount of work this morning. Whilst I was doing this, ironically, the command line integer number input routine turned out to have a bug in it - it ignored the minus sign - trivial to fix but more time. I also had to add a method to transmit a bunch of data without using binary ... basically a simple base 64 type encoding to keep the characters in the printable ASCII range.

I also put in some code to use blue compare with red as opposed to green compare with red to overcome problems with bright sunlight coming from the side - I think this is what I was seeing a couple of weekends ago with the faint picture. I also need to check pixel positions of blue vs. red, because of the missing blue at the start of the line and put this in as a settable non-volatile option. It's a good job we hadn't gone to a RG only bus (hardware change that uses 16 bit mode with only 8 bits physically wired).

Was hoping to get the wall detectors as well as the robot position stuff (that Alan was working on) done today, but that looks unlikely.

The good news, I guess, is that the basic principle of wall detectors and rotated plan view looks like it will work. Which is good, since the alternative is a re-write!

Other random stuff

Still need to add the black card to shield the shaft encoders.

Measured bearings of greater than 45 degrees needs work on - these will usually mean we have a bearing based on a horizontal line not a vertical line, since horizontal lines will always be less than 45 degrees. This will cause us problems as soon as there aren't any local vertical lines.

We also need to be able to measure robot position (in Z) without horizontal walls - there are three options: dead reckoning, horizontal wall gaps (what IR mice use) and stop and rotate 90 to check (and then rotate back 90). No code for either of the last two yet - although it might be fine to ignore for the wall follower case.

Running by MINOS?

What does all this mean for MINOS next weekend? I'm not sure, there is still a lot to do - but I'm pretty sure I'm not going to get the maze solver in. Assuming I can get the wall detection routines working, finish the robot position detect then write a movement control routines (I have the movement code and just need to link in some control code that uses the vision) then a non-contact wall follower might be possible.

Image corners and camera angle

Sorted out the segment processor going around corners ("corner cutting of the line detector"). Took me most of the time figuring out how process_segments worked (which is my own code)! Added some (more) comments on each block just in case I need to change it again. Once this was done, I basically added a very simple positive or negative gradient rule check into the segment processor that maintains the previous direction when matching segments.

Also squished a bug where I couldn't alter the camera angle - and in fact this was part of the reason why I was seeing distorted plan view images - although it eventually needed adjusting from 20.5 degrees to 24 degrees look down to make the plan view image look right.

Also ended up adding a command to list the internal trig variables and world Z table used by the reverse perspective. This showed these variables weren't changing when the camera angle changed. The serial command line really has been essential in the development of the mouse.

Two things that are bugging me is the slight (physical) rotation of the camera (around Z ... where Z is the direction the robot faces) and not knowing how fast these routines are running. However, neither problem is critical to getting the mouse running so I've leaving them. (The rotation could be fixed in software or hardware ... obviously physically adjusting the mount would be the least processing power ... but perhaps let's not touch the hardware at this late stage!)

Things next are: position location from the image lines, maze wall detection and some black card to make sure the shaft encoders work in bright light.

The maze wall detection is interesting - Basically I'm thinking about using circular or rectangular 'detection' areas to find the walls indicated by the lines. I've been contemplating which is the fastest option. I'm not an expert in a fast integer approach, but my previous work in 3d (game) collision detection with spheres and viewport clipping seems to be applicable here.