Our level editor is shaping up and this week I was able to contribute a small but important piece, the automatic ground finding algorithm. We have defined a spritesheet of ground tiles and defined a naming convention for each piece based on the player clip location and angle. We have also created corner pieces and have all 45 and 30 degree angles possible. My job was to analyze all these pieces and great an optimized set of lines for the physics engine. Instead of having each tile's coordinates put into the engine, we want to condense all straight lines to just 2 points, and get rid of all the intermediate points that basically give us no new info. For example, we have a set of tiles that should have a ground clip like this:
._._._._.
\.
|._._._.
The dots represent current vertices, and the lines are adjacencies. Using a map, where each dot is a node and each line is interpreted into an adjacency list, the algorithm becomes simple. Our desired output is:
.____.
\.
|.___.
As you can see, the dots are located at 3 distinct types of locations: end of a line, start of a line, and points where there is a change in direction that can be identified by the following rules:
Start/End of a line: Node has only one adjacency.
Change of direction: The previous adjacency has a different direction than the next adjacency.
My algorithm first picks a Node remaining (it does this smart by picking one that has only one adjacency) and begins to walk the map. Each step it takes it removes the adjacency it used to walk in order to avoid backtracking. When it can no longer walk, it has reached the end of a connected segment, and moves on to any remaining nodes, picking it's next item in a way to avoid starting in the middle of a line. So far it's working well, but the limitation is that at most a node can have two adjacency. This limits our level design to not having any 'T' or 4-way intersections in the terrain.
-Dave
