path-game/src/pathgame/algorithm/DijkstraMagic.java

package pathgame.algorithm;

import pathgame.tilemap.TileMap;
import pathgame.tilemap.TileType;
import pathgame.tilemap.Tiles;

import java.util.ArrayList;
import pathgame.gameplay.Player;

/** Class that takes a TileMap, finds all towns in it and generates a table of shortest paths between each town using the Dijkstra algorithm
 *
 */
public class DijkstraMagic {
    private int TOWN_ID = Tiles.TOWN.getId();
    private int START_ID = Tiles.HOME_TOWN.getId();
    private int PORT_ID = Tiles.PORT.getId();
    private int WATER_WEIGHT;
    private ArrayList<Coord> towns = new ArrayList<>();
    private ArrayList<Coord> ports = new ArrayList<>();
    private TileMap map;
    private Node2D[][] weightMap;
    private ArrayList<ArrayList<SaleRoute>> salesPitch = new ArrayList<>();

    /** Generates a table of shortest paths between each town in the given TileMap
     *
     * @param map TileMap that the algorithm should use
     * @param player that is traversing the map
     */
    public DijkstraMagic(TileMap map, Player player) {
        this.map = map;

        weightMap = new Node2D[map.getWidth()][map.getHeight()];

        setup(player);

        //printWeightMap();

        for(int i = 0; i < ports.size(); i++) {
            doMagic(i, false);
        }

        for(int i = 0; i < towns.size(); i++) {
            doMagic(i, true);
        }

        //printDijkstraResult();
    }

    /** Returns the generated table of Dijkstra results
     *
     * @return generated table of Dijkstra results
     */
    public ArrayList<ArrayList<SaleRoute>> getSalesPitch() {
        return salesPitch;
    }

    private void doMagic(int fromIndex, boolean forTown) {
        resetWeightMap();

        Coord origin;

        if(forTown) {
            origin = towns.get(fromIndex);
        }
        else {
            origin = ports.get(fromIndex);
        }

        int posX = origin.getX(), posY = origin.getY();

        weightMap[posX][posY].setCostSoFar(0);
        weightMap[posX][posY].setQAdded(true);

        ArrayList<Coord> tileQ = new ArrayList<>();
        tileQ.add(new Coord(posX, posY));

        while(tileQ.size() > 0) {
            int leastCost = Integer.MAX_VALUE;
            int leastIndex = -1;

            for(int i = 0; i < tileQ.size(); i++) {
                int iX = tileQ.get(i).getX();
                int iY = tileQ.get(i).getY();
                if(weightMap[iX][iY].getCostSoFar() < leastCost) {
                    leastCost = weightMap[iX][iY].getCostSoFar();
                    leastIndex = i;
                }
            }

            Coord c = tileQ.get(leastIndex);

            if(weightMap[c.getX()][c.getY()].isBlocked() && forTown) {
                tileQ.remove(leastIndex);
            }
            else {
                dijkstraForTownOrPort(tileQ.get(leastIndex).getX(), tileQ.get(leastIndex).getY(), tileQ, leastIndex, forTown);
            }
        }
        if(forTown) {
            //printPathMap();
            //printPorts();
            makeListForPitch(fromIndex);
        }
        else {
            addPortsPaths(fromIndex);
        }

        //printDijkstraMap();
    }

    private void dijkstraForTownOrPort(int posX, int posY, ArrayList<Coord> tileQ, int qIndex, boolean forTown) {
        int prevCost = weightMap[posX][posY].getCostSoFar();

        if(posX < weightMap.length-1) {
            adjacent(posX+1, posY, prevCost, 'w', null, -1, tileQ, forTown);
        }
        if(posX > 0) {
            adjacent(posX-1, posY, prevCost, 'e', null, -1, tileQ, forTown);
        }
        if(posY < weightMap[0].length-1) {
            adjacent(posX, posY+1, prevCost, 'n', null, -1, tileQ, forTown);
        }
        if(posY > 0) {
            adjacent(posX, posY-1, prevCost, 's', null, -1, tileQ, forTown);
        }

        if(forTown) {
            if(weightMap[posX][posY].hasExtraPaths()) {
                ArrayList<ExtraPath> extraPaths = weightMap[posX][posY].getExtraPaths();

                for(int p = 0; p < extraPaths.size(); p++) {
                    ExtraPath path = extraPaths.get(p);

                    ArrayList<ExtraPath> foreingPaths = weightMap[path.getDestX()][path.getDestY()].getExtraPaths();
                    int extraInd = -1;

                    for(int forP = 0; forP < foreingPaths.size(); forP++) {
                        ExtraPath fPath = foreingPaths.get(forP);
                        if(fPath.getDestX() == posX && fPath.getDestY() == posY) {
                            extraInd = forP;
                            break;
                        }
                    }

                    adjacent(path.getDestX(), path.getDestY(), prevCost, '\0', path, extraInd, tileQ, forTown);
                }
            }
        }

        tileQ.remove(qIndex);
    }

