PDA

View Full Version : List in stead of a 2-D array?



Smotsholle
30-11-2006, 12:05 AM
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:
http://webserv.nhl.nl/~kampe001/delphisonne2.jpg

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
30-11-2006, 01:24 AM
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&#40;const Key&#58; AnsiString&#41;&#58; THashIndex;

THashMode = &#40;hmTesting,hmNormal&#41;;
TDataMode = &#40;dmDeleteData,dmIterateData,dmTestingData&#41;;

TOnData = procedure&#40;const Key&#58; AnsiString; var Data&#58; Pointer; DataMode&#58; TDataMode&#41; of object;

PHashTableNode = ^THashTableNode;
THashTableNode = packed record
Key&#58; AnsiString;
Data&#58; Pointer;
PriorNode&#58; PHashTableNode;
NextNode&#58; PHashTableNode;
end;

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

procedure SetHashFunction&#40;AHashFunction&#58; THashFunction&#41;;

procedure Clear;
procedure IterateData;
procedure AddData&#40;Key&#58; AnsiString; Data&#58; Pointer&#41;;
function GetData&#40;Key&#58; AnsiString; var Data&#58; Pointer&#41;&#58; Boolean;
function DeleteData&#40;Key&#58; AnsiString&#41;&#58; Boolean;

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

function SimpleHash&#40;const Key&#58; AnsiString&#41;&#58; THashIndex;
function SimpleXORHash&#40;const Key&#58; AnsiString&#41;&#58; THashIndex;
function ElfHash&#40;const Key&#58; AnsiString&#41;&#58; THashIndex;

implementation

function SimpleHash&#40;const Key&#58; AnsiString&#41;&#58; THashIndex;
const
Multiplier = 65599; // a prime number
var
i&#58; Integer;
begin
Result &#58;= 0;

for i &#58;= 1 to Length&#40;Key&#41; do
begin
Result &#58;= Result * Multiplier + Ord&#40;Key&#91;i&#93;&#41;;
end;
end;

function SimpleXORHash&#40;const Key&#58; AnsiString&#41;&#58; THashIndex;
const
Multiplier = 65599; // a prime number
var
i&#58; Integer;
begin
Result &#58;= 0;

for i &#58;= 1 to Length&#40;Key&#41; do
begin
Result &#58;= Result * Multiplier xor Ord&#40;Key&#91;i&#93;&#41;;
end;
end;

function ElfHash&#40;const Key&#58; AnsiString&#41;&#58; THashIndex;
var
i, x&#58; Integer;
begin
Result &#58;= 0;
for i &#58;= 1 to Length&#40;Key&#41; do
begin
Result &#58;= &#40;Result shl 4&#41; + Ord&#40;Key&#91;i&#93;&#41;;
x &#58;= 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
30-11-2006, 07:52 AM
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
30-11-2006, 08:00 AM
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
30-11-2006, 08:45 AM
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
30-11-2006, 11:40 AM
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&#58; array of array of Tclass;

begin

setlength&#40;stuff, 200, 200&#41;;

and so on...

jdarling
30-11-2006, 01:20 PM
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:
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;

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):
function OppositeDir(ADir:Integer):Integer;
begin
OppositeDir := ExitCount-ADir;
end;
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
30-11-2006, 01:50 PM
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. (http://www.eonclash.com/PGD/HashTable.zip)

savage
30-11-2006, 02:38 PM
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
30-11-2006, 02:42 PM
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.

tux
30-11-2006, 03:23 PM
what about a list for the currently placed tiles. each item in the list only holds info on that tile in the game, so if i have placed 70 tiles i have 70 items in the list (0 to 69).

the only bad thing is if you then want to select a tile that is currently placed, you will have to loop through all the tiles (could get slow). so basically you would have something like this:



TTile = class/record etc
Image: TImage?;
DrawX: integer;
DrawY: Integer;

Smotsholle
30-11-2006, 04:56 PM
This idea is simple, but doesn't sound half bad, actually.

I allready have an array of all the tiles which are to be placed in the game. In stead of making another classlist point to the item allready in my array, I can just change a boolean (Placed := True) and change the X and Y coordinates.

It might become a bit tricky later on when I do have to do a recursive function on all the tiles, but this may suffice, that or I'll just stick with the huge 2d array.

tux
30-11-2006, 06:10 PM
Yes, each method has a downside.

With the memory pointer one (a tile with pointers to north, south, east, west) it can become quite complex if you just want to loop through each tile (you could get into an infinate loop if your not carefull, or you could miss a tile).

But with the TList, you dont have the "what tile is next to this one" without the extra overhead of also storing a north, south, east, west pointer. Well i guess you could loop through the list if you know what the X, Y of the tile should be... i should stop thinking out loud

cragwolf
30-11-2006, 08:54 PM
Yes, FPC has TFPHashTable, in the contnrs unit. You'll have to read the source to figure out how to use it, as there's no documentation.

paul_nicholls
30-11-2006, 09:07 PM
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 [url=http://www.eonclash.com/PGD/HashTable.zip]download ]

Nice work :)
cheers,
Paul.

Smotsholle
30-11-2006, 10:35 PM
I really like that hashtable thingy.

Not really applicable for this purpose to my taste, but handy nonetheless. I'll certainly keep this in mind and I bet it comes in handy in the future. Downloaded and stored it in case this thread dies in the future.

jdarling
01-12-2006, 03:32 PM
Ok, I got to playing around a bit last night, and worked up a sample of using DisplayLists and Pointer Records. Its a bit rough in the comments area, but it works quite well. Basically you can create any number of "rooms" you want in any direction defined. There very well may be an error, but I haven't found any when playing with it. Built in Lazarus, due to the use of windows controls, but could be converted to Delphi easy enough.

Even though I'm not using quick graphics (standard draw routines used), its pretty snappy. Graphics taken from Renears Tiles and are packaged with it. The TiledImage class may be of interest to some, as well as a few other things inside the zip file.

Download here (http://www.eonclash.com/PGD/DynamicTiles.zip)