I'm working on a prototype game at the moment and I've a road black.
Essentially the problem space for the basic game is this:
There are
6 Traders
10 Asset
1 Premium Asset.
Rules:
The player starts with 1 Asset
A Trader has 1-3 Assets
For each Asset there are 1-3 acceptable trades the trader will accept
An Asset can't be traded to the same Trader for a different Asset
Each Asset is only used once
The goal is for the player to trade a series of Assets to end up with the Premium Asset. Not all Assets are needed to reach goal.
The problem I'm having is coming up with a decent way of distributing the assets and creating the trades. Since each trade is effectively a node in tree but there should only be 1 path from to start to finish with various dead end branches.
My first thought was to randomly assign the assets and then create a path by starting at the first asset randomly picking the next asset from the unused ones assigned to the other traders. And then back filling to create dead ends.
But that doesn't seem like efficient solution and the back filling to create dead ends become over complicated. As well it doesn't extend well when I want to add in additional rules.
For instance there 2 other game modes I want to have Advance and Expert. In Advanced there up 3 premium assets and game can be won by getting any of them but there is a perfect solution that allows the player to get all of them. There also more assets, and traders as well as an additional rule that each trader has 1 trade that they will trade more than 1 item for. And in Expert mode the the perfect solution uses all assets.
I Can't help but feel there should be some form of path finding I can use to solve this problem but so far all I can think of some how using DFS.
If I understand you correctly, you want to determine how to distribute the assets and premium assets to the player and traders and set the acceptable trades for the traders such that the scenario always contains a trading path for the player to be successful
If this is correct, I would honestly just generate every possible scenario and then randomly select one of the ones from that set which allows the player to be successful
Assuming that this would be done during a loading stage, and users are willing to wait a little while, it shouldn't incur a performance issue
However, if it is a problem, you could store the scenarios which allow the player to be successful in a file that is distributed with your executable and then randomly select one at runtime
Hmm, maybe you need to start at the leaves (premium assets) and work back to asset 1. Each time you add a node you should easily be able to ensure there are no cycles. When you join the leaf trees together is entirely under your control. Asset 1 wouldn't be fixed, it would just be whatever ended up available at the top. Dead ends should be easy, just ensure none of the trades yield an object anywhere in the correct solution path. If you want it to be a little easier just make it a DAG instead of a tree, so there are multiple solutions.
After trying a few different approaches what I ended up doing was.
Creating all the assets, then building a path of a given depth starting at the premium asset by connection randomly selecting unique assets. The last asset in the path became the starting asset. Each time the code goes to pick the next asset it takes it from a randomly choose a trader from the pool or creates a new trader.
I then I create a number of dead end trades by looping through all the assets and choosing up to 2 assets it can be traded for with the restrictions that they have to be owned by another trader and can't be in the path.
It works and gives some flexibility but if anyone has thoughts on improvement I'd be happy to hear them.
