A true pathfinding library (Not a motion profiler)

I’ve been putting a lot of time into making a pathfinder that will take only a start and end point, and spit out a path. This uses a version of the A* algorithm. Currently it can take a 2d array, or a bitmap image to run the pathfinding on.

There’s also a computating to return a path of straight line waypoints. (Could be used to make your own straight line path follower or in conjunction with a motion profiling, such as Jaci’s Pathfinder.)

There’s a MotorOut class which takes an accelerometer and gyro input, and gives back motor powers. Mock testing gave me a deviation from the path of ~1 inch, but we all know practice is different. Hopefully I’ll be able to get this tested on an actual robot, but it probably won’t happen until after GRC (End of september).

There’s not a readme currently, but I did my best to make it intuitive, and I included JavaDoc. You can look at Main in github for an example. The Main class and the images folder are not included in the Jar.

I’d love to hear some feedback on whether any other teams would benefit from this.

If I can get it to work on one of our robots, I believe our team could benefit from this! :slight_smile: Thanks for sharing! Will get back to you if I can set it up.

I will also be hopeful that you will make a readme-helper soon as well! :slight_smile:

I think I have an idea for how to structure it. I might even get it done today. I’m working on training new programmers which is why I haven’t tested the path folloeer on one of our robots.

The actual Pathfinder part works. You could use it along with an autonamous system that reads each point and just goes in a straight line then turns towards the next point; repeat until at the end. We did this last year for autonomous. You can find the code here: https://github.com/frc-4931/2018-Robot/blob/master/src/org/usfirst/frc/team4931/robot/commands/AutoCommand.java

On a side note. I’ve been going back and forth if I want to add compatibility with Jaci’s path finder. If I do I’ll be down the road after I get everything worked out.

The problem with this scheme is that you just have so many points (one for each pixel) and it’s just not physically possible to stop and turn at every point, especially with the number of tiny turns A* takes to get the strictly shortest path.

You’ll need to smooth this path out in some way for it to be useful.You could also modify the algorithm to prioritize straight lines, but the problem with applying Manhattan pathfinding to the real world is that robots, especially large tank drive robots, work on a very non-Manhattan level. One assumption that A* makes is that you can move to any other connected node with the same cost, not caring how you got to this node. This is good for video games, but very not good for robots when we consider inertia and direction of travel.

How to solve this? You can use a less discrete grid, where assumptions of A* are better satisfied. You can also use a different algorithm like Lazy Theta*, which uses line of sight to find a path.

This is very helpful, and I’ve considered most of this.
The idea behind the follower is to be able to smooth it out without needed to run a separate algorithm, as it doesn’t directly turn at any point. I’m thinking running it into a PID type system. There is a way to reduce the path into straight lines from the A* path, only available based on the FRC implementation. I’ve looked into straight line search algorithms but most of them align to the grid which is not something I want.

After Gateway Robot Challenge this weekend I’ll be able to testing on our robots. I’m currently working on refining a couple things in order to be able to test right when I get access to the robots.