protected void addLevelStepToQueue(final Route route,
			final Queue<Route> outRouteQueue) {
		// As a first check, see if this route completes the level. If it does,
		// we want it in the queue immediately so we can use the queue to find
		// the fastest solution for us. Additional, non-O(log n) pruning is a
		// waste of time in this case.
		final Game game = route.getFinalState();
		final Player player = game.getPlayer();
		if (player.isInCastle()) {
			outRouteQueue.add(route);
			return;
		}

		// Next, make sure it isn't completely stupid. If it is, don't bother
		// looking at it further.
		if (pruneIndividual(route)) {
			return;
		}

		// Now go through all of the existing routes and see if this one
		// duplicates any of them. If it does and it's slower, don't add it to
		// the queue. If it does and it's _faster_, take the old run out. As
		// long as this method is called consistently, there won't ever be more
		// than one duplicate run in the queue.
		//
		// To minimize the amount of time wasted doing this, use a collection of
		// routes that are pre-sorted by how far the player has progressed
		// through the level. That way, we'll only have to check the routes that
		// have already made the same progress.
		Route badExistingRoute = null;
		HistoryEntry badExistingHistory = null;
		boolean shouldAddRoute = true;
		final int completionCode = player.getLevel().getCompletionCode();
		Collection<HistoryEntry> historyForCode = levelSnapshotsByCode
				.get(completionCode);
		if (historyForCode == null) {
			historyForCode = new ArrayList<>();
			levelSnapshotsByCode.put(completionCode, historyForCode);
		} else {
			final HistoryEntry existingEntry = findEquivalentHistoryEntry(
					route, historyForCode);
			if (existingEntry != null) {
				shouldAddRoute = (route.getTotalTime() < existingEntry.cumulativeTime);
				if (shouldAddRoute) {
					badExistingHistory = existingEntry;
					badExistingRoute = existingEntry.backReference;
				}
			}
		}

		final long queueOpsTimeStart = System.nanoTime();
		if (badExistingRoute != null) {
			outRouteQueue.remove(badExistingRoute);

			// Don't forget to clean the bad entry out of our per-road map, or
			// we won't really be removing it.
			historyForCode.remove(badExistingHistory);
		}
		if (shouldAddRoute) {
			outRouteQueue.add(route);

			// Remember the history for this road for next time.
			historyForCode.add(route.getHistory().get(
					route.getHistory().size() - 1));
		}
		totalAddToQueueOpsTime += System.nanoTime() - queueOpsTimeStart;
	}