Basic cgo

Go has provided within its distribution a couple of examples to describe how one uses cgo, the command line utility that one uses to interact with C libraries.  Beyond that there is practically no official documentation, perhaps due to the Go team's desire to encourage the development of native Go libraries.  However, not everyone is particularly keen on reinventing the wheel, making cgo rather important.

In this article I will try to describe how one would go about linking to a C library.  My example will basically be the cgo equivalent of an ncurses "Hello, world" program.  It provides several basics about cgo usage: interacting with C libraries, calling and passing parameters to C functions, and the Makefile.

First off, the very basics:

package gocurses 

/*
#include <ncurses.h>
import "C"
*/

"C" is not actually a real package.  It is merely a signal to cgo that the lines commented immediately prior to the import statement are to be compiled as C code and that their contents are to be accessible to the succeeding Go code.  Here we are including the ncurses header.  The functions, types, and variables exposed in that header are accessed as if they existed in the "C" package.  Thus, to create the ncurses window, we call:

C.initscr ();

Here's the entire program, which I will subsequently explain:

package gocurses

/*
#define NCURSES_ENABLE_STDBOOL_H 0

#include <ncurses.h>
#include <stdlib.h>

int Printw (const char* str) { return printw (str); }
*/
import "C"

import (
    "fmt";
    "unsafe"
)

func Hello (s string) {
    C.initscr ();

    p := C.CString (fmt.Sprintf ("Hello, %s", s));
    C.Printw (p);
    C.free (unsafe.Pointer (p));

    C.refresh ();
    C.getch ();
    C.endwin ()
}

Starting from the beginning, the macro is required due to ncurses handling of the bool type.  Do not worry too much about it for the purpose of this example.

Further down we see a wrapper around the ncurses 'printw' function.  This is necessary because cgo cannot deal with C's '...' parameter.  Fortunately we do not even need it, as it exists in this case merely for string formatting.

Note that I separate the import for "C" from the rest of the imports.  This is necessary, as putting it with the rest will (at the time of writing this article) prevent cgo from detecting where our C code is.

Further along we create our 'Hello' function and call 'initscr' to create a new ncurses window, as described earlier.  Now we deal with passing strings to C.  'C.CString' converts our Go string, 's', into a C-style string.  C strings are the only type whose conversion function is prefixed by 'C'.  All other types retain their own names.  Thus: for C ints, 'C.int'; for C floats, 'C.float'; etc.

We see here why we do not need to worry about the '...' parameter in 'printw'.  'fmt.Sprintf' can perform the formatting we need.  There are, perhaps, other uses of the '...' parameter that will require different workarounds, but for the purpose of this example we need not worry about them.

After calling Printw, we need to free the memory used by our new C string.  It is, after all, simply an array of chars created on the heap and we do not want a memory leak.  This is why we included 'stdlib.h': for the 'free' function.  'free' receives a pointer to void, a type that does not exist in Go.  'unsafe.Pointer' returns a compatible type, though.

The rest of the program is fairly basic.  Here's our main.go:

package main

import "gocurses"

func main () {
    gocurses.Hello ("world")
}

Now, we still need to compile everything.  We'll use a Makefile, as there a fair number of steps to compiling a cgo file.

include $(GOROOT)/src/Make.$(GOARCH)

PKGDIR=$(GOROOT)/pkg/$(GOOS)_$(GOARCH)

TARG=gocurses
CGOFILES=gocurses.go
CGO_LDFLAGS=-lncurses

include $(GOROOT)/src/Make.pkg

CLEANFILES+=main $(PKGDIR)/$(TARG).a

main: install main.go
        $(GC) main.go
        $(LD) -o $@ main.$O

The first line includes a file that simply defines some variables: CC, GC, LD, and O.  These define the compilers, the linker, and the file extension used for your platform.  On a 32-bit x86 platform, the values would be 8c, 8g, 8l, and .8, respectively.  On an amd64 platform, they would be 6c, 6g, 6l, and .6.

Next is simply a shortcut to Go's package directory.  It makes for less typing in Makefiles for larger projects.

The next five lines are cgo-specific:

TARG defines the name of the module we are compiling.  Since we defined it as gocurses in our source, that is the name here.

CGOFILES is a list of all .go files necessary for this module.  Since we everything is in a single file, we need only the one.

CGO_LDFLAGS defines any linker flags we need.  ncurses is not part of C's standard library, so we must tell cgo to explicitly link to it.

Next we include the file that Go provides to automate the cgo compilation process.  Take a look inside, if you wish, but I will not be going very deeply into what it does.  I will, however, explain a bit:

