3
\$\begingroup\$

I recently created this for a coursework assignment. I am always looking to learn and would like some feedback on my code. Is there any OO principles I'm going against or anything irritating I'm doing?

Search Class:

 import java.util.ArrayList;
 import java.util.Collections;
 import java.util.HashMap;
 import java.util.Map;

 /**
 * Represents the A* algorithm
 *
 * @author Paymon Sattarzadeh
 * @date 27/11/2014
 * @time 16:19
 */
 public class Search {

/**
 * Active instance of <code>Board</code>
 */
private Board board;
/**
 * Active instance of <code>Board</code> representing the goal state
 */
private Board goalBoard;
/**
 * g value
 */
private int g = 0;
/**
 * Is the search complete
 */
private boolean searchComplete = false;
/**
 * f values for the set of nodes currently being considered
 */
ArrayList<Integer> nodeFValues = new ArrayList();
/**
 * Tiles for the set of nodes currently being considered
 */
ArrayList<Tile> nodeTiles = new ArrayList<>();
/**
 * The last move
 */
private int lastMove = 0;

/**
 * Construct the <code>Search</code> instance
 *
 * @param board
 *      The board
 */
public Search(Board board, Board goalBoard){
    this.board = board;
    this.goalBoard = goalBoard;

    searchAlgo();
}

/**
 * Main search algorithm
 */
private void searchAlgo() {

    /* If there are no tiles out of place then you are at goal state */
    if (tilesOutOfPlaceHeuristic(board) == 0) {
        System.out.println("Complete");
        board.print();
        searchComplete = true;

        return;
    }

    /* Checks if the puzzle is solvable */
    if (isSolvable())
        nodeManager();
    else {
        System.out.println("This puzzle is not solvable");

        return;
    }


    ArrayList<Tile> listt = new ArrayList();

    /* Adds all the tiles with equal f values to the listt arraylist */
    for (int value : nodeFValues) {

        if (value == Collections.min(nodeFValues))
            listt.add(nodeTiles.get(nodeFValues.indexOf(value)));

    }

    /*
    * If there are nodes with the same f value as the min,
    * clear the nodeFValues list and get new f value(with complement of h2)
    */
    if (listt.size() > 1) {
        nodeFValues.clear();
        nodeTiles.clear();

        for (Tile tile : listt) {
            nodeFValues.add(node(tile, true));
            nodeTiles.add(tile);
        }

    }

    /* Gets the minimum fringe */
    int minFValueIndex = nodeFValues.indexOf(Collections.min(nodeFValues));

    /* Goes to the node with the lowest f value. */
    board.moveTile(board.findTile(0),
            nodeTiles.get(minFValueIndex).getXPosition(),
            nodeTiles.get(minFValueIndex).getYPosition());

    lastMove = nodeTiles.get(minFValueIndex).getNumber();
    g += 1;

    /* Clears the data from the previous node */
    nodeFValues.clear();
    nodeTiles.clear();

    /* If search is incomplete, it recursively calls itself */
    if (!searchComplete)
        searchAlgo();


}

/**
 * Manages the nodes and adds the values/tiles to the respective list
 */
private void nodeManager(){

    /* Stores all the f values for the nodes in the fringe */
    for(Tile tile: board.checkNeighbouringTiles(board.findTile(0))){
        if(lastMove != tile.getNumber()) {
            nodeFValues.add(node(tile, false));
            nodeTiles.add(tile);
            node(tile, false);
        }

    }

}

/**
 * Represents each node
 *
 * @param tile
 *      The tile to be moved in the node
 * @param useSecondHeuristic
 *      flag to consider whether to use the 2nd heuristic
 * @return
 *      f value
 */
private int node(Tile tile, Boolean useSecondHeuristic){

    /** Initialises new board object */
    Board nodeBoard = new Board(board.getTiles());

    nodeBoard.moveTile(nodeBoard.findTile(0), tile.getXPosition(), tile.getYPosition());

    int h1 = tilesOutOfPlaceHeuristic(nodeBoard);
    int h2 = manhattanHeuristic(nodeBoard);
    int f;

    if(!useSecondHeuristic)
        f = g + h1;
    else
        f = g + h1 + h2;

    return f;
}

/**
 * Calculates horizontal and vertical distances of tiles from their proper places.
 * Admissible Heuristic.
 *
 * @param board
 *      The board that needs reviewing
 * @return
 *      Sum of horizontal and vertical distances of tiles from their proper places.
 */
public int manhattanHeuristic(Board board) {

    int sum = 0;
    ArrayList<Tile> tiles = board.getTiles();
    Tile goalState;
    int goalX;
    int goalY;
    int differenceX;
    int differenceY;

    for(Tile tile: tiles){

        if(tile.getNumber() != 0) {
            goalState = goalBoard.findTile(tile.getNumber());
            goalX = goalState.getXPosition();
            goalY = goalState.getYPosition();

            differenceX = goalX - tile.getXPosition();
            differenceY = goalY - tile.getYPosition();

            sum += Math.abs(differenceX) + Math.abs(differenceY);
        }

    }

    return sum;
}

/**
 * Calculates number of tiles out of place. Admissible Heuristic.
 *
 * @param board
 *      The board that needs reviewing
 * @return
 *      Number of tiles out of place
 */
public int tilesOutOfPlaceHeuristic(Board board) {

    int tilesInWrongPlace = 0;
    ArrayList<Tile> tiles = board.getTiles();

    for(Tile tile: tiles){

        if(tile.getNumber() != 0) {
            if ((tile.getXPosition() != goalBoard.findTile(tile.getNumber()).getXPosition())
                    || (tile.getYPosition() != goalBoard.findTile(tile.getNumber()).getYPosition())){
                tilesInWrongPlace += 1;
            }
        }

    }

    return tilesInWrongPlace;
}

/**
 * Checks if the board is solvable.
 *
 * @return
 *      is solvable?
 */
private boolean isSolvable() {

    int numberOfInversions = 0;

    for(Tile i: board.getTiles()) {

        for (Tile j : board.getTiles()) {

            /* If the tile j is after(has a greater index) then tile i. */
            if (board.getTiles().indexOf(i) < board.getTiles().indexOf(j)) {

                if (i.getNumber() != 0 && j.getNumber() != 0) {
                    /* If j's number is lower then i's */
                    if (i.getNumber() > j.getNumber())
                        numberOfInversions += 1;
                }
            }

        }

    }

    /* If the grid width is odd, then the number of inversions in a solvable situation is even.*/
    if((Main.COLUMNS % 2 == 1) && (numberOfInversions % 2 == 1))
        return false;

    /* If the grid width is even, and the blank is on an even row counting from the bottom (second-last, fourth-last etc),
       then the number of inversions in a solvable situation is odd.*/
    if(((Main.COLUMNS % 2 == 0) && (board.findTile(0).getYPosition() % 2 == 0))
            && (numberOfInversions % 2 == 1))
        return false;

    /* If the grid width is even, and the blank is on an odd row counting from the bottom (last, third-last, fifth-last etc)
       then the number of inversions in a solvable situation is even. */
    if(((Main.COLUMNS % 2 == 0) && (board.findTile(0).getYPosition() % 2 == 1))
            && (numberOfInversions % 2 == 0))
        return false;

    return true;
}

}

