In this article we’ll going to learn Robby to use efficient pathfinding. The algortihm we’re going to use is spatial A-star. I used the implementation in C# of Christoph Husse to get me started. His original code can be found here.

Here you can see the algorithm at work on a labyrinth:

An explanation of the algorithm itself can be found here and for beginners here is an excellent tutorial.

In the structure of our project we’ve added a new folder: Algorithms. This will be the place where we will put all the algorithmes we’re going to use.

**ABSpatialAStar: **The main class that can do a search.

**ABOpenCloseMap: **The grid that contains our known map (made of ABPathNodes).

**ABPathNode: **A single node that will be checked if Robby can walk here or if it is a wall.

**ABPriorityQueue: **A good A* implementation does not use a standard Array for the open nodes. If a standard Array is used, the algorithm will spend a huge amount of time searching for nodes in that list; instead, a priority queue should be used. The one I used is a modified version of the one BenDi wrote. The original one can be found here.

I’ve added some ‘dirty’ tricks to speed up the process. e.g blowing up de map for a faster search. It scales down the map and blows up all the walls so they appear a lot thicker. This is easier for the algorithm to find the shortest path.

By using a reasonable blowup factor this has as a side effect that Robby stays away from the walls a little further. The result of the blowup can be seen here:

The code for the BlowUpMap function:

Function BlowUpMap(inPic as Picture, OddFactor as Integer, ScaleFactor as double) As Picture Dim tmpPic As Picture Dim w,h As Integer Dim x,y As Integer w = inPic.Width h = inPic.Height tmpPic = NewPicture(w*ScaleFactor, h*ScaleFactor, 32) Dim inRGB As RGBSurface Dim tmpRGB As RGBSurface inRGB = inPic.RGBSurface tmpRGB = tmpPic.RGBSurface Dim FactorDev2 As Integer = Floor(OddFactor/2) Dim FactorDev2Plus1 As Integer = FactorDev2 + 1 Dim a, b As Integer For x = FactorDev2Plus1 To w - FactorDev2Plus1 For y = FactorDev2Plus1 To h - FactorDev2Plus1 If inRGB.Pixel(x,y) = &c000000 then For a = x - FactorDev2 To x + FactorDev2 For b = y - FactorDev2 To y + FactorDev2 tmpRGB.Pixel(a*ScaleFactor,b*ScaleFactor) = inRGB.Pixel(x,y) Next Next End If Next Next Return tmpPic End Function

Implemented on our house plan this is what happens when Robby knows how to find the shortest path to the point we click on (make sure there is a path to the point you click):

The source code for the project can be downloaded from:

http://www.gorgeousapps.com/Rob2.zip

In the next episode we are going to make it a little more difficult for Robby to go somewhere by opening and closing doors so Robby has to adapt to the new situation.

Bye for now!

July 7th, 2012 at 15:06

A* requires discrete points to consider for path-finding. How do you convert your input mpa into these discrete points? Do you just use the pixel locations and have a huge list, or do you quantize to a particular size?

July 9th, 2012 at 09:56

I do use the pixel locations but the BlowUpMap() function decreases the size of the list.