Jamis Buck - Mazes for Programmers: Code Your Own Twisty Little Passages

Copyright 2015 The Pragmatic Programmers, LLC. This book is licensed tothe individual who purchased it. We don't copy-protect itbecause that would limit your ability to use it for yourown purposes. Please don't break this trust-don't allow othersto use your copy of the book. Thanks.
- Dave & Andy.

Many of the designations used by manufacturers and sellers to distinguish their products are claimed as trademarks. Where those designations appear in this book, and The Pragmatic Programmers, LLC was aware of a trademark claim, the designations have been printed in initial capital letters or in all capitals. The Pragmatic Starter Kit, The Pragmatic Programmer, Pragmatic Programming, Pragmatic Bookshelf and the linking g device are trademarks of The Pragmatic Programmers, LLC.

Every precaution was taken in the preparation of this book. However, the publisher assumes no responsibility for errors or omissions, or for damages that may result from the use of information (including program listings) contained herein.

Our Pragmatic courses, workshops, and other products can help you and your team create better software and have more fun. For more information, as well as the latest Pragmatic titles, please visit us at http://pragprog.com.

The team that produced this book includes: Jacquelyn Carter (editor), Potomac Indexing, LLC (indexer), Liz Welch (copyeditor), Dave Thomas (typesetter), Janet Furlow (producer), and Ellie Callahan (support).

For international rights, please contact .

No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form, or by any means, electronic, mechanical, photocopying, recording, or otherwise, without the prior consent of the publisher.
Printed in the United States of America.
ISBN-13: 978-1-68050-055-4

Book version: P1.0July 2015

A lot more goes into a book than I had imaginedand believe me, I had imagined a lot! None of this would have been possible without the faith that Dave Thomas and Andy Hunt had in me. A huge thanks goes to them for taking a risk on a book about mazes, of all things!

A huge debt is also owed to Jacquelyn Carter, my tireless and (seemingly!) endlessly patient editor. I cant imagine how she didnt despair at seeing my early chapter drafts. Thanks for showing me the way, Jackie.

Thanks, too, to the wonderful army of technical reviewers who pored over my code examples and prose explanations and made numerous suggestions. It is a better book because of your help: Bruce Williams, Jeff Hardy, Nick Quaranto, Trevor Turk, Amanda Wixted, Walter Pullen, Sam Stephenson, Chris Moyer, and Nick Capito.

Also, thanks to the readers of my blog, years ago, who read my series of articles about maze algorithms and gave me such wonderful encouragement. It is because of your enthusiasm that I ever even dared to consider this book.

Lastlyand most profoundlythanks go to my wife Tessa and my children, for the sacrifices theyve made during the last eight months. Books dont write themselves (sadly!) and this one required me to be off by myself, writing, for a few hours each day. The faith of my family, and their constant support and encouragement, carried me through.

Thank you, thank you, thank you!

Mazes are everywhere. From psychology experiments where mice scamper in search of cheese, to robotics demonstrations, to movies (Labyrinth, anyone?) and video games (Pac-Man? The Legend of Zelda? Doom?), to books and books of puzzles to be traced by finger or pencil, youve almost certainly encountered them at some point in your life.

What youre reading now is not a collection of mazes for you to solve. No, this is something much more exciting. This is a collection of ideas to inspire you.

Youre about to learn how to generate your own mazes. Random mazes, unique, each one different than the one before. Its a voyage of discovery where you never know quite what youll find when you crest the next hill.

Youll take your existing knowledge of software engineering and apply it to generating these puzzles in a variety of shapes and sizes. Youll make mazes out of squares, circles, triangles, and hexagons. Youll put them on cylinders and cubes, spheres and even Mbius strips. Youll stretch them into other dimensions, squeeze them into arbitrary outlines, weave them, braid them, print them, and fold them.

Youll discover yourself brimming with ideas, perhaps the most effective cure there is for programmers block, burnout, and gray days.

The chapters here are grouped into four parts, organized roughly around a simple progression of concepts. Youll learn about a dozen different ways to generate mazes, as well as a number of fascinating things to do with them.

Part One will introduce you to some basic techniques and will walk through the beginnings of a grid implementation that will be used throughout the book. Youll learn about Dijkstras algorithm and see how it can be used not only to find solutions to the mazes youll generate, but also to gain insight into the structures and patterns hiding within those mazes. By the end of Chapter 5 youll have learned a total of six different ways to generate these twisty little passages.