Monthly Archives: July 2012

RealBasic: Robot A.I. – Part 3 – Pathfinding with obstacles


Let’s learn Robby to react to an obstacle on its way to the target!

Just like your GPS has to recalculate the route to your destination if a road is blocked, Robby must adept and recalculate a new path to his target if a door is closed in front of him. You can close or open a doorway by rightclicking on the grey parts of the map.

When Robby starts a walk, his belief state is that all doors are open. If he encounters a closed door, he changes his belief state and recalculates an alternative route. Once the robot arrives at his destination, the belief state is reset:

Example:

Robby wants to go from point A to point B. The robot calculates its route and starts the walk (Dark blue path). Suddenly it finds a closed door in its path. Robby recalculates an alternative route to B and continues its walk (Light blue path). Pretty nifty hè! 🙂

Let’s look at it at work on our familiar floor plan:

As you can see I’ve also added the possibility to set Robby at any start position within the map and you can choose between a number of sensors.
Less sensors is faster but also less accurate and the algorithm may fail!

Note:
I’ve also been asked to extend the pathfinding example for the people that do not have RealBasic so they can use their own maps. To use your own maps with the ABExplorer.exe file you can give a map at the command line:

Systax: ABExplorer.exe /M=mapfile.png where mapfile is a picture file.

The map file specs:
1. must a picture size 500×500 pixels.
2. only contain 3 colors:

black RGB(0,0,0) for a wall
white RGB(255,255,255) for empty space
grey RGB(192,192,192) for a doorway that can be opened and closed

3. doorways that can be closed must be either horizontal or vertical, not diagonal.
4. make sure the map is ‘closed’: there is no way Robby can escape from the map.

The code and program can be downloaded from here

Try it out with you own maps!

In the next part of this series we’re going to learn Robby to find his location within the map. As for now, when we put Robby somewhere on the map, we tell him in which room and at what x,y coordinates he is. But what if he has to find this information for himself?

Until next time!

Click here to Donation if you like my work

Advertisements

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

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!

Click here to Donation if you like my work


%d bloggers like this: