ref: 55f9540179d10828ef79e90cc2f1c1b9335ff242
parent: 4cfec3765a8a5c89126bb3ca3d49f5a8680bcfc7
author: Simon Tatham <anakin@pobox.com>
date: Wed Sep 17 12:43:36 EDT 2008
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]