Consider an application to help manage task for a game player.
In the game, you control a hero who needs to complete various tasks in a busy, monster-filled world. Each task type has a priority depending on its urgency, importance, or difficulty. Here’s how a priority queue would help organize these tasks:
- Tasks with Different Priorities: Tasks can vary in urgency:
- Fight Monster (high priority): Monsters are actively attacking, so they need immediate attention.
- Heal Wound (medium priority): After fighting, the hero may need to heal; it’s important but can wait if an immediate threat exists.
- Collect Resources (low priority): Gathering resources for crafting or quests is useful but can be postponed if something more urgent arises.
- Scheduling with a Priority Queue: The game’s task manager adds tasks to a priority queue:
- Each task type has a priority level (higher priority tasks are at the front of the queue).
- As the hero completes tasks, the manager pulls the highest-priority task from the queue, ensuring the hero focuses on the most urgent or important task first.
- Dynamic Task Management: During gameplay, new tasks can be added based on in-game events, like a new monster appearing. The priority queue instantly reorders these tasks based on priority, keeping the hero focused on what matters most.
In this program, the priority queue is used to manage tasks by priority, ensuring that the highest-priority tasks are handled first. Each task has a priority level (higher values represent higher priority) and a duration representing the time needed to complete the task.
The CompareTask function is a custom comparator that defines how tasks are prioritized in the queue. By default, a priority_queue in C++ orders elements in descending order, but this only works for simple data types (like integers) where “greater than” or “less than” is straightforward. Here’s why CompareTask is essential in this program.
Program on github
Group work:
- Can you modify the program so that if there is a priority tie, the task that came first will be picked first?
- How can you test this?
- Can you modify this so that the shortest job will always be first. (watch out for how I use the priority to count down the task time left)