The cgo command line program creates four new files.  In our case they are gocurses.cgo1.go, gocurses.cgo2.go, gocurses.cgo3.c, and gocurses.cgo4.c.  The first is a translation of the original gocurses.go into normal go code.  The second defines all C types and variables that we used.  The third and fourth contain C code that wraps our calls.

When errors occur in the compilation of the Go code in a cgo file, it will often point to lines in *.cgo1.go.  Do not edit the contents of that file.  Use it as a reference to find where the error is in your .go file.

The actual steps the Makefile performs to compile these four files can be seen when one calls 'make main', though I will not go over them.

Back to the Makefile: CLEANFILES is just a list of files that Make.pkg uses to automatically remove all build files.  We add our executable to the list and also the package that it will install.

Finally we compile our main.go.  The 'install' directive there is what tells 'make' to actually start compiling our cgo files.

Please note that the final two lines must be indented using tab characters, not spaces.  When editing Makefiles you must ensure that your editor uses tabs and does not convert them to spaces.

I use vim and have set it to convert tabs to spaces, since I also code in Python.  However, when I need a tab I can create one using by pressing ctrl-v and hitting the tab key.

Well, that's it.  In the command line type 'make main' and the program should compile.  Run the executable 'main' and "Hello, world" should print.  Press any key and the program will exit.  Hopefully this little tutorial helps someone.

Reflection Package in Go

While Go does not have the level of introspection that allows a language like Python to define new types during runtime, it at least has the ability to examine and manipulate arbitrary types. One can, for example, pass a random object into a function that will identify the object's type and, in the case of a struct, its fields.

Indeed, if one looks into the 'fmt' package at the Printf family of functions, we see that Go's implementation of arbitrary parameters (the ... parameter) requires the use of 'reflect' to extract those parameters. Most interesting, however, is the 'xml' package, which contains a function call 'Unmarshal'. Unmarshal parses an xml file and attempts to implant the data into a given struct, matching xml elements with struct fields.

Unfortunately, reflection has a major issue: a lack of documentation. All we have to work with is the package specification and the aforementioned examples of the 'fmt' and 'xml' packages to learn from. Furthermore, these examples are rather complex. For this reason, I will make an attempt at producing a series of simple examples.

First off, let us have Go identify a parameter of arbitrary type.

Go allows one to take a parameter of any type and store it or pass it into a function via the empty interface: 'interface{}'. Since the empty interface defines no methods, all types implement it -- even basic types like integers or booleans. Thus we have the skeleton of our 'Identify' function:

func Identify (val interface{}) {

}

The first thing that 'reflect' must do for us is turn 'val' into something that the package can work with. The function that does this is NewValue, which takes as a parameter any value and returns a reflection value. Note that the type 'Value' is an interface. This will be more important later.

func Identify (val interface{}) {
    v := reflect.NewValue (val)
}

From here, the most basic way to identify the type is to simply ask for it via reflect.Value's 'Type' method. This returns a type object, which in turn implements a method call 'Name' that returns a string.

func Identify (val interface{}) {
    v := reflect.NewValue (val);

    fmt.Println (v.Type ().Name ())
}

Thus, when we call 'Identify (5)' the output is 'int'. Call 'Identify (Stuff{3})' and the output is 'Stuff'.

Not a very useful function except, perhaps, for debugging. Let's try something more complex, like diving into a struct instance to extract all field names and values and print them. Basically, it will be a generic Print function.

type Stuff struct {
    Num int;
    Str string;
    Boo bool
}

func PrintAny (val interface{}) {
}

We start the same way as with 'Identify', but creating a reflection value. However, to keep things generic and to avoid massive indentation, we'll use PrintAny simply as a feeder for the function that will do the actual work.

func printAny (val reflect.Value) {

}

func PrintAny (val interface{}) {
    v := reflect.NewValue (val);
    printAny (v)
}

To start we'll just have printAny deal with basic types. For the sake of simplicity, I'll just deal with the three basic types we'll need for our struct: int, string, and bool. First we'll use an if-statement to determine the type. Since the second value returned by a type assertion tells us whether the cast was successful, we can use that to determine whether we've found the correct type. The cast variable is of a type that implements a function called 'Get', which returns the value of the variable. The basic interface Value does not implement Get because it does not know what type to return.

func printAny (val reflect.Value) {
    if v, ok := val.(*reflect.IntValue); ok {
        fmt.Printf ("%d\n", v.Get ())
    } else if v, ok := val.(*reflect.StringValue); ok {
        fmt.Println (v.Get ())
    } else if v, ok := val.(*reflect.BoolValue); ok {
        fmt.Printf ("%t\n", v.Get ())
    } else fmt.Println ("Unknown Type")
}

