I found a paper on a quad tree constant time neighbor found algorithm here. But iI figured that I only need one part of the algorithm, I don’t actually need to find the neighbors, I just need the neighbor level differences which seems to be set in this part of the algorithm:
￼

The level difference calculations are done in the table before that pseudocode. See the box containing Case 1, Case 2, Case 3, & Case 4. The algorithm is a breadth-first search, so it starts with a single node that’s grey (partially black – e.g., enemy – and partially white – e.g., empty). Figure 7 shows an example of what happens when you calculate level differences on that node. And then it recursively subdivides until every node is either black or white. You can’t get the neighbor level differences without building the whole quadtree.