More detail on the 15 puzzle solver

The 15 puzzle program does not do any searching as it solves a puzzle. It uses an explicitly described method. (See the original post for details of this method) However, in applying this method, the program repeatedly needs to find a way to move a numbered tile from one position to another, without disturbing the positions of certain other "locked" tiles.

To do this, the program makes use of a simple maze pathfinding algorithm.

It uses the pathfinder to plot the path a tile must take to reach its target position without disturbing "locked" tiles. Once the path is plotted, the program typically tries to move the tile along the path.

However, since the tile can only move into an empty space, the empty space must be moved to the next spot the tile needs to move into (to progress it along its path). So, the program uses the pathfinding algorithm to plot a course for the empty space as well (again, without disturbing "locked" tiles, which would now typically include the tile trying to reach its destination).

Here is a description of the simple maze pathfinding algorithm:

1) Mark the destination on the maze with the number zero.
2) Every iteration of the following represents a single step in the maze, so the number of iterations doesn't need to be any higher than the maximum number of steps you are willing to take. (Theoretical maximum is width * length of the maze) For every iteration:

• Make a pass along every cell in the maze.
• If the cell is not a "wall" cell, check its immediate 4 neighbours.
• If one of these neighbour cells is marked with the number of the previous step, mark the current cell with the number of the current step.

3) Finished.

After running this algorithm, you end up with a maze (or whatever you were writing on) marked with the number of steps it will take to reach the goal from any cell in the maze.
So to plot a course from a particular point, you simply find the neighbouring cell with fewer steps remaining than the current one, and you keep doing this until you inevitably reach the goal cell.

In the 15 puzzle solver, this number is displayed in small print at the top right corner of each cell.

Cells shaded yellow are cells that have been marked as "walls".

I may release another version which displays more details about the steps it is taking, as well as displaying the path finding being done for the empty space (which was initially omitted for clarity).

Lights Out puzzle experiment

Downloads:

• Download Lights_080205_1040.zip here
  (The password of the zip file is createuniverses)

I wrote this program to see the effect of applying a simple rule for solving the light toggling puzzle.

The idea is, because the toggle pattern is a cross shape, you can toggle one cell in a row at a time by pressing the one below it. Working your way down, you can clear each row separately this way. (According to the rules of the light puzzle, "pressing" a cell means toggling the cells that make up the cross centered on that cell individually.)

Naturally, the interesting thing happens when you reach the bottom. Sometimes it will work itself out, sometimes it won't. When it doesn't, it can produce interesting patterns as you keep applying this algorithm. When the puzzle isn't solved, this program reapplies this technique, but in the other direction.

Press 'r' to generate a new puzzle. (It regenerates a new puzzle by "pressing" 1000 cells at random)
Press 'p' to pause the algorithm.
Press 'c' to continue the algorithm. Pressing it again will modify the speed at which the algorithm runs - whole row per frame, or single cell per frame.

Click to press the indicated cell (will toggle a cross shape at that position). You can do this during a solve as well. You can set up your own puzzle this way, and see how the algorithm handles it.

Screenshots:

Simple tennis program

Downloads:

• Download Tennis_080205_1040.zip here
  (The password of the zip file is createuniverses)

This program is the beginnings of a tennis simulation featuring some basic tennis mechanics.

This program demonstrates a means of making the ball land anywhere with an arbitrary apex height, and a means of determining which part of the trajectory can be reached by the player.
In this way, the program demonstrates a framework for staging all sorts of different scenarios and tennis playing strategies in the tennis universe.

Description of AI behaviour:

• AI runs directly toward the ball to intercept it
• AI runs to the center of its half of the court after hitting the ball and before its opponent does
• AI decides on where it would like the ball to land by choosing a random spot in opponent's half of the court
• AI may control the height of the apex of the ball's parabolic trajectory

The parabola the AI desires is precomputed, and an appropriate initial velocity vector is computed for the ball so that the ball follows the desired trajectory under the influence of a physics model which only includes gravity.

The physics ball is rendered as a white sphere, the "scripted" constant x-velocity ball is rendered as a yellow sphere.
I render both to ensure that they match up precisely.

The precomputed parabola is rendered as well. The green portion is the portion that can be reached by the player, the red portion is the portion that cannot be intercepted in time.

In this version, I've made the camera follow the player, so there is no interactivity.

Esc will close the program.

Screenshots:

Quotes by Q

Q is a godlike character who appears in Star Trek episodes to antagonise and challenge the various other human characters. He often has very juicy things to say about life and exploration, and so I'm collecting a few of his quotes here.

Q: We wanted to see if you had the ability to expand your mind and your horizons, and for one brief moment, you did.
Captain Jean-Luc Picard: When I realized the paradox.
Q: For that one fraction of a second, you were open to options you'd never considered. That's the exploration that awaits you, not mapping stars or studying nebulae, but charting the unknown possibilities of existence.
-- Star Trek The Next Generation, "All Good Things"

