FlorianF

Pathfinding with disappearing platforms

Aug 18th, 2020
244
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package stackexchange;
  2.  
  3. import java.util.*;
  4.  
  5. /**
  6.  *      V W X Y Z [
  7.  *      . . U . . .
  8.  *      . . . T . .
  9.  *      . Q R S . .
  10.  *      . P O . . .
  11.  *      . . N . . .
  12.  *      . . . M L .
  13.  *      . . . J K .
  14.  *      . . I . . .
  15.  *      . . H . . .
  16.  *      . G . . . .
  17.  *      F E D C B A
  18.  */
  19. public class TileLabyrinth1 {
  20.  
  21.     /** NUmber of tiles */
  22.     public static int SIZE = 27;
  23.    
  24.     /** Groups of tiles belonging to the same "ray".  Left, center and right */
  25.     public static String[][] GROUPS =
  26.             { { "AI", "BH", "C", "DG", "E", "F", "J", "KMNP", "LOQ", "R", "SV", "TUW", "X", "Y", "Z", "[" }
  27.             , { "A[", "BKLZ", "CJMSTY", "DHINORUX", "EGPQW", "FV" }
  28.             , { "A", "B", "C", "D", "E", "FGHK", "IJL", "M", "N", "OS", "PRT[", "QZ", "UY", "V", "W", "X" }
  29.             };
  30.    
  31.     public static int[][][] raysByDir;
  32.    
  33.     public static String uniqueKey(int[] board){
  34.         StringBuilder sb = new StringBuilder();
  35.         for( int i=0 ; i<board.length ; i++ ){
  36.             sb.append(String.valueOf((char)('A' + i)).repeat(board[i]));
  37.         }
  38.         return sb.toString();
  39.     }
  40.    
  41.     public static String boardToString(int[] board){
  42.         StringBuilder sb = new StringBuilder();
  43.         for( int i=0 ; i<board.length ; i++ ){
  44.             sb.append((board[i] == 0) ? '.' : (char)('A'+i));
  45.         }
  46.         return sb.toString();
  47.     }
  48.    
  49.     /** Initialize the rays index by direction */
  50.     public static void initLaby(){
  51.         raysByDir = new int[SIZE][GROUPS.length][];
  52.         for( int iFrom=0 ; iFrom < SIZE ; iFrom++ ){
  53.             for( int dir=0 ; dir<GROUPS.length ; dir++ ){
  54.                 int[] rayDir = new int[SIZE];
  55.                 int p = 0;
  56.                 for( String group : GROUPS[dir] ){
  57.                     String[] tiles = group.split("");
  58.                     for( String from : tiles ){
  59.                         if( from.equals("" + (char)('A'+iFrom)) ){
  60.                             for( String to : tiles ){
  61.                                 if( !from.equals(to) ){
  62.                                     rayDir[p++] = (char)(to.charAt(0) - 'A');
  63.                                 }
  64.                             }
  65.                         }
  66.                     }
  67.                 }
  68.                 raysByDir[iFrom][dir] = Arrays.copyOf(rayDir, p);
  69.             }
  70.         }
  71.     }
  72.    
  73.     public static boolean[] calcSolid(int[] board){
  74.         boolean[] solid = new boolean[board.length];
  75.         for( int i=0 ; i<6 ; i++ ){
  76.             solid[i] = true;
  77.         }
  78.         for( int i=6 ; i<board.length-6 ; i++ ){
  79.             boolean[] crossDir = new boolean[3];
  80.             for( int dir=0 ; dir<3 ; dir++ ){
  81.                 for( int j : raysByDir[i][dir] ){
  82.                     crossDir[dir] |= board[j] > 0;
  83.                 }
  84.             }
  85.             solid[i] = (crossDir[0]?1:0) + (crossDir[1]?1:0) + (crossDir[2]?1:0) >= 2;
  86.         }
  87.         for( int i=board.length-6 ; i<board.length ; i++ ){
  88.             solid[i] = true;
  89.         }
  90.         return solid;
  91.     }
  92.  
  93.     public static void printSol(Pos pos){
  94.         List<Pos> solution = new ArrayList<>();
  95.         while( pos != null ){
  96.             solution.add(pos);
  97.             pos = pos.prev;
  98.         }
  99.         Pos prevPos = null;
  100.         for( int s=solution.size() ; s-->0 ; ){
  101.             pos = solution.get(s);
  102.             StringBuilder sb = new StringBuilder();
  103.             if( prevPos == null ){
  104.                 sb.append("solution: ");
  105.             } else {
  106.                 sb.append("  ");
  107.                 for( int i=0 ; i<pos.board.length ; i++ ){
  108.                     if( pos.board[i] < prevPos.board[i] ) sb.append((char)('A'+i));
  109.                 }
  110.                 sb.append(" -> ");
  111.                 for( int i=0 ; i<pos.board.length ; i++ ){
  112.                     if( pos.board[i] > prevPos.board[i] ) sb.append((char)('A'+i));
  113.                 }
  114.                 sb.append(": ");
  115.             }
  116.             System.out.println(sb.toString() + boardToString(pos.board));
  117.             prevPos = pos;
  118.         }
  119.     }
  120.  
  121.     /** Breadth-first search for all positions reachable from the start */
  122.     public static void searchPath(){
  123.         int bestProgress = 0;
  124.         Pos bestPos = null;
  125.         int[] startBoard = new int[] { 1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 };
  126.         Map<String,Pos> positionsDone = new HashMap<>();
  127.         List<Pos> positionsTodo = new LinkedList<>();
  128.         Pos startPos = new Pos(startBoard, null, 0);
  129.         positionsDone.put(uniqueKey(startBoard), startPos);
  130.         positionsTodo.add(startPos);
  131.         while( !positionsTodo.isEmpty() && bestProgress%100 <= 20 ){
  132.             Pos posFrom = positionsTodo.remove(0);
  133.             int[] board = posFrom.board.clone();
  134.             for( int i = 0 ; i < board.length ; i++ ){
  135.                 if( board[i] == 0 ) continue;
  136.                 board[i]--;
  137.  
  138.                 boolean[] solid = calcSolid(board);
  139.                 boolean valid = true;
  140.                 for( int j=0 ; j<board.length ; j++ ){
  141.                     valid &= (board[j] == 0 || solid[j]);
  142.                 }
  143.                 if( valid ){
  144.                     int j0 = i;
  145.                     while( j0>0 && solid[j0-1] ) j0--;
  146.                     int j1 = i;
  147.                     while( j1<solid.length-1 && solid[j1+1] ) j1++;
  148.                     for( int j = j0 ; j <= j1 ; j++ ){
  149.                         if( j == i || !solid[j] ) continue;
  150.                         board[j]++;
  151.    
  152.                         Pos newPos = new Pos(board, posFrom, posFrom.dist+1);
  153.                         Pos oldPos = positionsDone.get(uniqueKey(board));
  154.                         if( oldPos == null || oldPos.dist > newPos.dist ){
  155.                             positionsDone.put(uniqueKey(board), newPos);
  156.                             positionsTodo.add(newPos);
  157.    
  158.                             int last = -1;
  159.                             int first = 0;
  160.                             for( int k=0 ; k<board.length ; k++ ){
  161.                                 if( board[k] != 0 ){
  162.                                     if( last<0 ) last = k;
  163.                                     first = k;
  164.                                 }
  165.                             }
  166.                             int progress = last*100 + first;
  167.                             if( progress > bestProgress ){
  168.                                 System.out.println("progress " + progress + " todo " + positionsTodo.size() + " done " + positionsDone.size());
  169.                                 bestProgress = progress;
  170.                                 bestPos = newPos;
  171.                             }
  172.                         }
  173.                         board[j]--;
  174.                     }
  175.                 } // if valid
  176.  
  177.                 board[i]++;
  178.             }
  179.         }
  180.  
  181.         printSol(bestPos);
  182.     }
  183.    
  184.     public static void main(String[] args) {
  185.         initLaby();
  186.         searchPath();
  187.     }
  188.  
  189.     static class Pos {
  190.         int[] board;
  191.         Pos prev;
  192.         int dist;
  193.        
  194.         public Pos(int[] board, Pos prev, int dist){
  195.             this.board = board.clone();
  196.             this.prev = prev;
  197.             this.dist = dist;
  198.         }
  199.    
  200.     }
  201. }
  202.  
RAW Paste Data