Jump to content
  • Advertisement
Sign in to follow this  
P0jahn

Finding wall point

This topic is 2075 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

Share this post


Link to post
Share on other sites
Advertisement

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

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

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?

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.

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?

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

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!