Technological Thoughts by Jerome Kehrli

I needed to have a little fun recently when slacking on my computer at night so, as is often the case in such situation, I spent some time on my snake project again.
I implemented a few evolutions as explained below and am now working on making the auto-pilot algorithm a little better.
It's funny how this snake application is something on which I get over and over again years after years, trying to make it better, reworking it, etc.

The first post on this blog about this app was there : www.niceideas.ch/roller2/badtrash/entry/snake-tt-0-2-alpha
Yeah, well, that doesn't make me younger, does it ?

The snake project

Snake is a little C++ / OpenGL / Real-Time project which shows a snake eating apples on a two dimensional board. It really is very much like the famous Nokia phone game except the snake finds its way on its own.

No nice textures, no sweet drawings yet, the world elements are mostly simple spheres. Trivial OpenGL features such as fog, lightning and shadows are implemented though.

The auto-pilot is still pretty stupid at the moment and the snake ends up eating itself quite fast.
This is the thing on which I am working now.

It still is a game as the "user" can at any moment deactivate the auto-pilot and take the control of the snake himself. At any moment, the auto-pilot can be re-engaged again or deactivated.

The project is open-source'd under GNU LGPL license and if you're interested in OpenGL, Vector Geometry, Real-time C++ Programming, or simply Algorithms you might very well enjoy having a look at the source code provided here.

1. Windows Executables

I have pre-compiled a windows executable using MingW and QT for Windows

The pre-built Windows Binary Executable is available here :

snake_win32_bin-0.3.1.zip

2. Build for Other platforms

Snake can be built using two different OpenGL canvas providers in three different configurations:

• the GLUT
• QT on Linux
• QT on Windows / MingW

MinGW, a contraction of "Minimalist GNU for Windows", is a minimalist development environment for native Microsoft Windows applications.
It's a pretty nifty compiler, Toolchain and tools collection for people such as myself who are very at ease with Unix but knows nothing about Windows (and I cannot stress enough how much this is a great source of pride and everyday happiness).

The source code is available here:

snake_src-0.3.1.zip

In order to build the software, one needs to :

1. Edit the file Makefile and defined the variables identifying the Qt installation (in case of using Qt)
2. Have GCC and the usual toolchain available in the PATH
3. Have OpenGL libraries (mesa or else) available in LD_LIBRARY_PATH
4. Open a console in the root folder of the source distribution
5. Type make and follow instructions
6. Use make clean to clean the binary objects

3. User Manual

• s - start/stop the camera rotation
• p - pause the game (both snake and camera rotation if enabled)
• o - turns the auto-pilot engine on/off
• u, h, j, k - When auto-pilot is turned off, one can use they keys to control the snake
• In addition, on the Qt version, the user can use the LEFT, RIGHT, UP, DOWN arrows to control the snake

4. Latest Changes

OpenGL Canvas library

I made a Qt version of the software since compiling the GLUT (or finding a binary version of it) under windows is a nightmare. The source code is very old and hasn't been maintained, etc.
Long story short, the GLUT library is pretty much impossible to compile under windows MingW (well OK at least let's say I didn't succeed in a few dozens of minutes so I dropped the idea) and I didn't want to bother on alternatives.
For the sake of completeness, let's say that the freeglut library is available for MingW and that would have been worth a try.

Anyway, I wanted to use Qt since ... well I love Qt. I really regret the licensing approach and the fact its not a truly open source library (opensource license of Qt is very very restrictive) but the slots and signal concepts as well as the completness and the overall design of the library are definitely awesome.
I've been playing a lot with wxWidgets on Linux before I encountered Qt and I have to admit that I'm really using exclusively Qt now when I program in C++. I'll share in a future post all the details in regards to why I believe Qt is awesome since this exceeds the scope of this article.

So yeah I figured I just port the Snake app from GLUT to Qt instead of messing with alternatives to GLUT such as freeglut.

Having done this, I can now easily build the snake project under both Windows/MingW and Linux.

Algorithm

I'm trying to experience many things in regards to how make the snake "smarter" and have him survive longer on the board.

The key idea on which I am working now is to give a huge weight (see algorithm section below) to cells that would cause a partitioning of the board should the snake go on them.

Implementing this should be straightforward, at least as much as the idea is simple, but happens to be difficult and I'm struggling with it.
For the moment I de-activated this and left the current implementation as commented code in the software. If anyone is willing to help, I would be really happy to have a second pair of eyes on this.

5. The algorithm

The way the auto-pilot drives the snake is really a simple idea: representing the board as a graph and using dijsktra's shorted path algorithm to find the shortest path from the snake head to the seed

The procedure getNextDirection is called each and every time the snake gets on a new cell to compute the direction he should take from there and hence the next cell he should reach.

procedure getNextDirection

    headCell = get cell of position of head of the snake
    seedCell = get cell of position of the seed
    
    for every cell in board do
        computeCost of cell
    end for 
    
    -- build a graph-like structure of the board,  
    -- connecting every cell with cost computed above 
        
    adjacencyMap = initialize empty array of list
    
    for every cell in board do
    
        for every neighbour of cell do  
            add to adjacencyMap[cell] 
                    an edge to neighbour 
                    with as weight the cost of neighbour computed above
        end for 
        
    end for 
    
    -- compute shortest path from every cell to every cell
    -- using dijkstra's algorithm and the data structure above
    
    dijkstraMinDistance, dijsktraPreviousCell = run dijkstra Shortest Path algorithm 
            on adjacencyMap for headCell
    
    -- get distance in shortest path from headCell to seedCell 
    minDistance = dijkstraMinDistance[seedCell] 
    
    cellTravelList = NULL;
    if no path has been found then
    
        -- we have a partitioning (unconnected graph) of the board 
        return dummy random direction
        
    else
    
        -- build the path form headCell to seedCell
        cellTravelList = path to follow using dijsktra's computed dijsktraPreviousCelli> above
        
        return next cell from cellTravelList         
    
    end if        

end procedure

The actual "intelligence" here is the in cost computation - the computeCost procedure - since this is how we can influence the path followed by the snake.

procedure computeCost (on cell)

    -- if cell has a body part on it or the head of the snake
    -- then return a ridiculously big value
    
    if cell is not free then
        return 99999999;
    end if
        
    -- we want the snake as close as possible to its body
    -- as a way to avoid partitioning of the board as much as possible
    
    bodyPartNearCount = count of parts of body in nearby cells 
    
    if bodyPartNearCount > 0 then
    	
    	-- dynamic cost
        return 10000 / ((bodyPartNearCount * bodyPartNearCount) + 1);
        
    end if
    
    -- also favoring long walks on the border seems a good idea 
    if cell is close to the border then
        return 9000
    end if
    
    -- default value 
    return 10000;

end procedure