Pathfinding | Hacker News Reader

Pathfinding

juhrjuhr.itch.io

155 pointssebg46 comments

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!

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.

Indeed. There is something satisfying about building these and watching them in full flow.

A couple of years ago, I completed a pathfinding assignment designed by David Churchill (https://www.cs.mun.ca/~dchurchill/) for his Algorithmic Techniques for AI course. I'm not a student, and only his students have access to the actual assignment files, so I made a faithful recreation of it by looking at slides he had on a video at the time. The assignment is about pathfinding on a 2D grid. That's fun enough, but I've wanted to put my own spin on it.

Over the past few weeks, I revisited this and applied it to real-world mapping data from OpenStreetMap instead. It uses OverPass API (https://dev.overpass-api.de/) to fetch the data, which is free to use. The data loading times can be a little unpredictable, especially for larger search areas, but I'm happy with it how it turned out. You can find it here if you're interested: https://johnh.co/projects/openstreetmap-pathfinding/

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: visualizations, yeah, it’s really easy to caught up in playing with the algorithm just to watch it run rather than using it in your project. Been there, did that. For two distinct projects.

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.

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

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/

True, but mind the search space size.

You can go through 50-80k search nodes in 10ms in a modern CPU, so even using Dijkstra seems feasible on a decent implementation as the grid used in the animations seems to have 100x80 nodes.

If I was making a game I'd focus on gameplay first, since giving the game some life by conditioning the paths seems more important to have a good game than achieving 200μs search times. Luckily, I'm not making a game :P, my current side-project is writing my own pathfinding playground to explore optimisation techniques and tools.

"This kind of efficiency problem is something that looks ripe for multi-threading, but the main problem I had here is that all the world state of the game is held on the main thread and in complicated structures"

Crazy idea but I wonder if it would be worth it to have the pathfinding thread simply have its entire own copy of the mutable world state. Then when anything changes the world, both copies are updated roughly in parallel.

It would be a ton of duplicate work, but if you're on a machine with cores sitting there doing nothing... why not?

Thought here: If I'm reading this right the cache remains valid unless something is done to the world state. Thus how about dumping the cache when the world is altered, the separate thread simply sits there rebuilding the cache. If an object should move one unit but the cache isn't there simply note the movement but don't update it. Next time around when you find the entry in the cache you move it two units. Given the stated calculation times I would think the user would not see this.

Pathfinding in general doesn't allow a lot of multi-threading. You can do bi-directional search, but it doesn't always work as good as it seems on a 2D maze[0], and adding workers beyond the 2nd requires being really good at guessing mid-points, but it's doable in domains with sub-goals.

[^0]: Not the case here, but some domains branch too much when going backwards and can easily explore states unreachable from the start.

Yes, threading within your pathfinding code is hard. But in this case I'm suggesting running all of pathfinding on one thread separate from the main game thread.

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 POIs, crossroads and corners that one can work with. Others might need some heuristics to determine those or merge together paths. It might also be worth trying to use a very coarse logic for gross movement but adjust the actual path moment to moment, but that's just an idea that I never tried.

The approach in the article is of course very dynamic, which has the advantage of being excellent at trying stuff out and visualizing it.

I personally never tried out the space partitioning mentioned in the article and don't understand it fully. But there might be strong similarities to what I described above.

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.

I remember fondly messing around with some pathfinding with some friends in my 20s and adding random amounts of cost to nearby nodes. This has the distinct effect of making NPCs meander around, or follow a "drunken path."

I like this idea. One could imagine certain types to skew the costs for interesting reasons. Small animals might want to move in a sort of scanning, zig-zag way for example.

Yes! Very creative thought. I hadn't tried abstracting the idea to other types of "effort."

I'm surprised it takes several milliseconds to find a path.

We've been using A* to find paths in games for over 20 years now. We did it on CPUs with speeds measured in Mhz. Higher clocks and architecture improvements mean we're a couple orders of magnitude faster. How is it that it takes so long to operate on modern hardware?

Games typically precomputed much of the pathfinding information and assumed a non-destructible world. The whole thing in the article about recomputing the blocked/non-blocked state is a thing many games with pathfinding simply didn't do at runtime at all.

They usually pathfinding on a larger granularity with more of the world aligned to a larger grid. Since asteroids are so organically shaped and freely movable in this case, it necessitates a finer pathfinding grid. It looks like they're roughly 6-8 pixels here. In an older game, it could easily be 16 or more. Pathfinding cost scales quadratically as the grid gets finer.

Also, while CPU speeds have increased, RAM access rates have not kept up. It's quite hard to actually keep the CPU busy and not have it stalled waiting for memory very often. "Data-oriented design" is a whole little subfield dedicated to dealing with this problem.

You probably realized its absurd to have 50000 square nodes in your pathfinding graph and instead divided the area into 50 convex polygons (if that). Convex polygons being the basic shape because you can go directly from every point within to every other point within.

Yeah generally you'd use a visibility graph/navmesh. I don't know why people keep trying to do path finding on a dense grid --- even with quadtree-based space partitioning, you might still end up with a complexity dependent on how far apart things are, rather than how many things there are.

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.

I'm guessing it might be multiple paths for multiple NPCs. But not sure.

And if you were performance conscious, you certainly would not do lots of pathfinding from scratch on every frame.

One of the first games I ever played was Warcraft I, and it was one of the games I always wanted to make but never could. One of the missing pieces of the puzzle was path finding. I still don't understand it, but at least now I have two resources that I can read when I'm done building my game maker and ready to make my game!

WC1 has fairly blocky movement and is grid based. It seems like units literally move from tile to tile so to speak.

If this is actually the case, you could try the Lee algorithm: https://en.wikipedia.org/wiki/Lee_algorithm. It's extremely simple and effective.

You might want to try adjusting it for diagonal movement and you probably don't want to store obsolete path sections, but only turns.

When I saw the GIFs in the blog post, I thought the goal of the game is to move asteroids around to prevent AI from finding a path to some goal. Would be an interesting concept.

What language are you using? For a small number of objects, it should be completely insignificant to performance to recompute the whole A* algorithm every frame without any form of caching. I'm surprised...

So interesting !

I made custom pathfinding solution before. How about considering my project too ?

https://github.com/Farer/bw_path_finding

One efficiency update you can make is that if background objects don’t move, then you don’t need to recalculate the path. So check if anything moved before recalculating.

Sure, but in games sometimes improving the average case is less important than the worst case.

So you're saying everything always moves all the time so it's more efficient to just never check and have the algorithm assume something moved always.

For most real time systems, including many games, it doesn't matter if one is more efficient than another because what matters is the predictability that comes from always rendering a complete frame in 1/60th of a second.

In many cases checking if absolutely nothing changed in a system isn't trivial either. You either have very fine grained tracking which involves a great deal of complexity and increased memory cost, or very broad tracking which results in a lot of false positives.

No, if it takes 1 ms to check if things have moved, and 5 ms to do the pathfinding then the worst case is 6ms when something moves. A guarantied 5 makes for a more stable frame rate than a sometimes 1ms, sometimes 6ms calculation. Often times 60 FPS average with high variability feels worse than 30 FPS with low variability.

That's true until the map itself changes, eg other objects moving around in the calculated path

Yeah I said that. If nothing moves. No need to change.

Interesting take. Make sure there are mineral eating aliens sleeping inside the asteroids :D

Reply on news.ycombinator.com