How monsters can always find players in video games?

11 May

Most of us have played video games long time ago, personally one of my favorite old titles was resident evil 2. In this game you were chased by raccoon city zombies and you either need to kill them or run away from them. When I played that game I was wondering how those zombies can always find me, no matter where I hide. They have even kept following me around if I tried to escape.

In this post I will try to answer this question for you, and I will show you by an example application I have created, how those bad zombies can always find you, no matter where you are hiding.

To simplify this let’s rephrase what we need to do. “we need to make the computer draw the shortest path (route) around obstacles between two points” for this purpose a computer scientist called Dijkstra invented a technique called “path finding”. This technique does exactly what we want. Latter on, other computer scientists improved this technique and called it “A star”.

For the A star technique to work the game level is divided into a grid of small squares,  All the squares overlapping the game map walls should be marked as none passable squares. All of the non marked squares are considered passable which simply means that the zombies can walk in this area (As far as I know zombies can’t penetrate walls, correct me if I were wrong)

The square overlapping the game player should be marked as well (in this figure it is marked in green), also the square overlapping with the zombie should be marked too (in the figure it is marked in red). Now the problem has been simplified enough for the A star to operate.

The A Star will inspect the eight squares around the zombie (diagonal squares are also counted) and choose the closest passable square to the player based on a heuristic function (simply a guess based on a mathematical formula).  as a result a path between the zombie and the player can be determied by repeating this process on each chosen square.

I don’t want to make things complicated so I will not talk about heuristic functions but you can try things yourself using this application. you can find the program in the following path after  you extract the archive [..\PathFinder\PathFinder\bin\Release\] you just need to run PathFinder.exe. If you are having any trouble using it, you can watch that video to know how to use it.

I have also included the source code for the computer science guys who are reading the post, as they might be interested in it. The application will only fail when there is no route between the starting node (zombie) and the target node (player), if this happened you will need the task manager to kill the application.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: