Pathfinding programming challenge
Summary: Implement a simplified A* pathfinding algorithm
The simplifications:
Movement is restricted to up, down, left and right.
Moveable squares all cost the same to move over
The simplified A* pathfinding algorithm
The world is divided into squares, one square is the starting point and another the destination. You will be given the number of rows and the number of columns. Squares should be numbered from left to right starting in the top left corner, e.g.
Code:
1 2 3 4 5 6
7 8 9 10 11 12
13 14 15 16 17 18
There are obstacles on some squares that mean these squares cannot be moved over, the location of the obstacles will be given using the numbering system above.
To find the path from the start to the destination you need to do the following:
1. Add the starting square to a “possible” list. This list contains all the squares that may become part of the path (they might not though which is why it’s called the possible list).
2. In turn, look at the squares immediately to the left, right, up and down. If these squares are moveable (i.e there isn’t an obstacle on them) add them to the possible list. If you add a square to the possible list you also need to record is parent square, i.e the square from which you would move onto this square, in this case it’s the starting square.
3. Remove the starting square from the possible list and add it to the “closed” list, the closed list contains squares you don’t need to consider.
You then need to work out which square to move to next, this is done be calculating the square with the lowest F score, where F = G + H
G is the movement cost to move to this square ( as per simplification 2, all squares cost the same), this is the cost to move to the parent square + the move cost of this square (i.e how many steps along the path is this square)
H is an estimated cost to move from this square to the destination, this is purely a guess as we don’t know the path to get there. A simple guess is the number of horizontal squares to the destination + the number of vertical squares to the destination.
The F score should be calculated for all squares you added to the possible list in 2
To continue the search:
4. Pick the square on the possible list with the lowest F score
5. Move this square from the possible list to the closed list
6. In turn, look at the squares immediately to the left, right, up and down. If these squares are moveable and not on the possible or closed list add them to the possible list. Remember to record its parent square.
7.If the square you a looking at is already on the possible list calculate the G cost to move to this square from the current one, if this G cost is less than the G cost already associated with the square then you have found a better path to that square. You should update the parent of that square to be the current square and recalculate is G and F scores.
8.Once you have checked the squares up, down left and right you should go to 4 and repeat until when you are doing step 6 you end up looking at the destination square. You have then found your path.
9.To create the path, follow the chain of parent squares back from your current square, this should lead you back to the start.
If you get to the point where the possible list is empty and you haven’t found your destination then there is no path!
Here is a graphical implementation of this simplified algorithm I made when I learnt it. The white squares are on the possible list, the purple have been looked at and are on the closed list, the direction of the ring thing indicates the parent square.
http://youtu.be/OuxkXUsljes
So. What do you guys think? I will come up with the specific details of the competition if people like the idea.
I've been trying to put something together but it seems to be taking significantly longer that last year. It's difficult to find enough algorithmic/computational based problems that have some element of originality and don't require a maths degree to understand 
Or if all else fails hopefully I will get a free weekend to plan it some more. I really like the path finding idea suggested above but it might be too complex to have as a single problem to solve.
