Saturday 26 December 2009

Snake game: when programming isn't compatible with modern theories

I saw a question about how to create a snake game "like on the Nokia mobile phones". The answers differed a lot from each other - but few talked objects (OOP). The general consensus was that the snake should be represented as a double-linked list, linked using pointers.

The first time that I saw the game, was on my brother's computer. He had created the computer himself, based on a Zilog Z80A CPU with 4MHz and 4kbyte RAM. Everything was home made - graphics electronics design, etching the boards, a hex keyboard for his machine code boot software, and a high level language and all the software on top of it. However, the computer had the boot software and the high level language in an EPROM (requires UV light to be erased), and there was no other persistent storage, so all programs that you wanted to use, had to be programmed before using it.

It was back in 1981, and I was allowed to use his computer for gaming, and I knew how to use the hex keyboard to instruct the boot software to start up the high level language, so that was great. I just had to program the snake game every time I wanted to play it, so I got quite good at it. And each time I programmed it, I made it a bit different, of course.

Enough about the background, here is the data structure of a snake game:

type
  TItem=(spEmpty, spFood, spPoison, spWall, spSnakeHead, spUp, spDown, spLeft, spRight);
var 
  arr:array[0..79,0..24] of TItem;
  TailX,TailY,HeadX,HeadY:integer;
  SnakeLength,LengthToAdd:integer;

This is how you add food or poison, avoiding snake positions, wall etc.:

procedure AddItem (item:TItem);
var
  x,y:integer;
begin
  // It can be argued that this loop does not
  // always end within finite time, but who cares?
  repeat
    x:=random(80);
    y:=random(25);
  until arr[x,y]=spEmpty;
  arr[x,y]:=item;
end;

Then you need this one:

procedure MoveCoor (var x,y:integer;dir:TItem);
begin
  case dir of
    spUp:dec (y);
    spDown:inc (y);
    spLeft:dec (x);
    spRight:inc (x);
  end;
end;

So when you want to move the snake's head, you do this:

arr[HeadX,HeadY]:=MoveDirection;
MoveCoor (HeadX,HeadY,MoveDirection);
found:=arr[HeadX,HeadY];
arr[HeadX,HeadY]:=spSnakeHead;
if found<>spEmpty then begin
  if found=spFood then LengthToAdd:=SnakeLength*0.5
  // Alternatively just set LengthToAdd:=1
  else (* End game, we ran into something that is not healthy *);
end;

Increasing the length is simple, just keep a counter of how much longer the snake needs to become, and every time you are about to move the tail, either decrement that counter, or when it is zero, actually move the tail. This is how to move the tail:

if LengthToAdd=0 then begin
  dir:=arr[TailX,TailY];
  arr[TailX,TailY]:=spEmpty;
  MoveCoor (TailX,TailY,dir);
end else begin
  dec (LengthToAdd);
  inc (SnakeLength);
end;

As you can see, a snake game is seriously simple, uses almost no CPU, is very short in source code and uses very little RAM. There is not a single object in all this, because OOP wasn't invented back then.

Could this be done more easily today using modern programming? I haven't found a better method, yet. If we should describe the old method with modern terminology, what would that description look like? The snake must be some kind of object, but it's data is stored in an array that represents the screen. However, the screen array doesn't just show the presence of the snake, but also the direction to go in order to find the next element of the snake. So, basically, according to modern criteria, this code is unstructured, messy, non-scalable, non-maintainable etc. However, in my opinion, as long as the code is easy to read, it is maintainable, and if it scales within required boundaries, it's scalable. It would be easy to encapsulate the "Snake game engine" into an API, hiding the implementation details, so I definitely still consider this to be great code.

Wednesday 23 December 2009

Unicode technical paper from Cary Jensen

Cary Jensen has produced a White Paper about migrating to Delphi 2009, with real stories from real migrations. View it here or download it here. The paper is the result of his call for migration stories, earlier, and a lot of people contributed with examples, including me. Besides being a good paper to read before migrating, it also explains many things that most may not be aware of.

Tuesday 22 December 2009

Kylix comeback or something better?

Heise.de reports, that the Qt toolkit is currently being ported to Google's Native Client (NaCl). Qt was known as the GUI framework for Kylix on Linux, and once Qt has been ported, it seems like a very easy thing to make Kylix able to compile GUI apps for Google NaCl, providing a development kit that creates GUI apps with native code to run as managed code inside a browser.

Does this make sense? Some of it does. Delphi/native developers create cool GUI apps, but most of them are networked. If we can create a applications, that are delivered as easily as web pages, using the same source code as our native Win32 apps, that would be extremely great. However, Qt or CLX would not be the best framework for it... so if Embarcardero delivers a CLX-based tool for Qt & NaCl, most users would probably initially not dare to use it for anything else than products with short expected support lifetime. However, the internet has a lot of these.

In order to invest a large amount of R&D money into apps developed using Delphi for Qt&NaCl, right from the first version, we need at least TCanvas support, but preferrably support of the visual components of the VCL.

I seriously hope that there is a business case for some of this. Embarcardero has a unique chance to create something great, based on existing technology. One of the cool things about Google Chrome and Google NaCl is, that they do not require administrative rights to be installed on a PC - unlike the .net runtime. And with Google Chrome Frame, even MSIE will be able to run this.

