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:

enter image description here

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:

enter image description here

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

I don't understand it looks to be properly working. Whats your problem? — progrenhard, Aug 04 '14 at 17:05

Adrián González · Accepted Answer · 2015-02-09T12:50:47.477

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,

Hello, thank you for reply. Your answer will help me. Now I created a xml file with structure: ... ... In this file I described the neighbors for each node. In the next step parse this xml file to ArrayList map (each node have AraryList with neighbors). A star used Array map to search path. Do you know what i mean? — , Aug 12 '14 at 22:12
Hi @michael, I think I understand the basics of your idea. If you finally decide to use the library for your project, you can implement the `TransitionFunction` as follows: 1) In the constructor, parse the XML file and store the information in a `Map>`. 2) The method `TransitionFunction.successorsOf(Point)`, will only take the information of the successors from the map you generated in 1). It should work pretty efficiently. — Adrián González, Aug 13 '14 at 09:30

score 1 · Answer 2 · edited May 23 '17 at 11:54

if you have enough memory for map you can still use the A* map version

look here this way you avoid graph confusions. Finds better way (not limited to graph nodes) but it is slower and more memory demanding.
Anyway Your issue looks like wrongly associated costs to the nodes

looks like the costs are not defined by physical distance but just node distance in graph instead so two nodes are always more costly then one diagonal no matter how far they really are.

That means it finds path with minimal nodes count not minimal distance but I do not use graph A* so take that in mind. If you can check the node.calculateDistanceBetweenNods() function or make nodes as seamless grid (add empty nodes) to correct this. But without experience with that lib I only speculate ...
Some insights (but I am not familiar with JAVA...)

so at first look you use float for current distances and int for constants which are they compared to. Also all if's are not handling float values !!! for example:
```
if(currentDistX == 0)
```
should be something like this:
```
if(fabs(currentDistX)<=1e-6)
```
and one last thing I do not know if JAVA has the same priority for <= and && or not but I would feel safer with
```
if((currentDistX<=0.0)&&(currentDistY<=0.0))
```
as I burned by this many times before across a lot of compilers.

Hi, thank you for reply time. Function EstimateDistanceToGoal and calculateDistanceBetweenNods body: float dx = goalX - startX; float dy = goalY - startY; float result = (float) (dx*dx)+(dy*dy); — , Aug 06 '14 at 10:30

score 0 · Answer 3 · answered Aug 05 '14 at 12:55

I found a mistake. but, not necessary the only one:

               if(currentDistY == 0)
               {
                   if(currentDistX < 0) <===== here, change to 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) <======= here, change to 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);
                       }
                   }
               }

You can re-think of it. You will find out.

Hi, thank you for reply time. My nodes form a graph, function registerEdges search only 8 neighbors. Sometime nodes dont have connection with other node. Method registerEdges should search all connection for current node and search path should avoid obstacle. — , Aug 06 '14 at 10:24

A star algorithm with image map (android)

3 Answers3