Move by still makes my player skip the floor

(azrafe7) #21

Haha… yeah Bre! :stuck_out_tongue_winking_eye: \o/

Listen… this thing should only partially work, but my test is flawed somewhere and I modified it so many times that can’t find where it’s going bad (if you have a testbed I’d like to play with it). Could you try to use it with your setup and see how it behaves?

You should replace your moveBy() calls with moveByBresenham() ones and lower the values of precision (< 10 probably). Also, if it doesn’t work, not even with precision at 1, try increasing your gravity value. As you can see it calls moveBy(), so moveCollideX/Y() should also be called in turn.

/**
 * Moves the Entity by amount specified, using the Bresenham's line algorithm and retaining integer values for its x and y.
 * @param	x			Horizontal offset.
 * @param	y			Vertical offset.
 * @param	solidType	An optional collision type (or array of types) to stop flush against upon collision.
 * @param	precision	Distance between consecutive tests. Higher values are faster but increase the chance of missing collisions.
 */
public function moveByBresenham(x:Number, y:Number, solidType:Object = null, precision:int = 1):void
{
	_moveX += x;
	_moveY += y;
	x = Math.round(_moveX);
	y = Math.round(_moveY);
	_moveX -= x;
	_moveY -= y;
	
	if (solidType) {
		var fromX:int = Math.round(this.x);
		var fromY:int = Math.round(this.y);
		var toX:int = fromX + x;
		var toY:int = fromY + y;
		
		var steep:Boolean = Math.abs(toY - fromY) > Math.abs(toX - fromX);
		
		if (steep) {	// swap x <-> y
			var tmp:int;
			
			tmp = fromX;
			fromX = fromY;
			fromY = tmp;
			
			tmp = toX;
			toX = toY;
			toY = tmp;
		}
		
		var deltaX:int = Math.abs(toX - fromX);
		var deltaY:int = Math.abs(toY - fromY);
		var error:int = deltaX / 2;
		var count:int = -1;
		
		var xStep:int = fromX < toX ? 1 : -1;
		var yStep:int = fromY < toY ? 1 : -1;
		
		while (fromX != toX) {
			if (count == precision || count < 0) {
				if (steep) {
					moveBy(fromY - this.x, fromX - this.y, solidType);
				} else {
					moveBy(fromX - this.x, fromY - this.y, solidType);
				}
				count = 0;
			}
			
			error -= deltaY;
			if (error < 0) {
				fromY += yStep;
				error += deltaX;
			}
			fromX += xStep;
			count++;
		}
		
		// last point
		if (steep) {
			moveBy(fromY - this.x, fromX - this.y, solidType);
		} else {
			moveBy(fromX - this.x, fromY - this.y, solidType);
		}
		
	} else {	// no solidType specified -> just move it
		this.x += x;
		this.y += y;
	}
}
(Abel Toy) #22

Let’s see…

I don’t have a testbed, I just test on my game :stuck_out_tongue:

And… it works!

Unless the speed is too high (I won’t need that…). Also a weird thing that happened is that with a high speed and low framerate, sometimes it’ll go through the one-tile even if they are really higher than the player… so apparently it isn’t taking into account there’s a thing in the middle? Weird.

Still wondering what the correct, predictive algorithm would be… but this works just fine for me!

(azrafe7) #23

Oh… Glad to know it works - didn’t exactly expect that!

How’s performance? Depending on how many entities it has to check against and the precision value it could be quite expensive.

Not sure I get this:

Can you post a screenshot/mockup of that?

About a predictive algorithm… I think it would be possible (under some constraints) to find out the intersection between the colliding hitboxes and react properly based on previous position and dimension of the overlapping area. Main problem is that things can get messy quite fast, since you have to take many things into account (first encountered object, L-shaped grid tiles, etc.). Nonetheless it could be worthy investigating more on the subject.

(Abel Toy) #24

How do physic engines do it?

(azrafe7) #25

You could actually try to use Nape for Continuous Collision Detection, should be pretty fast (although haven’t tried to integrate it in FP).

The only other thing I can point you to is how they did collision for N.

(Abel Toy) #26

I read the article, and if I understood it correctly, they assume the player is smaller than the grid so as to simplify the method. Which in my case wouldn’t work, as that fucker is fat.

I think I’ll just stick with your method! :smiley:

Also, what I meant with that is that, at really high speed:

.       |
        |
        |
x       |
        |
        |

The player (x) would go through this wall (|).

(azrafe7) #27

Then the problem could be with Bresenham inner workings, it skips a pixel when moving diagonally:

.      |x
       |x
       |x
      x|
      x|
      x|
    x  |
    x  |
    x  |

You could try to fatten your wall to work around that.

PS: If that doesn’t work I’d be glad to look further into it.

(Abel Toy) #28

The wall is 16x16. And even at precision 1, that will happen at high speeds.

(azrafe7) #29

Mmmhh… can you try with this?

There’s probably still something missing and getting long and tricky :smirk: , but shouldn’t go through walls.

/**
 * Moves the Entity by the x and y amount specified, using the Bresenham's line algorithm and retaining integer values for its x and y.
 * @param	x			Horizontal offset.
 * @param	y			Vertical offset.
 * @param	solidType	An optional collision type (or array of types) to stop flush against upon collision.
 * @param	precision	Distance between consecutive tests. Higher values are faster but increase the chance of missing collisions.
 */
public function moveByBresenham(x:Number, y:Number, solidType:Object = null, precision:int = 1):void
{
	if (solidType == null) {
		moveBy(x, y);
	} else {
		var fromX:int = Math.round(this.x);
		var fromY:int = Math.round(this.y);
		var toX:int = fromX + x;
		var toY:int = fromY + y;
		
		var steep:Boolean = Math.abs(toY - fromY) > Math.abs(toX - fromX);
		
		if (steep) {	// swap x <-> y
			var tmp:int;
			
			tmp = fromX;
			fromX = fromY;
			fromY = tmp;
			
			tmp = toX;
			toX = toY;
			toY = tmp;
		}
		
		var deltaX:int = Math.abs(toX - fromX);
		var deltaY:int = Math.abs(toY - fromY);
		var error:int = deltaX / 2;
		var count:int = -1;
		
		var xStep:int = fromX < toX ? 1 : -1;
		var yStep:int = fromY < toY ? 1 : -1;
		
		var hitEntity:Entity = null;
		
		while (fromX != toX) {
			if (count == precision && count > 0) {
				if (steep) {
					moveTo(fromY, fromX, solidType, true);
				} else {
					moveTo(fromX, fromY, solidType, true);
				}
				count = 0;
			}
			
			error -= deltaY;
			if (error < 0) {
				fromY += yStep;
				error += deltaX;
			}
			fromX += xStep;
			count++;
		}
		
		// last point
		if (steep) {
			moveTo(fromY, fromX, solidType, true);
		} else {
			moveTo(fromX, fromY, solidType, true);
		}
	}
}
(Abel Toy) #30

YUP YUP YUP!

Works completely as expected, even at really low framerates and really high speeds!

You’re the boss!

(azrafe7) #31

Ha… glad it works! :smiley:

Not so performant as I’d wished, but if it accomplishes its tasks then why not?!?

(Abel Toy) #32

Well I just need that on a single player class, so not much of a trouble…