Optimizing Fortbattles

The flash client for the fort battles has been developed in an extremely short time (compared to the rest) and due to this, it is not as efficient as it could be. I fixed the worst issue in the drawing algorithms of the client about 2 weeks ago: The sectors.

The reason was the algorithm of how the sectors have been drawn: For each cell, the algorithm checked the borders of the sector, and if the cell is next to different sector, a border is drawn on that side of the cell. So this check was done 4 times for each edge of the rectangle and for every rectangles on the map. This is a stable and simple approach, however, also one of the slowest approaches.

In order to fix that, I changed the approach of drawing the sectors: Instead of checking each cell one by one (about 600-700 cells), I wanted to draw each sector one by one (there are about 50 sectors). Therefore, I needed to determine the sector boundaries at first. This can be done ahead of time when the map is loading, so that algorithm for detecting these boundaries can be somewhat complex as long as the description of the boundaries can be easily used afterwards. Detecting the outline is in general a simple algorithm – also known as left-hand rule [1]: If you are in a maze and you want to find all possible ways, you can simply stretch out your hand and keep it on the wall. That way, you are traversing the complete maze – at least if it is an ordinary maze. Though this excludes mazes where there is a center maze where the walls are not connected with the walls on the entry of the maze, but for my problem, this doesn’t matter.

Actually, I tried at first a much simpler approach even, but that would have worked only for convex sector shapes, and we have a couple of concave sectors (If you don’t know the meaning of concave and convex, you might look it up here[2]).

I find graphics programming often very nice because even the bugs can look pretty:

So what went wrong here was that my “left hand” left the “wall”. Quite wrong. After a while the result looked like this:

Which is looking more correct. It also looks funny because I also used a small trick to detect problems in my border tracing: During the implementation it happened, that my algorithm did not notice that it traced a part that it had visited before, so my border description contained redundant information.

To see these multiple lines, I drew the outlines with random vector offsets at each point. This gave the output such a scribbled look. You can also see that way, that I already stripped the points away between the corners – if a line stretches over a couple of cells, the initial algorithm would record points at each corner of the rectangle. These points are not required to draw the sector, so I tweaked the algorithm to reduce the amount of drawn vertexes:

If the algorithm had still these unneeded points, it would have become visible when drawing the outlines with random vector offsets.

The performance win of this improved technique was not crucial but in deed measurable. There are other parts that could be optimized, but as this improved already one of the worst algorithms, this can now wait a bit.

[1]: Maze solving algorithm: http://en.wikipedia.org/wiki/Maze_solving_algorithm

[2]: Convex Hull: http://en.wikipedia.org/wiki/Convex_hull