I'm curious about how I should be drawing my game world. I'm going to have a map, let's say 1000 by 1000 tiles in size, with many players on it. Each player will be at a position in a map, and when they move I want their sprite to stay in the centre of the screen (so I want the map itself to move).

Is it efficient to do this by drawing a map 1 square bigger on each edge than the game window itself, then having the extra bits chopped off? Or should I be slicing and dicing sprites?

If you're curious as to what sorta thing I'm looking at, think tibia.com crossed with Pokemon, with graphics somewhere in between, and a turn-based attack / defence system.

  • 1
    \$\begingroup\$ I often hear anxframework.codeplex.com mentioned as an open source replacement of XNA, but "what technology to use" questions are out of scope. Also, your second question is a possible duplicate of gamedev.stackexchange.com/questions/46228/… \$\endgroup\$ – Exilyth Jul 23 '13 at 18:09
  • 1
    \$\begingroup\$ Hey Josh, "Which technology to use" questions are off topic for the site, so removed that one from your post. There are a number of questions on the site about drawing maps, keeping characters centered and so on. Have you searched for similar questions already? You kind of a have a pretty broad question here. \$\endgroup\$ – MichaelHouse Jul 23 '13 at 18:09
  • \$\begingroup\$ I thought I'd worded the question in such a way that it would be acceptable... The real question I'm asking with the replacement for XNA is have Microsoft officially released anything, or have they implied their support for a particular development library. Apologies if it was off topic. Regarding the map drawing, well I've played these sorts of games before, and I struggle to believe that the method which makes sense to me (and the one I've seen around many open source games) is using the language to its full potential, I don't believe it in fact to be remotely efficient... \$\endgroup\$ – XtrmJosh Jul 23 '13 at 18:12
  • 2
  • 1
    \$\begingroup\$ Josh, read the title of the linked question. It explicitly states 2D. \$\endgroup\$ – MichaelHouse Jul 23 '13 at 18:16

Just draw slightly outside the screen. Essentially, only cull tiles/objects that are completely outside the view frustrum/rectangle.

Slicing sprites manually is something you cannot possibly hope to do as fast as the GPU can. You'll have to do a lot of clipping manually in your own code, which the GPU has dedicated hardware for. It's significantly easier to calculate the visible or partially visible subsection, generate a vertex buffer for the tiles, and draw that.

I'd also suggest searching the other tilemap related questions on this site for further recommendations on culling, map representation, and so on.

| improve this answer | |
  • \$\begingroup\$ I've had a look at a variety of questions, primarily those which were suggested when I clicked "ask a new question", and typed a few phrases to see what results came up. They were all suggestive of this method, but somehow I can't seem to comprehend how it will work. I guess the only thing I can do now is actually try it, and see how hard it really is! \$\endgroup\$ – XtrmJosh Jul 23 '13 at 18:25

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.

| improve this answer | |
  • \$\begingroup\$ Very interesting post you've made there, and incredibly insightful. I did once contemplate the structure behind World of Warcraft (the freshest point in my mind), and I will presume from the flying mounts and what not that it is actually handled in a 3d "way", but using a group of 2d layers (as I intend to have). The game Tibia (my inspiration, really) uses 14 floors, and each floor is exactly 4 semis high (a semi being the division, you need 4 "partial floor changes" to change floor. Fascinating, I will continue to consider and post once I have done so, thanks! \$\endgroup\$ – XtrmJosh Jul 23 '13 at 20:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.