0
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ You actual question is really opinion based, and really depends on the context. Having a janitor actually search for trash is not quite the same thing as a janitor who just walk around and pick up trash. It's a totally different behaviour. \$\endgroup\$ – Alexandre Vaillancourt Feb 22 '14 at 13:08
  • 1
    \$\begingroup\$ Also, if your janitor has to go from his actual location to the trash in situation (1), he'll know which trash is the closest, but, based on that, he'll try to go through the wall? How will he know the path he'll have to follow to get to that thrash? From your question, you'll still have to implement a path-finding algorithm anyways. \$\endgroup\$ – Alexandre Vaillancourt Feb 22 '14 at 13:09
  • \$\begingroup\$ ^ This comment nails it so hard. What have you tried? \$\endgroup\$ – MickLH Feb 22 '14 at 13:20
  • \$\begingroup\$ See the cheap way \$\endgroup\$ – MichaelHouse Feb 22 '14 at 15:52
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ After I posted my question and did a bit more work, this is kind of the solution I arrived at. Rather than "search the building for trash", the Janitor checks rooms one by one (with a "last checked time"), and once in a room, sorts trash by distance and then path-finds to nearest. Works pretty well, so ended up being a combination of both. \$\endgroup\$ – Moo-Juice Feb 22 '14 at 14:40
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.