    private void adjacent(int posX, int posY, int prevCost, char dir, ExtraPath boatPath, int extraInd, ArrayList<Coord> tileQ, boolean forTown) {
        if(forTown) {
            if(!weightMap[posX][posY].isBlocked()) {
                adjacentCalc(posX, posY, prevCost, dir, boatPath, extraInd, tileQ, forTown);
            }
        }
        else {
            TileType type = weightMap[posX][posY].getType();

            if(type == TileType.SHALLOW_WATER || type == TileType.DEEP_WATER || type == TileType.PORT) {
                adjacentCalc(posX, posY, prevCost, dir, null, -1, tileQ, forTown);
            }
        }
    }

    private void adjacentCalc(int posX, int posY, int prevCost, char dir, ExtraPath extraPath, int extraInd, ArrayList<Coord> tileQ, boolean forTown) {
        int newCost = prevCost;
        if(forTown) {
            if(extraPath == null) {
                newCost += weightMap[posX][posY].getWeight();
            }
            else {
                newCost += extraPath.getPathWeight();
            }

        }
        else {
            newCost += WATER_WEIGHT;
        }

        if(newCost < weightMap[posX][posY].getCostSoFar()) {
            weightMap[posX][posY].setCostSoFar(newCost);
            if(extraPath == null) {
                weightMap[posX][posY].setPrevOfPath(dir);
            }
            else {
                weightMap[posX][posY].setPrevBoatPath(extraInd);
            }
        }

        if(!weightMap[posX][posY].isQAdded()) {
            weightMap[posX][posY].setQAdded(true);
            tileQ.add(new Coord(posX, posY));
        }
    }

    private void addPortsPaths(int fromIndex) {
        Coord origin = ports.get(fromIndex);

        for(int i = fromIndex+1; i < ports.size(); i++) {
            Coord nextPort = ports.get(i);

            if(weightMap[nextPort.getX()][nextPort.getY()].getCostSoFar() < Integer.MAX_VALUE) {
                //System.out.println("connecting ports " + fromIndex + " and " + i);

                int pathWeight = weightMap[nextPort.getX()][nextPort.getY()].getCostSoFar();
                ArrayList<Coord> pathCoords = new ArrayList<>();

                makePathCoords(false, new Coord(nextPort.getX(), nextPort.getY()), pathCoords);

                weightMap[origin.getX()][origin.getY()].addExtraPath(nextPort, pathWeight, pathCoords);
                weightMap[nextPort.getX()][nextPort.getY()].addExtraPath(origin, pathWeight, pathCoords);
            }
        }
    }

    private void makePathCoords(boolean forTown, Coord curPos, ArrayList<Coord> coordList) {
        while(true) {
            char dir = weightMap[curPos.getX()][curPos.getY()].getPrevOfPath();
            int extraInd = weightMap[curPos.getX()][curPos.getY()].getPrevBoatPath();
            if(forTown) {
                coordList.add(new Coord(curPos.getX(), curPos.getY()));
            }
            else {
                coordList.add(new Coord(curPos.getX(), curPos.getY(), true));
            }

            if(dir == 'n') {
                curPos.changeY(-1);
            }
            else if(dir == 'e') {
                curPos.changeX(1);
            }
            else if(dir == 's') {
                curPos.changeY(1);
            }
            else if(dir == 'w') {
                curPos.changeX(-1);
            }
            else if(extraInd != -1 && forTown) {
                ExtraPath extraPath = weightMap[curPos.getX()][curPos.getY()].getExtraPaths().get(extraInd);

                curPos.setCoord(extraPath.getDestX(), extraPath.getDestY());
                coordList.addAll(extraPath.getPathCoords());
            }
            else {
                break;
            }
        }

        if(!forTown) {
            coordList.remove(0);
            coordList.remove(coordList.size()-1);
        }
    }

    private void makeListForPitch(int fromIndex) {
        ArrayList<SaleRoute> listForPitch = new ArrayList<>();

        for(int i = fromIndex+1; i < towns.size(); i++) {
            ArrayList<Coord> listForRoute = new ArrayList<>();
            Coord curPos = new Coord(towns.get(i).getX(), towns.get(i).getY());
            int totalCost = weightMap[curPos.getX()][curPos.getY()].getCostSoFar();

            makePathCoords(true, curPos, listForRoute);

            listForPitch.add(new SaleRoute(listForRoute, totalCost));
        }

        salesPitch.add(listForPitch);
    }

    private void resetWeightMap() {
        for(int x = 0; x < weightMap.length; x++) {
            for (int y = 0; y < weightMap[0].length; y++) {
                weightMap[x][y].setCostSoFar(Integer.MAX_VALUE);
                weightMap[x][y].setQAdded(false);
                weightMap[x][y].setPrevOfPath('\0');
                weightMap[x][y].setPrevBoatPath(-1);
            }
        }
    }

