Effectiveness of greedily collecting items in open world games
This addresses a practical problem for players and developers of open world games, but it is incremental as it applies an existing greedy algorithm to a new gaming context.
The paper tackles the problem of determining whether greedily collecting the closest items first is an effective strategy in open world games, showing that it performs on average only 7% worse than the optimal solution in terms of total distance traveled, degrading to 16% worse when accounting for human distance estimation errors.
Since Pokemon Go sent millions on the quest of collecting virtual monsters, an important question has been on the minds of many people: Is going after the closest item first a time-and-cost-effective way to play? Here, we show that this is in fact a good strategy which performs on average only 7% worse than the best possible solution in terms of the total distance traveled to gather all the items. Even when accounting for errors due to the inability of people to accurately measure distances by eye, the performance only goes down to 16% of the optimal solution.