Masters of Orion II

Running Masters of Orion II with Wine

Just want to point out this great game which is available free of charge this days.

You can download Master Of Orion II from gamesnostalgia.com.

And it runs unter GNU/Linux thanks to Wine:

7z x masteroforion2_dos_win.7z
cd MasterOfOrion2/mastori2
winetricks ddr=gdi
wine SETSOUND.EXE
wine ORION95.EXE

Enjoy!

Update:

Wine 1.8.7 under Debian Stretch displayed a blank screen when starting the game. Using winetricks ddr=gdi as shown above seems to resolve that issue.

TIE Fighter flight simulator

Installing TIE Fighter on DOSBox

The Internet Archive hosts among other vintage PC games a copy of Star Wars TIE Fighter. I got the game to run under GNU/Linux using DOSBox. I only got it to run using a Joystick. The mouse controls didn’t seem to work properly.

Download TIE Fighter from here and place the files SWTieCD/cd/SWTIECD.cue and SWTieCD/cd/SWTIECD.BIN in a directory of your choice. Also rename them to lower case (i.e. swtiecd.cue and swtiecd.bin).

Edit your DOSBox configuration file (in my case $HOME/.dosbox/dosbox-0.74.conf and set the Joystick type to two axis (it is set to ch by default).

[joystick]
joysticktype=2axis
timed=false
swap34=true
buttonwrap=false

Change to the directory where the CD image is and run DOSBox as follows:

dosbox .

In the DOSBox window mount the CD image as follows:

imgmount d c:\swtiecd.cue -t iso

Now you can install and run the game:

d:\install

Enjoy!

See also:

• Star Wars TIE Fighter Collectors CD ROM
• TIE Fighter Joystick problems
• Top 30 abandonware games by genre

MEncoder options

Encoding DVDs with MEncoder

Here is an example on how to encode a DVD using MEncoder.

mencoder dvd://1 -o test.avi -ss 120 -endpos 10 -alang en -slang en -aid 130 -psprobe 1000000 -vf crop=720:446:0:66 -aspect 1.78 -af volume=15 -ovc x264 -x264encopts crf=21:threads=2 -oac mp3lame -lameopts q=2

You can get hints for the audio id, supported languages, aspect ratio, and other values by playing the DVD with mplayer dvd://1 and inspecting the resulting console output.

• dvd://1: read the main track of the DVD. Sometimes the main video is on another track (e.g. dvd://3, dvd://5, dvd://81, …).
• -o test.avi: selects the output file and AVI as container format. You could also specify an MP4 file here.
• -ss 120 -endpos 10: this tells the encoder to skip the first 120 seconds and then stop after encoding 10 seconds of video. This is used initially to test on a small representative part of the video that the encoding options are correct. Afterwards you can drop these options.
• -alang en: choose the English audio track.
• -slang en: add the English subtitles to the video.
• -aid 130: choose the audio track with id 130. Specifying this is not necessary in most cases.
• -psprobe 1000000: use this option to force MEncoder to extend the search for the audio stream. Only necessary if MEncoder says no audio stream found.
• -vf crop=720:446:0:66: you can use this to crop of black borders.
• -aspect 1.78: often it is necessary to set the pixel aspect ratio of the output video.
• -af volume=15: with many DVDs it is necessary to boost the audio volume.
• -ovc x264 -x264encopts crf=21:threads=2: this selects the H.264 video encoder and configures it.
• -oac mp3lame -lameopts q=2: this selects the MP3 audio encoder and configures it. You can also use -oac faac -faacopts quality=300 if you prefer to use the AAC codec.

Once you have found the right options, rerun the command without the -ss and -endpos option to encode the full video.

See also:

• MPlayer

Arduino hello world

Using an Arduino board with a GNU/Linux personal computer has become pretty straightforward. The following command will install the required software:

sudo aptitude install arduino-mk

In order to get the file-system permissions to use the USB-serial it is necessary to add the current user to the dialout group. It is necessary to log out and back in after this.

usermod $USER -a -G dialout

For the Arduino Diecimila you then create a Makefile with the following content (see /usr/share/arduino/hardware/arduino/boards.txt for other supported boards).

ARDUINO_DIR = /usr/share/arduino
BOARD_TAG    = diecimila
ARDUINO_PORT = /dev/ttyUSB0
ARDUINO_LIBS =
include /usr/share/arduino/Arduino.mk

Make sure that /dev/ttyUSB0 is the right device! You can do this by inspecting the output of dmesg after plugging in the Arduino device.

Now you can create a sketch file (ino file extension) for programming the micro controller. E.g. a file Blink.ino with the following content:

int led = 13;

void setup() {
  pinMode(led, OUTPUT);
}

void loop() {
  digitalWrite(led, HIGH);
  delay(50);
  digitalWrite(led, LOW);
  delay(50);
}

Finally compile and upload the code:

make
make upload

The source is available on Github: github.com/wedesoft/arduino-hello-world

Update:

It is also possible to switch the LED according to instructions send over the USB serial channel. The following program facilitates this:

int led = 13;

void setup() {
  Serial.begin(9600);
  pinMode(led, OUTPUT);
}

void loop() {
  char c;
  if (Serial.available()) {
    c = Serial.read();
    if (c == '1') {
      digitalWrite(led, HIGH);
      Serial.write("LED on\r\n");
    } else if (c == '0') {
      digitalWrite(led, LOW);
      Serial.write("LED off\r\n");
    } else
      Serial.write("Switch LED on/off using keys '1' and '0'\r\n");
  };
}

After opening screen as a serial terminal, the LED can be controlled using keys ‘1’ and ‘0’:

screen /dev/ttyUSB0 9600

Exit with Ctrl-A \

See also:

• Uploading a Sketch from the command line
• Control LEDs with lower level IO
• Three Alternatives to Arduino’s Serial Monitor
• Arduino ProtoShield

Graph colouring

Currently I am looking into register allocation using graph colouring (also see Chaitin’s paper on the subject). The graph colouring problem also occurs when trying to colour countries in a political world map where adjacent countries must have different colours. I thought it would be interesting to try a minimal implementation in Scheme. Feel free to suggest improvements in the comment section below .

A (undirected) graph is usually represented by a list of nodes (vertices) and a list of edges. If there are no insular nodes, a list of edges is sufficient. In Scheme (here GNU Guile implementation) one can do this as follows.

'((b . a) (a . c) (d . c))

The graph can be visualised on the command line using Graphviz and ImageMagick as follows.

echo 'graph test { b -- a; a -- c; d -- c; }' | dot -Tpng | display -

The following helper function graphviz uses a system call to display a graph from within the REPL.

(define (dot graph colors)
  (apply string-append
         (append (list "graph g {")
                 (map (lambda (color) (format #f " ~a [style=filled, fillcolor=~a];" (car color) (cdr color))) colors)
                 (map (lambda (edge) (format #f " ~a -- ~a;" (car edge) (cdr edge))) graph)
                 (list " }"))))
(define (graphviz graph colors) (system (format #f "echo '~a' | dot -Tpng | display -" (dot graph colors))))
(graphviz '((b . a) (a . c) (d . c)) '())

One can get the nodes of the graph by extracting all elements and suppressing any duplicates. The definition of delete-duplicates is part of SRFI-1 (Scheme Request for Implementation 1).

(use-modules (srfi srfi-1))
(define (nodes graph) (delete-duplicates (append (map car graph) (map cdr graph))))
(nodes '((b . a) (a . c) (d . c)))
; (b a d c)

The adjacency list of a node is simply the list of nodes of the sub-graph obtained by filtering for edges connecting to this node.

(use-modules (ice-9 curried-definitions))
(define ((has-node? node) edge) (or (eq? (car edge) node) (eq? (cdr edge) node)))
(define (adjacent graph node) (nodes (filter (has-node? node) graph)))
(adjacent '((b . a) (a . c) (d . c)) 'c)
; (a d c)

Chaitin’s graph coloring algorithm works by successively removing nodes with a low adjacency count from the graph. Removing a node from our graph can be done as follows.

(define (remove-node graph node) (filter (compose not (has-node? node)) graph))
(remove-node '((b . a) (a . c) (d . c)) 'c)
; ((b . a))

Using the argument of the minimum one can determine the node with lowest adjacency count.

(define (argmin fun lst)
  (let* [(vals   (map fun lst))
         (minval (apply min vals))]
    (list-ref lst (- (length lst) (length (member minval vals))))))

Now one can recursively remove the node with lowest adjacency count and then assign colours starting with the last node and working backwards. If an adjacent node has a colour already, another colour must be used.

(use-modules (srfi srfi-26))
(define (assign-colors graph nodes colors)
  (if (null? nodes) '()
    (let* [(target    (argmin (compose length (cut adjacent graph <>)) nodes))
           (coloring  (assign-colors (remove-node graph target) (delete target nodes) colors))
           (blocked   (map (cut assq-ref coloring <>) (adjacent graph target)))
           (available (lset-difference eq? colors blocked))]
      (cons (cons target (car available)) coloring))))
(define (coloring graph colors) (assign-colors graph (nodes graph) colors))
(coloring '((b . a) (a . c) (d . c)) '(red green blue))
; ((b . red) (a . green) (d . green) (c . red))
(let [(graph '((b . a) (a . c) (d . c)))] (graphviz graph (coloring graph '(red green blue))))

And here is an example of coloring a graph with a few more nodes.

(let [(graph '((run . intr)
               (intr . runbl)
               (runbl . run)
               (run . kernel)
               (kernel . zombie)
               (kernel . sleep)
               (kernel . runmem)
               (sleep . swap)
               (swap . runswap)
               (runswap . new)
               (runswap . runmem)
               (new . runmem)
               (sleep . runmem)))]
  (graphviz graph (coloring graph '(red green blue yellow))))