Basic cgo -- Redux!

I happened to notice that my Basic cgo article somehow ended up on go's Google Code page, and I thought that I should make sure my code still works. Some of the information is out of date, such as the files that cgo generates. As for the code: it both does and it doesn't. First off, the Makefile is out of date, so here's a new one:

include $(GOROOT)/src/Make.inc

TARG=gocurses

CGOFILES=gocurses.go

CGO_LDFLAGS=-lncurses

include $(GOROOT)/src/Make.pkg

CLEANFILES+=main

main: install main.go

$(GC) main.go

$(LD) -o $@ main.$O

Next, linking to ncurses via cgo currently does not work as a result of Issue 667. 6g spits out an "invalid recursive type" error and compilation fails. There is a way to work around this, however.

The file where the error occurs is _cgo_gotypes.go. In it is defined the go equivalents for the C types exposed in ncurses.h. The problem occurs where WINDOW is defined. If it is defined below the _win_st struct, 6g spits the error. If it is defined above _win_st, everything goes well. Fortunately, cgo will not recreate any files it generates as long as the original source file is unaltered. This allows us to modify any of those generated files and call make main again in order to continue building the project.

With that in mind, the fix is simple:

1. Run make main and see the error
2. Open _cgo_gotypes.go and move the line defining _Ctypedef_WINDOW to above _Ctype_struct__win_st
3. Run make main again

The program should work from there.

Callbacks with cgo

A major limitation of cgo is the lack of support for callbacks or, in more general terms, the ability for C to call a Go function.  This is a major issue for bindings to event driven systems.  As part of impending support for SWIG, however, the Go team has expanded cgo to provide a facility by which Go functions may be exposed to C.

In one's cgo files, exposing a function is a very simple matter: one precedes the function header with a comment starting with the word export and followed by the function name.  For example:

//export Foo

func Foo() {

    // ...

}

When cgo sees this it generates two new C files: _cgo_export.c and _cgo_export.h.  These files provide the wrappers that enable a C program to call Go functions.

Provided with the current distribution of Go is an example program demonstrating this new feature.  It is found in:

$GOBIN/misc/cgo/life

Looking through that example, though, one should notice one problem: it is not an example classic callbacks.  That is, Go is not passing functions to C.  Instead, the functions are merely being exposed so that C can call them.  Thus the problem remains for event driven libraries such as GLUT.  Callbacks are achieved via a bit of indirection.

Let us start by creating a very simple library that adds number via a callback.  It has a single function, call_add, which takes a function pointer and calls it to add two integers.

// calladd.h

typedef int(*adder)(int, int);

extern void call_add(adder);

//callback.c

#include <stdio.h>

#include "calladd.h"

void

call_add(adder func) {

    printf("Calling adder\n");

    int i = func(3, 4);

    printf("Adder returned %d\n", i);

}

Nothing to it.  Compile it and turn it into a shared object:

gcc -g -c -fPIC calladd.c

gcc -shared -o calladd.so calladd.o

Now here's the interesting part: in order to pass a Go function to C we must create a wrapper that passes the wrapper to the Go function.  Wonderful, eh?  Two levels of indirection. . .

// funcwrap.h

extern void pass_GoAdd(void);

// funcwrap.c

#include "_cgo_export.h"

#include "calladd.h"

void

pass_GoAdd(void) {

    call_add(&GoAdd);

}

Our cgo file is rather simple:

//callback.go

package callback

// #include "callgo.h"

// #include "funcwrap.h"

import "C"

func Run() {

    // call the wrapper

    C.pass_GoAdd()

}

//export GoAdd

func GoAdd(a, b int) int {

    return a + b

}

This is still not really a callback, as we are not passing an arbitrary function.  That would require yet another level of indirection (for a total of three), whereby we store a function pointer and call it within GoAdd.  Hopefully in the future one level will be removed.  I suspect that this could be possible if cgo interpreted any passing of an exported function to a C function as passing the wrapper, but I cannot say that I have looked deeply into the matter.

