Monthly Archive for February, 2009

When you are implementing a pathfinding algorithm you have usually some sort of defined map available. This is in most cases a tile map or a graph of nodes. If you have no nodes and no tiles you have two options: build a graph of nodes or put your smooth environment into a raster with a defined detail. Option two is usually faster but we have choosen number one for asthetic pleasure in the AudioTool. And we showed that building such a graph at runtime in Flash is something you can do if you implement clever optimizations.

You will always have problems without some kind of raster. Sometimes more, sometimes less. Usually you have to build your own context of how things are connected and how they behave in your environment. We were discussing a lot about the audio engine and the core structure behind. The most important part of the audio engine is probably the ability to build a linear chain of plugins which process signals that arrive in your speakers at the end of that chain. When we started this part we had a lot of optimizations in mind. Plugins that do not generate any audible output should not go into that chain etc. The code became quite complex and results in a lot of special case scenarios. Imagine a scope which is a pure visual element that shows the incomming waveform. This is a plugin which should not be kicked out of any chain but generates no audible output.

You can imagine that we used a graph for that kind of task. To be more specific: a directed cyclic graph since there is a direction of the flow and we are allowing feedbacks for audio signals. After some time of discussion I started researching for a better way of solving our signal chain. Because I beleive that a problem can be solved the easiest way on a pure mathematical basis I started with a plain graph — but this time a real graph. After some time I could produce the same output as our old solver but with less lines of code and we got rid of all the special cases.

Now having a real graph is fun and I was not surprised that lots of people invested their brainpower in graph algorithms. For the desktop in the AudioTool I always wanted to implement some kind of automatic layout algorithm. My first idea was to build a spring between two editors connected by a cable. I thought that this could be too complex but after spending the last days with graphs this became a possible solution and there are already algorithms which do the same thing: build springs for connections and let the system solve itself. I did some tests in a sandbox already but hopefully I can implement this in the AudioTool before FITC Amsterdam. The graph you see in the picture is a result of the graph layout engine.

But working with graphs opened my eyes even more. I am currently the poor bugger that has to implement a layout engine. Implementing a layout engine is by the way the most ungrateful task I could think of. Anyways, what if you think about the dependencies in your layout engine as a graph structure? You have usually three cases when calculating a size: relative known size to “some kind of available size”, absolute known size, absolute unknown size. Those cases can be reduced to their most simple form on a piece of paper and a graph structure evolves. You can get rid of observers and listeners in such a system if a connection in the graph has the meaning of invoking the layout engine again on a subset of nodes. Those subsets could be optimized even more if you figure out the strongly connected components in the graph. I have to admit that I did not implement this system yet but it makes a lot of sense in theory currently… something which makes working on a layout engine interesting again ;)

When you are implementing a pathfinding algorithm you have usually some sort of defined map available. This is in most cases a tile map or a graph of nodes. If you have no nodes and no tiles you have two options: build a graph of nodes or put your smooth environment into a raster ...