So as a part of the programming challenge module I did last semester, we were supposed to build a game which is similar to the Nintendo Tank war game. This was a group project and Tharindu and I designed and build the game. What we had to do was to build a client who can communicate with a server. All together five clients can connect with the server simultaneously and the server sends global updates about the position of each clients, positions of coin piles, etc on each second. the clients has to process this global update and send its next move to the server before the next global update is arrived from the server. More details about the server specification is available here.
So the main objective of the game is to collect as many coin piles as possible. The game is played on a 2D cell matrix as you can see on the below image. So what we had to do first was to create a suitable data structure which can be used by the path finding algorithm efficiently.
So for each cell we created a class called “Cell”. It has two constructors. A cell can be initialized either by giving its ID or it’s x,y coordinates. It has a list of adjacent neighbor cells(up,down,left,right). A “parent” variable, which is used in path finding algorithm and boolean variables to set if the cell is an obstacle or a coin pile. The Constant “ConfigData.Map_size” is either the number of columns or number of rows in the square matrix.
And then we have a “World” class which is composed of “Cell” objects. In the constructor of the “World” class a 2D array of “Cell” objects is initialized and for each cell in the 2D array, the neighboring cell is added to the neighbor’s list. We can get any cell in the 2D array either by its x,y coordinates or the cell ID.
Then comes the interesting part. We used Breath First Search algorithm to find the nearest cell which contains a coin pile. In the constructor of the class “BFS” a world object is initialized. findNextMove() method returns the ID of the next cell where the tank client should move. This method requires the cell ID of the current tank’s position. Then the Cell object corresponding to that position from the world object is assigned to the “start” variable.
The BFS algorithm works as follows. Until the queue which contains all the possible goal cells is empty, each cell in the queue is dequeued and scanned for it’s neighboring cells. If those neighbors are obstacle cells(water,brick,stone) then those cells are marked as visited, but doesn’t added to the queue. If a neighboring cell is not an obstacle and doesn’t contain a coin pile either, then that cell is marked as visited, set its parent cell as the current cell and added to the queue. If a cell with a coin pile is found, then using the “parent” variable in each cell, a back tracking loop will return the ID of the next cell where the tank should move. If the queue is empty(i.e. no coin pile is found) then after while loop finishes, it will return -1, which is not a valid cell ID.
This algorithm is best suited when the search space(size of the “World” 2D array) is small (typically less than 2500 cells). BFS is guaranteed to find the closest goal (if a goal exists). If there is no goal, BFS will go through the entire search space, thus the size of the queue will increase by 3 cells on each iteration (assuming there are no obstacles). This pitfall can be avoided by using AStar algorithm. But for a small search space BFS is more than enough. The full project can be downloaded from the Bitbucket repository.