Introduction
This is a project I started working on during the holiday break. I just finished my third Java class and I wanted to make something using some of the concepts I’d learned about (namely graphs and graph algorithms). I chose JavaFX for this project, because I wanted to go with something standard, since this is intended to be a very simple game that does not require a more advanced game library.
Description
The mazes are generated by creating a grid of anchor points for the walls and using random numbers to set walls between an anchor point and it’s adjacent point. First the horizontal walls are set, then the vertical walls in the same manner. The amount of walls is based on a load factor percentage (0% is no walls and 100% is completely grid-locked). The entry and exit are randomly selected along the left and right walls respectively. If the entry is in the top half, the exit will be in the bottom half and vice-versa. A new maze can be generated by clicking the “New Maze” button.
Future Plans
I still have quite a bit of work to do before I can say this project is in a finished state. I left off implementing the graph system, which will allow for graph algorithms to be used. One of the first things that I’ll use the graph for is to ensure that it is fully connected, so that a solution is guaranteed and so that there are no closed off areas. I also plan on using Dijkstra’s algorithm to implement a “Solution” button that will show the shortest solution path if clicked. At the moment I’m using a free movement system based on adding velocity values to the “Player” object. The collision detection is pretty rough as well. I plan on scrapping this system altogether and going with a grid-based movement system.
School is starting for me again tomorrow, so I’m not going to have much time to work on this. It might be a while until the next update.
February 3, 2017
Details
Well, I took a day off from school to work more on this project. The focus of this update was on the graph system. The graph is made up of verticies on each traversable location and must be fully connected to guarantee a solution as well as eliminate inaccessible areas. If you look at the previous update you will notice a lot of these unconnected parts of the maze which oftentimes results in a maze with no solution.
My resolution to this problem involved three methods within the MazeGraph class: connectGraph(), getSubGraphs(), and traverseGraph(). After initializing the graph by placing verticies in all open spots (after walls have been set) A call is made to connectGraph(). connectGraph() makes a call to getSubGraphs() which will return a list of MazeGraphs which are the fully-connected subgraphs. This list is built by maintaining a set of processed verticies local to getSubGraphs(), iterating over the verticies, and making calls to the recursive traverseGraph() method for each unprocessed vertex. Each time we return from traverseGraph(), we add the fully built subgraph into the list of subgraphs to be returned. When we return with the full list of subgraphs (back in connectGraph()) we enter a conditional loop that terminates when subGraphs.size() == 1 which inicates that there is only one fully-connected graph. Within this loop we have a loop that iterates over the subGraphs. For each subgraph, it iterates over the verticies until it finds one that is adjacent to a wall. Once a qualifying vertex is encountered, it makes a call to a static method in the main Game class called SeekNBreach(). This method looks around for an adjacent wall (so long as it isn’t a border wall) and makes a call to breachWall(). breachWall() removes the wall and creates a new open spot. When we return to the loop, we must add a new vertex into the open spot and connect it to the rest of the graph. First, we must calculate the required arguments to provide addVert(). We need the x and y screen coordinates, the row and column of the new vertex, and a PixelReader to use for determining adjacencies. After these calculations are made and it’s been added, we have to tell the new neighboring verticies about the new vertex we’ve just added. This is necessary to make the connection complete. After we’ve done this procedure (breach one wall in each subgraph) we call getSubGraphs again and return to the top of the conditional loop to see if the number of subgraphs is 1 yet. Typically this only takes a handful of iterations to achieve.
Future Plans
The lineup of issues that I intend to work on next are as follows: Bind player movement system to the graph, Create a wall manager class to eliminate static methods and fields, add “find solution” feature to highlight shortest solution path using Dijkstra’s algorithm.
The current movement system is unbound to the play area and works by adding velocity values to the Player object. Collision detection is performed by iterating over the set of walls and testing whether the player is inside of any of them during each frame. This approach works for some games, but certainly not this one. I plan on moving to a system that locks the player position to the grid. The only valid moves will be to adjacent verticies. This will provide a much smoother and more efficient movement system as well as eliminate the need for collision detection.
Currently the main Game class has a lot of static methods and fields. Most of these are related to the need for MazeGraph to have access to the set of walls. When we’re in connectGraph() and we need to make the call to seekNBreach, that is a static method and since the method is static, the walls need to be static as well. Another issue is when we add a new vertex from connectGraph, we need to get a PixelReader which needs to use the Canvas. This creates the need for another static call and for the canvas to be a static field. In adherence with best practices for object-oriented design, static methods and fields should be used sparingly.
May 1, 2017
Details
In this update I’ve added some outlines for the walls, a shortest path solver using breadth-first search, a couple of sound effects, and have made it available for download via Github.
The wall outlines are determined by the outlineWalls method in the main Game class. It is called after returning from initMazeGraph and the graph is fully in place. It works by iterating over all vertex positions in the graph and determining what the surrounding walls are for each vertex. Each wall now holds a list of Lines for rendering its outline. When a surrounding wall is detected next to a vertex, it calculates what side of the vertex the wall is on and adds a line to that wall which is directly adjacent to the vertex. Now, when the wall is rendered all of its outline edges are rendered as well.
The shortest path through the maze is computed by a series of methods of the MazeGraph class called from the main Game class at the end of initMazeGraph. The chain of methods begins with a call to solveMaze. The MazeGraph class now has a List of Vertex called solutionPath that stores the vertices along the path. solveMaze calls getSolutionPath which calls breadthFirstSearch. Each Vertex has two new fields,(boolean) bfsIdentified and (Vertex) bfsParent, that work with the breadthFirstSearch algorithm. Upon completion of the BFS, every Vertex should be identified and contain a parent Vertex, except for the start Vertex (the maze entrance). After returning from breadthFirstSearch, we are back in getSolutionPath. Now we need to create our list of Vertex for the solutionPath. This is done by traversing back up the graph from the Exit vertex by adding bfsParent vertices to the solutionPath List. The loop ends when we get to a vertex with a column of -1 which must be the Start vertex. To render the solution path we simply iterate over the solutionPath list of vertices and render a line from one vertex position to the next. This is controlled by a boolean field called renderSolution.
I’ve also started using the CSS functionality of JavaFX to make a nice gradient background and to make the buttons a different color.
I’ve finally started using git for version control and github to store this project online.
