List in stead of a 2-D array?

[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.