CODEWITHSUNDEEP
javapath-finding
stonedvolk
stonedvolk

Reputation: 31

Shortest path problem inside a grid structure

I'm working on a basic program where 2 players on a 2D board of size 30x30 have to reach a smaller grid of size A*A (let's call it rug) somewhere on the 2D board. I need to calculate which of the players is closer to the rug. I know how to calculate the distance to the top left corner of the rug (as i use x and y coordinates to draw it), but don't know how to calculate the distance to the nearest point of the rug, which could also e.g be the middle of the bottom of the rug.

Upvotes: 0

Views: 186

Answers (1)

aman.zip
aman.zip

Reputation: 71

This is more of an algorithms question than java. Could you clarify the information we have about the rug? Do we have the rug's coordinates? Do we have the player's coordinates?

Assuming you had the coordinates of the corners of a square A*A rug, you could simply compute which player has a shorter Euclidean distance to the rug corners, or its sides. This can be done by creating a list of coordinates the rug owns.

Bear in mind this is psuedo code, please do not just copy the code into your IDE and be upset it didn't pass your tests.

So again the steps are:

  1. Create a list of square rug's coordinates
  2. Add corners to that list
  3. Compute the points along the sides of the rug to be added to the list
  4. Compare the minimum euclidean distance between the players and ALL coordinates in the list. The lower distance is closest.

Let's suppose you had a unit square rug with corners at (1,1), (-1,1), (-1,-1), (1,-1).

    ArrayList<String> rugCoordinates = new ArrayList<String>();
    //first add all corners
    rugCoordinates.add("(1,1)");
    rugCoordinates.add("(-1,1)");
    rugCoordinates.add("(-1,-1)");
    rugCoordinates.add("(1,-1)");

Now you need to add the points along the line to the list. You can get the slope between the points via rise/run for example, between (-1,1) and (1,1) = 0 slope.

    slope = (yCoordTarget-yCoordSource)/(xCoordTarget-xCoordSource);
    for(int i = xCoordSource; i < xCoordTarget, i++){
        rugCoordinates.add(i, i+slope);
    }

Finally compare the min distances of players.

    if (findMinEuclideanDistance(player1) < findMinEuclideanDistance(player2)){
        return player1;
    else{
        return player2;
    }

Upvotes: 2

Related Questions