Unknown's avatar

About wjduquette

Author, software engineer, and Lay Dominican.

Recursive Backtracking

Here’s yet another maze, produced by a method called recursive backtracking. Unlike the previous algorithm, which is something I came up with myself, this is a well-known algorithm with rather delightful properties, as you can see for yourself.

Mta

The algorithm is straightforward:

  • Create a new, blank maze in which all cells are free. (A free cell is connected to no other cell). You can think of the free cells as square rooms with a closed door in each of the four walls.
  • Initialize an empty stack of cells.
  • Let C be a cell chosen randomly.
  • Repeat:
    • If there is at least one free cell next to C,
      • Let D be a free cell next to C, chosen randomly.
      • Open a door from C to to D.
      • Push C onto the stack.
      • Let C = D.
    • Otherwise,
      • Pop an old C from the top of the stack.
  • Until the stack is empty.

The maze shown above uses a slight variant called “inertia”, which makes it a little more likely that the next free cell chosen will be in the same direction as the previous. This makes the straight corridors just a little longer.

Like the previous algorithm, it produces a “dendritic” maze: one in which each cell is connected to every other cell by exactly one path. That’s cool if you’re printing the maze on a place mat, but a little boring if you’re using the maze in a game, so the next step is to take a maze like this and modify it in various ways.

A Bigger Maze

For Mark Lambert, here’s a bigger maze with an entrance and an exit.

Bigmaze

Kardde was curious how it was produced.

First, a maze is represented as a rectangular array of cells. Each cells is square, and has a wall on each side, and each wall has a door. When the algorithm begins, all of the doors are closed. The algorithm proceeds by judiciously opening doors into neighboring cells until all of the cells are reachable. A cell with all of its doors still closed is said to be “free”. Here’s the algorithm:

  • First, create a maze in which all of the doors are closed.
  • Pick a cell randomly, and add it to the list of growth candidates. (It will be the only entry.)
  • While there is at least one cell in the list of growth candidates,
    • Take a cell, C, from the list of candidates.
    • Find any free cells adjacent to C (north, south, east, or west), and pick one randomly. Call it F. If there are none, continue with the next candidate cell.
    • Let D be the direction from C to F.
    • Randomly pick a number N, from 1 to 4.
    • Beginning at cell C, drive in direction D, opening doors into free cells, until you’ve reached the Nth room, or the edge of the map, or a cell that’s not free.
    • If there are still free cells left adjacent to C, add it to the list of candidates.
    • Add the last cell to the list of candidates.
  • When no candidates remain, all cells are connected, and the maze is complete.

There are a number of things you can change about this. In particular, you can change how you pick the next candidate: the first entry, the second entry, a random entry, and so forth. Different choices will result in different looking mazes. Second, you can vary the number of steps to drive while opening cells. In the maze shown above, you drive up to four cells, random chosen from 1 to 4. Again, different numbers of cells make a difference. For example, suppose that instead of choosing a number from 1 to 4, I simply always choose 4:

Bigmaze2

As you’ll note, it looks quite a bit different.

Amazing

Here is the first real maze produced by my new Java code. It’s not a great maze (there are better algorithms), but I learned a lot from doing it.

Mta

A Cup of Joe

I’m a long time Tcl programmer; I can make Tcl sit up and beg. It’s been brought home to me, though, that the demand for making Tcl sit up and beg is low where I work. If funding were cut for my current project and I had to jump to another, my Tcl experience might not count for much. (One doesn’t always have the luxury of starting a new project and picking the infrastructure one wants.) Java, on the other hand, is widely used; and though I’ve done some work in Java it’s been around eight years. A Lot Can Happen in Eight Years, and in the case of Java it has. When I last used Java, it was Java 1.4 (or maybe even Java 1.3; I seem to recall that 1.4 was brand new). Java 6 is fairly standard today, and Java 7 is picking up steam.

I didn’t like Java 1.4 much, but Java 5 (i.e., Java 1.5; they dropped the “1.” around then) added a bunch of nifty new features that make the language much nicer to work with:

  • Parameterized Types (i.e., Generics)
  • A colllections library based on Generics
  • Annotations
  • Enum Classes
  • Auto-boxing and unboxing

(And no, I’m not going to describe all of those.)

