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

Groups > comp.programming > #6932 > unrolled thread

Tunnelling and pathfinding

Back to article view | Back to comp.programming

Contents

  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

#6932 — Tunnelling and pathfinding

If we want to tunnel from A to B through a binary image, essentially it's 
the pathfinding problem with the restriction that the path may not touch
a set pixel - so shrink the background by a pixel.

But that produces rather straight tunnels. How about starting two tunnelers, 
A and B, who do a  self avoiding random walk, biased so that they
tend to do in the direction of each other. Then when the paths hit, close 
the other end, and that's your tunnel. You can pathfind at each step
to prevent the tunnels backing into impossible corners, though that
would be expensive.

[toc] | [next] | [standalone]

#6933

malcolm.mclean5@btinternet.com writes:

> If we want to tunnel from A to B through a binary image, essentially it's 
> the pathfinding problem with the restriction that the path may not touch
> a set pixel - so shrink the background by a pixel.
>
> But that produces rather straight tunnels.

Surely it might fail to produce one at all if there are too many set
pixels?  But even when there is a path, I don't see how you can say
"that" produces rather straight ones because there is no "that" --
there's no algorithm at all.  I can come up with an algorithm that makes
straight paths, but I can also come up with another that makes very
bendy ones.

> How about starting two tunnelers, 
> A and B, who do a  self avoiding random walk, biased so that they
> tend to do in the direction of each other. Then when the paths hit, close 
> the other end, and that's your tunnel. You can pathfind at each step
> to prevent the tunnels backing into impossible corners, though that
> would be expensive.

I might help if you came up with some criteria for success.  I can see
that "rather straight" is bad, as is "expensive", but what measure do
you have for a good solution?

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#6937

On Wednesday, September 21, 2016 at 2:29:57 PM UTC+1, Ben Bacarisse wrote:
> malcolm.mclean5@btinternet.com writes:
> 
> > If we want to tunnel from A to B through a binary image, essentially it's 
> > the pathfinding problem with the restriction that the path may not touch
> > a set pixel - so shrink the background by a pixel.
> >
> > But that produces rather straight tunnels.
> 
> Surely it might fail to produce one at all if there are too many set
> pixels?  But even when there is a path, I don't see how you can say
> "that" produces rather straight ones because there is no "that" --
> there's no algorithm at all.  I can come up with an algorithm that makes
> straight paths, but I can also come up with another that makes very
> bendy ones.
> 
> > How about starting two tunnelers, 
> > A and B, who do a  self avoiding random walk, biased so that they
> > tend to do in the direction of each other. Then when the paths hit, close 
> > the other end, and that's your tunnel. You can pathfind at each step
> > to prevent the tunnels backing into impossible corners, though that
> > would be expensive.
> 
> I might help if you came up with some criteria for success.  I can see
> that "rather straight" is bad, as is "expensive", but what measure do
> you have for a good solution?
> 
It's meant for the dungeon generator in my binary image library.

A tunnel is where we have two "rooms", or areas of set pixels, and
we wish to connect them, by a one pixel wide path that gives the
impression of having been cut roughly by someone with a pickaxe
(or a giant burrowing worm or similar), with instruction to go
in the right general direction but no advanced engineering and
maybe needing to work round harder areas of rock.

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.

[toc] | [prev] | [next] | [standalone]

#6939

malcolm.mclean5@btinternet.com writes:

> On Wednesday, September 21, 2016 at 2:29:57 PM UTC+1, Ben Bacarisse wrote:
<snip>
>> I might help if you came up with some criteria for success.  I can see
>> that "rather straight" is bad, as is "expensive", but what measure do
>> you have for a good solution?
>> 
> It's meant for the dungeon generator in my binary image library.
<snip>
> But ultimately the criteria are aesthetic rather than strictly
> mathematical.

In my experience (more than none but not extensive) the aesthetic
effects of algorithms are almost impossible to predict.  Even a small
change in some parameter can alter the effect more horrid to very
pleasing.  I think you'll end up trying lots of alternatives and
tweaking them by hand.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#6941

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>

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

[toc] | [prev] | [next] | [standalone]

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

[toc] | [prev] | [next] | [standalone]

#6946

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

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?

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

[toc] | [prev] | [next] | [standalone]

#6947

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.

[toc] | [prev] | [next] | [standalone]

#6965

On Friday, September 30, 2016 at 11:50:58 AM UTC+1, Ben Bacarisse wrote:
> 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).
> 
You can remove the unfairness by using diagonal distance, which penalises
diagonal steps over axis-aligned ones.

abs(max(dx,dy)) - abs(min(dx, dy)) + sqrt(2*abs(min(dx.dy)));

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web