justinhj page

A* algorithm tutorial Tweet Production quality source code accompanying this tutorial can be found on Github Related blog posts Who uses this A* code Bug fixes Avoiding ten common video game AI mistakes Introduction Welcome to this A* tutorial. The A* algorithm is often used in video games to enable characters to navigate the world. This tutorial will introduce you the algorithm and describe how to implement it. State space search A* is a type of search algorithm. Some problems can be solved by representing the world in the initial state, and then for each action we can perform on the world we generate states for what the world would be like if we did so. If you do this until the world is in the state that we specified as a solution, then the route from the start to this goal state is the solution to your problem. In this tutorial I will look at the use of state space search to find the shortest path between two points (pathfinding), and also to solve a simple sliding tile puzzle (the 8-puzzle).