MazeAlgo

Other docs: CHANGELOG.md — versioned history · DEVOPS.md — CI/CD pipeline & release engineering

A 2D / 3D maze generation and search engine with a multi-threaded server backend and a JavaFX GUI.

This started as a university assignment and is being built out into a portfolio-grade project: clean MVVM separation, classic GoF design patterns, multi-threaded networking with smart caching, and full unit + integration test coverage.

2D mode — 20×20 maze, player at start, "A Job" goal at bottom-right	3D mode — rotatable cube with Focus combo for isolating a single layer

---

Quick start

Three steps. ~2 minutes on a clean machine.

1. Install JDK 17+ — Adoptium Temurin 17 (any vendor works; verify with java -version).

2. Download the JAR from the latest release — maze-algo-*-all.jar, ~16 MB, runs on Windows / macOS / Linux.

3. Run it:

   java -jar maze-algo-*-all.jar

The window opens with a generated 20×20 maze.

Drive the app

Action	How
Generate a new maze	Set rows / cols in the toolbar, click Generate
Move the player	W A S D or the arrow keys (8-directional in 2D)
Zoom	Scroll wheel
Pan	Click-drag; right-click recenters
Show optimal path	Solution Hint (orange dotted line)
Animate the search	Watch Search (Best-First paints visited cells yellow over ~3 s)
Switch to 3D	Pick 3D in the dimension combo, then rotate the cube with the mouse; use Focus to isolate one layer
Win	Reach the goal — a C–E–G–C chime plays

Building from source, contributing, or running the standalone server demo? See DEVOPS.md.

---

TL;DR

• What it is. A maze engine — generates 2D/3D mazes, solves them with BFS / DFS / Best-First (A* with admissible heuristics), and serves both operations over sockets.
• Status. 42 / 42 tests passing, shipped as a downloadable cross-platform JAR via a tag-triggered release pipeline.
• For the technically curious. Adapter, Strategy, Decorator, and Template Method patterns all appear here in real load-bearing roles — not as toy examples. The server caches solutions on disk keyed by SHA-256 of the maze bytes; an integration test confirms the search algorithm runs exactly once across two identical requests.

---

Tech stack

Layer	Choice
Language	Java 17 (compiled with --release 17, runs on JDK 17+)
Build	Maven 3.9
UI	JavaFX 17.0.11 — controls, fxml, media
Logging	Log4j2
Tests	JUnit Jupiter 5.8.1 (42 tests, all passing)

---

What's interesting in here

• Three search algorithms over a common interface. BFS, DFS, and a Best-First Search that behaves like A* when the domain supplies an admissible heuristic. Octile distance for 2D (diagonal moves cost more than straight moves), Manhattan distance scaled by step-cost for 3D — both proven admissible in comments next to the code.
• Adapter pattern keeps the search algorithms decoupled from the maze representation: SearchableMaze and SearchableMaze3D expose Maze / Maze3D as a generic ISearchable, so the same BestFirstSearch solves both 2D and 3D problems with zero changes.
• Iterative DFS (explicit stack, no recursion) so a 1000×1000 maze doesn't blow the JVM stack.
• Diagonal move legality. A diagonal step in 2D is only allowed when at least one of the two orthogonal cells around the corner is also open — paths can't squeeze through a wall pinhole.
• Multi-threaded socket server with an ExecutorService thread pool and a setSoTimeout-driven accept loop, so stop() is responsive even when no clients are connecting.
• Smart caching. Identical solve requests don't re-run the algorithm — SolutionCache keys solutions by SHA-256 of the maze bytes and stores them on disk under $TMPDIR/MazeAlgo/cache/. An integration test verifies that two identical requests invoke the search algorithm exactly once.
• Streaming run-length encoding via the MyCompressorOutputStream Decorator — a 10,000-byte sparse maze grid lands in well under 1 KB on the wire (>10× compression, asserted in the test suite).
• MVVM data binding all the way down. The custom MazeDisplayer Canvas binds to MazeViewModel properties (maze, playerRow, playerColumn, zoom) — moving the player updates the model, the view re-paints automatically, no manual repaint() plumbing.
• 42 tests, all passing, including a full end-to-end test that spins up MyServer on an OS-assigned port and verifies both strategies via real sockets, 10 ViewModel tests covering movement rules and the diagonal-pinhole edge case, and 6 listener-contract tests that pin the per-node observer hook used by the UI's "Watch Search" visualizer.

