pathfinding_proposal
This document is now out-of-date. It is recommended that you look at my 2011 GCER paper on the subject instead.
https://github.com/CBCJVM/GCER-Pathfinding-Paper-2011
This document presents a proposal of a set of algorithms that could be used together for intelligent path-finding support in CBCJVM.
We are looking at a very simplified version of the problem, as it assumes things like the bot having a radius of zero (being a singular point). I'm still trying to sort out the specifics of how this could be solved, but it seems like the easiest solution would be to virtually extend each line, further limiting the range of possible points to navigate to.
See Also: How CBCJVM Position Tracking Works
This is my best-attempt at describing the algorithm. I did my best, But there may be technical inaccuracies. You may want to consult Wikipedia in addition to this, especially if you have no clue what Dijkstra's Algorithm even does.
I made a mistake here: The original text has been removed. I'll update this with a fixed explanation soon.
So now our tree has turned into a linked list. We have the shortest possible path from S to E, and we have done it with relatively few steps in comparison to a bruteforce one. You should be able to visually verify that this would in fact be the shortest possible path.
We can divide the board up into line segments, one for each PVC pipe, or multiple for each object on the board, such as blocks. The static board could be stored in a file, and additional lines for movable objects could be dynamically set by the program (possibly even as a function of time).
The diagram shows that by drawing imaginary lines from each point of a line back to the point of the robot, and then extrapolating those lines outwards gives us a set of trapezoids expanding off infinitely who's area is not directly accessible. This effectively gives us our "Line of Sight". This algorithm can be seen as a type of reverse-ray-tracing algorithm. This part of the algorithm would not need to be implemented for our purposes, but it provides interesting perspective to the derivation of our final algorithm.
Now say we want to figure out if a point is "visible" or not. We simply need to place that point on our grid and then draw an imaginary line segment from the point to the center of the robot (shown in the second figure). If this line segment intersects any solid line segment, the point will be inaccessible. In the second figure, the first point's segment does not intersect any solid line, so it is directly accessible. The second point does intersect a solid line segment, so it is not "visible".
It should be noted that this algorithm is slow, requiring O(n) time for each
point check, or with crosschecking (which is how we would use it), it requires
O(n^2) time, but it should be fairly easy to implement. It could possibly be
sped by removing completely hidden lines from crosschecking as soon as possible,
but I do not believe speed should be too much of an issue, due to the low
complexity of the board, and the effort required to do this would probably
exceed the benefits of the performance gained. Furthermore, to my knowledge this
complete algorithm is a unique solution, created ad hoc by myself.
Each node on the board could be run through the Line-of-Sight algorithm, and then could store a cached list of visible nodes. This piece of the code would run only once, after initialization, or possibly multiple times, once after each movable object is shifted. Certain optimizations can occur here, deriving from the fact that if one node can see another node, that other node can see it. In other words, visibility is mutual.
Because each node would already be run through the Line-of-Sight algorithm, the only additional checks would have to be for the start and end nodes. Knowing what points are visible by what allows us to construct our tree for Dijkstra's algorithm. The fastest straight line path, if not direct, is one which runs along each corner, represented by nodes. This should be made obvious by the example above.
We can pair this code with CBCJVM's movement library and it's position tracking code (not yet stable).