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

Groups > comp.programming > #6941

Re: Tunnelling and pathfinding

Show all headers | View raw

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

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