Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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.

share|improve this question
    
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) –  DampeS8N Jan 2 '13 at 13:45
    
I'll expand my question –  Wolfrevo Kcats Jan 2 '13 at 14:33

2 Answers 2

up vote 5 down vote accepted

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.

share|improve this answer
    
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 –  Wolfrevo Kcats Jan 2 '13 at 13:15
    
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. –  Byte56 Jan 2 '13 at 15:14
    
@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. –  Byte56 Jan 2 '13 at 16:11
    
@Byte56 True, I forgot he said the map is only 1000x1000. –  DampeS8N Jan 2 '13 at 16:12
    
@DampeS8N I think your answer is still valid for the title question, just not the specifics of the OP's game. –  Byte56 Jan 2 '13 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.

share|improve this answer
    
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. –  Wolfrevo Kcats Jan 2 '13 at 2:08
    
-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. –  Byte56 Jan 2 '13 at 15:11

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.