Dynamically resize world based on number of avatars

[Spycho]

When a new avatar is started, or when a player has been inactive for a while a is removed.

[Spycho]

Requires #17 in order to be able to add 1 to all four map edges.

[eddarmitage]

I've just been speaking with @dsoid and he reckoned that a decision had been made in the past to just pregenerate the largest possible map on startup, and then hide/reveal as needed. I'm still going to tidy things up and allow negative coordinates, but maybe we want a bit more discussion about this?

[dsoid]

@eddarmitage Not sure if it was a final "decision" because terrain generation didn't get very far, but I think we agreed that the pregeneration option was viable and could give us more long-term benefits with potentially simpler code.

I'll explain it again here because it should be easier to discuss in written form.

By "current approach" I don't necessarily mean the current code. I mean the idea of starting with a small world and tacking new cells or areas onto it as we get more players.

The "pregeneration approach" basically means that the world will be generated in one go and that we will simply show/hide portions of it as players join/leave.

My opinion is that the current approach is fundamentally more complex for anything but the simplest terrain generation. We may keep it if we don't want to work much on terrain generation, but at some point it could prove to be too hacky to work with. I think it's a constraint that doesn't give us much benefit and that it's a premature (memory) optimisation.

Even if we don't want to pregenerate it now, at least we'll have a reference for its benefits/drawbacks.

My assumptions:

1. We do not mind too much if we occasionally regenerate the world with every player in it. (once every week or so) There's no human to inconvenience.
2. We don't need to start with a fully memory-optimised solution.
3. We may eventually want to add localised features into our world. Dungeons were one of the original and simplistic examples. We can add sanctuaries or dynamic terrain, all of which are trickier with the current approach.

Description:
KP1: Pregenerate a world with all the features in it and reveal it incrementally to the players.
KP2: If the pregenerated world turns out to be too small (or too large) for existing players, stop it and regenerate it at 2x or 10x or 0.1x the size. Or refuse more players. This may not even be needed.
KP2b: Memory consumption won't be an issue, because our peak consumption only depends on the number of players we want to support. We can reclaim valuable memory by regenerating the map if we're desperate.
KP3: Having the entire world generated in one go gives us a lot more freedom in terms of its content and we don't lose anything in terms of what we can generate.
KP4: Revealing or hiding parts of the world to the players can be done in linear time wrt the number of positions we want to show. The algorithm is trivial and very flexible.

Comparison:
KP5: Storage is not an issue for either option, but it may be more necessary for the pregeneration approach.
KP6: We can still use the original algorithm for the pregeneration approach, but we can modify it in more ways.
KP7: The up-front time complexity of the pregeneration approach is yet to be determined. I have a hunch that it can be made linear wrt the number of cells.

• Checking for connectedness can be done in linear time.
• Generating the cells can be done in linear time.
• The number of "special locations", if/when implemented, will be proportional to the world size.

KP8: Worlds generated with the current approach will invariably be more 'aliased' than what we can do by pregenerating them.

I hope that more or less makes sense.

[Spycho]

That makes a lot of sense. There are some complexities with it though, in that in order to reveal it, you can't just reveal it as you might introduce areas of the map that cannot be reached from other areas. for each expansion, you'd need to see if one of the would-be exposed cells is actually accessible, and make it impassible if not. Similarly, you'd have to see if expanding caused a previously forced-impassible cells is now accessible, and therefore unblock it.

Also, whilst it's not a massive problem to ditch the map and throw the avatars onto a new one, it would probably add a little delay at large scales, and would be a bit of an interruption if someone is watching the playback. There are advantages though, in that regenerating the map prevents people hard-coding human-learnt behaviour into the avatar, specific to the map the human has looked at. Not that this should be a problem at scale - a human wouldn't be able to do a good enough job of hard-coding sensible map specific decisions for it to be advantageous.

I think it's probably worth sticking with the current approach for the time being, as it's likely somewhat simpler (at least for basic landscapes). When we get around to adding the sort of functionality that might be more easily implemented with this approach (e.g. complex landscape features) we can re-evaluate.

It's also possible we end up going with a hybrid - generating larger blocks on the fly with complex landscape features, and stitching them together with existing map edges. you get some aliasing with that though, around the edges of the larger blocks. Not necessarily a bad thing though.

[dsoid]

@Spycho You're right. In order to reveal more of the map, I was thinking of an algorithm that would add the perimeter (or the starting point) of the revealed map to a queue and do a breadth-first walk by adding all new neighbours to the queue until we revealed enough cells. The downside is that we'd have to store whether something is revealed or not. The upside is that we'd guarantee that the perimeter of the map would be equidistant from the centre in terms of walking distance. We'd only spawn players on cells we marked as "revealed" and those areas are guaranteed to be reachable.

Fair enough. We can stick to this for the time being. Last time I checked though, the algorithm didn't run very fast on maps larger than 100x100.

The reason I didn't think regenerating the map would be a huge problem is because a week's or a month's worth of continuous gameplay is already more than what anyone could watch. And it would spice things up a bit. (testing the avatars on different landscapes) I only considered regeneration in the situations where we found ourselves with a massive influx of enthusiastic players.

[Spycho]

Implemented (very) basic map expansion in one direction (map expands east): d483e76. Currently with no obstructions. TODO: obstructions and expansion in other directions.

[observer61]

Added expansion in another direction, so it expands in both directions (away from 0,0)