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. Black lines are walls. Red dots are nodes. Blue lines are lines to join neighbours (note no blue line crosses a black line). 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 Continue reading...
