Help with advanced collision detection

So I'm making a platform game and using an advanced method of collision detection that I'm still learning how to use properly. The first class is the most important one in figuring out whats wrong, as it deals with all the collisions of the main character. The other two classes have code that is related to this one. Such as setting it up. The main issue that I am having is that my main character has a width and height the same as the tiles. 50 by 50px. So when I change playerWidth and playerHeight in collision.as to 25 by 25px respectively, the player seems to teleport downwards when he has an upward collision. But If I alter the variable playerHeight and increase the value from 25 to 30, the collision detection works fine. The player jumps up, hits the top tile, collision which stops the player from moving further upwards, the player falls back downwards to the tile below him due to gravity. Why does changing the height value matter? I've implimented several trace statements to follow the positioning, and other collision.as related values of the player to see what was causing this "teleporting effect" I'm still working on it, and still stuck as to how I can alter this to work properly. //Collision Class

package{
	
	
	public class collisions {
		
		
		private var tileWidth:int;			// game slicing tile's width
		private var tileHeight:int;			// game slicing tile's height
		private var playerWidth:int = 25	// half of real width
		private var playerHeight:int = 25	// half of real height
		private var map;					// map data container
		private var forecast_x:int;			// where the player will be at the end of the frame
		private var forecast_y:int;			
		public var can_jump:Boolean;		// if player can jump
		private var player;					// to store the player object in
		

		public function setup(setWidth,setHeight,setMap,setPlayer) {
			
			tileWidth = setWidth;
			tileHeight = setHeight
			map = setMap;
			player = setPlayer;
		}
//*********************************************************
		


		public function find_corners(point_x,point_y) {				
			// Looks in wich tiles(not pixels) these four point are.
			// Will be used to get the position of the corners and to get the end position of the player.
			player.downy = Math.round((point_y + playerHeight - tileHeight/2) / tileHeight);
			player.upy = Math.round((point_y - playerHeight - tileHeight/2) / tileHeight);
						trace("POINT_Y: " + point_y);
						trace("PLAYER.UPY: " + player.upy);
			player.rightx = Math.round((point_x + playerWidth - tileWidth/2) / tileWidth)
			player.leftx = Math.round((point_x - playerWidth - tileWidth/2) / tileWidth);
			
			// Gets the sort tile the position of the corners has.
			// One means there can be collision, zero is air.
			player.downright = map[player.downy][player.rightx];
			player.upright = map[player.upy][player.rightx];

			if (map[player.downy-1][player.rightx] == 1) player.downright = 1 ; // Because player is higher than tile we also have to check at middle point
			if (map[player.upy+1][player.rightx] == 1) player.upright = 1 ;
			
			player.downleft = map[player.downy][player.leftx];
			player.upleft = map[player.upy][player.leftx];
			
			if (map[player.downy-1][player.leftx] == 1) player.downleft = 1 ;	 // Because player is higher than tile we also have to check at middle point
			if (map[player.upy+1][player.leftx] == 1) player.upleft = 1 ;
		}
//*********************************************************



		public function check_ground() {
			player.downy = Math.round((player.y + (playerHeight+1) - tileHeight/2) / tileHeight);
			player.rightx = Math.round((player.x + playerWidth - tileWidth/2) / tileWidth)
			player.leftx = Math.round((player.x - playerWidth - tileWidth/2) / tileWidth);
			// Makes three points in tile-coordinates
			
			player.downleft = map[player.downy][player.leftx];
			player.downright = map[player.downy][player.rightx];
			// Checks the sort
			
			if(player.downleft == 1 || player.downright ==1){		// if there is any collision by the player's feet
				can_jump = true;									// than can jump
			}
			else{
				can_jump = false;									// else not
			}
		}
//*********************************************************



		public function solve(forecastx, forecasty) {
		// It's four times almost the same. It checks for collision between the spots, 
		// the four spots if there only were x_speeds, the four spots if there only was y_speed, 
		// the four spots if there were both y- and x_speed.	
		// That are 3*4 = 12 spots.
		//
		// var explanation:
		//
		// downC 	-> 	is collision under the spot
		// upC		->	is collision above the spot
		// rightC	->	is collision right from the spot
		// leftC	->	is collision left from the spot
		
			forecast_x = forecastx;
			forecast_y = forecasty;
			
			find_corners(forecast_x,forecast_y);
			
			if(player.downleft == 1) {
				find_corners(player.x,forecast_y);
					if(player.downleft == 1) {					
						player.downC = true;
					}
					else{
						player.downC = false;
					}
				find_corners(forecast_x,player.y);
					if(player.downleft == 1) {					
						player.leftC = true;
					}
					else{
						player.leftC = false;
					}
					if(player.leftC && player.downC) {
						forecast_x = (player.leftx+1) * tileWidth + playerWidth;
						forecast_y = (player.downy+1) * tileHeight - (playerHeight+1);
						player.y_speed = 0;
					}
					else if(player.leftC) {
						forecast_x = (player.leftx+1) * tileWidth + playerWidth;
					}
					else if(player.downC) {
						forecast_y = (player.downy+1) * tileHeight - (playerHeight+1);
						player.y_speed = 0;
					}
			}
			
			find_corners(forecast_x,forecast_y);
			
			if(player.downright == 1) {
				find_corners(player.x,forecast_y);
					if(player.downright == 1){					
						player.downC = true;
					}
					else{
						player.downC = false;
					}
				find_corners(forecast_x,player.y);
					if(player.downright == 1){					
						player.rightC = true;
					}
					else{
						player.rightC = false;
					}
					if(player.rightC && player.downC) {
						forecast_x = player.rightx * tileWidth - (playerWidth+1);
						forecast_y = (player.downy+1) * tileHeight - (playerHeight+1);
						player.y_speed = 0;
					}
					else if(player.rightC) {
						forecast_x = player.rightx * tileWidth - (playerWidth+1);
					}
					else if(player.downC) {
						forecast_y = (player.downy+1) * tileHeight - (playerHeight+1);
						player.y_speed = 0;
					}
			}
			
			find_corners(forecast_x,forecast_y);
			
			if(player.upleft == 1) {
				find_corners(player.x,forecast_y);
					if(player.upleft == 1) {					
						player.upC = true;
					}
					else{
						player.upC = false;
					}
				find_corners(forecast_x,player.y);
					if(player.upleft == 1) {					
						player.leftC = true;
					}
					else{
						player.leftC = false;
					}
					if(player.leftC && player.upC) {
						forecast_x = (player.leftx+1) * tileWidth + playerWidth;
						forecast_y = (player.upy) * tileHeight + playerHeight;
						player.y_speed = 0;
					}
					else if(player.leftC) {
						forecast_x = (player.leftx+1) * tileWidth + playerWidth;
					}
					else if(player.upC) {
						forecast_y = (player.upy) * tileHeight + playerHeight;
						player.y_speed  = 0;
					}
			}
			
			find_corners(forecast_x,forecast_y);
			
			if(player.upright == 1) {
				find_corners(player.x,forecast_y);
					if(player.upright == 1) {					
						player.upC = true;
					}
					else{
						player.upC = false;
					}
				find_corners(forecast_x,player.y);
					if(player.upright == 1){					
						player.leftC = true;
					}
					else{
						player.leftC = false;
					}
					if(player.leftC && player.upC) {
						forecast_x = player.rightx * tileWidth - (playerWidth+1);
						forecast_y = (player.upy) * tileHeight + playerHeight;
						player.y_speed = 0;
					}
					else if(player.leftC) {
						forecast_x = player.rightx * tileWidth - (playerWidth+1);
					}
					else if(player.upC) {
						forecast_y = (player.upy) * tileHeight + playerHeight;
						player.y_speed  = 0;
					}
			}
			
			player.x = forecast_x;		// place the player
			player.y = forecast_y;
			trace("FORECAST_Y: " + forecast_y);
			
			check_ground()		// runs the function to check for ground
		}
//*********************************************************

	}
	
}

