A star algorithm with image map (android)

Question

i used algorithm a start to find path with array nods. I have image map and nodes like this:

Red nodes is obstacle, black used to find path. I dont know why this path is to curve. I used this library https://code.google.com/p/a-star-java/source/browse/AStar/src/aStar/?r=7 and I was changed function registerEdges.:

  private void registerEdges(ArrayList<Node> nodes) 
   {
       float currentDistX = 0;
       float currentDistY = 0;
       float distance = 0;

       for(int l = 0 ; l < nodes.size(); l++)
       {
           MINDISTN = Integer.MIN_VALUE;
           MINDISTS = Integer.MAX_VALUE;
           MINDISTE = Integer.MIN_VALUE;
           MINDISTW = Integer.MAX_VALUE;

           MINDISTNE = Integer.MAX_VALUE;
           MINDISTNW = Integer.MAX_VALUE;
           MINDISTSE = Integer.MAX_VALUE;
           MINDISTSW = Integer.MAX_VALUE;

           Node node = null;
           currentDistX = 0;
           currentDistY = 0;

           //System.out.println("current " + node.x + " " + node.y);
           for(int j = 0 ; j < map.size() ; j++)
           {
               if(l != j)
               {
                   node = map.get(l);


                   currentDistX = map.get(j).x - node.x;
                   currentDistY = map.get(j).y - node.y;

                   if(currentDistX == 0)
                   {
                       if(currentDistY < 0)
                       {
                           if(currentDistY > MINDISTN)
                           {
                               MINDISTN = currentDistY;
                               node.setNorth(map.get(j));
                               //System.out.println(currentDist + " n " + map.get(j).x + " " + map.get(j).y);
                           }
                       }
                       else if(currentDistY > 0)
                       {
                           if(currentDistY < MINDISTS)
                           {
                               //System.out.println(currentDist + " south " + map.get(j).x + " " + map.get(j).y);
                               MINDISTS = currentDistY;
                               node.setSouth(map.get(j));
                           }
                       }      
                   }           

                   if(currentDistY == 0)
                   {
                       if(currentDistX < 0)
                       {

                           if(currentDistX > MINDISTE)
                           {
                               MINDISTE = currentDistX;
                               node.setEast(map.get(j));

                               //System.out.println(currentDist + " e " + map.get(j).x + " " + map.get(j).y);
                           }
                       }
                       else if(currentDistX > 0)
                       {
                           //System.out.print("m " + MINDISTRIGHT);
                           if(currentDistX < MINDISTW)
                           {
                               MINDISTW = currentDistX;
                               node.setWest(map.get(j));
                               //System.out.println(currentDist + " w " + map.get(j).x + " " + map.get(j).y);
                           }
                       }
                   }

                   if(currentDistY != 0 && currentDistX != 0)
                   {

                       if(currentDistX > 0 && currentDistY > 0)
                       {
                           distance = node.calculateDistanceBetweenNods(map.get(j));

                           if(distance < MINDISTNE)
                           {
                               MINDISTNE = distance;
                               node.setNorthEast(map.get(j));

                               //System.out.println(currentDist + " e " + map.get(j).x + " " + map.get(j).y);
                           }
                       }
                       else if(currentDistX < 0 && currentDistY > 0)
                       {

                           distance = node.calculateDistanceBetweenNods(map.get(j));

                           if(distance < MINDISTNW)
                           {
                               MINDISTNW = distance;
                               node.setNorthWest(map.get(j));

                               //System.out.println(currentDist + " e " + map.get(j).x + " " + map.get(j).y);
                           }
                       }
                       else if(currentDistX <= 0 && currentDistY <= 0)
                       {

                           distance = node.calculateDistanceBetweenNods(map.get(j));

                           if(distance < MINDISTSW)
                           {
                               MINDISTSW = distance;
                               node.setSouthWest(map.get(j));

                               //System.out.println(currentDist + " e " + map.get(j).x + " " + map.get(j).y);
                           }
                       }
                       else if(currentDistX > 0 && currentDistY < 0)
                       {

                           distance = node.calculateDistanceBetweenNods(map.get(j));

                           if(distance < MINDISTSE)
                           {
                               MINDISTSE = distance;
                               node.setSouthEast(map.get(j));

                               //System.out.println(currentDist + " e " + map.get(j).x + " " + map.get(j).y);
                           }
                       }
                   }
               }
           }
    }

This function looks for North,South,West,East,N-East... neighbor node.
Estimate Path:

public float getEstimatedDistanceToGoal(float startX, float startY, float goalX, float goalY) {         
            float dx = goalX - startX;
            float dy = goalY - startY;

            //float result = (float) (Math.sqrt((dx*dx)+(dy*dy)));

            //Optimization! Changed to distance^2 distance: (but looks more "ugly")

            float result = (float) (dx*dx)+(dy*dy);


            return (float) Math.sqrt(result);
    }

Bad connection current nodes with neighbor nodes.
Example:

Some nodes have one-way connection (image up).
Node 2 have neighbor node 1, node 1 don't have neighbor node 2.

Answer 1

The code you pasted in your answer seems a little bit complicated for a bidimensional path search.

If I understand you well, you intend to search the shortest path in the image in a 8-connected grid, and you are trying to use A* to solve the problem. I recommend you to use a search library which organizes the different components of the search algorithm more clearly.

In the basis, if you have an implementation for A* you only need to define:

• A cost function (which might be the euclidean distance between points, according to your problem description).
• A transition function (which given a Point retrieves you the 8 neighbors, filtering those that are not accesible due to the obstacles in the map image).
• An heuristic function, which you already implemented in getEstimatedDistanceToGoal.

You might take a look to the Hipster library, which in addition to have a more clear structure, has the benefit of generate the nodes of the graph in a dynamic way. This allows you to save a lot of memory, as the majority of the nodes that you are generating a priori will not be used in the search process.

Here you can find an example of code for a 2D search using a maze. The only thing you need to adapt the example to your case is to implement a the TransitionFunction to use your map image. The example uses the following code to generate the neighbor nodes given a current one (function Maze2D.validLocationsFrom(Point)):

public Collection<Point> validLocationsFrom(Point loc) {
   Collection<Point> validMoves = new HashSet<Point>();
   // Check for all valid movements
   for (int row = -1; row <= 1; row++) {
      for (int column = -1; column <= 1; column++) {
         try {
            //
            //TODO: Implement isFree(Point) to check in your map image
            //if a node is occupied or not.
            //
            if (isFree(new Point(loc.x + column, loc.y + row))) {
               validMoves.add(new Point(loc.x + column, loc.y + row));
            }
         } catch (ArrayIndexOutOfBoundsException ex) {
         // Invalid move!
         }
      }
   }
   validMoves.remove(loc);
   return validMoves;
}

In the example the function isFree(Point) queries the maze to know if a node is occupied or not. You only need to fill this function to query your map image instead of the maze, and that's it!

I hope my answer helps,