Artificial Intelligence for Games

A* Pathfinding Algorithm

For this first assignment, we had to implement the A* algorithm for finding the path from the current position to the goal. The engine and all the tools for the character to move from one point to other were given so we could concentrate all our effort in the pathfinding.

In the video you can see:

  • How the search for the path changes for different heuristics.
  • Rubber-banding (removes redundant nodes from final path), smoothing and straight line path search.
  • Usage of previous methods in a more complex map.

Cellular Automata

For the final assignment we had to research and present an interesting project about an AI related topic. We saw CA slightly during the first weeks and I felt like this topic could be exploited a bit more. I did a small research about the topics this technique could cover and the most interesting ones where terrain generation and fire simulation, so I decided to combine both of them.

In the video you can see:

  • Different kind of terrains generated using only CA, where blue is water and green is land (darkest areas represent high altitude).
  • Simulation of how a civilization would spread along the terrain. Probability to spread along high altitude is lower, that’s why population concentrates in the lightest areas. Population dynamics were done using the rules in Conway’s Game of Life.
  • Fire simulation, where there’s a probability for fire to start at a random cell, a probability for it to be caused by overpopulation and a probability for it to be propagated to surrounding cells. As in population, probabilities decrease as the altitude increases. Red cells are cells currently in fire and black cells are burned cells.