Jump to content

  • Log In with Google      Sign In   
  • Create Account

Finding wall point


Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.


  • You cannot reply to this topic
23 replies to this topic

#1   Members   -  Reputation: 305

Like
0Likes
Like

Posted 05 November 2013 - 02:33 PM

The world in my game is represented with a two dimensional array: byte[stage_height][stage_width].

If the byte is 0, the pixel is solid space, if it is 1, its hollow. 

 

So I have a game object called A, and is placed somewhere in my world. I want to iterate from A to an other point and see if there is solid space between these two points. 

 

I already have a function that does this, but the performance of that method is awful. Is there anything faster around here? Super-precision is not required.

 

Here is my function if anyone is interested:

public static boolean solidSpace (int x0, int y0, int x1, int y1)
{
     float dx = Math.abs(x1-x0);
     float dy = Math.abs(y1-y0); 
     int sx = (x0 < x1) ? 1 : -1;
     int sy = (y0 < y1) ? 1 : -1;
     float err = dx-dy;
     byte[][] b = Stage.STAGE.stageData;
 
     while (true)
     {
          if (b[y0][x0] == SOLID)
               return false;
 
          if (x0 == x1 && y0 == y1) 
               return true;
 
          float e2 = 2*err;
          if (e2 > -dy)
          {
               err -= dy;
               x0 += sx;
          }
          if (e2 < dx)
          {
               err += dx;
               y0 += sy;
          }
     }
}


#2   Crossbones+   -  Reputation: 19669

Like
0Likes
Like

Posted 05 November 2013 - 02:39 PM

Bresenham's line algorithm?

 

EDIT: It's basically what you are doing. So no, I don't think there is something much faster you could do, other than minor optimizations.


Edited by Álvaro, 05 November 2013 - 02:41 PM.


#3   Members   -  Reputation: 305

Like
0Likes
Like

Posted 05 November 2013 - 02:45 PM

Would it be possible to jump more than one step each iteration(in the function posted above)?



#4   Crossbones+   -  Reputation: 19669

Like
0Likes
Like

Posted 05 November 2013 - 02:46 PM

Your problem might be in that you seem to be using Java. Try implementing this in C and compare speeds.



#5   Crossbones+   -  Reputation: 19669

Like
1Likes
Like

Posted 05 November 2013 - 02:47 PM

Also, why are you using `float' at all? All your numbers are integers...



#6   Members   -  Reputation: 122

Like
0Likes
Like

Posted 05 November 2013 - 03:45 PM

Also, why are you using `float' at all? All your numbers are integers...

 The error from the line is still using floats .

 

 Another approach  is considering floating point maths ( pseudo code)


float dx = x1-x0;
float dy = y1-y0;
float max_side = MAX(FABS(dx),FABS(dy)); // length of the longest side
if(max_side == 0)
{
	if (b[y0][x0] == SOLID)
        	return false;
	else
		return true;
}

dx /= max_side;
dy /= max side;
// Normalised stepping
do
{
	if (b[y0][x0] == SOLID)
        	return false;
	if(max_side == 0)
	 	return true;
	max_side--;
	y0 += dy;
	x0 += dx;
}
  
















Edited by seedy, 05 November 2013 - 03:48 PM.


#7   Crossbones+   -  Reputation: 19669

Like
0Likes
Like

Posted 06 November 2013 - 01:51 AM

The error from the line is still using floats .


What operation in the original code produces something that is not an integer?

#8   Members   -  Reputation: 305

Like
0Likes
Like

Posted 06 November 2013 - 08:37 AM

seedy: I think that code works better. 

How could I modify it, so it continues until it finds solid space? I tried by removing the "return false" checks but it did not work.



#9   Members   -  Reputation: 897

Like
0Likes
Like

Posted 06 November 2013 - 05:34 PM

Is "A" going to be moving very far each frame? You could limit the number of iterations to only as far as "A" can move at any given frame. Another way is to reduce the resolution of the SPACE/SOLID blocks (this will depend on what your game should look like).

 

By the way, can you give a screen shot so I can get an idea of what your game looks like?



#10   Crossbones+   -  Reputation: 4972

Like
0Likes
Like

Posted 07 November 2013 - 01:02 AM

For large traces, dense matrix representations won't do it. You'll need a hierarchical approach involving a quadtree or at least a sparse structure.

