123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345 |
- package pathgame.algorithm;
- import pathgame.tilemap.TileMap;
- import pathgame.tilemap.TileType;
- import pathgame.tilemap.Tiles;
- import java.util.ArrayList;
- import pathgame.gameplay.Player;
- 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<>();
- 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();
- }
- 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) {
- 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 i = 0; i < extraPaths.size(); i++) {
- ExtraPath path = extraPaths.get(i);
- adjacent(path.getDestX(), path.getDestY(), prevCost, '\0', path, i, 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(0);
- }
- }
- 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();
- coordList.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 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++) {
- if(map.getTile(x, y).getId() == TOWN_ID || map.getTile(x, y).getId() == START_ID) {
- towns.add(new Coord(x, y));
- }
- else if(map.getTile(x, y).getId() == PORT_ID) {
- ports.add(new Coord(x, 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).isBlockingMovement(player)) {
- weightMap[x][y].setBlocked(true);
- }
- }
- }
- player.switchSailing();
- WATER_WEIGHT = Tiles.SHALLOW_WATER.getEnergyCost(player);
- player.switchSailing();
- }
- 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++) {
- int cost = weightMap[x][y].getWeight();
- TileType type = weightMap[x][y].getType();
- if(type == TileType.PORT) {
- System.out.print("P ");
- }
- else if(type == TileType.SHALLOW_WATER) {
- System.out.print("s ");
- }
- else if(type == TileType.DEEP_WATER) {
- System.out.print("d ");
- }
- else {
- System.out.print(cost + " ");
- }
- }
- System.out.println();
- }
- System.out.println();
- }
- }
|