//Main Class

package  {
	import flash.display.*;
	import flash.events.*;
	import flash.ui.*;
	import flash.utils.Timer;
	import flashx.textLayout.elements.InlineGraphicElement;
	
	public class SkyEngine extends MovieClip {
		private var player:sky = new sky;
		private var mapHolder:MovieClip = new MovieClip();
		public static var ground_a:Array = new Array();
		
		
		public var tile_width = 50;
		public var tile_height = 50;
		private var forecast_x:int;
		private var forecast_y:int;
		
	//PLAYER MOVEMENTS
		private const gravity = 2;
		private const maxSpd:int = 16;
		
		private const walkSpd:int = 8;
		private const jumpSpd:int = 20;
		
		
		private var left:Boolean;
		private var right:Boolean;
		private var up:Boolean;
		
		public var map:Array = new Array();
		public var map_data:mapData = new mapData;
		public var tiles:Array = new Array();
		public var player_collisions:collisions = new collisions;
		public var jump_trigger = true;
		
		private const startX = 250;
		private const startY = 200;
		
		private var flipped:Boolean = false;
		private var jumpTrigger:Boolean = false;
		private var walkTrigger:Boolean = false;
		
		private var skyRunning:Boolean = false;

		public function SkyEngine() {
			createMap();
			createPlayer();
			stage.addChild(mapHolder);
			stage.addEventListener(KeyboardEvent.KEY_DOWN, kDL);
			stage.addEventListener(KeyboardEvent.KEY_UP, kUL);
			stage.addEventListener(Event.ENTER_FRAME, loop);
			player.width = 50;
			player.height = 50;
			player_collisions.setup(tile_width,tile_height,map,player);
					
		}
		
		public function createMap(){
			map_data.setup();
			map = map_data.map_array;
			mapHolder.x = 0;
			mapHolder.y = 0;
			
			for(var t = 0; t < map.length; t++){
				for(var u = 0; u < map[t].length; u++){
					if(map[t][u] == 1){
						var tile:ground = new ground;
						mapHolder.addChild(tile);
						tile.gotoAndStop(1);
						tile.x = u * 50;
						tile.y = t * 50;
						ground_a.push(tile);
					}
				}
			}
			//map
		}
		
		private function createPlayer(){
			addChild(player);
			player.x = startX;
			player.y = startY;
			player.xSpd = 0;
			player.ySpd = 0;
			jumpTrigger = true;
		}
		
		public function kDL(e:KeyboardEvent):void{
			if(e.keyCode == 37 || e.keyCode == 65){
				left = true;
				
				if(player.currentFrame < 90||player.currentFrame > 105){
					player.gotoAndPlay("RUN");
				}
					
				player.rotationY = 180;
			}
			if(e.keyCode == 38 || e.keyCode == 87){
				up = true;
				jump_trigger = true;
			}
			if(e.keyCode == 39 || e.keyCode == 68){
				right = true;
				
				if(player.currentFrame < 90||player.currentFrame > 105){
					player.gotoAndPlay("RUN");
				}
					
				player.rotationY = 0;
			}
		}
		public function kUL(e:KeyboardEvent):void{
			if(e.keyCode == 37 || e.keyCode == 65){
				left = false;
			}
			if(e.keyCode == 38 || e.keyCode == 87){
				up = false;
			}
			if(e.keyCode == 39 || e.keyCode == 68){
				right = false;
			}
			player.gotoAndPlay(1);
		}
			
		
		public function loop(e:Event){
			updatePlayer();
		}
		
		private function updatePlayer(){
			player.ySpd += gravity;
				if (left == true) {
					player.xSpd = -walkSpd;
				}
				if (right == true) {
					player.xSpd = walkSpd;
				}
				if (up && player_collisions.can_jump) {
					player.ySpd = -jumpSpd;
				}
				if (player.ySpd > maxSpd) {
					player.ySpd = maxSpd;
				}
			forecast_y = player.y + player.ySpd;
			forecast_x = player.x + player.xSpd;
			player_collisions.solve(forecast_x, forecast_y);
			player.xSpd = 0;
				if(player_collisions.can_jump){
					jumpTrigger = true;
				}
		}
		
		
		
		
		
		
		

	}
	
}

