40 ms·

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

by setr 2y ago

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_Plus_An_Extreme_A_Star_Speed_Optimization_for_Static_Uniform_Cost_Grids.pdf http://www.gameaipro.com/GameAIPro2/GameAIPro2_Chapter14_JPS... [1] https://factorio.com/blog/post/fff-317 https://factorio.com/blog/post/fff-317 [2] https://www.youtube.com/watch?v=RMBQn_sg7DA https://www.youtube.com/watch?v=RMBQn_sg7DA

Farer 2y ago
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.

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*

by setr 2y ago

Farer 2y ago

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.