Q: If you can't take a little bloody nose, maybe you had better go back home and crawl under your bed. It's not safe out here! It's wondrous, with treasures to satiate desires both subtle and gross. But it's not for the timid.
-- Star Trek The Next Generation, "Q Who"


Captain Jean-Luc Picard: Having a good laugh now, Q? Does it amuse you to think of me living out the rest of my life as a dreary man in a tedious job?
Q: I gave you something most mortals never experience: a second chance at life. And now all you can do is complain?
Captain Jean-Luc Picard: I can't live out my days as that person. That man is bereft of passion... and imagination! That is not who *I* am!
Q: Au contraire, he is the person you wanted to be: one who was less arrogant and undisciplined in his youth, one who is less like me? The Jean-Luc Picard you wanted to be, the one who did NOT fight the Nausicaans, had quite a different career from the one you remember. That Picard never had a brush with death, never came face to face with his own mortality, never realized how fragile life is or how important each moment must be, so his life never came into focus. He drifted through much of his career, with no plan or agenda, going from one assignment to the next, never seizing the opportunities that presented themselves. He never led the away team on Milika III to save the ambassador, or took charge of the Stargazer's bridge when its captain was killed. And no one ever offered him a command. He learned to play it safe. And he never, ever got noticed by anyone.
Captain Jean-Luc Picard: You're right, Q. You gave me the chance to change, and I took the opportunity. But I admit now, it was a mistake.
Q: Are you asking me for something, Jean-Luc?
Captain Jean-Luc Picard: Give me a chance to put things back the way they were before.
Q: Before, you died in sickbay. Is that what you want?
Captain Jean-Luc Picard: I would rather die as the man I was, than live the life I just saw.

-- Star Trek The Next Generation, "Tapestry"

(For an excellent alternative script, read this)

I read this article in the newspaper today: Robobugs to swarm over enemy lines

The article is not all that interesting or well researched in itself (the idea of swarms of simple agents is an old one in computer simulation, the idea of using it in war is both offensive and infantile). What causes me to mention it in my blog is the following strangely surreal and unsettling line:

"While some of the robobugs still only exist on the drawing board, the company said plans for the spider-like bug were "well advanced" and they had hopes they may hit the battlefields as early as this year."

Anything strike you as just a little smelly in this? In particular, read this bit:

"...may hit the battlefields as early as this year"

Its as though battlefields are supposed to be as mundane and commonplace as supermarket store shelves.

"the new ipod/other wanky worthless widget may hit the supermarket shelves as early as this year..."

Humans are weird and hideous sometimes.

On making editors

Making an editor or deciding how an editor would be made for the simulator you're making is a useful thing to do to clarify what it is that is important in your universe. Understanding more about the process of making an editor and the role of the editor is vitally important in any development of artificial intelligence, physics or other simulations in other domains.

Edits in the editor ideally should result in a directly observable and understandable effect in the simulation. This means that the visualization should be designed to reflect the effect of the edit, or alternately, the only edits allowed should be the ones meaningful in the context of what is being visualized.

Suppose I'm looking at making an editor for the AI behavior of the soccer players in BallGame.

Something I may wish to edit in this world is the decision logic of the AI team when assigning roles.

If I don't make any changes to the way the game is presented, it will not be very apparent at all what the effect of my changes are. Conversely, where there are changes in the behavior of the players, it will be unclear how and why the edit I just made is responsible.

One visualization that may illuminate the effects of the edit may be to visualize how frequently some decision paths are taken versus others. The decision tree can be rendered as a graph, and proportionally bolder connections can be drawn for the paths that are taken more frequently. Another is to contrive simple situations to exhibit the new designed behavior, and see if it works as intended.

The goal of the visualization is to reveal causal relationships among events that have emerged as a result of the edit. The author of the edit already knows the causal relationships the author has explicitly designed, however the author won't know what other causal relationships have also hitched a ride as the side effects of the edit.

If we see that an edit causes oscillating behavior, we want to see explicitly what the causal chain was, so we can take some steps to repairing it. If we see that an edit causes interesting maneuvers to happen, we want to see explicitly what the causal chain was, so that we can learn something new about the emergent behavior of the soccer players.

Particularly, we want to see that the causal chain we found wouldn't have been possible or logically valid before the edit. In this way, we can make new discoveries.

Set up the same world without the edit, reveal that the causal chain cannot occur as before.

Sometimes, we want to study the behavior of a complex system over the course of a long period of time. Basic statistical analysis is ideally suited to this, because it can provide a brief summary of a large body of data.

How many times did the event occur?
How long between events?
Are the delays between events evenly spaced, or randomly spaced?
Were there periods of even spacing?
What else tended to happen during these times?
Are there any soccer players that always had posession?
Are there any soccer players that almost never did?

Thats enough rambling for one post.