Tiles is not scalable

[timhutton]

Currently, Tiles uses a hard-coded bounding-box request covering all the globe. If there are lots of tiles painted, this will stop working.

Ideally it would:

• only request tiles as needed to draw them
• intelligently cache tiles on the client

[timhutton]

Thoughts: (suggestions welcome!)

• Server stores a 'modified' UTC timestamp on each tile, updated when painted.
• Client uses localStorage to cache tiles in a quadtree. Each leaf quad stores: { bool is_empty; color c; timestamp last_checked; } Or maybe a list of tiles and centers.
• Client requests tiles from the server by sending a tuple of bounding box and timestamp, asking for any tiles in that region that were modified after a certain time. Server responds with list of tiles centers and colors. If more than N tiles are to be sent, the server sends a message instead saying 'too many'.
• Client chooses how often to check each region for updates, based on what the user is looking at and when it last checked there.
• If localStorage is exhausted, client deletes distant/ignored bits of the cache (merging quads and marking them as unchecked). Will also need to consider other games that also require localStorage on same origin.

So a new client might proceed like this:

• Initial quadtree is single quad saying whole world empty, last checked in 1970.
• Request whole world. Server says 'too many'.
• Subdivide quad into four. Ask about user's current quad first. Repeat. Eventually we will get to a subdivision where the server sends a list of tiles.
• Client reverts to background polling of nearby quads, in anticipation of small panning movements.
• User pans to France. Client starts asking about quads there.

Questions:

• Is there an efficient way for the server to answer queries of the form above?
• If we're implementing this much it might be best to consider at the same time how to get tiles that are square everywhere on Leaflet's default Mercator projection.
• Is there such a thing available as a lightweight javascript library we can use?
• Do we want the same quadtree structure mirrored on the server side?

[rawles]

At the moment we store a history of all tile operations, so that we can plot a nice video of the tiles changing over time. From this point of view, it would be nice to have a button with a camera icon which sends the bounding box of the page

Quadtrees seem appropriate, not just for the client but also for the server. I still think that centres aren’t as useful as sending bounding boxes, because I think we want the ability to send areas of colour rather than sending a large number of tiles. These areas can be made to be compatible with your strategy for storing the quad tree. I also think that we should have a fixed number of colours for games, rather than using hex colours, perhaps eight. In effect we have only five now because of the limited area of the user interface.

I can get the server to check the number of tiles that it needs to send too. We could have another endpoint for the client to see how many tiles would need to be sent, before actually requesting them. The use-case seems to be repeatedly trying to determine the largest quad for which the server will return a set of tiles. This is very wasteful for the server, since it needs to explicitly count the tiles in the area requested before failing, possibly many times. Since we know the bounding box of the client’s map, can’t we just start with that? We could even say ‘return as much as you can around this bounding box’, though perhaps the user would prefer to reduce bandwidth usage and only cache a certain area (this could be explicitly defined by the user).

Having squares everywhere on a spherical surface sounds tricky but maybe someone’s tried to solve this already. Ideally we’d need the squares to line up as much as possible. We could just start from the equator, and do a band of squares, then move up and do the same, but the edges of the square would move out of sync. Perhaps we can deform the squares somehow.

[timhutton]

Once the client has got the subdivision structure in place (cached with localStorage) they will no longer need that sequence of asking for over-large boxes and being rebuffed. From that point onwards, the client will only query for the smaller quads, which will only occasionally return 'too many'.

But yes, to mitigate the initial cascade of 'too many' responses the client could subdivide in advance and then only query for the smaller quads, based on the current map view or the user's location.

Squares everywhere on Mercator isn't too hard, we just need to make the latitude_divisor a function of latitude.

[rawles]

The squares wouldn't be the same size, but I suppose that doesn't matter too much, especially as the change would be gradual. Okay, great.

My suggestion was to have a two-step query. The first allows the client to know how many tiles exist for each quad (and, possibly, subquads), given the bounding box, so it can then structure its successive queries accordingly. This count can be cached on the server so its execution will be very cheap. The second is the actual query.

[timhutton]

Oh I see. Yes, your idea of having two endpoints is good. So maybe a spec:

1. tile_count/ takes (timestamp,bounding_box) and returns (#number of tiles in that bounding box modified since that timestamp).
2. tiles/ takes (timestamp,bounding_box) and returns list of (tile center, color) for those tiles in the bounding box that were modified since that timestamp. It is up to the client to not request too large an area.

[timhutton]

Proposal for tiles that are everywhere square on Leaflet's default map projection:

latitude_divisor = 342 / cos(latitude*PI/180.0)
longitude_divisor = 342

At Cambridge this is the same as our current tiles, where we currently use:

latitude_divisor = 556
longitude_divisor = 342

[timhutton]

Actually there's a better way of getting everywhere-square tiles on Leaflet's default projection. WebMercator/EPSG:3857 has a horizontal range of coordinates +/- 20026376.39 and a vertical range of +/- 20048966.10. Leaflet has functions to project to/from this coordinate system to LatLng. Squares in that coordinate system appear square on Leaflet maps. If we allow tile coordinates to be 324n where n is an integer in [-61809, 61809] horizontally, or [-61879, 61879] vertically then we have an unambiguous coordinate system with tiles pretty much the same size as currently.

[apgoucher]

I like the proposals in this thread. I'd make two adjustments:

• slight reduction of tile size so that the world is exactly 2^17 * 2^17 (making it ideal for quadtrees);
• include a 'last modified' timestamp for every node in the quadtree, not just the leaf nodes.