Storing items in world

Quote:

2. Store all items (which know their own location) in a large list

Yes, depending on how large your game world is, this method would defiantly not be the best approach for handling this.

Quote:

1. Since my game is tile based each tile would store the items located on it..

One suggestion would be to store the items in a quad tree. A quad tree is a fairly common structure. Therefore, you should be able to find alot of useful information about it online. One advatage to this approach is that the data is arranged spatially so that you can quickly access it during run time. Other approaches exist, however this would probably give you a good start. (I am assuming your world will be comprised of many (perhaps 100's of) tiles since you mentioned it is an RPG.)

You could use a structure for your tiles and include a byte for items assuming you have less than 255 items if not go for something higher. Although doing it in bytes would save a lot more space than kicking it up to int if you have thousands of tiles. Make a Item number of zero be no item at all.

struct g_Tile
{
byte ItemRef;
// Insert other info about tile
};

Give all your items an id which will be associated with that byte.
This is a rather simple approach but should do what you want it to.

I would use the factory model for this, whereby a "factory" class loads a item prototypes from a file and stores them in an std::map. Then, I would have a list of all items that have been spawned and their locations.

Quote:

Original post by Grahf750 I am not sure how I should store all of the items in my world. The game is a tile based rpg. The two ideas I had were: 1. Since my game is tile based each tile would store the items located on it. 2. Store all items (which know their own location) in a large list. I am leaning towards idea 1 as idea 2 sounds messy, but I was wondering if anybody had any other options I could think about.

I'm sort of doing both. To explain, I'm coding a tile based RPG, but only a tiny subset of tiles are loaded at any one time (9 roughly 400m x 400m tiles out of potentially 1000s). Each tile comes with a load file containing local game objects (buildings, trees, moveable items, etc). When loading these are stored in a list (using the std::map class).

When a map tile is deleted from memory all related objects are also removed from the list unless they have been 'altered' in some way. By altered, this might be a building object that has been altered by a game script (for instance I'm working on a series of scripts that effectively burn down a village replacing the original buildings with ruins), or more typically a moveable item (such as a pile of money) that the player or an NPC has interacted with.

This system results in a series of persistent game objects that are then stored in the save file and reloaded into the list at the start of the next playing session.

Pretty easy in theory, but it's been a bit tricky to get right in practice. Deciding if an object is persistent or not, controlling whether a persistent object is active or not (i.e. within the currently active tiles) and moving items to and from the player's or an NPC's inventory system all proved to be difficult to do, but this is more down to the management of the game world (there isn't actually a 'world' as such, just a set of 3x3 active tiles with the ability to identify neighbouring tiles as needed). Having said that, the system is working well and should continue working nicely even when the number of persistent objects gets much greater and even without any spatial partitioning of the items in the list (if it doesn't then the way to go would be to cull less important persistent objects).

Quadtree method is a fair approach. There are so many ways you can extend this, or even use some form of bitstreams to reduce the amount of memory your maps consume (Although only needed if your loading 'several' maps on a single server).

If you have the memory and a longer loading/unloading period isn't an issue, then go with your own idea of using large arrays; I can't think of a faster way to access the information. Quadtrees are pretty memory and speed efficient but doesn't quite compare to a byte/int array with speed, assuming you'll need to access this information constantly (several time for every move)

It all depends on what you want. It's speed vs memory usage.

edit:
Do some benchmarking tests and see what you like. Sometimes speed isn't worth boring code when you're only losing half a nanosecond per cycle.