Game Design with Intel Tools Part 2: Parallelizing A* Algorithm Share your comment!

This blog is the second in a four-part series in which the Intel software development tools are used to develop a game. The first blog in the series uses Intel Performance Primitives (IPP) to perform image processing for the game’s splash screen. The first article can be found here. The source code for all articles in the series can be found on Sourceforge here.

The Play Field

This game is played from an overhead view. It is similar to Pac Man in that there are four enemies that chase a single player object. For right now, the game will simply use colored rectangles to represent the enemies, the player, and the walls. At a later point, the plain blocks will be replaced by animated images. For now, though, the walls are blue, the enemies are green, the player is red, and a representation of the shortest path from enemy to player is yellow.

The following figure shows the game when it first starts. There are predetermined walls that are drawn as blue rectangles. The player is in the center of the screen, and is represented by a red rectangle. Finally, the four enemies are in the four corner regions, and are represented by green rectangles.

game2-1

Code Additions

There are two main code additions in this second part: drawing the play field and finding the shortest path from each enemy to the player. Drawing the play field is done based on a two-dimensional array that contains representative values for each type: wall, player, and enemy. I have used a similar approach in many of my classes where we created software that implemented similar overhead view games.

The second chunk of code that was added was code to find the shortest path from enemy to player. The algorithm is known as the A* algorithm (pronounced A star). It is commonly used in game development for similar tasks such as finding shortest paths around obstacles. A* is a modified breadth first search, and examination of the code will shed light on how this algorithm works.

Showing Shortest Paths

The program has a mode that shows all shortest paths between enemies and player. The paths are drawn with yellow rectangles. The following figure shows the shortest paths drawn on the play field.

gamae2-2

The following code shows how the program manages the calculation and drawing of the shortest paths.

First, please realize that the drawPath() function is not called during normal game play. This is simply to show the shortest paths right now during development. One of the issues with this code is that it is sequential. This causes an unnecessary bottleneck since finding shortest paths must happen repeatedly at a regular time period. The best way to mitigate this bottleneck is to parallelize this loop. We can use OpenMP to parallelize the loop. There are no data dependencies, so this provides a straightforward use of OpenMP. Before parallelization, the loop took 124 milliseconds, and after the parallelization it took 37 milliseconds. The modified (parallelized) loop code can be seen below.

Conclusion

Using OpenMP, which the Intel compiler provides, speeds up finding the shortest paths. This continues game development, and Intel is providing tools to enhance the effort.

Posted on February 17, 2017 by Rick Leinecker, Slashdot Media Contributing Editor