Let's take for example that in our game, we divide our world (1000x1000 tiles) into chunks of 100x100 tiles. Each chunk contains its own npcs, traps, players, items, whatever. Now, there comes to my mind many problems:

  • Pathfinding: what if an npc at one chunk needs to find a player/npc that is near him but not in the same chunk?

  • Sight: Npc wants to check if someone is near him, what if the nearest npc/player is like the previous example at other chunk.

I'd like to find a solution where the player doesnt have to see how chunks are loaded and interaction between chunks is possible, but seems hard.

EDIT: what i have in mind is a multiplayer rpg (not as big as a mmo), where the map is divided into chunks. Each chunk would represent maybe a settlement, a portion of a forest, a portion of a hill, etc ... I thought about loading not just the chunk being visited by a player, but its surroundings, so transitions are easier.

I need this organization because i'll have many entities to manage. Maybe in the world map exists 100 cities, and each one contains 10 citizens. If a chunk is visited by a player, i want him to see how each citizen talk, and walk, and live. But a chunk not being visited should be handle differently. Maybe i'll do some checks when the night comes to see what happened there.

  • \$\begingroup\$ If you can elaborate on the game, that would be helpful. Right now my answer mostly assumes you are talking about a single player game. However, you say "players" which suggests this is a multiplayer or MMO game. I've added some notes on that, but generally it isn't wise to be small-chunk based for MMOs. (because a popular MMO will have most of the map loaded at any one time anyway so the benefits don't offset the overhead) \$\endgroup\$
    – DampeS8N
    Commented Jan 2, 2013 at 13:45
  • \$\begingroup\$ I'll expand my question \$\endgroup\$ Commented Jan 2, 2013 at 14:33

2 Answers 2


Create class to encapsulate your chunks that will behave like virtual 2D array. Each time you need X:Y tile, that class would find correct chunk and correct local position inside it. For example, if your pathfinding wants 101:206 tile, that class would find 1:2 chunk and return 1:6 tile from it.

For entities, you may need spatial partitioning structure. Update it each time chunk is loaded or unloaded.

  • \$\begingroup\$ I think i get what you mean, but i dont fully understand. Could you elaborate your answer a bit more? if entity a is on chunk 2 at 2.2 and entity b (enemy) is on chunk 1 at 5.6, how could i calculate the distance? I dont see how this solution would fit in a pathfinding system made of nodes. Pseudocode is welcomed \$\endgroup\$ Commented Jan 2, 2013 at 13:15
  • \$\begingroup\$ This is the best way to go. Abstracting the chunks away. To find the distance between two entities, you just need to convert their local coordinates into "world" coordinates, then get the distance between those. Entities should never be storing their coordinates as chunk local coordinates though. The chunks are just the underlying data structure for the world. Store everything in world coordinates. Convert to local chunk coordinates only when you need to interact with the terrain data. \$\endgroup\$
    – House
    Commented Jan 2, 2013 at 15:14
  • \$\begingroup\$ @DampeS8N Traveling 1000 tiles is not huge. A vast majority of the path finding would take place over short distances. This is ideal for the situation as it's presented. It's the simplest to implement, with the least complexity, and the best work/benefit ratio of any of the other alternatives. And so far, appears to be the fastest for path finding across the entire world if pre-processing time is taken into account. \$\endgroup\$
    – House
    Commented Jan 2, 2013 at 16:11
  • \$\begingroup\$ @Byte56 True, I forgot he said the map is only 1000x1000. \$\endgroup\$
    – DampeS8N
    Commented Jan 2, 2013 at 16:12
  • \$\begingroup\$ @DampeS8N I think your answer is still valid for the title question, just not the specifics of the OP's game. \$\endgroup\$
    – House
    Commented Jan 2, 2013 at 16:34

If your first question is strictly about pathfinding, I believe you can simplify the problem by defining some preconditions.

For example: each chunk is connected to every adjacent chunk by a single door. This door is never blocked and is always walkable.

In this case to find your way anywhere you need to find two paths: one global, the sequence of doors to travel, and a lot of local ones (these can be generated when your agent enters a chunk and thrown away when it leaves it) for each chunk to travel to the next door.

If you need anything more complicated, this is a starting point. You can easily modify this idea to have multiple doors, shortcuts between chunks, blocked doors, chunk penalties, etc.

Of course there are other solutions to this problem too - small local graphs that include multiple chunks and are generated dynamically, or even pre-generating the graph for your entire world, and loading parts of it on demand. Each solution has its drawbacks, and you also need to consider which algorithm you're using. A* using Eucledian distance for its heuristic function is always a good idea, as it will keep look-ups very close to the origin in most situations, especially if you accept sub-optimal solutions.

  • \$\begingroup\$ I get your point, but ultimately it does not resolve the original problem. With your suggestion i could take into account the "door" but not people through this door. \$\endgroup\$ Commented Jan 2, 2013 at 2:08
  • \$\begingroup\$ -1 I think this answer misses the point of chunking terrain. It's supposed to be abstracted away from the user and preferably the developer too. Creating additional complexity between chunks is the opposite direction you want to go. \$\endgroup\$
    – House
    Commented Jan 2, 2013 at 15:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .