Re:Ask HN: Have you ever seen a pathfinding algorithm of thi...
by bee_rider on Tuesday January 07, 2025 @04:43PM
(#42627934)
The ability to reason about obstacles that you can’t see could be an interesting feature to add for a human-equivalent creature, although I guess it will be a real mess to simulate something as smart as a person, haha. But for example, if you know what a house looks like, you can probably speculate about where obstacles might be, depending on parts of the roofline that you can see. And might be wrong. And your odds of being wrong might be influenced by your familiarity with some region’s architectural conventions.
Re:Ask HN: Have you ever seen a pathfinding algorithm of thi...
by jvanderbot on Tuesday January 07, 2025 @05:09PM
(#42628233)
Yeah, that's an interesting problem.
I've worked in planning for a bit, mostly for robotics. I can honestly say that the _planning_ side of making interesting behaviors is really simple. It's the world representation that is hard. In the real world it's hard to build up a good enough representation to do smart things. Most robots can't reasonably see longer than 50 yards/100 yards. In games is hard to build up a bad enough representation to match the partial information in the real world - running just about any planner on the map will just work and probably look too good.
Re:Ask HN: Have you ever seen a pathfinding algorithm of thi...
by Farer on Tuesday January 07, 2025 @09:28PM
(#42630233)
Oh! This is it! This is exactly why I wanted to create a new algorithm!
Re:Ask HN: Have you ever seen a pathfinding algorithm of thi...
by jvanderbot on Wednesday January 08, 2025 @07:10AM
(#42633355)
If you want something that looks a little "more real" but doesn't involve complex management of memory, maybe try a bug algorithm. https://en.wikipedia.org/wiki/Bug_algorithm
It errs on the side of "stupid" but is much easier to implement.
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 optimal thing, which is fine but may not "look right". So clip visibility with obstacle, add that, and union it with all known obstacles, then replan. Keep it fast by doing a union "in place" with known obstacles so your obstacle list doesn't grow unbounded.
You can imagine it would walk toward the goal until it sees a wall, then it would go either left or right for a step, then back for two steps, then left for 4 steps, then back for 8 ... because the A* "frontier" keeps expanding so it keeps searching along that frontier.
And if you're lucky, you just discovered the optimal search variant of the "Drunkards walk" search problem.