PacMario is a 2D game inspired by the popular retro games: Pacman and Mario. General logic of the game is derived from the first one whereas graphics are borrowed from the Mario Game. Project is coded in the C programming language. Uses the SDL graphic library. Opponent’s moves are generated by finding the shortest path between nodes in a graph.
Graphical module was separated from the logic in the code. As a result code gained substantial flexibility (e.g. implementing a new graphical engine would be a fairly easy task).
Graphics and logics are glued back together in the control module. It performs as an intermediate layer whose main responsibilities are: initialization of modules, keyboard events handling, communication between logic and graphics, and lastly final clean up.
Module division per file
- graphics: ‘gfx.c’
- logics: ‘logic.c’ ‘adj.c’
- control: ‘main.c’ ‘ctrl.c’
Two of the three computer players are “dummies” - their moves are generated by random function. The function creates linked list of permissible moves for the current figure position. The next move is drawn from this list.
The logic behind the third player’s moves is a bit more advanced. Its moves are optimal in any given situation due to the implementation of the Dijkstra Algorithm. To achieve this a few transformations were needed.
The map of the game is coded as a two-dimensional matrix. In the first transformation it is converted to the undirected graph with edges of equal cost. In the memory, the graph is stored as an adjacency matrix. A generated move is first stored as a graph node and then converted back to the index position of the two-dimensional matrix.
Example (4x4 map)
The picture below subsequently shows: visual representation, two-dimensional matrix, undirected graph
A slight modification of Dijkstra’s Algorithm was needed to find an optimal move for the third player. The original Dijkstra only holds information about the distance of the shortest path, not the nodes of the path itself. An auxiliary array was added to store predecessors for each node included in the shortest path in the graph.
The game leverages from basic multi-threading, since the rendering and movement calculations could be performed concurrently. In the main loop, when user’s and computer’s moves are applied to the board, the program starts separate thread for performing graph algorithms, which are moderate in terms of time consumption (on Mac M1 machine it took ~4-7ms for moves generation), thus a slight improvement of the performance was achieved.
The Game uses SDL2 graphical library.
SDL2 project website: https://www.libsdl.org/
Library sources
Installation of the following libraries is required to compile and run the game:
-
SDL2 Image (https://github.com/libsdl-org/SDL_image)
Linking libraries in the linker is needed for SDL2, SDL2 Image, SDL2 TTF. Depending on the user’s operating system, it may be necessary to change paths in the #include declarations: SDL.h → SDL/SDL.h and SDL_image.h → SDL/SDL_image.h)