Ask HN: Have you ever seen a pathfinding algorithm of this type?
blog.breathingworld.com
blog.breathingworld.com
https://en.wikipedia.org/wiki/Visibility_graph
On a visibility graph you can run any search algorithm. The key thing is this graph is sparse (the number of nodes is really limited by the amount and complexity of the obstacles, not the distances).
This algorithm follows almost perfectly your outlined steps. In particular it draws a line to the destination, and if it encounters an obstacle it "walks" paths (generates successors for A*) along the exterior of an obstacle until it can "See" (draw a straight line to) the destination or another obstacle. By using "obstacle free distance to destination" as a heuristic at each node, this will provide optimal paths.
You can, just from the wikipedia page, deduce a good response to the problem of "select the optimal point for bypassing the obstacle". (Maybe try the vertices of the convex hull / AABB - and don't worry, it may take a few iterations to truly wrap around an obstacle)
This will perform much, much better on sparse environments than a grid, because a grid has to iterate O(n) for n grid cells, while a visibility graph has to iterate O(n) for n obstacles (of a given complexity).
Very nice!
Ah, I did hear about the Visibility Graph through AI. I didn’t fully understand it due to my lack of knowledge. But with you bringing it up again, I think I should look into that as well. Thank you for your kind response.
Expire them by time, refresh them by range (can see as they move). Constantly replan and I bet you'd get something reasonable looking, but _only_ if you add an obstacle that represents only what the creature can see. If you add the whole obstacle (regardless of what it can see), it'll just do the optimal thing, which is fine but may not "look right". So clip visibility with obstacle, add that, and union it with all known obstacles, then replan. Keep it fast by doing a union "in place" with known obstacles so your obstacle list doesn't grow unbounded.
You can imagine it would walk toward the goal until it sees a wall, then it would go either left or right for a step, then back for two steps, then left for 4 steps, then back for 8 ... because the A* "frontier" keeps expanding so it keeps searching along that frontier.
And if you're lucky, you just discovered the optimal search variant of the "Drunkards walk" search problem.
I've worked in planning for a bit, mostly for robotics. I can honestly say that the _planning_ side of making interesting behaviors is really simple. It's the world representation that is hard. In the real world it's hard to build up a good enough representation to do smart things. Most robots can't reasonably see longer than 50 yards/100 yards. In games is hard to build up a bad enough representation to match the partial information in the real world - running just about any planner on the map will just work and probably look too good.
It errs on the side of "stupid" but is much easier to implement.
Maybe take a look at HPA* (hierarchal A* - partition the map, pathfind on high-level map, then pathfind at lower granularity).
You can also encode into the hierarchy information about whether a rabbit exists in the chunk in the first place, to reduce the initial search for nearest-rabbit.
Factorio had a good blog post on it [1], and Rimworld too but it also enabled arbitrary-sized partitions. [2]
I'm kind of just guessing based on your basic description though; what's the full scenario in mind?
[0] http://www.gameaipro.com/GameAIPro2/GameAIPro2_Chapter14_JPS...
What I'm aiming for, however, is a real-time scenario where such preprocessing is not strictly necessary. I want to implement something akin to how many creatures with human-like vision navigate using only partial information, just as humans do in real-life situations.
Currently, trees are appearing and disappearing dynamically. In the future, such situations are expected to occur more frequently, so I am aiming to create a lightweight solution that can handle these changes in real-time.
As you mentioned, for cases like rabbits, their location information is already preprocessed and divided by zones. Since this is a small task, it doesn't impose a significant burden on the system. This information is intended to be used when wolves are searching for rabbits.
Additionally, I have recently been considering processing even smaller zones than the current ones to handle the vision of wolves more effectively.
The algorithm in a maze would just use "intersections" as successors, rather than "Next next step down the hall".
This is, in fact, an optimal search algorithm for this problem, and scales much better than any grid search in this case.
And I actually have implemented this for some problems and it actually is as good as the theory says. The hard part is transforming from "Grid with 0/1 obstacles" to "sparse set of visible nodes". That's not trivial and can put the whole thing out of reach.
It would essentially break down the flow of how humans navigate into small, incremental steps. Look with their eyes, make a judgment, move, and repeat the process again and again...
Of course, trial and error could also occur. This might actually make it feel more natural.
In the end, I feel like it might have to transition into the realm of inference, much like AI that mimics human reasoning.
The simplest and most memory hungry thing would be to have a tile map where every tile has a precalculated map on the direction to go to reach every other tile. If you used that as a basis for optimisation you can rapidly improve, for instance an easy first step is to not store any direction data for areas where the path in a straight line is optimal.
Optimize more and you can reduce the scale of data and compute required to calculate the map you can eventually calculate the map quicker and often for only the start and end points you care about. Follow those optimisations far enough and you end up with many of the algorithms used today.
If you have a lot of things moving in a dense area, often the optimal is to maintain a bitmap of 'Something is here' making presence detection trivial.
If you then do a 8 passes over that bitmap for each direction you can go (for square tiles) you can create 8 further maps with a count recording when that pass last saw an obstruction. That lets you implement a very fast jump point search where instead of scanning tile by tile you can jump to the next obstruction in order to either find the way around or find the dead end.
I think the algorithm mentioned in the article is essentially a jump point search but not going into how the "select the optimal point for bypassing the obstacle" is done. Again this comes back to static/dymamic and how to determine that point. If using object outlines, can objects scale or rotate? You could probably do a reasonable version of jump point with convex hulls around objects and simple fast-out distance functions. A single object system would have difficulty dealing when multiple objects have overlapping bounds though. Two S shaped objects that are overlapping in their bounds might have a path possible through them but it is likely to not involve the optimal passing point of each individual shape alone is not on the path between them.
So the ideal is different for static/dynamic, dense/sparse, or memory availability, but all of those factors come back to how they influence how you decide what to look at and how to ignore irrelevant information.
Simon Peyton Jones on Getting from A to B fast route finding on slow computers [PWL London]
https://www.youtube.com/watch?v=L1XDdy-hOH8
- Follow the path found (if there's none, that's it)
- As you follow the path, sense the world and take note of new obstacles.
- If there's an action you can't make because of a new obstacle, re-run A.
There's ways of re-using the state from previous A runs (as long as the goal is still the same) that becomes handy on complex maps where the path you wanted to follow is blocked deeply.
BTW, if you tie-break nodes on lower heuristic value (h-value), then you'll be more likely to search deeper paths, which makes optimizations like trying to follow a straight line kind of useless, but as always, run benchmarks before guessing.
Also, if you have a tight deadlines for the search algorithm, like having to make another tick on the game happen, there's some real-time variants of A* that have a bound for how many nodes A* can expand on each run. I don't think you'll need real-time A* though, I remember that this approach using Dijkstra was fast enough for a project back in Uni on now 15yo hardware, so newer hardware using A* must be good enough ever for large graphs.
In my project, since I don’t need to guarantee complete real-time processing, there isn’t an absolute necessity to find paths as quickly as possible. However, since many entities need to find paths simultaneously, I’d like to keep the computations as minimal as possible.
It might be similar to what you mentioned about algorithms being fast enough on low-spec hardware. In my case, I’m currently using an ultra-low-power Mini PC with an *N100 CPU* as a server. This choice not only helps me study methods to optimize performance but also satisfies my curiosity about fully leveraging the advantages of *MSA (Microservice Architecture)*-based services.
Core … and a bit too vague. I'd be curious what happens to it if you run into a concave object. Image running into the back curve of a crescent, or, since diagonals are not legal moves,
XXXXX
XXX X
X
X
S - - > X E
X
X
XXX X
XXXXX
Of course, the optimal path S → E avoids walking into that entirely.
Since it seems to be a game, though, the other consideration is "should the entity use optimal pathfinding?" Confounding an opponent with an odd shape could be just called "gameplay". (Different opponents might even have different levels of intelligence, and thus, different pathfinding. Some 2D games I have played have this exact mechanic.)
Yes, as you mentioned, the idea of "it doesn’t have to be the optimal path" aligns perfectly with my thinking as well.
In the case of the algorithm I’m currently working on, it wouldn’t enter those concave areas directly. Instead, it would "look" at the obstacle first, recognize that the path is blocked, and then proceed toward one of the corners at the bottom or top of the concave shape. Afterward, it should be able to exit again using the same approach.
However, to make it behave more like a creature with vision in certain situations, it might be good to enhance the algorithm slightly so that it can preemptively recognize "Ah, this is a concave obstacle." That way, it could avoid inefficient behavior while still maintaining its "realistic" navigation style.
Anyway, the details are not enough for me to fully grasp the algo described.
The agents in the article seem to mostly be finding their way around sparsely-distributed, discrete obstacles, so I can see how the "raycasting" approach described would work well, but in a sufficiently obstructed environment like a maze, something like (double-ended) A* is going to both be simpler and likely perform better.
The convex hull is just where the paths will go if it has to go around an obstacle.
So if your maze is specified as obstacles take the vertices. If your maze is specified some other way it depends how expensive it is to translate it.
What you're suggesting is fine and well and good, but it will in an asymptotic analysis do more work than double ended a* that only expands successors for intersections.
Think about all the iterations where the expanded state is just one more grid cell closer to the end of the hall, vs just jumping to the end of the hall. If you limit to counting only iterations, a geometric approach is faster (vs grid).
That may not be the best way to do it in practice. It's also way harder to implement because let's face it everything is a grid.
This is still technically A* if you squint. The straight line is like using a eulicdean heuristic. The "optimal point" is just an abstracted way of navigating around obstacles.
The main thing you lose is that your path is no longer guaranteed to be optimal or guaranteed to be found if a solution exists. This was a problem I encountered, but I was trying to pathfind in a dynamic environment.
If your environment is static, you're better off just doing a pre-processing step where you divide your world into chunks of terrain. Maybe by using a flood fill algorithm and breaking off chunks when they reach the size of 100 tiles. Then you can maintain a graph that tells you if you can traverse from one chunk to another.
Your pathfinding over large distances would consist of an A* search on the graph of pre-computed chunks, and another A* search from your current chunk->next chunk.
If you look at runs, this tie breaking makes A* behave like a greedy algorithm in the absence of obstacles and simply follow a straight path if there's one, and act sort of cleverly when there's a small detour.
The idea goes: Best to just search in that space vs iterating over some other space attempting to indirectly coax out the optimal path. The bonus is that VG-based search is very fast b/c it doesn't search over anything but those. It's just everyone already has grids so they probably just would rather use that.
That's all I'm claiming. That, and TFA is basically the same as VG-based search. So, yeah, there are infinite ways to find paths, some optimal some not, some doing more work, some doing less. They'll all probably be fine but not all come with books of guarantees. OP has done a good job to intuit an optimal algorithm with fantastic performance guarantees in this setting.
You would still be choosing a node with the best f-value, so you'll get optimal solutions with any admissible heuristic. In a 2D-grid your heuristic should also be consistent, which will result in pretty good behaviour.
Yes, as you mentioned, the fact that "it’s not guaranteed to always find a solution" is perfectly fine for me. That’s because it feels more natural.
Moreover, since my goal isn’t to always find an answer in the shortest time, this approach aligns even better with my intentions. In my case, I’d like to handle aspects like "trial and error" as part of the learning concept for entities such as rabbits or wolves.
And of course, I’m aiming for something that works well in *dynamic situations*, not just static ones.
Sooner or later, someone will link to Amit's pages, so it may as well be me :-). Since you are talking about ray casting, perhaps your "performance" question is about the shape/quality of the path. From Amit's: "The most common question I get when people run pathfinding on a grid is why don’t my paths look straight?" [0]
I also recall a video by the 8-Bit Guy [1] where he discussed his pathfinding hacks for Planet X16. Due to hardware limitations, he had to get creative with his path finding. Probably not super-relevant to your project, both could be fun/inspiring in the sense of finding a less traditional way of doing things that really fits your project needs.
--
0: https://www.redblobgames.com/pathfinding/a-star/implementati...
In such cases, humans cannot see the back side of obstacles. Additionally, there are situations where the exact destination may not be known. They simply infer based on what they can see in front of them. "There's an obstacle over there. Which way would be better to go around?" My approach began from this perspective.
This flow of pathfinding is entirely different from A*. So, the algorithm has been modified a bit now. I changed it so that it does not investigate the entire shape or full outline of obstacles. The flow is as follows:
1. Attempt to move in a straight line in the direction I want to go. 2. Detect an obstacle. 3. Explore the visible outline of the obstacle, focusing on the side that seems closer to the destination. 4. When reaching the endpoint of the outline, select an appropriate detour point nearby.
The final detour point will, of course, be a location where a straight-line movement from the starting point avoids hitting the obstacle. Once I reach the detour point from the starting point, I repeat the process.
[1] https://www.cs.cmu.edu/~motionplanning/lecture/Chap2-Bug-Alg... [2] https://en.wikipedia.org/wiki/Jump_point_search
It heads to the goal until an obstacle is reached, then follows the wall. Unusually, it forks and follows both the left and right wall simultaneously. It's not always optimal, but the optimal algorithms such as A* have to test more cells.
This algorithm runs my NPCs in Second Life.
[1] https://github.com/John-Nagle/lslutils/blob/master/npc/obsol...
Given the hardware of the time and the (relatively) large maps, we couldn't just use A.
Fun fact: There was a building called the "Robot Command Center." If you had one, path finding was upgraded by first running this method, and then running A constrained to some distance from the initial path. The result was a more efficient path that removed silly bits of backtracking and so forth. I've not seen another RTS where there was an upgrade that affected path finding.
Hearing stories about the challenges and solutions for low-spec hardware like this is incredibly fascinating.
Your current solution seems like it could be a minefield of edge cases.
One nice thing we added to those "large" game worlds back then was to pre-compute "highway" routes and then path-find at run-time to a nearby "on-ramp" to save time. Also, we cheated by teleporting NPCs when no-one was looking.
However, in my project, everything is in plain view for everyone to observe, so I won’t be able to use any cheats like that!
The pathfinding was a pretty expensive part of the game. I don't remember the profiling details of course (it was 25 years ago) but I do remember us being concerned about it. If I remember correctly we ended-up spreading out the computational load over multiple frames since the P.F. cost is obviously very bursty. I vaguely recall refactoring it to make it stateful so that we could spread the computational cost over X frames. Because pathfinding and follow code were the very first things I worked on for those games I had to write a sandbox because there was no game environment to work in yet.
I also remember that we added more and more "optimization" hacks to the pathfinder because of the cost. The discussion was like: "Its taking too long when the NPCs go upstairs and they end up lost in the bedrooms by the timeout" and so we'd add hacks like "Exclude staircases". There were a number of these hacks. Each of those hacks would then create non-obvious complications and I strongly remember a lot of frustrating time chasing bug reports of the "bad pathfind in case X" variety only to discover that it was working exactly as designed and that the real problem was one of these hacks had unexpected consequences like: "We excluded to staircase but the staircase tiles extend in front of the door so now they can't find their way out."
This is a tangent to your question about pathfinding, but while I'm thinking about it ... a lesson from U7 pathfinding (and animation in general) was that the stateful requirements were common enough that by U8 I built a Domain Specific Language to model/handle it. The language I built (called Unk) and its compiler had closure concepts very similar to what I later discovered was called "async/await" semantics. This DSL made the game designers life a lot easier -- remember other than those Unk scripts everything was in C and assembly, ie no garbage collectors. Again, I was too young and naive (pre-internet!) to know that async-like language concepts already existed so I just naively "invented" it all from scratch.
I think that the problem with A* is that it use a mix of horizontal and vertical and 45° lines, but your proposal makes more natural straigh lines. I think it's more nice, but don't think it's more efficient (but I don't have a hard proof).
PS: The guidelines ask to use the original title. https://news.ycombinator.com/newsguidelines.html
If diagonals on a 2D-grid are forbidden, then you need to use the Manhattan distance as the heuristic.
The article mentions wolves and rabbits, what if a rabbit is in a cave. That is to say the obstacle you need to waypoint around is in fact something you need to go inside of. The wrong waypoints to navigate around the obstacle becomes circle the obstacle indefinitely.
I would probably go with a hierarchical A* that way you can get the high level path quickly and do the local fine grain pathfinding in small chunks as you go.
The example you mentioned might need to be delegated to the wolf’s *lifestyle logic*. For more thoughts on this, it would be great if you could check out the link below: https://blog.breathingworld.com/concept-meeting-for-wolf-dev...
In conclusion, the wolf will, of course, have intelligence and will also possess skills for hunting. With those capabilities, the wolf will likely be able to track the traces left by the rabbit and ultimately find it.
We are now at the final stage. When looking for a detour in the direction blocked by the map boundary and failing to find one, the program attempts exploration on the opposite side. It's getting very close to being complete.
I will direct the author to any number of references in the field of robotic motion planning. These are algorithms designed to deal with continuous spaces, which is the limiting case of the author's problem with too fine grained a resolution in the A* search graph.
Checking the textbook on my shelf, Principles of Robot Motion (2005), I find an algorithm called "Tangent Bug" within the first 30 pages, which is similar in spirit to the author's proposed approach. The textbook goes on for 500 more pages to develop a host of more sophisticated techniques, including "sampling-based planning," which the author may find extremely useful.
Edit: Just recalled this excellent blog post of Casey Muratori on using one of the sampling algorithms, "RRT", for The Witness: https://caseymuratori.com/blog_0005
As you mentioned, *"the goal is to find a decently short path, not necessarily the shortest one."* That’s absolutely right. The basic idea is that when an obstacle is encountered, *I just need to find the first detour point.* After that, the process can be repeated from that detour point in the same way.
The link you provided is also very intriguing. I’ll take a closer look and provide feedback again afterward!
this looks to be solving a different problem than A*, which operates over discrete graphs. this looks to be operating in 2D continuous space instead.
so, what is the algorithm for finding the optimal point on the obstacle's outline for bypass (4)? is it finding the point on the outline nearest the destination?
then, how do you subsequently "backtrack" to a different bypass point on the obstacle if the first choice of bypass point doesn't work out?
there's something interesting here for trying to directly operate on 2D space rather than discretizing it into a graph, but I'm curious how the details shake out.
1. Detect a collision with an obstacle on the straight path connecting the starting point and the destination. 2. Decide which direction to explore along the obstacle's outline (for now, the side closer to the destination). 3. If the end of the visible outline is reached, search for an appropriate detour point around that outline. 4. Select a detour point where a straight-line movement from the starting point avoids the obstacle, preferably closer to the destination.
---
If the first detour point selection fails, I plan to search in the *opposite direction* along the outline where the obstacle was first encountered. I’m currently working on resolving this part.
You can check out my progress here: https://github.com/Farer/bw_path_finding