This is the cumbersome way of doing this. I show it simply to demonstrate type assertions with reflect. Now let's simplify it using the ability of the switch-statement to deal with types. This way, we do not have to worry about 'ok'. The switch-statement automatically looks over the cases to decide which is valid, with 'default' handling the final 'else' case.

func printAny (val reflect.Value) {
    switch v := val.(type) {
        case *reflect.IntValue:
            fmt.Printf ("%d\n", v.Get ())
        case *reflect.StringValue:
            fmt.Println (v.Get ())
        case *reflect.BoolValue:
            fmt.Printf ("%t\n", v.Get ())
        default:
            fmt.Println ("Unknown Type")
    }
}

Thus:

func main () {
    var num int = 4;
    PrintAny (num)
}

. . . will output '4'. However, what if we call 'PrintAny (&num)'? It'll run into the default case. Let's get around that.

The reflect package handles pointers via the 'PtrValue' type. The value held by the memory pointed to is accessed by PtrValue's 'Elem' method, which returns a generic reflect 'Value'. To get the actual value, we must run it through the switch-statement again, but instead of nesting one, we'll simply recurse by calling printAny again with the result of 'Elem' as the parameter.

func printAny (val reflect.Value) {
    switch v := val.(type) {
        case *reflect.PtrValue:
            if v.IsNil () {
                fmt.Println ("nil")
            }
            printAny (v.Elem ())
        case *reflect.IntValue:
            fmt.Printf ("%d\n", v.Get ())
        case *reflect.StringValue:
            fmt.Println (v.Get ())
        case *reflect.BoolValue:
            fmt.Printf ("%t\n", v.Get ())
        default:
            fmt.Println ("Unknown Type")
    }
}

This is why I separated the bulk of the code from the original PrintAny function.

Note that I check to see if the pointer is nil. If I don't, when the function recurses it'll land in the default case.

Next is dealing with structs. All structs, regardless of the actual type, are defined by 'reflect.StructValue'. It implements all methods necessary to iterate through its fields and extract their data. The fields are accessed individually by calling the 'Field' method with an index as the parameter. 'Field' returns a basic 'Value', so we can recurse again.

func printAny (val reflect.Value) {
    switch v := val.(type) {
        case *reflect.PtrValue:
            if v.IsNil () {
                fmt.Println ("nil")
            }
            printAny (v.Elem ())
        case *reflect.StructValue:
            for i := 0; i < v.NumField (); i++ {
                printAny (v.Field (i))
            }
        case *reflect.IntValue:
            fmt.Printf ("%d\n", v.Get ())
        case *reflect.StringValue:
            fmt.Println (v.Get ())
        case *reflect.BoolValue:
            fmt.Printf ("%t\n", v.Get ())
        default:
            fmt.Println ("Unknown Type")
    }
}

Wait, though: in the introduction to this example I said that I wanted the field names, too. Fortunately 'reflect' allows us to find those via the 'StructType' type. 'StructType' and other '*Type' types in 'reflect' provide information on the type itself. In the case of structs, this includes information on the fields. This is accessed by casting the value returned by the 'Type' method.

The methods for accessing the fields of a 'StructType' do not return a 'Value', but a 'StructField', a struct that contains data about the field, including what we are looking for: the field's name. As such, we iterate through it much as we would the 'StructValue''s fields.

func printAny (val reflect.Value) {
    switch v := val.(type) {
        case *reflect.PtrValue:
            if v.IsNil () {
                fmt.Println ("nil")
            }
            printAny (v.Elem ())
        case *reflect.StructValue:
            typ := v.Type ().(*reflect.StructType);

            for i := 0; i < typ.NumField (); i++ {
                name := typ.Field (i).Name;
                field := v.FieldByName (name);

                fmt.Printf ("%s: ", name);
                printAny (field)
            }
        case *reflect.IntValue:
            fmt.Printf ("%d\n", v.Get ())
        case *reflect.StringValue:
            fmt.Println (v.Get ())
        case *reflect.BoolValue:
            fmt.Printf ("%t\n", v.Get ())
        default:
            fmt.Println ("Unknown Type")
    }

}

And that's it! Try it out with our 'Stuff' struct:

func main () {
    a := Stuff{4, "Hi!", true};
    PrintAny (&a)
}

The obvious application for a similar function would be serialization, though I would not use it for complex structures. It would indeed be best only for small structures tailor made to save only that which needs to be saved. Everything else can be derived when reading from the saved data.

Another application is the ... parameter, as I mentioned at the beginning of this article. The ... parameter is treated as a struct containing the values passed into it. For example:

fmt.Printf (format, 1, 2.3, true, "me");

The types that Printf deals with internally are actually a string and a struct with an int field, a float field, a bool field, and a string field. Of course, it also handles more types that my little example does, but it is not difficult to implement them.