---

Architecture

                           ┌──────────────────────────────────┐
                           │   View  (JavaFX)                 │
                           │   MazeView.fxml + Controller     │
                           │   MazeDisplayer Canvas           │
                           └────────────────┬─────────────────┘
                                            │ binds to JavaFX properties
                           ┌────────────────▼─────────────────┐
                           │           ViewModel              │
                           │   maze / solution / playerRow    │
                           │   playerColumn   (Observable)    │
                           └────────────────┬─────────────────┘
                                            │
                           ┌────────────────▼─────────────────┐
                           │            Model                 │
                           │   ┌────────────┐  ┌───────────┐  │
                           │   │ Algorithms │  │  Server   │  │
                           │   │ (gen+sea-  │  │ + Cache + │  │
                           │   │  rch +     │  │  Compres- │  │
                           │   │  adapters) │  │  sion     │  │
                           │   └────────────┘  └───────────┘  │
                           └──────────────────────────────────┘

The UI talks to the server, not the algorithms directly. When you launch mvn javafx:run, MazeApp.start() spawns two embedded MyServer instances on OS-assigned ports (one hosting GenerateMazeStrategy, one hosting SolveMazeStrategy) and injects those ports into MazeModel via the FXMLLoader controller factory. Every Generate click sends int[]{rows, cols} over a socket, receives RLE-compressed bytes, and reconstructs the Maze. Every Solution Hint click sends the Maze over a socket and receives a Solution from the SHA-256-keyed cache (or a fresh Best-First run on cache miss). The Watch Search mode stays in-process — it needs the per-node observer callback that the server protocol doesn't stream.

---

Design patterns at a glance

Pattern	Where	Why it's here
Adapter	SearchableMaze, SearchableMaze3D	The search algorithms speak ISearchable, not Maze. The adapters expose a 2D Maze (8 neighbours, diagonals with the pinhole rule) and a 3D Maze3D (6 neighbours, no diagonals) under the same interface, so one BestFirstSearch solves both dimensionalities with zero changes.
Strategy	ISearchingAlgorithm (BreadthFirstSearch, DepthFirstSearch, BestFirstSearch)	Swappable searchers behind a uniform solve(ISearchable) → Solution contract. Adding a new algorithm doesn't touch any caller — the MazeViewModel, the SolveMazeStrategy, the SolutionCache all keep working.
Strategy	IServerStrategy (GenerateMazeStrategy, SolveMazeStrategy)	One pluggable behaviour per server endpoint. MyServer doesn't know what the strategy does; it just dispatches sockets to it. Adding a new endpoint = one new class implementing serverStrategy(in, out).
Decorator	MyCompressorOutputStream / MyDecompressorInputStream	Wrap any OutputStream / InputStream to add streaming run-length encoding without anyone caring. The server hands a wrapped stream to the generate path; the client unwraps with the matching decorator. Same maze bytes go in either side of the wrapper.
Template Method	ASearchingAlgorithm, AMazeGenerator, AMaze3DGenerator	Shared concerns (counter reset, the per-node listener callback, timing) live in the base class; subclasses fill in only the variable bits (open structure for searchers, carve algorithm for generators).
Factory (Supplier)	SolveMazeStrategy(cache, () -> new BestFirstSearch())	A fresh searcher per request, injected as a Supplier — keeps the strategy testable (the integration test verifies the cache by counting how often the supplier is invoked) and avoids leaking state across pooled solves.
Observer (callback)	ASearchingAlgorithm.setNodeEvaluatedListener(...)	Lets the UI watch the search happen. The "Watch Search" button registers a listener that funnels each evaluated state into the canvas's visited-cells set on the JavaFX thread. Server / sync paths register no listener and pay nothing.

---

Best-First → A* (the heuristic does all the work)

