Really enjoy your works.
Thank you!
Introduction to the A* Algorithm (2014)
11–20 of 31 posts
Re: Introduction to the A* Algorithm (2014)
#12I used to be obsessed with the programming game Screeps and read most of these blog posts when they were still published on the authors stanford pages- there's a lot of great stuff in there.
Screeps is fascinating but I never got motivated to play it. :(
I use the Stanford pages [1] to link to interesting papers and I use Red Blob Games to explore interactive ways of presenting topics. The most recent update to the Stanford pages is from 3 weeks ago, about any-angle pathfinding [2]. But most of what I do these days is on the Red Blob Games site. I probably would've kept using the Stanford pages but they have a 100MB quota limit and I was running out of space…
[1] http://www-cs-students.stanford.edu/~amitp/gameprog.html may be the oldest surviving game development website, as I started it in either 1994 or 1995. Older than Google or Wikipedia or even Slashdot. [2] http://theory.stanford.edu/~amitp/GameProgramming/Variations...
Re: Introduction to the A* Algorithm (2014)
#13Re: Introduction to the A* Algorithm (2014)
#14A* 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 fa…
This 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
Re: Introduction to the A* Algorithm (2014)
#15A* 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 fa…
You 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])
Why 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.
Re: Introduction to the A* Algorithm (2014)
#16A* 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 fa…
I'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.
Re: Introduction to the A* Algorithm (2014)
#17Re: Introduction to the A* Algorithm (2014)
#18Earlier quoted context omitted.
You 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])
Why 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.
g(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.
Re: Introduction to the A* Algorithm (2014)
#19Earlier quoted context omitted.
Why 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.
g(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.
But 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.
Re: Introduction to the A* Algorithm (2014)
#20A* 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 fa…
I'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.