CODEWITHSUNDEEP
javapathshortest
MarsPeople
MarsPeople

Reputation: 1824

How can i find the closest path in matrix that A to any B?

For example:

m_array = new int[6][6];
m_array[0] = new int[]{2, 0, 0, 0, 0, 0};
m_array[1] = new int[]{0, 2, 0, 0, 0, 2};
m_array[2] = new int[]{2, 0, 0, 1, 0, 0};
m_array[3] = new int[]{0, 0, 0, 0, 0, 0};
m_array[4] = new int[]{0, 2, 0, 0, 2, 0};
m_array[5] = new int[]{0, 0, 2, 0, 0, 0};

How can i find the the closest 2 to 1?

i want a function that it return an array path include points of array. For example i will give the "m_array" to my function and it will return to me the nearest 2 for 1, an array path like [2,3][3,4][4,4]

Upvotes: 0

Views: 3445

Answers (5)

SKYFALL26
SKYFALL26

Reputation: 73

Here's my piece of code. Seems way simpler than anything I saw here so decided to post:

public static boolean isWithinRadius(int[] position, int[] centerPosition, int radius) {

        int xCenterPoint = centerPosition[0];
        int yCenterPoint = centerPosition[1];
        int zCenterPoint = centerPosition[2];


        int xPoint = position[0];
        int yPoint = position[1];
        int zPoint = position[2];

        boolean xMatch = (xPoint - radius <= xCenterPoint) && (xPoint >= xCenterPoint - radius);
        boolean yMatch = (yPoint - radius <= yCenterPoint) && (yPoint >= yCenterPoint - radius);
        boolean zMatch = (zPoint - radius <= zCenterPoint) && (zPoint >= zCenterPoint - radius);


        return xMatch && yMatch && zMatch;

    } // public boolean isWithinRadius (int[], int)

