# Getting to a point on a 2d array, labeling each cell the distance it would take from there.

George Junglin

Greenhorn

Posts: 5

posted 4 years ago

Hello everyone, this is a school assignment and I am dead stuck. First of all we are supposed to create a binary matrix, I did so like this:

Then we create a sort of obstacle.. declaring the obstacles as 0, then changing those obstacles to the max value of an integer (Integer.MAX_VALUE)

After that is done I declare my "goal cell," or where I want to get with a zero, whilst changing all the 1's (safe areas) to xmax*ymax.

They then want us to apply this algorithm to change all the free space cells from their initial values. They call is the "Distance Transform Algorithm"

cell[x,y] = min { cell[x,y] , cell[x-1,y+1] + d , cell[x,y+1] + a , cell[x+1,y+1) + d, cell[x+1,y] + a , cell[x+1,y-1] + d , cell[x,y-1]+ a , cell[x-1,y-1] +d , cell[x-1,y] + a }

Now the goal is to show on each cell, how many steps it would take to get to the 0 cell, keeping the obstacles labelled infinity.. Any idea on how to do this I am completely stuck.

I tried simply making a for loop and doing the algorithm but it is obviously the wrong way to go because my minimum value stays around xmax*ymax -1 .

Thank you!!

Then we create a sort of obstacle.. declaring the obstacles as 0, then changing those obstacles to the max value of an integer (Integer.MAX_VALUE)

After that is done I declare my "goal cell," or where I want to get with a zero, whilst changing all the 1's (safe areas) to xmax*ymax.

They then want us to apply this algorithm to change all the free space cells from their initial values. They call is the "Distance Transform Algorithm"

cell[x,y] = min { cell[x,y] , cell[x-1,y+1] + d , cell[x,y+1] + a , cell[x+1,y+1) + d, cell[x+1,y] + a , cell[x+1,y-1] + d , cell[x,y-1]+ a , cell[x-1,y-1] +d , cell[x-1,y] + a }

Now the goal is to show on each cell, how many steps it would take to get to the 0 cell, keeping the obstacles labelled infinity.. Any idea on how to do this I am completely stuck.

I tried simply making a for loop and doing the algorithm but it is obviously the wrong way to go because my minimum value stays around xmax*ymax -1 .

Thank you!!

George Junglin

Greenhorn

Posts: 5

posted 4 years ago

First: your description is all about numbers and manipulations. My suggestion: back up and tell us

Second: All I can see from your code so far is that you're filling every cell with 1. You haven't supplied any value for min2 or explained why a is set to 1 and d to 2, or what min1 and min2 are used for. Good programs should be easily readable by

I should be able to understand, simply from reading your code, exactly what your program is trying to do - and right now I haven't the faintest idea. It sounds like some sort of 'best path' heuristic, but you haven't explained it well enough. Your "distance transform algorithm" would appear to be some sort of minimum value of a cell and all its surrounding neighbours, but what those 'a's and 'd's are for I have no idea.

It's probably also worth mentioning that

Winston

George Junglin wrote:Then we create a sort of obstacle.. declaring the obstacles as 0, then changing those obstacles to the max value of an integer (Integer.MAX_VALUE)

After that is done I declare my "goal cell," or where I want to get with a zero, whilst changing all the 1's (safe areas) to xmax*ymax.

They then want us to apply this algorithm to change all the free space cells from their initial values. They call is the "Distance Transform Algorithm"

cell[x,y] = min { cell[x,y] , cell[x-1,y+1] + d , cell[x,y+1] + a , cell[x+1,y+1) + d, cell[x+1,y] + a , cell[x+1,y-1] + d , cell[x,y-1]+ a , cell[x-1,y-1] +d , cell[x-1,y] + a }

Now the goal is to show on each cell, how many steps it would take to get to the 0 cell, keeping the obstacles labelled infinity.. Any idea on how to do this I am completely stuck.

I tried simply making a for loop and doing the algorithm but it is obviously the wrong way to go because my minimum value stays around xmax*ymax -1 .

First: your description is all about numbers and manipulations. My suggestion: back up and tell us

*what you're trying to do*...in English. That diagram is a good start, but you also need to understand (and so do we) how your "transforms" are supposed to create the values you've shown.

Second: All I can see from your code so far is that you're filling every cell with 1. You haven't supplied any value for min2 or explained why a is set to 1 and d to 2, or what min1 and min2 are used for. Good programs should be easily readable by

*anyone*, including duffers like me; and that involves using good descriptive names rather than 'a's and 'd's and 'min1's.

