# Constrained Random Walks

I’ve been playing around with a few methods for generating “interesting” tessellations. The properties I’m looking for are

- irregular (not all the same shape)
- majority non-convex shapes (squiggle back towards itself)

Initially I was approaching the problem focused on the shapes themselves, but quickly realized that was unsuitable because every shape’s edge is also the (partial) edge to another shape. Instead, focusing on the lines themselves essentially cuts the number of edges in half, though you do have to walk the edge graph to recover a shape’s perimeter.

My general approach has been to generate a random set of points, disperse them with a few rounds of voronoi, and then generate an initial tessellation with a voronoi diagram. From there, the goal is to reshape the straight lines into a more interesting curve.

For reshaping straight lines, the constraints are:

- maintain end points
- no intersections with self or other lines

The two ways I see of approaching this problem are:

- geometrically - lines + bezier curves with some computational geometry for intersection detection/avoidance
- computer science(y) - grid of pixels

I have some good results from the former but wanted to see what the latter would yield. Even though the end result can’t be pixelated, it should be easy enough to recover the path of pixels and apply some smoothing if they’re too bumpy.

For pixel paths, I’m only considering 4 neighbors (NESW) and you can’t create a solid 4x4 block anywhere (that makes recovering a path ambiguous).

To get started, I wanted to mirror the functionality of reshaping lines like before. And so given a straight (currently only applicable to horizontal lines from L to R) line, what paths can you take from the start to end with a given path length `L`

? Here are the paths for L = 1..10 They are grouped internally by the gap length which is the number of pixels between the start and end points. (code is here)

Aside: as much as we all grumble about css being uber complicated, `image-rendering: pixelated`

is a pretty neat thing!