Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.programming > #6933
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Newsgroups | comp.programming |
| Subject | Re: Tunnelling and pathfinding |
| Date | 2016-09-21 14:29 +0100 |
| Organization | A noiseless patient Spider |
| Message-ID | <878tulidnz.fsf@bsb.me.uk> (permalink) |
| References | <9937e5f0-bdca-49dc-b228-6fdd0b68f3c8@googlegroups.com> |
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