I like pentagons.
Instead of porno line drawings we should etch these tilings on our spacecraft to impress the aliens.
That’s the way it has to be, right? Either they are slime mold or we look like slime mold to them. “Oh, how cute. Their greatest ‘thinkers’ consider it a big paradox that they haven’t detected us monitoring them since they went multicellular.” —S.A.A.
Tessellation is pretty cool, and to me this is just a form of that. I imagine it's a lot easier now with computers, you could probably throw together a genetic algorithm that mutates a shape until it finds one that gets 100% coverage; I'm sure there's probably some favoured angles or such as well.
You just need to provide a gradient for the search space. Something like inverse of average gap between tiles. This is standard for any metaheuristic search (of which genetic algorithms are a sub-category), so I wouldn't call it "doing something clever".
Metaheuristics search a problem space to find an exact solution (total plane tiling). In order to search that space, they need direction. The "almost plane tiling" is the direction. You said it would be difficult for a genetic algorithm to find a solution because the set of solutions is very small, but that's missing the point of a metaheuristic. It's the difference between climbing a hill and a cliff. Either way the goal is at the top, but the hill is easier to get up.