Hey, I'm the developer of the game in the blog post. What takes several milliseconds is the number of world queries that need to be made to detect blocking objects and also object proximity. This is why I went with a quad tree to try to speed that part of things up.

Once those queries have been made the actual search is very fast. The problem then is that those queries need to be made again due to the dynamic nature of the game world.

This definitely happens! Mostly it's from the NPC taking a corner a little too quickly when there's obstacles around. I've added data to the resulting path so that the NPC can know how far each path step is from an obstacle so that it can slow itself down first.

Like you said, it adds a lot to the fun so I'm only trying to smooth out those cases that look stupid.

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 to be on the front page of HN and not try to direct people towards the commercial side of things. Here is the link to the game's steam page, you can wishlist and maybe buy the game when it's released so I can afford living expenses and expensive coffee beans: https://store.steampowered.com/app/3656660/Deep_Space_Exploi...

Thank you! :)

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.

afaik jump point search would work for uniform cost grids but not if there's the exponential term that OP has

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!

Great particle effects! Wishlisted and waiting!