You can see how it'll only allow enemies (or anything else following a path on the network) to jump from platform to platform at certain points. For example they'll only jump to the highest bumpy platform from the right hand side of the platform below it. The basic waypoint generation goes something like this:
- Generate "surface groups" from a soup of surfaces. Surfaces are single straight 2d line segments, and surface groups contain all surfaces which touch (so the bumpy platform at the top is four surfaces in it's own surface group)
- Generate waypoints along each surface. Depending on the length each surface gets three or more waypoints (one at each end, and one or more at regular intervals in the middle). Waypoints hold a position and a reference back to their surface group. All waypoints along a surface are linked to the ones adjacent to themselves.
- We then prune redundant waypoints (as the earlier steps will produce waypoints exactly on top of each other when surfaces touch). It might be better to just not create redundant waypoints in the first place, but this way produces simpler code and is more robust.
- Finally, we create the links between platforms. Here we just link any waypoints to all other waypoints within a threshold distance, as long as the other waypoint is in a different surface group. Not creating links in the same surface group means we don't try and create links from one end of a platform to another (which would cause enemies to jump along platforms rather than walk along them).
I'm sure it could be optimised (such as not producing redundant waypoints in the first place), but it doesn't seem to produce any noticable loading delay, and it's going to be done offline at compile time eventually anyway.
At the moment every time we create a "link" we actually create two - one going one way and the other going the other way (which is why in the screenshot the waypoints are joined with two lines). One thing I might add later is generating single-direction links, for example going from the top bumpy platform to the one below it so that enemies can jump down but not up.