This will return true if a position is within the radius of the centerPosition.

  1. centerPosition is the center of the rings. (If you don't need Z value, just put 0 anywhere it is asked for.)
  2. Radius 1 == Ring 1 , Radius 2 == Ring1 & Ring 2. etc. You can scan the radius. Try to build on that. If you are interested, I've wrote an advanced Matrix Class to which you can scan(hash based) and find objects within it. I was just about to write the code that returns an ArrayList of objects found within a radius.

If you wish to find objects only within a specific ring (rather than all objects within a radius) use this code:

public static boolean isWithinRadiusRing(int[] position, int[] centerPosition, int radius) {


        int xCenterPoint = centerPosition[0];
        int yCenterPoint = centerPosition[1];
        int zCenterPoint = centerPosition[2];


        int xPoint = position[0];
        int yPoint = position[1];
        int zPoint = position[2];

        boolean xRingMatch = (xPoint - radius == xCenterPoint) || (xPoint == xCenterPoint - radius);
        boolean yRingMatch = (yPoint - radius == yCenterPoint) || (yPoint == yCenterPoint - radius);
        boolean zRingMatch = (zPoint - radius == zCenterPoint) || (zPoint == zCenterPoint - radius);

        boolean xRadiusMatch = (xPoint - radius <= xCenterPoint) && (xPoint >= xCenterPoint - radius);
        boolean yRadiusMatch = (yPoint - radius <= yCenterPoint) && (yPoint >= yCenterPoint - radius);
        boolean zRadiusMatch = (zPoint - radius <= zCenterPoint) && (zPoint >= zCenterPoint - radius);

        boolean xMatch = xRingMatch && yRadiusMatch && zRadiusMatch;
        boolean yMatch = yRingMatch && xRadiusMatch && zRadiusMatch;
        boolean zMatch = zRingMatch && xRadiusMatch && yRadiusMatch;

        /*
            System.out.println("xRingMatch="+xRingMatch+" yRingMatch="+yRingMatch+" zRingMatch="+zRingMatch);
            System.out.println("xRadiusMatch="+xRadiusMatch+" yRadiusMatch="+yRadiusMatch+" zRadiusMatch="+zRadiusMatch);
            System.out.println("xMatch="+xMatch+" yMatch="+yMatch+" zMatch=" +zMatch);
            System.out.println("return=" + (xMatch || yMatch || zMatch));
        */

        return xMatch || yMatch || zMatch;

    } // public boolean isWithinRadiusRing(int[], int[] , int)

This will return true if the given position is within a given radius ring from centerPosition (radius 1 == ring1, radius 2 == ring 2, etc.)

To find out the Radius Distance between two positions:

        public static int getDistanceRadius(int[] startPosition, int[] endPosition) {

            // The xyz value that streches the most the distance between two positions
            // is the radius value.
            int xDistance = Math.abs(startPosition[0] - endPosition[0]);
            int yDistance = Math.abs(startPosition[1] - endPosition[1]);
            int zDistance = Math.abs(startPosition[2] - endPosition[2]);

            int radius = (xDistance > yDistance ? xDistance : yDistance);        
            radius = (radius > zDistance ? radius : zDistance);

            return radius;

        } // public static int getDistanceRadius(int[], int[])

Upvotes: 0

MarsPeople
MarsPeople

Reputation: 1824

This function splice my matrix array as ring radius.

public static int[][] SpliceMatrix(int orginX, int orginY, int ringRadius, int[][] map){

    int[][] tempMap = new int[ringRadius * 2 + 1][ringRadius * 2 + 1];

    int tempY = -ringRadius;
    for(int i = 0; i < (ringRadius * 2 + 1); i++){
        int tempX = -ringRadius;

        for(int j = 0; j < (ringRadius * 2 + 1); j++){
            try{
                tempMap[i][j] = map[orginY + tempY][orginX + tempX];
            }catch(ArrayIndexOutOfBoundsException e){
                tempMap[i][j] = 1;
            }

            tempX++;
        }

        tempY++;
    }

    return tempMap;
}

I used the A* algoritm in this function:

private static Point findNext2(int orginX, int orginY, int[][] map){

    //Find "2"s
    ArrayList<Point> ends = new ArrayList<Point>();

    for(int i = 0; i < map.length; i++){
        for(int j = 0; j < map[0].length; j++){
            if(map[i][j] == 2){
                ends.add(new Point(j, i));

                map[i][j] = 0;//Clear for A*
            }
        }
    }

    //Find the closest
    if(ends.size() > 0){
        Point p = null;
        int distance = 100;

        for(int i = 0; i < ends.size(); i++){
            int tempDistance = APlus.go(orginX, orginY, ends.get(i).x, ends.get(i).y, map).size();
            System.out.println(tempDistance);
            if(tempDistance != 0 && tempDistance < distance){
                distance = tempDistance;
                p = new Point(ends.get(i).x, ends.get(i).y);
            }

        }

        if(p == null){
            System.out.println("2 is not accesible");

            return null;
        }

        return p;

    }else{
        System.out.println("There is no 2 in ring");

        return null;
    }

}

Then i use

public static void main(String args[]){

    int[][] m_array = new int[6][6];
    m_array[0] = new int[]{1, 1, 0, 0, 2, 0};
    m_array[1] = new int[]{0, 0, 0, 0, 0, 1};
    m_array[2] = new int[]{1, 1, 1, 0, 1, 0};
    m_array[3] = new int[]{1, 0, 1, 0, 1, 0};
    m_array[4] = new int[]{0, 0, 0, 0, 1, 0};
    m_array[5] = new int[]{0, 0, 0, 0, 0, 0};

    int[][] c = SpliceMatrix(2, 2, 2, m_array);//int x, int y, ringRadius, matrix

    Point p = findNext2(3, 3, c);//orginX, orginY, matrix
    System.out.println(p + " is the closest 2");
 }

I hope that was descriptive. I can't using the HTML correctly yet.

Upvotes: 0

Houshang.Karami
Houshang.Karami

Reputation: 291

I prefer quickgraph for find closer points or paths ; So,Please see this link: http://www.codeproject.com/Articles/5603/QuickGraph-A-100-C-graph-library-with-Graphviz-Sup

Upvotes: 0

Mateusz Kowalczyk
Mateusz Kowalczyk

Reputation: 2066

Unsure what you mean as you seem to be asking two different things. I can't really help on the path aspect as you didn't specify much criteria as to how we can move. You also seem to be asking how to find the closest 2 to 1. Although not the most efficient, you could simply traverse the matrix and use Pythagoras' to work out the distance of each 2 to 1 based on the indices. Alternatively, you could traverse the matrix starting from your 1, outwards, in square shapes. This could be faster in that you would stop the second you find a 2, as opposed of having to traverse the whole matrix checking for 2s with the first solution, although first solution is easier to implement and shouldn't make that much difference given that your matrices are small (Both are O(n) I believe, however best case with the second way is that you can find a 2 with the first check whereas you always need to traverse whole matrix when using Pythagoras').

I hope this makes sense.

EDIT AFTER SOME CLARIFICATION: Here is a method that I hope satisfies your requirements. First a class to wrap up the points for easy access.

public class Point {
    private int x, y;
    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public int getX() { return x; }
    public int getY() { return y; }
    public int setX(int x) { this.x = x; }
    public int setY(int y) { this.y = y; }

}

Now the method itself:

public ArrayList<Point> getPath(int[][] matrix) {
    Point closestTwo = getClosestTwo(matrix); // Implement this as you wish
    Point onePosition = getOnePosition(matrix);

    ArrayList<Point> pointList = new ArrayList<Point>();

    Point currentlyOn = onePosition;

    while (currentlyOn.getX() != closestTwo.getX() && currentlyOn.getY() != closestTwo.getY()) {
        currentlyOn = oneStep(currentlyOn, closestTwo);
        pointList.add(currentlyOn);
    }

    return pointList;
}

Here is an example of oneStep method that you can use to get closer. It returns a point which would advance you the most while only doing one step (diagonals take priority).

public Point oneStep(Point from, Point goal) {
    int x = from.getX() - goal.getX();
    int y = from.getY() - goal.getY();
    Point nextStep = new Point (from.getX(), from.getY());

    if (x > 0) {
        nextStep.setX(nextStep.getX() + 1)
    } else if (x < 0) {
        nextStep.setX(nextStep.getX() - 1)
    }

    if (y > 0) {
        nextStep.setY(nextStep.getY() + 1)
    } else if (y < 0) {
        nextStep.setY(nextStep.getY() - 1)
    }

    return nextStep;
}

I believe this should work fine. You should get an ArrayList of Point if you use this. An example of getClosestTwo method could be something like this (using Pythagoras'). Remeber to import java.lang.Math;

public Point getClosestTwo(int[][] matrix) { // Assumes matrix is initialized, non-empty etc.
    int x, y;
    double smallestDistance = matrix.size() * matrix[0].size(); // bigger than possible
    Point onePosition = getOnePosition(matrix);

    for (int i = 0; i < matrix.size(); i++) {
        for (int j = 0; j < matrix[0].size(); j++) {
            double tmp = (double)(Math.abs(i - y) + Math.abs(j - x))
            double distance = Math.sqrt(tmp);
            if (distance < smallestDistance) {
                y = i;
                x = j;
                smallestDistance = distance;
            }
        }
    }

    return new Point(x, y);
}

getOnePosition(int[][] matrix) can be simply implemented like so:

// Return null if no 1 in matrix
public Point getOnePosition(int[][] matrix) {
    for (int i = 0; i < matrix.size(); i++) {
        for (int j = 0; j < matrix[0].size(); j++) {
            if (matrix[i][j] == 1) {
                return new Point(j, i);
            }
        }
    }
    return null;
}

Hope this helped. Remember to check for nulls, write safe code etc. etc. You can probably put this all together. I hope there aren't any typos or errors with this code that you won't be able to fix.

Upvotes: 0

Marko Topolnik
Marko Topolnik

Reputation: 200148

These are the things you leave us guessing:

  • there is only one 1, but many 2's;
  • the path allows diagonal steps;
  • you are looking for the shortest among all paths that connect the 1 with some 2.

My current thinking is that there is a metric that can be defined for the path length between any two points, so the concepts "a 2 with the shortest path to 1" is equivalent to the concept "the 2 closest to the 1". The metric can be defined as the number of "rings" around the central 1 one must cross to get to a 2:

0 0 0
0 1 0
0 0 2  --> the 2 is in the first ring

0 0 0 0 0
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
0 2 0 0 0 --> the 2 is in the second ring.

If all my assumptions are correct, then you need a function that gives all the members of the first ring, the second ring, and so on, and another function that will search a ring for a 2. Then, finally, you need an algorithm to draw a path to the 2. I hope you realize the path is not unique. A trivial algorithm will move diagonally until aligned (either horizontally or vertically) with the 2 and then continue non-diagonally to the target.

Upvotes: 1

Related Questions