"The Starcraft AI isn't very I"
"...but it's kinda A"
Here's a thought, if you have a very small circular polygon, and grow the edges outwards (camp skeleton stylee) then it is just an approximation of a Voronoi:

If a and b are polygons and we give each edge a negative weight then where they intersect we get a voronoi tesselation of sorts. By giving the sides different negative speed we immitate a voronoi where each point has a shape that grows out of it. (We could even change the shape as it grows outwards, but thats getting ahead of ourselves)
Now of course this is pointless (as the voronoi has a lower time complexity) for circles. However if we wanted to create an interesting brick wall, instead of circles we could use brick shapes... suddenly we are in the situation where we can grow interesting bricks to fit the shape of the walls. So different shaped bricks can be mixed and matched with suitable input polygon generators.

His approach was to cut the building up into a bunch of lego (more like duplo) blocks (funny that he ended up needing a straight skleton implementation to shrink the mortar between the bricks in correctly) . Each block was then textured according to its meta data and situation eg 'next to a window and on the side = this type of block'. This doesn't give much scope for interaction between the bricks, but it does look like a really fast algorithm!
There's some serious potential for improvement here - we push the camp skeleton into 3D and then give it an input volume (bounded by the outer wall and a shrunk wall thickness). Then we create brick shaped (tiny) input polygons in the centre of the bricks and let them grow outwards into one another to fill all the spaces. We get a nicely tesselated brick wall out of it! We'd need to remember to set different speeds on different sides to keep a proportioned brick shape -

I guess we would let the brick volumes intersect, then shrink them back in again to create the morar. The outside surfaces could have a roof-like straight skeleton applied to them to make them bevelled.
Well thats enough work for a pHD, but I've been thinking about this and I think Bristol has left a giant gap in my education - working with other people (who arn't nerds). Think its time I got a job behind a bar.
Random thoughts:
- If a straight skeleton is created, then we can take another line pattern, say a 'curve' and exturude it along the edges of the skeleton? It wouldn't change the intersection points and would need to be scaled for the different weights, but it may be a faster way to make more complicated rooves:
- People keep comming to this page for a straight skeleton implemetation (often in java). I think I'd better write one that I dont mind publishing. Think I'll get all the ideas correct in lush first and then throw it into java. I tried seperating out my code from sity the other night, but was far too tightly coupled to get it out gracefully (and its crap).