Skip to end of metadata
Go to start of metadata

Overview

This week I decided to make a logic puzzle/game. I have several ideas, but the (first?) one I decided to implement was a topological ordering of a graph -- but of course I don't call it that! The premise is that a group of people (the names are of my cousins) got together and played a game. In the game (the details of which are unknown and unimportant), each player got a score that was distinct from all of the others so that they can be ordered into first, second, third ... places. In my puzzle, a list of hints are given to help you figure out the order. You solve the puzzle by moving the names around the landscape with the mouse so that first place is on the left, last place is on the right, and the others are ordered between them.

Implementation

 Graph

The graph has nodes labeled with names, and edges that represent that the source scored higher than the destination. I used an adjacency matrix to store the Edges. I made it an Edge[][], but I could have made it a boolean[][]. I chose to do it with Edge just in case I decide to implement another puzzle that has more elaborate edges. For now, though, Edge is an empty class within Graph. It also has a Vertex[] (vertices are described in the next subsection) and a count of how many vertices have been added. The constructor requires a maximum number of vertices that will be allowed; this is used to initialize the arrays. To build up the graph, there are methods addEdge(sourceLabel, destLabel) and addVertex(label, landscape)/addVertex(label, landscape, x0, y0, dx, dy). The vertices require extra information so that they can add themselves to a random position on the landscape, with the option of specifying a region (dx=dy=0 would put it in a specific location). For my puzzle, I also needed a method arrangeTopologically(x0, y0) that would set the positions of the vertices so that they are in order on the landscape. This method used getTopologicalOrder() which returns a Queue<Vertix>. To make the Queue, I first set all of the vertices to be unmarked, then add them to the Queue when all of their predecessors are marked (I mark them when they are offered to the queue). I find the predecessors using a private method that scans the appropriate column in the adjacency matrix. I could have just as well done it by finding successors and stacking them, but I felt like starting at the beginning would be more sensible if I wanted to perhaps arrange the first n vertices to help the puzzler. Graph also has a method isOrdered() that checks to see if the vertices are arranged on the landscape from left to right in a topological order. Often graphs have more than one correct topological order, so I couldn't compare the vertices to the queue generated by my algorithm. Instead, I check every edge and test if its sources's x-coordinate is less than the destination's. If they are, then it is in topological order and the method returns true. The only remaining method in Graph is drawArrows(). This tells all of the vertices their successors so that the vertices will draw their edges on every update.

Vertices

Vertex is the Agent in this simulation, so, as mentioned above, it is up to them to draw whatever part of the Graph should be shown. When a Vertex constructor is called, it not only initializes the instance variables, but also adds the Vertex to the landscape. Apart from accessors and mark()/unmark(), the only methods with any code deal with drawing. drawLineTo(Vertex destination), called from Graph's drawArrows() or when the user connects two words, adds the destination vertex to a sort of adjacency list (it is not really an adjacency list because it may or may not have all of the adjacent vertices, and it could have vertices not connected by edges). When draw() is called, it iterates through the list, drawing arrows to each vertex. Afterward, it draws a filled oval and writes the string on top of it.

User Interface

When the program starts up, simulation's initialize() method builds a graph (using an array of vertex labels, it scrambles them into an order, then adds edges randomly so that the new order is the only order). The vertices all have empty 'adjacency lists,' so all that is drawn of the graph are vertices. In addition, I have a Text resource that accepts a String[] and draws the Strings on the Landscape. It writes a hint for every edge, and these are drawn in the upper left corner of the screen. The user can click on vertices (vertices turn blue when selected) to move them (by clicking on empty area) or draw a line from one to another (by clicking on the destination vertex). When the user thinks he has ordered them from left to right, he can click on the button "Submit Solution" to receive an appropriate message via JOptionPane. If he gets stuck, he can get help by clicking "Show Arrows," which calls graph's drawArrows(), removing any wrong arrows that the user may have added and adding any arrows not yet on the landscape. If the user still has trouble, he can click "Show Solution," and the vertices will jump into topological order. The buttons' actionListener is the LandscapeDisplay, but it sends the ActionEvents to sim.react(String command), where it is translated into a graph method.

Pictures



Sorry about the fuzzyness. The reddish text is instructions, the green is the hints (for example "Marsha scored lower than Sarah," and "Karen scored higher than Danielle").






Conclusion

I was a little unsure of having the same assignment for a third week, but I'm happy with the puzzle I created, and am glad I was able to learn to work with graphs. I feel like I have really deviated from the whole idea of agents, and that my LandscapeDisplay class bears little resemblance to the original, but I guess that doesn't really matter.

Addendum

After this project was due, I implemented a maze-generating and -solving algorithm. The maze is a graph where the vertices are each square of the path and the edges indicate that there is no wall between the two vertices.

Generating the maze

My sister shared with me an algorithm she found online for generating mazes. I unfortunately do not recall the reference. The idea is to have a list of vertices (initially only containing the start square) from which you randomly choose one. From that vertex, visit each adjacent vertex. If it has been encountered before, do not add an edge (this prevents loops). If it has not, then do add an edge, and add it to the list. This eventually visits every vertex, so every location is reachable from the start, including the finish.

Solving the maze

I included five different algorithms for solving the maze as agents in this simulation. All are Robots, which display a dialog box upon successfully reaching the end. The five Agents listed below extend Robot.

  • UserBot: The user controls this Agent with the arrow keys.
  • SmartBot: This bot finds the straight path to the end using a recursive depth-first algorithm that builds a stack of directions. It gives the other bots a head-start, and then follows its instructions to quickly reach the end.
  • DepthBot: This bot uses a similar algorithm to the SmartBot to develop its instruction queue. In order to add some variation, at each decision it randomly chooses an order in which to explore the paths. During the recursive search, it adds every node it visits to a queue. I create several of these at the beginning, and they immediately begin to pursue their paths.
  • BreadthBot: This bot differs from SmartBot and DepthBot because it calculates its next moves as it goes along. Like breadth-first search, it works by splitting itself and trying all options at the same time. To be fair, only one of its MiniBots moves each iteration. These are stored in a queue, and in each move one is polled and commanded to move itself. Whenever it reaches an intersection, it splits itself into more MiniBots; otherwise it simply moves forward. Regardless, at the end of the move it adds itself and any new bots to the queue.
  • WillyNillyBot: This bot also calculates its next move as it goes along. These are memoryless and choose a random direction in which to move each time. Occasionally they actually make it to the finish.
    Comparison of methods
    Different mazes end up with different length paths to the end, which is shown by the SmartBot's time. Since the DepthBots have some randomness, they may do as well as the SmartBot, but usually do somewhat worse. The BreadthBot has no randomness, but rarely beats many DepthBots. The WillyNillyBots are hardly worth considering.

Smart

Depth

Breadth

WillyNilly

38

207,233,573

375

3473

38

49,187,677

372

8014

40

381,393,635

381

2518

Labels