I’ve recently been cooking up some fun stuff trying to develop the best search AI. I’m tired of the seemingly lazy way that AI will give up on searching after a qualification such as “Time out of LoS” is achieved, and then they magically forget about it. Instead, I became determined to devise a way to solve this. And so, I have. My solution is simple, that instead of following a searching roam algorithm using randomly selected points over a proximity distribution to create psuedo intelligent search patterns for a period of time, instead my design searches the environment with EQS, forming a collection of convex shapes which include all areas which are currently out of the AIs line of sight. It then gets a set of all the places through the environment it can’t go. It selects these areas in order of proximity to eachother, finding the nearest point to the previous and tracing a path through the environment that eventually visits at least one point from which any given shape previously unseen is seen in it entirety.
Ive encountered a bit of a problem though as I try to improve this. One, is that occasionally shapes which have already been seen will be seen twice. I can tweak this through lazy approximation, and check if anywhere along the route is “close enough” and then look for a point near there which meets the qualifications. This works but everytime the route changes, this process becomes recursively more and more needed to create the perfect route. Secondly, the random chance is occasionally miraculously inefficient. I can solve this by generating 10 paths, and choosing the best among them. However, both of these solutions exponentially increase the processor time required to accomplish the goal as the size and complexity of the environment increases.
I’m posting this to see if I can hopefully inspire some more mathematically inclined coders here to assist me in determining a way to efficiently generate the shortest path through a grid, such that there exists on the path at least one point from which an uninterrupted line can be traced to each corner of any given concave shape, that does not intersect with any shape from another given set. Any kind of thought, even an incomplete answer is welcome in developing this new form of AI search pathing.