The Prison Escape was a C++ AI simulation that I made in my final HND year at ESAT for the AI programming subject. In it, there were three types of agents: the guards that protect and patrol the prison, the prisoners that are forced to work in turns and the soldiers that tried to rescue their allies. The main focus of the project was the calculation of the paths and the design of the behaviour of the agents.
For the calculation of the paths, I used the A* algorithm that I combined with different “tricks” looking for an efficient and faster way to handle the problem. First, I started precalculating some paths like the routes from the soldiers base to the entries of the prison.
In the next step, I introduced LODs to the costs map to be able to parallelize the process with threads. Thus, the agents didn’t really need to wait until the calculation of the entire path to start moving. Another bonus point it’s that if the agent has to change its destiny in the middle of the current path, all the time consumption calculating the entire path it’s not wasted because it didn’t happen. Also, I added a counter to the intermediate paths of the LODs to detect if it’s worth storing it instead of calculating it each time, similar to a heat map.
Going further with the heat map idea, I translated the hotter points and zones of the map to a “point of interest” and precalculated the paths between them similar to a graph. Basically, at this point, I had detected, precalculated and stored the paths that will be queried by the agents in almost every simulation.
To design the different behaviours of the guards I implemented a finite state machine. Thus, I gain modularity because I can separate and differentiate more easily in each case. They were categorised by its movement type that could be a pattern or a graph. The pattern was a combination of simple commands like move to the right, stop and turn left. The graph was a matrix that stored the path combination possibilities and each path was calculated using the method mentioned before.
Codeffee 
Leave a Reply