Generator functions in Go

When I learned how channels work in Google's Go language, one of the first thoughts that came to my mind was not inter-thread communication, but generator functions ala Python's yield statement.  That is because of the Wikipedia article on the subject, which mentions that Java can implement generators via threading.  Common threading, however, is not always a quick and easy process, so I more-of-less decided that the feature could only really work well in languages that explicitly have the feature.  That is not the case with Go.

Goroutines are a light-weight implementation of threading, without much of the complexity associated with threading.  All you need to launch a goroutine is any function and the 'go' keyword.  Channels can help for passing data out of goroutines and when channels are created without defining a buffer size, they block execution until the channel is read from.  That feature of channels is very similar to what Python's 'yield' statement does.

func Count (start, length int) chan int {
    yield := make (chan int);

    go func () {
        for num := start; num < start + length; num++ {
            yield <- num
        }

        close (yield)
    } ();

    return yield
}

As you can see, it's slightly different from Python, but very workable and without much difficulty.  The actual code for the generator is held within an anonymous function, but outside of that all we do is create the channel and return it.

Note that the channel is closed at the end of the generator.  This is important, as trying to read beyond the end of the goroutine causes the program to panic and die.  If, on the other hand, the channel is closed and one reads beyond the end of the goroutine, the result is simply zeros.

Another great feature of channels is that they are one of the types that may be used by the 'range' clause in 'for' loops.  Thus, in such a loop one does not have to check to see if the channel is closed; Go does that for you.

One day holiday, but no Dragon Age

I made the error of letting Impulse patch Dragon Age and the game doesn't work any more. I'm certainly not going to re-download the thing, I'm hoping that System Restore might solve things. . . If not, then it's the weekend before I play it again.

Instead I spent the day playing around with Google's new 'Go' programming language. I really like it!  It's got many great modern features and certain elements of the syntax remind me of Pascal. Most important, to me, are the features that allow one to make the most of multi-core systems. Python, which I've been playing with most in recent times, is actually best on single-core systems, unfortunately. I just might find myself migrating toward Go. . .

The make-or-break point of it, though, will be its ability to interface with existing C libraries. Right now that's a bit iffy. I'm trying to write an interface to a library I've been using lately and it inexplicably refuses to work with some functions. Fortunately, the compiler is open-sourced and not particularly huge, so perhaps I can figure out what's happening. . . That might have to wait for the weekend, too.

Fast Rendering With libtcod in Python

Python, being an interpreted language, is not all that speedy.  Obviously a great deal of effort has gone into optimisation of the interpreter, but by far the best way of producing fast code is via the liberal use of functionality implemented in C.  By this I do not mean that one should go out of their way to write one's own C extensions for every taxing operation.  It is usually sufficient to make use of existing libraries, both standard and extension.

The Chronicles of Doryen Library, or libtcod, is an ASCII rendering engine, primarily intended for rogue-like games.  It features full 24-bit colour and a very nice set of utility modules -- basically everything one might need to produce a rogue-like.  As I said, though, it is a rendering engine and not a game engine.  One still has to implement one's own data structures and game loop.

The most obvious way of printing characters on screen in libtcod is via the put_char function.  It places a character at the specified location in a buffer.  The character's colour may be set either by previously altering the default foreground and background colours (via set_background_color and set_foreground_color) or by afterward setting the colours for that particular location on screen (via set_back and set_fore).  The problem here is obvious, as what you have is a minimum of three function calls for each and every character on screen.  If one is rendering to a traditional 80 by 25 viewport, that is two-thousand characters or six-thousand function calls every frame.  That is not including whatever happens throughout the rest of the program loop.

Clearly another method is required.  Fortunately, libtcod provides functions capable of printing multiple characters (ie: a string) with a single call: print_left, print_center, and print_right.  Furthermore, it provides functionality though which one may specify colours within the string.  This is how I implemented my solution.

First off, let us start with a data structure:

class Cell (object):
    __slots__ = '_fg', '_bg', 'char'

    def __init__ (self, fg,  bg, char):
        self.fg = fg
        self.bg = bg
        self.char = char

To be honest, using a class is somewhat slower than simply storing this data in a tuple, but this makes the code more readable.  I used __slots__ because it does at least provide a small boost in speed.

The easiest way to store the scene is in a list.  More specifically in a list of lists.  The outer list is a collection of rows, with each inner list being the rows themselves.  Let us generate a random scene:

chars = ['\'', '`', ',', '.', '.', '.']
raw_scene = [[Cell ((1, 255, 1), (1, 1, 1), random.choice (chars)) for x in range (width)] for y in range (height)]

There: a Dwarf Fortress-like grassy field!

