10 posts
Posted 21 July 2015 - 05:39 AM
Background:
[indent=1]Its been a while since I've messed with CC or even Lua, but I've decided to come back and tackle a project gave up on a few years back. I don't want to complicate my question with too many details but basically I'm building a semi-autonomous system. To do so, my turtles are keeping maps of their environment, which means they will need to explore a bit.[/indent]
My question (if you haven't figured out from the title):
What would be the most efficient (I was thinking more time, than fuel) method for sweeping an unknown area?
[indent=1]A ) The simplest would be three nested loops for x, y, z. Possibly by chunk. But with that would waste time in cases of overlap (areas already explored) as well as reaching blocked off areas. (Imagine being under a 'U' shape, trying to get inside)[/indent]
[indent=1]B ) To deal with weird U shaped pockets and whatnot, I added a maximum radius from the starting block, creating more of a sphere than cube. Then to minimize overlap, I throw a Dijkstra's out there (favoring forward, up, and down movement to minimize rotating time) to find all nearby unmapped blocks.[/indent]
[indent=1]C ) Alternative solution is a recursive search where as the turtle travels, it checks all adjacent blocks and queues up unmapped ones. Then it continues on until it hits (1) a dead-end/nothing unmapped or (2) hits the maxed radius. It then backtracks to next queued (last added) unmapped block.[/indent]
A is obviously the most accurate, as it hits every block, which also makes it the slowest. B is almost as accuate (skips blocks inaccessible within the radius) but faster as it minimizes rotating. C might miss some blocks that aren't touched (and then queued) but is almost 3 times faster than B to complete.
Now, I'm not looking for a code handout :P/>. Just maybe a fresh mind to point out where I've gone wrong in my logic. Is there something I missed? Maybe a tweak to one of the above methods that blows the others out of the water? Some method entirely new (and probably embarrassingly obvious) that I haven't stumbled upon?
My (ugly as hell) code and testing examples can be provided upon request.
[indent=1]Its been a while since I've messed with CC or even Lua, but I've decided to come back and tackle a project gave up on a few years back. I don't want to complicate my question with too many details but basically I'm building a semi-autonomous system. To do so, my turtles are keeping maps of their environment, which means they will need to explore a bit.[/indent]
My question (if you haven't figured out from the title):
What would be the most efficient (I was thinking more time, than fuel) method for sweeping an unknown area?
[indent=1]A ) The simplest would be three nested loops for x, y, z. Possibly by chunk. But with that would waste time in cases of overlap (areas already explored) as well as reaching blocked off areas. (Imagine being under a 'U' shape, trying to get inside)[/indent]
[indent=1]B ) To deal with weird U shaped pockets and whatnot, I added a maximum radius from the starting block, creating more of a sphere than cube. Then to minimize overlap, I throw a Dijkstra's out there (favoring forward, up, and down movement to minimize rotating time) to find all nearby unmapped blocks.[/indent]
[indent=1]C ) Alternative solution is a recursive search where as the turtle travels, it checks all adjacent blocks and queues up unmapped ones. Then it continues on until it hits (1) a dead-end/nothing unmapped or (2) hits the maxed radius. It then backtracks to next queued (last added) unmapped block.[/indent]
A is obviously the most accurate, as it hits every block, which also makes it the slowest. B is almost as accuate (skips blocks inaccessible within the radius) but faster as it minimizes rotating. C might miss some blocks that aren't touched (and then queued) but is almost 3 times faster than B to complete.
Now, I'm not looking for a code handout :P/>. Just maybe a fresh mind to point out where I've gone wrong in my logic. Is there something I missed? Maybe a tweak to one of the above methods that blows the others out of the water? Some method entirely new (and probably embarrassingly obvious) that I haven't stumbled upon?
My (ugly as hell) code and testing examples can be provided upon request.
