The new generator works on the same 'combinatorial coordinates' system
as the more recently written Hats and Spectre generators.

When I came up with that technique for the Hats tiling, I was already
tempted to rewrite the Penrose generator on the same principle,
because it has a lot of advantages over the previous technique of
picking a randomly selected patch out of the subdivision of a huge
starting tile. It generates the exact limiting distribution of
possible tiling patches rather than an approximation based on how big
a tile you subdivided; it doesn't use any overly large integers or
overly precise floating point to suffer overflow or significance loss,
because it never has to even _think_ about the coordinates of any
point not in the actual output area.

But I resisted the temptation to throw out our existing Penrose
generator and move to the shiny new algorithm, for just one reason:
backwards compatibility. There's no sensible way to translate existing
Loopy game IDs into the new notation, so they would stop working,
unless we kept the old generator around as well to interpret the
previous system. And although _random seeds_ aren't guaranteed to
generate the same result from one build of Puzzles to the next, I do
try to keep existing descriptive game IDs working.

So if we had to keep the old generator around anyway, it didn't seem
worth writing a new one...

... at least, until we discovered that the old generator has a latent
bug. The function that decides whether each tile is within the target
area, and hence whether to make it part of the output grid, is based
on floating-point calculation of the tile's vertices. So a change in
FP rounding behaviour between two platforms could cause them to
interpret the same grid description differently, invalidating a Loopy
game on that grid. This is _unlikely_, as long as everyone uses IEEE
754 double, but the C standard doesn't actually guarantee that.

We found this out when I started investigating a slight distortion in
large instances of Penrose Loopy. For example, the Loopy random seed
"40x40t11#12345", as of just before this commit, generates a game
description beginning with the Penrose grid string "G-4944,5110,108",
in which you can see a star shape of five darts a few tiles down the
left edge, where two of the radii of the star don't properly line up
with edges in the surrounding shell of kites that they should be
collinear with. This turns out to be due to FP error: not because
_double precision_ ran out, but because the definitions of COS54,
SIN54, COS18 and SIN18 in penrose.c were specified to only 7 digits of
precision. And when you expand a patch of tiling that large, you end
up with integer combinations of those numbers with coefficients about
7 digits long, mostly cancelling out to leave a much smaller output
value, and the inaccuracies in those constants start to be noticeable.

But having noticed that, it then became clear that these badly
computed values were also critical to _correctness_ of the grid. So
they can't be fixed without invalidating old game IDs. _And_ then we
realised that this also means existing platforms might disagree on a
game ID's validity.

So if we have to break compatibility anyway, we should go all the way,
and instead of fixing the old system, introduce the shiny new system
that gets all of this right. Therefore, the new penrose.c uses the
more reliable combinatorial-coordinates system which doesn't deal in
integers that large in the first place. Also, there's no longer any
floating point at all in the calculation of tile vertex coordinates:
the combinations of 1 and sqrt(5) are computed exactly by the
n_times_root_k function. So now a large Penrose grid should never have
obvious failures of alignment like that.

The old system is kept for backwards compatibility. It's not fully
reliable, because that bug hasn't been fixed - but any Penrose Loopy
game ID that was working before on _some_ platform should still work
on that one. However, new Penrose Loopy game IDs are based on
combinatorial coordinates, computed in exact arithmetic, and should be
properly stable.

The new code looks suspiciously like the Spectre code (though
considerably simpler - the Penrose coordinate maps are easy enough
that I just hand-typed them rather than having an elaborate auxiliary
data-generation tool). That's because they were similar enough in
concept to make it possible to clone and hack. But there are enough
divergences that it didn't seem like a good idea to try to merge them
again afterwards - in particular, the fact that output Penrose tiles
are generated by merging two triangular metatiles while Spectres are
subdivisions of their metatiles.

This is the most efficient way to apply the combinatorial coordinate
system. As described in my original article (and mentioned again in
the followup one), you can walk along a horizontal or vertical line of
the tiling, identifying which edge of each tile the line will leave it
by, and computing the location and coordinates of the next tile beyond
that edge, so that you visit every tile intersected by the edge.

