Graphs

Many of the programs on the DelphiForFun website use graphs for game play. Examples include Sliding Coins Puzzle, Nim, Gametrees, and Minimax, Knight's Tour, Traffic Jam and Coal to Diamonds Puzzle. We recommend that you do some background reading if necessary, and we provide some guidance and links below. Graphs are often used together with the Minmax algorithm, which is also covered in the suggested reading. The terminology has these synonyms and abbreviations:
  • A directed graph is a digraph.
  • A vertex is a node.
  • An arc is an edge.
  • BFS stands for Breadth First Search.
  • DFS stands for Depth First Search.
  • An heuristic is variously described as an evaluation or rule of thumb.

Several online documents of university Artificial Intelligence course material cover the use of graphs in games. For a thorough explanation of a simple example of the Minimax algorithm see the MIT paper. A useful paper from Iowa covers the terminology and gives clear examples of an adjacency matrix. Trees are special cases of graphs. See this StackOverflow page to help you to decide if a certain graph is a tree. (We have covered binary trees in our tutorial on recursion and referred back to it from our sections on sorting and searching). Two relevant instructive pages on the DelphiForFun website are Graph Searching and Nim, Gametrees, and Minimax.

See our demonstration of breadth first search and depth first search, together with its Smart Pascal code, below.

Tree Search Demonstration

The demonstration is set up for BFS (breadth first search). Change the selection to DFS for depth first search. Select the node number of the target to see the search results in the memo.

TreeSearch.html

If the program does not work, try another browser such as Chrome. If you see no display at school, the security system might have blocked it. You can try instead this direct link to the program running on its own page.

The nodes are stored in a TObjectList. We use a queue to hold the indices of nodes to be visited in the BFS and a stack to hold them in the DFS. The code of XQueue and XStack was posted recently by Nico Wouterse on the Smart Mobile Studio forum.

Smart Pascal Code of Form

unit Form1;

interface

uses 
  SmartCL.System, SmartCL.Graphics, SmartCL.Components, SmartCL.Forms, 
  SmartCL.Fonts, SmartCL.Borders, SmartCL.Application, System.Lists,
  SmartCL.Controls.PaintBox, SmartCL.Controls.Memo, SmartCL.Controls.Listbox,
  SmartCL.Controls.Label, System.Colors, uRendering, uNode, XQueue, XStack;
type
  TForm1 = class(TW3Form)
  private
    {$I 'Form1:intf'}
  protected
    NodeIndexQueue: TQueue;
    PathStack, NodeIndexStack: TStack;
    CurrentIndex: integer;
    PathString: string;
    procedure InitializeForm; override;
    procedure InitializeObject; override;
    procedure SetupNodes;
    procedure BFS(TargetNode: TNode);
    procedure DFS(TargetNode: TNode);
    procedure RetrievePath;
  end;
var
  ListOfNodes: TObjectlist;
  A, B, C, D, E, F, G, H, I, J, CurrentNode, TempNode: TNode;

implementation

procedure TForm1.RetrievePath;
begin
  PathString := 'Found path: ';
  // Follow reverse path via previousNode values and add each node to stack.
  PathStack := TStack.Create;
  PathStack.Push(CurrentIndex);
  repeat
    CurrentNode := CurrentNode.PreviousNode;
    CurrentIndex := ListOfNodes.IndexOf(CurrentNode);
    PathStack.Push(CurrentIndex);
  until CurrentIndex = 0;
  // Pop the nodes to get the forward path to the target.
  for var i := 0 to PathStack.Length - 1 do
    begin
      CurrentIndex := PathStack.Pop;
      PathString += TNode(ListOfNodes[CurrentIndex]).Name + ' ';
     end;
  W3Memo1.Text := W3Memo1.Text + PathString;
end;

