Fast Path Finding (part II)

Last week we had a first look at a simple path finding algorithm with application to games. This week, let us have a look a the relative performance of the implementations considered: C# with a naïve implementation that scans the whole map multiple times; a C# implementation that uses lists to maintain and visit only the border of the solved region (affording massive speed-ups, one hopes); and C++ versions of these two variants, plus a C++ variant that uses set (as bitmaps) to maintain the border list.

In any quantitative study, the first thing to do is to collect data. The best way is to automate the collection, by, for example, adding a function that puts the player in all legal positions on the map, compute all the shortest paths, and measures how long it takes. One may also consider disabling the on-demand power policy as the CPU may jump (progressively?) in high gear as the data collection progresses, introducing bias.

Fast Path Finding (part I)

The other day in class I was telling my students that sometimes simple strategies simply do not cut it. As an easy-to-understand example, I discussed the behavior of baddies in video games. If your game asks for the baddies to chase the player, the first thing you might try is to move the baddies in the direction of the player, without any other sophistication.

So the algorithm in this case is that you move the baddie closer to the player (or try to, as there might be obstacles), and this translates to something like two lines of code:

Test Drive (more GPS data)

In a few previous entries, we looked at how to capture, parse, and evaluate the precision of a NMEA-capable GPS. The next step is to take it on a test drive.

The setup is simple: a laptop, a USB GPS, a car, and a map. The map is provided by Google Maps, of course. The car and the laptop do not really matter (as long as one of the two runs Linux and has a USB port); the USB GPS is the Columbus V800.

A First Look At GPS Data

In previous installments, we looked at how to read data from a serial-over-USB GPS, then how to parse the data. However, getting data isn’t everything, we must also ascertain it’s valid

The first thing that comes to mind to test the device’s precision (while I don’t really know how to check for the accuracy) by plug it in, leave it stationary, and collect the readings for a good while

Parsing GPS data with Bash

Last time we looked at how to get the data to the GPS and now we will have a look at how to parse the data. Turns out that except for the check-sum, everything is pretty straight forward, even in Bash.

So, why bash in the first place? Well, there’s not real reason except that for the something else I’m working on, it’s the ideal glue-code language, allowing me to invoke simply other programs that I do not want to re-code (or take parts of) to do what I want. I must say that I even have a C# version of the GPS data grabber, but while fancier, it does not bring much more than the Bash version.

Reading GPS data with Bash

I am presently working on something that requires geolocation. Not knowing much about GPSes and related topics, I decided to get a USB GPS. This week, let’s have a look at how we can extract information from the USB GPS using Bash.

The first step is to locate your USB GPS as a device. If it’s NMEA compliant, it should mount automagically as a USB serial port. You would think that lsusb -v would show you the device, but it does not always. Sometimes it shows as “Brand X GPS”, sometimes it only shows as a generic device, say “MediaTek Inc.”, or even as a modem. It will typically show up as /dev/ttyUSB0 or /dev/ttyACM0.

Shallow Constitude

In programming languages, there are constructs that are of little pragmatic importance (that is, they do not really affect how code behaves or what code is generated by the compiler) but are of great “social” importance as they instruct the programmer as to what contract the code complies to.

One of those constructs in C++ is the const (and other access modifiers) that explicitly states to the programmer that this function argument will be treated as read-only, and that it’s safe to pass your data to it, it won’t be modified. But is it all but security theater?

Compressed Series (Part I)

Numerical methods are generally rather hard to get right because of error propagation due to the limited precision of floats (or even doubles). This seems to be especially true with methods involving series, where a usually large number of ever diminishing terms must added to attain something that looks like convergence. Even fairly simple sequences such as

may be complex to evaluate. First, is cumbersome, and becomes small exceedingly rapidly.

Float16

The possible strategies for data compression fall into two main categories: lossless and lossy compression. Lossless compression means that you retrieve exactly what went in after compression, while lossy means that some information was destroyed to get better compression, meaning that you do not retrieve the original data, but only a reasonable reconstruction (for various definitions of “reasonable”).

Destroying information is usually performed using transforms and quantization. Transforms map the original data onto a space were the unimportant variations are easily identified, and on which quantization can be applied without affecting the original signal too much. For quantization, the first approach is to simply reduce precision, somehow “rounding” the values onto a smaller set of admissible values. For decimal numbers, this operation is rounding (or truncating) to the th digit (with smaller than the original precision). A much better approach is to minimize an explicit error function, choosing the smaller set of values in a way that minimizes the expected error (or maximum error, depending on how you formulate your problem).

An (Incomplete) Experiment with Sensors

When you have lm-sensors installed on Linux, you can invoke sensors to list all detected sensors and their states. While it is generally of mild interest except when you suspect that something’s wrong with your box—or, more precisely, when you want to make sure something doesn’t go wrong.

Amongst the sensors, there are temperature sensors that gives you information about the chipset and CPU. You can also find out about fan speeds. So I wondered if could use the sensors to see if there’s a significant difference between when the computer is idle and when I am using it. I thought I could, maybe, also see temperature differences between day and night.