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
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
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
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(N2), 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.
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
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
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
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.