GPWiki.org
GPWiki.org
It is currently Fri May 24, 2013 9:25 am

All times are UTC




Post new topic Reply to topic  [ 5 posts ] 
Author Message
PostPosted: Sun Dec 11, 2011 9:22 am 
Rookie

Joined: Sun Oct 16, 2011 6:45 pm
Posts: 4
I've been wondering what the better way to approach a certain way I've been coding, especially since I want to try a larger scale game.

Let's say you have a 2d grid for a game.

e.g. tile[1000][1000] (1000x1000 tiles = 1mil tiles)

Now I want to be able to have multiple objects (tables, chairs, potions, etc) on some tiles (note: sometimes 1 object, sometimes a multitude on the same tile).

The 2 ways I've always done it are either:

1. Add a variable (or array) to the tile object and store values in there.
The drawback I see to this is the waste of memory (variables/arrays for every tile even though they may not have objects).

2. Have a seperate list of objects/items and do a for...next loop to find any items for the tile being drawn.
The drawback I see to this is speed. The loop is run for every single tile. If the item list is small it's fine, but if there's say 2,000 items? 20,000 items?


Is there is a better way to do this? Or which of the above is the preferred method?

I was wondering if there's some way to "index" the list perhaps for faster finding of items? Databases such as MSSQL and MySQL and such have the index option to speed up queries, is there something similar that's possible to implement?


Top
 Profile  
 
PostPosted: Sun Dec 11, 2011 10:27 am 
Bytewise

Joined: Sun Oct 16, 2011 3:09 pm
Posts: 277
Location: Here (where else?)
hyarion wrote:
Let's say you have a 2d grid for a game.

e.g. tile[1000][1000] (1000x1000 tiles = 1mil tiles)
If every tile is used, this is fine. If you have a lot of 'holes', you may want to change storage of tiles.

hyarion wrote:
1. Add a variable (or array) to the tile object and store values in there.
The drawback I see to this is the waste of memory (variables/arrays for every tile even though they may not have objects).
I'd start with each object pointing to the next object in the room. That way, storage in a tile is reduced to a single pointer.
If most of the rooms have at least one object, this is fine.

The big advantage of this is that it is easy and fast to find objects at a tile.
If you have other queries, like 'give me all chairs', the above is very awkward.

hyarion wrote:
2. Have a seperate list of objects/items and do a for...next loop to find any items for the tile being drawn.
The drawback I see to this is speed. The loop is run for every single tile. If the item list is small it's fine, but if there's say 2,000 items? 20,000 items?
With 1 million tiles, only 20000 objects? That very few, I'd expect several 100 thousand tbh.

But you are right, you are wasting a lot of CPU time here :)

One simple step is to sort your objects, and use bisection. A second step is to sort them such that your order of tile drawing matches with the sort order, so you can 'walk' through the list objects in parallel with drawing tiles.

Another approach is to use hash your objects on position into a table. The basic idea is that the position becomes the key to find something (much like an index number in an array finds you the n-th item). There are a lot of different hashing forms. Read about them :)


hyarion wrote:
Is there is a better way to do this? Or which of the above is the preferred method?
Yes, it depends.

There is really no single-best solution. It depends on what questions you need answered, and how often. Getting objects based on position may cause a completely different data structure from queries on type of objects.

Some keywords to look for: lists, sets, maps/dictionaries/associative arrays, linked list, data structures, binary trees, searching, sorting
(not sure about the last two, but they are vast areas, Knuth wrote a complete book about each of them).

Another direction is to look at programming languages and their libraries. Many have the above data structures standard available.

hyarion wrote:
I was wondering if there's some way to "index" the list perhaps for faster finding of items? Databases such as MSSQL and MySQL and such have the index option to speed up queries, is there something similar that's possible to implement?
They do either hashing or some form of binary trees (or even n-ary trees).

Have fun exploring this area :D


Top
 Profile  
 
PostPosted: Sun Dec 11, 2011 10:29 am 
Dexterous Droid
User avatar

Joined: Wed Aug 18, 2004 7:40 pm
Posts: 3735
Location: South Africa
What you've described is the exact problem that exists. You have to choose.

