Закончил 3-е упражнение 4-й главы

7 files changed, 488 insertions, 0 deletions

diff --git a/Занимательное программирование/4/3_recursive/src/main/java/net/caraus/labyrinth/Location.java b/Занимательное программирование/4/3_recursive/src/main/java/net/caraus/labyrinth/Location.java
new file mode 100644
index 0000000..b2f5a46
--- /dev/null
+++ b/Занимательное программирование/4/3_recursive/src/main/java/net/caraus/labyrinth/Location.java
@@ -0,0 +1,8 @@
+package net.caraus.labyrinth;
+
+public record Location(boolean leftWall, boolean upWall) {
+    @Override
+    public String toString() {
+        return String.format("(%s, %s)", leftWall, upWall);
+    }
+}
diff --git a/Занимательное программирование/4/3_recursive/src/main/java/net/caraus/labyrinth/Main.java b/Занимательное программирование/4/3_recursive/src/main/java/net/caraus/labyrinth/Main.java
new file mode 100644
index 0000000..2ef6adc
--- /dev/null
+++ b/Занимательное программирование/4/3_recursive/src/main/java/net/caraus/labyrinth/Main.java
@@ -0,0 +1,62 @@
+package net.caraus.labyrinth;
+
+import com.badlogic.gdx.ApplicationAdapter;
+import com.badlogic.gdx.Gdx;
+import com.badlogic.gdx.files.FileHandle;
+import com.badlogic.gdx.graphics.glutils.ShapeRenderer;
+import com.badlogic.gdx.graphics.Color;
+import static com.badlogic.gdx.graphics.glutils.ShapeRenderer.ShapeType;
+import com.badlogic.gdx.utils.ScreenUtils;
+
+import java.io.BufferedReader;
+import java.io.IOException;
+
+/** {@link com.badlogic.gdx.ApplicationListener} implementation shared by all platforms. */
+public class Main extends ApplicationAdapter {
+    private ShapeRenderer shape;
+    private Maze maze;
+    private RecursiveSolve solver;
+
+    @Override
+    public void create() {
+        shape = new ShapeRenderer();
+
+        FileHandle file = Gdx.files.internal("sample.txt");
+
+        try {
+            this.maze = new Maze(file.reader("utf-8"));
+        } catch (IOException e) {
+        }
+        this.solver = new RecursiveSolve(this.maze, new Point(0, 0), new Point(this.maze.width() - 1, 0));
+        this.solver.start();
+    }
+
+    @Override
+    public void render() {
+        ScreenUtils.clear(0.15f, 0.15f, 0.2f, 1f);
+
+        this.shape.begin(ShapeType.Line);
+
+        this.shape.setColor(Color.RED);
+        this.maze.draw(this.shape);
+
+        this.shape.setColor(Color.GREEN);
+        this.solver.draw(this.shape);
+
+        /* this.elapsedTime += Gdx.graphics.getDeltaTime();
+        if (this.elapsedTime > 1.0f) {
+            if (this.solver.solve() != Solution.CONTINUE) {
+                this.elapsedTime = Float.NEGATIVE_INFINITY;
+            } else {
+                this.elapsedTime -= 1.0f;
+            }
+        } */
+
+        this.shape.end();
+    }
+
+    @Override
+    public void dispose() {
+        this.shape.dispose();
+    }
+}
diff --git a/Занимательное программирование/4/3_recursive/src/main/java/net/caraus/labyrinth/Maze.java b/Занимательное программирование/4/3_recursive/src/main/java/net/caraus/labyrinth/Maze.java
new file mode 100644
index 0000000..eaeb72b
--- /dev/null
+++ b/Занимательное программирование/4/3_recursive/src/main/java/net/caraus/labyrinth/Maze.java
@@ -0,0 +1,84 @@
+package net.caraus.labyrinth;
+
+import com.badlogic.gdx.graphics.glutils.ShapeRenderer;
+import com.badlogic.gdx.math.Vector2;
+
+import java.io.BufferedReader;
+import java.io.Reader;
+import java.io.IOException;
+
+public final class Maze {
+    private Location[][] maze;
+
+    public static final int[] DX = {1, 0, -1, 0};
+    public static final int[] DY = {0, -1, 0, 1};
+    public static final float CELL_SIZE = 75.0f;
+
+    public Maze(Reader inputReader) throws IOException {
+        BufferedReader reader = new BufferedReader(inputReader);
+
+        String[] inputPair = reader.readLine().split(" ");
+        var width = Integer.parseInt(inputPair[0]);
+        var height = Integer.parseInt(inputPair[1]);
+
+        this.maze = new Location[width + 1][height + 1];
+
+        for (var y = 0; y <= height; ++y) {
+            for (var x = 0; x <= width; ++x) {
+                if (y == height || x == width) {
+                    this.maze[x][y] = new Location(true, true);
+                } else {
+                    inputPair = reader.readLine().split(" ");
+                    this.maze[x][y] = new Location(inputPair[1].equals("1"), inputPair[0].equals("1"));
+                }
+            }
+        }
+    }
+
+    public int width() {
+        return this.maze == null ? 0 : this.maze.length - 1;
+    }
+
+    public int height() {
+        return this.maze == null ? 0 : this.maze[0].length - 1;
+    }
+
+    public void draw(ShapeRenderer shape) {
+        for (var x = 0; x < width(); ++x) {
+            for (var y = 0; y < height(); ++y) {
+                var start = new Vector2((x + 1) * CELL_SIZE, (height() - y + 1) * CELL_SIZE);
+
+                if (this.maze[x][y].upWall()) {
+                    var end = new Vector2(start).add(CELL_SIZE, 0);
+
+                    shape.line(start, end);
+                }
+                if (this.maze[x][y].leftWall()) {
+                    var end = new Vector2(start).sub(0, CELL_SIZE);
+
+                    shape.line(start, end);
+                }
+            }
+        }
+        // Рисуем нижнюю и правую стены.
+        var edge = new Vector2(CELL_SIZE * (width() + 1), CELL_SIZE);
+        shape.line(new Vector2(CELL_SIZE, CELL_SIZE), edge);
+        shape.line(new Vector2(edge).add(0, height() * CELL_SIZE), edge);
+    }
+
+    public boolean canGo(Point xy, int deltaIndex) {
+        if (DX[deltaIndex] == -1) {
+            return !this.maze[xy.x()][xy.y()].leftWall();
+        } else if (DX[deltaIndex] == 1) {
+            return !this.maze[xy.x() + 1][xy.y()].leftWall();
+        } else if (DY[deltaIndex] == -1) {
+            return !this.maze[xy.x()][xy.y()].upWall();
+        } else {
+            return !this.maze[xy.x()][xy.y() + 1].upWall();
+        }
+    }
+
+    public Location at(Point xy) {
+        return this.maze[xy.x()][xy.y()];
+    }
+}
diff --git a/Занимательное программирование/4/3_recursive/src/main/java/net/caraus/labyrinth/Point.java b/Занимательное программирование/4/3_recursive/src/main/java/net/caraus/labyrinth/Point.java
new file mode 100644
index 0000000..6f70d4c
--- /dev/null
+++ b/Занимательное программирование/4/3_recursive/src/main/java/net/caraus/labyrinth/Point.java
@@ -0,0 +1,4 @@
+package net.caraus.labyrinth;
+
+public record Point(int x, int y) {
+}
diff --git a/Занимательное программирование/4/3_recursive/src/main/java/net/caraus/labyrinth/RecursiveSolve.java b/Занимательное программирование/4/3_recursive/src/main/java/net/caraus/labyrinth/RecursiveSolve.java
new file mode 100644
index 0000000..73a2f25
--- /dev/null
+++ b/Занимательное программирование/4/3_recursive/src/main/java/net/caraus/labyrinth/RecursiveSolve.java
@@ -0,0 +1,81 @@
+package net.caraus.labyrinth;
+
+import com.badlogic.gdx.graphics.glutils.ShapeRenderer;
+import java.util.ArrayList;
+import java.util.HashSet;
+
+public final class RecursiveSolve extends Thread {
+    private Maze maze;
+    private Point start;
+    private Point finish;
+    private boolean[][] visited;
+
+    // Результирующий маршрут.
+    private ArrayList<Point> path;
+
+    public RecursiveSolve(Maze maze, Point start, Point finish) {
+        this.maze = maze;
+        this.start = start;
+        this.finish = finish;
+
+        this.visited = new boolean[this.maze.width()][this.maze.height()];
+        this.path = new ArrayList<>(this.maze.width() * this.maze.height() + 1);
+
+        for (var column: this.visited) {
+            for (var y = 0; y < column.length; ++y) {
+                column[y] = false;
+            }
+        }
+    }
+
+    private boolean solve(Point nLocation) throws InterruptedException {
+        this.visited[nLocation.x()][nLocation.y()] = true; // Пометить локацию как посещенную.
+        synchronized(this) {
+            this.path.add(nLocation); // Добавить ее в описание маршрута.
+        }
+        Thread.sleep(500);
+
+        // Если финишная локация найдена, конец алгоритма.
+        if (this.finish.equals(nLocation)) {
+            return true;
+        }
+        for (var i = 0; i < 4; ++i) {
+            // Если дорожка свободна, идем по ней.
+            var neighbour = new Point(nLocation.x() + Maze.DX[i], nLocation.y() + Maze.DY[i]);
+
+            if (maze.canGo(nLocation, i) && !this.visited[neighbour.x()][neighbour.y()]) {
+                // Если решение найдено, конец алгоритма.
+                if (solve(neighbour)) {
+                    return true;
+                }
+            }
+        }
+        synchronized(this) {
+            this.path.remove(this.path.size() - 1);
+        }
+        return false;
+    }
+
+    @Override
+    public void run() {
+        try {
+            solve(this.start);
+        } catch (InterruptedException e) {
+        }
+    }
+
+    private void drawPoint(ShapeRenderer shape, Point nLocation) {
+        final float markSize = 20.0f;
+        final float halfMark = Maze.CELL_SIZE / 2 - markSize / 2;
+
+        shape.ellipse((nLocation.x() + 1) * Maze.CELL_SIZE + halfMark,
+                (this.maze.height() - nLocation.y()) * Maze.CELL_SIZE + halfMark,
+                markSize, markSize);
+    }
+
+    synchronized public void draw(ShapeRenderer shape) {
+        for (var point: this.path) {
+            drawPoint(shape, point);
+        }
+    }
+}
diff --git a/Занимательное программирование/4/3_recursive/src/main/java/net/caraus/labyrinth/lwjgl3/Lwjgl3Launcher.java b/Занимательное программирование/4/3_recursive/src/main/java/net/caraus/labyrinth/lwjgl3/Lwjgl3Launcher.java
new file mode 100644
index 0000000..d17ac8a
--- /dev/null
+++ b/Занимательное программирование/4/3_recursive/src/main/java/net/caraus/labyrinth/lwjgl3/Lwjgl3Launcher.java
@@ -0,0 +1,45 @@
+package net.caraus.labyrinth.lwjgl3;
+
+import com.badlogic.gdx.backends.lwjgl3.Lwjgl3Application;
+import com.badlogic.gdx.backends.lwjgl3.Lwjgl3ApplicationConfiguration;
+import net.caraus.labyrinth.Main;
+
+/** Launches the desktop (LWJGL3) application. */
+public class Lwjgl3Launcher {
+    public static void main(String[] args) {
+        if (StartupHelper.startNewJvmIfRequired()) return; // This handles macOS support and helps on Windows.
+        createApplication();
+    }
+
+    private static Lwjgl3Application createApplication() {
+        return new Lwjgl3Application(new Main(), getDefaultConfiguration());
+    }
+
+    private static Lwjgl3ApplicationConfiguration getDefaultConfiguration() {
+        Lwjgl3ApplicationConfiguration configuration = new Lwjgl3ApplicationConfiguration();
+        configuration.setTitle("Labyrinth");
+        //// Vsync limits the frames per second to what your hardware can display, and helps eliminate
+        //// screen tearing. This setting doesn't always work on Linux, so the line after is a safeguard.
+        configuration.useVsync(true);
+        //// Limits FPS to the refresh rate of the currently active monitor, plus 1 to try to match fractional
+        //// refresh rates. The Vsync setting above should limit the actual FPS to match the monitor.
+        configuration.setForegroundFPS(Lwjgl3ApplicationConfiguration.getDisplayMode().refreshRate + 1);
+        //// If you remove the above line and set Vsync to false, you can get unlimited FPS, which can be
+        //// useful for testing performance, but can also be very stressful to some hardware.
+        //// You may also need to configure GPU drivers to fully disable Vsync; this can cause screen tearing.
+
+        configuration.setWindowedMode(640, 480);
+        //// You can change these files; they are in lwjgl3/src/main/resources/ .
+        //// They can also be loaded from the root of assets/ .
+        configuration.setWindowIcon("libgdx128.png", "libgdx64.png", "libgdx32.png", "libgdx16.png");
+
+        //// This should improve compatibility with Windows machines with buggy OpenGL drivers, Macs
+        //// with Apple Silicon that have to emulate compatibility with OpenGL anyway, and more.
+        //// This uses the dependency `com.badlogicgames.gdx:gdx-lwjgl3-angle` to function.
+        //// You can choose to remove the following line and the mentioned dependency if you want; they
+        //// are not intended for games that use GL30 (which is compatibility with OpenGL ES 3.0).
+        configuration.setOpenGLEmulation(Lwjgl3ApplicationConfiguration.GLEmulation.ANGLE_GLES20, 0, 0);
+
+        return configuration;
+    }
+}
diff --git a/Занимательное программирование/4/3_recursive/src/main/java/net/caraus/labyrinth/lwjgl3/StartupHelper.java b/Занимательное программирование/4/3_recursive/src/main/java/net/caraus/labyrinth/lwjgl3/StartupHelper.java
new file mode 100644
index 0000000..b62cf6f
--- /dev/null
+++ b/Занимательное программирование/4/3_recursive/src/main/java/net/caraus/labyrinth/lwjgl3/StartupHelper.java
@@ -0,0 +1,204 @@
+/*
+ * Copyright 2020 damios
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at:
+ * https://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+//Note, the above license and copyright applies to this file only.
+
+package net.caraus.labyrinth.lwjgl3;
+
+import com.badlogic.gdx.Version;
+import com.badlogic.gdx.backends.lwjgl3.Lwjgl3NativesLoader;
+import org.lwjgl.system.macosx.LibC;
+import org.lwjgl.system.macosx.ObjCRuntime;
+
+import java.io.BufferedReader;
+import java.io.File;
+import java.io.InputStreamReader;
+import java.lang.management.ManagementFactory;
+import java.util.ArrayList;
+
+import static org.lwjgl.system.JNI.invokePPP;
+import static org.lwjgl.system.JNI.invokePPZ;
+import static org.lwjgl.system.macosx.ObjCRuntime.objc_getClass;
+import static org.lwjgl.system.macosx.ObjCRuntime.sel_getUid;
+
+/**
+ * Adds some utilities to ensure that the JVM was started with the
+ * {@code -XstartOnFirstThread} argument, which is required on macOS for LWJGL 3
+ * to function. Also helps on Windows when users have names with characters from
+ * outside the Latin alphabet, a common cause of startup crashes.
+ * <br>
+ * <a href="https://jvm-gaming.org/t/starting-jvm-on-mac-with-xstartonfirstthread-programmatically/57547">Based on this java-gaming.org post by kappa</a>
+ * @author damios
+ */
+public class StartupHelper {
+
+    private static final String JVM_RESTARTED_ARG = "jvmIsRestarted";
+
+    private StartupHelper() {
+        throw new UnsupportedOperationException();
+    }
+
+    /**
+     * Starts a new JVM if the application was started on macOS without the
+     * {@code -XstartOnFirstThread} argument. This also includes some code for
+     * Windows, for the case where the user's home directory includes certain
+     * non-Latin-alphabet characters (without this code, most LWJGL3 apps fail
+     * immediately for those users). Returns whether a new JVM was started and
+     * thus no code should be executed.
+     * <p>
+     * <u>Usage:</u>
+     *
+     * <pre><code>
+     * public static void main(String... args) {
+     * 	if (StartupHelper.startNewJvmIfRequired(true)) return; // This handles macOS support and helps on Windows.
+     * 	// after this is the actual main method code
+     * }
+     * </code></pre>
+     *
+     * @param redirectOutput
+     *            whether the output of the new JVM should be rerouted to the
+     *            old JVM, so it can be accessed in the same place; keeps the
+     *            old JVM running if enabled
+     * @return whether a new JVM was started and thus no code should be executed
+     *         in this one
+     */
+    public static boolean startNewJvmIfRequired(boolean redirectOutput) {
+        String osName = System.getProperty("os.name").toLowerCase(java.util.Locale.ROOT);
+        if (!osName.contains("mac")) {
+            if (osName.contains("windows")) {
+// Here, we are trying to work around an issue with how LWJGL3 loads its extracted .dll files.
+// By default, LWJGL3 extracts to the directory specified by "java.io.tmpdir", which is usually the user's home.
+// If the user's name has non-ASCII (or some non-alphanumeric) characters in it, that would fail.
+// By extracting to the relevant "ProgramData" folder, which is usually "C:\ProgramData", we avoid this.
+// We also temporarily change the "user.name" property to one without any chars that would be invalid.
+// We revert our changes immediately after loading LWJGL3 natives.
+                String programData = System.getenv("ProgramData");
+                if(programData == null) programData = "C:\\Temp\\"; // if ProgramData isn't set, try some fallback.
+                String prevTmpDir = System.getProperty("java.io.tmpdir", programData);
+                String prevUser = System.getProperty("user.name", "libGDX_User");
+                System.setProperty("java.io.tmpdir", programData + "/libGDX-temp");
+                System.setProperty("user.name", ("User_" + prevUser.hashCode() + "_GDX" + Version.VERSION).replace('.', '_'));
+                Lwjgl3NativesLoader.load();
+                System.setProperty("java.io.tmpdir", prevTmpDir);
+                System.setProperty("user.name", prevUser);
+            }
+            return false;
+        }
+
+        // There is no need for -XstartOnFirstThread on Graal native image
+        if (!System.getProperty("org.graalvm.nativeimage.imagecode", "").isEmpty()) {
+            return false;
+        }
+
+        // Checks if we are already on the main thread, such as from running via Construo.
+        long objc_msgSend = ObjCRuntime.getLibrary().getFunctionAddress("objc_msgSend");
+        long NSThread      = objc_getClass("NSThread");
+        long currentThread = invokePPP(NSThread, sel_getUid("currentThread"), objc_msgSend);
+        boolean isMainThread = invokePPZ(currentThread, sel_getUid("isMainThread"), objc_msgSend);
+        if(isMainThread) return false;
+
+        long pid = LibC.getpid();
+
+        // check whether -XstartOnFirstThread is enabled
+        if ("1".equals(System.getenv("JAVA_STARTED_ON_FIRST_THREAD_" + pid))) {
+            return false;
+        }
+
+        // check whether the JVM was previously restarted
+        // avoids looping, but most certainly leads to a crash
+        if ("true".equals(System.getProperty(JVM_RESTARTED_ARG))) {
+            System.err.println(
+                    "There was a problem evaluating whether the JVM was started with the -XstartOnFirstThread argument.");
+            return false;
+        }
+
+        // Restart the JVM with -XstartOnFirstThread
+        ArrayList<String> jvmArgs = new ArrayList<>();
+        String separator = System.getProperty("file.separator", "/");
+        // The following line is used assuming you target Java 8, the minimum for LWJGL3.
+        String javaExecPath = System.getProperty("java.home") + separator + "bin" + separator + "java";
+        // If targeting Java 9 or higher, you could use the following instead of the above line:
+        //String javaExecPath = ProcessHandle.current().info().command().orElseThrow();
+
+        if (!(new File(javaExecPath)).exists()) {
+            System.err.println(
+                    "A Java installation could not be found. If you are distributing this app with a bundled JRE, be sure to set the -XstartOnFirstThread argument manually!");
+            return false;
+        }
+
+        jvmArgs.add(javaExecPath);
+        jvmArgs.add("-XstartOnFirstThread");
+        jvmArgs.add("-D" + JVM_RESTARTED_ARG + "=true");
+        jvmArgs.addAll(ManagementFactory.getRuntimeMXBean().getInputArguments());
+        jvmArgs.add("-cp");
+        jvmArgs.add(System.getProperty("java.class.path"));
+        String mainClass = System.getenv("JAVA_MAIN_CLASS_" + pid);
+        if (mainClass == null) {
+            StackTraceElement[] trace = Thread.currentThread().getStackTrace();
+            if (trace.length > 0) {
+                mainClass = trace[trace.length - 1].getClassName();
+            } else {
+                System.err.println("The main class could not be determined.");
+                return false;
+            }
+        }
+        jvmArgs.add(mainClass);
+
+        try {
+            if (!redirectOutput) {
+                ProcessBuilder processBuilder = new ProcessBuilder(jvmArgs);
+                processBuilder.start();
+            } else {
+                Process process = (new ProcessBuilder(jvmArgs))
+                        .redirectErrorStream(true).start();
+                BufferedReader processOutput = new BufferedReader(
+                        new InputStreamReader(process.getInputStream()));
+                String line;
+
+                while ((line = processOutput.readLine()) != null) {
+                    System.out.println(line);
+                }
+
+                process.waitFor();
+            }
+        } catch (Exception e) {
+            System.err.println("There was a problem restarting the JVM");
+            e.printStackTrace();
+        }
+
+        return true;
+    }
+
+    /**
+     * Starts a new JVM if the application was started on macOS without the
+     * {@code -XstartOnFirstThread} argument. Returns whether a new JVM was
+     * started and thus no code should be executed. Redirects the output of the
+     * new JVM to the old one.
+     * <p>
+     * <u>Usage:</u>
+     *
+     * <pre>
+     * public static void main(String... args) {
+     * 	if (StartupHelper.startNewJvmIfRequired()) return; // This handles macOS support and helps on Windows.
+     * 	// the actual main method code
+     * }
+     * </pre>
+     *
+     * @return whether a new JVM was started and thus no code should be executed
+     *         in this one
+     */
+    public static boolean startNewJvmIfRequired() {
+        return startNewJvmIfRequired(true);
+    }
+}