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

[George Junglin]

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:

		
int[][] cell = new int[8][10];
int min1, min2, xmax, ymax, a, d; a=1; d=2; min1 = -1; xmax = 8; ymax =10;
		for (int row = 0 ; row < 8 ; row++) 
		{
			for (int col = 0 ; col < 10 ; col++)
			{
				cell[row][col] = 1 ;
				
			}
		}

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]

The goal is the create this..

9 8 7 6 5 4 5 0 0 0
8 7 6 5 4 3 4 5 6 7
0 0 0 0 3 2 3 4 5 6
8 7 6 0 2 1 2 3 4 5
7 6 5 0 1 G 1 0 5 6
6 5 4 3 2 1 2 0 6 7
7 6 5 4 3 2 3 0 7 8
8 7 6 5 4 3 4 8 0 9

G is the goal... 0's represent infinity.

[Winston Gutkowski]

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

[Campbell Ritchie]

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]

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.

[Campbell Ritchie]

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.

[George Junglin]

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...

for (int col = 0 ; x < 10 ; col++) 
  {
	for (int row = 0 ; y < 8 ; row++)
	 {
	    cell[x][y] =  Math.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)
         }
   }

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

[Winston Gutkowski]

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?)

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.

[George Junglin]

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 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?)

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.

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]

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