• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
P0jahn

Finding wall point

23 posts in this topic

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

Share this post


Link to post
Share on other sites

[url="http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm"]Bresenham's line algorithm[/url]?

 

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
0

Share this post


Link to post
Share on other sites

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

0

Share this post


Link to post
Share on other sites

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
0

Share this post


Link to post
Share on other sites

The error from the line is still using floats .


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

Share this post


Link to post
Share on other sites

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.

0

Share this post


Link to post
Share on other sites

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?

0

Share this post


Link to post
Share on other sites

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

0

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites

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
0

Share this post


Link to post
Share on other sites


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

Share this post


Link to post
Share on other sites

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
0

Share this post


Link to post
Share on other sites


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.

0

Share this post


Link to post
Share on other sites

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

0

Share this post


Link to post
Share on other sites

 

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.

-2

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites

Hmm ok then, they are all integers then. So get rid of the floats.

 

It also says there are 8 cases to consider as well.

 

 

However, as mentioned above this is only for the first octant. This means there are eight possible cases to consider. The simplest way to extend the same algorithm, if implemented in hardware, is to flip the co-ordinate system on the input and output of the single-octant drawer.

0

Share this post


Link to post
Share on other sites

 

 

 

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.

 

public static boolean solidSpace (int x0, int y0, int x1, int y1)
{
     float dx = Math.abs(x1-x0);
     float dy = Math.abs(y1-y0); 

     float err = dx-dy;

     while (true)
     {

          float e2 = 2*err;
          if (e2 > -dy)
          {
               err -= dy;

          }
          if (e2 < dx)
          {
               err += dx;
          }
     }
}

The code above is from the original post with only the parts relating to floating point numbers left.  Subtracting 2 integers does result in an integer but the result is then placed into a floating point number which will get converted into a floating point number.

 

Rereading what you have said, you asked what in the original code does not use floats and I have shown which parts of the code does use floating points. I think what you meant that floating points are not needed as all the maths involved can be represented with integer maths.

Edited by seedy
0

Share this post


Link to post
Share on other sites

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


This is the comment that started the whole argument between us. I stand by that comment. If you don't know what "integer" means (it's a notion in Math, not programming), you might have misunderstood.
0

Share this post


Link to post
Share on other sites

Using all integers works fine, no floats required. But it did not increase the speed of the function at all. Mather fact, the function is actually fast, taking about 10000-15000 ns to complete.

I thought it was lagging but the issue was not in that function. Thanks for all the help anyway!

0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0