AI: Smarter pathfinding for choosing nearest item?

[Veyda]

Not as much a bug as unoptimal and possibly unintended behaviour.

From the actions of colonists, it looks like that when selecting the nearest location (which meal to eat, which item to get to begin work on a bill, which stockpile of equal priority to put the item into etc) the AI does a simple |x1-x2| + |y1-y2| search to yield the item that's theoretically closest when going in a straight line.

In case of non-trivial pathing (a large base with multiple hallways), this can lead the AI to select an item that's much further away than optimal, wasting incredible amounts of time.

This extremely annoying behaviour can be improved on by doing a more costly search that radiates out from the colonist and takes impassable squares into account.

EDIT: Actually.. ideally, not only impassable squares, but also the cost of traversing the passable ones - for example, an item outdoors may be closer to get to, as far as the number of squares traveled, but is in deep snow in a swamp, so it will take more time to get to.

EDIT2: At this point, it's already more of a suggestion, so.. It would be neat if the AI also looked ahead at its job queue's next task - for example, not only where the item needs to be taken from, but also where it needs to go, thus taking the full roundtrip into consideration, but this could turn into a major CPU hog if unoptimized.

[Tynan]

Actually they only do radial searches sometimes. For the simplest searches, they do a proper BFS traversal through the region graph.

For meals, for example, its because the algorithm trades off various aspects of the food to find the best one (e.g. they'll search further to get a lavish meal than raw meat). Doing this along paths would be somewhat more difficult and I haven't done it yet.

Anyway you're right it is a suggestion, I'll write down a todo to perfect this in the cases it's not done (as there are several old bits of code that don't use region traversal when they could). Thanks.