Tuesday, 30 November 2010

DelphiDoom for Delphi fans

I've recently found Delphi Doom, an adaptation from the original UNIX Doom C source code to Delphi. The project was finished in 2005 but the latest deploy was released on 3 March 2008 (Version: 1.0.2 build 383). I've been tinkering with it and it's been great!. It cast me back when I was young, trying to pass all the levels by killing some hideous and very nasty monsters. This Application is a WIN32 port of the famous Doom game created by ID Software. The main difference of DelphiDoom is that is written in the Pascal programming language. The source code has been translated from C to Pascal. In addition many new features have been added to to expand the old engine features and take advantage of capabilities of modern computers. Remember that you need the IWAD file just for being able to pay. The IWAD file is the file which contains all of the game data for a complete game.

Enjoy the game!.

Thursday, 18 November 2010

2d Physics with Delphi

I'm modelling a series of objects with some physics and mathematics and I found interesting to talk about the library I am using: Delphi APE. This fantastic library available for Delphi  (Windows) and Lazarus (Linux) allows very simple task as powerful as gravity, collision processes, grouping behaviour and general process. Great the job done by Alex cove and others like Vincent and Jeremy who helped him to make the conversion to Delphi.
This great library which I'm testing with Delphi 2010 is very easy to use and it shows a very interesting example combining different elements and letting them play. You can download the library from here, and test the different modelled items. The results are very well done and with simple steps we can achieve things like this:

Another interesting library is the one done by Algoryx called Phun.:


Related articles:

Wednesday, 17 November 2010

Alpha-beta pruning algorithm with Delphi

I'm trying to get round to writing more often and to do my own research with some interesting and complicated algorithms. Given to my great passion for different types of algorithms, in AI , I have found one very interesting and here you can get it build with Delphi 2010. With this solution, you'll be able to add values to the leaves and run the algorithm to find the nodes that will be evaluated and others that will be pruned. I've used my little framework to build the structure (using a GDI render) and then only focus on the algorithm that was the important part. Alpha-beta pruning is a search algorithm which seeks to reduce the number of nodes that are evaluated in the search tree by the minimax algorithm. It is a search with adversary algorithm used commonly for machine playing of two-player games (Tic-tac-toe, Chess, Go, etc.). It stops completely evaluating a move when at least one possibility has been found that proves the move to be worse than a previously examined move. Such moves need not be evaluated further. Alpha-beta pruning is a sound optimization in that it does not change the result of the algorithm it optimizes (Algorithmist.com). 

The pseudo-code is quite simple, and it looks like this:
The structure of the application is very simple and the most difficult part is the simulation process where you need to draw every step of the algorithm.
You can download the application from here (Thundax Alpha-beta pruning) and play with it to understand how the algorithm works.
This video shows the execution of the program:
The code of the algorithm is explained as follows:

Alpha-beta algorithm:
function TViewMinimax.alphabeta(Node: TNode; alpha: integer; beta: integer): integer;
var
    i: integer;
    ret: integer;
begin
    if Node.isLeaf then
        ret := Node.Value
    else
    begin
        for i := 0 to Node.children.Count - 1 do
        begin
            alpha := max(alpha, -alphabeta(Node.children.Items[i], -beta, -alpha));
            case Node.player of
                tMAX:
                    begin
                        Node.Value := alpha;
                        SetAlpha(Node, alpha);
                        Node.visited := true;
                    end;
                tMIN:
                    begin
                        Node.Value := -alpha;
                        SetBeta(Node, alpha);
                        Node.visited := true;
                    end;
            end;
            if beta <= alpha then
                Break;
        end;
        ret := alpha;
    end;
    result := ret;
end;

Drawing the nodes by using a pre-order method for iterating the binary tree:
procedure TViewMinimax.Draw;
begin
    preorder(Self.FMinimax.root);
end;

procedure TViewMinimax.preorder(root: TNode);
begin
    if Assigned(root) then
    begin
        if root.children.Count > 0 then
        begin
            DrawLine(root, root.children.Items[0]);
            DrawLine(root, root.children.Items[1]);
            preorder(root.children.Items[0]);
            preorder(root.children.Items[1]);
        end;
        DrawRectangle(root);
    end;
