Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Introduction to the A* Algorithm (2014)

redblobgames.com

Post reply on HN
Print view View original

21–30 of 31 posts

Re: Introduction to the A* Algorithm (2014)

#21

Post by heavenlyblue »

Animats wrote: post #6

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 fa…

Uhm. 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.

Re: Introduction to the A* Algorithm (2014)

#23

Post by slingnow »

Animats wrote: post #6

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 fa…

How is this the top comment? This is just a flat out bad approach to pathfinding, as previous comments have pointed out.

Re: Introduction to the A* Algorithm (2014)

#24

Post by feoren »

I have bookmarked many Red Blob Games posts like this one, both because of their excellent content, but also as examples of how to write truly great tutorials. Well organized content, good CSS without over-styling, advanced JavaScript but only used in the exact right places: interactive demos, toggles to customize the content more to your use case (e.g. hex vs. square), and not to hijack my scroll bar or for unnecessary flashiness. This site is my go-to for inspiration on how to write a fantastic tutorial.

Re: Introduction to the A* Algorithm (2014)

#26

Post by Animats »

DizzyDoo wrote: post #16
Animats wrote: post #6

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 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…

sounds 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.

Re: Introduction to the A* Algorithm (2014)

#27

Post by DizzyDoo »

Animats wrote: post #26
DizzyDoo wrote: post #16

Earlier quoted context omitted.

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…

sounds 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.

That 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.

Re: Introduction to the A* Algorithm (2014)

#28

Post by self-symmetric »

A few years ago, I wondered whether it was possible to extend A* to pathfinding with momentum. It would require a consistent and admissible heuristic for Newtonian kinematics. It was a little tricky to find but it turns out that it does exist!

The code (and animations) are here: https://github.com/matthew-piziak/spacepath

It shows a spaceship finding time-optimal paths around asteroids, with nothing but A* doing the pathing.

Re: Introduction to the A* Algorithm (2014)

#30

Post by Animats »

DizzyDoo wrote: post #27
Animats wrote: post #26

Earlier quoted context omitted.

sounds 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.

That 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…

I 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/READM...

Post reply on HN