I've gone and ripped out all of the player controller code from my project with a view to rewriting it from scratch. The previous version was a fairly abstract state machine with each state represented by a class derived from PcState. While this nicely compartmentalised up the code, it led to a fair amount of duplication, was hard to see what was going on at a higher level and took a lot of effort to add new states.

So now I've decided to implement the PcStateMachine as a single class and deal with all the states in one .cpp file. There are a couple of places where we switch on the current state and call things like updateIdle(), updateRunning() etc. but also more opportunity to share code between states and get a better overview of the entire thing.

Since this is all currently half done and rather low on eye-candy results, I thought I'd write a bit up about my automatic edge-detection preprocess step today. Here you can see the results in yellow of running the routine on the current example map.

The maps are exported from my own level editor and consist of definitions of physical polyhedrons (currently all cuboids but any convex shape can be supported), and triangle faces which are assembled into a vertex buffer or buffers and added to the scene. So the edge detection needs to work on the physical shapes.

When the level is loaded, the Physics object is populated with Body instances, each of which has a Shape, of which Polyhedron is the most common type and the only one relevant currently to edge detection.

Polyhedron is so common in fact that I have broken the rules of object-orientation and have the following as part of the Shape interface:

class Polyhedron;class Shape{public:// snip virtual Polyhedron *polyhedron(){ return 0; } virtual const Polyhedron *polyhedron() const { return 0; }// snip};A bit nasty, but means I can test without a dynamic_cast and quickly get hold of the Polyhedron interface. Obviously all other Shape classes leave this as is, but Polyhedron implements both to return this.

Once all the Body instances are added to the Physics object, the edge-detection steps are run. First up, it iterates over all of the Body instances and, for those that are actually Polyhedrons, calls Polyhedron::createInitialEdges(), which just returns a list of edges of any face in the Polyhedron whose normal dots above a certain value with Vec3(0, 1, 0) (i.e. is pointing sufficiently upwards or is walkable, depending on how you want to think about it).

pod_vector Polyhedron::createInitialEdges() const{ pod_vector e; pod_vector vs = vertices(); for(uint f = 0; f < fs.size(); ++f) { if(dotVectors(ns[f], Vec3(0, 1, 0)) >= 0.8f) { for(uint i = 0; i < fs[f].size(); ++i) { uint j = i < fs[f].size() - 1 ? i + 1 : 0; Vec3 a = vs[fs[f]]; Vec3 b = vs[fs[f][j]]; Vec3 c = (b - a); Vec3 n = crossVectors(normalizeVector(c), ns[f]); e.push_back(Edge(a, b, n)); } } } return e;}This gives us pre-clipped edges like this. Note the edges cross the gaps where they should not at this stage.

So we gather up a map with the key being a Body* and the value being a list of edges, where an edge is just two local positions and a "normal" which represents which direction the edge is "facing". This is then passed into the preprocess stage.

For each Body, we run the Physics broadphase to get a list of other Body instances that could potentially be close enough to this Body to require some edge clipping. Edges are collected then passed into the clipSegments method along with the currently considered edge. Segment is a transformed Edge in world corrdinates and no normal.

PreprocessEdgeMap preprocessShapeEdges(const PreprocessEdgeMap &input, Physics &physics){ PreprocessEdgeMap result; for(auto i = input.begin(); i != input.end(); ++i) { BroadphaseResult bp = physics.broadphaseAabb(i->first->aabb().expanded(0.25f), BodyFilterSet({ i->first })); auto bodies = bp.bodies; for(auto e = i->second.begin(); e != i->second.end(); ++e) { Segment s = transformSegment(*e, i->first->transform()); pod_vector clips; clips.push_back(s); for(auto b = bodies.begin(); b != bodies.end(); ++b) { pod_vector c = transformSegments(input.at(*b), (*b)->transform()); for(auto j = c.begin(); j != c.end(); ++j) { clips = clipSegments(clips, *j); } } pod_vector final; for(auto j = clips.begin(); j != clips.end(); ++j) { final.push_back(untransformSegment(*j, i->first->transform(), e->normal)); } for(auto j = final.begin(); j != final.end(); ++j) { if(vectorLength(j->first - j->last) > 0.001f) { result[i->first].push_back(*j); } } } }}The clipSegments method walks over the list of Segments and compares them to the current Segment, looking to see if there is an intersection. If there is, the intersected range is calculated and added to a list of ranges. Finally this range is inverted to give back the segments that are not being clipped out, which is returned.

pod_vector clipSegments(const pod_vector &a, const Segment &b){ std::vector > clips; for(auto i = a.begin(); i != a.end(); ++i) { clips.push_back(pod_vector()); if(distanceToLine(i->first, i->last, b.first) < 0.001f && distanceToLine(i->first, i->last, b.last) < 0.001f) { float t0 = pointOnLine(i->first, i->last, b.first); float t1 = pointOnLine(i->first, i->last, b.last); if(t0 > t1) std::swap(t0, t1); clips.back().push_back(Range(t0, t1)); } } pod_vector final; for(uint i = 0; i < a.size(); ++i) { if(clips.size()) { Vec3 p = a.first; Vec3 e = a.last - a.first; pod_vector range; for(uint j = 0; j < clips.size(); ++j) { float t0 = clips[j].first; float t1 = clips[j].last; if(t0 >= 1 || t1 <= 0) { final.push_back(Segment(p, p + e)); } else { range.push_back(Range(t0, t1)); } } std::sort(range.begin(), range.end()); range = invertRange(range); for(uint j = 0; j < range.size(); ++j) { float t0 = range[j].first; float t1 = range[j].last; final.push_back(Segment(p + (e * t0), p + (e * t1))); } } else { final.push_back(a); } } return final;}This transforms the image above into this. Note at the sections where the ground lines up, the edges are now gone and note particularly around the hole in the top-right area of the map, the walkable ground is now continuous.

The final edges are converted back to local space and assigned to the Shape that first generated them. Now when the game is running, we can query a Shape to get hold of a list of its clipped edge segments. For example, you can pass a flag to the Kinematic Character Controller class (Kcc) to tell it to not move over edges (when walking for example). That looks like:

Vec3 Polyhedron::edgeConstrainQuery(const Vec3 &pos, float radius, const Matrix &transform) const{ Vec3 v(0, 0, 0); for(auto &i: es) { Vec3 a = transformCoord(i.first, transform); Vec3 b = transformCoord(i.last, transform); Vec3 n = transformNormal(i.normal, transform); Vec3 p = closestPointOnSegmentToPoint(a, b, pos); float dist = vectorLength(p - pos); if(dist <= radius) { float m = radius - dist; v += -(n * m); } } return v;}Vec3 Kcc::edgeQuery(const RayResult &floor) const{ if(floor.valid()) { if(const Polyhedron *p = floor.body().shape().polyhedron()) { return p->edgeConstrainQuery((pos - Vec3(0, shape.height() / 2, 0)), shape.radius() / 2, floor.body().transform()); } } return Vec3(0, 0, 0);}void Kcc::implementMove(Vec3 &position, bool &grounded, Physics &physics, MoveFlags flags, const Vec3 &step) const{// snip if(flags & StayOnEdges) { sep += edgeQuery(floor); } position += mv + sep;// snip}We can also use the edges for edge-hanging and shimmying and anything else that requires such data.

So it would be a painful step to have manually had to define these edges in the editor. I've been using the edge detector in test projects for over a year now and have yet to find a configuration of shapes that fools it so it was well worth the effort to initially write. Anything we can remove the human effort from and have automatically generated is excellent for an indie developer as we all know that creating level content is probably the hardest challenge in a project of this type.

If you are still with me, thanks for perservering. Probably a bit too much code and not enough screen-candy in this journal for most, but I felt like explaining this would give a bit of insight into quite how much is going on under the hood in this game. I am planning a similar write-up of the Kinematic Character Controller at some point soon since this is also a highly complex area that took many years to get right and I'm quite pleased with the way I was able to implement it in Bullet without having to use an actual physical object to represent the player. More on that soon.