More than that, I did all of my work at the command line, using the Emacs editor; all the cool kids these days seem to be using this Integrated Development Environment called Eclipse. Seems that if I want to fit in on an existing project, I’d better learn that too. So that’s my new project for awhile: rediscovering Java and learning how to use Eclipse.

I don’t know how much I’ll blog about it, but I thought I’d show the fruits of my first morning’s work: an image rendered by a short Java program.

Checker

Some years ago I wrote a little old-school dungeon-crawling game called Ramble, and I put together some algorithms for creating random dungeon mazes. I’m thinking that I’ll try re-implementing some of those in Java, as a first project; and save the finished mazes as PNG images. Think of the above as the proof-of-concept: how to draw an image and save it to disk.

My Sisters the Saints

My Sisters the Saints: A Spiritual Memoir Recently I received a review copy of My Sisters the Saints, a “spiritual memoir” by Colleen Carroll Campbell, and I confess I stayed up late to finish it.

In this book Campbell shares her life with us, both the good and the bad, and along the way she tells about particular saints who helped her get through. The names are familiar: St. Teresa of Avila; St. Therese of Lisieux; St. Faustina, St. Edith Stein, Mother Teresa, and St. Mary, Mother of God. She tells us of their lives and writings, and just what there was about them that spoke to her and helped her to cope with the trials of her life. I was familiar with most of the saints in question, but nevertheless I learned a thing or two about them.

The compelling part of the book, though, is Campbell’s own story, and her efforts to get over herself, and to learn to serve and love God. Running through much of the book is the story of her father’s struggles with Alzheimer’s Disease. These passages resonated especially strongly with me, because my own father was afflicted with Alzheimer’s in his last years.

My father was a brilliant man, and a born problem-solver, and it was horrifying and distressing to watch his capabilities fade. More than that, nothing made Dad angrier than a problem he could nothing about (politics, consequently, always made him furious), and as time went on there were more and more of these. Once he got terribly angry with my wife Jane, because “People aren’t keeping me informed about what’s going on!” Jane, with perfect grace, said, “Yes, Dad, you’re right.” And he was—not for lack of trying on our part, but he was right.

Every since then, I’ve determined that if I get Alzheimer’s in my turn, as seems likely (all of his siblings who lived long enough have shown the signs), that I want to be jolly rather than grumpy. And to be jolly then, I figure I need to stop being grumpy now. It’s a hard thing to do.

But Campbell’s father has shown me a better way. Campbell came to befriend the saints while learning to cope with her father’s illness; but her father had spent the better part of his life learning to know God and his saints. And in the year or so after the onset of Alzheimer’s, when he could still talk and make some amount of sense, everyone who met him was struck by his joy and his faith. Here was a man who was offering up his trials to God, and spreading God’s love and peace to his family and to the others in the nursing home where he lived.

Eventually Campbell’s father deteriorated to the point where he couldn’t even talk anymore, far past where my father was when my father died; and he suffered horribly. But he held on to the joy as long as he could.

So that’s my new goal. I don’t just want to be jolly when I’m old and infirm; I want to be joyful, and a blessing to those around me. May it be so.

Avernum HD

I’ve not posted much about books this week, because I’ve been playing Avernum: Escape from the Pit on my iPad.

As it happens, I’m a sucker for RPGs. I’ve got probably a dozen of them on my iPad, of all flavors; and none of them of really grabbed me the way Avernum has. It’s got a great big world you can roam freely (well, unless you get killed); dozens of quests of various kinds; lots of weapons and spells and magic devices to discover; interesting monsters; it’s just plain cool.

The premise is simple: having offended the emperor, you’ve been thrown down into the underground world of Avernum. There is no escape; once there, you simply have to learn to live there with the other exiles, scratching out a living. Human beings have a hardscrabble existence in Avernum, fighting for their lives against the Nephilim, the Nepharim, the Ghouls, the Ogres, the Giants, and the Slithzerikai. So you and your three companions (two fighters, a priest, and a mage, naturally) go out adventuring and helping folks out.

Your view of the world is a topdown three-dimensional view, so it looks purty. Difficulty can be set anywhere from easy to hard. Combat is turn-based: during combat, when it’s a character’s turn you move them as desired, and then combat continues. It’s surprisingly sophisticated; to survive, you have to take advantage of the terrain, or at least take it into account.

