Sign in to follow this  

item storage on a tile map

This topic is 4271 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hey, I've not really been working on game developing for long. I'm more of an application programmer, so the whole concept of keeping speed as your prime requirement is a bit foreign to me. :) Anyways: At the moment I'm working on a way to store units/items on a tile map. The first way I tried was the one that was most obvious to me at the time, keeping the items in an array. Clearly a bad idea as the speed took quite a hit when searching through every item in the game to find out if it should be rendered, and where, whenever the map moved. I then moved on to an associative array containing.. arrays. It works fairly well, in that I can just check for the map tiles association to find out what's at that tile. However it was a bit messy, and required more code than I really wanted to write for movement. My current method is having every tile on the map keep a list of items at its position. Compared to the other methods it's faster, and it's easier to keep track of. But on the other hand, I'm not too keen on keeping a list of item references on map squares. It doesn't feel quite fitting. What I'm wonder is, are there methods about for doing this that are fast and easy to manage? I can use the current method i have just fine, but it doesn't feel exactly up to par.. Which I would quite prefer to be. Cheers, JD.

Share this post


Link to post
Share on other sites
The associateve array does not have to be a lot of code, perhaps only 1 line:

typedef std::map< Point2D, ObjectList > ObjectMap;

The other way, having an "ObjectList" per tile probably does not "feel" right because of the overhead of "one list per tile". Do the maths to see what you get: 16 bytes (say) per tile * 1000 * 1000 tiles = 16Meg. This will be very fast, but can you spare the memory ? Possibly. Also it may not feel right to mix your (static) tile data with (dynamic) object data.

A third way would be to have a ObjectList for every N*N tiles. So you get your potential object list for a given tile, and then search through this list for objects that exactly match your tile.

You can combine methods 2 and 3 by having N variable (#define, template, const int, whatever). In the case of "N=1" you are back to where you started, but possibly your implementation would split the tile array data from your object array data (this is a good thing in terms of "separation").

Here is where good code design will let you try/interchange these methods. First define you interface:


// Assuming your Object class has a "GetPosition" function/variable
class ObjectMap
{
virtual void SetMapSize(int inWidth,int inHeight)=0;
...
virtual void AddObject(Object *inObj)=0;
virtual void MoveObject(Object *inObj,Point2D inNewPosition)=0;
virtual void GetObjectsAtPosition(Point2D inPosition, ObjectList &outList)=0;
...
};



Here you have no idea which of the methods was used underneath - but that is the point !

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
maybe you would consider making the tile as a class or a struct, and include a pointer to item (if the item is generic) or item_id (if the item is unique, so that you can lookup the item from your database and put it there), or even a pointer to a linked list if you decided to have multiple items on the tile. You then use an array of the said class or struct to build the tiles/maps.

-geekman-

Share this post


Link to post
Share on other sites
Quote:
Original post by Huge_
The associateve array does not have to be a lot of code, perhaps only 1 line:

typedef std::map< Point2D, ObjectList > ObjectMap;

The other way, having an "ObjectList" per tile probably does not "feel" right because of the overhead of "one list per tile". Do the maths to see what you get: 16 bytes (say) per tile * 1000 * 1000 tiles = 16Meg. This will be very fast, but can you spare the memory ? Possibly. Also it may not feel right to mix your (static) tile data with (dynamic) object data.

A third way would be to have a ObjectList for every N*N tiles. So you get your potential object list for a given tile, and then search through this list for objects that exactly match your tile.

You can combine methods 2 and 3 by having N variable (#define, template, const int, whatever). In the case of "N=1" you are back to where you started, but possibly your implementation would split the tile array data from your object array data (this is a good thing in terms of "separation").

Here is where good code design will let you try/interchange these methods. First define you interface:

*** Source Snippet Removed ***

Here you have no idea which of the methods was used underneath - but that is the point !




Well the list in itself wasn't alot of code, the issue is organizing movement and all with it. Plus having a list per tile was obviously not something which fulfilled my wildest hopes and dreams.
I don't really know if the third way is worth the calculation time. If you have a list for 3x3 tiles, for example, and there's an item right at the center tile.. That item will be checked 9 times instead of once. I suppose I could run some benches to it to see how it matches up. Ofcourse if the world is largely empty, then you'd benefit quite a bit from doing it that way.


Quote:
Original post by TheKnight
This is not yet for my brains but couldn't you use a three dimentional array and use the array coordinents to define what object goes on the tile?


That was.. kindof.. the "solution" I was running at the time of my posting. However, it produces the maximum amount of overhead since it will have to have an array set for every tile in the game. Also, you don't want to go into three dimensional arrays so lightly, every dimension you add will increase the memory consumed by quite alot.
For the map, you can do fine with a single array.


Quote:
Original post by Anonymous Poster
maybe you would consider making the tile as a class or a struct, and include a pointer to item (if the item is generic) or item_id (if the item is unique, so that you can lookup the item from your database and put it there), or even a pointer to a linked list if you decided to have multiple items on the tile. You then use an array of the said class or struct to build the tiles/maps.

-geekman-


I've written this implementation as well (the linked list), and it was fairly fast and i didn't have much trouble with it.. Just a hint slower than actually placing all the items in an array inside the tile. I'm still considering using it, not sure though.


Thanks for the advice everyone,
Looks like it'll take a while before I can make up my mind. ;)

JD.

Share this post


Link to post
Share on other sites
A std::multimap<location, datum>?
-- nice and quick. Can have more than one thing at a location this way.

A quadtree?
-- Provides space-local storage
-- The final "leaves" may be either tiles or a fixed size grid of tiles

Share this post


Link to post
Share on other sites

This topic is 4271 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this