5
\$\begingroup\$

I'm looking to implement the minimum number of moves algorithm for the java game I'm developing but I can't quite figure it out.

Here's an example picture:

enter image description here

There are also some specifications about this:

The solution in the example above is not unique; other solutions would also be valid as long as the "final character layout (or the positioning of the characters in the nodes)" matches a certain condition (I don't think that's very relevant now so won't go into detail). Also, the nodes aren't actually moved, only it's content.

Adjacent elements cannot be swapped (i.e. in the example above, on the starting side's first swap, 'E' couldn't be swapped with neither 'A' or 'B'; B could be swapped with any character but 'E' and so on.)

The same character can be swapped as many times as one wishes. So, for example, 'B', in the starting side of the picture, could be swapped with 'D' in the first move (B and D trade places) and then 'B' could be swapped with, let's say, 'E' (so B and E trade places).

So how exactly should I approach this, in order to get the minimum moves? I don't need a full solution, but some pseudo-code or a couple of hints would be greatly appreciated!

\$\endgroup\$
  • 2
    \$\begingroup\$ What constitutes a correct "solution"? You say the "final character layout (or the positioning of the characters in the nodes) matches a certain condition"... but you'll have to explain that. No one can give you a solution to a problem that isn't explained. \$\endgroup\$ – Foggzie Dec 22 '15 at 22:23
  • 1
    \$\begingroup\$ It sounds like you might want to use a search algorithm like A* - it's not only useful for path finding. \$\endgroup\$ – Adam Dec 23 '15 at 0:30
  • 1
    \$\begingroup\$ @Adam Hey, thanks for the tip, i'm going to take a look at it! \$\endgroup\$ – Francisco Dec 23 '15 at 0:56
  • 1
    \$\begingroup\$ Yeah; for A*, instead of having the nodes be "locations" they are "game states" where the "destination" is a "win state". And the "arcs" are not "paths" but "moves". You have to compute all the moves and game states that can be achieved from the current state and find the least "moves" to get to the "win" state. \$\endgroup\$ – Alexandre Vaillancourt Dec 23 '15 at 7:29
1
\$\begingroup\$

As people have said in comments section, A* or (AStar) is a viable algorithm for this, and a good waypoint.

Here you have a generic AStar implementation in Java so you can start with something. Please, ask if you have any question.

import java.util.*;


public class AStar {


  public static class PriorityList extends LinkedList {

    public void add(Comparable object) {
      for (int i=0; i<size(); i++) {
        if (object.compareTo(get(i)) <= 0) {
          add(i, object);
          return;
        }
      }
      addLast(object);
    }
  }

  protected List constructPath(AStarNode node) {
    LinkedList path = new LinkedList();
    while (node.pathParent != null) {
      path.addFirst(node);
      node = node.pathParent;
    }
    return path;
  }

  public List findPath(AStarNode startNode, AStarNode goalNode) {

    PriorityList openList = new PriorityList();
    LinkedList closedList = new LinkedList();

    startNode.costFromStart = 0;
    startNode.estimatedCostToGoal =
      startNode.getEstimatedCost(goalNode);
    startNode.pathParent = null;
    openList.add(startNode);

    while (!openList.isEmpty()) {
      AStarNode node = (AStarNode)openList.removeFirst();
      if (node == goalNode) {
        // construct the path from start to goal
        return constructPath(goalNode);
      }

      List neighbors = node.getNeighbors();
      for (int i=0; i<neighbors.size(); i++) {
        AStarNode neighborNode =
          (AStarNode)neighbors.get(i);
        boolean isOpen = openList.contains(neighborNode);
        boolean isClosed =
          closedList.contains(neighborNode);
        float costFromStart = node.costFromStart +
          node.getCost(neighborNode);

        // check if the neighbor node has not been
        // traversed or if a shorter path to this
        // neighbor node is found.
        if ((!isOpen && !isClosed) ||
          costFromStart < neighborNode.costFromStart)
        {
          neighborNode.pathParent = node;
          neighborNode.costFromStart = costFromStart;
          neighborNode.estimatedCostToGoal =
            neighborNode.getEstimatedCost(goalNode);
          if (isClosed) {
            closedList.remove(neighborNode);
          }
          if (!isOpen) {
            openList.add(neighborNode);
          }
        }
      }
      closedList.add(node);
    }

    return null;
  }

}
\$\endgroup\$
  • 1
    \$\begingroup\$ Hey! Thanks a lot for your answer! I ended up using BFS because i wasn't so sure about the heuristic to use in this case, but i'm definetly going to try it with A* now. Thanks! \$\endgroup\$ – Francisco Jan 13 '16 at 11:34
  • \$\begingroup\$ BFS is also nice. You can try both and keep the one that fits your needs better. \$\endgroup\$ – Mayuso Jan 13 '16 at 11:42
  • 1
    \$\begingroup\$ Yeah, will do. Thank you very much for the help! :) \$\endgroup\$ – Francisco Jan 13 '16 at 11:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.