Finding the nearest object, considering obstacles

Question

For the purposes of this question, we'll assume it involves a Janitor assigned to clean up trash in a building. Given that it is a building, it is safe to assume there are one or more rooms, walls, etceteras that act as physical obstacles.

It's time for the janitor to earn his paycheck, and he heads to the nearest piece of trash to clean up. We can resolve this in two ways:

1. The cheap way. Simply do a distance check and head to the nearest.
2. The expensive way, Path-find to pieces of trash and pick the one with the easiest/shortest route.

Now, (1) is cheap computationally but can give false results. A piece of trash could be on the other side of a wall but only 3 "squares" away - it'll actually take the janitor a lot more time to get there then say, a piece of trash in the same corridor 5-squares away.

(2) would give more accurate results, but requires a metric-ton more computation.

Are there better approaches to "nearest thing", or would you just have the janitor wander around on a pre-set route that covered "as much as possible" and just have him clean up as he goes?

Answer 1

If you have rooms and corridors separated by walls and inter-connected by doors you can assume each door is a node in a graph. The door-graph can be pre-computed, with costs equal to the distance between the doors. You create a cost graph, including the minimum costs from the janitor to each door based on the current position of the janitor and the constant distances between the doors. Then for each pile of trash, you check all the doors in the same room and pick the minimum cost (that cost is the distance from the janitor to that door + the distance from the pile of trash to that door). After that, you just pick the pile of trash with the minimum cost.

It is still a path-finding algorithm, but I think it will work pretty fast, even for massive amounts of data, but I don't think one janitor can clean that much trash :).

Hope it helps.

Answer 2

Well this is assuming that this janitor is some form of god who knows where all the trash is. Pathfinding to every piece to figure out distance is a pretty bold move for someone undercover. In fact he may consider using something such as A* to figure out the nearest objects.

Instead let's look at it from an alternative perspective:

The janitor knows he must clean, but does not know where there is trash. The janitor must then go search for trash to clean.

Now this janitor could either clean as he goes, or he can scout things out first. Using a grid system similar to the A* pathfinding above, you could create a grid that constantly searches outwards until it finds trash, starting with the janitor.