You can have
1. a dense matrix (you have a value for every single tile in the world)
2. a sparse matrix (you store the info some other way, so as not to use up space for empty tiles)

Choose the method based on what will be happening. If almost all your tiles have no information, then it's a waste of space (and probably time). If they almost all have information, then it's not a waste of space and will save time.

I would say that in games, use a dense matrix - every tile is going to have information stored about it like tileset number, tile blending, visibility perhaps. So it works out OK.

_________________
Whatever the mind can conceive and believe, it can achieve


Top
 Profile  
 
PostPosted: Sun Dec 11, 2011 10:36 am 
Rookie

Joined: Sun Oct 16, 2011 6:45 pm
Posts: 4
Thank you, some nice information there :)


Top
 Profile  
 
PostPosted: Sun Dec 11, 2011 7:09 pm 
Source Code Swashbuckler
User avatar

Joined: Wed Nov 09, 2011 3:58 am
Posts: 199
Location: Brazil
I guess the best way is to create a class for maps and a list of objects. The class of maps will contain a 2D array of objects of the type cTile( inside the cTile, there will be FX and FY integer variables ).
Well, suppose a class "cTile", "cMap", and "cGameObject":
(just a pseudo-code)
Code:

class cGameObject
  public:
  FMySprite : cBitmap;
  FPositionX, FPositionY : Int;
end;

struct cTile
  FX, FY : Int;
  Solid : Boolean; // if you want;
end;

class cMap
  public:
  FMapTileSet : cBitmap; // the bitmap that contains the tileset;
  F2DMatrixTiles : array of array of cTile; // dynamic 2D arraw of cTile;
  FListOfObjects : array of cGameObject;
  procedure ReadMapFromTxtFile(FileName : string);
  procedure ReadObjectsFromTxtFile(FileName : string);
end;


Now, the implementation of the methods:
Code:
procedure cMap.ReadMapFromTxtFile(FileName : string);
begin
  // load the values of FX and FY of the tiles from the file.
  // for example, the tile[2,3] has FX = 3
  // and the tiles have 16x16 size
  // then, on the screen, it will be painted a cutted rectangle picture from the FMapTileSet
  // with these values (FX * 16, FY * 16, (FX * 16) + 16, (FY * 16) + 16)
  // them, FX and FY mean with tile will be painted on the screen.

  // to implement this function you will need I/O knowledge(read and write bytes in a file);
end;

procedure cMap.ReadObjectsFromTxtFile(FileName : string);
begin
  // Loop for, where for each object saved in the txt file, create a object cGameObject in the memory, in the matrix FListOfObjects;
  // also, read in the file, the position of the object and put it in FPositonX and FPostionY;
  // this way, objects and tiles has no link between each other, just collision, if you want, for example;

  // to implement this function you will need I/O knowledge(read and write bytes in a file);
end;

procedure DrawMapAndObjects(Map: cMap);
begin
  // FIRST, DRAW THE TILES:
  // Draw only the tiles visible in the screen, don't lose time drawing not visible tiles;
  // It will not affect the game logic, if a object collide in a not-visible tile(out of the screen), it will
  // use the variable FSolid of cTile to know if the tile is Solid, the cGameObject will not know if the
  // tile is solid by the drawn image of the tile.
 
  //SECOND, DRAW OBJECTS
  // The same, draw only the visible ones. Remember, the objects are CREATED in the
  // ReadObjectsFromTxtFile procedure, but they will not be necessarily drawn in the screen, but
  // they MUST be created;
end;

// In the MAIN procedure/function

procedure Main;
var
  FCurrentMap : cMap;
begin
  // do initialization stuff

  // Initialize the map
  FCurrentMap := cMap.Create;
 
  FCurrentMap.ReadMapFromTxtFile('map001.txt'); // Create tiles;
  FCurrentMap.ReadObjectsFromTxtFile('map001.txt');  // Create objects;

  DrawMapAndObjects(FCurrentMap); // Draw visible tiles and visible objects
end;

_________________
"Life finds a way." - Ian Malcolm
My WebBlog: PixelDeveloper
English is not my native language, so excuse me for any writing mistakes.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 5 posts ] 

All times are UTC


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum

Search for:
Jump to:  
cron
Powered by phpBB® Forum Software © phpBB Group