To conclude, here's the Makefile for this project (a modified version of the life example's):

CGO_LDFLAGS=_cgo_export.o calladd.so funcwrap.so $(LDPATH_linux)

CGO_DEPS=_cgo_export.o calladd.so funcwrap.so

CLEANFILES+=main

include $(GOROOT)/src/Make.pkg

funcwrap.o: funcwrap.c _cgo_export.h

    gcc $(_CGO_CFLAGS_$(GOARCH)) -g -c -fPIC $(CFLAGS) funcwrap.c

funcwrap.so: funcwrap.o

    gcc $(_CGO_CFLAGS_$(GOARCH)) -o $@ funcwrap.o $(_CGO_LDFLAGS_$(GOOS))

main: calladd.so install main.go

    $(GC) main.go

    $(LD) -o $@ main.$O

Grid Squares in a Circle

I know that it's a minor operation, but for a long time I couldn't help but wonder if there were an optimized way of finding out which squares in a grid fall within a given radius. However, because it is such a minor operation and because the brute force method works adequately, I never actually went out of my way to try and solve this problem -- until now. Boredom is a wonderful thing. . .

First off, the brute force approach:

Given an origin (x0, y0) and a radius r, the maximum orthogonal extents of a circle is equal to (x0±r, y0±r). Given those extents, coordinates whose distance from the origin are less than or equal to the radius are within the circle.

def brute_coords(r):

    coords = []

    for y in range(-r, r+1):

        for x in range(-r, r+1):

            if math.hypot(x, y) <= r:

                coords.append((x, y))

    return coords

Very easy and with relatively small circles it is sufficiently fast. However, there should be a way to do this without even considering squares outside of the circle. There is and the solution comes thanks to the Pythagorean Theorem. Specifically, the circle's radius is the hypotenuse of a triangle and the distance along the x-axis is another length. The number of squares above and below that axis is equal to the final length. Thus we iterate along the minimum and maximum x-coordinates and calculate the verticals.

def smart_coords(r):

    coords = []

    for x in range(-r, r+1):

        dy = int(math.sqrt(r*r - x*x))

        for y in range(-dy, dy+1):

         coords.append((x, y))

    return coords

With small radii, such as a character's vision radius in a roguelike, the performance difference is a few milliseconds at most, on my system. With a radius of 100, smart_coords is twice as fast. At 1000, it takes 12 seconds, while brute_coords takes 17. That's pretty good!

As for whether the optimization is worthwhile in practical applications, I have no idea. I haven't made any real comparison and probably won't bother to. I will use it, though, if for no other reason than because it is better and it is not a very complex solution.

Go, syscall, and inotify

At the time of writing this article, Go does not implement all of the syscalls for which it has constants.  One of these is inotify, which allows one to monitor file system events.  It, and similar libraries are what allow file managers such as KDE's Dolphin or Gnome's Nautilus to almost immediately show a file's new date-stamp when it has been modified.

For information on inotify, check out the following article at LinuxJournal.com:

http://www.linuxjournal.com/article/8478

Fortunately, Go's syscall package exports the low-level function that it uses for all implemented syscalls.  This function is named, appropriately, Syscall.  There is also Syscall6, which receives six arguments (in addition to the syscall id) instead of three.  For our purposes, Syscall will be sufficient.

First, the basics:

Syscall receives and returns all values as the type uintptr.  This seems strange and at a glance would seem to indicate that it deals with pointers to all values, but that is actually not necessarily the case.  Integers, for example, are simply converted directly via a cast.

param := uintptr (num)

Strings, however, are a slightly more complex affair, but the syscall package provides a necessary function, StringBytePtr, which simply converts the string to a byte slice and returns a pointer to the first element.

param := uintptr (unsafe.Pointer (StringBytePtr (str)))

