Sunday, January 21, 2007

Visualizing Sorting Rules

So, the sorting rules for the sprite graphic (which includes such lovely permutations as the Pachyrat, Bunnysaur, and Llamacorn (do you ever get tired of writing L's? I think not)) were getting unwieldy and as a result were largely incorrect. However, I was having some trouble convincing my topo sort algorithm to report cycles, and even then it would have been problematic to figure out where they needed to be broken. What does this mean? Vaguely, it means that my rules would occasionally say that the bunny ears were in front of the bunny rider, and occasionally the bunny ears would be behind the bunny rider. Of course it would be much more complicated. Here's an example cycle: the bunny ears are behind the mount head which is behind the llama fur, which is behind the saddle, which is behind the dinosaur head, which is behind the bunny ears. Since the rules file uses a lot of regular expressions and sandwiching techniques, these cycles are hard to find. I needed a way to visualize the problem.

Enter Graphviz. Graphviz is a tool that takes data describing a graph and produces an image of the graph. A picture is worth a thousand words. I spruced up the Cixar Python library's graphkit module (which uses Graphviz) and wrote a tool that produces graphs of layer sorting rules files. This is what I beheld. (old rules)

So, there are a few cycles in there. Ok, maybe a lot. They're easiest to spot by looking for arrows pointing up instead of down. Ooops. Clearly this isn't manageable. So, I started rewriting the layer sorting rules one set of layers at a time. I added a feature that lets me make "virtual layers" like "rider_face_bottom" and "rider_face_top" so I could organize the layers into boxes and sandwich the boxes. This is the result. In addition, the layer rules are all correct now, and I will be able to show off some demo graphics that include the mount rider tomorrow. (new rules)

No comments: