Naive Path Finding

comments 7
Tutorials
Featured Video Play Icon

This one is a rather brute force approach for a problem we had to solve on a recent job: Finding a path through a bunch of obstacles. Admittedly what we implement here isn’t a very sophisticated algorithm, but its power lies in its simplicity: It will find a path as long as it’s got enough points available.

Also this is another instance where a closest point search comes in quite handy. PCFind, Nearpoints or PCOpen would all be viable options, yet we settled for using PGFind this time, introducing an accelerated version of PCFind.

Have fun VEXing!
Download Project File (.hipnc)

Share on FacebookTweet about this on TwitterPin on PinterestEmail this to someoneShare on LinkedInShare on Google+

7 Comments

  1. Another great tutorial. A couple things that might improve performance:
    1) You are normalizing the tgt vector every iteration of the foreach loop. You could do it once outside the loop.
    2) You dont need the extra step with acos. You get the same results with just using dot product result. Set odp = -1.0 (implying vectors that point in exact opposite directions) and check if( dp > odp ).

    I think. 🙂 Someone check my math.

    • Moritz says

      Hi Robert,

      thanks for the feedback, I didn’t check your math but it clearly works in code and spares an acos => awesome! Admittedly I usually pay little attention to optimizing my code while recording so any hints are highy appreciated!

      Cheers,
      Mo

      P.S: I remember getting into Processing back in uni after seeing your work 🙂

    • Moritz says

      Sorry – I don’t quite get it I must admit – what max do you mean?

      Cheers,
      Mo

  2. Really good stuff! I’m trying to wrap my brain around the next step of this. Being, if you have for example the 20 points in the scatter that all form paths down to the end point from the 20 start points, how do you separate the 20 paths into groups so that you could connect them together without interference from one of the other paths?

    For example when there’s only one start point I can use the connect adjacent pieces to get a nice single path connected but doing the same with 20 start points leads to cross talk among the paths.

Leave a Reply

Your email address will not be published. Required fields are marked *