Tag Archives: algorithm

Towers of Hanoi puzzle game applied to real-life and work

Posted on September 10, 2012 by Tom

The Towers of Hanoi game is a very clean, effective puzzle to learn problem solving, and also learn problem analysis. It’s easy to play with 2-3 discs, and becomes more challenging for inexperienced people with more discs.

After learning the method to solving, it becomes easy, where each additional disc simply doubles the time it takes to solve the puzzle. The real challenge then becomes keeping track of which level within which stack you need to move.

I often refer to this puzzle in conversation, when doing things in life that require moving lots of stuff, physically, mentally, emotionally. It’s come up in my facebook status messages.

Continue reading →

Posted in Technology, Thoughts | Tagged , , , | Leave a comment

Bezier timing

Posted on April 7, 2010 by Tom

I have just finished a bezier timing algorithm, and I’ll give a small description here.

I will be using the bezier values a linear stepping value in a loop… layman’s terms: a counter that counts up evenly, 0,1,2,3 or 0,2,4,6, etc.

There are methods to do this in the iPhone SDK but I already wrote half of the code, and it wasn’t much effort to complete.  Plus, I looked up the CAMediaTimingFunction class, and it seemed too complicated just for what I wanted (just an in-and-out structure).

So all I did is this: create a 100-element array.

.. and it gets a bit complicated, so here’s the code to build the array:

float t;
int i;
CGPoint bpoints[1000];
CGPoint bypoints[100];
for (i = 0; i < 1000; i++) {
 t = i / 1000.0f;
 bpoints[i].x = (1-t)*(1-t)*(1-t)* 0  + 3*(1-t)*(1-t)*t*0.5 + 3*(1-t)*t*t* 0.5 + t*t*t*1.0;
 bpoints[i].y = (1-t)*(1-t)*(1-t)* 0  + 3*(1-t)*(1-t)*t*0.05 + 3*(1-t)*t*t* 0.95 + t*t*t*1.0;
}
for ( transitionTimeStep =0; transitionTimeStep < 100; transitionTimeStep++) {
 float closest = 1.1;
 int closestI = -1;
 // Find the index in bpoints where .x is the closest to the transitionTimestep percent
 for (int x = 0; x < 1000; x++) {
  if ( fabs( bpoints[x].x - ( transitionTimeStep /100.0f)) < closest) {
   closest = fabs( bpoints[x].x - ( transitionTimeStep /100.0f));
   closestI = x;
  }
 }
 bypoints[transitionTimeStep] = bpoints[closestI].y;
}

The first loop creates a high-resolution set of points on a quadratic bezier curve (see Wikipedia’s page for Bezier curves) where the 4 points are between 0.0 and 1.0.  The points (0,1,2,3) have the following x,y coordinates:

  • 0,0
  • 0.5, 0.05
  • 0.5, 0.95
  • 1.0, 1.0

If a person even multiplied these values by 100 and then used a program like Adobe Illustrator, the curve would look something vaguely like a capitol letter S.  Rather, it’s actually more like a forward-slash /  and little curves at the top and bottom .

So I collect the high-resolution points of the line, and then loop through my time-step array.  For every element in the time-step array, I examine every x-coordinate value of the bpoints array.  If the value is closest to the current time-step index value, then I save the bpoints array y-coordinate value.

Yes, this seems very complicated now, but when I was doing it, it seemed very easy.  I guess sometimes I just get on a roll and create complicated stuff.

Also, I know there are better ways to do this, but I only want a look-up table and when I see it in live operation before typing this post, it works beautifully.

An important note!  The bpoint array is VERY important.  It is not good to simply create an exact-resolution array and fill it with values.  I did that at first, and found that there were too many indexes being dropped, that when the timing animation was run, there was a lot of choppy movement, like if the smooth slope of the curve was suddenly turned into a staircase of jagged edges.

So, creating the higher-resolution array first and then scanning it for the closest x value was the logical solution.  Perhaps I could have done it with a 200 element array, but I didn’t try it.

The process only takes a split-second, and it’s only done once at the beginning of the program.

That’s all, take care everyone.

Posted in Technology | Tagged , , , , , , | Leave a comment

Progress in movement algorithm design

Posted on February 19, 2010 by Tom

The album Bolero Gypsies: new flamenco is playing in my ears and the book iPhone cool projects from apress is spread open on my lap and I am typing a blog update on the iPod touch.

The chapter in the book I am reading is about the subject of networking. This may be getting ahead of myself, but it’s good to know for when the opportunity presents itself, and it will.

Yesterday, I created the movement of one of the principle game assets that will be moving constantly in the game. Let’s call this object a “bird” (it’s not in the game, neither is it in the air but it serves for this explanation).  The movement requires intelligence, not merely a simple movement like a rotation of some degrees on every game loop (eg. coins in Super Mario games or rings in Sonic the Hedgehog games). The game world may be large when the game is finished. The first draft for movement has become the following: a “home path” in the same style of the common footpath worn by animals in their native environments, when they travel the paths frequently. So it is with this movent. A path throughout any part of the game world.

This path is achieved by using a number of data variables.

The most important is the array of “checkpoints”. These are the same as checkpoints in a racetrack. In my first version of the movement system, the checkpoints are created as cubes in the world 3d model file, with special object names and serial number prefixes, such as “homepath001”. The name is searched and all the points are loaded into an array.

After the array, the most important variable is for storing the index serial number for the checkpoint the bird will be moving toward. Optionally, this destination may be interupted an replaced with any arbitrary location and the bird will move toward there instead.

Now, storing the index value of the next checkpoint allows us to determine the direction of movement whenever we want to. So now, this permits us to consider other random travel destinations.  If any arbitrary destination is chosen at anytime, another variable must store the yes/no status indicating if the object is moving toward the next checkpoint or not. So this possibility brings the necessity of another variable to store the actual destination location instead of only referencing the next checkpoint from the next-checkpoint-index. When the next checkpoint is reached, the index of the next checkpoint is updated, and the location for the new next-checkpoint is copied to this destination as the default destination.

This is just the tip of the iceberg.

Assuming movement toward some arbitrary location is part of the object’s life cycle, not only following a path forever, then it stands to reason to store not only the next destination separate to the next checkpoint as we’ve discussed, but also store the current home-path-location of the bird as soon as a new, arbitrary, destination is created. This will give the bird next-destination options to choose between, when it reaches the arbitrary location.  It may chose to return to it’s home path from where it left the path, somewhat tracing it’s path backward. Or, it may choose to continue to the next checkpoint directly.

In the case of the city pigeon bird, a home path might be the path around a large office building, and its checkpoints are lamp posts and parking lots (it may choose to walk in a parking lot).  When it is anywhere flying or walking, it may decide to go look at something away from its path, but it will try to keep its home building in sight, and if it decides to return, it can go onto wherever it wants, in the direction of its home!

Having more options is always a better thing than few options or only one.

Following this, I have implemented bezier curves for a smooth transition from approaching one checkpoint to the start of the next checkpoint’s path.  It doesn’t work well if a bird (or any other creature) is moving in a straight line and then instantly is moving in a separate direction..

Never before have I worked with bezier curve equations, so it’s brand new.  But I got the equation from Wikipedia’s page and plugged it in, and now it works.  This is a complicated issue, and not really part of algorithm design, but of implementation.

That will remain for some other day.

Posted in Technology | Tagged , , , , , , | Leave a comment