Monday, March 18, 2013

A Maze Generator

I did it because it was a test to win a job *. I wrote it in 2 days (the time allowed), without pain.

The main features are:
  • choice of the size : both width and height are configurable

  • a pseudo random number generator (PRNG) allows you to deterministically generate a wide set of mazes (one seed for one maze). An easy solution for this is to use a hash algorithm (like md5) ; but I chose to code one from scratch. The solution I used was the combination of a middle square method and a big array (~#500) of random pre-drawed values. By this way I had a short simple algorithm with a decent period.

  • 6 types of pattern. Each "simulating" a kind of environment. At first you will recognize the very famous classic labyrinth approach. Then the "noisy" is just the way I used to intensely test my PRNG. The "lines" is in my mind a kind of french city map generator, The "rectangular" could be seen as generating small village as we can see in old RPG games. The "bubbles" is a not very convincing way to build a lunar ground. And finally "manhattan", which I think doesn't need deep explanations. Note that if "classical" works well at any size, you will have more convincing results with other patterns if you set width and height at minimum 60x60.

  • if you look closely to the map, you will see 2 colored squares : the green acting as a starting point and the blue as an end point. So you can finally generate a path between the two squares. The search is implemented with the famous A* algorithm. The path generated this way is not always the shortest, but is very efficient.

Now let's play:

In spite of the short time The project has a safe structure (MVC). Maybe I will reuse all or some parts of it to explore some new directions for a game.

*  I must admit I infinitely prefer this kind of test, which let you be creative and demonstrate that you code professionnally, compared to some fuc**** ugly listing of artificial technical questions that nobody cares in real life.

No comments:

Post a Comment