Path: csiph.com!eternal-september.org!feeder.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: Ben Bacarisse Newsgroups: comp.programming Subject: Re: Tunnelling and pathfinding Date: Wed, 21 Sep 2016 14:29:52 +0100 Organization: A noiseless patient Spider Lines: 28 Message-ID: <878tulidnz.fsf@bsb.me.uk> References: <9937e5f0-bdca-49dc-b228-6fdd0b68f3c8@googlegroups.com> Mime-Version: 1.0 Content-Type: text/plain Injection-Info: mx02.eternal-september.org; posting-host="017616aa25f81ec581c44d76d61ba2f3"; logging-data="6922"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/Q0UxsoBj+B7XkYd7uB86nQSotXkpbgiY=" Cancel-Lock: sha1:FH+ttJmyS1q7cSSyh/QUxbY48Ac= sha1:JSh0+9T5/YpoPektIzT36AHhryM= X-BSB-Auth: 1.35d7d808b9d1593abc77.20160921142952BST.878tulidnz.fsf@bsb.me.uk Xref: csiph.com comp.programming: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.