# RealBasic: Robot A.I. – Part 2 – Pathfinding

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):

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!