Edge smartdraw is SLOW

[apocalyptech]

I discovered while implementing the larger brush sizes that our edge smartdraw function is absolutely godawful slow. It's not bad when just using the 3x3 Square brush, but anything larger than that ends up pegging my system quite a bit. Disabling smartdraw makes things run quite quickly, at least.

So! I don't find it surprising that the edge smartdraw is slow, but I'm guessing that fixing it might be more trouble than I'm willing to spend at the moment. We'll see. The way I see it, here are the options:

1) Fix the edge smartdraw so it's not a sloth 2) Warn the user, when using larger brushes for floors, that they might want to disable smartdraw, or at least floor smartdraw. 3) Automatically disable floor smartdraw while using larger brushes.

Number 1 is the "real" solution, number 2 is probably where I'll end up going.

Anyway, I'll at least take a look and see if there are any obvious shortcuts / optimizations that could be made.

[apocalyptech]

Actually, now that I've taken a quicker look, I think that the real issue isn't the smartdraw itself, really. MapGUI.action_draw_tile() ends up calling a bunch of self.redraw_tile() in there, looping on lists of tiles sent back from the smartdraw module.

I bet what would actually help this out a lot is if action_draw_tile() just kept a dict of affected tiles and returned it - then the calling function could loop through that list and just do the redraws once for the entire drawing loop, instead of multiple times. As it is, a 5x5 square floor draw would probably be calling at least 225 redraw_tile()s for each "step."

[apocalyptech]

Ah, well, alas. Looks like streamlining that doesn't actually save much time.

It does look like having floor randomization on tends to impact the speed a bit, too.

Edit: Well, rather than rely on estimations, I added in a bit of timing code to measure how long we were spending in smartdraw, and it looks like smartdraw itself probably isn't the bottleneck here. Will investigate more...

[apocalyptech]

So, it's only tangentially related to smartdraw, really. (Specifically in that with smartdraw active, there's simply lots more tiles that need to be redrawn, typically.) The bulk of the CPU time on this thing comes from the calls to MapGUI.redraw_tile(), which is probably set up reasonably for redrawing a single tile, but leads to an awful lot of duplicated work when dealing with a block. Probably the best way to address this would be to redo that function to take in a list/dict/whatever of tiles and have it "intelligently" redraw a whole chunk of the map, rather than redrawing a single tile at a time.

[apocalyptech]

Okay so: I've been stuck on one annoying little issue which has been making me feel rather like an idiot for the past few days. I'd hoped that a week's break while I had houseguests would clear it up a bit, but apparently not. Perhaps you could point out something stupid I'm doing here? I feel like there's an absurdly simple solution to this that I'm just not getting.

Fixing the speed issue here will involve basically having redraw_tile (or a separate function, whatever) redraw not just a single tile, but a list of passed-in tiles (ie: the list of tiles that have changed as a result of the larger-brush draw action). The function will basically end up rendering a small little rectangle of the map - for instance, here's the "patched" image that the current redraw_tile ends up generating if I add a bag in Baizel's house:

When I set up a function to take a range of tiles instead, what I'll need to do is define a "rectangular" area which we know we need to redraw. For some situations this is quite simple. For example, pretend that the lava tiles are the ones passed-in, and the whole areas of grass+lava defines the "rectangle" I'm talking about:

So far so good. In all those cases, we can define the northwest corner of the "rectangle" by taking the minimum X and minimum Y values from each of the coordinates. For instance, if we have (1,6) and (3,2), the NW corner is (1, 2). I'd been using this graphic to work out some of this on paper, btw:

The problem's more that due to the even/odd row differences, there's also many situations where a simple "min(x1, x2), min(y1, y2)" doesn't quite do the trick. Take for instance these two situations:

