Tic Tac Toe Solver! (#253)

* Tic Tac Toe Solver!

* alpha-beta-pruning

* Small changes

---------

Co-authored-by: Yasin <LifeIsAParadox@users.noreply.github.com>

5 files changed, 249 insertions, 0 deletions

diff --git a/src/main/java/me/xmrvizzy/skyblocker/SkyblockerMod.java b/src/main/java/me/xmrvizzy/skyblocker/SkyblockerMod.java
index 4ec579ae..3d1427a2 100644
--- a/src/main/java/me/xmrvizzy/skyblocker/SkyblockerMod.java
+++ b/src/main/java/me/xmrvizzy/skyblocker/SkyblockerMod.java
@@ -10,6 +10,7 @@ import me.xmrvizzy.skyblocker.skyblock.*;
 import me.xmrvizzy.skyblocker.skyblock.dungeon.DungeonBlaze;
 import me.xmrvizzy.skyblocker.skyblock.dungeon.DungeonMap;
 import me.xmrvizzy.skyblocker.skyblock.dungeon.LividColor;
+import me.xmrvizzy.skyblocker.skyblock.dungeon.TicTacToe;
 import me.xmrvizzy.skyblocker.skyblock.dwarven.DwarvenHud;
 import me.xmrvizzy.skyblocker.skyblock.item.CustomArmorDyeColors;
 import me.xmrvizzy.skyblocker.skyblock.item.CustomArmorTrims;
@@ -94,10 +95,12 @@ public class SkyblockerMod implements ClientModInitializer {
         CustomItemNames.init();
         CustomArmorDyeColors.init();
         CustomArmorTrims.init();
+        TicTacToe.init();
         containerSolverManager.init();
         scheduler.scheduleCyclic(Utils::update, 20);
         scheduler.scheduleCyclic(DiscordRPCManager::updateDataAndPresence, 100);
         scheduler.scheduleCyclic(DungeonBlaze::update, 4);
+        scheduler.scheduleCyclic(TicTacToe::tick, 4);
         scheduler.scheduleCyclic(LividColor::update, 10);
         scheduler.scheduleCyclic(BackpackPreview::tick, 50);
         scheduler.scheduleCyclic(DwarvenHud::update, 40);
diff --git a/src/main/java/me/xmrvizzy/skyblocker/config/SkyblockerConfig.java b/src/main/java/me/xmrvizzy/skyblocker/config/SkyblockerConfig.java
index 491ef8ea..68ea596e 100644
--- a/src/main/java/me/xmrvizzy/skyblocker/config/SkyblockerConfig.java
+++ b/src/main/java/me/xmrvizzy/skyblocker/config/SkyblockerConfig.java
@@ -417,6 +417,8 @@ public class SkyblockerConfig implements ConfigData {
         @ConfigEntry.Gui.Tooltip
         public boolean blazesolver = true;
         public boolean solveTrivia = true;
+        @ConfigEntry.Gui.Tooltip
+        public boolean solveTicTacToe = true;
         @ConfigEntry.Gui.CollapsibleObject
         public LividColor lividColor = new LividColor();
         @ConfigEntry.Gui.CollapsibleObject()
diff --git a/src/main/java/me/xmrvizzy/skyblocker/skyblock/dungeon/TicTacToe.java b/src/main/java/me/xmrvizzy/skyblocker/skyblock/dungeon/TicTacToe.java
new file mode 100644
index 00000000..f5d55d2c
--- /dev/null
+++ b/src/main/java/me/xmrvizzy/skyblocker/skyblock/dungeon/TicTacToe.java
@@ -0,0 +1,138 @@
+package me.xmrvizzy.skyblocker.skyblock.dungeon;
+
+import java.util.List;
+
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+import me.xmrvizzy.skyblocker.config.SkyblockerConfig;
+import me.xmrvizzy.skyblocker.utils.RenderUtils;
+import me.xmrvizzy.skyblocker.utils.Utils;
+import me.xmrvizzy.skyblocker.utils.color.QuadColor;
+import me.xmrvizzy.skyblocker.utils.tictactoe.TicTacToeUtils;
+import net.fabricmc.fabric.api.client.rendering.v1.WorldRenderContext;
+import net.fabricmc.fabric.api.client.rendering.v1.WorldRenderEvents;
+import net.minecraft.block.Block;
+import net.minecraft.block.Blocks;
+import net.minecraft.client.MinecraftClient;
+import net.minecraft.client.network.ClientPlayerEntity;
+import net.minecraft.client.world.ClientWorld;
+import net.minecraft.entity.decoration.ItemFrameEntity;
+import net.minecraft.item.FilledMapItem;
+import net.minecraft.item.map.MapState;
+import net.minecraft.util.math.BlockPos;
+import net.minecraft.util.math.Box;
+import net.minecraft.util.math.Direction;
+
+/**
+ * Thanks to Danker for a reference implementation!
+ */
+public class TicTacToe {
+	private static final Logger LOGGER = LoggerFactory.getLogger(TicTacToe.class);
+	private static final QuadColor RED = QuadColor.single(1.0f, 0.0f, 0.0f, 1f);
+	private static Box nextBestMoveToMake = null;
+
+	public static void init() {
+		WorldRenderEvents.BEFORE_DEBUG_RENDER.register(TicTacToe::solutionRenderer);
+	}
+	
+	public static void tick() {
+		MinecraftClient client = MinecraftClient.getInstance();
+		ClientWorld world = client.world;
+		ClientPlayerEntity player = client.player;
+		
+		nextBestMoveToMake = null;
+		
+		if (world == null || player ==  null || !Utils.isInDungeons()) return;
+		
+		//Search within 21 blocks for item frames that contain maps
+		Box searchBox = new Box(player.getX() - 21, player.getY() - 21, player.getZ() - 21, player.getX() + 21, player.getY() + 21, player.getZ() + 21);
+		List<ItemFrameEntity> itemFramesThatHoldMaps = world.getEntitiesByClass(ItemFrameEntity.class, searchBox, ItemFrameEntity::containsMap);
+		
+		try {
+			//Only attempt to solve if its the player's turn
+			if (itemFramesThatHoldMaps.size() != 9 && itemFramesThatHoldMaps.size() % 2 == 1) {
+				char[][] board = new char[3][3];
+				BlockPos leftmostRow = null;
+				int sign = 1;
+				char facing = 'X';
+				
+				for (ItemFrameEntity itemFrame : itemFramesThatHoldMaps) {
+					MapState mapState = world.getMapState(FilledMapItem.getMapName(itemFrame.getMapId().getAsInt()));
+					
+					if (mapState == null) continue;
+					
+					int column = 0, row;
+					sign = 1;
+					
+					//Find position of the item frame relative to where it is on the tic tac toe board
+					if (itemFrame.getHorizontalFacing() == Direction.SOUTH || itemFrame.getHorizontalFacing() == Direction.WEST) sign = -1;
+					BlockPos itemFramePos = BlockPos.ofFloored(itemFrame.getX(), itemFrame.getY(), itemFrame.getZ());
+
+					for (int i = 2; i >= 0; i--) {
+						int realI = i * sign;
+						BlockPos blockPos = itemFramePos;
+						
+						if (itemFrame.getX() % 0.5 == 0) {
+							blockPos = itemFramePos.add(realI, 0, 0);
+						} else if (itemFrame.getZ() % 0.5 == 0) {
+							blockPos = itemFramePos.add(0, 0, realI);
+							facing = 'Z';
+						}
+						
+						Block block = world.getBlockState(blockPos).getBlock();
+						if (block == Blocks.AIR || block == Blocks.STONE_BUTTON) {
+							leftmostRow = blockPos;
+							column = i;
+							
+							break;
+						}
+					}
+					
+					//Determine the row of the item frame
+					if (itemFrame.getY() == 72.5) {
+						row = 0;
+					} else if (itemFrame.getY() == 71.5) {
+						row = 1;
+					} else if (itemFrame.getY() == 70.5) {
+						row = 2;
+					} else {
+						continue;
+					}
+					
+					
+					//Get the color of the middle pixel of the map which determines whether its X or O
+					int middleColor = mapState.colors[8256] & 255;
+					
+					if (middleColor == 114) {
+						board[row][column] = 'X';
+					} else if (middleColor == 33) {
+						board[row][column] = 'O';
+					}
+					
+					int bestMove = TicTacToeUtils.getBestMove(board) - 1;
+					
+					if (leftmostRow != null) {
+						double drawX = facing == 'X' ? leftmostRow.getX() - sign * (bestMove % 3) : leftmostRow.getX();
+						double drawY = 72 - (double) (bestMove / 3);
+						double drawZ = facing == 'Z' ? leftmostRow.getZ() - sign * (bestMove % 3) : leftmostRow.getZ();
+						
+						nextBestMoveToMake = new Box(drawX, drawY, drawZ, drawX + 1, drawY + 1, drawZ + 1);
+					}
+				}
+			}
+		} catch (Exception e) {
+			LOGGER.error("[Skyblocker Tic Tac Toe] Encountered an exception while determining a tic tac toe solution!", e);
+		}
+	}
+	
+	private static void solutionRenderer(WorldRenderContext context) {		
+		try {
+			if (SkyblockerConfig.get().locations.dungeons.solveTicTacToe && nextBestMoveToMake != null) {
+				RenderUtils.drawBoxOutline(nextBestMoveToMake, RED, 5);
+			}
+		} catch (Exception e) {
+			LOGGER.error("[Skyblocker Tic Tac Toe] Encountered an exception while rendering the tic tac toe solution!", e);
+		}
+	}
+}
diff --git a/src/main/java/me/xmrvizzy/skyblocker/utils/tictactoe/TicTacToeUtils.java b/src/main/java/me/xmrvizzy/skyblocker/utils/tictactoe/TicTacToeUtils.java
new file mode 100644
index 00000000..5e5c8f89
--- /dev/null
+++ b/src/main/java/me/xmrvizzy/skyblocker/utils/tictactoe/TicTacToeUtils.java
@@ -0,0 +1,104 @@
+package me.xmrvizzy.skyblocker.utils.tictactoe;
+
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.Map;
+
+public class TicTacToeUtils {
+
+    public static int getBestMove(char[][] board) {
+        HashMap<Integer, Integer> moves = new HashMap<>();
+        for (int row = 0; row < board.length; row++) {
+            for (int col = 0; col < board[row].length; col++) {
+                if (board[row][col] != '\0') continue;
+                board[row][col] = 'O';
+                int score = alphabeta(board, Integer.MIN_VALUE, Integer.MAX_VALUE, false, 0);
+                board[row][col] = '\0';
+                moves.put(row * 3 + col + 1, score);
+            }
+        }
+        return Collections.max(moves.entrySet(), Map.Entry.comparingByValue()).getKey();
+    }
+
+    public static boolean hasMovesLeft(char[][] board) {
+        for (char[] rows : board) {
+            for (char col : rows) {
+                if (col == '\0') return true;
+            }
+        }
+        return false;
+    }
+
+    public static int getBoardRanking(char[][] board) {
+        for (int row = 0; row < 3; row++) {
+            if (board[row][0] == board[row][1] && board[row][0] == board[row][2]) {
+                if (board[row][0] == 'X') {
+                    return -10;
+                } else if (board[row][0] == 'O') {
+                    return 10;
+                }
+            }
+        }
+
+        for (int col = 0; col < 3; col++) {
+            if (board[0][col] == board[1][col] && board[0][col] == board[2][col]) {
+                if (board[0][col] == 'X') {
+                    return -10;
+                } else if (board[0][col] == 'O') {
+                    return 10;
+                }
+            }
+        }
+
+        if (board[0][0] == board[1][1] && board[0][0] == board[2][2]) {
+            if (board[0][0] == 'X') {
+                return -10;
+            } else if (board[0][0] == 'O') {
+                return 10;
+            }
+        } else if (board[0][2] == board[1][1] && board[0][2] == board[2][0]) {
+            if (board[0][2] == 'X') {
+                return -10;
+            } else if (board[0][2] == 'O') {
+                return 10;
+            }
+        }
+
+        return 0;
+    }
+    public static int alphabeta(char[][] board, int alpha, int beta, boolean max, int depth) {
+        int score = getBoardRanking(board);
+        if (score == 10 || score == -10) return score;
+        if (!hasMovesLeft(board)) return 0;
+
+        if (max) {
+            int bestScore = Integer.MIN_VALUE;
+            for (int row = 0; row < 3; row++) {
+                for (int col = 0; col < 3; col++) {
+                    if (board[row][col] == '\0') {
+                        board[row][col] = 'O';
+                        bestScore = Math.max(bestScore, alphabeta(board, alpha, beta, false, depth + 1));
+                        board[row][col] = '\0';
+                        alpha = Math.max(alpha, bestScore);
+                        if (beta <= alpha) break; // Pruning
+                    }
+                }
+            }
+            return bestScore - depth;
+        } else {
+            int bestScore = Integer.MAX_VALUE;
+            for (int row = 0; row < 3; row++) {
+                for (int col = 0; col < 3; col++) {
+                    if (board[row][col] == '\0') {
+                        board[row][col] = 'X';
+                        bestScore = Math.min(bestScore, alphabeta(board, alpha, beta, true, depth + 1));
+                        board[row][col] = '\0';
+                        beta = Math.min(beta, bestScore);
+                        if (beta <= alpha) break; // Pruning
+                    }
+                }
+            }
+            return bestScore + depth;
+        }
+    }
+}
\ No newline at end of file
diff --git a/src/main/resources/assets/skyblocker/lang/en_us.json b/src/main/resources/assets/skyblocker/lang/en_us.json
index 39a215d2..ae24d9ed 100644
--- a/src/main/resources/assets/skyblocker/lang/en_us.json
+++ b/src/main/resources/assets/skyblocker/lang/en_us.json
@@ -208,6 +208,8 @@
   "text.autoconfig.skyblocker.option.locations.dungeons.blazesolver": "Solve Blaze Puzzle",
   "text.autoconfig.skyblocker.option.locations.dungeons.blazesolver.@Tooltip": "Boxes the correct blaze in green, also draws a line to and boxes the next blaze to kill in white.",
   "text.autoconfig.skyblocker.option.locations.dungeons.solveTrivia": "Solve Trivia Puzzle",
+  "text.autoconfig.skyblocker.option.locations.dungeons.solveTicTacToe": "Solve Tic Tac Toe Puzzle",
+  "text.autoconfig.skyblocker.option.locations.dungeons.solveTicTacToe.@Tooltip": "Puts a red box around the next best move for you to make!",
   "text.autoconfig.skyblocker.option.locations.dungeons.lividColor": "Livid Color",
   "text.autoconfig.skyblocker.option.locations.dungeons.lividColor.enableLividColor": "Enable Livid Color",
   "text.autoconfig.skyblocker.option.locations.dungeons.lividColor.enableLividColor.@Tooltip": "Send the livid color in the chat during the Livid boss fight.",