0

I'm having some difficulties with the following problem:

I'm making a little game where you're at a specific spot and each spot has each some possible directions.

The available directions are N(ord),E(ast),S,W . I use the function getPosDirections to get the possible directions of that spot. The function returns the directions into an ArrayList<String> e.g. for spot J3: [E,W]

Now the game goes like this: 2 dice will be rolled so you get a number between 2 and 12, this number represents the number of steps you can make.

What I want is an ArrayList of all the possible routes

clarification of all the possible routes: When I'm at the current position I check what the possibilities are from there. Let's say that's go East and go West. So we get 2 new positions and from there on we need to check for the next possibilities again for both positions (until we took x directions)

(x equals the number thrown by the dice).

e.g.: I throw 3 and I'm currently at spot J3: 

[[E,N,E],[E,N,S],[E,S,E],[E,S,S],[W,N,E],[W,N,S],[W,S,E],[W,S,S]]

How would obtain the last mentioned Array(list)?

Improve this question
4
  • could you post the getPosDirections function, and maybe some more indications about what your complete playground looks like ? Commented Mar 15, 2010 at 22:08
  • "What I want is an ArrayList of all the possible routes" All possible routes to what? Commented Mar 15, 2010 at 22:09
  • @T.J. Crowder: "lussen" is Dutch for "loops", I think he mixed it up :) Commented Mar 15, 2010 at 22:18
  • Sorry I made a little mistake. Lusses is indeed loops (I changed the title), I also have written a clarification regarding All possible routes. Thanks you all for your input. Commented Mar 15, 2010 at 22:40

2 Answers 2

Reset to default
1

First, you might wish to think about your approach some more. In the worst case (a 12 is rolled, and all 4 directions are possible at every location), there will be 4^12 ~= 160 million routes. Is it really necessary to iterate over them all? And is it necessary to fill about 1 GB of memory to store that list?

Next, it is probably a good idea to represent directions in a type-safe manner, for instance using an enum.

That being said, recursion is your friend:

private void iteratePaths(Location currentLoc, List<Direction> currentPath, List<List<Direction>> allPaths, int pathLength) {
    if (currentPath.size() >= pathLength) {
        allPaths.add(new ArrayList<Direction>(currentPath));
        return;
    }
    for (Direction d : currentLoc.getPosDirections()) {
        currentPath.add(d);
        Location newLoc = currentLoc.walk(d);

        iteratePaths(newLoc, currentPath, allPaths, pathLength);

        currentPath.remove(currentPath.size() - 1);
    }
}

public void List<List<Direction>> getAllPaths(Location loc, int length) {
    List<List<Direction>> allPaths = new ArrayList<List<Direction>>();
    List<Direction> currentPath = new ArrayList<Direction>();
    iteratePaths(loc, currentPath, allPaths, length);
    return allPaths;
}
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1

You can assume that your field of spots is a complete graph. Then you need to implement BFS or DFS with saving pathes.

You can implement all logic in any of these algorithms (like getting a list of possible directions from a certain node).

Improve this answer

1 Comment

Expand or link the acronyms, at least.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.