Ball Rolling

The trick to understanding how the ball moves is to assume the ball will roll in more or less a straight line and stop only when colliding with a blue block or the gray border. This action can be simulated in our model by using a search along a specific horizontal or vertical line for as long as the value of our model or array is zero.

As the ball may not stop or roll in the manner that we expect we only need to make a single move, restore the maze to horizontal and then take another picture to see what has actually happened. Despite the need for only the very next move we still need to determine the entire path from the white ball to the destination as the next move can only be calculated by knowing the entire route.

We calculate this path by starting at the balls current location and start searching in all the 4 possible directions for the next stop. As we only assume north, south, west and east ball movements we only need to check the possibility of the ball rolling in those directions. This process then repeats in each of those 4 new locations for the next 4 and so on. By checking if any of those new locations is the destination we can search the entire maze for the quickest way to get to the destination, i.e. the red square destination coordinates terminate the search.

The above image show the first four search levels. Note that at every stop point all those directions (other than the one just came from) are explored if there is no obstacle present in that spot in the array. This expansion can increase the total number of search paths quite quickly, however, as we have a relatively small maze this is not currently an issue and no search pruning is required.

The actual algorithm is known as a breadth first search as it will guarantee that the shortest solution (the one with the least ball rolls as apposed to actual distance) will be found first. This algorithm is done in VBScript and implements a queue structure for the search. As each new stop location is found it is added to the queue. The queue then grows with new search locations being added to the end with the top of the queue being the point of new exploration.

See the commented VBScript code contained in the VBScript module for further details.