News for hackers. Stuff that matters.
Re:Ask HN: Have you ever seen a pathfinding algorithm of thi... by setr on Tuesday January 07, 2025 @02:12PM (#42626116)
The core optimization you're trying sounds fairly similar to JPA*, which I believe is fantastic on open maps but eh on dense ones.[0]

Maybe take a look at HPA* (hierarchal A* - partition the map, pathfind on high-level map, then pathfind at lower granularity).

You can also encode into the hierarchy information about whether a rabbit exists in the chunk in the first place, to reduce the initial search for nearest-rabbit.

Factorio had a good blog post on it [1], and Rimworld too but it also enabled arbitrary-sized partitions. [2]

I'm kind of just guessing based on your basic description though; what's the full scenario in mind?

[0] http://www.gameaipro.com/GameAIPro2/GameAIPro2_Chapter14_JPS...

[1] https://factorio.com/blog/post/fff-317

[2] https://www.youtube.com/watch?v=RMBQn_sg7DA

Re:Ask HN: Have you ever seen a pathfinding algorithm of thi... by Farer on Tuesday January 07, 2025 @09:41PM (#42630319)
First, I understand that the JPA (Jump Point Search) family only works efficiently in static environments. This means it requires preprocessing to achieve high efficiency.

What I'm aiming for, however, is a real-time scenario where such preprocessing is not strictly necessary. I want to implement something akin to how many creatures with human-like vision navigate using only partial information, just as humans do in real-life situations.

Currently, trees are appearing and disappearing dynamically. In the future, such situations are expected to occur more frequently, so I am aiming to create a lightweight solution that can handle these changes in real-time.

As you mentioned, for cases like rabbits, their location information is already preprocessed and divided by zones. Since this is a small task, it doesn't impose a significant burden on the system. This information is intended to be used when wolves are searching for rabbits.

Additionally, I have recently been considering processing even smaller zones than the current ones to handle the vision of wolves more effectively.