PathFinder is broken, here is my guess

[GoogleCodeExporter]

What steps will reproduce the problem?
1. Try to display the path given by BWTA::PathFind() on a map with thin
separators (see attached map).
2. Give the marine a goal position outside the maze, on the bottom right
corner of the map.
3. See how the path goes through walls (unwalkable tiles).

What is the expected output? What do you see instead?
Expected output: the path should go to the top/north.
But it goes to the right/east.

What version of the product are you using? \
BWAPI 2.6, BWTA 1.6.3 (rev. 133 on the svn)
On what operating system?
Windows XP SP2

Where is the bug? I think that the bug is in src/load_data.cpp line 54. The
data used for lowResWalkability is only the top left square from the 4
squares constituting a lowResWalkability square from rawWalkability ones.
This is false as you can see on unwalkable.pdf attached with this report.
You can print this walkability of the WalkTiles on the example map (or any
map presenting such a disposition) with:
    for (int x = 0; x < Broodwar->mapWidth()*4; x++)
    {
        for (int y = 0; y < Broodwar->mapHeight()*4; y++)
        {
            if(Broodwar->isWalkable(x,y))
                Broodwar->drawBox(CoordinateType::Map, 8*x, 8*y, 8*x+6,
8*y+6, Colors::Green);
            else
                Broodwar->drawBox(CoordinateType::Map, 8*x, 8*y, 8*x+6,
8*y+6, Colors::Red);
        }
    }

Suggestion: You should use the full grid in AStarSearchPath() from
src/pathfinding.cpp (for instance but not only, lines 186 and 187) to get
the result right. 

Regards,
Gabriel

Original issue reported on code.google.com by gabriel....@gmail.com on 31 Mar 2010 at 1:24

Attachments:

• test_pathfinding_dumb_simpl.scm
• unwalkable.pdf

[GoogleCodeExporter]

No one to answer this? And BWTA won't work with CGAL3.6 / boost1.42...

Original comment by gabriel....@gmail.com on 5 Apr 2010 at 10:24

[GoogleCodeExporter]

There are exactly two problems, the one mentioned above coming from the 
resolution of
the walkability grid and one coming from the algorithm: between lines 189 and 
190 of
src/pathfinding.cpp, you should have a test for "can we cross diagonally" (same
problem as above). Such a test can be written: 
if (!(p.x() == x || p.y() == y) && !(walkability[p.x()][y] || 
walkability[x][p.y()]))
continue;

Regards,
Gabriel

Original comment by gabriel....@gmail.com on 6 Apr 2010 at 11:39

[GoogleCodeExporter]

Original comment by lowerlo...@gmail.com on 11 Apr 2010 at 8:09

• Changed state: Accepted

[GoogleCodeExporter]

I think there is a mistake in he following lines of AStarSearchDistance &
AStarSearchPath. Please correct me if i'm wrong!

int minx=getmax(p.x()-1,0);
int maxx=getmin(p.x()+1,BWAPI::Broodwar->mapWidth());
int miny=getmax(p.y()-1,0);
int maxy=getmin(p.y()+1,BWAPI::Broodwar->mapHeight());

for(int x=minx;x<=maxx;x++)
  for(int y=miny;y<=maxy;y++)
  {
    etc.
  }

it should be:

for(int x=minx;x<maxx;x++) //CHANGE
  for(int y=miny;y<maxy;y++) //CHANGE
  {
    etc.
  }

Reasoning:
The map dimensions might be 96x96. Therefore "Broodwar->mapWidth()" = 96.
However, the 96 tile co-ordinates go from 0-95, not 1-96.
The rightmost tile on the map would have co-ords such as (95,0)to (95,95).

using  "x <= maxx" causes the algorithm to include tiles (96,0) to (96,96).
these tiles are outside the maps area and give incorrect results.
Often causing crashes (depending on how the function has been used).

Original comment by Kali...@gmail.com on 20 May 2010 at 3:31

[GoogleCodeExporter]

ah it should be

int minx=getmax(p.x()-1,0);
int maxx=getmin(p.x()+1,BWAPI::Broodwar->mapWidth()-1);
int miny=getmax(p.y()-1,0);
int maxy=getmin(p.y()+1,BWAPI::Broodwar->mapHeight()-1);

bwapi beta 2.7.1 now correctly reports the bottom 4 rows of walkability tiles as
unwalkable (as well as 20 columns in from each side) since those tiles are 
unwalkable
regardless of the actual map data for those tiles.

The low res map data should be true only if all 16 walk tiles are walkable 
because it
is set like so:

    for(int x=0;x<width;x++)
    {
      for(int y=0;y<height;y++)
      {
        MapData::lowResWalkability[x/4][y/4]&=MapData::rawWalkability[x][y];
      }
    }

it uses &=, so if any of the 16 raw walkability tiles is false, 
lowResWalkability for
that tile will be false.

Original comment by lowerlo...@gmail.com on 21 May 2010 at 5:24

[GoogleCodeExporter]

[deleted comment]

[GoogleCodeExporter]

Pathfinding should be fixed as of r148 (with bwapi 2.7.1).

Original comment by lowerlo...@gmail.com on 21 May 2010 at 10:30

[GoogleCodeExporter]

Original comment by lowerlo...@gmail.com on 23 Jul 2010 at 9:58

• Changed state: Fixed