chiark / gitweb /
Completely rewrite the loop-detection algorithm used to check game
authorSimon Tatham <anakin@pobox.com>
Sat, 10 Sep 2005 09:39:29 +0000 (09:39 +0000)
committerSimon Tatham <anakin@pobox.com>
Sat, 10 Sep 2005 09:39:29 +0000 (09:39 +0000)
commitefda6cff49e7579b5c10b16694ac57340ce2fc2b
treee97bc9592afe354e443aea11b4f503a4402f5dda
parent72989cdf1d73b371fec933e905c5482d709ec6bb
Completely rewrite the loop-detection algorithm used to check game
completion, _again_. In r6174 I changed it from dsf to conventional
graph theory so that it could actually highlight loops as opposed to
just discovering that one existed. Unfortunately, yesterday I
discovered a fundamental graph-theoretic error in the latter
algorithm: if you had two entirely separate loops connected by a
single path, the path would be highlighted as well as the loops.

Therefore, I've reverted to the original dsf technique, combined
with a subsequent pass to trace around each loop discovered. This
version seems to do a better job of only highlighting the actual
loops.

[originally from svn r6283]
[r6174 == 2bd8e241a93165a99f5e2c4a2dd9c3b3b1e3c6f3]
slant.c