Best-First reduces to A* exactly when the heuristic is admissible — it never overestimates the true remaining cost. The reduction itself is one swap: replace BFS's FIFO with a priority queue ordered by g + h (cost-so-far + heuristic-to-goal).

src/main/java/mazealgo/model/algorithms/search/BestFirstSearch.java

openList = new PriorityQueue<>(
    Comparator.comparingDouble(s -> s.getCost() + domain.heuristic(s, goal))
);
return super.solve(domain);

That comparator is the whole algorithm. Choose h wrong and A* either explores far too much (loose) or quietly returns a suboptimal path (inadmissible). The two adapters supply different heuristics because the two domains have different neighbour topologies.

2D — Octile distance. SearchableMaze is 8-connected: straight = 10, diagonal = 15 (≈ √2 rounded for integer arithmetic).

return 10 * Math.max(dr, dc) + 5 * Math.min(dr, dc);

The shape of that formula falls out of the optimal unobstructed path: min(dr,dc) diagonal moves plus max − min straight ones. Plug in costs and simplify: 15·min + 10·(max − min) = 10·max + 5·min. Walls can only lengthen the real path, so octile distance is a tight admissible lower bound — and tightness is what makes A* expand few nodes.

Why not Manhattan in 2D? It's the textbook 4-connected heuristic, but on this 8-connected grid it overestimates: Manhattan(3,3) = 6, while the actual three-diagonal cost is 3 × 1.5 = 4.5. Inadmissible → A* silently loses its optimality guarantee. Picking the right heuristic for the connectivity isn't an optimization, it's a correctness condition.

3D — Manhattan × step-cost. Maze3D is 6-connected (no diagonals at all), so every step costs exactly STRAIGHT_COST and the cheapest path between two cells is |dd| + |dr| + |dc| straight moves. Manhattan is the tightest admissible heuristic here — exactly the reverse of the 2D case.

---

Server protocol

Two ports, one strategy each. The client speaks Object streams; the server-to-client direction is RLE-compressed for the generate endpoint. Ports 5400 / 5401 are the standalone-demo defaults — when the JavaFX app boots, it spawns both servers on OS-assigned ports instead.

GENERATE (default port 5400)
   client →  ObjectOutputStream  →  int[]{rows, columns}      →  server
   client  ←──── byte[] (RLE-compressed Maze.toByteArray) ────  server

SOLVE (default port 5401)
   client →  ObjectOutputStream  →  Maze                       →  server
   client  ←─────────── Solution ──────────────                 server
       (server consults SolutionCache before running search)

SolutionCache keys on SHA-256(Maze.toByteArray()). A corrupted cache entry is dropped silently — the next request rebuilds it.

---

Project structure

src/main/java/mazealgo/
├── MazeApp.java                            JavaFX Application entry — spawns embedded servers
├── Launcher.java                           workaround for non-modular JavaFX launch
├── model/
│   ├── MazeModel.java                      facade — talks to the embedded servers over sockets
│   ├── algorithms/
│   │   ├── mazeGenerators/                 Maze, Position, generators (Empty/Simple/My)
│   │   ├── maze3D/                         Maze3D, Position3D, generators, SearchableMaze3D
│   │   └── search/                         ISearchable, AState, BFS, DFS, BestFirstSearch, SearchableMaze, Solution
│   ├── io/                                 MyCompressorOutputStream, MyDecompressorInputStream
│   └── server/                             MyServer, IServerStrategy, Generate/SolveMazeStrategy, SolutionCache
├── view/                                   MazeDisplayer / Maze3DDisplayer canvases, controller, SoundPlayer
├── viewmodel/                              MazeViewModel + MovementDirection — JavaFX-property bridge
└── examples/                               manual runners + RunMazeServer/RunMazeClient

src/test/java/...                            42 tests across compression, byte serialization,
                                             cache, search correctness, ViewModel movement rules,
                                             the listener contract, and end-to-end server

---

Author

daney23 — Eyal Dan — Software & Information Systems Engineering Student @ BGU. Built on Windows with IntelliJ IDEA and JDK 17 / 25.