I have no real idea what you're doing here, but the pixel step cannot just be +1 or -1: almost horizontal (or vertical) traces will have an increment close to 0 in the corresponding coordinate.

Using float is definitely required, but I'm inclined to believe you're not doing it correctly.

 

Also, define "the performance of that method is awful".


Previously "Krohm"


#11   Crossbones+   -  Reputation: 19669

Like
0Likes
Like

Posted 07 November 2013 - 03:42 AM

Using float is definitely required


Line algorithms have been around for a long time, when floating-point operations were prohibitively expensive. Go ahead and read the link I posted to Bresenham's line algorithm.

#12   Crossbones+   -  Reputation: 2590

Like
0Likes
Like

Posted 07 November 2013 - 04:07 AM

As many have already pointed out, Bresenham's line algorithm specifically avoids using floats. I'm no Java expert, but I believe floats are quite slow in Java.

 

I've commented things in your code that could be improved.

public static boolean solidSpace (int x0, int y0, int x1, int y1)
{
     float dx = Math.abs(x1-x0);    // why make these floats? The two input arguments are integers, so the result can be an integer too
     float dy = Math.abs(y1-y0);   // <-----
     int sx = (x0 < x1) ? 1 : -1;
     int sy = (y0 < y1) ? 1 : -1;
     float err = dx-dy;                    // dx and dy should be integers, so err can also be an integer
     byte[][] b = Stage.STAGE.stageData;   // This could be expensive, copying a two dimensional array from one place to another. Consider using the original array directly
 
     while (true)
     {
          if (b[y0][x0] == SOLID)
               return false;
 
          if (x0 == x1 && y0 == y1) 
               return true;
 
          float e2 = 2*err;
          if (e2 > -dy)
          {
               err -= dy;
               x0 += sx;
          }
          if (e2 < dx)
          {
               err += dx;
               y0 += sy;
          }
     }
}

And here's how I'd write it.

public static boolean solidSpace (int x0, int y0, int x1, int y1)
{
     int dx = Math.abs(x1-x0);
     int dy = Math.abs(y1-y0); 
     int sx = (x0 < x1) ? 1 : -1;
     int sy = (y0 < y1) ? 1 : -1;
     int err = dx-dy;
 
     while (true)
     {
          if (Stage.STAGE.stageData[y0][x0] == SOLID)
               return false;
 
          if (x0 == x1 && y0 == y1) 
               return true;
 
          float e2 = 2*err;
          if (e2 > -dy)
          {
               err -= dy;
               x0 += sx;
          }
          if (e2 < dx)
          {
               err += dx;
               y0 += sy;
          }
     }
}

How large is your array (stage_width and stage_height), and how many line checks are you performing every game loop? I have a feeling there may be some inefficiency in the way you're using the method as well.


Edited by TheComet, 07 November 2013 - 04:09 AM.

"Windows 10 doesn't only include spyware, it is designed as spyware" -- Gaius Publius, The Big Picture RT Interview

"[...] we will access, disclose and preserve personal data, including your content (such as the content of your emails, other private communications or files in private folders), when we have a good faith belief that doing so is necessary" -- Windows 10 Privacy Statement


#13   Crossbones+   -  Reputation: 4972

Like
-2Likes
Like

Posted 07 November 2013 - 07:25 AM


Line algorithms have been around for a long time, when floating-point operations were prohibitively expensive. Go ahead and read the link I posted to Bresenham's line algorithm
I will state it again. I would use floats.

Previously "Krohm"


#14   Crossbones+   -  Reputation: 8704

Like
0Likes
Like

Posted 07 November 2013 - 08:20 AM

Hm... I don't see why e2 has to be a float. err is an integer, and surely err * 2 will still be an integer.

 

You can try to mark all your constants and remove some redundant operations, sometimes it helps a bit (after all, it isn't something the JVM can't do on its own). You'll have to test it though.

