Ok, do you know how breadth-first search works? This uses a breadth-first search but then the AI does line-of-sight checks while moving, to determine the waypoint that is closest to the target but that the AI can still see from its position.
Usually in a breadth-first search you would store some kind of direction value for each checked position that tells you the direction it was checked from, but this doesn’t store any direction values at all.
Instead, the order in which positions are checked tells you how close they are to the target—if a position is checked and found empty then it’s added to a list, and since each position is checked before expanding its neighbors, positions closer to the target will be closer to the start of the list than positions further from the target.
Then the AI simply searches the listed positions in order, and the first position it can see, it stops checking and aims for that one.
1 Like