Recursion to create possible combinations?
Posted: Mon Aug 03, 2009 3:59 pm
I haven't been a member of any development community such as this one in the past, so my apologies for offending anyone by joining with the intentions of asking this question.
I've been wracking my brain for weeks over this problem, trying to attack it from different angles, and everything I've done so far hasn't worked. Basically, I've been working on a game very similar to the board game "Ticket to Ride". If you're not familair with it, here's as much information as you'll need to understand my problem.
The playing area is a map of the US and lower Canada. A number of cities are marked on the map, and there are connections between some cities. Each route has a numeric value ranging from 1 to 6; it's generally an indication of the length of the route. Something between Dallas and Houston might only be 1, whereas something between Portland, OR and Salt Lake City might be 6. The game is played by purchasing these routes which in turn fulfill certain demand cards that provide bonus points. For example, if you have a single line of track that connects Montreal with New Orleans, no matter how convoluted the track is, you could qualify for 13 bonus points.
Here's the problem. At the end of the game, there are some points awarded to the owner of the longest track, and I would like to be able to determine this programmatically. My best guess so far is that this can be done recursively by starting with one route, determining the neighboring cities and whether or not the player owns any of those routes and, if so, moving on to them to continue the cycle until they player is out of routes. Unfortunately, I'm very lost in trying to figure this out. Is there anyone out there who might have an idea what to do here? I'm up for pretty much anything, but the end result needs to be able to:
1. Compile a list of possible combinations, and as a result
2. Identify branching tracks and compensate by building possible combinations with them as well
It's really the branching that gets me. What I mean by this is, if I have a track that connects Denver to Kansas City, and Kansas City to St. Louis, that's worth a total of 6 (4 and 2, respectively). If I also have a track that connects Kansas City to Oklahoma City (worth 2) then I've got a problem. All four cities are on the same circuit, but only a single line can qualify for the longest track; I need to be able to have the program figure out that there are essentially 3 possible combinations and list them so that their overall values can be determined.
If you've made it this far, my thanks to you. Any input on how I can go about this is greatly appreciated.
I've been wracking my brain for weeks over this problem, trying to attack it from different angles, and everything I've done so far hasn't worked. Basically, I've been working on a game very similar to the board game "Ticket to Ride". If you're not familair with it, here's as much information as you'll need to understand my problem.
The playing area is a map of the US and lower Canada. A number of cities are marked on the map, and there are connections between some cities. Each route has a numeric value ranging from 1 to 6; it's generally an indication of the length of the route. Something between Dallas and Houston might only be 1, whereas something between Portland, OR and Salt Lake City might be 6. The game is played by purchasing these routes which in turn fulfill certain demand cards that provide bonus points. For example, if you have a single line of track that connects Montreal with New Orleans, no matter how convoluted the track is, you could qualify for 13 bonus points.
Here's the problem. At the end of the game, there are some points awarded to the owner of the longest track, and I would like to be able to determine this programmatically. My best guess so far is that this can be done recursively by starting with one route, determining the neighboring cities and whether or not the player owns any of those routes and, if so, moving on to them to continue the cycle until they player is out of routes. Unfortunately, I'm very lost in trying to figure this out. Is there anyone out there who might have an idea what to do here? I'm up for pretty much anything, but the end result needs to be able to:
1. Compile a list of possible combinations, and as a result
2. Identify branching tracks and compensate by building possible combinations with them as well
It's really the branching that gets me. What I mean by this is, if I have a track that connects Denver to Kansas City, and Kansas City to St. Louis, that's worth a total of 6 (4 and 2, respectively). If I also have a track that connects Kansas City to Oklahoma City (worth 2) then I've got a problem. All four cities are on the same circuit, but only a single line can qualify for the longest track; I need to be able to have the program figure out that there are essentially 3 possible combinations and list them so that their overall values can be determined.
If you've made it this far, my thanks to you. Any input on how I can go about this is greatly appreciated.