end;

procedure TViewMinimax.DrawRectangle(Node: TNode);
begin
    Fcanvas.Font.Name := 'Arial';
    Fcanvas.Brush.Style := bsSolid;
    if Node.visited then
        Fcanvas.Brush.Color := clRed
    else
        Fcanvas.Brush.Color := clWhite;
    if Node.selected then
        Fcanvas.Brush.Color := clGreen;
    Fcanvas.Pen.Width := 2;
    Fcanvas.Pen.Color := clBlack;
    Fcanvas.Rectangle(Node.position.x - gap, Node.position.y - gap, Node.position.x + gap, Node.position.y + gap);
    Fcanvas.TextOut(Node.position.x - 5, Node.position.y - 5, Inttostr(Node.Value));
    Fcanvas.Brush.Color := clWhite;
    if (Node.isLeaf) and (Node.Order <> 0) then
        Fcanvas.TextOut(Node.position.x - 5, Node.position.y + 15, Inttostr(Node.Order));
    if not Node.isLeaf then
    begin
        case Node.player of
            tMAX:
                begin
                    if Node.alpha <> 0 then
                        Fcanvas.TextOut(Node.position.x - 65, Node.position.y - 10, Inttostr(Node.Order) + ': a=' + Inttostr(Node.alpha));
                    if Node.newAlpha <> 0 then
                        Fcanvas.TextOut(Node.position.x - 65, Node.position.y + 5, Inttostr(Node.NewOrder) + ': a=' + Inttostr(Node.newAlpha));
                end;
            tMIN:
                begin
                    if Node.beta <> 0 then
                        Fcanvas.TextOut(Node.position.x - 65, Node.position.y - 10, Inttostr(Node.Order) + ': ß=' + Inttostr(Node.beta));
                    if Node.Newbeta <> 0 then
                        Fcanvas.TextOut(Node.position.x - 65, Node.position.y + 5, Inttostr(Node.NewOrder) + ': ß=' + Inttostr(Node.Newbeta));
                end;
        end;
        if Node.text <> '' then
        begin
            Fcanvas.Brush.Color := clyellow;
            if (Node.newAlpha = 0) and (Node.Newbeta = 0) then
                Fcanvas.TextOut(Node.position.x - 53, Node.position.y + 5, Node.text)
            else
                Fcanvas.TextOut(Node.position.x - 53, Node.position.y + 20, Node.text)
        end;
    end;
end;

Setting up the Minimax Algorithm:
procedure TForm1.Start1Click(Sender: TObject);
var
    vminimax: TViewMinimax;
    minimax: TMinimax;
    words: TStringList;
    alpha, beta: integer;
begin
    minimax := TMinimax.Create;
    if Edit1.Text <> '' then
    begin
        words := TStringList.Create;
        SplitTextIntoWords(Edit1.Text, words);
        minimax.AddNumbers(words);
    end;
    minimax.CreateTree;
    Memo1.Lines.Clear;

    Image1.Canvas.Brush.color := clwhite;
    Image1.Canvas.Rectangle(0, 0, Image1.Width, Image1.Height);

    vminimax := TViewMinimax.Create(Self.Image1.Canvas, minimax, Memo1);
    if CheckBox1.Checked then
        vminimax.time := 1000
    else
        vminimax.time := 0;
    alpha := alphavalue;
    beta := betavalue;

    vminimax.Draw;
    Self.Image1.Canvas.TextOut(951, 25 - 5, 'MAX');
    Self.Image1.Canvas.TextOut(951, 127 - 5, 'MIN');
    Self.Image1.Canvas.TextOut(951, 228 - 5, 'MAX');
    Self.Image1.Canvas.TextOut(951, 328 - 5, 'MIN');

    Start1.Enabled := false;
    CheckBox1.Enabled := false;
    vminimax.alphabeta(minimax.root, alpha, beta);
    vminimax.Draw;
    Start1.Enabled := true;
    CheckBox1.Enabled := true;

    FreeAndNil(words);
    FreeAndNil(minimax);
    FreeAndNil(vminimax);
