Posts Tagged ‘Path finding’

Path finding / Routing in Games

September 8th, 2010 No comments

On of the more complex Topics in Game-Development is the Path finding Problem. The task is simple : “Go from Point A to Point B on the shortest Distance”. Mostly seen in some Tower Defense games. The easiest way to solve this is to give your moving objects a pre-defined path. You’ll see that in a lot of Tower Defense Games because it’s plain simple.

Some of the other Tower Defense Games are keeping the Path finding simple by only moving in 4 Directions, so always move in a right angle. This makes the math behind the calculations a Lot easier. But this looks a little bit stupid to me when NPCs running against a wall, and then moving left or right. So by searching for some algorithm that performs well an consider at least 8 directions, if found nothing handy in the web.

The Solution was to make my own Route-Algorithm which looks pretty clean at the Moment and performs pretty good. I wrote some tests that print a result route in a HTML File:

The image shows the route path in green, the blocked Parts in red. The start point is on the top , the end point at the bottom. How dows the algorithm work ? In short words: I pre calculate the complete Gamefield, every Field has a “weight”. So if your Objects starts moving it always knows the next step from the current field by looking at all neighbor fields. So the routing is fixed as long as no more “blocks” are occurring, so you only have to calculate one time and work with that result till something changes.