procedure TForm1.BFS(TargetNode: TNode);
begin
  repeat
    if NodeIndexQueue.Length = 0 then
      begin
        ShowMessage('Error - not found');
        exit;
      end
    else
      begin
        CurrentIndex := NodeIndexQueue.Dequeue;
        W3Memo1.Text := W3Memo1.Text + 'Visited ' + inttostr(CurrentIndex) + ' ';
        CurrentNode := TNode(ListOfNodes[CurrentIndex]);
        if CurrentNode = TargetNode then
          begin
            RetrievePath;
            exit;
          end
        else
          begin // not found
            TempNode := CurrentNode;
            for var i := 0 to TempNode.AdjacentNodes.Count - 1 do
              begin  // Add child nodes to queue
                CurrentNode :=  TNode(TempNode.AdjacentNodes[i]);
                CurrentNode.PreviousNode := TempNode;
                CurrentIndex := ListOfNodes.IndexOf(CurrentNode);
                NodeIndexQueue.Enqueue(CurrentIndex);
              end;
            W3Memo1.Text := W3Memo1.Text + 'Queued indices: ' +
                            NodeIndexQueue.FHandle.join(' ') + #13#10;
          end;
      end;
  until false;
end;

procedure TForm1.DFS(TargetNode: TNode);
begin
  repeat
    if NodeIndexStack.Length = 0 then
      begin
        ShowMessage('Error - not found');
        exit;
      end
    else
      begin
        CurrentIndex := NodeIndexStack.Pop;
        W3Memo1.Text := W3Memo1.Text + 'Visited ' + inttostr(CurrentIndex) + ' ';
        CurrentNode := TNode(ListOfNodes[CurrentIndex]);
        if CurrentNode = TargetNode then
          begin
            RetrievePath;
            exit;
         end
        else
          begin // not found
            TempNode := CurrentNode;
            for var i := TempNode.AdjacentNodes.Count - 1 downto 0 do
              begin  // Push child nodes to stack in reverse order
                CurrentNode :=  TNode(TempNode.AdjacentNodes[i]);
                CurrentNode.PreviousNode := TempNode;
                CurrentIndex := ListOfNodes.IndexOf(CurrentNode);
                NodeIndexStack.Push(CurrentIndex);
              end;
            W3Memo1.Text := W3Memo1.Text + 'Stacked indices: ' +
                            NodeIndexStack.FHandle.join(' ') +  #13#10;
          end;
      end;
  until false;
end;

procedure TForm1.InitializeForm;
begin
  inherited;
  SetupNodes;
  // Draw tree in paint box
  PB.OnPaint := procedure(Sender: TObject; Canvas: TW3Canvas)
                begin
                  RenderScene(PB.Canvas);
                  PB.Invalidate;
                end;
  // List box for selecting destination node
  lbTarget.ItemHeight := 28;
  lbTarget.ItemClass := TW3Label;
  for var i := 1 to 9 do
    lbTarget.Add;
  lbTarget.Styles.SelectedColor := clLightBlue;
  lbTarget.EnableAnimation := false;
  for var i := 0 to 8 do
    TW3Label(lbTarget.Items[i]).Caption := inttostr(i + 1);

  lbTarget.OnSelected := procedure (sender: TObject; idx: integer)
    begin
      W3Memo1.Text := '';
      CurrentNode := A;
      if lbSearchType.SelectedIndex = 0 then  // BFS
        begin
          NodeIndexQueue := TQueue.Create;
          NodeIndexQueue.Enqueue(0);
          BFS(TNode(ListOfNodes[idx + 1]));
        end
      else  // DFS
        begin
          NodeIndexStack := TStack.Create;
          NodeIndexStack.Push(0);
          DFS(TNode(listofnodes[idx + 1]));
        end;
    end;
  // List box for selecting BFS or DFS
  lbSearchType.ItemHeight := 28;
  lbSearchType.ItemClass := TW3Label;
  lbSearchType.Add;
  lbSearchType.Add;
  lbSearchType.Styles.SelectedColor := clLightBlue;
  lbSearchType.SelectedIndex := 0;
  lbSearchType.EnableAnimation := false;
  TW3Label(lbSearchType.Items[0]).Caption := 'BFS';
  TW3Label(lbSearchType.Items[1]).Caption := 'DFS';
end;

procedure TForm1.InitializeObject;
begin
  inherited;
  {$I 'Form1:impl'}
end;
 