If none of that code makes sense to you, I suggest that you study Generator Expressions.  They are immensely useful.

Anyway, this is the raw data from which we will construct the scene.  We keep it in memory for cases where we must update the scene, as the compiled data may not be as intuitive to alter (though it is certainly possible).

The scene is compiled by converting every cell into a string consisting of libtcod colour codes and the cell's character:

def compile_scene (raw_scene):
    scene = []

    for y in range (height):
        scene.append ([])

        for x in range (width):
            cell = raw_scene[y][x]
            scene[y].append ('%c%c%c%c%c%c%c%c%c%c' % ((tcod.COLCTRL_FORE_RGB, ) + cell.fg + (tcod.COLCTRL_BACK_RGB, ) + cell.bg + (cell.char, tcod.COLCTRL_STOP)))

    return scene

Leaving the individual little strings separate from each other allows one to later swap it with a different one.  Besides, Python provides the functionality to quickly combine them when we draw the scene.

Drawing the scene is simply a matter of using the join function of Python strings to combine the strings in every row.  We could technically also add a newline character to the end of every row and then combine the rows, allowing one to draw the entire scene in a single function call, but for some reason that produced a strange bug for me whereby sometimes the scene would not fully render.  I even ported the program to C and encountered the same issue.  Printing each line one-by-one seems to work, though, and it is not much slower.

def draw (con, scene):
    scene_str = [''.join (scene[y]) for y in range (height)]

    for y in range (height):
        tcod.console_print_left (con, 0, y, tcod.BKGND_SET, scene_str[y])

We can even go further and draw only a portion of the scene:

def draw (con, scene, left, top):
    scene_str = [''.join (scene[y][left:left + scr_width]) for y in range (top, top + scr_height)]

    for y in range (scr_height):
        tcod.console_print_left (con, 0, y, tcod.BKGND_SET, scene_str[y])

This is useful in cases where the scene encompasses an area larger than the viewport.

The full version of my test program also incorporates an update function and several light sources altering the visibility of each cell.  It is in that version that the bug I mentioned appeared.

Anyway, I hope this helps anyone who has had problems with rendering speed in Python.  It has been a long time since I wrote an article on my blog, so at the very least it was worthwhile for me. . .

The Mote in God's Eye

I do not think that one who basks in political correctness should bother with The Mote in God's Eye, by Larry Niven and Jerry Pournelle.  If one looks both closely and shallowly at this book, one might decide that one has found trove of male chauvinism and racism.  I tend to do so, though only for my own personal entertainment.

The imperial navy, for example, seems to be comprised entirely of men.  This is not unusual, historically or currently, but the great assumption is often that the future will hold greater equality in all things.  Another example here is that the purpose of aristocratic women is apparently to perform as social butterflies, get married, and pop out heirs.  Once again, equality is generally expected in future settings, but then again: who is to say how the future and future human attitudes will develop?  The assumption of equality is based on current conditions facing no drastic changes -- which is entirely naive.  (There is another example, but it's a spoiler, so I won't reveal it.)

As for racism, the Moties (the alien race described) are a species with several genetic castes somewhat akin to polymorphism in insects.  There is a master caste, a mediator caste, a medical caste, a warrior caste, an engineer caste, etc.  Key in the argument of racism is that the master caste is white and the engineer caste (intrinsicly gifted in making things, but incapable of higher thought processes) is brown.  Here I can say that dark and light are used as the easily recognisable archetyes that they are, in western culture.  If that's not clear enough, think of the terms "white-collar" and "blue-collar".

Enough of the self-indulgent under-thinking, though.  Mote is basically a story of first contact -- the first first-contact -- with an intelligent alien civilisation.  Most books that I've read that deal with such a scenario assume a human civilisation that has yet to explore and colonise beyond the solar system -- assuming they got far off Earth at all.  Basically: contemporary settings.  In Mote, humanity has gone through the cycles of multi-stellar civilisation twice (the CoDominion and the First Empire), each followed by a collapse and period of barbarism, and has once again risen to a vast Empire.  For me, this is a unique experience.

The book is presented largely as a political drama, with several mysteries involving characters motivations.  There is little physical action, though what there is gripped my eyes and I had little desire to pull away.  All-in-all it had a somewhat Asimovian feel.  If you've read Isaac Asimov's Foundation series, you'll know what I mean.  Dramatic irony and discovery are where most of the action is, and I think Pournelle and Niven did a great job.

To be honest, though, I do have a couple gripes.  First is due to my own misconceptions: I expected more military science fiction; an interstellar war.  I didn't get that, but I probably should have read the synopsis more closely.  I don't like to do that, though, as it may spoil too much.  The second is related to the romance in the novel.  The pairing is far too obvious and it develops far to quickly and suddenly.  I have this problem with a great many books by a great many authors, though, so it shouldn't be surprising, anymore.

