Archived

This topic is now archived and is closed to further replies.

Programming Puzzle!

This topic is 5119 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Ok. I''ll explain this as simple as I can. If anyone has played final fantasy xi, this is regarding the skill chain system. Each character can learn weapon skills. Each weapon skill can have multiple elements. I have a table of elemental compatibility- that is, which elements are compatible with which other ones. When you do one weapon skill, and you do another weapon skill that has an element that is compatible with the first, it will create a chain. You can have up to 4 weapon skills in a chain. Now here is my problem. I am trying to make a tool that will display all possible chain combinations. That is, you input the weapon skills you have available, and it outputs the possible combinations. I will try to outline how I had first imagined the loop that would actually OUTPUT the combinations. (in visual basic, but its not that difficult to understand) I had planned the loop to go something like this:
For Skillone = 0 to Total_Skills_Available

  For SkillTwo = 0 to Total_Skills_Available

  '' check to see if SkillOne is compatible with SkillTwo
  
  '' If the two skills are compatible, add them to a
  '' temporary class that will hold the skills in the chain.

  '' Now I am stuck. 


  Next

Next
 
The loop above basically just goes through every possible 2-skill-combination and if they are compatible elements, then it goes onto a new loop that finds what skills are compatible with skill2, and what skills are compatible with skill3. For a total of 4 skills at the end. I have tried a few loops, but I always come to a point where the whole thing just gets so confusing I forget what it all does, I end up implementing stuff I already implemented, try to re-write code that already worked, etc. I had initially thought that I would have to put 2 more "For" statements, but now I just have no idea what the hell I''m doing, and I need a beer. If anyone can try and help, it would be very appreciated thanks

Share this post


Link to post
Share on other sites
This problem is one of finding all 4-edge paths in a directed graph. Write an algorithm to do that, and you will have solved the problem.

Hint: finding all 4-edge paths is the same as finding all 3-edge paths that have an edge leading away from the terminal point of the path.

Hint: all nodes begin and end 0-edge paths.

Recursion, baby.


"Sneftel is correct, if rather vulgar." --Flarelocke

Share this post


Link to post
Share on other sites
Look for Transitive Closure to the forth degree.

http://graphics.cs.ucdavis.edu/~okreylos/Private/AlgorithmCorner/PathFinding.html

That has some what of an explanation of finding paths of a certain length.

~Wave

Share this post


Link to post
Share on other sites
That''s not necessarily true, if you assume that 2-combos and 3-combos are also chains in their own right. Thus, you have an "all prefixes" kind of situation.

The trick, however, is still recursion! You just gotta work forward and do an exhaustive search. Computers are pretty fast these days ;-)

You''ll need one chained data structure (list, or array with 4 elements) and a function which, given a pre-condition chain, scans all skills and tacks on the post-conditions (if possible) and recurses.

Something like (sorry, C/C++ style):

struct skill {
uint32 components;
char * name;
};
skill allSkills[] = {
... you do the hard work ...
};
enum {
NumSkills = sizeof(allSkills)/sizeof(allSkills[0]),
};
enum {
MinToPrint = 2,
};

void print_chain( skill ** skills, int size )
{
// excercise for reader
}

void scan_and_recurse( skill ** skills, int maxDepth, int curDepth ) {
// use the fact that -1 sets all bits so matches everything
uint32 match = (uint32)(curDepth ? skills[ curDepth-1 ].components : -1);
for( int ix = 0; ix < NumSkills; ++ix ) {
if( allSkills[ix].components & match ) {
skills[ curDepth ] = &allSkills[ix];
if( curDepth+1 >= MinToPrint ) {
print_chain( skills, curDepth+1 );
}
if( curDepth+1 < maxDepth ) {
scan_and_recurse( skills, maxDepth, curDepth+1 );
}
}
}
}

int main()
{
skill * skills[ 4 ];
scan_and_recurse( skills, 4, 0 );
return 0;
}




Haven''t syntax checked it, but should be close.

Share this post


Link to post
Share on other sites
Recursion is the more elegant solution here, but you can do it iteratively. Something like this, where compat checks if skill a is compatible with skill b.


bool compat(int a,int b);

for (i=0; i<totSkills; i++) {
for (j=i+1; j<totSkills; j++) {
if (!compat(j,i)) continue;
for (k=j+1; k<totSkills; k++) {
if (!compat(k,i) || !compat(k,j)) continue;
for (l=k+1; l<totSkills; l++) {
if (!compat(l,i) || !compat(l,j) || !compat(l,k)) continue;
// Add skill chain i,j,k,l to the list

}
}
}
}

Share this post


Link to post
Share on other sites