Save "Explored Area" to SQL Database

Question

For a strategy game, the area "already explored" has to be saved to a DB, so that the player can (upon resuming his game) see where he has already been.

The game will be a mmo-game, so i have to handle lots of users - each with perhaps 100x100 fields or more that are already explored.

I thought about client sided creating of a bitmap (each field with value 0 = unexplored or 1 = explored), then sending it to the server database to save it as a blob.

Has somebody already tried that solution or has choosen another (better) one?

Answer 1

If you're really worried about the storage most of all, the maximum you'll have to store is half the map, plus one bit. The first half of the exploration, you keep track of where they've been. Once they reach halfway explored, you switch over to keeping track of where they haven't been and flip you bit. This will cost you a performance hit when you need to switch over to tracking where they haven't been. You'll have to iterate the tiles and see which ones haven't been visited and store those instead. If you were to make a graph of the storage for this technique, it would look like a tent or triangle. Near zero storage on both ends, and the most storage in the middle.

You can improve this by breaking the map up into regions. Do the same half-way technique for each region and you can further just store a single bit for "explored" once the entire region has been explored. Breaking it up into regions also breaks up the performance hit when switching at the halfway point.

How it's stored in the database really depends on how you have things organized already. I'd suggest doing a serialized bitmap stored in the database, per region, that's updated when the player exits the region.

Additional improvements:

• Make the resolution of your explored area overlay half or a quarter that of your tile map. This can drastically reduce the amount of data you need to store, without affecting the game mechanic too drastically.
• Use a lossless compression algorithm to store the data instead. (again trading performance for storage).

Answer 2

Many problems can always be solved with a bit of decomposition.

First off, if your target is the MMO space, then I suspect you either elected to create your maps in continous connected zones much like World of Warcraft's world maps are designed or they're separated into zone-based maps much like GuildWars2.

In either implementation, a map includes area triggers that signify sub-areas or sub-zones within that map (terminology is entirely up to you). So if you combine the characterId, mapId, and areaId; that can easily describe an entry in an exploration table on the server side.

When a player enters a particular map, it's the server's job to query this exploration table and send the client information about what the player has already explored so it can update it's world map state, etc. As the player navigates throughout the world, the area triggers fire and check whether the player has ever visited the area. If so, nothing happens. If not, the server updates the player's exploration state, sends a packet to the client so that it can do the same and perhaps inform the player they've discovered the new area. At some checkpoint on the server side, the exploration data held in memory will be committed back to the database.

Such a narrow table can easily hold millions of rows with little overhead. But it's important to note here that it's the server's job to detect when new areas are explored and to simply send visual information to the client. In no way does the client update any of this state on the server. It's all transparently done based on the player's current position in the map and the area trigger objects defined by the game map design team.

Answer 3

Beside using the trick of flipping from saving the discovered tiles to saving the undiscovered ones once the player has reached 50% of exploration, this comes down to a data organization and compression problem.

As per your question, I assume that the player usually explores the area by moving between adjacent tiles. This will lead to a pattern of "explored paths" in a mostly undiscovered area, and "patches" of undiscovered tiles in a mostly discovered area.

What that knowledge means is that the pattern of discovery will probably have a lot of contiguous tiles sharing the same state. This is interesting, because this kind of data usually compresses very well under most compression algorithms, like LZMA.

Another approach might be to see your data not as a set of tiles, but as a set of blocks sharing the same state. You could achieve such partition using data structures like BSP trees.

I would probably try the compression first, as it would be easy to implement and most likely yield sufficient results.

Answer 4

How about using binary(length) or varbinary(maxlength)? With binary you could store the data for the entire map as bits. Imagine a grid or matrix where the first bit is the position (0,0) and the next is (0,1). Each bit's index N represents the position (N % Width, N / Width). This means 1024 * 1024 bits in total which is one megabyte per player. If you divide the map to sectors and only store the bitmap for players who have visited ta specific sector, you can take it down to 10-100K per player.

With varbinary you could possibly save visited space by storing only the positions of the visited areas (for beginners) before players reach the point where it's worth storing the entire map. For instance the first 10 bits represent the X position of the first visited area and the next 10 bits it's Y position. The next 20 bits are the second visited area.