Replace Diamond search with a BFS

[mina1460]

This PR is a step forward to enable us to do two things: 1- have a readable version of the existing cryptic diamond search that is potentially parallelizable. 2- Allow us to fix this bug by introducing a priority queue based on the Manhattan distance instead of the order of traversal.

Notes for code reviewers:

• the hashset of the visited points can be replaced by a normal tree-based set, but hashmaps with simple hash functions can outperform the log search for large trees, which is the case in this scenario.

[github-actions[bot]]

clang-tidy review says "All clean, LGTM! :+1:"

[QuantamHD]

Looks nice! Does the change to BFS affect the PPA?

[github-actions[bot]]

clang-tidy review says "All clean, LGTM! :+1:"

[github-actions[bot]]

clang-tidy review says "All clean, LGTM! :+1:"

[maliberty]

is "which is the case in this scenario" based on measurement?

[maliberty]

@QuantamHD this PR right now doesn't affect PPA (power, performance, area) but once we switch to a priority queue it will - hopefully for the better. That change will be made in this PR, this review was just for an initial look.

[ApeachM]

Hi, Mina. I have some question for making sure my understanding.

1. Is it correct that the reason for changing the existing diamond search to BFS is to make the code more readable?
2. Are x_offset and y_offset grid coordinates rather than Manhattan distances? If then, I don't think this could solve the bug that you mentioned. Would my thougt be correct?

[mina1460]

Hi @ApeachM Sorry, I think I was not clear in the PR description. 1- Yes you are 100% correct. This PR helps make diamond search easier to maintain and understand. 2- You are also correct. As it stands now, using the queue alone, doesn't solve the bug you discovered. But, it makes it much easier to fix when we move the queue to a priority queue (min heap) where the ordering of the elements in the heap is based on their manhattan distance. This will solve the bug in the gif in the PR description

[ApeachM]

Thank you for your answer.

Maybe we need to expand the search space as much as the aspect ratio, collect the points, and sort them by distance in future work.

This is not by the BFS but by diamond search, but you may refer to the code. This code searches the following GIF when the aspect ratio (site_height/site_width) is 5, which is an extreme case.

Thank you for your work!

[github-actions[bot]]

clang-tidy review says "All clean, LGTM! :+1:"

[github-actions[bot]]

clang-tidy review says "All clean, LGTM! :+1:"

[github-actions[bot]]

clang-tidy review says "All clean, LGTM! :+1:"

[github-actions[bot]]

clang-tidy review says "All clean, LGTM! :+1:"

[github-actions[bot]]

clang-tidy review says "All clean, LGTM! :+1:"

[github-actions[bot]]

clang-tidy review says "All clean, LGTM! :+1:"

[github-actions[bot]]

clang-tidy review says "All clean, LGTM! :+1:"

[github-actions[bot]]

clang-tidy review says "All clean, LGTM! :+1:"

[github-actions[bot]]

clang-tidy review says "All clean, LGTM! :+1:"

[github-actions[bot]]

clang-tidy review says "All clean, LGTM! :+1:"

[github-actions[bot]]

clang-tidy review says "All clean, LGTM! :+1:"

[github-actions[bot]]

clang-tidy review says "All clean, LGTM! :+1:"

[mariam606]

@maliberty Hello, I spoke with Mina and I am interested in taking this up. I agreed with him and he will guide me through it. Can I do so? Thanks in advance!

[maliberty]

That's sounds great - I haven't had time to investigate the failures in this PR.