Jump to content

  • Log In with Google      Sign In   
  • Create Account

FREE SOFTWARE GIVEAWAY

We have 4 x Pro Licences (valued at $59 each) for 2d modular animation software Spriter to give away in this Thursday's GDNet Direct email newsletter.


Read more in this forum topic or make sure you're signed up (from the right-hand sidebar on the homepage) and read Thursday's newsletter to get in the running!


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 P0jahn   Members   -  Reputation: 272

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;
          }
     }
}


Sponsor:

#2 Álvaro   Crossbones+   -  Reputation: 13928

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 P0jahn   Members   -  Reputation: 272

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 Álvaro   Crossbones+   -  Reputation: 13928

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 Álvaro   Crossbones+   -  Reputation: 13928

Like
1Likes
Like

Posted 05 November 2013 - 02:47 PM

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



#6 seedy   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 Álvaro   Crossbones+   -  Reputation: 13928

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 P0jahn   Members   -  Reputation: 272

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 Hawkblood   Members   -  Reputation: 725

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 Krohm   Crossbones+   -  Reputation: 3257

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



#11 Álvaro   Crossbones+   -  Reputation: 13928

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 TheComet   Crossbones+   -  Reputation: 1644

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.

YOUR_OPINION >/dev/null

#13 Krohm   Crossbones+   -  Reputation: 3257

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.

#14 TheChubu   Crossbones+   -  Reputation: 4782

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 TheComet   Crossbones+   -  Reputation: 1644

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.


YOUR_OPINION >/dev/null

#16 seedy   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 seedy   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 Álvaro   Crossbones+   -  Reputation: 13928

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 Paradigm Shifter   Crossbones+   -  Reputation: 5438

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 TheChubu   Crossbones+   -  Reputation: 4782

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