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).
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.
Is there a nice way to handle the idea that a creature might have a better or worse memory or ability to build a model of the environment? That seems like it would be an interesting dimension to add to a creature.
Sure, if you held a deadline to my head and told me to do it, I'd just include obstacles that are "within their memory".
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.
The ability to reason about obstacles that you can’t see could be an interesting feature to add for a human-equivalent creature, although I guess it will be a real mess to simulate something as smart as a person, haha. But for example, if you know what a house looks like, you can probably speculate about where obstacles might be, depending on parts of the roofline that you can see. And might be wrong. And your odds of being wrong might be influenced by your familiarity with some region’s architectural conventions.
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.
If you want something that looks a little "more real" but doesn't involve complex management of memory, maybe try a bug algorithm. https://en.wikipedia.org/wiki/Bug_algorithm
It errs on the side of "stupid" but is much easier to implement.
Oh~ This is very similar to the concept I was thinking of.
I don't really like the idea of exploring strictly in a clockwise direction, though.
Thank you for the information!
The core optimization you're trying sounds fairly similar to JPA*, which I believe is fantastic on open maps but eh on dense ones.[0]
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?
First, I understand that the JPA (Jump Point Search) family only works efficiently in static environments.
This means it requires preprocessing to achieve high efficiency.
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.
It seems like this would do OK for open areas with a few simple obstructions. I'm not sure how it would do if there were complex obstructions. For instance, it's unclear how it would work if you were trying to pathfind through a maze.
@johnfn
The approach I’m considering would be similar to how humans navigate: using only visible information to continuously infer and find the way in real-time.
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.
It would do just fine - but that's because OP is essentially grabbing on the intuition behind Visibility Graph search, which is (or was) a very common path planning algorithm using just obstacle boundaries.
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.
It's not my idea. There's a bunch of video tutorials on it if you want to google around.
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.
The difficulty has always been in how many things you look at. Tiles or objects. With static maps you can quite easily structure things so that you don't have to look at very much at all. When things are dynamic tests such as 'look at the thing in the way' suddenly get harder because you have to determine for any given point A) is something in the way? and B) what is it?
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.
I was thinking this too, A* is a good general performance algorithm, it’s possible the poster found an algorithm that performs better on their use case, but doesn’t generalise as well as A*, custom path finding algorithms that take advantage of domain knowledge are pretty common!
This has been done, many times before, it turns out the neural network just learns a crapper version of A*, and of course, any domain knowledge from whatever environment it's in, there was a post on this very thing last year on hacker news.
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
It goes from 0 all the way up to A*, then beyond. I think the new stuff is based on https://www.cs.tau.ac.il/~haimk/papers/sp-wea.pdf but I'm not sure since the paper isn't explicitly named in the video.
I haven’t watched the video yet, but I really like the title: “on slow computers.”
I'll give you feedback again after I watch it.
The document you mentioned also seems to have a lot to learn from.
- Run A* on the optimistic pathfinding graph (no obstacles on the unknown cells).
- 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.
As far as I’ve researched, if there’s an assumption that there are no obstacles, the fastest way to select a straight path is Bresenham's Line Algorithm.
If I’m mistaken about this, please let me know!
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.
> Among the outline information, select the optimal point for bypassing the obstacle. (This part is the core)
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
Once you're inside such a shape, following the outline is not the optimal way around it (you'd waste time in the little alcoves at the top & bottom, and I could make those alcoves considerably more pathological, too). You'd want to head for one of the opening's corners.
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.
You're referring to the "Convex Hull". And if you are inside a shape, drawing edges to the visibile vertices of the shape (until you're on the boundary of the convex hull) will easily get you a path out, and, bonus, will eventually draw a perfect shortest path to the end.
Imagine a maze or labyrinth, with the agent and the destination both inside of it. Is it useful to try to figure out the convex hull of the walls, even if it is effectively "the entire maze"?
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.
You can path-find using only vertices and a can-see function to generate a-star successors.
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.
Yes I have, I did something similar for a project naviagting in a space game.
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.
I feel this is not needed if you tie-break nodes in Open to favour lower h-values. This leads to a node selection bias for deeper paths, which are more likely closer to the goal.
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.
On a sparse map, you can tune A* all day, but ultimately if your paths involve more than 1) vertices on the obstacles or 2) straight lines from src to (maybe some of) those vertices to goal, you have created suboptimal paths.
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.
> On a sparse map, you can tune A* all day, but ultimately if your paths involve more than 1) vertices on the obstacles or 2) straight lines from src to (maybe some of) those vertices to goal, you have created suboptimal paths.
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.
Oh! This seems like something even AIs haven’t suggested before.
The fact that it attempts paths in real-time without preprocessing is what I like the most! I definitely need to research this further!
I’ll definitely take a look at it. Thank you!
Hey there, it is a little bit ambiguous what you mean by "find an algorithm that performs better". Do you mean in terms of runtime, or in the "quality" of the path?
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.
Oh, I saw that blog too. It helped me a lot to be inspired.
What I mean by "performance" is that I want to minimize preprocessing, and I want to minimize the amount of computation I can do even when I'm navigating in real time. I'll definitely watch the video you gave me. Thank you!
I think this part also needs to be considered.
Many pathfinding algorithms, including A* , aim to find the optimal path.
However, my goal started with replicating how humans visually find their way.
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.
So far, no one has mentioned "Bug Algorithms", which have a similar structure of (1) walk in the direction of the goal, (2) walk around obstacles as they are encountered, (3) leave the obstacle to proceed when some condition is met. They are very simple to implement (though not optimal) and there are a number of variants to play around with. Howie Choset has some good lecture slides that describe them [1]. However, as some others have mentioned, something like Jump Point Search [2] is likely a better option given the described scenario.
I've done that something like that.[1] It's appropriate where there's a significant cost to detecting obstacles, because it tests few unnecessary cells.
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.
We used this algorithm in the RTS Outpost 2 in 1997. I think the original Command and Conquer did something similar.
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.
Oh, as expected, A* couldn't be fully utilized on older hardware. I can totally relate, as I’m running my server on a Mini PC with an *N100 CPU* right now.
Hearing stories about the challenges and solutions for low-spec hardware like this is incredibly fascinating.
Very similar to the pathfinder I wrote for Ultima in 1990. At the time I was too young and naive to know that there were lots of existing similar graph algorithms (this was before the internet and, more importantly, I was 20 years old and therefore already knew everything LOL).
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.
Yes. I worked on Ultima 7, 8 and Online (but only on UO in early stages as a manager to help get it started). Glad you enjoyed them. I think I still have box copies around here somewhere.
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.
Yes, I was a huge fan of Ultima 7, 9 and Online.
I remember that incredible sense of freedom gave me a kind of liberation(?). It’s an honor to be able to have this conversation with you.
Thinking about how you were already grappling with pathfinding issues and addressing them in real-time back then makes me feel a bit envious. I’m sure there weren’t many people who could have had such experiences at that time.
It’s thanks to people like you with those experiences that today’s programming languages and skills have developed as they have.
My technical level is far below yours, but I want to complete a lightweight pathfinding algorithm for my project, no matter what.
Thank you for sharing such an inspiring story.
In addition to the other options posted here, you can do what 3D games do: they have polygons covering all navigable areas. You then find which polygons connect source to destination, then create lines/curves across them (you never have to path find within an area because other don't contain obstacles). The harder problem is creating these maps, but there are quite a few solutions to that (e.g. voronoi). You could use a quadtree, and your navigation graph would consist of the set of the deepest nodes.
Your current solution seems like it could be a minefield of edge cases.
It seems to be almost completed. Would you like to finish it together?
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 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).
Since I recently felt the limitations of the A* algorithm in my LIVE project, I am planning to proceed with this attempt.
As a result of discussing with many AIs, it was difficult to find existing cases.
As far as I have reviewed extensively, I have come to the conclusion that the A* algorithm also involves a lot of unnecessary computations, so I am trying to minimize such computations themselves.
Since I am continuously running the service in LIVE, I believe I will be able to thoroughly verify its performance.
For reference, the current LIVE service is utilizing a Mini PC equipped with an N100 CPU.
This is also an attempt to achieve performance based on minimal specifications.
A* searches on a generic weighted graph, there's no vertical, horizontal nor diagonal movements. The only thing that matters is which nodes exists and how they are connected.
If diagonals on a 2D-grid are forbidden, then you need to use the Manhattan distance as the heuristic.
Step 4 is going to be tough. How do you handle concave obstacles?
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.
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.
The blog post is lacking critical details stating what exactly the problem definition is. But making some assumptions, I believe the objective is to find a decently short path using less computation time than A*, rather than to specifically find the shortest path.
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
Oh! That’s exactly correct! It seems I didn’t explain it clearly enough.
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!
I’ve reviewed the source code.
It seems like starting with clear and accurate information about the obstacles could be an issue.
Also, if the obstacles become very large, preprocessing will likely be necessary.
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.
The algorithm for finding detour points is as follows.
In fact, I’ve improved it a bit through research:
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.
It seems that the A* algorithm is not delivering the performance I was hoping for, so I am trying a new approach.
Are there any existing cases, by any chance?
If not, I would like to hear your thoughts on this approach.
You're referring to a visibility graph.
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!
@jvanderbot
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.
Is there a nice way to handle the idea that a creature might have a better or worse memory or ability to build a model of the environment? That seems like it would be an interesting dimension to add to a creature.
Sure, if you held a deadline to my head and told me to do it, I'd just include obstacles that are "within their memory".
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.
The ability to reason about obstacles that you can’t see could be an interesting feature to add for a human-equivalent creature, although I guess it will be a real mess to simulate something as smart as a person, haha. But for example, if you know what a house looks like, you can probably speculate about where obstacles might be, depending on parts of the roofline that you can see. And might be wrong. And your odds of being wrong might be influenced by your familiarity with some region’s architectural conventions.
Yeah, that's an interesting 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.
Oh! This is it! This is exactly why I wanted to create a new algorithm!
If you want something that looks a little "more real" but doesn't involve complex management of memory, maybe try a bug algorithm. https://en.wikipedia.org/wiki/Bug_algorithm
It errs on the side of "stupid" but is much easier to implement.
Oh~ This is very similar to the concept I was thinking of. I don't really like the idea of exploring strictly in a clockwise direction, though. Thank you for the information!
The core optimization you're trying sounds fairly similar to JPA*, which I believe is fantastic on open maps but eh on dense ones.[0]
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...
[1] https://factorio.com/blog/post/fff-317
[2] https://www.youtube.com/watch?v=RMBQn_sg7DA
First, I understand that the JPA (Jump Point Search) family only works efficiently in static environments. This means it requires preprocessing to achieve high efficiency.
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.
It seems like this would do OK for open areas with a few simple obstructions. I'm not sure how it would do if there were complex obstructions. For instance, it's unclear how it would work if you were trying to pathfind through a maze.
@johnfn The approach I’m considering would be similar to how humans navigate: using only visible information to continuously infer and find the way in real-time.
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.
It would do just fine - but that's because OP is essentially grabbing on the intuition behind Visibility Graph search, which is (or was) a very common path planning algorithm using just obstacle boundaries.
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.
I also hope it works as well as you’re thinking.
It's not my idea. There's a bunch of video tutorials on it if you want to google around.
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.
The difficulty has always been in how many things you look at. Tiles or objects. With static maps you can quite easily structure things so that you don't have to look at very much at all. When things are dynamic tests such as 'look at the thing in the way' suddenly get harder because you have to determine for any given point A) is something in the way? and B) what is it?
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.
I was thinking this too, A* is a good general performance algorithm, it’s possible the poster found an algorithm that performs better on their use case, but doesn’t generalise as well as A*, custom path finding algorithms that take advantage of domain knowledge are pretty common!
It would be great if it could be applied universally, but it seems that accommodating all situations in the real world won’t be easy.
In the end, I feel like it might have to transition into the realm of inference, much like AI that mimics human reasoning.
This has been done, many times before, it turns out the neural network just learns a crapper version of A*, and of course, any domain knowledge from whatever environment it's in, there was a post on this very thing last year on hacker news.
Have a look at:
It goes from 0 all the way up to A*, then beyond. I think the new stuff is based on https://www.cs.tau.ac.il/~haimk/papers/sp-wea.pdf but I'm not sure since the paper isn't explicitly named in the video.I haven’t watched the video yet, but I really like the title: “on slow computers.” I'll give you feedback again after I watch it. The document you mentioned also seems to have a lot to learn from.
- Run A* on the optimistic pathfinding graph (no obstacles on the unknown cells).
- 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.
As far as I’ve researched, if there’s an assumption that there are no obstacles, the fastest way to select a straight path is Bresenham's Line Algorithm. If I’m mistaken about this, please let me know!
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.
> Among the outline information, select the optimal point for bypassing the obstacle. (This part is the core)
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,
Once you're inside such a shape, following the outline is not the optimal way around it (you'd waste time in the little alcoves at the top & bottom, and I could make those alcoves considerably more pathological, too). You'd want to head for one of the opening's corners.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.)
@deathanatos
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.
Unless the "outline" is like tensing a rubber band around the object. In that case, the collision would happen outside the convex part.
Anyway, the details are not enough for me to fully grasp the algo described.
You're referring to the "Convex Hull". And if you are inside a shape, drawing edges to the visibile vertices of the shape (until you're on the boundary of the convex hull) will easily get you a path out, and, bonus, will eventually draw a perfect shortest path to the end.
See: https://news.ycombinator.com/item?id=42608107#42626311
Imagine a maze or labyrinth, with the agent and the destination both inside of it. Is it useful to try to figure out the convex hull of the walls, even if it is effectively "the entire maze"?
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.
You can path-find using only vertices and a can-see function to generate a-star successors.
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.
Yeah, thank you! I couldn't find the right term.
Yes I have, I did something similar for a project naviagting in a space game.
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.
This can be improved on using visibility graphs. In that case, the complexity is only determined by the number of obstacles. https://en.wikipedia.org/wiki/Visibility_graph
I feel this is not needed if you tie-break nodes in Open to favour lower h-values. This leads to a node selection bias for deeper paths, which are more likely closer to the goal.
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.
On a sparse map, you can tune A* all day, but ultimately if your paths involve more than 1) vertices on the obstacles or 2) straight lines from src to (maybe some of) those vertices to goal, you have created suboptimal paths.
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.
> On a sparse map, you can tune A* all day, but ultimately if your paths involve more than 1) vertices on the obstacles or 2) straight lines from src to (maybe some of) those vertices to goal, you have created suboptimal paths.
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.
I don't think we're disagreeing
@wormlord
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.
It sounds like you're looking for Any Angle pathfinding. The fastest known algorithm for 2D grids is ANYA: https://ojs.aaai.org/index.php/ICAPS/article/view/13609
Oh! This seems like something even AIs haven’t suggested before. The fact that it attempts paths in real-time without preprocessing is what I like the most! I definitely need to research this further! I’ll definitely take a look at it. Thank you!
And for non-grids (arbitrary constant cost 2d meshes) you can use polyanya.
Hey there, it is a little bit ambiguous what you mean by "find an algorithm that performs better". Do you mean in terms of runtime, or in the "quality" of the path?
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...
1: https://youtu.be/HP4ObKlCe6w?feature=shared&t=360
Oh, I saw that blog too. It helped me a lot to be inspired. What I mean by "performance" is that I want to minimize preprocessing, and I want to minimize the amount of computation I can do even when I'm navigating in real time. I'll definitely watch the video you gave me. Thank you!
I think this part also needs to be considered. Many pathfinding algorithms, including A* , aim to find the optimal path. However, my goal started with replicating how humans visually find their way.
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.
So far, no one has mentioned "Bug Algorithms", which have a similar structure of (1) walk in the direction of the goal, (2) walk around obstacles as they are encountered, (3) leave the obstacle to proceed when some condition is met. They are very simple to implement (though not optimal) and there are a number of variants to play around with. Howie Choset has some good lecture slides that describe them [1]. However, as some others have mentioned, something like Jump Point Search [2] is likely a better option given the described scenario.
[1] https://www.cs.cmu.edu/~motionplanning/lecture/Chap2-Bug-Alg... [2] https://en.wikipedia.org/wiki/Jump_point_search
I've done that something like that.[1] It's appropriate where there's a significant cost to detecting obstacles, because it tests few unnecessary cells.
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...
Oh, thank you. I'll have to take a look at the source code as well.
Oh~ This is definitely worth referencing as well. Thank you for the information!
We used this algorithm in the RTS Outpost 2 in 1997. I think the original Command and Conquer did something similar.
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.
Oh, as expected, A* couldn't be fully utilized on older hardware. I can totally relate, as I’m running my server on a Mini PC with an *N100 CPU* right now.
Hearing stories about the challenges and solutions for low-spec hardware like this is incredibly fascinating.
Very similar to the pathfinder I wrote for Ultima in 1990. At the time I was too young and naive to know that there were lots of existing similar graph algorithms (this was before the internet and, more importantly, I was 20 years old and therefore already knew everything LOL).
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.
Wow~ You’re one of the developers of Ultima, a game I truly loved! The concept of using "highways" is really fascinating!
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!
Yes. I worked on Ultima 7, 8 and Online (but only on UO in early stages as a manager to help get it started). Glad you enjoyed them. I think I still have box copies around here somewhere.
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.
Yes, I was a huge fan of Ultima 7, 9 and Online. I remember that incredible sense of freedom gave me a kind of liberation(?). It’s an honor to be able to have this conversation with you. Thinking about how you were already grappling with pathfinding issues and addressing them in real-time back then makes me feel a bit envious. I’m sure there weren’t many people who could have had such experiences at that time. It’s thanks to people like you with those experiences that today’s programming languages and skills have developed as they have. My technical level is far below yours, but I want to complete a lightweight pathfinding algorithm for my project, no matter what. Thank you for sharing such an inspiring story.
In addition to the other options posted here, you can do what 3D games do: they have polygons covering all navigable areas. You then find which polygons connect source to destination, then create lines/curves across them (you never have to path find within an area because other don't contain obstacles). The harder problem is creating these maps, but there are quite a few solutions to that (e.g. voronoi). You could use a quadtree, and your navigation graph would consist of the set of the deepest nodes.
Your current solution seems like it could be a minefield of edge cases.
Yes, I’m also trying to explore as many options as possible. However, I do have a strong desire to minimize preprocessing as much as I can.
IMO, sounds like you want A* with JPS https://en.wikipedia.org/wiki/Jump_point_search
A* and JPS seem a bit different from the direction I’m aiming for.
It seems to be almost completed. Would you like to finish it together?
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.
https://github.com/Farer/bw_path_finding
Is this faster than A*?
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
Since I recently felt the limitations of the A* algorithm in my LIVE project, I am planning to proceed with this attempt. As a result of discussing with many AIs, it was difficult to find existing cases. As far as I have reviewed extensively, I have come to the conclusion that the A* algorithm also involves a lot of unnecessary computations, so I am trying to minimize such computations themselves. Since I am continuously running the service in LIVE, I believe I will be able to thoroughly verify its performance. For reference, the current LIVE service is utilizing a Mini PC equipped with an N100 CPU. This is also an attempt to achieve performance based on minimal specifications.
A* searches on a generic weighted graph, there's no vertical, horizontal nor diagonal movements. The only thing that matters is which nodes exists and how they are connected.
If diagonals on a 2D-grid are forbidden, then you need to use the Manhattan distance as the heuristic.
Step 4 is going to be tough. How do you handle concave obstacles?
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.
Thank you so much for providing an example related to the project!
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.
This is a visibility graph search. You can use the convex hull of any obstacle.
The blog post is lacking critical details stating what exactly the problem definition is. But making some assumptions, I believe the objective is to find a decently short path using less computation time than A*, rather than to specifically find the shortest path.
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
Oh! That’s exactly correct! It seems I didn’t explain it clearly enough.
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!
I wrote a similar algorithm for pathfinding around vector shapes in Javascript, the implementation was surprisingly simple.
https://github.com/Wazzaps/FastPathfinder
I’ve reviewed the source code. It seems like starting with clear and accurate information about the obstacles could be an issue. Also, if the obstacles become very large, preprocessing will likely be necessary.
Oh~ That’s awesome! I’ll start analyzing the source code! Thank you!
can you specify the algorithm in more detail?
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.
The algorithm for finding detour points is as follows. In fact, I’ve improved it a bit through research:
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
It seems that the A* algorithm is not delivering the performance I was hoping for, so I am trying a new approach. Are there any existing cases, by any chance? If not, I would like to hear your thoughts on this approach.
You should probably just use a quad tree to put your objects into and traverse that with a path finding algorithm.
Yeah, I thought about that too, but I'm also trying to keep pre-processing work as light as possible.