YSFLIGHT.COM -

11/27/2014 Circle tangential line, A* path finder, and AVL tree

It is Thanksgiving break! My teaching duty for this semester is almost over. All I have to do is grading final presentations and last exam. I am able to relax and work on my hobby projects including YSFLIGHT, Scenery Editor, and Polygon Crest.

I thought I start with fixing bunch of reported bugs (Thank you for the bug reports!), but before that I felt it's a shame that computer-controlled airplanes wander into the range of anti-air batteries and shut down. It's a good idea to write a simple path-planning program so that computer-controlled airplanes can avoid obstacles and anti-air batteries.

I didn't intend to do anything sophisticated. All I need to do is find a course that avoid all circles that define firing ranges of anti-air batteries. For example, if I calculate tangential line that passes through the current location of the airplane, and the firing-range circle and keep the airplane outside of the tangential lines, it's done.

I was sure I have written such a function before. I looked for the functions in my class library, but turned out I never put it in my collection of the reusable functions. I always add a function or a class to my YS-Class library whenever I write a piece of code that relies only on C/C++ standard. But, I didn't find such a function. I wrote one, and added to my class library.

I could easily calculate a threat-avoiding path when there is only one firing-range circle. I needed to expand it for multiple-circles and in case the airplane is already inside one of the circles. Which turned out not too trivial. If I don't care the computational time, I can run an exhaustive search. It will finish in reasonable computational time, considering the number of anti-air objects of YSFLIGHT. However, if I need to do it fraction of 1/60 seconds, so that the calculation does not substantially slow down the frame rate, an exhaustive search is not an option. It does not have to be 100% optimal path. As long as it finds a reasonable path, it's good enough. I tried to think something that is easy enough to implement and can come up with a reasonable threat-avoiding path. But, I couldn't find one.

I decided to study a path-finding algorithm and implement. I didn't know much about path-finding, but one of my students was talking about an algorithm called A*. She was able to implement the algorithm by herself. If a student can implement it, I should be able to do it quickly. What's good about writing YSFLIGHT is I end up with learning new algorithms and techniques.

I have implemented an algorithm described in Wikipedia almost as is. But, I faced one problem, which was finding a node from openSet that has the minimum cost-function value f. In each step, openSet is updated. The number of elements in the set grows or shrinks, or the cost-function value of an element in the set may change. What I did was used a simple array, and kept the element sorted in the descending order. Cost for finding the location to add a new element is O(logN). Finding the minimum-f element is O(1). However, when I insert a new element, I need to shift the elements in the array, which cost O(N). I need to do N times. So, the overall computational complexity becomes O(N²), where N is the number of elements in the openSet. Which will be ok if the number of elements N is small. But, is it small?

Test program screen shot. Green: found path.
Black: obstacle. Cyan: closedSet. Magenta: openSet.

I implemented and experimented. In conclusion, the elements in the openSet grows to the number of elements on the boundary of the area where the algorithm has already visited. It makes sense because the openSet is where the algorithm would search for the next step. But, it can grow more than insignificant number.

Finding a path from lower left to upper right of a 400x300 lattice took 120ms on my 2008 MacBook Pro. I won't need that much resolution for the threat-avoiding path for an airplane because the airplane cannot turn quickly anyway. But, if I want to use it for taxiing-path calculation, I would use even denser resolution. It's not fast enough.

It must be how I store the openSet. It needs to be always sorted and needs to be able to find the minimum-f node quickly. For this kind of purpose, I have been interested in implementing a kind of self-balancing binary tree. Actually, I needed a similar data structure many times before, but always I found an alternative way of solving the problem. But, this time, it is a good opportunity to learn and implement one, then I can use it for the future projects.

There seems to be several different kinds of self-balancing binary trees. I remember one of the students working on the AVL tree for his data-structure course assignment. If a student could implement it in a week, I should be able to do it in an hour or so.

Why not finding a code from the Internet? I wouldn't learn anything if I randomly cut & pates someone else's code.

I just implemented the algorithm shown in Wikipedia as is. My honest feeling was "Is that it? Is this simple algorithm really maintains the AVL tree structure?" And, it was, apparently. I wrote various tests to check if the tree is balanced as advertised, if the balances are calculated correctly, if the elements are stored in the correct order, etc. I also tested by randomly inserting and deleting nodes. It worked!

Then I tested the speed by inserting 2 million nodes, which took 9 seconds on my 2008 MacBook Pro. Slow. I was expecting it to be much faster. At that moment, the code had redundant checks that were not supposed to be necessary if the algorithm was implemented correctly. I could drop those checks. Nonetheless, there didn't seem to be too much room for speeding up because the algorithm was so simple.

After thinking about an hour for why it was that slow in Dunkin Donuts in Oakland, I realized that I forgot adding the optimization option (/O2) for the compiler! That was dumb.

It was a templated class. The compiler was supposed to make simple functions inline, but since I didn't put /O2 option, none of the functions were inline-expanded. With /O2 option, adding 2 million nodes took less than 3 seconds, almost 2. Not too bad. I increased the node count, and inserting 10 million nodes took 24 seconds. It is supposed to grow by the factor of NlogN. So, it makes sense. After dropping redundant checks, the time was reduced to 19 seconds. I feel that I can further reduce unnecessary balance-calculations, and may be able to gain another 10% or so, but it is practically fast enough.

I also tested A* code with /O2 option, and it took 60 to 80 milliseconds. I didn't see four-times acceleration with the /O2 option.

But, it was supposed to become much faster by replacing the sorted array with the AVL tree. But, it didn't happen. After using the AVL tree for the openSet, it was still 60 to 80 milliseconds. Looked like the overhead was in somewhere else. My guess was not right.

Looks like I need to look into the code and speed it up before incorporating with YSFLIGHT. But, when it is working, it can be used not just for avoiding anti-air threats, but also for avoiding terrain, and auto-calculating taxiing paths (without specifying taxiing path in the Scenery Editor!). But, maybe not in the next release.

So, I initially tried to do it with circle-tangential calculation, but it was not that straight forward. I ended up implementing A* path finding algorithm, but it was not as fast as I wanted, and I tried to make it faster by AVL tree, only to find that A* was running so slow because I forgot /O2 option. And, AVL tree didn't help much. That was what I was doing over the last weekend.

After writing this much, I realized that if I combine overlapping firing-range circles and make it a set of non-overlapping circles, it is almost trivial to find a path, by the way.