Board Class:

 import java.util.ArrayList;

 /**
 * The board where the game is played.
 *
 * @author Paymon Sattarzadeh
 * @date 27/11/2014
 * @time 12:20
 */
 public class Board {

/**
 * The board
 */
private ArrayList<Tile> board;

/**
 * Constructs a <code>Board</code> instance and fills
 * it with <code>Tile</code> instances
 */
public Board(ArrayList<Tile> tiles) {
   this.board = tiles;
}

/**
 * @return
 *      Tiles in board
 */
public ArrayList<Tile> getTiles(){

    return board;
}

/**
 * Moves the specified <code>Tile</code> to the specified position.
 * Swaps positions with <code>Tile</code> at that position.
 *
 * @param tile
 *      <code>Tile</code> to be moved
 * @param x
 *      The horizontal position you want <code>Tile</code> to move to.
 * @param y
 *      The vertical position you want <code>Tile</code> to move to.
 */
public void moveTile(Tile tile, int x, int y) {

    int _x = tile.getXPosition();
    int _y = tile.getYPosition();

    Tile tileToBeMoved = board.get(board.indexOf(tile));
    Tile tileAtPosition;

    if(findTile(x, y) != null) {
        tileAtPosition = findTile(x, y);
    } else {
        System.out.println("No tile exists at that position");

        return;
    }

    /* Move tileToBeMoved to chosen position */
    tileToBeMoved.setPosition(x, y);

    /* swap*/
    tileAtPosition.setPosition(_x, _y);

}

/**
 * Checks if neighbouring <code>Tile</code>s exist, if so, it returns the <code>Tile</code>
 *
 * @param tile
 *      Current <code>Tile</code>
 * @return
 *      Set of <code>Tile</code>s
 */
public ArrayList<Tile> checkNeighbouringTiles(Tile tile){

    ArrayList<Tile> neighbouringTiles = new ArrayList<>();

    int x = tile.getXPosition();
    int y = tile.getYPosition();

    /* Neighbour to the right of tile */
    int rightNeighbourX = x + 1;
    int rightNeighbourY = y;

    /* Neighbour to the left of tile */
    int leftNeighbourX = x - 1;
    int leftNeighbourY = y;

    /* Neighbour to the top of tile */
    int topNeighbourX = x;
    int topNeighbourY = y - 1;

    /* Neighbour to the bottom of tile */
    int bottomNeighbourX = x;
    int bottomNeighbourY = y + 1;


    for(Tile t: board) {
        if ((t.getXPosition() == rightNeighbourX) && (t.getYPosition() == rightNeighbourY)) {
            neighbouringTiles.add(t);

        } else if((t.getXPosition() == leftNeighbourX) && (t.getYPosition() == leftNeighbourY)){
            neighbouringTiles.add(t);

        } else if((t.getXPosition() == topNeighbourX) && (t.getYPosition() == topNeighbourY)){
            neighbouringTiles.add(t);

        } else if((t.getXPosition() == bottomNeighbourX) && (t.getYPosition() == bottomNeighbourY)){
            neighbouringTiles.add(t);
        }
    }

    return neighbouringTiles;
}

/**
 * Finds a <code>Tile</code> with matching position
 *
 * @param x
 *      The horizontal position
 * @param y
 *      The vertical position
 * @return
 *      matching <code>Tile</code>
 */
public Tile findTile(int x, int y){

    for(Tile t: board) {
        if(t.getXPosition() == x && t.getYPosition() == y)
            return t;
    }

    return null;
}

/**
 * Finds a <code>Tile</code> with matching number
 *
 * @param number
 *      The number on the <code>Tile</code>
 * @return
 *      matching <code>Tile</code>
 */
public Tile findTile(int number){

    for(Tile t: board) {
        if(t.getNumber() == number)
            return t;
    }

    return null;
}


/**
 *Prints the board
 */
public void print() {

    System.out.println("*=====*");

    for(int j = 0; j < Main.ROWS; j++){
        System.out.print("||");

        for(int i = 0; i < Main.COLUMNS; i++){

            if(findTile(i, j).getNumber() == 0)
                System.out.print(" ");
            else if(findTile(i, j) != null)
                System.out.print(findTile(i, j).getNumber());

        }
        System.out.println("||");
    }

    System.out.println("*=====*");

}

}