As I said, though, it's overall a great book.  Probably because it doesn't involve war and high military drama, it may be one of the best first-contact stories out there.  Definitely a recommended read to all interested in such things.

Acceleration/Decelleration

Say we want to move an object to a particular point in the shortest amount of time, given a maximum acceleration. It follows that the object must accelerate constantly until it comes to a point where it must decellerate constantly in order to come to a stop at the destination. Looking at this problem we have a known starting velocity, a known final velocity, a known total distance, and a known acceleration. There is a kinematics equation that uses all of those values:

v**2 = v0**2 + 2 * a * d

Unfortunately, that's only one acceleration, but our problem actually consists of two parts: an acceleration and a decelleration. At the end of the object's acceleration it reaches a maximum velocity, the final velocity for that part. The maximum velocity then becomes the starting velocity for the second part. Therefore we have two equations:

v_max**2 = v0**2 + 2 * a * d1
vf**2 = v_max**2 + 2 * -a * d2

This leads to two more unknowns: d1 and d2, the distances travelled during the first and second parts, respectively. However, the total of d1 and d2 is known as the distance from the start to the destination. Therefore, if we solve for d1 and d2 and add the results, it should equal the total distance.

d1 = (v_max**2 - v0**2) / (2 * a)
d2 = (vf**2 - v_max**2) / (2 * -a)
d = d1 + d2

The maximum velocity is still unknown, though, so let's sub in the formulas for d1 and d2:

d = (v_max**2 - v0**2) / (2 * a) + (vf**2 - v_max**2) / (2 * -a)

... simply it:
   
d = (2 * v_max**2 - v0**2 - vf**2) / (2 * a)

... and solve for the maximum velocity:

v_max = sqrt ((2.0 * a * d + v0**2 + vf**2) / 2.0)

Now, we simply have the object accelerate to that velocity and then decellerate back down to the final velocity. In the end, the object should be at the destination. Of course, now that the maximum velocity is a known value, one can now calculate d1 and use that value to determine how long the object should accelerate.

King David's Spaceship

I just finished reading King David's Spaceship, by Jerry Pournelle.  It's part of his Future History series, though very far removed from the Codominion era books.  Those books ended with a prequel to a galactic empire, though the empire itself is never touched upon except as a history to later books.  This one takes place after that empire's fall and the during the rise of a new one.

Anyway, for a title that indicates a plot about building a spaceship, the story itself has little to do with that.  It is the ultimate goal, but the bulk of the plot takes place in a medieval environment.  That's not to say that I am disappointed, though.  Pournelle writes plenty of military science fiction and he's good at it, even when the 'military' part is with early medieval technology.  No, instead of disappointed I was merely surprised at where the focus ended up.

Cyborg

Just finished watching Cyborg, a Jean-Claude Van Damme film from 1989. When I was young I remember Super Channel (a pay movie channel, back then) occasionally had promotions whereby they provided free viewing for a week. Those were the only times I ever saw anything from that channel. Once in a while, my sister would set her alarm clock to an early morning hour and wake me up so we could watch a late movie that looked interesting. That's how I first saw this film.

I really enjoyed it back then, having never before seen anything like the post-apocalyptic vision presented. It had good action, with a particularily menacing villain, and an element of drama that made it yet more memorable. Watching it again, I recognise the old, cheap effects (by modern standards), and the generally bad acting (not just from Van Damme). I can still enjoy it, though, and perhaps not all of that is simply due to nostalgia.

On another note, the movie reminds me alot of Fallout. :) The world presented is more lush outside of urban areas, but the ruined cities and the scavenged look of the costuming is definitely Fallout-like.

Collision Detection for Fast Objects and Circle-Line Intersection

In my current project I produced my own little set of classes for simulating physics.  It's very unrealistic, at this point, because realistic physics makes it very difficult to implement a thrust control AI.  More on that another time.  For now, I'm talking collision detection.

The objects I'm dealing with are very small relative to the velocities at which they may travel.  These are spacecraft and projectiles moving at realistic speeds -- not like one would see in a game like Star Control or indeed most other space sims, where craft seem to move slower than modern aircraft do.  In my program, projectiles like missiles are often moving so fast that simply collision detection allows them to pass right through their targets.  That's a problem.

The easiest solution to this is to simply use a smaller timestep.  I've locked the framerate at only 25 Hz, but I step through the physics update functions four times per frame.  As far as the physics is concerned, the actual framerate is 100 Hz.  Even with such a framerate, collisions often fail to register.  The solution I decided upon was to implement a second step to collision detection whereby the system would also look at the area between the object's current position and its previous position.

