1
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ What's the problem with keeping a list of explored area for each user on the server? Have you tried this and found it not to work or what? \$\endgroup\$ – MichaelHouse Feb 28 '14 at 20:06
  • \$\begingroup\$ I don't find creating a bitmap on the client side and sending it to the server the least bit secure and I do find cheating to be a nuisance. \$\endgroup\$ – AturSams Feb 28 '14 at 20:14
  • 2
    \$\begingroup\$ @ArthurWulfWhite Depending on what's actually revealed, the user would probably only be cheating themselves, since they wouldn't know where they haven't been (making it more difficult to find new things). \$\endgroup\$ – MichaelHouse Feb 28 '14 at 20:21
  • \$\begingroup\$ I agree. It depends on the game mechanics. \$\endgroup\$ – AturSams Feb 28 '14 at 20:24
  • 1
    \$\begingroup\$ You should never store bitmaps in a database. In that case you could just as well create bitmap files on your server. Anything that isn't well suited for a normalized DB design doesn't really belong in a DB IMHO. \$\endgroup\$ – bummzack Feb 28 '14 at 21:40
3
\$\begingroup\$

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).
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ What do you mean by save where they've been and then save where they haven't been? If they have been to half the map, the best way to store this is with one bit per grid square and flipping all the ones and zeroes does not preserve space. At best you could then compress the black and white bitmap using standard lossless image compression such as GIF or PNG. \$\endgroup\$ – AturSams Mar 1 '14 at 9:32
  • \$\begingroup\$ @arthur It's a great question, it depends on how things are being stored. You're right that it wouldn't work with a bitmap. OP would have to compare a few methods and strategies. \$\endgroup\$ – MichaelHouse Mar 2 '14 at 0:09
2
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ msdn.microsoft.com/en-gb/library/ms188362.aspx \$\endgroup\$ – AturSams Feb 28 '14 at 20:22
  • \$\begingroup\$ The actual map has size 1000 x 1000, so varbinary(maxlength) could work to save the whole map. But I do not see how your suggestion about saving only the visited areas could work with a varbinary. Could you please explain? \$\endgroup\$ – A. K-R Feb 28 '14 at 21:14
  • \$\begingroup\$ Lets say new players that may not return statistically are 40% of the player population and that they often only visit 1% or 2% of the map. In this case you can save a sparse array of areas visited. For instance lets say the map is 1024 * 1024, you could use in theory only 20bits in the form (x, y) (uncompressed) to signify one area they visited. You need one million bits to save the entire zone so spending 20bits is a bargain. If you do one better and divide the entire map to sectors, you could save even more that way. \$\endgroup\$ – AturSams Mar 1 '14 at 9:25

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.