From PNG to Box2D – first attempt

If you followed the posts using marching squares algorithm to trace the contour of an image and reduce the number of points in a polygon with the Ramer-Douglas-Peucker algorithm you probably imagined where I wanted to go… I am going to use Antoan Angelov’s b2Separator class to convert any PNG image to a Box2D body, assuming the PNG has transparency.

Look at the example:

On the left, the original image with the contour traced by marching squares, on the right, the same contour optimized with Ramer-Douglas-Peucker algorithm, and on the bottom the static Box2D body made with b2Separator class using 1/10 of the total vertices to save fixtures.

It’s just an attempt and can be fairly optimized, but it starts to work pretty well.

This is the code, which is just a mix of the codes you can find in the Ramer-Douglas-Peucker algorithm and b2Separator class examples.

package {
	import flash.display.Sprite;
	import flash.display.BitmapData;
	import flash.display.Bitmap;
	import flash.geom.Matrix;
	import flash.geom.Point;
	import flash.events.Event;
	import Box2D.Collision.Shapes.*;
	import Box2D.Common.Math.*;
	import Box2D.Dynamics.*;
	import Box2DSeparator.*;
	public class Main extends Sprite {
		private var bitmapData:BitmapData=new BitmapData(640,480,true,0x00000000);
		// tolerance is the amount of alpha for a pixel to be considered solid
		private var tolerance:Number=0x01;
		var world:b2World, bodyDef:b2BodyDef, body:b2Body, fixtureDef:b2FixtureDef, polyShape:b2PolygonShape, worldCont:Sprite = new Sprite();
		public function Main() {
			// adding a png image with transparency
			bitmapData.draw(new Logo(300,225),new Matrix(1,0,0,1,10,10));
			var bitmap:Bitmap=new Bitmap(bitmapData);
			addChild(bitmap);
			bitmap.alpha=0.5;
			// at the end of this function, marchingVector will contain the points tracing the contour
			var marchingVector:Vector.<Point>=marchingSquares(bitmapData);
			marchingVector=RDP(marchingVector,0.2);
			var canvas:Sprite=new Sprite();
			addChild(canvas);
			canvas.graphics.moveTo(marchingVector[0].x+320,marchingVector[0].y);
			for (var i:Number=0; i<marchingVector.length; i++) {
				canvas.graphics.lineStyle(2,0xffffff);
				canvas.graphics.lineTo(marchingVector[i].x+320,marchingVector[i].y);
				canvas.graphics.lineStyle(1,0xff0000);
				canvas.graphics.drawCircle(marchingVector[i].x+320,marchingVector[i].y, 2);
			}
			canvas.graphics.lineStyle(2,0xffffff);
			canvas.graphics.lineTo(marchingVector[0].x+320,marchingVector[0].y);
			// Box2D's turn;
			world=new b2World(new b2Vec2(0,10),true);
			debug_draw();
			addChild(worldCont);

			// Here we create the non-convex polygon! We do it in 5 steps.

			// 1) We create a b2Separator instance.
			var sep:b2Separator = new b2Separator();

			// 2) Then we create a b2Body instance. This is where the fixtures of the non-polygon shape will be stored.
			bodyDef = new b2BodyDef();
			bodyDef.position.Set(160/30,240/30);
			body=world.CreateBody(bodyDef);

			// 3) We also need a b2FixtureDef instance, so that the new fixtures can inherit its properties.
			fixtureDef = new b2FixtureDef();
			fixtureDef.restitution=0.4;
			fixtureDef.friction=0.2;
			fixtureDef.density=4;

			// 4) And what is of most importance - we need a Vector of b2Vec2 instances so that we can pass the vertices! 
			// Remember, we need the vertices in clockwise order! For more information, read the documentation for the b2Separator.Separate() method.
			// Notice how I am reversing the Vector
			var vec:Vector.<b2Vec2> = new Vector.<b2Vec2>();
			for (i=marchingVector.length-1; i>=0; i--) {
				// reducing a bit the polys
				if (i%10==0) {
					vec.push(new b2Vec2(marchingVector[i].x/30,marchingVector[i].y/30));
				}
			}
			//vec.push(new b2Vec2(-100/30, -100/30), new b2Vec2(100/30, -100/30), new b2Vec2(100/30, 0), new b2Vec2(0, 0), new b2Vec2(-100/30, 100/30));

			// If you want to be sure that the vertices are entered correctly, use the b2Separator.Validate() method!
			// Refer to the documentation of b2Separate.Validate() to see what it does and the values it returns.
			if (sep.Validate(vec)==0) {
				trace("Yey! Those vertices are good to go! ("+sep.Validate(vec)+")");
				sep.Separate(body, fixtureDef, vec);
			}
			else {
				trace("Oh, I guess you messed something up :( ("+sep.Validate(vec)+")");
			}

			// 5) And finally, we pass the b2Body, b2FixtureDef and Vector.<b2Vec2> instances as parameters to the Separate() method!
			// It separates the non-convex shape into convex shapes, creates the fixtures and adds them to the body for us! Sweet, eh?
			//trace(sep.Validate(vec));
			//sep.Separate(body, fixtureDef, vec);

			// Assigning an event listener, which allows us to call update() every frame.
			stage.addEventListener(Event.ENTER_FRAME, update);

		}

		public function RDP(v:Vector.<Point>,epsilon:Number):Vector.<Point> {
			var firstPoint:Point=v[0];
			var lastPoint:Point=v[v.length-1];
			if (v.length<3) {
				return v;
			}
			var index:Number=-1;
			var dist:Number=0;
			for (var i:Number=1; i<v.length-1; i++) {
				var cDist:Number=findPerpendicularDistance(v[i],firstPoint,lastPoint);
				if (cDist>dist) {
					dist=cDist;
					index=i;
				}
			}
			if (dist>epsilon) {
				var l1:Vector.<Point>=v.slice(0,index+1);
				var l2:Vector.<Point>=v.slice(index);
				var r1=RDP(l1,epsilon);
				var r2=RDP(l2,epsilon);
				var rs:Vector.<Point>=r1.slice(0,r1.length-1).concat(r2);
				return rs;
			}
			else {
				return new Vector.<Point>(firstPoint,lastPoint);
			}
			return null;
		}

		private function findPerpendicularDistance(p:Point, p1:Point,p2:Point) {
			var result;
			var slope;
			var intercept;
			if (p1.x==p2.x) {
				result=Math.abs(p.x-p1.x);
			}
			else {
				slope = (p2.y - p1.y) / (p2.x - p1.x);
				intercept=p1.y-(slope*p1.x);
				result = Math.abs(slope * p.x - p.y + intercept) / Math.sqrt(Math.pow(slope, 2) + 1);
			}
			return result;
		}

		public function marchingSquares(bitmapData:BitmapData):Vector.<Point> {
			var contourVector:Vector.<Point> = new Vector.<Point>();
			// this is the canvas we'll use to draw the contour
			var canvas:Sprite=new Sprite();
			addChild(canvas);
			canvas.graphics.lineStyle(2,0x00ff00);
			// getting the starting pixel;
			var startPoint:Point=getStartingPixel(bitmapData);
			// if we found a starting pixel we can begin
			if (startPoint!=null) {
				// moving the graphic pen to the starting pixel
				canvas.graphics.moveTo(startPoint.x,startPoint.y);
				// pX and pY are the coordinates of the starting point;
				var pX:Number=startPoint.x;
				var pY:Number=startPoint.y;
				// stepX and stepY can be -1, 0 or 1 and represent the step in pixels to reach
				// next contour point
				var stepX:Number;
				var stepY:Number;
				// we also need to save the previous step, that's why we use prevX and prevY
				var prevX:Number;
				var prevY:Number;
				// closedLoop will be true once we traced the full contour
				var closedLoop:Boolean=false;
				while (!closedLoop) {
					// the core of the script is getting the 2x2 square value of each pixel
					var squareValue:Number=getSquareValue(pX,pY);
					switch (squareValue) {
							/* going UP with these cases:
							
							+---+---+   +---+---+   +---+---+
							| 1 |   |   | 1 |   |   | 1 |   |
							+---+---+   +---+---+   +---+---+
							|   |   |   | 4 |   |   | 4 | 8 |
							+---+---+   +---+---+  +---+---+
							
							*/
						case 1 :
						case 5 :
						case 13 :
							stepX=0;
							stepY=-1;
							break;
							/* going DOWN with these cases:
							
							+---+---+   +---+---+   +---+---+
							|   |   |   |   | 2 |   | 1 | 2 |
							+---+---+   +---+---+   +---+---+
							|   | 8 |   |   | 8 |   |   | 8 |
							+---+---+   +---+---+  +---+---+
							
							*/
						case 8 :
						case 10 :
						case 11 :
							stepX=0;
							stepY=1;
							break;
							/* going LEFT with these cases:
							
							+---+---+   +---+---+   +---+---+
							|   |   |   |   |   |   |   | 2 |
							+---+---+   +---+---+   +---+---+
							| 4 |   |   | 4 | 8 |   | 4 | 8 |
							+---+---+   +---+---+  +---+---+
							
							*/
						case 4 :
						case 12 :
						case 14 :
							stepX=-1;
							stepY=0;
							break;
							/* going RIGHT with these cases:
							
							+---+---+   +---+---+   +---+---+
							|   | 2 |   | 1 | 2 |   | 1 | 2 |
							+---+---+   +---+---+   +---+---+
							|   |   |   |   |   |   | 4 |   |
							+---+---+   +---+---+  +---+---+
							
							*/
						case 2 :
						case 3 :
						case 7 :
							stepX=1;
							stepY=0;
							break;
						case 6 :
							/* special saddle point case 1:
							
							+---+---+ 
							|   | 2 | 
							+---+---+
							| 4 |   |
							+---+---+
							
							going LEFT if coming from UP
							else going RIGHT 
							
							*/
							if (prevX==0&&prevY==-1) {
								stepX=-1;
								stepY=0;
							}
							else {
								stepX=1;
								stepY=0;
							}
							break;
						case 9 :
							/* special saddle point case 2:
							
							+---+---+ 
							| 1 |   | 
							+---+---+
							|   | 8 |
							+---+---+
							
							going UP if coming from RIGHT
							else going DOWN 
							
							*/
							if (prevX==1&&prevY==0) {
								stepX=0;
								stepY=-1;
							}
							else {
								stepX=0;
								stepY=1;
							}
							break;
					}
					// moving onto next point
					pX+=stepX;
					pY+=stepY;
					// saving contour point
					contourVector.push(new Point(pX, pY));
					prevX=stepX;
					prevY=stepY;
					//  drawing the line
					canvas.graphics.lineTo(pX,pY);
					// if we returned to the first point visited, the loop has finished;
					if (pX==startPoint.x&&pY==startPoint.y) {
						closedLoop=true;
					}
				}
			}
			return contourVector;
		}

		private function getStartingPixel(bitmapData:BitmapData):Point {
			// finding the starting pixel is a matter of brute force, we need to scan
			// the image pixel by pixel until we find a non-transparent pixel
			var zeroPoint:Point=new Point(0,0);
			var offsetPoint:Point=new Point(0,0);
			for (var i:Number=0; i<bitmapData.height; i++) {
				for (var j:Number=0; j<bitmapData.width; j++) {
					offsetPoint.x=j;
					offsetPoint.y=i;
					if (bitmapData.hitTest(zeroPoint,tolerance,offsetPoint)) {
						return offsetPoint;
					}
				}
			}
			return null;
		}

		private function getSquareValue(pX:Number,pY:Number):Number {
			/*
			
			checking the 2x2 pixel grid, assigning these values to each pixel, if not transparent
			
			+---+---+
			| 1 | 2 |
			+---+---+
			| 4 | 8 | <- current pixel (pX,pY)
			+---+---+
			
			*/
			var squareValue:Number=0;
			// checking upper left pixel
			if (getAlphaValue(bitmapData.getPixel32(pX-1,pY-1))>=tolerance) {
				squareValue+=1;
			}
			// checking upper pixel
			if (getAlphaValue(bitmapData.getPixel32(pX,pY-1))>tolerance) {
				squareValue+=2;
			}
			// checking left pixel
			if (getAlphaValue(bitmapData.getPixel32(pX-1,pY))>tolerance) {
				squareValue+=4;
			}
			// checking the pixel itself
			if (getAlphaValue(bitmapData.getPixel32(pX,pY))>tolerance) {
				squareValue+=8;
			}
			return squareValue;
		}

		private function getAlphaValue(n:Number):Number {
			// given an ARGB color value, returns the alpha 0 -> 255
			return n >> 24 & 0xFF;
		}

		public function debug_draw():void {
			var debugDraw:b2DebugDraw = new b2DebugDraw();
			debugDraw.SetSprite(worldCont);
			debugDraw.SetDrawScale(30);
			debugDraw.SetFillAlpha(0.5);
			debugDraw.SetLineThickness(1);
			debugDraw.SetFlags(b2DebugDraw.e_shapeBit|b2DebugDraw.e_centerOfMassBit);
			world.SetDebugDraw(debugDraw);
		}

		private function update(e:Event):void {
			world.Step(1/30, 10, 10);
			world.ClearForces();
			world.DrawDebugData();
		}
	}
}