The basic collision detection simply uses circles.  I detect collisions between the circular collision hulls of the current and previous position by defining a rectangle between them whose side lie tangent to both circles.  The slope of those tangent lines is no chore to discover as the radius of each circle is the same.  The slope is simply the slope of the vector that connects their centres:

# get the positions
x0, y0 = pos
x0p, y0p = prev_pos

# get the distance between the two
dx, dy = x0 - x0p, y0 - y0p
dist = math.hypot (dx, dy)

# normalize the vector
ndx, ndy = dx / dist, dy / dist

slope = ndy / ndx

We will use the normalized vector to determine where the corners of the rectangle lie.  This is found simply by rotating the vector 90 degrees left and right.  Multiply the results by the radius of the circles to produce vectors and add them to the current and previous positions to get the corners.

# get the end-piece slopes
ex0, ey0 = -ndy, ndx
ex1, ey1 = ndy, -ndx

# get the corners of the rectangle
px0, py0 = x0p + ex0 * radius, y0p + ey0 * radius
px1, py1 = x0 + ex0 * radius, y0 + ey0 * radius
px2, py2 = x0 + ex1 * radius, y0 + ey1 * radius
px3, py3 = x0p + ex1 * radius, y0p + ey1 * radius

Assuming that the previous position (x0p, y0p) is to the left of the current position (x0, y0), the top-left point is (px0, py0).  The rest of the points continue clockwise around the rectangle.

What we now need to do is test for a collision between the rectangle and the circular collision hull of the other object.  Cirlce-Rectangle collision occurs when either the circle touches a rectangle edge or when the centre of the circle falls with the bounds of the rectangle.  The latter is easier to test for, of course.

Determining whether a point is within a rectangle is simply a matter of finding which side of each edge the point lies.  Simply:

def get_side (p0, p1, point):
  x, y = point
  x0, y0 = p0
  x1, y1 = p1
   
  ex0 = x1 - x0
  ey0 = y1 - y0
   
  ex1 = x - x1
  ey1 = y - y1
   
  return ex0 * ey1 - ey0 * ex1

The order in which points are entered into this function is important.  Entered clockwise: if the return value is positive, the point lies above the line; if the value is zero, the point lies on the line; if the value is negative, the point lies below the line.  Therefore the point lies within the rectangle if the return value is negative for all sides.

If the centre of the circle is not within the rectangle, it is still possible that it touches one of the edges.  The only two edges we have to test are the top and bottom edges.  The end-pieces lie within the circles of the current and previous position circles, so we need not test them.

I must admit that I had great difficult trying to find an algorithm for Circle-Line Intersection.  I found a few sources where simply code was given, but I prefer an explanation to accompany code.  Eventually it dawned upon me to simply use the equations for lines and circles:

# line
y = m * x + b

# circle
r**2 = (x + x0)**2 + (y + y0)**2

The circle equation is easiest to deal with if simplified to assume that its origin is (0, 0).  Therefore:

r**2 = x**2 + y**2

If we do that, however, we must account for that in the for the line equation.  The easiest way to do that is to simply subtract the origin coordinates from the coordinates of the current and previous positions.

For the line equation, we found the slope, m, previously, and can find b by substituting either the current or previous position coordinates (modified as in the previous paragraph) into x and y.  Solving for b:

b = y0 - m * x0

Now, let us take the original line equation and substitute it for y in the circle equation:

r**2 = x**2 + (m * x + b)**2

Before we try to solve for x, let's evaluate the equation as far as it can go:

r**2 = x**2 + m**2 * x**2 + m * x * b + m * b + b**2

It looks intimidating, but we can turn it into a quadratic equation:

0 = (1 + m**2) * x**2 + m * x * b + m * b + b**2 - r**2

We can then solve for x via the quadratic formula, but to be honest we don't actually need it.  As it turns out, all we need is the result of the discriminant:

D = b**2 - 4 * a * c

The discriminant, after all, exists within the quadratic formula's square-root, which will not result in a real number if the discriminant is negative.  Ultimately, what this means is that the circle does not intersect the line if the discriminant is negative.  If it is not negative, the circle intersects the line at one or two points.

The expressions a, b, and c are extracted from our quadratic equation as follows:

a = 1 + m**2

b = m * b

c = m * b + b**2 - r**2

The resulting discriminant is:

D = m**2 * b**2 - 4 * (1 + m**2) * (m * b + b**2 - r**2)

There are no unknown values in this equation.  We have m, the slope, r, the radius, and b.  Here's the final function for Circle-Line Intersection:

