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

41–48 of 48 posts

Re: Pathfinding

#41

Post by dietr1ch »

munificent wrote: post #19

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

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.

Re: Pathfinding

#42

Post by dietr1ch »

pton_xd wrote: post #39

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

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.

Re: Pathfinding

#43

Post by SuperV1234 »

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

Re: Pathfinding

#44

Post by munificent »

dietr1ch wrote: post #41
munificent wrote: post #19

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

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

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.

Re: Pathfinding

#45

Post by porphyra »

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

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

Re: Pathfinding

#46

Post by LorenPechtel »

munificent wrote: post #19

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

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.

Re: Pathfinding

#48

Post by lostmsu »

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.
Post reply on HN