List in stead of a 2-D array?

[Smotsholle]

Just to updat my knowledge I'm trying to create a boardgame in delphi. For those of you who know it, It's called carcassonne.

The starts out with a single square tile. Basically the player places a new tile adjecent to that tile and this process repeats itself until the game is out of tiles. I think you can understand the game field keeps on growing and I can never know how large the gamefield will become.

Here's an image to illustrate the gamefield:


The O-tiles show you where you're allowed to place the tile shown in the upper right corner.
The X-tiles show you where you can't place 'em.

I know of 2 ways to store the playfield:
1. I create a huge 2D array of TTile in which I store the tile info in a class.
2. I create a pointer to the starttile and the this tile has 4 pointers in it pointing north,east,south and west to an adjecent TTile object. This would create a web of intertwined TTile objects.
Problem with this is finding a specific tile and drawing it on a DrawGrid (Which I used for this).

But there must be a 3rd way of implementing this. I was thinking of some sort of TList, but in this case 2 dimensional. This list would expand as I put more tiles in it.

For drawing purposes it would be the easiest to just call TileList[x,y] to get a specific tile. Is there any way this can be done or should I just stick with option 1 or 2?

Opt 1. High memory storage, Quick tile search.
Opt 2. Low memory storage, Slow & complex tile search.

[paul_nicholls]

Perhaps you could use some sort of hash table object that stores the tile using the x and y coordinate as the key?

This should be really fast, and use a lot less memory than method 1, and also be much easier than method 2, as you can just see if there is a tile object at (x-1,y),(x+1,y), etc. to check for adjacent tiles...

I have a unit for a HashTable class that you can use (can't remember where I got it from, could have even converted it from C++ or something). It seems to find items really fast which is great!

How to use:

Type
    TTile = Class
       SomeData: Integer;
    End;

    TTilesIterator = Class
    Private
        Procedure OnData(const Key: AnsiString; var Data: Pointer; DataMode: TDataMode);
    Public
        Procedure IterateTiles(AHashTable: THashTable);
    End;
Var
    HashTable     : THashTable;
    Tile1         : TTile;
    Tile2         : TTile;
    Tile          : TTile;
    TilesIterator : TTilesIterator;
    
Function GridCoordToKey(x,y: Integer): AnsiString;
Begin
    Result := Format('%d,%d',[x,y]);
End;
Procedure TTilesIterator.OnData(const Key: AnsiString; var Data: Pointer; DataMode: TDataMode);
Begin
    If &#40;Data <> Nil&#41; And &#40;DataMode = dmIterateData&#41; Then
        WriteLn&#40;Key,'&#58; ',TTile&#40;Data&#41;.SomeData&#41;;
End;
Procedure TTilesIterator.IterateTiles&#40;AHashTable&#58; THashTable&#41;;
Begin
    AHashTable.OnData &#58;= OnData;
    AHashTable.IterateData;
End;
begin
    TilesIterator &#58;= TTilesIterator.Create;

    HashTable &#58;= THashTable.Create;
    Tile1 &#58;= TTile.Create;
    Tile1.SomeData &#58;= 1;
    Tile2 &#58;= TTile.Create;
    Tile2.SomeData &#58;= 2;

    //  add tiles to &#40;1,1&#41; and &#40;1,2&#41;
    //  if any data is already using this key, then the old data gets replaced with the new data
    HashTable.AddData&#40;GridCoordToKey&#40;1,1&#41;,Tile1&#41;;
    HashTable.AddData&#40;GridCoordToKey&#40;1,2&#41;,Tile2&#41;;

    //  get tile at &#40;1,1&#41;
    If HashTable.GetData&#40;GridCoordToKey&#40;1,1&#41;,Pointer&#40;Tile&#41;&#41; Then
        WriteLn&#40;Tile.SomeData&#41;;
    WriteLn;

    //  iterate through all tiles in the hash table
    TilesIterator.IterateTiles&#40;HashTable&#41;;

    //  delete tile at &#40;1,1&#41;
    HashTable.DeleteData&#40;GridCoordToKey&#40;1,1&#41;&#41;;
    ReadLn;
    HashTable.Free;
    Tile1.Free;
    Tile2.Free;
    TilesIterator.Free;

unit HashTableUnit;

interface

type
  THashIndex = LongWord;
  THashFunction = function(const Key: AnsiString): THashIndex;

  THashMode = (hmTesting,hmNormal);
  TDataMode = (dmDeleteData,dmIterateData,dmTestingData);

  TOnData = procedure(const Key: AnsiString; var Data: Pointer; DataMode: TDataMode) of object;

  PHashTableNode = ^THashTableNode;
  THashTableNode = packed record
    Key: AnsiString;
    Data: Pointer;
    PriorNode: PHashTableNode;
    NextNode: PHashTableNode;
  end;

  THashTable = class
  private
    FNumOfItems: Integer;
    FHashMode: THashMode;
    FOnData: TOnData;
    FHashTableLength: Integer;
    FHashFunction: THashFunction;
    FHashTable: array of PHashTableNode;
  protected
    procedure SetHashMode(AHashMode: THashMode);
    function GetNode(Key: AnsiString; var Index: THashIndex): PHashTableNode;
    procedure DeleteNode(var Node: PHashTableNode);
  public
    constructor Create(AHashTableLength: LongWord = 383);
    destructor Destroy; override;

    procedure SetHashFunction(AHashFunction: THashFunction);

    procedure Clear;
    procedure IterateData;
    procedure AddData(Key: AnsiString; Data: Pointer);
    function GetData(Key: AnsiString; var Data: Pointer): Boolean;
    function DeleteData(Key: AnsiString): Boolean;

    property HashTableLength: Integer read FHashTableLength;
    property NumOfItems: Integer read FNumOfItems;
    property HashMode: THashMode read FHashMode write SetHashMode;
    property OnData: TOnData read FOnData write FOnData;
  end;

function SimpleHash(const Key: AnsiString): THashIndex;
function SimpleXORHash(const Key: AnsiString): THashIndex;
function ElfHash(const Key: AnsiString): THashIndex;

implementation

function SimpleHash(const Key: AnsiString): THashIndex;
const
  Multiplier = 65599; // a prime number
var
  i: Integer;
begin
  Result := 0;

  for i := 1 to Length(Key) do
  begin
    Result := Result * Multiplier + Ord(Key[i]);
  end;
end;

function SimpleXORHash(const Key: AnsiString): THashIndex;
const
  Multiplier = 65599; // a prime number
var
  i: Integer;
begin
  Result := 0;

  for i := 1 to Length(Key) do
  begin
    Result := Result * Multiplier xor Ord(Key[i]);
  end;
end;

function ElfHash(const Key: AnsiString): THashIndex;
var
  i, x: Integer;
begin
  Result := 0;
  for i := 1 to Length(Key) do
  begin
    Result := (Result shl 4) + Ord(Key[i]);
    x := Result and $F0000000;
    if &#40;x <> 0&#41; then
      Result &#58;= Result xor &#40;x shr 24&#41;;
    Result &#58;= Result and &#40;not x&#41;;
  end;
end;

constructor THashTable.Create&#40;AHashTableLength&#58; LongWord = 383&#41;;
begin
  inherited Create;

  FHashMode &#58;= hmNormal;
  FOnData &#58;= nil;
  FHashTableLength &#58;= AHashTableLength;

  SetLength&#40;FHashTable,FHashTableLength&#41;;

  SetHashFunction&#40;SimpleHash&#41;;

  //  make all the hash table pointers to nil
  FillChar&#40;FHashTable&#91;0&#93;,SizeOf&#40;FHashTable&#41;,0&#41;;
end;

destructor THashTable.Destroy;
begin
  Clear;

  inherited Destroy;
end;

procedure THashTable.SetHashFunction&#40;AHashFunction&#58; THashFunction&#41;;
begin
  if&#40;Assigned&#40;AHashFunction&#41;&#41;then
    FHashFunction &#58;= AHashFunction;
end;

procedure THashTable.SetHashMode&#40;AHashMode&#58; THashMode&#41;;
begin
  if&#40;FNumOfItems = 0&#41;then
    FHashMode &#58;= AHashMode;
end;

function THashTable.GetNode&#40;Key&#58; AnsiString; var Index&#58; THashIndex&#41;&#58; PHashTableNode;
begin
  Result &#58;= Nil;

  if&#40;FHashMode = hmTesting&#41;then
    Exit;

  Index &#58;= FHashFunction&#40;Key&#41; mod FHashTableLength;

  Result &#58;=  FHashTable&#91;Index&#93;;

  while&#40;Result <> nil&#41;do
  begin
    if&#40;Result^.Key = Key&#41;then
    begin
      Break;
    end;

    Result &#58;= Result^.NextNode;
  end;
end;

function THashTable.GetData&#40;Key&#58; AnsiString; var Data&#58; Pointer&#41;&#58; Boolean;
var
  Node&#58; PHashTableNode;
  Index&#58; THashIndex;
begin
  Result &#58;= False;

  Node &#58;=  GetNode&#40;Key,Index&#41;;

  if&#40;Node <> nil&#41;then
  begin
    Data &#58;= Node^.Data;
    Result &#58;= True;
  end;
end;

procedure THashTable.DeleteNode&#40;var Node&#58; PHashTableNode&#41;;
begin
  if&#40;Node = nil&#41;then
    Exit;

  while&#40;Node^.NextNode <> nil&#41;do
  begin
    DeleteNode&#40;Node^.NextNode&#41;;
  end;

  if Assigned&#40;FOnData&#41; then
    FOnData&#40;Node^.Key,Node^.Data,dmDeleteData&#41;;

  Dec&#40;FNumOfItems&#41;;
  
  Dispose&#40;Node&#41;;
  Node &#58;= nil;
end;

procedure THashTable.Clear;
var
  i&#58; Integer;
begin
  if&#40;FHashMode = hmTesting&#41;then
    Exit;

  for i &#58;= Low&#40;FHashTable&#41; to High&#40;FHashTable&#41; do
  begin
    DeleteNode&#40;FHashTable&#91;i&#93;&#41;;
  end;

  FNumOfItems &#58;= 0;
end;

procedure THashTable.IterateData;
var
  i&#58; Integer;
  Node&#58; PHashTableNode;
begin
  for i &#58;= Low&#40;FHashTable&#41; to High&#40;FHashTable&#41; do
  begin
    Node &#58;= FHashTable&#91;i&#93;;

    if&#40;FHashMode = hmTesting&#41;then
    begin
      if Assigned&#40;FOnData&#41; then
        FOnData&#40;'',Pointer&#40;Node&#41;,dmTestingData&#41;;
    end
    else
    while&#40;Node <> nil&#41;do
    begin
      if Assigned&#40;FOnData&#41; then
        FOnData&#40;Node^.Key,Node^.Data,dmIterateData&#41;;

      Node &#58;= Node^.NextNode;
    end;
  end;
end;

procedure THashTable.AddData&#40;Key&#58; AnsiString; Data&#58; Pointer&#41;;
var
  Index&#58; THashIndex;
  Node&#58; PHashTableNode;
begin
  Node &#58;= GetNode&#40;Key,Index&#41;;

  if&#40;FHashMode = hmTesting&#41;then
  begin
    Inc&#40;FNumOfItems&#41;;
    FHashTable&#91;Index&#93; &#58;= Pointer&#40;Integer&#40;FHashTable&#91;Index&#93;&#41;+1&#41;;
    Exit;
  end;

  if&#40;Node = nil&#41;then
  //  not found, so create a new Node and add to the beginning of the
  //  linked list at the hash table index
  begin
    Inc&#40;FNumOfItems&#41;;
    
    New&#40;Node&#41;;

    Node^.Key &#58;= Key;
    Node^.PriorNode &#58;= nil;
    Node^.NextNode &#58;= FHashTable&#91;Index&#93;;
    Node^.Data &#58;= Data;
    FHashTable&#91;Index&#93; &#58;= Node;

    if&#40;Node^.NextNode <> nil&#41;then
      Node^.NextNode^.PriorNode &#58;= Node;
  end
  else
    Node^.Data &#58;= Data;
end;

function THashTable.DeleteData&#40;Key&#58; AnsiString&#41;&#58; Boolean;
var
  Index&#58; THashIndex;
  Node&#58; PHashTableNode;
begin
  Result &#58;= False;

  if&#40;FHashMode = hmTesting&#41;then
    Exit;

  Node &#58;= GetNode&#40;Key,Index&#41;;

  if&#40;Node <> nil&#41;then
  begin
    Result &#58;= True;

    if&#40;Node^.PriorNode = nil&#41;and&#40;Node^.NextNode = nil&#41;then
    //  node being deleted is at the beginning of the list...
    begin
      FHashTable&#91;Index&#93; &#58;= nil;
    end
    else
    if&#40;Node^.PriorNode <> nil&#41;and&#40;Node^.NextNode <> nil&#41;then
    //  node being deleted is somewhere in the middle of the list...
    begin
      Node^.PriorNode^.NextNode &#58;= Node^.NextNode;
      Node^.NextNode^.PriorNode &#58;= Node^.PriorNode;
    end
    else
    if&#40;Node^.PriorNode = nil&#41;and&#40;Node^.NextNode <> nil&#41;then
    //  node being deleted is at the beginning of the list...
    begin
      Node^.NextNode^.PriorNode &#58;= nil;

      FHashTable&#91;Index&#93; &#58;= Node^.NextNode;
    end
    else
    if&#40;Node^.PriorNode <> nil&#41;and&#40;Node^.NextNode = nil&#41;then
    //  node being deleted is at the end of the list...
    begin
      Node^.NextNode^.PriorNode &#58;= nil;
    end;

    if Assigned&#40;FOnData&#41; then
      FOnData&#40;Node^.Key,Node^.Data,dmDeleteData&#41;;

    Dec&#40;FNumOfItems&#41;;

    Finalize&#40;Node^&#41;;
    Dispose&#40;Node&#41;;
  end;
end;

end.

cheers,
Paul.

[cairnswm]

How about using StringGrid instead of DrawGrid and store the tile in each Cell's Data property?

And you can do the same owner draw functions in StringGrid as you can in Draw Grid.

[Traveler]

Hey, that looks like a pretty cool unit!

(...) process repeats itself until the game is out of tiles

(...) I can never know how large the gamefield will become.

These two sentences confuse me a bit. Is the board region unlimited or is it limited by the number of tiles?

[cairnswm]

Each turn a player places a tile at the edge of the current tiles. This means (theoretically) the board could grow in a single long line.

So you never really know where the edge of the board starts or ends except by checking the size of the board currently.
----

In a Grid the cells could be moved as the player places a new tile.

[JernejL]

1. I create a huge 2D array of TTile in which I store the tile info in a class.

Why not just use a 2D dynamic array?

var
stuff: array of array of Tclass;

begin

setlength(stuff, 200, 200);

and so on...

[jdarling]

Well, personally I would use pointer records. For example, you know that rooms can be N, S, E, and W of the origion point. So design a record around it:
[pascal]const
ExitNorth = 0;
ExitEast = 1;
ExitWest = 2;
ExitSouth = 3;
ExitCount = 4;
type
PGameTile=^TGameTile;
TGameTile=packed record
TileIndex : Integer;
Adjacent : Array[0..ExitCount] of PGameTile;
end;
[/pascal]
Then define a root tile for the game, each time a move is made allocate a new game tile, set its adjacent room pointers as appropriate (btw; I laid out the exits and count that way for a reason, here is a fast way to find the opposite dir):
[pascal]function OppositeDir(ADir:Integer):Integer;
begin
OppositeDir := ExitCount-ADir;
end;[/pascal]
To release the rooms, simply walk each room, releasing its exit rooms. On Draw, start at your root room, and draw the rooms leading each direction if they are not nil. If they are nil, then calculate if its a valid room and mark appropriately.

Hows that for a 3rd option for you? It gives the best of both worlds, your not allocating any more memory then you need, and it can scale within the available memory of the system. If you really wanted to you could store the structure to a TFileStream and have loading/saving of game states.

[jdarling]

Also, for anyone that doesn't care to copy/paste and edit to get the above hash table stuff to work, I took the time to get it to compile in FPC. Quite nice, so you don't have to duplicate efforts here is a download link.

[savage]

I think Delphi 7 onwards have a THashedList object list IIRC. I would assume that FreePascal's libraries have something similar, don't they?

[Smotsholle]

The current inefficient version uses the following:

gamegrid: array[-tc..tc,-tc..tc] of TTile;

The starter tile is placed on [0,0] and since there are "tc+1" tiles in total I used this sollution, but of course this may be inefficient.

I don't really know if this actually takes up this much memory because most of these tiles will eternally remain NIL, so they shouldn't take up any memory, but on the other hand, the pointers may (not so well versed in computer memory usage).

tilelist: array[1..tc] of TTile;

This is the deck from which the player draws a tile each turn. Placing the tile simply lets the gamegrid point to this tile and then remove it from the tilelist.

The tile image is loaded from a BMP file and placed in a TBitmap within the TTile class. Each tile has it's own bitmap. This could mean I store the same bitmap twice, but on the other hand, the Tile can be rotated over a 90 degree angle so this would mean the TBitmap can turn out 4 different ways for each tile type.

I'm just wondering. Is this way truly inefficient. It could be acceptable because many items in the gamegrid are NIL.



About the suggestions:
- StringGrid in stead of DrawGrid:
I'm most comfortable storing the data in a seperate class. Maybe I'll make an OpenGL version later on. I don't know if it supports bumpmapping, but Making an extremely high bumpmap so cities and other buildings appear to have height would be cool. So I don't want to link to this grid.

- Hash table:
Don't know anything about hashtables yet, but I wouldn't mind learning a thing or two about that, so if it turns out to be the best option, I'll certainly put in the effort to use that.

- Pointer records:
This sounds like a good plan and kind of reminds me of Idea #2. I agree this would be the most memory friendly Idea, but what if I want to draw all tiles on a grid?

- Dynamic array:
In my screenshot you can see there are a lot of empty tiles in an array such as this one. Which brings me back to my question. Do nil pointers take up virtually no space?

The basic game has 72 tiles (one is placed by default, so 71 are left). In the worst case scenario the tiles could be placed in an L shape making it a grid size of 36x37 tiles. This would be a grid of 1332 tiles using the dynamic array. 1332-72 equals 1260 nil pointers.
Since carcassonne became more and more popular over the years lots of expansions have been made. With all current expansions added I don't think I would be surprised to get over 200 tiles in total (and trust me, the true fans play in this manor (imagine the complexity then)). I'm not even counting the unofficial expansions now.