What is an algorithm?

A algorithm is defined by both the algorithmic problem and its solution. An algorithmic problem is the characterisation of all the legal inputs for the algorithm and the desired outputs for those inputs. This is a rather trivial example of an algorithmic problem:

• Given a set of numbers (i.e 5,9,7,2,1,5) return how many numbers are divisible by 3.

For the above set of numbers the answer is 1. One could easily write a function that would give this output:

for input(a,b,c,d....) output(1) 


This would provide the correct output for the example set of data but not all possible sets of data - it is not an algorithmic solution. An algorithmic solution is one which will provide the correct output for any legal input. The pseudo-code below would be an example of an algorithmic solution for this problem.

(1) create variable a
(2) for - number of numbers in the set
           if - current number is divisible by 3
           add one to variable a
(3) return a


This code would produce the correct output for this algorithmic problem regardless of what the input is as long as it is a legal input (a set of numbers). It does not matter if the set is 5 numbers or a million - the correct result will be returned.

After claiming that my line of sight code in the previous post was an algorithm I realised that I do not know the definition of one. So I did some research and wrote the above. In hindsight I think I was correct in calling my code an algorithm.

Map Randomisation

I was recently thinking about how I could generate a playable random map for my tile based strategy game. I can foresee many difficulties with this. Below is a sample map created in the map editor:

This map although not very well balanced looks sensible. The roads are connected and features such as trees and mountains are grouped in semi-realistic clumps. The river is also continuous and flows from one side of the map to another. If this sort of result is to be achieved my a random map generator it will need to follow these rules:

• If the tile is blank there must be a chance that a feature is placed on it. This should be larger if adjacent tiles contain this feature.
• Roads and rivers must form a closed loop. (counting the map edge as closed).
If there is a road or river section in an adjacent tile and it is "facing" into the tile it must be continued.
• (Optional) The map be balanced in terms of resource and position or be symmetrical.

Ideally the chance of each feature (i.e. hills,woods,mountains) being placed in tile should be determined by an initial value and the tiles surrounding it. If this was a case the user could define the initial chances by selecting an option such as hilly or woodland before generating the map while the affect of nearby tiles could help produce the desired "clumping" of features.

I intend to try and write some pseudocode which achieves these effects soon.