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

Groups > comp.programming > #6947

Re: Tunnelling and pathfinding

Show key headers only | View raw

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

> On 29/09/16 01:00, Ben Bacarisse wrote:
>> 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?
>
> I think it's more likely that you understand Hausdorff dimension
> better than I do. I was under the impression that it could be applied
> to any curve.
>
> Easier, I learn, would be to calculate the Minkowski-Bouligand
> dimension. (Easier in the sense that I can actually see how I would go
> about doing that!)

Why do you think the answer will be anything other than 1?  That's what
I'm missing here.  (I'm assuming that the underlying metric space is not
anything odd, of course.)

> But maybe there is some simpler way to measure wiggliness in such a
> way that under-wiggly or over-wiggly tunnels can be identified and
> rejected?

How about length/distance-between-ends?  It's a bit "unfair" on simple
45-degree tunnels which are essentially direct, but that could be dealt
with in the interpretation or by including a factor based on the angle
(it would be sqrt(2) for 45-degree tunnels, 1 for east-west and
north-south ones).

-- 
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