    private void setup(Player player) {
        //find towns

        for(int x = 0; x < map.getWidth(); x++) {
            for(int y = 0; y < map.getHeight(); y++) {
                weightMap[x][y] = new Node2D(map.getTile(x, y).getEnergyCost(player));
                weightMap[x][y].setType(map.getTile(x, y).getType());

                if(map.getTile(x, y).getId() == TOWN_ID || map.getTile(x, y).getId() == START_ID) {
                    towns.add(new Coord(x, y));
                    weightMap[x][y].setTown(true);
                }
                else if(map.getTile(x, y).getId() == PORT_ID) {
                    ports.add(new Coord(x, y));
                }

                if(map.getTile(x, y).isBlockingMovement(player)) {
                    weightMap[x][y].setBlocked(true);
                }
            }
        }

        player.switchSailing();

        WATER_WEIGHT = Tiles.SHALLOW_WATER.getEnergyCost(player);

        player.switchSailing();
    }

    private void printDijkstraMap() {
        String ANSI_RESET = "\u001B[0m";
        String ANSI_BLUE = "\u001B[34m";
        String ANSI_PURPLE = "\u001B[35m";
        String ANSI_RED = "\u001B[31m";

        for(int y = 0; y < weightMap[0].length; y++) {
            for(int x = 0; x < weightMap.length; x++) {
                int cost = weightMap[x][y].getCostSoFar();
                if(cost == Integer.MAX_VALUE) {
                    System.out.print("- ");
                }
                else {
                    if(weightMap[x][y].getType() == TileType.PORT) {
                        System.out.print(ANSI_RED + cost + " " + ANSI_RESET);
                    }
                    else if (weightMap[x][y].getType() == TileType.SHALLOW_WATER) {
                        System.out.print(ANSI_BLUE + cost + " " + ANSI_RESET);
                    }
                    else if (weightMap[x][y].isTown()) {
                        System.out.print(ANSI_PURPLE + cost + " " + ANSI_RESET);
                    }
                    else {
                        System.out.print(cost + " ");
                    }

                }

            }
            System.out.println();
        }

        System.out.println();
    }

    private void printDijkstraResult() {
        System.out.println();

        String ANSI_RESET  = "\u001B[0m";
        String ANSI_BLUE = "\u001B[34m";

        for(int origNum = 0; origNum < salesPitch.size(); origNum++) {
            for (int lNum = 0; lNum < salesPitch.get(origNum).size(); lNum++) {
                System.out.print("Total Cost: " + salesPitch.get(origNum).get(lNum).getTotalCost() + "   ");

                for (int lInd = 0; lInd < salesPitch.get(origNum).get(lNum).getPath().size(); lInd++) {
                    Coord c = salesPitch.get(origNum).get(lNum).getPath().get(lInd);
                    if(c.isBoatTile()) {
                        System.out.print(ANSI_BLUE + c.getX() + "/" + c.getY() + " " + ANSI_RESET);
                    }
                    else {
                        System.out.print(c.getX() + "/" + c.getY() + " ");
                    }
                }
                System.out.println();
            }

            System.out.println();
        }

        System.out.println();
    }

    private void printPorts() {
        for(int y = 0; y < weightMap[0].length; y++) {
            for(int x = 0; x < weightMap.length; x++) {
                if(weightMap[x][y].hasExtraPaths()) {
                    ArrayList<ExtraPath> extraPaths = weightMap[x][y].getExtraPaths();

                    System.out.println(x + "/" + y);
                    for (int i = 0; i < extraPaths.size(); i++) {
                        System.out.println("port id: " + i + ", " + extraPaths.get(i).getDestX() + "/" + extraPaths.get(i).getDestY());
                    }
                    System.out.println();
                }
            }
        }
    }

    private void printPathMap() {
        for(int y = 0; y < weightMap[0].length; y++) {
            for(int x = 0; x < weightMap.length; x++) {
                if(weightMap[x][y].hasExtraPaths()) {
                    System.out.print(weightMap[x][y].getPrevBoatPath() + " ");
                }
                else {
                    System.out.print(weightMap[x][y].getPrevOfPath() + " ");
                }
            }
            System.out.println();
        }

        System.out.println();
    }

    private void printWeightMap() {
        String ANSI_RESET = "\u001B[0m";
        String ANSI_BLUE = "\u001B[34m";
        String ANSI_CYAN = "\u001B[36m";
        String ANSI_RED = "\u001B[31m";

        for(int y = 0; y < weightMap[0].length; y++) {
            for(int x = 0; x < weightMap.length; x++) {
                int cost = weightMap[x][y].getWeight();
                TileType type = weightMap[x][y].getType();
                if(weightMap[x][y].isTown()) {
                    System.out.print(ANSI_RED + "T " + ANSI_RESET);
                }
                else if(type == TileType.PORT) {
                    System.out.print(ANSI_CYAN + "P " + ANSI_RESET);
                }
                else if(type == TileType.SHALLOW_WATER) {
                    System.out.print(ANSI_BLUE + "s " + ANSI_RESET);
                }
                else if(type == TileType.DEEP_WATER) {
                    System.out.print(ANSI_BLUE + "d " + ANSI_RESET);
                }
                else {
                    System.out.print(cost + " ");
                }
            }
            System.out.println();
        }

        System.out.println();
    }
}