Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #6942

Re: Tunnelling and pathfinding

Show all headers | View raw

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.

Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Tunnelling and pathfinding malcolm.mclean5@btinternet.com - 2016-09-20 01:05 -0700
  Re: Tunnelling and pathfinding Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-09-21 14:29 +0100
    Re: Tunnelling and pathfinding malcolm.mclean5@btinternet.com - 2016-09-23 00:43 -0700
      Re: Tunnelling and pathfinding Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-09-23 19:31 +0100
      Re: Tunnelling and pathfinding Richard Heathfield <rjh@cpax.org.uk> - 2016-09-28 18:53 +0100
        Re: Tunnelling and pathfinding Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-09-29 01:00 +0100
          Re: Tunnelling and pathfinding Richard Heathfield <rjh@cpax.org.uk> - 2016-09-30 07:35 +0100
            Re: Tunnelling and pathfinding Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-09-30 11:50 +0100
              Re: Tunnelling and pathfinding malcolm.mclean5@btinternet.com - 2016-10-10 01:55 -0700

csiph-web