end;

Splitting the text into numbers (comma separated values):
procedure SplitTextIntoWords(const S: string; words: TstringList);
var
    startpos, endpos: Integer;
begin
    Assert(Assigned(words));
    words.Clear;
    startpos := 1;
    while startpos <= Length(S) do
    begin
        while (startpos <= Length(S)) and (S[startpos] = ',') do
            Inc(startpos);
        if startpos <= Length(S) then
        begin
            endpos := startpos + 1;
            while (endpos <= Length(S)) and not (S[endpos] = ',') do
                Inc(endpos);
            words.Add(Copy(S, startpos, endpos - startpos));
            startpos := endpos + 1;
        end;
    end;
end;

Related links:

Friday, 12 November 2010

Wednesday, 10 November 2010

Genetic Algorithms (GA)

This semester I am improving knowledge in terms of Artificial Intelligence and one of the concepts that most captivated me was the resolution of problems using genetic algorithms. These are based on coding the problem in chromosomes and genes into packages. After applying a series of functions, we need to mutate the population to reach our goal. and find the best solution. The definition from wikipedia is: "The genetic algorithm (GA) is a search heuristic that mimics the process of natural evolution. This heuristic is routinely used to generate useful solutions to optimization and search problems. Genetic algorithms belong to the larger class of evolutionary algorithms (EA), which generate solutions to optimization problems using techniques inspired by natural evolution, such as inheritance, mutation, selection, and crossover".
Basically the algorithm works like this:


There are several examples on the net which uses GA to solve common problems such as these:
One of the examples that best shows the use of GA is the solution from Roger Alsing where the algorithm is trying to copy an image generating polygons. These polygons are created in a population of chromosomes and they try to evolve to fit the source image. I've been playing with it and it's great!. You can download the source code and the binaries from here.


Here you can see the results of playing with the application:

Genetic Vectorizer Example by Roger Alsing:

Using my image (40h of running time):

using Einstein image (20h of running time):
Video showing the start of the algorithm:


In the video you can see the different steps the algorithm is doing by creating a population of chromosomes as polygons and trying to fit them by shape and by colour from the source image. The result of the application is the image shown  above.


Sodorace game:
Sodarace is the on-line Olympics pitting human creativity against machine learning in a competition to design robots that race over 2D terrains using the Sodaconstructor virtual construction kit.

Enjoy the learning!.

Related articles:

Outstanding videos of robots

Due to the recent contributions of the scientific community about robots, here are a collection of the best videos I found on the Web. It's amazing how technology improves and the number of mysteries that lie ahead. In the following videos we can see the different robots built by Boston Dynamics (for me the most outstanding are the Big Dog and Little Dog). And we can also find the new Actroid-F presented recently in the AIST Lab Fair and other different examples of robots.




Boston Dynamics: Big Dog:

Boston Dynamics: Little Dog:

Actroid-F in AIST Open Lab:
 

Transformer Robot:

I hope you enjoy the astonishing videos!

Wednesday, 3 November 2010

David McCandless: The beauty of data visualization

This is an interesting video from TED talking about the beauty of data visualization. David McCandless turns complex data sets (like worldwide military spending, media buzz, Facebook status updates) into beautiful, simple diagrams that tease out unseen patterns and connections. Good design, he suggests, is the best way to navigate information glut -- and it may just change the way we see the world.

Presentation of the new Rad Studio XE and the new Visual Studio 2010 in Barcelona

On November 24 will be held this seminar in Barcelona, which conveniently will show us the new features of the new RAD Studio XE, Delphi XE, C++ Builder XE, Delphi Prism XE and RadPHP XE. I'll take this opportunity to learn in a practical way the latest additions, see examples of operation, contact other users, chat with the team and meet interesting Danysoft promotions. I'm also attending the Visual Studio 2010 presentation which will show us practical themes that are awakening the community of developers. The new ASP.NET , the MVC Framework and the new features included in the WCF (Windows Communication Foundation) will be the discussed topics.

I'll see you there!.

Related topics: