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:
Code:
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 (Data <> Nil) And (DataMode = dmIterateData) Then
WriteLn(Key,': ',TTile(Data).SomeData);
End;
Procedure TTilesIterator.IterateTiles(AHashTable: THashTable);
Begin
AHashTable.OnData := OnData;
AHashTable.IterateData;
End;
begin
TilesIterator := TTilesIterator.Create;
HashTable := THashTable.Create;
Tile1 := TTile.Create;
Tile1.SomeData := 1;
Tile2 := TTile.Create;
Tile2.SomeData := 2;
// add tiles to (1,1) and (1,2)
// if any data is already using this key, then the old data gets replaced with the new data
HashTable.AddData(GridCoordToKey(1,1),Tile1);
HashTable.AddData(GridCoordToKey(1,2),Tile2);
// get tile at (1,1)
If HashTable.GetData(GridCoordToKey(1,1),Pointer(Tile)) Then
WriteLn(Tile.SomeData);
WriteLn;
// iterate through all tiles in the hash table
TilesIterator.IterateTiles(HashTable);
// delete tile at (1,1)
HashTable.DeleteData(GridCoordToKey(1,1));
ReadLn;
HashTable.Free;
Tile1.Free;
Tile2.Free;
TilesIterator.Free;
Code:
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 (x <> 0) then
Result := Result xor (x shr 24);
Result := Result and (not x);
end;
end;
constructor THashTable.Create(AHashTableLength: LongWord = 383);
begin
inherited Create;
FHashMode := hmNormal;
FOnData := nil;
FHashTableLength := AHashTableLength;
SetLength(FHashTable,FHashTableLength);
SetHashFunction(SimpleHash);
// make all the hash table pointers to nil
FillChar(FHashTable[0],SizeOf(FHashTable),0);
end;
destructor THashTable.Destroy;
begin
Clear;
inherited Destroy;
end;
procedure THashTable.SetHashFunction(AHashFunction: THashFunction);
begin
if(Assigned(AHashFunction))then
FHashFunction := AHashFunction;
end;
procedure THashTable.SetHashMode(AHashMode: THashMode);
begin
if(FNumOfItems = 0)then
FHashMode := AHashMode;
end;
function THashTable.GetNode(Key: AnsiString; var Index: THashIndex): PHashTableNode;
begin
Result := Nil;
if(FHashMode = hmTesting)then
Exit;
Index := FHashFunction(Key) mod FHashTableLength;
Result := FHashTable[Index];
while(Result <> nil)do
begin
if(Result^.Key = Key)then
begin
Break;
end;
Result := Result^.NextNode;
end;
end;
function THashTable.GetData(Key: AnsiString; var Data: Pointer): Boolean;
var
Node: PHashTableNode;
Index: THashIndex;
begin
Result := False;
Node := GetNode(Key,Index);
if(Node <> nil)then
begin
Data := Node^.Data;
Result := True;
end;
end;
procedure THashTable.DeleteNode(var Node: PHashTableNode);
begin
if(Node = nil)then
Exit;
while(Node^.NextNode <> nil)do
begin
DeleteNode(Node^.NextNode);
end;
if Assigned(FOnData) then
FOnData(Node^.Key,Node^.Data,dmDeleteData);
Dec(FNumOfItems);
Dispose(Node);
Node := nil;
end;
procedure THashTable.Clear;
var
i: Integer;
begin
if(FHashMode = hmTesting)then
Exit;
for i := Low(FHashTable) to High(FHashTable) do
begin
DeleteNode(FHashTable[i]);
end;
FNumOfItems := 0;
end;
procedure THashTable.IterateData;
var
i: Integer;
Node: PHashTableNode;
begin
for i := Low(FHashTable) to High(FHashTable) do
begin
Node := FHashTable[i];
if(FHashMode = hmTesting)then
begin
if Assigned(FOnData) then
FOnData('',Pointer(Node),dmTestingData);
end
else
while(Node <> nil)do
begin
if Assigned(FOnData) then
FOnData(Node^.Key,Node^.Data,dmIterateData);
Node := Node^.NextNode;
end;
end;
end;
procedure THashTable.AddData(Key: AnsiString; Data: Pointer);
var
Index: THashIndex;
Node: PHashTableNode;
begin
Node := GetNode(Key,Index);
if(FHashMode = hmTesting)then
begin
Inc(FNumOfItems);
FHashTable[Index] := Pointer(Integer(FHashTable[Index])+1);
Exit;
end;
if(Node = nil)then
// not found, so create a new Node and add to the beginning of the
// linked list at the hash table index
begin
Inc(FNumOfItems);
New(Node);
Node^.Key := Key;
Node^.PriorNode := nil;
Node^.NextNode := FHashTable[Index];
Node^.Data := Data;
FHashTable[Index] := Node;
if(Node^.NextNode <> nil)then
Node^.NextNode^.PriorNode := Node;
end
else
Node^.Data := Data;
end;
function THashTable.DeleteData(Key: AnsiString): Boolean;
var
Index: THashIndex;
Node: PHashTableNode;
begin
Result := False;
if(FHashMode = hmTesting)then
Exit;
Node := GetNode(Key,Index);
if(Node <> nil)then
begin
Result := True;
if(Node^.PriorNode = nil)and(Node^.NextNode = nil)then
// node being deleted is at the beginning of the list...
begin
FHashTable[Index] := nil;
end
else
if(Node^.PriorNode <> nil)and(Node^.NextNode <> nil)then
// node being deleted is somewhere in the middle of the list...
begin
Node^.PriorNode^.NextNode := Node^.NextNode;
Node^.NextNode^.PriorNode := Node^.PriorNode;
end
else
if(Node^.PriorNode = nil)and(Node^.NextNode <> nil)then
// node being deleted is at the beginning of the list...
begin
Node^.NextNode^.PriorNode := nil;
FHashTable[Index] := Node^.NextNode;
end
else
if(Node^.PriorNode <> nil)and(Node^.NextNode = nil)then
// node being deleted is at the end of the list...
begin
Node^.NextNode^.PriorNode := nil;
end;
if Assigned(FOnData) then
FOnData(Node^.Key,Node^.Data,dmDeleteData);
Dec(FNumOfItems);
Finalize(Node^);
Dispose(Node);
end;
end;
end.
cheers,
Paul.
Bookmarks