Create non-convex, complex shapes with Box2D

If you are working with Box2D for a while, probably you have already met the problem you can’t create non-convex shapes. This is a problem Box2D faces for years, as you can see from this post, and due to Box2D’s structure itself, we will never be able to create concave shapes.

That’s why some 3rd party libraries like PhysicsEditor allow us to break a concave shape into a set of convex shapes and make possible the creation of complex bodies.

Antoan Angelov, the author of the optimized version of the Box2d slicing engine, strikes back with another great Box2D class called b2Separator.

« The class is called b2Separator, and yes – it is made to work specifically with Box2D! What does it do, you ask? Well, we all hate when we have to make a more complex, non-convex shape for our b2Body – because we have to manually make many b2Fixtures, and make those really confusing and time-wasting calculations to see how each fixture is supposed to fit in with the others. Well, our troubles are now over, because what b2Separator does is separate a non-convex shape into smaller, convex shapes in a very optimized way and add them as b2Fixtures to a b2Body. All you need to do is give it the vertices of the shape you want! »

This is the fully commented class:

/*
* Convex Separator for Box2D Flash
*
* This class has been written by Antoan Angelov. 
* It is designed to work with Erin Catto's Box2D physics library.
*
* Everybody can use this software for any purpose, under two restrictions:
* 1. You cannot claim that you wrote this software.
* 2. You can not remove or alter this notice.
*
*/

