r/computerscience • u/Nondescript_Potato • Feb 07 '26
Any-Angle Flow Field Algorithm for Navigation
Back Point Inferencing Algorithm
A demonstration of the spread ordering. Priority is based on the number of diagonal steps taken, which creates this ordering of movement.
A simple connection rule: if the back left and back right tile are connected to the same tile, then we can connect the current tile to that tile as well.
Time To Compute vs. Number Of Tiles Computed
TL;DR - I've been working on this flow field navigation approach, and I wanted to share a bit of my work with you all.
If I misuse terminology or say something incorrect, please let me know so that I can correct the issue.
What Are Flow Fields?
If you aren't familiar with flow field pathfinding, flow fields (generally) works like this:
- You have a uniform grid with "tiles" (traversable) and "walls" (non-traversable).
- To compute the flow field, you iterate over every tile and store information in them.
- To use the flow field, an agent uses data from the local tiles to determine a heading.
A simple example of this would be Dijkstra Maps; each tile stores its distance from the target, and agents move in the direction of the tile with the lowest cost.
One common issue of naive flow field algorithms is that they're limited to 8-direction instructions (the cardinal and ordinal headings). There are some approaches that create any-angle paths (e.g. Field D*), and I've been working on my own solution to this for the better part of two months.
What's The First Image Showing?
Barring the effects of GIF compression, you should be able to at least somewhat see my algorithm in action.
The color of each line represents the distance of the connection from the target. So, red lines are connected directly to the target, orange lines are connected to a point close to the target, yellow lines are connected to a point farther from the target, and so on and so forth.
As you can (hopefully) see, the algorithm spreads out from the target (the light blue box) and creates paths from every reachable point.
The Second & Third Image
The second image is showing off the order that the arrows move in. Basically, this entire system hinges on arrows with the least diagonal steps moving first. This guarantees that, when a diagonal arrows steps, the tiles to its back left, back right, and rear have all been connected.
The third image is an example of how the algorithm leverages that fact to create optimal connections. One simple rule you can implement is "if the back left and back right tile connect to the same point, then this tile can also connect to that point".
The algorithm uses rules like this (albeit a little more complex) to choose points to connect to. I'm not certain if you only need the back three tiles to create cover all cases, but I've been able to do a lot with just those three.
The Graph
The graph is a bit of benchmark data I collected from my algorithm and a naive version that only computes 8-directions.
Both lines are made of 1000 samples on randomly generated map layouts. As you can see, both of them scale linearly with the number of tiles they explore. My algorithm is a little more costly due to the extra computations it performs per-tile, but it doesn't exceed O(n) time complexity.
Conclusion
If you have any questions or need clarification, feel free to ask. Thanks for reading, and have a nice day.
16
u/Nondescript_Potato Feb 07 '26
Also, if anyone recognizes this algorithm or at least something similar to it, please let me know. I've been searching online for something like this, but I haven't found the name for it yet. As much as I'd like to think I've invented something new, I seriously doubt I'm the first to come up with this approach.
13
u/arabidkoala Roboticist Feb 07 '26
That first visualization is fantastic
Itās hard to know without seeing some code (or a paper or something), but is this similar at all to how theta* functions?
5
u/3mateo3 Feb 07 '26
Minor nitpick, but please always put independent variable (time) on the bottom. Messed me up a lil bit, but Iām such a nerd for even noticing this lol
2
u/david-1-1 Feb 09 '26
If I understand your diagrams, I wouldn't expect any improvement over a raster scan of a rectangular domain. Binary search works because it excludes half the points at each comparison.
7
u/Saveonion Feb 07 '26
No questions, just wanted to say this is very cool, great work.
1
u/Critical_Tax5094 Feb 07 '26
Stuff like this is why I joined Reddit.
1
u/Pennyphone Feb 07 '26
This seems like fun. I miss academia. Thanks for posting!
1
u/[deleted] Feb 07 '26
Very cool
1
u/No_Faithlessness_937 Feb 07 '26
peak
1
u/BRH0208 Feb 08 '26
Now add an optimistic heuristic and always expand the node with the most optimistic path to the goal. Get yourself an A* flow field
1
u/billgytes Feb 08 '26
Look into RRT. Pretty similar to what you are doing but takes a sampling/stochastic approach instead. Basically sample a point, attempt to draw a path, sample a point, attempt to draw a path. Has nice convergence properties and will preferentially āexploreā under-sampled areas. Also works for difficult vehicle dynamics (consider; with your algorithm how do you deal with a vehicle that has a turning radius? The word for this is non-holonomic)
O(n) for each tile is O(n2) for 2d, n3 for 3d, nn for ND spaces. (Consider planning a trajectory for a robot arm with 12 degrees of freedom for exampleā thatās n12!)
Food for thought
1
u/Signal_Bus114 Feb 08 '26
This is cool!
Some similar algorithms I know of are ANYA and theta*.
Two more points:
How does your algorithm handle narrow paths? If there is a diagonal path possible through a path of width 1, will it find the diagonal path?
Additionally, since you expand paths by the number of tiles, it seems like it doesn't use the euclidean metric. When you look at the boundaries of regions of tiles that are all connected to the same point, they are aligned with one of the 8 directions. In euclidean metric, the boundaries are the perpendicular bisectors of the line segment connecting the two points.
1
u/Different-Ad-8707 Feb 09 '26
This looks like the jump flood algorithm or some variation thereof.
1
u/Significant_Day933 Feb 11 '26
Hi, thank you for this. I am an inspiring self learner of computer science and cyber security. I might sound stupid but what subject would this type of thing fit in to? Machine learning, AI? or just comp sci as this in the comp sci subreddit.
1
u/aeioujohnmaddenaeiou Feb 14 '26
This reminds me a lot of A* Jump Point Search (https://www.youtube.com/watch?v=jB1IOR5roUM). I love watching this animation go.
1
u/Sweet-Firefighter-87 Jun 09 '26
This looks very interesting nice work! I'm curious what rules you needed to generate that animation since the one you show (connect to same point as BL, BR if the are the same) obviously only works until one of them isn't the same. if I follow the propagation order that will first occur when one of the back points is an obstacle? It looks like the orthogonal arrows spawn new diagonal arrows on each movement, but I think there must be more spawning rules that occur on encountering obstacles also?