Although Syscall must receive three values (in addition to the syscall id), if the particular syscall requires less, one simply passes 0 to the remainder.  Similarily, it always returns three values, though not all are meaningful.  All are of the type uintptr: the first two being the actual return values, while the last is an error code.  Values that are not needed may be received as an empty variable: _.

The os package contains the functionality needed to print syscall error codes.  os.NewSyscallError receives a string and an integer.  The first should be the name of the syscall you attempted, while the last is the error code that Syscall returned (casted to int, of course).  The structure returned implements os.Error.

In C inotify consists of three functions: inotify_init, inotify_add_watch, and inotify_rm_watch.  The corresponding syscall ids are SYS_INOTIFY_INIT, SYS_INOTIFY_ADD_WATCH, and SYS_INOTIFY_RM_WATCH.  Given the above information, it is simple to call each.  For example:

fd , _, errptr = syscall.Syscall (syscall.SYS_INOTIFY_INIT, 0, 0, 0);
if err = os.NewSyscallError ("SYS_INOTIFY_INIT", int (errptr)); err != nil {
    // deal with the error
}

The first returned variable fd is the file descriptor, the second is ignored, and the last is the error code.

pth := "/home/ostsol/Programming/Go/notify/blah.txt"
str := uintptr (unsafe.Pointer (syscall.StringBytePtr (pth)));
wd, _, errptr = syscall.Syscall (syscall.SYS_INOTIFY_ADD_WATCH,
uintptr (fd), str, 0x00000002);
if err = os.NewSyscallError ("SYS_INOTIFY_ADD_WATCH", int (errptr)); err != nil {
    //deal with the error
}

Unfortunately, Go does not expose the event masks for inotify.  0x00000002 is the mask for the modify event.

The event can be read via syscall.Read, which receives the file descriptor (casted to int) and an empty byte buffer.  The inotify event structure is, of course, not implemented in Go, so one has to create one's own:

type NotifyEvent struct {
    Wd int32;
    Mask uint32;
    Cookie uint32;
    Len uint32
}

Decoding the buffer filled by syscall.Read is accomplished via the encoding/binary package.  The binary.Read function expects a type that fulfills the io.Reader interface, which one can create via the NewReader function in the strings package.

The original inotify_event structure exposed via the C header sys/inotify.h also contains a name field.  You'll notice that its type is char[0].  We did not add this field to our structure because binary.Read would try to find a value to put in it.  The value only exists if the Len field is greater than zero.  If it is, we can extract the string from the byte buffer manually.

chars := make ([]byte, 80);
ln, errno := syscall.Read (fd, chars);
if err = os.NewSyscallError ("SYS_READ", errno); err != nil {
    // deal with it
}

event := new (NotifyEvent);

reader := strings.NewReader (string (chars[0:]));
if err = binary.Read (reader, binary.LittleEndian, event); err != nil {
    // deal with it
}

fmt.Println ("Event:");
fmt.Printf ("\twd: %d\n\tmask: %d\n\tcookie: %d\n\tlen %d\n",
event.Wd, event.Mask >> 16, event.Cookie, event.Len);

if event.Len > 0 {
   fmt.Printf ("\tname: %s", string (chars[16:16+event.Len]))
}

In a real system, multiple events may be returned by syscall.Read.  Thus, the buffer may have to be much larger and one will have to iterate through it, each time creating a reader further along in the buffer.

event := new (NotifyEvent);

for i := uint32 (0); i < uint32 (ln); i += 16 + event.Len {
reader := strings.NewReader (string (chars[i:]));
 // ...
}

There are two problems that I encountered in the creation of this article.  First is the event.Mask field.  The value it returns is 32768, which is not the flag that I input via SYS_NOTIFY_ADD_WATCH.  Secondly, using SYS_NOTIFY_RM_WATCH tosses me an 'invalid argument' error.  Thinking it was a Go problem, I re-wrote the program in C, but the same issues occurred.  It's strange, but everything else I did works solidly.  Hopefully this article helps despite the issues.

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. . .

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.

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!