There is also an implementation using a Qt front end and scriptable with ECL. For more information visit the QtCSG page.
This program demonstrates an algorithm for performing CSG (Constructive Solid Geometry) operations, and it is based on the Java CSG implementation called UnBBoolean (http://unbboolean.sourceforge.net/)
I found this excellent CSG implementation written in Java many months ago. Since it is very readable, and elucidates the concepts very clearly, I thought it may be worth translating this implementation into C++, so that this library can be used in C++ projects.
After months of procrastination and occasional work, the translation is completed. This is thanks to the excellently designed, crystal clear architecture of the original Java code, and the helpful comments.
Dealing with a large chunk of another programmer's source code is a very interesting excercise. There is an algorithm in the java code which implements the face cutting, but it runs all at once. If you want to figure out the reason for a particular problem, or simply want to peer into the inner workings of the algorithm, the standard line debugger is the wrong tool for the task. I found a simple and very useful technique for peering into code that runs all at once. I built a diagnostic object which allows me to take snapshots of the various geometric calculations it is performing, in order to "play it back" later, once the algorithm has finished. This was immensely helpful, and I will use this technique again. It is especially useful for reviewing algorithms that do things with geometry in 3D space.
Controls for the program
The controls are subtly different from my other programs, to allow finer control of navigation through the 3D space.
Moving the camera with the mouse:
Left mouse + mouse move ROTATES the camera.
Holding space + holding left mouse ROTATES the camera so it points to the selected location.
Holding space + holding left mouse + mouse move ORBITS the camera around the selected location.
Holding right mouse + mouse move PANS the camera along the camera plane, anchored on the selected point.
Mouse wheel MOVES the camera forward and back, based on the distance to the selected location. This means that before using the mouse wheel, make sure the mouse is hovering over the object you are interested in, because the distance of the step is a proportion of the distance between the camera and the object the mouse is hovering over.
Controlling diagnostic tool playback:
'd' toggles rendering of the diagnostic information.
Left arrow key steps the diagnostic playback backward one step.
Right arrow key steps the diagnostic playback forward one step.
Up arrow key steps the diagnostic playback forward continuously. (~20 steps per second, 1 per frame)
Down arrow key steps the diagnostic playback backward continuously. (~20 steps per second, 1 per frame)
A note on the diagnostic tool rendering:
Naturally it is up to the programmer what is being investigated, and I found myself frequently changing what the diagnostic tool should focus on. As you try to filter the volumes of data the diagnostic tool generates, I felt I had many options with how to proceed to learn more. I could either find some fancy ways to filter the data for the information I was interested in, leaving the snapshot taking as it was, or I could look at another aspect of the algorithm by modifying what I was choosing to record from the algorithm, and how I was going to present it.
There are 4 "episodes" in the diagnostic tool playback in this program.
1) Reveal the sequence of cuts made to the faces of the cone
2) Reveal each facet indivudually and all the facets that have come before, to enable me to visually ensure that there are no duplicates, and to inspect weird constructions of the algorithm
3) and 4), same as 1) and 2), except for the cube.
Screenshots:
All 3 models: difference, intersection and union:
Bird's eye view of the difference model:
External of the intersection model:
The interior of the union model:
One of the diagnostic frames:
Constructive Solid Geometry program
Lights Out puzzle experiment
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
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:
MagicVines clone uploaded
This is my simplified clone of the PopCap game, MagicVines.
While playing this game (the PopCap version), I was wondering whether strategic decisions about which group of 3 to clear really mattered, and whether a robot which will take the effort out of finding groups of 3 would change the game into a strategic one.
So, I made this program initially to reveal how solvable randomly generated boards would be. In this way, it becomes a little clearer whether the game is sensitive to strategic choices, or whether the game was only about how rapidly the player can recognise groups of 3.
If there is any strategy, it seems to be to try to clear the bottom cells first, because they are replenished less often than cells at the top.
Screenshots:
There are 2 executables in this zip file:
- MagicVines.exe
- MagicVines_Robot.exe
Usage instructions for MagicVines.exe:
Click a cell to flip it from horizontal - vertical, and vice versa.
The board clears consecutive groups of 3 or more matching cells in the same column or row continuously in the background. If the board is still eliminating, your group may not get eliminated right away - it will eventually as the board resolves itself. Try to get cascading eliminations!
Press 'r' at any time to reset the board for a new game.
Usage instructions for MagicVines_Robot.exe:
Clicking a cell will direct the focus of the robot player, so that it clears groups around the clicked cell first, before any other cell.
Press 'r' at any time to reset the board for a new game.
15 Puzzle solver
This program depicts a method for solving the 15 puzzle.
I wrote this to see if the explicit method I was using to solve this puzzle could be encoded, and whether there were puzzle instances my method would not work on.
A ran a separate testbed app that did thousands of runs to determine the success rate of various methods for solving this puzzle. For each run, a random instance of the puzzle was produced by making over 100 random moves. In this way, it is clear that the instance of the puzzle would be solvable.
An earlier method I used worked ~80% of the time for 100,000 runs. The method I present here was successful for all 100,000 runs, and then millions of runs after that.
When you step through the algorithm, you'll be able to clearly see the method for solving the puzzle.
Description of the method:
1) Move 1 into position
2) Move 2 into position
3) Get 4 out of the way
4) Move 3 to the top right
5) Move 4 below the 3
6) Slot in 3 and 4 in consecutive moves
Top row is done. Top row tiles are never touched again.
7) Move 5 into position (never touching the top row)
8) Move 6 into position
9) Move 8 out of the way
10) Move 7 to the top right
11) Move 8 below the 7
12) Slot 7 and 8 in consecutive moves
Top 2 rows are done. Top 2 rows are never touched again.
13) Move 10 out the way
14) Move 9 into position
15) Move 10 next to the 9
16) Slide 9 and 10 in consecutive moves so they are out of the way
17) Move 11 next to 10
18) Move 12 next to 11
19) Move 9,10,11,12 in 4 consecutive moves so that they are in a solid block to the left
20) Rotate the remaining tiles (13,14,15) until the 13 touches the 12
21) Rotate all 8 tiles until they are all in position
And now the puzzle should be solved.
Here are the controls:
'c' runs the algorithm continuously until the puzzle is solved
'p' pauses the continuous run
's' Moves one tile (steps the algorithm until it moves a tile)
'r' Generates a new puzzle
'q' or Esc closes the program
Notes on the implementation:
This program is another demonstration of the value of moving an algorithm into an updatable object that can be queried. By this I mean that instead of implementing your algorithm in a function, you implement it as a state machine, with the various states corresponding to different stages of the algorithm. Local variables of the function become member variables of this object, and any recursive function calls are handled by using a stack. In this way, it is possible to observe the operation of the algorithm, and perhaps do other things in the meantime.
From the caller, its the difference between doing this:
RunAlgorithm(data);
and this:
Algorithm a;
a.Reset(data);
while(!a.Finished())
{
a.Update();
}
You can see where the second approach would have many advantages.
Screenshots:
Picture Logic solver
This program solves picture logic puzzles, and demonstrates the algorithm for a single solving pass on an individual row or column in detail.
PictureLogic.exe generates a random image, and solves it by repeatedly applying the solving passes alternately on all columns and rows.
PictureLogic_RowColAlgorithm.exe demonstrates the algorithm for applying a single solving pass to a row or column.
Controls for both PictureLogic.exe and PictureLogic_RowColAlgorithm.exe are:
'c': Commences or resumes continuous updating of the solving algorithm
'p': Pauses the continuous run.
's': Update the solver one step.
'r': Generate a new puzzle instance.
'q' or Esc: Closes the program.
For the algorithm demonstration program, there is some basic logic guiding the generation of the puzzle instances, but it can still generate unsolvable instances. However, the algorithm will detect these.
Screen layout for PictureLogic.exe:
The only thing displayed is the picture logic puzzle. This consists of the grid and block sizes, as you would see in any puzzle book.
Screen layout For PictureLogic_RowColAlgorithm.exe:
The puzzle instance is displayed in the 1D grid at the bottom: Solid rectangles indicate a cell that must be filled, hollow rectangles indicate a cell that must remain empty. Above this 1D grid are the block sizes.
Just above the puzzle instance is a 1D grid is where the results of the solving pass will appear at the end of the run.
The algorithm will enumerate every possible placement of the blocks in this 1D space during the course of the algorithm, and you can see the results of its work in the middle of the window.
At the top of the window are grids describing the "invariant" cells - the cells that stay the same for all possible placements of the blocks. These are then referred to to generate the result of the solving pass.
I hope these programs are interesting for you, and perhaps teach you about this puzzle and one way of solving it, and perhaps show the benfit of encapsulating an algorithm into an object so that you may query it and control its execution from the outside.
Screenshots:
Domino placement game
This is an implementation of the domino placement puzzle. In this version, you are able to explore the puzzle in a new way - the program plays the puzzle with you!
When you place a domino, the AI propagates the constraints of your new placement, allowing you to see the logical effects of your placement. You can very quickly see whether you'd get to a dead end or a solution with a particular placement, and there are unlimited levels of undo.
You can have your puzzle loaded from a file, or watch as the placer generates a new puzzle for you.
Screen layout:
The left grid shows the puzzle.
The right grid is the solving area.
The middle column shows all unplaced dominos.
Controls:
Clicking once between 2 cells is sufficient to describe a domino placement.
Left mouse in between 2 cells in the right grid will place a domino there.
Right mouse in between 2 cells will reveal all the other places that same domino could be placed.
Mouse wheel when the mouse is over the center column to scroll the available dominos awaiting placement.
Right click on one of these available dominos to see where it could be placed.
Press 'u' to undo your last placement (there are unlimited undo levels).
Press 'l' to load the next level in the level file. (It loads from board_in_dominosa.txt).
Press 'r' to reset the solution board and begin the puzzle again.
Press 'n' to generate a new puzzle.
The puzzles in board_in_dominosa.txt are in the format that dominosa.exe uses when you save a puzzle. Dominosa.exe comes from Simon Tatham's Portable Puzzle Collection, available from http://www.chiark.greenend.org.uk/~sgtatham/puzzles/
Enjoy!
Screenshots:
