Best way to draw a grid of 1x1 widgets and only recompute/redraw individual widgets that have changed?

[byorgey]

Curious if anyone has thoughts on the best way to accomplish this with Brick. For context, see swarm-game/swarm#2510 . Should we wrap each individual 1x1 widget in its own cache and invalidate the ones we want to redraw? And how do we draw/lay out the grid of widgets so that brick doesn't have to re-process the entire grid every time a single 1x1 widget updates?

I realize this may be an abuse of brick. 😄 Also open to hearing about ways that we could e.g. use some escape hatch to render/draw our grid at a lower level in order to achieve what we want.

[jtdaugherty]

It's hard for me to say. I think it depends on where time is being spent in drawing. The code I see in that linked discussion,

render . vBox . map hBox . chunksOf w . map (renderCoord . Cosmic (vr ^. subworld)) $ ixs

could render individual 1x1 world map cells with cached (WorldCell row col) (say), but that still leaves the surrounding vertical and horizontal boxes to do all the same work they usually do. Perhaps that's an easy experiment to conduct.

I guess if it were me, my instinct would be to try hard to avoid using boxes at all to render the world map unless I could keep the number of boxes to a minimum, such as by constructing a Vty image directly rather than using the built-in boxes. The built-in box functions are meant for more general layout situations and are a much bigger hammer than you probably need for rendering the world, at least at an individual row or cell level, which by the sound of it is just a concatenation of 1x1 Vty images. The more you can just go straight to using Vty and skip brick functions for those small renderings, the more overhead you'll save.

With that said, avoiding hBox and vBox means you take on responsibility for some of the work those functions do, but that would depend on whether you're wanting to do things like track extents, support mouse interaction, etc. If you are just using the box functions as glorified image concatenation functions and don't need to record extents or support mouse interaction, I think there's a good chance you could avoid them altogether.

Another idea is to combine these two approaches in a way: rather than caching and invalidating at a 1x1 grid cell level and using boxes to lay out those tiny cells (costing more overhead), you could cache and invalidate at a larger chunk size (e.g. 5 rows x 20 columns). If you can know which chunk to invalidate based on changes at an individual cell level, that would make it possible to keep using the box layout functions to concatenate larger chunks at render time, but use fewer box cells (reducing overhead) at the cost of rendering a bit more unnecessarily (a whole chunk or maybe a few chunks). But I don't know how will that would work practically since I don't know how often whole chunks would be likely to get cache-invalidated as a consequence of small changes in the map.

[byorgey]

Thanks, that's very helpful! I was just looking into using a raw Vty image, I will for sure try that and see if it speeds things up a bit. Drawing the world in smaller chunks and caching each chunk is a great idea too.

We do want mouse interaction, but I don't think we do that at the level of the individual 1x1 cells --- we just set the entire rectangle as clickable and interpret the coordinates appropriately. So none of this should interfere with that...I think.

[jtdaugherty]

we just set the entire rectangle as clickable and interpret the coordinates appropriately. So none of this should interfere with that...I think.

Yeah, that should be okay. Given some Vty image x, if you write clickable WorldRegion $ raw x, then you'll get mouse click events in your event loop when the world map is clicked on, along with the location of the click. And if you need to translate the world map around to keep it centered about some location, say, then translateBy offset $ clickable WorldRegion $ raw x will give you mouse click events in the world coordinate space even as it's translated around the screen. (This more or less assumes that the world map is the lowermost layer of your Brick application's layer stack, with HUD-like bits layered on top. If you don't want to use translate -- if you're managing the cropping / presentation of your world in the viewable window some other way -- then you'll need to keep track of your world map upper-left corner offset and add that to any incoming mouse click coordinates to get the right world coordinates.)

[byorgey]

Yeah, that should be okay. Given some Vty image x, if you write clickable WorldRegion $ raw x, then you'll get mouse click events in your event loop when the world map is clicked on, along with the location of the click.

Yes, I can confirm this still works.

if you're managing the cropping / presentation of your world in the viewable window some other way -- then you'll need to keep track of your world map upper-left corner offset and add that to any incoming mouse click coordinates to get the right world coordinates.

It's nice to know how translateBy works re: mouse click events, but indeed, we're already managing it ourselves anyway --- the world is huge and you're only ever viewing a small part of it. (We definitely don't want to render a $2^{32} \times 2^{32}$ Image and then let brick/vty translate + crop it for us! 😄) If we go with building the whole view out of smaller individually-cached chunks I suppose we'll have to do a bit more math, but I don't expect it to be difficult.

[byorgey]

Just a follow-up to note that I have now also implemented caching/invalidating at a larger chunk size, so that we can avoid redrawing the entire world every frame but also not pay too much overhead for assembling lots of 1x1 widgets. I am happy to report that this makes a huge difference - I can now run at 30fps at full-screen resolution, even when scrolling the world (before it was only like 7 fps)! swarm-game/swarm#2515

@jtdaugherty , quick question - am I correct in assuming that the brick widget cache will never kick old things out of the cache --- so if e.g. I want the cache to be limited to a max number of entries, I will have to keep track and invalidate old entries myself? I imagine this would hardly ever be relevant for most brick applications.

[byorgey]

Makes sense. I can pretty easily just maintain an LRU "shadow cache" containing only keys, and invalidate the corresponding entry in the brick cache every time a key gets kicked out of the shadow cache.

[jtdaugherty]

Maybe I'm not understanding your application design, but what would you need an additional cache for? Supposing that your world map is broken up into individually-cached chunks, it seems to me that every chunk is in one of two states prior to each redraw:

• Unchanged (with respect to its on-screen representation), in which case the renderer will use the most recent rendering of that chunk or draw it and cache the result otherwise, or
• Changed (with respect to its on-screen representation), in which case your event loop would need to invalidate that particular chunk in the rendering cache.

I would imagine that the second step would be done any time an individual cell within a chunk changes, so your invalidation is a continuous process. Or perhaps you have some additional intermediate layers of caching for some other reason?

[jtdaugherty]

Which is to say,

handleEvent :: ... -> EventM n s ()
handleEvent e = do
    -- Handle 'e' and somehow determine that it affected a given world location, 'loc'.
    let chunkName = chunkNameForLocation loc
    invalidateCacheEntry chunkName

[byorgey]

Yes, it would be perfectly correct without maintaining the additional cache. The issue is that the world is very large (2^32 x 2^32 --- so, practically infinite) and if you wander around the world a bunch, the cache could end up containing images of chunks that are very far away and may never be needed again. The cache thus ends up being a sort of memory leak if you do a lot of wandering around. So the purpose of the additional "shadow cache" would just be to keep memory usage capped at some constant maximum.

[jtdaugherty]

Oh, I see! Makes sense. Thank you for the explanation!