Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.programming > #6933
| Path | csiph.com!eternal-september.org!feeder.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail |
|---|---|
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
| 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> (permalink) |
| 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 |
Show key headers only | View raw
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.
Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll 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