Jump to content
  • Advertisement
Sign in to follow this  
dev578

Trouble with an algorithm

This topic is 4637 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

What I am trying to implement here is an algorithm that can place x dots on a y by z grid, in all possible combinations that they can be. The dots are labeled 1 through x+1. (x, y, and z are constants) A few additional specifications are that if dot 1 is placed at (0,1) and dot 6 is placed on (5,6); and in another instance if dot 6 is placed on (0,1) and dot 1 is placed on (5,6), then they are TWO different combinations. Additionally, two dots cannot be placed on the same point. This probably sounds ridiculous, but I am doing this to try to solve for all possible combinations in a game I am making, so I can solve my game, in a sense. I don't really even know where to start, I would assume it would be a large nested for loop mess, but I really can't think of anything that would work. If anyone could help me out, that would be greatly appreciated. I know this is hard (for me anyway), so definately rating++ to someone who helps. Thank you, Dev578

Share this post


Link to post
Share on other sites
Advertisement
As near as I can tell, the number of different permutations you have is (y * z)!/(y * z - x)! This can be a really, really big number. Are you sure you need to find all the permutations?

Share this post


Link to post
Share on other sites
Yes, it's a permutation problem--akin to 'arrange x objects in y*z places'. That's

y*zPx = (y*z)! / (y*z - x)!

as SiCrane mentioned. By the way, if the dots are labelled 1 through x+1 that makes x+1 dots in total. Just wanted to warn you, in case you plan to put that on the cover of the box of your game. [lol]

/edit: An important thing I forgot to mention--this assumes that all the dots are actually placed on the grid. If the number of dots placed is variable, then you are in an even bigger soup.

Total permutations = SUM (n = 0 to x) y*zPn

or something like that.

Share this post


Link to post
Share on other sites
Thank you, now that I know what it is called, I found a few articles on it that I am reading through. FYI, this is not going to be part of the game, it is separate, just so I can calculate all the possibilities and spit out the best solution. And yes, I understand that this will take awile to iterate through:) Rating++, and thank you.

Dev578

Share this post


Link to post
Share on other sites
Assuming x,y, and z are reasonable, you can use a recursive backtracking algorithm to generate all placements.


int grid[y][z];

void BackTrack(int depth)
{
if(depth == x)
{
//a solution has been found
}
else
{
for(int i = 0; i < y; ++i)
{
for(int j = 0; j < z; ++j)
{
if(grid[j] == 0)
{
grid[j] = depth+1;
BackTrack(depth+1);
grid[j] = 0;
}
}
}
}
}

//main, or some other section of your code
int main()
{
intialize grid to all 0's
BackTrack(0);
return 0;
}


As has already been said, this task quickly becomes too large. If I knew more about your game, I may be able to give a better solution.

[Edited by - Forcas on December 4, 2005 6:18:12 PM]

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!