Primarily because the two tiles are on a mix of even/odd rows, the rectangle has to get "expanded" a bit beyond what might be immediately obvious - in each case there's a couple of different options which would work equally well. My problem is that I've got some mental block with coming up with a programmatic way to determine the corner to use (again, mostly right now I'm just looking at the NW corner). If both tiles are odd, or both are even, it's easy (as above) - just use the "min" technique.

If the odd/evenness is mixed, though, the closest I'd been able to come is: 1) If the "min" coordinates are in an odd row, subtract 1 from x 2) If the "min" coordinates are in an even row, use the min row

For example (I've bolded the option which fits the above method): (3,3) + (2,6): "min" method gives (2,3) (odd) - answer is (2,2) or (1,3)

(3,3) + (1,8): "min" method gives (1,3) (odd) - answer is (1,2) or (0,3)

(2,6) + (2,5): "min" method gives (2,5) (odd) - answer is (2,4) or (1,5)

(3,4) + (2,7): "min" method gives (2,4) (even) - answer is (2,3) or (2,4)

(4,2) + (2,5): "min" method gives (2,2) (even) - answer is (2,1) or (2,2)

(3,5) + (4,4): "min" method gives (3,4) (even) - answer is (3,3) or (3,4)

However, it ends up falling down in, for instance, this case:

(3,4) + (2,3): "min" method gives (2,3) (odd) - answer is (2,2) or (2,3)

It's in an odd row, but subtracting X from the "min" value would give (1,3), which is too much. It'd look like this:

Whereas the only two options that make sense, (2,2) or (2,3), look like this:

There's probably other exceptions too, but that's the one that's been annoying me for awhile. I remain convinced that I'm just somehow way way overthinking this, and I'd appreciate a second set of eyes to point out any stupidity I might be engaging in here. Thanks!

[elliotkendall]

I would probably just throw up my hands and do circular redraws (pass in center coords and a radius) instead of trying to get rectangles working correctly. If you're dead set on getting this working, though, I'd probably need to do some trial and error to figure it out.

[apocalyptech]

Heh, fair enough, though I think that computing circles, given the coordinate system, might be tricky as well. :) No matter, I'll poke around with it a bit more. Perhaps I can put it to bed this weekend.

Other options, of course, would be to sort of define a "virtual" brush that goes along with the actual brush, which specifies the redraw area on a per-brush basis. Or, alternatively, as far as I can tell, the worst-case scenario for my "best" attempt would probably just end up drawing a little more than was needed, so I may just go ahead and live with that.

[elliotkendall]

Right. We just want to improve performance, so it doesn't have to be perfect, just better than it is now.

And now I'm working on a clone brush tool that's also suffering from weird grid problems, so I don't get to throw my hands up just yet :)

[apocalyptech]

Okay, well, I've got a method which is pretty quick and does Well Enough that I don't care to tweak it further. Basically whenever there's a mismatch, I'm massaging the data so that the points on the rectangle always end up on an even row. It'll end up sometimes drawing more that it needs to, but it'll be good enough.

For the NW corner of the box: 1) If even/odd is the same: (min(x1, x2), min(y1, y2)) 2) If not, subtract 1 from the y value of the odd row, then use the min() method

For the SE corner of the box: 1) If even/odd is the same: (max(x1, x2), max(y1, y2)) 2) If not, add 1 to the y value of the even row, then use the max() method

Then finally once we've looped through all the tiles, apply the same logic to the two computed points, so that we end up with a "regular" rectangle with all coordinates on even rows.

This patch is a crude demonstration, overriding all editing functionality by allowing you to select two points (highlighted in red) which will then show you the NW/SE corners in green (click again to dismiss) - https://gist.github.com/apocalyptech/84916102e2afa9582e29 - If the NW or SE point overlaps a selected point, it'll still highlight in red, not green.

Anyway, should be able to work that in by tonight, and hopefully get this closed out.

[elliotkendall]

You may also be interested in a static method I added to the Map class for the copy tool I'm working on, which let you apply one or more directions (N, S, E, W, NW, NE, SW, SE) to a coordinate pair and get back the resulting coordinate. There's also a method to find a path of directions between two sets of coordinates.

[apocalyptech]

Oh, hm, interesting. I'd actually already had a "coords_relative" (and tile_relative) function in there, though it wasn't static. We should probably collapse those down to using one or the other, rather than having two functions to do the same thing. :) I do like the pathing function...

[apocalyptech]

I think I'm actually pretty close to just giving up on the performance fixes for this, for now. Near as I can tell, there's really not one specific thing that's causing the slowdown, just a combination of everything doing. The redraw_tile() fix that I suggested above doesn't really give much speed improvement, though I think I'll end up pushing it out anyway because it does prevent a lot of duplicate work, even if the performance gains are pretty minimal.

One thing I'll probably look into is seeing how it works if compiled with cython. Perhaps I could "solve" it with just brute force like that.

The OTHER way of dealing with it, honestly, is probably to just start doing the display stuff "properly" by throwing all the rendering jobs onto the GPU, instead of doing it in Cairo surfaces. I assume that that would probably involve using some kind of GL surface (most likely via SDL). I'd been thinking I might want to do that anyway eventually, honestly. I somehow doubt that I'll end up making the time to dig into it, though.

So anyway, that's where this one isn't. :)