Path: csiph.com!eternal-september.org!feeder.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Ben Bacarisse <ben.usenet@bsb.me.uk>
Newsgroups: comp.programming
Subject: Re: Tunnelling and pathfinding
Date: Thu, 29 Sep 2016 01:00:17 +0100
Organization: A noiseless patient Spider
Lines: 56
Message-ID: <8760pfa832.fsf@bsb.me.uk>
References: <9937e5f0-bdca-49dc-b228-6fdd0b68f3c8@googlegroups.com> <878tulidnz.fsf@bsb.me.uk> <26334da4-49fb-4dd3-bf0f-fb8938ef85f9@googlegroups.com> <nsh028$qjo$1@dont-email.me>
Mime-Version: 1.0
Content-Type: text/plain
Injection-Info: mx02.eternal-september.org; posting-host="017616aa25f81ec581c44d76d61ba2f3"; logging-data="12127"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/4Pxk104PEYh7Ubw81JkXirnTa1KdRtkU="
Cancel-Lock: sha1:iQKdKlv9/lVmek2cuZ4EbvyQOYM= sha1:Z2gcuJwEUuKxZAM4jmAqKoM/57I=
X-BSB-Auth: 1.dcbfefc927f1764bb36d.20160929010017BST.8760pfa832.fsf@bsb.me.uk
Xref: csiph.com comp.programming:6942

Richard Heathfield <rjh@cpax.org.uk> writes:

> On 23/09/16 08:43, malcolm.mclean5@btinternet.com wrote:
>
> <snip>
>
>> So the tunnel must connect the two rooms is a path is possible,
>> it must not touch any other set pixels, loops are maybe acceptable
>> and small expanded sections, but it mustn't degenerately expand
>> the entire space or create excessive loops. Paths must be 4-
>> connected (no diagonal moves allowed) and the background must also
>> remain 4-connected.
>>
>> But ultimately the criteria are aesthetic rather than strictly
>> mathematical.
>
> I'm kind of late to this party, for which I apologise.
>
> One possible fitness measure would be the number of turns in the
> tunnel. Since only NSEW turns are allowed, they are easy to
> categorise, so they should be fairly easy to count, too.
>
> Let us assume that a perfectly straight path between A and B is
> possible. 0 turns.
>
> If that is the case, then the minimum number of turns other than 0 is
> 4, I think:
>
> --+ +--
>   | |
>   +-+
>
> And from now on, if the direction of approach to B is fixed, then I
> think I'm right in saying that the number of turns must now be a
> multiple of 2, as any deviation from straight (one turn) requires an
> odd number of turns to get it back on track:
>
>     +--+
>     |  |
> --+ |  +--
>   | |
>   +-+
>
>
> If you want something that's quite wiggly but not /too/ wiggly,
> measure the Hausdorff dimension of the candidate curve, and reject it
> if it's too high or too low. You have thus reduced the problem to the
> trivial one of calculating the Hausdorff dimension of an arbitrary
> curve. <cough>

I don't see the connection with Hausdorff dimension.  Surely, since a
discrete lattice is assumed, the dimension of the curve will be 1?  Or
is there some interesting metric being applied here that I've missed?

-- 
Ben.