I am facing the following situation:
In my game there are multiple quests to do and some require to complete another quest before being able to pick them up.
Say, for example: Before being able to do Quest 2 you need to complete Quest 1, however you can start Quest 3 in parallel, no matter if you have completed 1 or 2 already. Quest 4 (!) however requires 2 and 3 to be complete.
My current idea of implementation would be that each Quest has it’s required pre-quests and every tick every quest get’s checked. This feels totally wrong though, because I could use a tree for that (not exactly a tree because I will have multiple roots, so let’s say a graph).
Now I have two approaches: Only check the root Nodes for completion and when it’s complete, remove the node from the graph. This could be used during the game, maybe even only do that after some quest has been completed (infact I could even simply pick the quest from the tree which has been done).
The other situation is when the game starts up: I have my savegame which contains the state of all quests and then I have to really iterate from the root downwards or I could iterate from the leaves up: When a leaf is completed, I could skip all the parental nodes.
I guess which is more effective depends on the actual tree, but could I use some hybrid mode? Like checking the leaves and if those aren’t completed, leave them in and let the “root-down” do it’s job?
The real question now is: Does this sound like a good and effective way? It’s atleast better than doing all checks per Quest. On the other hand: Isn’t building the tree and checking it that way quite slow?
Also: Is there already a good java implementation, maybe even using Generics? I can’t use the SceneGraph because it only allows to have one Parent.
Edit: Another thought: There might be Quests excluding each other (Like: When you did Quest A you cannot choose Quest B anymore): How could I add them?
My approach to that : have an “accomplished quest” dictionnary. When a quest is done, you add it. You can serialize this dictionnary in the save file (with date and success details if needed)
The quests that need accomplishement update their availability in two manners :
listening to dictionnary modification (they receive the newly accomplished quest and check if it completes their need)
reading the whole dictionnary, when loading saved game or entering a new quest zone
This way you don’t have to manage a tree. Just add requirments to your quests and listen to changes.
You can make the requirement more generic, like “player level is between x and y” or “discussion node reached” or whatever. Generic QuestRequirement would listen to generic QuestRequirementChangeEvents.
I like the Idea especially because there will be some “random-place” events, like “Enter Zone X and Quest Y pops up”.
On the other hand it’s still brute-forcing all “non-completed” Quests on an ChangeEvent.
Maybe I’ll combine the two because that way I could still go with the generic requirements.
The Serialization of a Dictonary however rocks, mhh.
Remember : “Optimisation is the root of all evil”. One day, when you have 3000 quests (all Outland in World of Warcraft) you will notice that the quest update system take more than 10 milliseconds. Then you will think about it an entire minute, and pick one of the hundreds of solutions that come to your mind to kick that lag out.