OUR EXPERT
Grab the code for this tutorial with: git clone https:// github.com/ asmith1979/ lxf299_ bomberman/
DEPTH-FIRST SEARCH
QUIK TIP
DIJKSTRA ALGORITHM
Andrew Smith works as a developer for NHS Digital when he’s not updating ancient gaming code.
Depth-first search (DFS) is an algorithm for searching or traversing through graph and tree data structures. In the context of this game project, the algorithm is used to help an enemy character choose what action to take depending on the current situation. On each level of the map, various actions are attempted, such as:
When writing a program that uses graphics resources such as this one, create a folder called “images” that can store all the images used for the game project so that it is organised in a structured way.
When naming variables, function names and so on, try to choose a name for them that is understandable to you and others who will view or edit the code.
The Dijkstra algorithm is used to find the shortest path between two nodes in a graph. With regard to this game project, the algorithm is first used to find the shortest distance to a box crate to bomb and then the shortest distance to safety. If the player is nearer to the enemy character than a box crate is, then the shortest path is calculated between the enemy character and another player, which could be a human player or another AI player. Once all the box crates on the game map have been eliminated, the other enemy players on the game map (if they are still alive) is targeted with the shortest possible route to them. To see the route that the enemy Dijstra character calculates, leave the variable named show_path set to True – this is set in the Python script file menu.py. As well as attacking enemy players, the algorithm is also used to attempt to escape from enemy defeat by trying to calculate the shortest distance to safety behind a boulder that can protect against a bomb blast. All the decisions are based on the current grid or map layout of bombs, players, explosions or boulders, which is updated in real time during play. The implementation of this algorithm can be found in the Enemy class located in enemy.py in the class methods create_grid_ dijkstra and dijkstra.