I’ve got too many hours into it already, and I suspect it’s going to last me a couple of more weeks. It’s well-worth your time, if you like that sort of thing.

The game is also available on Windows and Mac

Lillian Gilbreth and the Modern Kitchen

Via Instapundit, here’s an article about Lillian Gilbreth and the invention of the modern kitchen. If you’ve read Cheaper by the Dozen, the Gilbreth name will be familiar to you. (If you haven’t, go do so now.) Gilbreth was the wife of Frank Gilbreth; she and her husband were pioneers in the area of motion study and eliminating needless motions from different kinds of industrial work. After his death, she began to revise the kitchen along the same lines; the modern kitchen “work triangle” comes directly from her work.

According to the lore of Jane’s family, they’ve got a mild Gilbreth connection. In Cheaper by the Dozen, there’s a scene where Frank is left to manage the children (they had twelve) while Lillian is away for the day. When she returns, he says something like, “They were no trouble, except for that red-haired kid. Him I had to speak to several times.” And Lillian said, “But Frank, he’s not ours. He lives next door.” Jane’s Uncle Dudley always claimed to be the red-haired kid.

Soul of Fire

Soul of Fire (Magical British Empire, #2) Soul of Fire is the second novel in Sarah Hoyt’s “Magical British Empire” trilogy, and it’s rather better than Heart of Light, its predecessor—though not devoid of problems.

I am most unusually going to indulge in spoilers in this review; be warned.

It seems that there are two magic rubies, the Heart of Light and the Soul of Fire. The latter was stolen in the days of Charlemagne, and he used it to gather up all of the magic in Europe to himself and his descendants, thus establishing what one might call the magical right of kings. By the Victorian era, of course, the blood of Charlemagne has diffused throughout Europe; magical ability, once the mark of nobility, is now popping up in the oddest places.

Once used, the Soul of Fire was apparently used up, and was lost. And now everybody and his brother are trying to find the Heart of Light, in order to use it as Charlemagne used the Soul of Fire. This search drove the action in the previous book, Heart of Light, at the end of which we discover that the purpose of the two gems is to stabilize the world, and if the Heart of Light is found and used as everybody intends, the world as we know it will come to an end. (Bom-bom-BOM, as my second son would say.) Therefore, Soul of Fire begins with Peter Farewell, one of the principles of the previous book, searching for the Soul of Fire in order to rescue it from the bad guys and save the world. As the book begins he has traced it to India; and he immediately has a sort of cute-meet with Sofie, a young Englishwoman, which is to say he saves her from falling to her death from a balcony as she’s fleeing her home in order to avoid an unwelcome marriage to an ugly British raja. Interesting how he does it; for our Peter is a were-dragon, and he saves her by changing shape and catching her. This was extremely dangerous for him, because were-creatures of all sorts are subject to immediate execution by the English crown, and he had previously managed to keep his affliction secret.

Peter’s relationship with “the dragon” is interesting. He has trouble controlling the change, especially in confined, crowded spaces; and he has trouble controlling “the dragon”; and of course this is a romance, and of course, being an English gentleman (his father’s an earl) Peter has scruples about marrying any one, even though narrative causality dictates that he’s going to marry the young lady he rescued. She, of course, is the latest descendant of the family to whom Charlemagne gave the Soul of Fire for safe-keeping, a charge the family has been faithful to through the centuries.

Will fierce beast win fair lady? Will the world be saved? These are the ostensible subjects of the tale…but things are not as they seem. The real subject of the book seems to be alienation: and specifically the alienation of the were-folk of Europe, who have been raised to loathe themselves. We see this in Peter, who regards his dragon-self as The Other, the Not To Be Trusted. And as the tale proceeds, and he is forced to rely more on “the dragon” in aid of his young lady, he grows less conflicted…and discovers that perhaps “the dragon” can be trusted after all, if only he embraces it and accepts it as part of himself.

Two other plot elements cast light on his personal growth. First, there are the were-folk of India. It develops that large portions of the Indian population, especially among the higher castes, are were-folk. We meet were-monkeys, were-elephants, and were-tigers. (The raja who was seeking to marry Sofie is in fact the King of the Tigers.) They have no problems with being were-folk; and the normal humans around them have no trouble with it either, though they walk carefully when were-tigers are in view. So coexistence, were-folk with normal humans, and were-folk with themselves, are both possible.

May I say I really like the prevalence of were-folk in India; it makes Hoyt’s India much more interesting than most.

The second plot element is a young British soldier, who has also been sent to India to find the Soul of Fire. He’s acquainted with young Sofie (indeed, his superiors tried to persuade him to marry her), but though he likes her, he’s not attracted to her. And why not? Because, overwhelmed by Peter Farewell’s dragonly glamour, he discovers (to his shock and dismay) that he’s attracted to men. His subsequent emotional turmoil and alienation is exactly parallel with Peter Farewell’s, and it takes him the rest of the book to find peace, living in the wilds of India with a sepoy who happens to be a were-elephant and who fell in love with him at first sight. The sepoy suffers alienation as well; his family rejects him, not because he loves men but because he loves an Englishman, who is outside the caste system.

Now, all of this is somewhat interesting. Alienation and marginalization of The Other are common themes in fantasy and science fiction, and I’ve sometimes wondered when reading books like Kathryn Kurtz’ Chronicles of the Deryni whether there was a homosexual subtext in the author’s mind. This is the first book I’ve read that makes the link quite so explicit. Now, I don’t object to Hoyt dealing with themes like this explicitly. It’s certainly true that having a false self-image is harmful, and that accepting yourself as you presently are is the beginning of maturity. (Though not the end of it; at any time, there are aspects of each of us that need to get cleaned up.) And it’s certainly been true that to be gay in America has been fraught with alienation.

No, what I object to is the hamfisted way in which Hoyt pulls in the relationship between the two young soldiers. Suddenly, in the dark of the jungle, the Englishman looks in the Hindu’s eyes, and smells his breath, and suddenly, pretty much out of a clear blue sky, passion erupts and the curtain descends (for which I am grateful; and I will note with equal gratitude that all of the sex in the book is either offstage or glossed over). It was clumsy, and it seemed out of place, and from my point of view, it didn’t aid the story; rather, it shouted, “Here’s the point, people! Here’s the point! Pay attention!” And this is almost never a good thing in a work of fiction, no matter who’s writing it or what the point is. Sigh.

Darkship Thieves

DarkShip Thieves After I reviewed Sarah Hoyt’s Heart of Light, a friend of mine sent me a copy of Hoyt’s first science fiction novel, Darkship Thieves, just to show me that she really does write good stuff. He was right.

Darkship Thieves is a consciously Heinleinesque tale set in a future Solar System. Our heroine, Athena Hera Sinistra, daughter of one of the oligarchs who run the Earth, wakes from sleep in her stateroom on her father’s ship in orbit around Earth to discover a man about to give her an injection. Athena is a piece of work: spoiled, temperamental, the terror of boarding schools all over the world, and extremely accustomed to getting her own way; she’s also strong, fast, skilled in hand-to-hand combat (for reasons that make sense, in context) and lickety-split she’s made it to one of the ship’s escape pods and used to, well, escape.

The pod is picked up by one of the so-called “darkship thieves”, a clandestine ship that harvests the power pods that grow in Earth orbit and takes them to a colony asteroid that’s not supposed to exist, and there begins a tale of mystery, villainy, derring do, and true love. Athena, as I said, is a piece of work…but an insistence on getting your own way is not always a bad thing, assuming you can adjust what you want a bit.

This is the kind of story where a good bit of the fun lies in learning (with the main characters) just how the world got to be the way it is, and in which the accepted public explanation and the truth are rather different. It’s good fun, and I’m looking forward to the sequel.

(Oh, and for those who know their Heinlein: this is the Heinlein of The Moon is a Harsh Mistress rather than the Heinlein of either Have Space Suit, Will Travel or Stranger in a Strange Land. Which is to say that Hoyt pushes against current social mores a bit, but doesn’t take it to absurdity. Also, I think Hoyt might be better at characterization.)

Out of Exile!

After eight (8) months, we are back in our kitchen! There are a few little things still to be done, but we have actually eaten some homecooked meals in the new kitchen this week. Woohoo!

No pictures, yet, as there are cardboard boxes everywhere still.