def circle_line_intersection (p0, p1, origin, radius):
    x, y = origin
   
    px0, py0 = p0[0] - x, p0[1] - y
    px1, py1 = p1[0] - x, p1[1] - y
   
    dx, dy = px1 - px0, py1 - py0
   
    if dx == 0.0:
        return radius > abs (px0)
   
    m = dy / dx
    b = py0 - m * px0
   
    return m**2 * b**2 - 4 * (1 + m**2) * (m * b + b**2 - radius**2) >= 0.0

I test if dx is equal to zero because if it is, we'll end up with a division-by-zero error.  However, all that means is that the line is vertical.  As such, we can simply test one of the positions' x-coordinates against the radius of the circle.

This form of collision detection will not tell you exactly where the collision occured, of course.  However, that was not relevant to my needs, so I gratefully never considered it.  All I needed to know was whether my projectile had hit something or not, and this works quite well.

There are some problems with this solution, of course.  For example, if the projectile is moving along a curved path, this does not provide a perfect solution, as a rectangle has entirely flat sides.  Right now, however, I don't particularily feel like looking into collisions with arbitrary curves. . .

Circular number systems

When one deals with angles one must eventually find a way to work around the barrier between 359 degrees and 0 degrees.  For example, if one has an angle at 5 degrees and another at 355 degrees, what is the distance between them?  If one subtracts normally the result will be either 350 or -350, depending on the order one places them in the expression.  This is mathematically correct, producing the difference, but rarely is that what one wants.

The general case is finding out how to rotate an object to a particular destination.  Ideally one should rotate the object such that the shortest amount of time is taken, which means taking the shortest distance.  Rotating 350 degrees is obviously, to human perception, not the shortest distance.  The shortest distance is -10 degrees, of course, but the problem is how to write a program to give that result.

It is easy, if one uses a couple 'if-else' statements.  We start at 5 degrees and need to get to 355, so try the basic equation:

distance = destination - origin

distance = 355 - 5

350

This is, as mentioned earlier not the answer we want, so subtract maximum span of angle values, 360, and we have our answer: -10.  This works as long as the distance crosses over zero and the basic equation results in a positive number.  If it results in a negative number, then we add 360 instead.  If we are not crossing over zero, we add or subtract nothing.  One can always tell if the distance crosses over zero if the result of the basic equation is outside of the range (-180, 180).

Let's turn this into Python code:

def diff (start, end):
    dist = end - start
   
    if dist < -180:
        dist += 360
    if dist > 180:
        dist -= 360
   
  return dist

Simple enough and it works to a degree even when the values are not clamped to (0, 360].  However, I said 'to a degree'.  If the starting angle is 721 and the end is -1, the distance, according to this function is -362.  721 degrees is actually just 1 degree, so the distance should be -2.  To solve for this we should convert all values such that they appear between the standard range of (0, 360].  Therefore the new function is:

def diff (start, end):
    start = start - int (start / 360) * 360
    end = end - int (end / 360) * 360
   
    dist = end - start
   
    if dist < -180:
        dist += 360
    if dist > 180:
        dist -= 360
   
    return dist

This works, perfectly, but it's a rather long function.  For a time I was satisfied with it, but thought that a shorter way was possible.  I presented my problem and solution on the PyGame newsgroup and was greeted with some much better solutions.  Here's one:

def diff (start, end):
    return (end - start + 180) % 360 - 180

I started with a function with an 8-line body of code (not counting whitespace) and got back a function with a single line of code.  There's no conditional statements, either.  It is simply perfect.

This function is easily modified to work with whatever range of values one chooses.  If one works with radians instead of degrees:

def diff (start, end):
    return (end - start + 0.5 * pi) % pi - 0.5 * pi

Or how about a twelve-hour clock?

def diff (start, end):
    return (end - start + 6) % 12 - 6

Perfect!

A belated introduction. . .

I registered this blog some weeks ago, but between my ISP and some strange Windows 7 network bugs, I suffered enough annoying internet outages at the time that I never got around to producing my first post.  Well, here it is -- not the post I had originally written, but a post nevertheless.

This is Cheesesun Works!  What is Cheesesun?  Cheesesun is what I am told my handle, Ostsol, means if translated to English from Swedish.  That wasn't what I had in mind when I originally chose my handle, but I like it.

Cheesesun Works will primarily be my development blog.  Programming is like doodling, to me.  I may not produce much in terms of finished products, but I do like to experiment and learn.  Hopefully I will eventually finish something, but until then, here I will post my development thoughts and discoveries.

While secondary, I'll also likely use this as a log of my readings.  I use public transit every working day (no car; I got my learner's permit only recently) and work on the opposite side of the city from where I live.  The result is a 45 minute span each way in which I have nothing to do.  So I read.