So, the time has come to choose a first algorithm to move the Creatures in the World grid. For now, they move pretty stupidly, by alternating horizontal and vertical movements towards a target -the Spot with the highest score in their local environment-. The plan is to improve this by implementing an A* path-finding algorithm to determine where to go next.

Why A*?

A* is a very common pathfinding algorithm in graphs, which means it translates perfectly to pathfinding in grids. It does not require any preprocessing of the graph/grid, which is good for our part as we will never perform the pathfinding twice on the same grid.

A* is widely documented, so I will not detail it here. For reference, Wikipedia propose history and complexity information in addition to the pseudocode. On Ray Wenderlich's website you can find a tutorial for beginners complete with step-by-step illustrations of an example and an Obj-C pseudocode. And because it always help to be able to play around with new algorithms, here is a fantastic visualisation tool for pathfinding algorithms.

Heuristic choice

Part of our heuristic will relay on the evaluation of the environment, which we will probably discuss in a future log. For now, we are using the feeding power and the presence/absence of other Creatures to determine the score of a Spot during the local environment perception phase. If we could always reach our target immediately, this would not be necessary, but as it is possible that the Creature will only reach an intermediary point on the way to the target, we prefer to account for the convenience of each Spot.

We also want to account for the number of moves necessary to reach the target -in other words the Manhattan distance from the current position. This reflects the fact that we do not want to wander all over the grid before reaching our target.

In A*, the lower the heuristic the better. However, in our case the higher the score the better, so we set our heuristic function to be h(Spot) = ManhattanDistanceToDest(Spot) + MaximumPossibleScore - Score(Spot)

Our heuristic is admissible but not consistent/monotonous, so we will have to keep track of visited node (closed list) in our implementation.