Tile Class:

 /**
* Represents a single tile on a board
*
 * @author Paymon Sattarzadeh
* @date 27/11/2014
* @time 02:27
*/
public class Tile {

/**
 * Number on Tile
 */
private int number;

/**
 * Horizontal position of tile
 */
private int x;

/**
 * Vertical position of tile
 */
private int y;

/**
 * Constructs a <code>Tile</code> instance with a number and position.
 *
 * @param number
 *      The number for the <code>Tile</code>.
 * @param x
 *      The Horizontal position for the <code>Tile</code>.
 */
public Tile(int number, int x, int y){
    this.number = number;
    this.x = x;
    this.y = y;
}

/**
 * @param x
 *      Horizontal position for the <code>Tile</code>
 * @param y
 *      Vertical position for the <code>Tile</code>
 */
public void setPosition(int x, int y){

    this.x = x;
    this.y = y;
}

/**
 * @return
 *      Current horizontal position of <code>Tile</code>
 */
public int getXPosition(){

    return x;
}

/**
 * @return
 *      Current vertical position of <code>Tile</code>
 */
public int getYPosition(){

    return y;
}

/**
 * @param number
 *      Number on Tile
 */
public void setNumber(int number){

    this.number = number;
}

/**
 * @return
 *      Current number on tile
 */
public int getNumber(){

    return number;
}

}
\$\endgroup\$
  • \$\begingroup\$ According to Java conventions you should always use braces in if-else statements: "if statements always use braces {}. Avoid the following error-prone form: if (condition) //AVOID! THIS OMITS THE BRACES {}! statement;" oracle.com/technetwork/java/codeconventions-150003.pdf \$\endgroup\$ – Laura Dec 8 '14 at 18:42
  • \$\begingroup\$ Also you should not use underscores in Java "int _x = tile.getXPosition();". You suggest you rename this variable to "xPosition". Also some logic from Search class like "isSolvable()" where you check if the Board is solvable should not be written in that class as the scope of that class is only for Search. You should write this method in the Board class. \$\endgroup\$ – Laura Dec 8 '14 at 18:51
  • \$\begingroup\$ @Laura Feel free to write a CR. You do not need cover everything, a partial CR is perfectly fine (ideally, state upfront what you cover and what not), so may may stop when it gets boring. \$\endgroup\$ – maaartinus Dec 8 '14 at 19:05