public static boolean solidSpace ( int x0, int y0, final int x1, final int y1) // Some parameters are constant.
{
    final int dx = Math.abs(x1-x0); // Constant
    final int minusDy = -Math.abs(y1-y0); // Looks to me from what you're doing that you need -dy
                                         // stored instead of just dy and negating it all the time.
 
    final int sx = (x0 < x1) ? 1 : -1; // Constant
    final int sy = (y0 < y1) ? 1 : -1; // Constant
    int err = dx+minusDy; // Changed the op from -dy to +minusDy.
 
    final byte[][] stageData = Stage.STAGE.stageData; // Constant reference to stageData.
    
    while ( x0 != x1 || y0 != y1 ) // Boolean algebra! Yay!
    {
         if ( stageData[y0][x0] == SOLID ) // I'd put the braces anyway. Code style thing.
              return false; // I don't get why "solidSpace()" returns false if it is solid
                            // but it's your code so it returns false. :D
 
         final int e2 = 2*err; // Constant for the scope of the loop iteration. If err is integer, 2 * err will be integer.
         
         if ( e2 > minusDy ) // Removed the -dy for minusDy.
         {
              err += minusDy; // Adding minusDy instead of substracting dy.
              x0 += sx;
         }
         
         if ( e2 < dx )
         {
              err += dx;
              y0 += sy;
         }
    }
    return true; // The 'true' return is here now.

}

BTW TheComet, final byte[][] stageData = Stage.STAGE.stageData isn't copying the array. Java works with references for everything that isn't a primitive type (that means arrays are references too).

 

Holding the constant reference in the method's scope *might* help the JVM if it's making any null check, it will do nothing otherwise.


Edited by TheChubu, 07 November 2013 - 08:34 AM.

"I AM ZE EMPRAH OPENGL 3.3 THE CORE, I DEMAND FROM THEE ZE SHADERZ AND MATRIXEZ"

 

My journals: dustArtemis ECS framework and Making a Terrain Generator


#15   Crossbones+   -  Reputation: 2590

Like
0Likes
Like

Posted 07 November 2013 - 08:59 AM


BTW TheComet, final byte[][] stageData = Stage.STAGE.stageData isn't copying the array. Java works with references for everything that isn't a primitive type (that means arrays are references too).

Ah, that's cool, I didn't know that.


"Windows 10 doesn't only include spyware, it is designed as spyware" -- Gaius Publius, The Big Picture RT Interview

"[...] we will access, disclose and preserve personal data, including your content (such as the content of your emails, other private communications or files in private folders), when we have a good faith belief that doing so is necessary" -- Windows 10 Privacy Statement


#16   Members   -  Reputation: 122

Like
0Likes
Like

Posted 07 November 2013 - 04:17 PM

seedy: I think that code works better. 

How could I modify it, so it continues until it finds solid space? I tried by removing the "return false" checks but it did not work.

	if(max_side == 0)
	 	return true;
	max_side--;

The do loop is controlled by the length of the line. You could check to see if the line went outside of your array x0 < 0 or x0 >= map_width ( C++ programmer another languages might start at 1 to map_width) and also the same for y0. Else you might want to check Z units past the end of the line - just add Z to max_side before starting the loop



#17   Members   -  Reputation: 122

Like
-2Likes
Like

Posted 07 November 2013 - 04:20 PM

 

The error from the line is still using floats .


What operation in the original code produces something that is not an integer?

 

 If you read the code which was originally posted you would have see the use of floats and not have asked.



#18   Crossbones+   -  Reputation: 19669

Like
0Likes
Like

Posted 07 November 2013 - 09:16 PM

The error from the line is still using floats .


What operation in the original code produces something that is not an integer?

 If you read the code which was originally posted you would have see the use of floats and not have asked.

I am rather confused. Are you saying that the code mutated? The code in the first post (which doesn't seem to have been altered) uses the type `float' but none of the operations can possibly result in a value that doesn't represent an integer. If you disagree with this, please explain what operation produces something that is not an integer.

#19   Crossbones+   -  Reputation: 5832

Like
0Likes
Like

Posted 07 November 2013 - 09:28 PM

I the original code correct?

 

Should it be dx / dy instead of dx - dy?


"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley

#20   Crossbones+   -  Reputation: 8704

Like
0Likes
Like

Posted 08 November 2013 - 05:06 AM

Look at the Wikipedia link http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm

 

OP seems to have taken it almost verbatim from the last one in there (under the "Simplification" title). Which also explains the "while (true)" block, since that Wiki pseudocode doesn't has conditionals in the loop either.


"I AM ZE EMPRAH OPENGL 3.3 THE CORE, I DEMAND FROM THEE ZE SHADERZ AND MATRIXEZ"

 

My journals: dustArtemis ECS framework and Making a Terrain Generator





Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.




PARTNERS