By doing one iteration, say vertically up the left of your target
area, and using the tiles you find as starting points for a series of
perpendicular sub-iterations spaced closely enough not to miss any
tiles, you can arrange to visit every tile intersecting your target
region, without having ever had to store a large BFS queue of tiles
left to visit. You only have to keep a small bounded number of
coordinate variables for the whole run, so you can generate a very
large patch of tiling with minimal memory and CPU time.

You can even arrange not to emit any duplicates, without having to
actually store the tiles you've already visited, by checking whether
the y-coordinate of the previous horizontal iteration will have
visited the same tile already.

For Spectres, an extra wrinkle (almost literally) is that they're not
convex, so a horizontal line can visit the same one twice, with
another tile in between. So another part of de-duplication is noticing
_that_: is the edge through which we've just entered this tile the
first one we would have seen while traversing our line? If not, then
trust that it's been emitted already.

As a proof of concept (since I claimed it would work in my writeup
article), and in case anyone wants larger tilings than actual Loopy
will conveniently give you, I've implemented that algorithm in
spectre-test.

However, the actual grid generation for Loopy still uses the more
memory-intensive breadth-first search: because that's what I
implemented first (it's more likely to detect its own errors); because
if I changed it now it would invalidate game descriptions (from all of
two days' worth of live play, but even so); and because the linear
space requirement isn't an important cost for Loopy, which is actually
going to _store_ the whole grid after it's generated, so it needed
linear space _anyway_.

This uses a tile shape very similar to the hat, but the tiling
_structure_ is totally changed so that there aren't any reflected
copies of the tile.

I'm not sure how much difference this makes to gameplay: the two
tilings are very similar for Loopy purposes. But the code was fun to
write, and I think the Spectre shape is noticeably prettier, so I'm
adding this to the collection anyway.

The test programs also generate a pile of SVG images used in the
companion article on my website.

The 'core' library contains almost all the same objects as 'common',
but leaves out hat.c. And the auxiliary program 'hatgen' now links
against that slightly reduced core library instead of 'common'.

This avoids a dependency loop: one of hatgen's jobs is to generate
hat-tables.h, but hat-tables.h is a dependency of it.

Of course, the generated hat-tables.h is already committed, so this
doesn't present a bootstrapping problem in a normal build. But if
someone modifies hatgen.c in order to regenerate hat-tables.h, and
does so in a way that makes it uncompilable, they can't rebuild hatgen
and try again! Of course you can always revert changes with git, but
it's annoying to have to. Better to keep the dependencies non-cyclic
in the first place.

I want to generate an SVG diagram for an upcoming article.

I ran this again today with Leak Sanitiser on, which complained.

In this commit, 'DSF' is simply a typedef for 'int', so that the new
declaration form 'DSF *' translates to the same type 'int *' that dsfs
have always had. So all we're doing here is mechanically changing type
declarations throughout the code.

No functional change: currently, this just wraps the previous sfree
call.

I just found these self-tests lying around in mines.c under an #ifdef
that nobody ever enables. Let's put them somewhere more sensible! We
already have a separate tool for working with the obfuscation system
in a puzzle-independent way, and it seems reasonable to put them in
there.

In commit 8d6647548f7d005 I added the Hats grid type to Loopy, and
mentioned in the commit message that I was very pleased with the
algorithm I came up with.

In fact, I was so pleased with it that I've decided it deserves a
proper public writeup. So I've spent the Easter weekend producing one:

  https://www.chiark.greenend.org.uk/~sgtatham/quasiblog/aperiodic-tilings/

In this commit I adjust the header comments in both penrose.c and
hat.c to refer to the article (replacing a previous comment in
penrose.c to a much less polished page containing a copy of my
jotting-grade personal notes that I sent James Harvey once). Also,
added some code to hatgen.c to output Python hat descriptions in a
similar style to hat-test, which I used to generate a couple of the
more difficult diagrams in the new article, and didn't want to lose.