A road named NoNameUno

For randomly generated tree, now the placement of tree algorithm works after porting to java, patching, simplifying the routines. Interestingly, the original algorithm's base reference point is zero coordinate, and in my situation it could be any suitable point in the surface. So depending on the surface resolution in pixels, it is possible that some of the random trees can not be placed unless it dynamically adjust the edge lengths and base reference points. Since we know the bounds of the surface geometry, it was not very hard to adjust ( if it is possible to adjust !), and that seems to be working after I plugged in a wrapper to the placement algorithm.

In a short while I should be getting back to the basics of the game formulation...

For now, I was able to bootstrap the Android on Openmoko's free runner phone. But I'm still working for a solution to connect to the device from my development environment. Once I get the device to talking to Eclipse IDE and/or adb android tools, I should be fine for my basic steps. Next I will have to venture the land of DBoard, which is the debug board for the phone. Most of the android stuff could be debugged or poked around using ADB and/or Eclipse. Linux kernel debugging, booting etc., will need the DBoard.

On the application side, I've quite a bit of improvements. Now I can place multiple trees in the canvas. I need bit more data structures to implement the rest of the game engine. Once that is there, I should be able to play against the computer. Hope to win some intermediate level games. By the way, games are structured in three levels: Beginner, Intermediate, and Advance level. The combinatorial explosion even with 30 to 40 nodes with random edges between them would make, at least my head to spin.

In a combinatorial game design to be played by users, one basic step is to generate random configurations and place them on the board. I thought it would be not so difficult to handle that, since I know how to generate random configurations of those games and output the numbers to signify or if you will, map the output set to a specific game configuration...

In first attempt, I was trying to generate random tree edges using some published source code. Since my past life ( 20 or so years ago ), I was dealing mainly with graphs and networks, I can still use the knowledge to bootstrap the process, and as expected I was able to generate random graph with specific properties that each instance is a tree. There is no forest, and no cycles.

Now when I tried to place ( or rather draw it on computer's drawing surface ) using program modules that I wrote, I found that it is a complex problem to place even a tree with 20 nodes without crossing edges, and without having a visually unpleasant outcome...  Though I had the feeling that I would be in trouble, since it is a powerful geometric problem, and once again my whatever little computational geometry background telling me that I'm about to face a huge problem placing random tree on a drawing canvas.

Though there are variations of this problem declared as NP-HARD, the problem I was trying to deal with seems to have a O(n) solution. It's an old problem, and has history by itself. Currently I'm trying to absorb the article and the algorithm written by John Q. Walker II. It was published in Dr. Dobb's journal.

Once I write this algorithm using Java, and get the graph placement working I will start analyzing the mathematical properties of those games, well of course, using some of the books written on them.

I will have to switch to a new direction, since building multiple kernel sources seems to be a bit of a problem. I'm actually trying to have both openmoko and beagleboard environment simultaniously...

Well, for the application side I'm trying to comeup with a GUI interface that does not have rectangular boundaries for the controls. So for example if I've a bucket of fruits, and I click on banana, it should tell me which banana I picked...

I will get back to android kernel port soon ...

Before I dive into the detail of my application I would like to explain a bit about combinatorial games, and programming challenges involved in them.

Combinatorial games are in general two party or single party games like: Chess, Nim, Hackenbush etc. The beauty of these games are that one party can be the computer and there are already rich bodies of mathematical formulations for them. Also most of them has combinatorial explosions so effecient handling of data structures and algorithms are central to have a decent experience for users. Also some of these games have evaluation processes that quantifies the chances of winning. When an user plays these games, they can not possibly calculate the chances of winning, but for fairly large configurations of these classes of games, computer can detects the chances, a play accordingly.  Moreover the configurations of these games can sometimes be randomly generated, placed on the board for other party ( an user) to play. Easy games, not so easy games, and difficult ones can be placed as an user become more and more familiar with the games and builds intuition.

In my next few blogs, I will try to clarify the process or approach I'm taking to implement some instances of combinatorial games. But it requires some of the following -

• Given a configuration, can I quantify the game value. And chance of winning.
• Does it really matters if the user start first or the computer starts first?
• What, if any chance, of declaring that no matter how hard you try, you gona loose to your opponent (computer).
• What are the fundamental types and data structures we need to use.
• What are the performance problems we are likely to hit when we set out to implement.
• How to represent these to an user - User interface related stuff.
• Finally how much I can carry from one game to another type of game - Reusability.
• How do we classify the hardness of the configuration?
• How do we generate and place those configurations in increasing order of difficulties?

To build an Android application and test, we don't need to build Android sources. All we need is to setup the eclipse environment as discussed earlier. But building Android and upload to a device is essential for new boards.  Here I will discuss a bit of my experience building android from source.

Android source is maintained using git souce code control system. To get the source and build use the instructions from the link -  http://source.android.com/download/using-repo.

Once you have the source downloaded you can build the source tree. By default, you will not get the linux os source, instead you will received a prebuilt subdirectory for linux kernel. So for now, we can build the android framework related stuff.

Following link tells us how to build the android ( without building the linux kernel ) -

http://source.android.com/download.

Once you build the android infrastructure, next step would be to bring down the kernel source and build it. I'm sure the linux kernel hacker knows lot more than me, but goldfish is one of the default configuration that you can get from the kernel git repository on top of the base kernel, then build it. This is where the device specific personalizations are needed, and for that we need to tweek the standard configurations to target device specific configurations...

I was looking at Android to see how it works, and how I could develop some application(s) or hack the linux kernel. Anything new makes me feel like I'm a moron. So I started off slow, and encounter quite a few problems that I would like to discuss here in couple upcoming blog topics.

My first approach was to get the application development environment ready, so that I can build some simple applications and try it out on an emulator, since I'm not ready to invest on devices and other board support packages needed to do any serious development.

I looked at the online documents published by google, and subscribed to a few of the google groups. I have been using eclipse for just about 3 months because my previous job was posix compiant middleware, and was looking for one IDE that spans between Windows and Linux when it comes to using it seemlessly. If you don't know eclipse is based on java, and its default environment is Java, but there is a lot of plug-ins that gives you other development facilities. For example, the CDT gives the c/c++ development environment.

What you need for android is to get the android sdk, and android plug-in for eclipse. Once you have that, searching a few online sites gives enough information to get the android application development environment going. Note that once you have the environment set, you can either build a simple application with generated java code to build and test. This has been explained in some online sites. Also you can create a project from existing sample projects that come with the sdk. For running a built project, you need to create AVD ( android virtual device). AVDs are somewhat tied to sdk version, so you need to know what version of sdk you want to use. In my case I've seen three different types: v1.1, v1.5, and Google API version. I stick to sdk 1.5, since it is the latest and I did not yet look at Google API.

To create AVDs, you can use the tools that come with sdk. For a reference look at - http://developer.android.com/guide/developing/tools/avd.html. As soon as you create an AVD, it would show up in your eclipse environment. Just look under -

Windows->Preference  or Windows->Android DVD Manger.

Once you have the device manager configured, you should be able to run your application on emulator. But be watchful about the starting of the device ( in this case your emulator).  I've seen it gets stuck, and sometime it is just slow. If it is stuck, you might need to kill the emulator window by closing it, then re-run the application. For more informations on the status of the AVD etc., you need to look at the documents to use the tools from the sdk. There are couple of useful tools under the tools subdirectory of your sdk installation directory.