2
\$\begingroup\$

Your indentation is a little inconsistent. I don't know if that's how it looks in your IDE or is an artifact of the copy and paste. In general code is easier to read when formatted consistently. For example, your declaration of the Search class is indented more than its fields. Usually the opposite would be true.

ArrayList<Integer> nodeFValues = new ArrayList();

You'd normally have the left side defined by the interface rather than the implementation. That way, you can pass it to anything that expects the interface and can easily change your implementation at just a single place. It also helps remind you of what is part of the interface and what is specific to the implementation. You can't accidentally access something specific to the implementation through an interface object.

private List<Integer> nodeFValues = new ArrayList<>();

Unless you are doing something clever that I missed, you probably want to use the <> operator to indicate that you want this to be a list of the same type as the left side definition.

You also want to declare this as private almost always. You could also declare this as final if you never assign a new list to it. Yes, you will still be able to clear it and add elements to the list if you declare it final. You just won't be able to assign to the variable itself.

public Search(Board board, Board goalBoard){
    this.board = board;
    this.goalBoard = goalBoard;

    searchAlgo();
}

As a general rule, you don't want to do processing in your constructor. You don't show your main function, so I don't know what should change there. It could be as simple as calling searchAlgo right after calling the constructor.

Note: this is a very common thing to try when first encountering objected-oriented principles. It's just that doing this makes it harder to reuse the code in different ways. For example, you might have reasons to do something else before running the search. As a general rule, constructors should just allocate and initialize variables. They should not attempt to read input or process things.

