Map Chunking

Published on 2023-03-19
#gamedev #bit-dungeons

One of the challenges of creating an open-world in a multi-player game is deciding how to handle map data - particularly if you're not storing maps on the client. In Bit Dungeons maps are stored purely on the server for a variety of reasons.

  • Smaller bundle size when loading the game

  • Ability to selectively hide data on the map (hidden walls, players, etc.)

  • Can edit map data without sending out client updates

The obvious solution is to chunk the map - as many games do - in order to avoid streaming too much data at once. This is also neccesary to avoid choking the server with needless broadcast messages.

Bit Dungeons does this currently by breaking maps into 30x30 chunks of tiles. When a player loads in, they load all chunks immediately around them, for a total of 90x90 tiles. Anything outside of that won't be loaded on the client - but this is well within the expected range of a player's view.

Currently, the server maintains a list of loaded chunks, and each chunk contains references to player entity IDs that are within it. So we can quickly look up a chunk, grab it's neighbors, and pull all players within that 90x90 grid - then broadcast any updates to them.

Dynamic Sizing

One thing I've been thinking about is if it would be possible to break down chunks further. They need to be large enough to cover a "reasonable" range of view, but I can't simply resize them to whatever the player can see plus a little extra. Modifying the client to have infinite zoom and load all chunks would be incredibly easy.

However, it would be nice to be able to prevent broadcasting messages to players who are definitely not interested in them. An example, which is probably the easiest situation to handle with a special case, is idle players. If a player is not moving, they are not going to be interested in any updates that are not within their immediate view.

Attaching an "Idle" component to those players, and excluding them from the chunk broadcast system would be handle this case.

However, there are other scenarios where having more control could be nice. Imagine two chunks seperated by a wall of trees; there's no way the player can ever get over there. Should they be receiving events from that other chunk?

If it were a thin wall of tiles, then no - it wouldn't really make sense, as they could still see beyond it. One thought is preprocessing the map data when the server is started and statically defining neighbors might be the best way to handle this.

Thinking out loud here, but an option could be running a pathfinder from the center of each chunk to the center of each neighbor. If the distance crosses a certain threshold, then that chunk could be considered "out of range" - and we wouldn't add it to the neighbor list.

This would have an additional benefit of making neighbor lookups much faster, as they could be stored in set instead of queried at runtime.

Something to think about, at least.

Priority Events

While I don't truly think there will ever be a need for more granular control, I have also been experimenting with asssigning game events a priority. The idea is that if a single chunk becomes too active, events are passed into a "broadcast delay queue" and players outside that chunk will start receiving less important updates at a slower rate. Sort of inspired by EVE Online's "time dilation" system.

Of course, all of this is only really considering running on a single server. I'd like to start poking at sharding the map horizontally, which will invite a whole new host of interesting problems. There is a lot to do before I have time for that, though.

Back Home