Pursuit-Evasion Game (PEG) consists of a team of pursuers trying to capture one or more evaders. PEGs are important due to its application in surveillance, search and rescue, disaster robotics, boundary defense and so on. But, in general, PEG requires exponential time to compute the minimum number of pursuers to capture an evader. To mitigate this, we have design a parallel optimal algorithm to minimize the capture time in PEG. Given a discrete topology, this algorithm also outputs the minimum number of pursuers to capture an evader. Our new algorithm enable us to investigate larger topologies. A classic example of PEG is the popular arcade game Pac-Man. Although Pac-Man topology has almost 300 nodes, our algorithm can handle this. We show that Pac- Man is overkill, i.e., given the Pac-Man game topology, Pac- Man game contains more pursuers/ghosts (four) than it is necessary (two) to capture evader/Pac-man. We also extend the algorithm to consider different speeds. we also extended the algorithm to increase evader survival in a game. We evaluate these algorithms for many different topologies.