Material Finding Compass

[scrasmussen]

David Griffin and Soren Rasmussen Goal: Create a Parallel Algorithm that can be Implemented The purpose of this algorithm will be to calculate the shortest path to a material selected by the user, eg. diamonds, coal, etc. If a material is underground the algorithm will take into consideration the durability of the materials around it that would need to be removed to calculate the shortest path. Eg. digging through 8 blocks of dirt will be quicker than digging through 4 blocks of diamonds. We will figure out some way to equate the time it takes to break a single block with the time it would take to walk across a single block.

Possible implementation: We will use a breadth first search algorithm. We will use a while loop that ends when the closest instance of the right material is found. Within the loop we will use a concurrent_queue of position, distance pairs. The queue will be initialized with the starting position and a distance of 0. We will use a parallel for loop to iterate over all of the pairs within the queue and put the possible position and distances into a new concurrent_queue that will be used for the next step. We will have the distance also take into account the durability of the material. We will use a concurrent_hashMap of position to shortest distances to store the shortest distances found so far. After the material is found the first time the shortest distance found thus far will be stored in an int. A new position, distance pair will be added to the queue only if the distance is less than any other found so far to that position and less than the lowest distance found to the material so far. Anytime the material is found it will be added to another list that will be examined outside of the for loop. We will swap the old concurrent_queue and the new one(populated within the for loop) after the for loop has finished. The while loop will continue until all of the positions have a distance greater than the minimum distance found so far. This can be kept track of using boolean values that are only ever set to true and an int that will only ever be read within the parallel for loop; thus we can avoid any concurrency issues.

Work-Span: This algorithm will require examining every voxel within the area that is reachable in the same number of steps as the closest instance of the desired material. let that distance be r then the work is O(4/3 _Pi_r^3) or just O(r^3). If there were no limit to the number of threads available then a thread would always be examining one of the voxels on the shortest path. Thus the span is r. Therefor this problem is highly scalable.

Resources: https://www.threadingbuildingblocks.org/docs/help/reference/algorithms/parallel_for_func.htm https://www.threadingbuildingblocks.org/docs/help/reference/containers_overview/concurrent_queue_cls.htm https://www.threadingbuildingblocks.org/docs/help/reference/containers_overview/concurrent_hash_map_cls.htm

[ColterTucker]

Is this search algorithm only searching for the closest block of the desired material? Or would there be a minimum amount of blocks of the resource that would need to be available in order for the algorithm to take that "area" into account?

[edwardsCam]

I like it. Based on your description, I'm assuming that once it finds the nearest material, it simply points you in that direction, rather than showing the actual path to it? If so then I think you have a good implementation. Is it necessary to have two lists though? Wouldn't it make sense to have the concurrent_queue be a priority queue, and any pairs that would go into your second list, instead just go into the main queue with high priority? Perhaps I misunderstood what you meant, but that seems to make sense to me.