private void searchAlgo() {

So searchAlgo seems short for search algorithm. I tend to be against abbreviations, as they slow code reading more than they speed code writing. After school, you will find that you spend more time reading code (both yours and that of others) than you do writing code. But that's not actually the biggest concern that I have with that name.

As a general rule, classes and objects should get noun names and methods should get verbs. This makes makes the code read more naturally. Search algorithm is an adjective followed by a noun, so I wouldn't use it as a method name. You could name the class SearchAlgorithm, but I think that I might name it Searcher or BoardSearcher. You can then name the method either search (specific to this problem) or the more generic process. Since you presumably don't have a standard to which to adhere, I'd probably go with search. This isn't the optimal use case for something like process.

if (tilesOutOfPlaceHeuristic(board) == 0) {

Again, I would name this as as a verb, e.g. countTilesOutOfPlace. You're actually counting the tiles, so you don't need to call it a heuristic. You might also define this in the Board class, as it is something you use for searching, not part of the search itself.

if ( board.countTilesOutOfPlace() == 0 ) {

That also resolves another issue where you were calling the function with a parameter board even though board is a member of the class.

    if (isSolvable())
        nodeManager();
    else {

You do two things here. First, the Java standard prefers that you always use braces (although the language allows the other form. More seriously (at least to me), you are mixing styles in the same control statement. Even in languages where the single statement form is allowable if not preferred, it's better not to use both forms in the same if/else construct.

As Laura noted, isSolvable really should be a method on the Board class, not the search class.

Another thing is that you shouldn't need to do isSolvable on each call to the function. Check if a board is solvable before passing the board to search at all.

    ArrayList<Tile> listt = new ArrayList();

I don't like the name listt. I'm guessing that this is short for list of tiles, which is redundant. We can already see that it's a list of tiles. What's the purpose of this list of tiles? As a default name if nothing better presents itself, I'd prefer just tiles which is simpler. Also, I'd again rewrite this:

    List<Tile> listt = new ArrayList<>();

Favor interface declarations and avoid typeless lists.

    /* Adds all the tiles with equal f values to the listt arraylist */
    for (int value : nodeFValues) {

        if (value == Collections.min(nodeFValues))
            listt.add(nodeTiles.get(nodeFValues.indexOf(value)));

    }

I have a problem with nodeFValues that I didn't realize when you created it. It looks like it is a list that assumes that it is indexed the same as nodeTiles. This is fragile. If you accidentally add an F-value out of place, then your code won't work. It would be better if F-values were either part of the Tile class, so that each Tile would know its own F-value, or if the F-Values data structure were a Map from Tile to F-Value. Either way, you'd avoid the errors that could arise from having two parallel data structures.

You can actually avoid all this by making Tile implement the Comparable interface. Then you could just say something like

Tile tile = Collections.min(nodeTiles);

Your compare function could check the first heuristic and then fail over to the second heuristic if the first wasn't detailed enough.

    board.moveTile(board.findTile(0),
            nodeTiles.get(minFValueIndex).getXPosition(),
            nodeTiles.get(minFValueIndex).getYPosition());

Why is this so complicated? It looks like board.findTile(0) is how you represent the empty space where no tile is present. Since all moves will involve this tile, why specify it? Also, why get the X and Y positions now? You could pass just the tile and get those in the move function. Then you could write

   board.move(tile);

That way you don't have to specify that the tile is moving to the empty space and the caller doesn't even need to know where the tile is located. You move a little bit of code out of the two callers and into the moveTile function.

public void moveTile(Tile tile) {
    if ( ! board.contains(tile) ) {
        System.out.println("That tile is not part of this board");

        return;
    }

    int x = tile.getXPosition();
    int y = tile.getYPosition();

    /* Swap the positions of tile and the empty space */
    tile.setPosition(emptySpace.getXPosition(), emptySpace.getYPosition());
    emptySpace.setPosition(x, y);

}

I'm not sure about calling return there. It might be better to throw an IllegalArgumentException.

Note that I also have the board track the empty space separately in this implementation. That saves calling board.findTile(0) every time that you want the empty space. Just call it once in the constructor:

public Board(ArrayList<Tile> tiles) {
    this.board = tiles;
    this.emptySpace = findTile(0);
}

Then you never have to do it again.

    lastMove = nodeTiles.get(minFValueIndex).getNumber();

This isn't the last move, but the last moved tile. Why not just save the tile?

    lastMovedTile = tile;

That way when we get the neighbors of the empty space, we can just remove this.

    nodeTiles = board.getNeighboursOfEmpty();
    nodeTiles.remove(lastMovedTile);

Or even just get the neighbors at the end of the function while tile is still defined.

    nodeTiles.remove(tile);

Now we've saved a variable.

    g += 1;

If g is the number of moves, then why not call it numberOfMoves or similar?

    numberOfMoves++:

Also, if you're just incrementing by 1, then there's an operator for that.

/* If search is incomplete, it recursively calls itself */
if (!searchComplete)
    searchAlgo();

This will work, but it mostly seems a waste of stack space. It's probably better to put the whole thing in a loop instead.

while ( board.countTilesOutOfPlace() != 0 ) {

You can get rid of the searchComplete variable. It will never be true here as you return whenever you set it to true.

    Board nodeBoard = new Board(board.getTiles());

    nodeBoard.moveTile(nodeBoard.findTile(0), tile.getXPosition(), tile.getYPosition());

Does this work properly? It seems like it would move the actual tile when you want it to move a temporary tile.

    if(!useSecondHeuristic)
        f = g + h1;
    else
        f = g + h1 + h2;

It's not clear to me why you add g here. It's going to be the same for all the tiles.

public int manhattanHeuristic(Board board) {

Given the description, I'd probably call this calculateManhattanDistance instead. You're using it for a heuristic, but the function itself is not a heuristic. It returns an actual value. You then use the exact value as a heuristic for which move is better. That's a characteristic of how you are using it rather than a description of its nature.

        for (Tile j : board.getTiles()) {

            /* If the tile j is after(has a greater index) then tile i. */
            if (board.getTiles().indexOf(i) < board.getTiles().indexOf(j)) {

This code is more complicated than it needs to be. You have a list, so the inner loop can be

        if ( i.getNumber() == 0 ) {
            // if i is the empty space, skip to the next tile
            continue;
        }

        Iterator<Tile> to = board.getTiles().listIterator(board.getTiles().indexOf(i));
        // starts with i, so skip to the next one
        to.next();
        while ( to.hasNext() ) {
            Tile j = to.next();

            if ( j.getNumber() != 0 ) {
                 /* If j's number is lower then i's */
                 if ( i.getNumber() > j.getNumber() ) {
                        inversionCount++;
                 }
            }
        }

That way you don't have to generate all the tiles each time and ignore half of them (on average).

Also, if i is the empty space, this doesn't bother generating values of j since all values of j won't be checked.

I changed numberOfInversions to inversionCount because I name scalar variables with singular names and collections with plural names. An int is a scalar, so I wouldn't give it a plural name.

    if((Main.COLUMNS % 2 == 1) && (numberOfInversions % 2 == 1))

COLUMNS probably shouldn't be a public member of Main. It would seem to be a characteristic of the Board and should be stored in that object and accessed by a getter.

    /* If the grid width is even, and the blank is on an even row counting from the bottom (second-last, fourth-last etc),
  then the number of inversions in a solvable situation is odd.*/
    if(((Main.COLUMNS % 2 == 0) && (board.findTile(0).getYPosition() % 2 == 0))
            && (numberOfInversions % 2 == 1))
        return false;

    /* If the grid width is even, and the blank is on an odd row counting from the bottom (last, third-last, fifth-last etc)
  then the number of inversions in a solvable situation is even. */
    if(((Main.COLUMNS % 2 == 0) && (board.findTile(0).getYPosition() % 2 == 1))
            && (numberOfInversions % 2 == 0))
        return false;

The comments and code don't match. According to the comments, you should return true in both these cases. Either the comments are wrong or the code is. If the code is correct as is, you could write it more simply

    if ( ( ( Main.COLUMNS % 2 == 0 ) && ( board.findTile(0).getYPosition() % 2 != numberOfInversions % 2 ) ) {
        return false;
    }

If the comments are correct, change the != to ==. You can also use an if/else to get rid of the extra check on COLUMNS.

This review is relatively long, so I won't try to review Board and Tile directly (I've made some comments along the way in this code).

In general, you should prefer to work with interfaces rather than implementations. A good search implementation should be independent of what it is searching. For example, you might have a search that worked with any type that implements Comparable. Then you could move all the game logic out of your Search class. You might put a little in Main and a lot in Board and Tile.

As it is, you'd have to redo your Search class almost entirely to work with a different kind of search space. Even another game would be mostly differently.

Incidentally, if you'd included your Main class, I probably would have tried to run this. As it is, I haven't run any of your code nor my modifications. I also didn't try to figure out if this was a valid implementation of A*.

\$\endgroup\$
2
\$\begingroup\$

It's not bad, though I wrote a lengthy list. The biggest problem is the overlong method Search.searchAlgo, where I've got lost.

Search

/**
 * g value
 */
private int g = 0;

Whatever it means, right? Either write a comment making something clearer or leave it out.

private int g = 0;

Zero is the default, so save you keyboard.

ArrayList<Integer> nodeFValues = new ArrayList();

You should declare everything as List rather than ArrayList as it's more general (and for nearly purposes equally good).

You should switch warnings on and get "row type" warning and fix it.

private void searchAlgo() {

As the name says, it's an algorithm and as such in can be used in various ways. The problem with yours is that it prints something instead of returning the solution (or null or alike if none exists).

/* Checks if the puzzle is solvable */
if (isSolvable())

I'm puzzled (pun intended)! Usually, the only way how to prove solvability is to find a solution. I see, I should have read the title. So it's fine.

    nodeManager();

A method name should be a verb with possible exceptions like newSomething for methods returning Something.

So either manageNodes or NodeManager nodeManager = new NodeManager();.

ArrayList<Tile> listt = new ArrayList();

listt looks more like a typo than a name. While I still can recall A*, the exact variable names are gone (and maybe they were called differently in my book).

for (int value : nodeFValues) {
    if (value == Collections.min(nodeFValues))

Computing the minimum again and again doesn't make it faster.

If there are nodes with the same f value as the min, clear the nodeFValues list and get new f value(with complement of h2)

qaStaH nuq?

/* If search is incomplete, it recursively calls itself */
if (!searchComplete)
    searchAlgo();

And checks again if the problem is solvable. Writing shorter methods would make it clear immediately. Use your IDE to "extract method".

I must confess, I'm not sure if this is A*. It may be. Try with a terrible heuristic (always return zero is stupid, but correct) and a simple problem, it must solve it.

int h2 = manhattanHeuristic(nodeBoard);

Heuristics may be expensive and with useSecondHeuristic = false, you don't need it. If you really want this variable, use

int h2 = useSecondHeuristic ? manhattanHeuristic(nodeBoard) : 0;

This is rather overcomplicated, especially this part

int f;

if(!useSecondHeuristic)
    f = g + h1;
else
    f = g + h1 + h2;

return f;
  • Usually, all variables should be assigned in the declaration (?: makes it easy).
  • A condition in "if-then-else" should not be negated.
  • The "single return" rule is obsolete like FORTRAN.

What about

int h1 = tilesOutOfPlaceHeuristic(nodeBoard);
int h2 = useSecondHeuristic ? manhattanHeuristic(nodeBoard) : 0;
return h1 + h2;

? This looks like Pascal

int sum = 0;
ArrayList<Tile> tiles = board.getTiles();
Tile goalState;
int goalX;
int goalY;
int differenceX;
int differenceY;

All the non-initialized variables should be defined and initialized in the loop. Save 5 lines and make it readable.

public int manhattanHeuristic(Board board) ...
public int tilesOutOfPlaceHeuristic(Board board) ...

Again, methods should be called using verbs... but this would ideally be a class implementing Heuristic. This would make your A* very general.

/* If the grid width is even, and the blank is on an even row counting from the bottom (second-last, fourth-last etc),
   then the number of inversions in a solvable situation is odd.*/
if(((Main.COLUMNS % 2 == 0) && (board.findTile(0).getYPosition() % 2 == 0))
        && (numberOfInversions % 2 == 1))
    return false;

/* If the grid width is even, and the blank is on an odd row counting from the bottom (last, third-last, fifth-last etc)
   then the number of inversions in a solvable situation is even. */
if(((Main.COLUMNS % 2 == 0) && (board.findTile(0).getYPosition() % 2 == 1))
        && (numberOfInversions % 2 == 0))
    return false;

This could be simplified to something like

/* If the grid width is even, then the blank must on an even row counting from the bottom (second-last, fourth-last etc),
   and the number of inversions must be odd, or vice versa.*/
if (((Main.COLUMNS % 2 == 0) && (board.findTile(0).getYPosition() % 2 == numberOfInversions % 2))
    return false;

Board

int _x = tile.getXPosition();

That's a terrible name. If you can't find anything better, use x2, but what about tileX?

System.out.println("No tile exists at that position");

Can it happen? If so, does the printing help?

If it's impossible, so throw an exception. If it's possible, consider returning boolean. Never print.

  • Checks if neighbouring Tiles exist, if so, it returns the Tile public ArrayList checkNeighbouringTiles(Tile tile){

That's a lie. It checks nothing and never returns a tile (it may return a list containing a single tile). what about getNeighboringTiles?

public Tile findTile(int x, int y){

    for(Tile t: board) {
        if(t.getXPosition() == x && t.getYPosition() == y)
            return t;
    }

    return null;
}

It'd be probably faster to maintain a bidirectional mapping where a tile remembers it's position and a position knows what tile lies on it. You obviously would have to keep it in sync all the time. The easiest way is to use immutable Tile and Position and let Board keep track of everything. You could use a BiMap or run your own using e.g. arrays.

Tile

No (new) problems here.

\$\endgroup\$

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.