// Map Data Class

package{
	
	
	public class mapData {
		
		public var map_array:Array = new Array();
		public function setup(){
						//trace("uberboobage");
						map_array = [
					  [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
					  [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
					  [1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
					  [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
					  [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
					  [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1],
					  [1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
					  [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
					  [1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
					  [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
					  [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
					  [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
					  [1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
					  [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
					  [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
					 ]
			
			
		}
	}
}

delete everything (with the forecasts and stuff) and use the sweep and prune method.

Remember, this is the same as writing a physics collision between 2 shapes, the tiles are just there for the spatial partitioning.

tbh. i didn’t bother to read through all that code but i think what qwerber means is:
check if the hitboxes of two object collide.
if so, use a more specific algorithm on those two objects to check if their pixels collide within the rectangular area between the corners of the two hitboxes.

Not entirely what I mean; You must incorporate the positions of the shapes in the frame right before the two shapes overlap, so you know exactly which direction it came from for accurate collision.

oh yeah of cause, to actually make up for the overlap, so that the two object will in fact never overlap. forgot about that

Craksy! good to see you on these forums friend.
Remember when I couldn’t even properly make a preloader? Look at me now!

Well, I haven’t heard of the sweep and prune method. So I’ve got some more reading and research cut out for me.
But I have seen examples and tuts on collision detection via checking for overlap to get very accurate collision.
Sucks that I have to scrap most of the engine again, but it will be worth it in the end, I’m sure.

Thanks guys!

Is this a good tutorial on what you guys meant by “sweep and prune” ?

It looks somewhat similar to what I was doing.

http://www.playchilla.com/as3-spatial-hash

Originally posted by alecz127:

Is this a good tutorial on what you guys meant by “sweep and prune” ?

It looks somewhat similar to what I was doing.

http://www.playchilla.com/as3-spatial-hash

http://www.gamasutra.com/view/feature/131790/simple_intersection_tests_for_games.php?page=3
http://www.gamedev.net/topic/366781-aabb-vs-aabb-sweep-test-collision/

Thanks a million qwerber!

In the first link the equations are pretty confusing, but if you look at the diagrams, what it basically tells you is that you must find the movement vector and do some geometric math, then find the exact time of collision and move the shape back along the movement vector the amount of time it took to collide.

If you are confused about what I mean by time in this context, just think about frames. Each frame the object moved like 10 pixels and it gives the illusion of moving. In a real world situation an object doesn’t really teleport 20 mm to the left. So if the object in your game moved 20 pixels in the last frame, figure out what fraction of a frame of time it took to collide with the other object if it was moving at a uniform speed.

Dang it I’m so bad at explaining things.

No, that makes perfect sense.

Originally posted by qwerber:

In the first link the equations are pretty confusing, but if you look at the diagrams, what it basically tells you is that you must find the movement vector and do some geometric math, then find the exact time of collision and move the shape back along the movement vector the amount of time it took to collide.

If you are confused about what I mean by time in this context, just think about frames. Each frame the object moved like 10 pixels and it gives the illusion of moving. In a real world situation an object doesn’t really teleport 20 mm to the left. So if the object in your game moved 20 pixels in the last frame, figure out what fraction of a frame of time it took to collide with the other object if it was moving at a uniform speed.

Dang it I’m so bad at explaining things.

Nah nah. That makes perfect sense.

A takes T time (frames) to collide with and overlap B.

So we subtract a fraction of the T (frames) to reel A back right before overlap which gives us the exact time of collision, which gives us perfect collision detection.

Soooooo facinating. o.o

Where frames exist because like you said objects in flash basically teleport every frame whatever movement speed they possess in the direction they are moving.

Hey guys. I understand the math that qwerber was discussing with me to a degree, but I’m really unsure how to format what I’m thinking in my head into AS3, been trying different approachs, different tutorials even.

Heres what I’ve got. What am I doing wrong?
Its a tile based game btw, trying to find a math based collision detection.

This current code is part of my engine, the two functions below are called from my main loop function.

private function updatePlayer(){
	if(gravityB){
		player.ySpd += gravity;
	}
	if (left == true) {
		player.xSpd = -walkSpd;
	}
	if (right == true) {
		player.xSpd = walkSpd;
	}
	if (up) {
		player.ySpd = -jumpSpd;
	}
	if (player.ySpd > maxSpd) {
		player.ySpd = maxSpd;
	}
	player.x += player.xSpd;
	player.xSpd = 0;
	if(playerMoveY){
		player.y += player.ySpd;
	}
}
		
private function updateCollisions(){
	if(gravityB == true){
		player.y += player.ySpd;
	}
	x2 = player.x + player.xSpd;
	x1 = player.x;
			
	y2 = player.y + player.ySpd;
	y1 = player.y;
			
for(var i:int = 0; i<ground_a.length; i++){
				
	var ty:int = ground_a[i].y;
	var positions = ty - y1;
				
	if(ground_a[i].hitTestPoint(x2, y2,true)){
		
		if(y1 <= ground_a[i].y){
			player.y -= positions;
			trace(positions);
		}
	} else {
		//playerMoveY = true;
	}
	if(i >= ground_a.length){
		i = 0;
	}
				
	if(positions <= 4 && positions > 0){
		gravityB = false;
		player.y = y2
						
	} else if(gravityB == false){
							
	}
}

Here, I wrote a quick tutorial on sweep testing, still WIP.
http://www.kongregate.com/forums/4-game-programming/topics/259954-aabb-sweep-test-tutorial

Originally posted by qwerberberber:

Here, I wrote a quick tutorial on sweep testing, still WIP.
http://www.kongregate.com/forums/4-game-programming/topics/259954-aabb-sweep-test-tutorial

thank you!
holy crap. With the timing I almost feel like this was written for me.
Its very in depth and specific, I look forward to implimenting this.
And I look forward to the full work.

I was having trouble because most tutorials or explanations would show diagrams, but no code, or code but no diagrams. And when you mix pictureless code with abbreviated variable names, you get a very confused me.
Or I would find stuff that wasn’t exactly tile based collision detection that used simple math to detect everything quickly and efficiently, and was perfectly written. Thanks a ton buddy!

It’s not complete though, collision with more than one tile is a bit different.

I have to ask, are you the same person?
And I see… thats the issues I’m running into as well. Its difficult for me to figure out how to cycle through all the tiles of my map array without using a for loop.

for loop is fine, you just have to run the collision on the right tiles then use one of the several times returned to displace the object at the end.