3 ms·
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 r
by jvanderbot 2y ago
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 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.
- bee_rider 2y agoThe 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.
- jvanderbot 2y agoYeah, 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.
- Farer 2y agoOh! This is it! This is exactly why I wanted to create a new algorithm!
- jvanderbot 2y agoIf 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 https://en.wikipedia.org/wiki/Bug_algorithm It errs on the side of "stupid" but is much easier to implement.
- Farer 2y agoOh~ This is very similar to the concept I was thinking of. I don't really like the idea of exploring strictly in a clockwise direction, though. Thank you for the information!