chiark / gitweb /
Yet another complete rewrite of Slant's loop detection during
authorSimon Tatham <anakin@pobox.com>
Wed, 17 Sep 2008 16:43:36 +0000 (16:43 +0000)
committerSimon Tatham <anakin@pobox.com>
Wed, 17 Sep 2008 16:43:36 +0000 (16:43 +0000)
commit55f9540179d10828ef79e90cc2f1c1b9335ff242
treebc00e110de2db6450e076075292d7ab05ef0cf87
parent4cfec3765a8a5c89126bb3ca3d49f5a8680bcfc7
Yet another complete rewrite of Slant's loop detection during
gameplay. Having tried methods based on using the slashes to define
a dsf on grid vertices, and also methods based on tracing round the
loops using conventional (non-dsf-based) graph theory, it occurred
to me the other day that there's a far simpler technique involving
connectivity. A loop is precisely that which causes the playing area
to become disconnected; so what we do now is to go through and build
a dsf describing connectedness of the _area_ of the grid rather than
the vertices. That divides the area into its maximal connected
components, and then we can trivially identify every edge that's
part of a loop by noticing that it separates two nonequivalent
pieces of space. The resulting algorithm is half the size of the old
one, and it's much easier to be confident of its correctness.

(Having said which, there will doubtless turn out to be an
embarrassing bug in it, but I haven't found it yet.)

[originally from svn r8187]
slant.c