Working with chunks of terrain

Question

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.

Answer 1

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.

Answer 2

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.