procedure TForm1.SetupNodes;
begin
  // Call each node constructor to set X and Y coordinates and name.
  A := TNode.Create(150, 20, '0');
  B := TNode.Create(100, 80, '1');
  C := TNode.Create(200, 80, '2');
  D := TNode.Create(30, 140, '3');
  E := TNode.Create(100, 140, '4');
  F := TNode.Create(140, 140, '5');
  G := TNode.Create(190, 140, '6');
  H := TNode.Create(230, 140, '7');
  I := TNode.Create(60, 200, '8');
  J := TNode.Create(130, 200, '9');
  // Link up the nodes
  A.AddLink(B);
  A.AddLink(C);
  B.AddLink(D);
  B.AddLink(E);
  B.AddLink(F);
  C.AddLink(G);
  C.AddLink(H);
  E.AddLink(I);
  E.AddLink(J);

  ListOfNodes := TObjectList.Create;
  // Place the nodes in the ListOfNodes TObjectList.
  ListOfNodes.Add(A);
  ListOfNodes.Add(B);
  ListOfNodes.Add(C);
  ListOfNodes.Add(D);
  ListOfNodes.Add(E);
  ListOfNodes.Add(F);
  ListOfNodes.Add(G);
  ListOfNodes.Add(H);
  ListOfNodes.Add(I);
  ListOfNodes.Add(J);
end;
 
initialization
  Forms.RegisterForm({$I %FILE%}, TForm1);
end.    

Smart Pascal Code of uNode

unit uNode;

interface

uses 
  SmartCL.System, System.Lists;

type
  double = float;

  TNode = class(TObject)
  public
    X, Y: double;
    Name: string;
    AdjacentNodes: TObjectList;
    PreviousNode: TNode;
    constructor Create(XX, YY: double; NodeName: string);
    procedure AddLink(NewNode: TNode);
  end;

implementation

constructor TNode.Create(XX, YY: double; NodeName: string);
begin
  X := XX;
  Y := YY;
  Name := NodeName;
  AdjacentNodes := TObjectlist.Create;
  PreviousNode := nil;
end;

procedure TNode.AddLink(NewNode: TNode);
begin
  AdjacentNodes.Add(NewNode);
end;

end.
    

Smart Pascal Code of uRendering

unit uRendering;

{
    Adapted from A_Star, Copyright (c) 2011 Christopher Winward

    Licensed under the Apache License, Version 2.0 (the "License"); you may not
    use this file except in compliance with the License, as described at
    http://www.apache.org/licenses/ and http://www.pp4s.co.uk/licenses/

    Converted to Smart Pascal by PPS (2016)
}

interface

uses
  SmartCL.System, SmartCL.Graphics, uNode;

procedure DrawNode(Canvas: TW3Canvas; NodeToDraw: TNode);
procedure RenderScene(Canvas: TW3Canvas);

implementation

uses
  Form1;

procedure DrawNode(Canvas: TW3Canvas; NodeToDraw: TNode);
begin
  Canvas.FillStyle := 'white';
  Canvas.FillRectF(NodeToDraw.X, NodeToDraw.Y, 32, 32);
  // Write the node name.
  Canvas.FillStyle := 'black';
  Canvas.Font := 'bold 12pt arial';
  canvas.FillTextF(NodeToDraw.Name, NodeToDraw.X, NodeToDraw.Y, 10000);
end;

procedure RenderScene(canvas: TW3Canvas);
var
  Count, InnerCount : integer;
begin
  // Draw the  background
  Canvas.FillStyle := 'lightgrey';
  Canvas.FillRect(0, 0, 304, 232);
  // Draw the nodes.
  for Count := 0 to ListOfNodes.Count - 1 do
    DrawNode(Canvas, TNode(ListOfNodes[Count]));
  // Draw the edges
  for Count := 0 to ListOfNodes.Count - 2 do
    begin
      for InnerCount := 0 to (TNode(ListOfNodes[Count]).AdjacentNodes.Count - 1) do
        begin
          TempNode := TNode(TNode(ListOfNodes[count]).AdjacentNodes[InnerCount]);
          Canvas.FillStyle := 'blue';
          Canvas.StrokeStyle := 'blue';
          Canvas.BeginPath;
          Canvas.LineF(TNode(ListOfNodes[Count]).X + 16,
                       TNode(listOfNodes[Count]).Y + 16,
                       TempNode.X + 16, TempNode.Y + 16);
          Canvas.ClosePath;
          Canvas.Stroke;
        end;
    end;
end;

end.
    

Smart Pascal Code of XQueue

We thank Nico Wouterse for sharing his code of XQueue.

unit XQueue;

interface

uses
  SmartCL.System, System.Types;

type
  TQueue = class (TObject)
  public
    Constructor Create; virtual;
    Procedure   Enqueue(Item: Variant);
    Function    Dequeue: Variant;
    Function    Peek: Variant;
    Function    Length: Variant;
    Procedure   Print;
    FHandle :   THandle;
  end;

implementation

Constructor TQueue.Create;
begin
  inherited Create;
  FHandle := TVariant.CreateArray;
end;

Procedure TQueue.Enqueue(Item: Variant);
begin
  If Item.IsString then Item := "'" + Item + "'";
  FHandle.push(Item);
end;

Function TQueue.Dequeue: Variant;
begin
  result := FHandle.shift();
end;

Function TQueue.Peek;
begin
  result := FHandle[0];
end;

Function TQueue.Length:Variant;
begin
   result := FHandle.length;
end;

Procedure TQueue.Print;
begin
  writeln(FHandle.join(' - '));
end;

end.
    

Smart Pascal Code of XStack

We thank Nico Wouterse for sharing his code of XStack.

unit XStack;

interface

uses
  SmartCL.System, System.Types;

type
  TStack = class (TObject)
  public
    Constructor Create; virtual;
    Procedure   Push(Item: Variant);
    Function    Pop: Variant;
    Function    Peek: Variant;
    Function    Length: Variant;
    Procedure   Print;
    FHandle :   THandle;
  end;

implementation

Constructor TStack.Create;
begin
  inherited Create;
  FHandle := TVariant.CreateArray;
end;

Procedure TStack.Push(Item: Variant);
begin
  If Item.IsString then Item := "'" + Item + "'";
  FHandle.push(Item);
end;

Function TStack.Peek;
begin
  result := FHandle[FHandle.length-1];
end;

Function TStack.Pop: Variant;
begin
  result := FHandle.pop();
end;

Function TStack.Length:Variant;
begin
   result := FHandle.length;
end;

Procedure TStack.Print;
begin
  writeln(FHandle.join(' - '));
end;

end.    

XML Code of Form

We use the Android-HoloDark.css theme.

<SMART>
  <Form version="2" subversion="2">
    <Created>2016-12-03T14:16:26.359</Created>
    <Modified>2016-12-05T12:05:59.562</Modified>
    <object type="TW3Form">
      <Caption>W3Form</Caption>
      <Name>Form1</Name>
      <object type="TW3PaintBox">
        <Width>304</Width>
        <Height>232</Height>
        <Name>PB</Name>
      </object>
      <object type="TW3Memo">
        <Width>272</Width>
        <Top>240</Top>
        <Height>160</Height>
        <Name>W3Memo1</Name>
      </object>
      <object type="TW3ListBox">
        <Width>48</Width>
        <Top>30</Top>
        <Left>320</Left>
        <Height>272</Height>
        <Name>lbTarget</Name>
      </object>
      <object type="TW3Label">
        <Caption>Select Target</Caption>
        <Width>128</Width>
        <Left>304</Left>
        <Height>24</Height>
        <Name>W3Label1</Name>
      </object>
      <object type="TW3ListBox">
        <Width>48</Width>
        <Top>328</Top>
        <Left>320</Left>
        <Height>72</Height>
        <Name>lbSearchType</Name>
      </object>
      <object type="TW3Label">
        <Caption>Select Search Type</Caption>
        <Width>152</Width>
        <Top>304</Top>
        <Left>280</Left>
        <Height>24</Height>
        <Name>W3Label2</Name>
      </object>
    </object>
  </Form>
</SMART>

Programming - a skill for life!

Challenges from the DelphiForFun Website