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

Pathfinding

juhrjuhr.itch.io

Post reply on HN
Print view View original

31–40 of 48 posts

Re: Pathfinding

#31

Post by porphyra »

chrisdalke wrote: post #5

Writing path planning code is one of the most enjoyable programming tasks. Love the visualizations. The path following code is also interesting because I bet you'll run into some corner cases where the A* path thinks a path is feasible, but the vehicle overshoots and hits something. Although in a game I guess that adds to the fun & chaos.

You might be able to add velocity information when doing the A* search, as well as use minkowski sum to make sure that it never tries to squeeze through too tiny a gap.

Re: Pathfinding

#32

Post by juhrjuhr »

johnh-hn wrote: post #29
juhrjuhr wrote: post #22

Hello! I'm the developer of this game. Thanks very much for your interest and discussion here :) I'm starting to feel like I didn't go into enough detail with my post, since there's a lot I could talk about and also a lot I could benchmark to give you some actual numbers on performance. But maybe I'll leave that for a different post in the future. The game I'm developing is a commercial project, so it would be silly…

This is a cool concept. How long have you been working on it? And do you have a rough idea of when you'll release it?

Thank you! At the moment, about 7 months (I originally thought it would take 4-6 months haha). I'm really hoping to release it in the next couple of months, but my ability to estimate these things is obviously lacking.

Re: Pathfinding

#33

Post by johnh-hn »

juhrjuhr wrote: post #32
johnh-hn wrote: post #29

Earlier quoted context omitted.

This is a cool concept. How long have you been working on it? And do you have a rough idea of when you'll release it?

Thank you! At the moment, about 7 months (I originally thought it would take 4-6 months haha). I'm really hoping to release it in the next couple of months, but my ability to estimate these things is obviously lacking.

You're being consistent and that's the most important thing. I hope we see it again here once it's complete. Good luck!

Re: Pathfinding

#34

Post by dgb23 »

Sharlin wrote: post #15
dgb23 wrote: post #9

Neat article! This will depend on the type of game or application, but one thing I've been doing is to do the more rigorous pathfinding when the environment (collision map) changes in order to generate a sort of precomputed pathfinding map (grid, or graph). When I search a path, or route for an entity, then it's on that pathfinding map. Again, it depends on how that simulation fundamentally works. Some have natural P…

What you refer to is commonly called a navigation mesh: https://en.wikipedia.org/wiki/Navigation_mesh

Conceptually yes, thanks! But it seems like my implementation is more basic than that. I'm only using the graph part so to speak, because of other constraints.

Re: Pathfinding

#35

Post by jvanderbot »

chrisdalke wrote: post #5

Writing path planning code is one of the most enjoyable programming tasks. Love the visualizations. The path following code is also interesting because I bet you'll run into some corner cases where the A* path thinks a path is feasible, but the vehicle overshoots and hits something. Although in a game I guess that adds to the fun & chaos.

Take it from an old hand: you want to add a tad of circular margin to your obstacles via minkowski sum.

Re: Pathfinding

#36

Post by taneq »

tavianator wrote: post #27
juhrjuhr wrote: post #22

Hello! I'm the developer of this game. Thanks very much for your interest and discussion here :) I'm starting to feel like I didn't go into enough detail with my post, since there's a lot I could talk about and also a lot I could benchmark to give you some actual numbers on performance. But maybe I'll leave that for a different post in the future. The game I'm developing is a commercial project, so it would be silly…

You may want to look into improvements to A* for grids, like Rectangular Symmetry Reduction.

Also jump point search: https://zerowidth.com/2013/a-visual-explanation-of-jump-poin...

Re: Pathfinding

#39

Post by pton_xd »

Nice! There's a few techniques that I remember when doing something similar. Subgoal graphs [0], using precalculated landmarks in the heuristic [1], and theta* [2] may be worth looking into. A bunch of other variations and techniques are on the Red Blob Games site [3]. Also the priority queue implementation you use can really impact performance if it's not done well.

[0] https://www.gameaipro.com/GameAIPro2/GameAIPro2_Chapter15_Su...

[1] https://www.redblobgames.com/pathfinding/heuristics/differen...

[2] https://web.archive.org/web/20190717211246/http://aigamedev....

[3] https://theory.stanford.edu/~amitp/GameProgramming/

Re: Pathfinding

#40

Post by dietr1ch »

taneq wrote: post #36
tavianator wrote: post #27

Earlier quoted context omitted.

You may want to look into improvements to A* for grids, like Rectangular Symmetry Reduction.

Also jump point search: https://zerowidth.com/2013/a-visual-explanation-of-jump-poin...

If just use A*, but you rank open to loop for lowest (f, h) pairs, then the search frontier just dives despite having multiple optimal paths, as the new node tie-breaking ensures we prefer nodes that seem closest to the goal.
Post reply on HN