41–50 of 77 posts
We are now at the final stage. When looking for a detour in the direction blocked by the map boundary and failing to find one, the program attempts exploration on the opposite side. It's getting very close to being complete.
In such cases, humans cannot see the back side of obstacles. Additionally, there are situations where the exact destination may not be known. They simply infer based on what they can see in front of them. "There's an obstacle over there. Which way would be better to go around?" My approach began from this perspective.
This flow of pathfinding is entirely different from A*. So, the algorithm has been modified a bit now. I changed it so that it does not investigate the entire shape or full outline of obstacles. The flow is as follows:
1. Attempt to move in a straight line in the direction I want to go. 2. Detect an obstacle. 3. Explore the visible outline of the obstacle, focusing on the side that seems closer to the destination. 4. When reaching the endpoint of the outline, select an appropriate detour point nearby.
The final detour point will, of course, be a location where a straight-line movement from the starting point avoids hitting the obstacle. Once I reach the detour point from the starting point, I repeat the process.
Earlier quoted context omitted.
I feel this is not needed if you tie-break nodes in Open to favour lower h-values. This leads to a node selection bias for deeper paths, which are more likely closer to the goal. If you look at runs, this tie breaking makes A* behave like a greedy algorithm in the absence of obstacles and simply follow a straight path if there's one, and act sort of cleverly when there's a small detour.
On a sparse map, you can tune A* all day, but ultimately if your paths involve more than 1) vertices on the obstacles or 2) straight lines from src to (maybe some of) those vertices to goal, you have created suboptimal paths. The idea goes: Best to just search in that space vs iterating over some other space attempting to indirectly coax out the optimal path. The bonus is that VG-based search is very fast b/c it does…
You would still be choosing a node with the best f-value, so you'll get optimal solutions with any admissible heuristic. In a 2D-grid your heuristic should also be consistent, which will result in pretty good behaviour.
You're referring to a visibility graph. https://en.wikipedia.org/wiki/Visibility_graph On a visibility graph you can run any search algorithm. The key thing is this graph is sparse (the number of nodes is really limited by the amount and complexity of the obstacles, not the distances). This algorithm follows almost perfectly your outlined steps. In particular it draws a line to the destination, and if it encounters a…
Ah, I did hear about the Visibility Graph through AI. I didn’t fully understand it due to my lack of knowledge. But with you bringing it up again, I think I should look into that as well. Thank you for your kind response.
Earlier quoted context omitted.
Is there a nice way to handle the idea that a creature might have a better or worse memory or ability to build a model of the environment? That seems like it would be an interesting dimension to add to a creature.
Sure, if you held a deadline to my head and told me to do it, I'd just include obstacles that are "within their memory". Expire them by time, refresh them by range (can see as they move). Constantly replan and I bet you'd get something reasonable looking, but _only_ if you add an obstacle that represents only what the creature can see. If you add the whole obstacle (regardless of what it can see), it'll just do the o…
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-rabb…
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.
- Run A* on the optimistic pathfinding graph (no obstacles on the unknown cells). - Follow the path found (if there's none, that's it) - As you follow the path, sense the world and take note of new obstacles. - If there's an action you can't make because of a new obstacle, re-run A . There's ways of re-using the state from previous A runs (as long as the goal is still the same) that becomes handy on complex maps wher…
In my project, since I don’t need to guarantee complete real-time processing, there isn’t an absolute necessity to find paths as quickly as possible. However, since many entities need to find paths simultaneously, I’d like to keep the computations as minimal as possible.
It might be similar to what you mentioned about algorithms being fast enough on low-spec hardware. In my case, I’m currently using an ultra-low-power Mini PC with an *N100 CPU* as a server. This choice not only helps me study methods to optimize performance but also satisfies my curiosity about fully leveraging the advantages of *MSA (Microservice Architecture)*-based services.
It seems like this would do OK for open areas with a few simple obstructions. I'm not sure how it would do if there were complex obstructions. For instance, it's unclear how it would work if you were trying to pathfind through a maze.
It would essentially break down the flow of how humans navigate into small, incremental steps. Look with their eyes, make a judgment, move, and repeat the process again and again...
Of course, trial and error could also occur. This might actually make it feel more natural.
It seems like this would do OK for open areas with a few simple obstructions. I'm not sure how it would do if there were complex obstructions. For instance, it's unclear how it would work if you were trying to pathfind through a maze.
It would do just fine - but that's because OP is essentially grabbing on the intuition behind Visibility Graph search, which is (or was) a very common path planning algorithm using just obstacle boundaries. The algorithm in a maze would just use "intersections" as successors, rather than "Next next step down the hall". This is, in fact, an optimal search algorithm for this problem, and scales much better than any gri…
It seems like this would do OK for open areas with a few simple obstructions. I'm not sure how it would do if there were complex obstructions. For instance, it's unclear how it would work if you were trying to pathfind through a maze.
I was thinking this too, A* is a good general performance algorithm, it’s possible the poster found an algorithm that performs better on their use case, but doesn’t generalise as well as A*, custom path finding algorithms that take advantage of domain knowledge are pretty common!
In the end, I feel like it might have to transition into the realm of inference, much like AI that mimics human reasoning.