I am currently prototyping a new game that works a lot like Pac Man except you’re a farmer planting and harvesting flowers.
The finer details of the game are still to be worked out. The first prototype had an open grid of squares and the player was able to move freely in any direction.
An open grid did not work well with Pac Man style controls.
This approach did not work due to how the movement system works. The player’s tractor moves continuously in a straight line but is only allowed to turn when it is in the centre of a tile. Turning felt unresponsive if the player turned between tiles.
As a solution I decided to try mazes with long corridors. I wanted a maze that would start small but grow into a large maze as the player progressed.
The maze starts with 1 square and grows as the player scores points.
After dusting of the old Data Structures and Algorithms textbooks I thought that a good approach would be to use a graph data structure. I put together a simple implementation using C# that I’ll share on GitHub in the future.
One constraint on the grid is that there should always be an Euler Cycle available. This means that it should be able to visit every path in the maze without repeats. The player’s score will scale with big combos of flowers so it’d be nice to always have plenty of scope for long chains without repeats.
The easiest way to accomplish this was to make sure that each node in the grid has 2 or 4 paths as continuous graphs where all nodes have an even number of vertices will always have an Euler cycle.
The results of applying 1 extension to the grid.
The algorithm for extending the maze is as follows:
- Select 2 random degree two nodes. (I.e. Nodes with 2 links.)
- Add an extra link to each of these nodes so there are 2 nodes in the graph with 1 link.
- While there remains an odd node in the graph: Link it to another odd node.
All being well this method can be used to extend the maze while ensuring there’s an Euler cycle.
A large maze created by repeatedly extending the maze with this algorithm.
When the method works it can generate large mazes with Euler cycles very quickly however it has 2 major disadvantages:
- It is complex and error prone: On the plus side I now know how to recover Unity from an infinite loop. On the negative side I put Unity into many infinite loops and chased many frustrating bugs trying to get the thing to work. It would be difficult to further tune the algorithm for varied gameplay.
- The mazes aren’t that fun: There’s an infinite variety of mazes but they’re all quite ‘samey’. Playing on random mazes doesn’t seem like it will be terribly engaging.
So while the random maze prototype did not completely pan out it wasn’t a total waste of time. I have a decent graph data structure that can be used to represent levels in future version and some path-finding code that can be used for AI.
Memory match card game tutorial in progress.
In other news I have a Scratch tutorial in progress detailing how a memory match card game could work.
The Scratch code is nearly complete and I’ll be starting the write-up soon.