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

package pathgame.algorithm;


import pathgame.gameplay.PlayerAbilities;
import pathgame.tilemap.TileMap;

import java.util.ArrayList;

public class DijkstraMagic {
    private int townID = 18;
    private ArrayList<Coord> towns = new ArrayList<>();
    private TileMap map;
    private Node2D[][] weightMap;
    private ArrayList<ArrayList<SaleRoute>> salesPitch = new ArrayList<>();

    public DijkstraMagic(TileMap map) {
        this.map = map;

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

        setup();

        printWeightMap();

        for(int i = 0; i < towns.size(); i++) {
            doMagicforTown(i);
        }

        printDijkstraResult();
    }

    public ArrayList<ArrayList<SaleRoute>> getSalesPitch() {
        return salesPitch;
    }

    private void doMagicforTown(int fromIndex) {
        if(fromIndex != 0) {
            resetWeightMap();
        }

        Coord origin = towns.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;
                }
            }

            dijkstraOnTile(tileQ.get(leastIndex).getX(), tileQ.get(leastIndex).getY(), tileQ, leastIndex);
        }

        makeListForPitch(fromIndex);

        //printDijkstraMap();
    }

    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();

            while(true) {
                char dir = weightMap[curPos.getX()][curPos.getY()].getPrevOfPath();

                listForRoute.add(new Coord(curPos.getX(), curPos.getY()));

                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 {
                    break;
                }
            }

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

        salesPitch.add(listForPitch);
    }

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

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

        if(weightMap[posX][posY].hasExtraPaths()) {
            //TODO: implement extra path stuff
        }

        tileQ.remove(qIndex);

        if(posX < weightMap.length-1) {
            if(!weightMap[posX+1][posY].isQAdded()) {
                weightMap[posX+1][posY].setQAdded(true);
                tileQ.add(new Coord(posX+1, posY));
            }
        }
        if(posX > 0) {
            if(!weightMap[posX-1][posY].isQAdded()) {
                weightMap[posX-1][posY].setQAdded(true);
                tileQ.add(new Coord(posX-1, posY));
            }
        }
        if(posY < weightMap[0].length-1) {
            if(!weightMap[posX][posY+1].isQAdded()) {
                weightMap[posX][posY+1].setQAdded(true);
                tileQ.add(new Coord(posX, posY+1));
            }
        }
        if(posY > 0) {
            if(!weightMap[posX][posY-1].isQAdded()) {
                weightMap[posX][posY-1].setQAdded(true);
                tileQ.add(new Coord(posX, posY-1));
            }
        }

        if(weightMap[posX][posY].hasExtraPaths()) {
            //TODO: implement extra path stuff
        }
    }

    private void checkNeighbor(int posX, int posY, int prevCost, char origin) {
        int newCost = prevCost + weightMap[posX][posY].getWeight();

        if(newCost < weightMap[posX][posY].getCostSoFar()) {
            weightMap[posX][posY].setCostSoFar(newCost);
            weightMap[posX][posY].setPrevOfPath(origin);
        }
    }

    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');
            }
        }
    }

    private void setup() {
        //find towns
        //mock implementation
        /*
        //test start
        towns.add(new Coord(0, 0));
        towns.add(new Coord(2, 3));
        towns.add(new Coord(4, 1));
        towns.add(new Coord(0, 4));
        towns.add(new Coord(4, 7));
        towns.add(new Coord(2, 5));
        towns.add(new Coord(3, 9));
        towns.add(new Coord(1, 8));
        //new test
        towns.add(new Coord(1, 3));
        towns.add(new Coord(1, 5));

        towns.add(new Coord(1, 14));
        towns.add(new Coord(0, 10));
        //towns.add(new Coord(2, 8));
        //towns.add(new Coord(0, 2));
        //towns.add(new Coord(0, 5));
        //towns.add(new Coord(0, 14));
        //towns.add(new Coord(1, 0));
        //towns.add(new Coord(1, 7));
        //towns.add(new Coord(1, 9));
        //towns.add(new Coord(1, 11));*/



        /*weightMap[0][0] = new Node2D(1);
        weightMap[1][0] = new Node2D(1);
        weightMap[2][0] = new Node2D(1);
        weightMap[3][0] = new Node2D(5);
        weightMap[4][0] = new Node2D(5);

        weightMap[0][1] = new Node2D(1);
        weightMap[1][1] = new Node2D(10);
        weightMap[2][1] = new Node2D(1);
        weightMap[3][1] = new Node2D(5);
        weightMap[4][1] = new Node2D(1);

        weightMap[0][2] = new Node2D(1);
        weightMap[1][2] = new Node2D(10);
        weightMap[2][2] = new Node2D(1);
        weightMap[3][2] = new Node2D(1);
        weightMap[4][2] = new Node2D(1);

        weightMap[0][3] = new Node2D(1);
        weightMap[1][3] = new Node2D(1);
        weightMap[2][3] = new Node2D(1);
        weightMap[3][3] = new Node2D(1);
        weightMap[4][3] = new Node2D(5);

        weightMap[0][4] = new Node2D(1);
        weightMap[1][4] = new Node2D(1);
        weightMap[2][4] = new Node2D(1);
        weightMap[3][4] = new Node2D(5);
        weightMap[4][4] = new Node2D(5);

        weightMap[0][5] = new Node2D(1);
        weightMap[1][5] = new Node2D(1);
        weightMap[2][5] = new Node2D(1);
        weightMap[3][5] = new Node2D(5);
        weightMap[4][5] = new Node2D(5);

        weightMap[0][6] = new Node2D(1);
        weightMap[1][6] = new Node2D(10);
        weightMap[2][6] = new Node2D(1);
        weightMap[3][6] = new Node2D(5);
        weightMap[4][6] = new Node2D(1);

        weightMap[0][7] = new Node2D(1);
        weightMap[1][7] = new Node2D(1);
        weightMap[2][7] = new Node2D(1);
        weightMap[3][7] = new Node2D(1);
        weightMap[4][7] = new Node2D(1);

        weightMap[0][8] = new Node2D(1);
        weightMap[1][8] = new Node2D(1);
        weightMap[2][8] = new Node2D(1);
        weightMap[3][8] = new Node2D(1);
        weightMap[4][8] = new Node2D(5);

        weightMap[0][9] = new Node2D(1);
        weightMap[1][9] = new Node2D(1);
        weightMap[2][9] = new Node2D(1);
        weightMap[3][9] = new Node2D(1);
        weightMap[4][9] = new Node2D(5);

        weightMap[0][10] = new Node2D(1);
        weightMap[1][10] = new Node2D(5);
        weightMap[2][10] = new Node2D(1);
        weightMap[3][10] = new Node2D(5);
        weightMap[4][10] = new Node2D(5);

        weightMap[0][11] = new Node2D(1);
        weightMap[1][11] = new Node2D(1);
        weightMap[2][11] = new Node2D(1);
        weightMap[3][11] = new Node2D(5);
        weightMap[4][11] = new Node2D(1);

        weightMap[0][12] = new Node2D(1);
        weightMap[1][12] = new Node2D(10);
        weightMap[2][12] = new Node2D(1);
        weightMap[3][12] = new Node2D(1);
        weightMap[4][12] = new Node2D(1);

        weightMap[0][13] = new Node2D(1);
        weightMap[1][13] = new Node2D(10);
        weightMap[2][13] = new Node2D(1);
        weightMap[3][13] = new Node2D(1);
        weightMap[4][13] = new Node2D(5);

        weightMap[0][14] = new Node2D(1);
        weightMap[1][14] = new Node2D(1);
        weightMap[2][14] = new Node2D(1);
        weightMap[3][14] = new Node2D(5);
        weightMap[4][14] = new Node2D(5);*/

        //test end

        /*towns.add(new Coord(6, 10));
        towns.add(new Coord(30, 29));
        towns.add(new Coord(41, 20));
        towns.add(new Coord(42, 24));
        towns.add(new Coord(26, 41));

        towns.add(new Coord(39, 26));
        towns.add(new Coord(16, 8));
        towns.add(new Coord(6, 27));
        towns.add(new Coord(26, 7));
        towns.add(new Coord(28, 13));

        towns.add(new Coord(49, 4));
        towns.add(new Coord(34, 47));
        towns.add(new Coord(20, 20));
        towns.add(new Coord(43, 32));
        towns.add(new Coord(43, 21));

        towns.add(new Coord(3, 43));
        towns.add(new Coord(34, 8));
        towns.add(new Coord(30, 17));
        towns.add(new Coord(35, 49));
        towns.add(new Coord(28, 10));*/


        for(int x = 0; x < map.getWidth(); x++) {
            for(int y = 0; y < map.getHeight(); y++) {

                //actual implementation - find towns; townID needs to be set to correct value

                if(map.getTile(x, y).getId() == townID) {
                    towns.add(new Coord(x, y));
                }

                //translate map to weightMap
                //TODO: boats

                PlayerAbilities test = new PlayerAbilities("", 0, 0, 0, 0, 0, 0, 0);

                weightMap[x][y] = new Node2D(map.getTile(x, y).getEnergyCost(test));
            }
        }
    }

    private void printDijkstraMap() {
        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 {

                    System.out.print(cost + " ");
                }

            }
            System.out.println();
        }

        System.out.println();
    }

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

        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++) {
                    System.out.print(salesPitch.get(origNum).get(lNum).getPath().get(lInd).getX() + "/" + salesPitch.get(origNum).get(lNum).getPath().get(lInd).getY() + " ");
                }
                System.out.println();
            }

            System.out.println();
        }

        System.out.println();
    }

    private void printWeightMap() {
        for(int y = 0; y < weightMap[0].length; y++) {
            for(int x = 0; x < weightMap.length; x++) {
                System.out.print(weightMap[x][y].getWeight() + " ");
            }
            System.out.println();
        }

        System.out.println();
    }
}