I have a canvas of size of approximately 1000x1000 pixels. I also have a matrix that represents that canvas and returns -1 if that 'pixel' is walk-able. I need to find a path between one of my objects and some endpoint that DOESN'T necessarily need to be shortest. I just need a path. What algorithm should I use?

  • \$\begingroup\$ What algorithms have you tried? You've got classics like A*, Djikstra's algorithm, breadth-first or depth-first search at your disposal. Did you run into any specific uncertainty in your research into these algorithms, or encounter a particular problem in your attempts to implement them so far? \$\endgroup\$ – DMGregory Apr 20 at 16:38
  • \$\begingroup\$ @DMGregory I couldn't find any information on whether or not those algorithms would work on this scale(1 millions nodes in a graph?). I might be totally wrong and if I am, please correct me. \$\endgroup\$ – droft1312 Apr 20 at 16:47
  • \$\begingroup\$ 1. Did you try it? Each of the examples above is linear in the number of edges in the graph - that's about the best asymptotic complexity you can expect for a traversability search without further constraints. The rest will depend on your implementation, the structure of your maps, and your choice of heuristic if using A*, ie. all issues for which we need you to take the first step and try implementing them, to isolate whether/what specific problems arise. \$\endgroup\$ – DMGregory Apr 20 at 16:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.