Your basic tiles will be represented twice.
- The 'game' tiles, that will just be things like 'collides' and a reference to some visual content. Probably an id number for a sprite, or possible multiple if you want more complex maps. If you think about a tree on grass the tree is probably better as a separate object rather than part of the tile.
- The 'graphics' tiles. This is what is visible on the screen. It could be a big pre-rendered bitmap, or a bunch of preloaded images that you look up based on indices (or even both).
- Objects. Efficiency says you probably won't want this in an array unless you have an extremely high density. Possibly look at a QuadTree although a basic list could probably work too.
The choice between using an array (a good choice for tiles), or a list/quadtree will depend on your data density. For tiles you know you will have 100% data density because each cell on your map requires a visible tile (although for a massive 'growing' game world like some kind of a Tile based MUD this might not be the case). Choosing between a list/quadtree will probably depend on your total object count and the types of operations you are performing (a list would be quicker for updating every object once per gametick, a quadtree would be quicker for locating an object based on its position in the game world).
But you don't have to choose just one representation. You can store reference (pointer/smart pointer) to objects in multiple different data structures. Rather than scan though all your objects every game tick, just make a list of objects that need to be updated and also have them in a quadtree for position lookup information and rendering purposes. This way only objects that need to be updated will be check. Just remember to remove them from all the possible locations when they are destroyed.
So don't have any operations that require you to 'scan' your map, that will kill performance. The possible exception to this rule would be path finding.
There are also many kinds of 'lists'. Rather than a basic 'linked list'. A que or cirque might be a better choice for a list of things to be updated. You will want to learn about different data structures (or containers in C++ terminology).
There are different types of 'arrays' as well. Some kind of dynamic array (or C++ vector_ might be a better choice if you need resizing (maybe you want a client to request chunks from the server based on the resolution of the screen, so you need to be able to resize all your arrays on the fly. But that is probably overkill for most purposes, it would probably be simpler to just blow away your arrays.
When it comes down to it, 'graphics' and 'game' tiles are basically the same thing but the graphics could use much more data pertile since it has to have the rendered graphics there. Both of them can use the same buffering algorithms to store nearby tiles.
For the 'game' tiles, 1000x1000 isn't a huge number of tiles on a modern system. You could probably load the whole thing into memory in a grid array. At 4 bytes pertile (just enough for a int for a tile index id, it's about 3MB) At 32 bytes a tile (kind of a lot, it's 30MB). This is only the game datastore side of things, for graphics prerendering the whole map into memory would be excessive. Although you could probably get away with having all your tile sprites loaded in at a set and just using an index pertile and looking it up on the fly when rendering, of course then your maps are limited to a specific 'style' such as 'dungeon', 'snow', 'desert', 'forest', etc... Something like Zelda would have worked that way but now days I think we can do better and remove the need to limit graphics to a fixed set. So for the graphics you will defiantly want a buffer system
A game like Minecraft breaks the game world into chunks rather than loading tiles. This allows for an entire area to be loaded at once which is much more efficient. Also you can do things like memory alignment. Or having some chunks hosted on a totally different server. Minecraft uses something like 64*64*128, but for a flat 2D game you would probably want something bigger. But don't worry about things like memory alignment at this stage, optimize later.
So for a MMO with a big map I would probably recommend streaming in the 'game' tiles into a buffer too (just like the graphics tiles). Just load chunks off the side of the screen. Do remember that the number of chunks you need will be based on the resolution of the client. Aim for having basically an infinity sized map. All you need to ensure is that loading the tiles is faster than walking the distance (not hard on a modern system).
On the client side when you walk, don't 'move' all the tiles in memory. Instead have a tile_offset that represents the first left tile (either the buffer or visible tile). When you walk change this offset and load in new tiles behind it. You will also want a scrolling animation so have another pixel_offset that represents how many pixels each tile is moved over by (this will just cycle once per step). Use the % modulus operator to handle wrapping on these offsets.
Chucks can be a hassle as you have to be able to handle boundary conditions.
Another thing to consider is if you want your maps to be based on the client-side or server-side. Most MMO's use client-side maps where the client and the server have an identical copies that are shipped with the game (or possibly via an update). Something like a MUD or SecondLife has server-side 'maps' that are stored on the server and sent to the client. Server side maps allow for continuous changes to the game world, if you allow others to get the server software then also totally different worlds, and can even be edited live if you want. But the down side is they will delay the tile loading time, will need a larger buffer for tiles off the edge (in case there is an intermittent network interruption), it will put more strain on the server (since now it has to stream chunks/tiles to the client). You could possibly make a 'hybrid' version, where when the client enters a map it checks to see if they have the current version of it and if they don't will download it all from the server in one go (or you can download it perchunk to stop a 30MB transfer for a small edit to a single tile somewhere, or you could look at something that lets you make a 'diff' between 2 maps and just send the diff).
The main difference between implanting client/server side maps will be where the 'game' tiles are loaded from. Either from disk (client) or from a network connection (socket). You might also have to implement the 'graphics' tiles transfer/synchronization if you want to be able to make new tiles as opposed to just maps. In that case you would need to transfer image sprites (simple file transfer would work fine), maintain a list of all the tile_id to image_file mappings, and transfer/synchronize that to clients.
If you are doing a MMO you can try to separate the visual components from the ones that effect gameplay/physics. The server only need to know about collisions and any possible interactions. But this will depend a lot on your specific setup (is it pertile collisions or perpixel). For example World of Warcraft looks like a 3D game but if you think about it, it's probably only taking place on a 2D plane (I haven't played it that much so I could be wrong), they could theoretically treat the entire this as a 2D game at the server side.