Friday 18 December 2009

Call for learning about bits and bytes

I still often encounter people with a Master's degree in Computer Science, Information Technology or whatever, who are not used to think bits and bytes. The world of computing is huge, and I fully understand that the universities need to filter and carefully select what topics they should teach their students. However, there is a huge number of topics where knowledge about bit manipulation is important: IT security, resource leaks, format compatibility, communication protocols, low level APIs, data conversion, and even such thing as understanding UTF-8 used in XML, and many other places. There almost isn't a problem that cannot be understood by looking at it as bits and bytes.

Therefore, my advice to Computer Science students is this: Learn and understand bits and bytes, addressing, data formats (including IEEE 754!), binary operators and pointers and offsets. Don't consider yourself a good programmer before you know these by heart.

Thursday 10 December 2009

When to use record instead of classes

The original use or the record construct in ObjectPascal was to group different values in a way, that can be used in arrays, parameters etc. Classes have taken over this job, but the record construct is still sometimes important.

For instance:

type
  TTest=
    class
      a,b,c:integer;
    end;

var 
  arrT:array[1..1000000] of TTest;

begin
  for i:=low(arrT) to high(arrT) do begin
    arrT[i]:=TTest.Create;
    arrT[i].a:=2;
    arrT[i].b:=3;
    arrT[i].c:=4;
  end;
end;

On my computer, this takes 161ms first time, and 91ms second time. Reading it like this, takes 9ms:

begin
  c:=0;
  for i:=low(arrT) to high(arrT) do begin
    c:=c+arrT[i].a+arrT[i].b-arrT[i].c;
  end;
end;

If you rewrite this code to use array of record, it looks like this:

type
  RTest=
    record
      a,b,c:integer;
    end;

var 
  arrR:array[1..1000000] of RTest;

begin
  for i:=low(arrR) to high(arrR) do begin
    arrR[i].a:=2;
    arrR[i].b:=3;
    arrR[i].c:=5;
  end;
end;

This takes 17ms first time and 9ms second time. Reading it takes 6ms:

begin
  for i:=low(arrR) to high(arrR) do begin
    arrR[i].a:=2;
    arrR[i].b:=3;
    arrR[i].c:=5;
  end;
end;

In other words, in this specific case, a record is about 10 times faster than a class, using Delphi 2009. Adding a string that does not receive a value, does not change the values much. Instead of 17ms, it now takes 23ms, but the record size has increased, so that makes sense:

type
  RTest=
    record
      a,b,c:integer;
      s:string;
    end;

However, if you assign a value to the string, performance drops:

begin
  for i:=low(arrR) to high(arrR) do begin
    arrR[i].a:=2;
    arrR[i].b:=3;
    arrR[i].c:=5;
    arrR[i].s:='234';
  end;
end;

In this case, the record solution takes 124ms, and the class-based solution takes 214ms. In other words, record only beats the class solution by a factor 2. The reason? Each string value assignment is as complicated as creating an object.

Conclusion: record beats classes in speed, but the benefit is only significant if you use less than one string value per record, and don't use classes inside the record. The biggest improvement is in creating the data structures, not in reading them.

Monday 7 December 2009

Why there is no app store on Windows

How long does it take to install Microsoft Office? Well, first you have to order it, and then you have to wait for it to arrive by mail, on a physical medium. Ever wondered why there is no app store on Windows?

Steve Ballmer explains it in an article on CNET: "nobody has any trouble getting apps"

I'm obviously nobody, so there must be another reason. Here is my best guess: An app store on Windows would be a target of regulation by authorities, and this would make it hard for Microsoft to design the app store in a way, that makes Microsoft applications the obvious choice for Windows users. Microsoft seems to take it for granted, that the alternative to getting an app on Windows, is to get the app on another PC that does not run Windows. For many Windows software vendors, it has always been the rule of thumb, that the user picks the application first, and the OS next - but...

as Ballmer puts it: "The whole Internet is designed basically for the Windows PC."

So, why is everyone excited about "app stores" like in Ubuntu, iPhone, Playstation, Android etc.? Ballmer explains it this way:

Ballmer: "...you need so many apps in a mobile app store is to remap Web sites that were written for the PC to look good on a mobile phone..."

Seen from a marketing point of view, there is no doubt that brands, that made it well on the web, like Facebook, are also good for marketing app stores. However, most of the apps that I downloaded from an app store, have either used the built-in GPS, used the built-in camera, improved the phones user interface, saved phone bill costs or interacted with other apps on the phone, like the contacts database. Nothing of this can be done from a web app.

Since Microsoft does not seem to be motivated for an app store, what about Google, Oracle/Sun and IBM? However, they do everything they can to make Windows substitutable, and do not have an interest in creating an app store for Windows. Sun was discussing a Java app store, but that doesn't really solve the problem. Creating an Open Source app store has 2 problems: Lack of accountability and lack of wide deployment. The app store needs to be very widely deployed in order to be attractive - you cannot ask people to download and install an app store, it needs to be there automatically, maybe as part of something else (like bundling with a browser).

There seems to be no reason to expect a Windows app store any time soon.