I should be able to understand, simply from reading your code, exactly what your program is trying to do - and right now I haven't the faintest idea. It sounds like some sort of 'best path' heuristic, but you haven't explained it well enough. Your "distance transform algorithm" would appear to be some sort of minimum value of a cell and all its surrounding neighbours, but what those 'a's and 'd's are for I have no idea.

It's probably also worth mentioning that

`xmax == cell.length`, and

`ymax == cell[0].length`- at least that's what it looks like; and if you used those values, you could code this for a grid of almost any size.

Winston

"Leadership is nature's way of removing morons from the productive flow" - Dogbert

Articles by Winston can be found here

Campbell Ritchie

Sheriff

Posts: 50277

80

posted 4 years ago

What’s a 2D array? It might be common enough in C/C++, but it doesn’t exist in Java. What you have is an array of arrays, which is better.

George Junglin

Greenhorn

Posts: 5

posted 4 years ago

Yes, array of an array. As to the original reply, that is basically all I was given, to initialize the goal, obstacle, and free cells, then apply that algorithm. I just do not understand it. I ran a couple of for loops applying the algorithm to every cell but it does not give me what I need. Here is the outline.

Step 1: Initialize the obstacle cells using infinity (highest possible integer value), the goal cell using zero (0), and the free space cells using a large value (the product of Xmax and Ymax is safe).

Step 2: The distance increment for the vertical and horizontal neighbors is a = 1 and for the diagonal neighbors is d = 2. The distance value of a free space cell is evaluated by the following formula.

cell[x,y]=min {cell[x,y],cell[x−1,y+1]+d,cell[x,y+1]+a,cell[x+1,y +1]+d,cell[x+1,y]+a,cell[x+1,y

− 1] + d, cell[x, y − 1] + a, cell[x − 1, y − 1] + d, cell[x − 1, y] + a}

Repeat Step 2 until all of the free space cell values are changed from the initial values.

Implementation

You have to implement the following

1. Implement the distance transform algorithm.

Input: A binary matrix Output: A distance transform matrix 2. Calculate the shortest path

Input: A binary matrix, a starting point, and a goal point Output: A list containing the cell index from starting point to goal point.

3. Calculate the shortest path considering additional safety

Input: A binary matrix, a starting point, a goal point and a safety pa- rameter Output: A list containing the cell index from starting point to goal point.

Step 1: Initialize the obstacle cells using infinity (highest possible integer value), the goal cell using zero (0), and the free space cells using a large value (the product of Xmax and Ymax is safe).

Step 2: The distance increment for the vertical and horizontal neighbors is a = 1 and for the diagonal neighbors is d = 2. The distance value of a free space cell is evaluated by the following formula.

cell[x,y]=min {cell[x,y],cell[x−1,y+1]+d,cell[x,y+1]+a,cell[x+1,y +1]+d,cell[x+1,y]+a,cell[x+1,y

− 1] + d, cell[x, y − 1] + a, cell[x − 1, y − 1] + d, cell[x − 1, y] + a}

Repeat Step 2 until all of the free space cell values are changed from the initial values.

Implementation

You have to implement the following

1. Implement the distance transform algorithm.

Input: A binary matrix Output: A distance transform matrix 2. Calculate the shortest path

Input: A binary matrix, a starting point, and a goal point Output: A list containing the cell index from starting point to goal point.

3. Calculate the shortest path considering additional safety

Input: A binary matrix, a starting point, a goal point and a safety pa- rameter Output: A list containing the cell index from starting point to goal point.

Campbell Ritchie

Sheriff

Posts: 50277

80

George Junglin

Greenhorn

Posts: 5

posted 4 years ago

That is the algorithm we are supposed to use on each cell...

I understand the min function only takes two parameters but for understanding sake..

Campbell Ritchie wrote:Welcome to the Ranch

Are you supposed to work out the algorithm for yourself from scratch? Or are you allowed to find it? It should be easy enough to find in an artificial intelligence book (e.g. Russell and Norvig), or on Wikipedia.

That is the algorithm we are supposed to use on each cell...

I understand the min function only takes two parameters but for understanding sake..

posted 4 years ago

Right, and that's why I was saying that

First: That

(a) It should look like?

(b) It should be called?

Second: I suspect that 'a' stands for 'adjacent' and 'd' stands for 'diagonal', and that the algorithm is meant to reflect the number of moves