How would you optimize the process? Download the source code.

Get the most popular Phaser 3 book

Through 202 pages, 32 source code examples and an Android Studio project you will learn how to build cross platform HTML5 games and create a complete game along the way.

Get the book

215 GAME PROTOTYPES EXPLAINED WITH SOURCE CODE
// 1+2=3
// 100 rounds
// 10000000
// 2 Cars
// 2048
// A Blocky Christmas
// A Jumping Block
// A Life of Logic
// Angry Birds
// Angry Birds Space
// Artillery
// Astro-PANIC!
// Avoider
// Back to Square One
// Ball Game
// Ball vs Ball
// Ball: Revamped
// Balloon Invasion
// BallPusher
// Ballz
// Bar Balance
// Bejeweled
// Biggification
// Block it
// Blockage
// Bloons
// Boids
// Bombuzal
// Boom Dots
// Bouncing Ball
// Bouncing Ball 2
// Bouncy Light
// BoxHead
// Breakout
// Bricks
// Bubble Chaos
// Bubbles 2
// Card Game
// Castle Ramble
// Chronotron
// Circle Chain
// Circle Path
// Circle Race
// Circular endless runner
// Cirplosion
// CLOCKS - The Game
// Color Hit
// Color Jump
// ColorFill
// Columns
// Concentration
// Crossy Road
// Crush the Castle
// Cube Jump
// CubesOut
// Dash N Blast
// Dashy Panda
// Deflection
// Diamond Digger Saga
// Don't touch the spikes
// Dots
// Down The Mountain
// Drag and Match
// Draw Game
// Drop Wizard
// DROP'd
// Dudeski
// Dungeon Raid
// Educational Game
// Elasticity
// Endless Runner
// Erase Box
// Eskiv
// Farm Heroes Saga
// Filler
// Flappy Bird
// Fling
// Flipping Legend
// Floaty Light
// Fuse Ballz
// GearTaker
// Gem Sweeper
// Globe
// Goat Rider
// Gold Miner
// Grindstone
// GuessNext
// Helicopter
// Hero Emblems
// Hero Slide
// Hexagonal Tiles
// HookPod
// Hop Hop Hop Underwater
// Horizontal Endless Runner
// Hundreds
// Hungry Hero
// Hurry it's Christmas
// InkTd
// Iromeku
// Jet Set Willy
// Jigsaw Game
// Knife Hit
// Knightfall
// Legends of Runeterra
// Lep's World
// Line Rider
// Lumines
// Magick
// MagOrMin
// Mass Attack
// Math Game
// Maze
// Meeblings
// Memdot
// Metro Siberia Underground
// Mike Dangers
// Mikey Hooks
// Nano War
// Nodes
// o:anquan
// One Button Game
// One Tap RPG
// Ononmin
// Pacco
// Perfect Square!
// Perfectionism
// Phyballs
// Pixel Purge
// PixelField
// Planet Revenge
// Plants Vs Zombies
// Platform
// Platform game
// Plus+Plus
// Pocket Snap
// Poker
// Pool
// Pop the Lock
// Pop to Save
// Poux
// Pudi
// Pumpkin Story
// Puppet Bird
// Pyramids of Ra
// qomp
// Quick Switch
// Racing
// Radical
// Rebuild Chile
// Renju
// Rise Above
// Risky Road
// Roguelike
// Roly Poly
// Run Around
// Rush Hour
// SameGame
// SamePhysics
// Save the Totem
// Security
// Serious Scramblers
// Shrink it
// Sling
// Slingy
// Snowflakes
// Sokoban
// Space Checkers
// Space is Key
// Spellfall
// Spinny Gun
// Splitter
// Spring Ninja
// Sproing
// Stabilize!
// Stack
// Stairs
// Stick Hero
// String Avoider
// Stringy
// Sudoku
// Super Mario Bros
// Surfingers
// Survival Horror
// Talesworth Adventure
// Tetris
// The Impossible Line
// The Moops - Combos of Joy
// The Next Arrow
// Threes
// Tic Tac Toe
// Timberman
// Tiny Wings
// Tipsy Tower
// Toony
// Totem Destroyer
// Tower Defense
// Trick Shot
// Tunnelball
// Turn
// Turnellio
// TwinSpin
// vvvvvv
// Warp Shift
// Way of an Idea
// Whack a Creep
// Wheel of Fortune
// Where's my Water
// Wish Upon a Star
// Word Game
// Wordle
// Worms
// Yanga
// Yeah Bunny
// Zhed
// zNumbers