This is a read-only snapshot of the ComputerCraft forums, taken in April 2020.
O.S's profile picture

*Efficiently* Exploring an Area

Started by O.S, 21 July 2015 - 03:39 AM
O.S #1
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.
flaghacker #2
Posted 21 July 2015 - 07:36 AM
Instead of searching an entire area, you can have your turtles explore on the go, using an algorithm like D*. That could end up being really complicated though, I don't know D* that wel. But it should be as efficient as it will get :)/>.
Edited on 21 July 2015 - 05:37 AM
O.S #3
Posted 21 July 2015 - 07:56 AM
Ah, this looks promising! I'm already implementing A* for pathfinding once the map is filled out, but I haven't come upon D* yet. It might take me some time to fully absorb this, but many thanks for the nudge in the right direction! :D/>
flaghacker #4
Posted 21 July 2015 - 08:06 AM
You're welcome ;)/>.

You'd have to replace all pathfinding with D*, because the area will never be really known.

Also, small correction, look for D* lite, it seems to be a better version of D*.
Edited on 21 July 2015 - 06:08 AM