I am trying to program a pointer to the worlds of the world. I used the A * algorithm on a cell containing earth and water cells. But I think that the best solution would be continents, islands and landfills; calculate the visibility grid for the space between them (only once); then indicate the beginning and destination on the visibility chart; then enable A * on the resulting graph. Looking around, I found a book called computational geometry, which describes an algorithm for computing the visibility graph. However, before trying to implement it in C ++ - does this sound like a good idea?
As far as I know, many different algorithms with different numerical complexity have been proposed for calculating visibility graphs. It also seems to me that this is an active area, and not something that has been resolved forever. Therefore, it seems to me that this is a real question. If you think otherwise, please let me know why!
Edit: Now I implemented an algorithm that first computes a visibility graph on a world map consisting of polygons with approximately 5,000 vertices. At the second stage, A * works on the visibility chart. There is probably a limit, in terms of runtime and memory, to how detailed a map can be. Currently, the visibility chart takes about 10 minutes to calculate on my laptop (I believe that the algorithm is quite efficient, but I also believe that my code is not very efficient and can speed up significantly). Once the visibility graph is calculated, A * is very fast. Thanks again for the answers and comments!
source
share