4 ms·
A* is less useful when you're not omniscient, that is, testing if a cell is blocked has a sensing cost. I ran into this in a game application. To find out if a
by Animats 5y ago
A* is less useful when you're not omniscient, that is, testing if a cell is blocked has a sensing cost. I ran into this in a game application. To find out if a cell is obstructed, I have to do a ray cast at a few points in the cell, which uses resources. A* requires sensing a large number of cells to collect non-useful data, and if you have a big, mostly open space with some obstacles, like the real world, it does far too much sensing.
So I ended up with a variant on Pledge's approach to wall-following. Head toward the goal until an obstacle is detected. Then, start wall-following, but simultaneously in both left and right directions. When one of the wall-follower tests can head towards the goal, do that, and kill off the other wall-follower. So you alternate between heading towards the goal in open space, cheaply, and wall following.
Searching both left and right simultaneously avoids taking the long way round some obstacles.
- adamc 5y agoGreat comment!
- 10000truths 5y agoYou can modify the A* cost function to take the sensing cost into account: f(x) = g(x) + h(x) Just becomes: f(x) = (g(x) + [past sensing costs]) + (h(x) + [estimate of future sensing costs])
- thaumasiotes 5y agoWhy are you including [past sensing costs] in g(x)? The sensing costs aren't part of the cost of following the path; they're a cost of calculating it.
- 10000truths 5y agog(x) represents the costs that have been incurred thus far, since the starting point. How you wish to quantify and evaluate that cost is up to you as the implementer. For spatial navigation purposes, most people opt for “cost = Euclidean distance traversed”, but if Euclidean distance is not the only thing you’re trying to minimize, then your cost function must take other factors into account.
- thaumasiotes 5y agoBut look, the goal is "find the path that costs the least to traverse". The stated problem with A* is "running A* is too expensive". Why mix the outside-the-universe cost of running A* into the within-universe cost of traversing the path? If you've already paid the cost of scanning a path, the cost of using the knowledge you gained from that is still zero.
- garaetjjte 5y agoFactorio solved this with hierarchical pathfinding: https://factorio.com/blog/post/fff-317 https://factorio.com/blog/post/fff-317
- Animats 5y agoRight, that's a low-end navmesh.
- cmehdy 5y agoThis reminds me of what the Death Stranding team presented at GDC regarding the pathfinding. They had LOTS of new issues for a game due to the unique nature of Death Stranding (obstacles, tripping, balancing) and they do an excellent job at outlining their approach. Video (51 mins): https://www.youtube.com/watch?v=yqZE5O8VPAU https://www.youtube.com/watch?v=yqZE5O8VPAU
- DizzyDoo 5y agoI'm a bit confused by your comment, when you say that "testing if a cell is blocked has a sensing cost", do you mean the obstacle/wall is not in your graph at the point of search? A properly calculated navmesh by definition has the obstacle/wall 'cut out' of the mesh (or otherwise represented in a modifier area). Perhaps I've misunderstood you but it sounds like you're trying to build, at least partially, the navmesh as you search? If you're rather talking about temporary obstacles like other nav agents that need to be avoided, there are a number of approaches to agent avoidance that work nicely on a subset of a navgraph.
- Animats 5y agosounds like you're trying to build, at least partially, the navmesh as you search? Yes. I'm coding non-player characters, using an API which lets them sense their surroundings by ray-casting but does not give them direct access to the system's world model. They're limited in what they can sense.
- DizzyDoo 5y agoThat sounds like an issue (and a big issue at that) with the API your engine is providing to you, rather than an issue inherent in A*! Building/rebuilding a navmesh is the expensive bit, cell look-ups ought to be essentially 'free', performance-wise. In an engine like Unity a physics raycast is a super expensive call to make, so if that's also the case for your situation then that's a real shame, I hope you can work around that. If I'm doing regular "were are other objects relative to an object" I much prefer an ordered-spatially data structure like a quadtree, but doing a quick hash of the position and sticking it in a key based store works fine too. Again, that's one of those data structures that is expensive to build and cheap to query, so only building it once every x frames is probably a good idea. But again, not sure what your API is giving to you and how low level you get to work.
- Animats 5y agoI could go into more detail, but it would be off topic and lengthy. If you really are interested, see [1] [1] https://github.com/John-Nagle/lslutils/blob/master/npc/README.md https://github.com/John-Nagle/lslutils/blob/master/npc/READM...
- viseztrance 5y agoI've been working on a video game and actually followed the article to implement astar. If you have an inaccessible node, astar will indeed scan everything. But to get around this I only had to add a limit to the number of frontier iterations which was just a conditional.
- heavenlyblue 5y agoUhm. What you had to do instead of ray casting in real time: - build a graph of connectivity of all areas of the map OFFLINE - make sure that graph also has information about disconnected components and never apply A* to points which are disconnected from each other Do A* on that graph.
- slingnow 5y agoHow is this the top comment? This is just a flat out bad approach to pathfinding, as previous comments have pointed out.