package Box2DSeparator{
	import Box2D.Collision.Shapes.b2PolygonShape;
	import Box2D.Common.Math.b2Vec2;
	import Box2D.Dynamics.b2Body;
	import Box2D.Dynamics.b2FixtureDef;

	public class b2Separator;
	{
		public function b2Separator() {
		}

		/**
		 * Separates a non-convex polygon into convex polygons and adds them as fixtures to the body parameter.
* There are some rules you should follow (otherwise you might get unexpected results) : *
    *
  • This class is specifically for non-convex polygons. If you want to create a convex polygon, you don't need to use this class - Box2D's b2PolygonShape class allows you to create convex shapes with the setAsArray()/setAsVector() method.
  • *
  • The vertices must be in clockwise order.
  • *
  • No three neighbouring points should lie on the same line segment.
  • *
  • There must be no overlapping segments and no "holes".
  • *

* @param body The b2Body, in which the new fixtures will be stored. * @param fixtureDef A b2FixtureDef, containing all the properties (friction, density, etc.) which the new fixtures will inherit. * @param verticesVec The vertices of the non-convex polygon, in clockwise order. * @param scale [optional] The scale which you use to draw shapes in Box2D. The bigger the scale, the better the precision. The default value is 30. * @see b2PolygonShape * @see b2PolygonShape.SetAsArray() * @see b2PolygonShape.SetAsVector() * @see b2Fixture * */ public function Separate(body:b2Body,fixtureDef:b2FixtureDef,verticesVec:Vector.,scale:Number=30):void { var i:int,n:int=verticesVec.length,j:int,m:int; var vec:Vector.=new Vector. ,figsVec:Array; var polyShape:b2PolygonShape; for (i=0; i ; vec=figsVec[i]; m=vec.length; for (j=0; jverticesVec can be properly distributed into the new fixtures (more specifically, it makes sure there are no overlapping segments and the vertices are in clockwise order). * It is recommended that you use this method for debugging only, because it may cost more CPU usage. *

* @param verticesVec The vertices to be validated. * @return An integer which can have the following values: *

    *
  • 0 if the vertices can be properly processed.
  • *
  • 1 If there are overlapping lines.
  • *
  • 2 if the points are not in clockwise order.
  • *
  • 3 if there are overlapping lines and the points are not in clockwise order.
  • *
* */ public function Validate(verticesVec:Vector.):int { var i:int,n:int=verticesVec.length,j:int,j2:int,i2:int,i3:int,d:Number,ret:int=0; var fl:Boolean,fl2:Boolean=false; for (i=0; i0)?i-1:n-1; fl=false; for (j=0; j0)) { fl=true; } } if ((j!=i3)) { j2=(j):Array { var vec:Vector.; var i:int,n:int,j:int; var d:Number,t:Number,dx:Number,dy:Number,minLen:Number; var i1:int,i2:int,i3:int,p1:b2Vec2,p2:b2Vec2,p3:b2Vec2; var j1:int,j2:int,v1:b2Vec2,v2:b2Vec2,k:int,h:int; var vec1:Vector.,vec2:Vector.; var v:b2Vec2,hitV:b2Vec2; var isConvex:Boolean; var figsVec:Array=[],queue:Array=[]; queue.push(verticesVec); while (queue.length) { vec=queue[0]; n=vec.length; isConvex=true; for (i=0; i ; vec2=new Vector. ; j1=h; j2=k; v1=vec[j1]; v2=vec[j2]; if (! pointsMatch(hitV.x,hitV.y,v2.x,v2.y)) { vec1.push(hitV); } if (! pointsMatch(hitV.x,hitV.y,v1.x,v1.y)) { vec2.push(hitV); } h=-1; k=i1; while (true) { if ((k!=j2)) { vec1.push(vec[k]); } else { if (((h<0)||h>=n)) { err(); } if (! this.isOnSegment(v2.x,v2.y,vec[h].x,vec[h].y,p1.x,p1.y)) { vec1.push(vec[k]); } break; } h=k; if (((k-1)<0)) { k=n-1; } else { k--; } } vec1=vec1.reverse(); h=-1; k=i2; while (true) { if ((k!=j1)) { vec2.push(vec[k]); } else { if (((h<0)||h>=n)) { err(); } if (((k==j1)&&! this.isOnSegment(v1.x,v1.y,vec[h].x,vec[h].y,p2.x,p2.y))) { vec2.push(vec[k]); } break; } h=k; if (((k+1)>n-1)) { k=0; } else { k++; } } queue.push(vec1,vec2); queue.shift(); break; } } if (isConvex) { figsVec.push(queue.shift()); } } return figsVec; } private function hitRay(x1:Number,y1:Number,x2:Number,y2:Number,x3:Number,y3:Number,x4:Number,y4:Number):b2Vec2 { var t1:Number=x3-x1,t2:Number=y3-y1,t3:Number=x2-x1,t4:Number=y2-y1,t5:Number=x4-x3,t6:Number=y4-y3,t7:Number=t4*t5-t3*t6,a:Number; a=(((t5*t2)-t6*t1)/t7); var px:Number=x1+a*t3,py:Number=y1+a*t4; var b1:Boolean=isOnSegment(x2,y2,x1,y1,px,py); var b2:Boolean=isOnSegment(px,py,x3,y3,x4,y4); if ((b1&&b2)) { return new b2Vec2(px,py); } return null; } private function hitSegment(x1:Number,y1:Number,x2:Number,y2:Number,x3:Number,y3:Number,x4:Number,y4:Number):b2Vec2 { var t1:Number=x3-x1,t2:Number=y3-y1,t3:Number=x2-x1,t4:Number=y2-y1,t5:Number=x4-x3,t6:Number=y4-y3,t7:Number=t4*t5-t3*t6,a:Number; a=(((t5*t2)-t6*t1)/t7); var px:Number=x1+a*t3,py:Number=y1+a*t4; var b1:Boolean=isOnSegment(px,py,x1,y1,x2,y2); var b2:Boolean=isOnSegment(px,py,x3,y3,x4,y4); if ((b1&&b2)) { return new b2Vec2(px,py); } return null; } private function isOnSegment(px:Number,py:Number,x1:Number,y1:Number,x2:Number,y2:Number):Boolean { var b1:Boolean=((((x1+0.1)>=px)&&px>=x2-0.1)||(((x1-0.1)<=px)&&px<=x2+0.1)); var b2:Boolean=((((y1+0.1)>=py)&&py>=y2-0.1)||(((y1-0.1)<=py)&&py<=y2+0.1)); return ((b1&&b2)&&isOnLine(px,py,x1,y1,x2,y2)); } private function pointsMatch(x1:Number,y1:Number,x2:Number,y2:Number):Boolean { var dx:Number=(x2>=x1)?x2-x1:x1-x2,dy:Number=(y2>=y1)?y2-y1:y1-y2; return ((dx<0.1)&&dy<0.1); } private function isOnLine(px:Number,py:Number,x1:Number,y1:Number,x2:Number,y2:Number):Boolean { if ((((x2-x1)>0.1)||x1-x2>0.1)) { var a:Number=(y2-y1)/(x2-x1),possibleY:Number=a*(px-x1)+y1,diff:Number=(possibleY>py)?possibleY-py:py-possibleY; return (diff<0.1); } return (((px-x1)<0.1)||x1-px<0.1); } private function det(x1:Number,y1:Number,x2:Number,y2:Number,x3:Number,y3:Number):Number { return x1*y2+x2*y3+x3*y1-y1*x2-y2*x3-y3*x1; } private function err():void { throw new Error("A problem has occurred. Use the Validate() method to see where the problem is."); } } }

And this is what you can do with it:

Download the source code and all required libraries.

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