Third: That algorithm is NOT run on obstacles (you didn't mention that; at least not directly). It's also

Fourth: What about 'rows' and 'columns' instead of 'xmax' and 'ymax'?

Fifth: You could also make your program a lot easier to read by adding a descriptive constant or two, for example:

Sixth: Get out some paper and a pen and work out what happens when you run the algorithm

Does that produce what you want?

If not, what do you think you might need to do?

How will you know when you DO have what you want?

You can't code a problem until you

HIH

Winston

PS: I broke up that enormous line of yours. They make threads very hard to read. Please re-read the UseCodeTags page.

George Junglin wrote:I understand the min function only takes two parameters but for understanding sake.

Right, and that's why I was saying that

*describing the problem*(or in this case, the solution you've been given) is very important.

First: That

`min()`call takes the cell and all its immediate neighbours. Why not make it a method? And if you do, what do you think:

(a) It should look like?

(b) It should be called?

Second: I suspect that 'a' stands for 'adjacent' and 'd' stands for 'diagonal', and that the algorithm is meant to reflect the number of moves

*that only involve 90-degree turns*. So:

__document it__; either at the class level or with a comment on each field.

Third: That algorithm is NOT run on obstacles (you didn't mention that; at least not directly). It's also

*different*if the "centre" cell is on one of the edges of the grid.

Fourth: What about 'rows' and 'columns' instead of 'xmax' and 'ymax'?

Fifth: You could also make your program a lot easier to read by adding a descriptive constant or two, for example:

`private static final int OBSTACLE = Integer.MAX_VALUE;`

...

private final int FREE_CELL_START_VALUE = rows * columns;(Question: Why do you think this value is used?)

...

private final int FREE_CELL_START_VALUE = rows * columns;

Sixth: Get out some paper and a pen and work out what happens when you run the algorithm

__once__on every cell (assuming they're properly initialized).

Does that produce what you want?

If not, what do you think you might need to do?

How will you know when you DO have what you want?

You can't code a problem until you

*understand how it works*. And when you DO write your code, making it easily readable for everybody is a major step to becoming a good programmer, rather than just "someone who writes Java code".

HIH

Winston

PS: I broke up that enormous line of yours. They make threads very hard to read. Please re-read the UseCodeTags page.

*Thoroughly*.

Articles by Winston can be found here

George Junglin

Greenhorn

Posts: 5

posted 4 years ago

I think I have come to a solution thanks to your break down, I was looking at it all wrong.

I appreciate the help and will take your advice about how to lay it out for next time I have a problem

Winston Gutkowski wrote:George Junglin wrote:I understand the min function only takes two parameters but for understanding sake.

Right, and that's why I was saying thatdescribing the problem(or in this case, the solution you've been given) is very important.

First: Thatmin()call takes the cell and all its immediate neighbours. Why not make it a method? And if you do, what do you think:

(a) It should look like?

(b) It should be called?

Second: I suspect that 'a' stands for 'adjacent' and 'd' stands for 'diagonal', and that the algorithm is meant to reflect the number of movesthat only involve 90-degree turns. So:document it; either at the class level or with a comment on each field.

Third: That algorithm is NOT run on obstacles (you didn't mention that; at least not directly). It's alsodifferentif the "centre" cell is on one of the edges of the grid.

Fourth: What about 'rows' and 'columns' instead of 'xmax' and 'ymax'?

Fifth: You could also make your program a lot easier to read by adding a descriptive constant or two, for example:

private static final int OBSTACLE = Integer.MAX_VALUE;(Question: Why do you think this value is used?)

...

private final int FREE_CELL_START_VALUE = rows * columns;

Sixth: Get out some paper and a pen and work out what happens when you run the algorithmonceon every cell (assuming they're properly initialized).

Does that produce what you want?

If not, what do you think you might need to do?

How will you know when you DO have what you want?

You can't code a problem until youunderstand how it works. And when you DO write your code, making it easily readable for everybody is a major step to becoming a good programmer, rather than just "someone who writes Java code".

HIH

Winston

PS: I broke up that enormous line of yours. They make threads very hard to read. Please re-read the UseCodeTags page.Thoroughly.

I think I have come to a solution thanks to your break down, I was looking at it all wrong.

I appreciate the help and will take your advice about how to lay it out for next time I have a problem

posted 4 years ago

No probs. Good luck. And welcome to JavaRanch.

Winston

George Junglin wrote:I think I have come to a solution thanks to your break down, I was looking at it all wrong.

I appreciate the help and will take your advice about how to lay it out for next time I have a problem

No probs. Good luck. And welcome to JavaRanch.

Winston

Articles by Winston can be found here