CODEWITHSUNDEEP
pythonalgorithmpath-findinga-starmaze
AstonKey
AstonKey

Reputation: 71

Connect nodes to neighbours via line of sight (straightline)

I have a structure that is similar to a maze, but with much more open space. And for each node in the structure, I would like to find all it's 'neighbours' (nodes are neighbours if they are in line of sight, i.e no walls blocking the straight line between them).

Here is a little image to help explain what I mean.

Node neighbours example

I am currently implementing a very naive and extremely costly brute force approach. In which I check every combination of nodes for an intersect with any of the maze walls (walls stored in 'edges').

for n1 in nodes:
    for n2 in nodes:
        if not intersect(n1, n2, edges):
            n1.neighbours.append(n2)
            n2.neighbours.append(n1)

This works fine for small structures like the example above. But I would love for this to be scalable to much larger structures.

So my question is if there is any way to find all the neighbours of each node much faster/ more efficiently.

Cheers :)

Upvotes: 4

Views: 179

Answers (1)

Bearded grasshopper
Bearded grasshopper

Reputation: 11

You might want to read Monge's book on projective geometry :)

Let's use an occlusive screen around each node, a square is computationally easy, a circle needs more math. The screen is a collection of edges that hide space from the node. The screen.occlude() method takes one of your walls as input an calculates the projection on the screen, and then extends the occlusion by adding an edge or extending one.

The result is that there are (much?) less occlusion edges then walls. Then we invert the loops over occlusion edges and nodes to gain time. Note that the method .remove_occluded_by() only loops over remaining candidate neighbours, which is a shrinking collection. I guess the gain is from O(n^2) to O(n*log(n))

You can also have on each side of the square 2 points that are the extremes of the occlusion in that direction, possibly the corners of the virtual square. Every node outside the 4 occlusion cones is visible. Not sure this will gain time.

for n1 in nodes:
    n1.occlusion = a_1_by_1_square_occlusion( centre = n1 )
    for e in edges:
        n1.occlusion.occlude( e )
    n1.neighbours = nodes - n1                # your choice
    n1.neigbours.remove_connected_walls( n1 ) # your choice
    for o in n1.occlusion.edges:
        n1.neighbours.remove_occluded_by( o )

Upvotes: 1

Related Questions