Home > 1.20, Fort battles > Optimizing Fortbattles

Optimizing Fortbattles

July 27th, 2009

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.

Sectors and onlinestate of players

Sectors and onlinestate of players

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:

Wrongly implemented left hand rule

Wrongly implemented left hand rule

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

The correctly found sector outlines

The correctly found sector outlines

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:

removing the unneeded points when drawing a straight line saves time during drawing.

Removing the unneeded points when drawing a straight line saves time during drawing.

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

Categories: 1.20, Fort battles Tags: , , ,
  1. Ormitoryx
    July 27th, 2009 at 19:10 | #1

    That’s all very interesting, but when are you going to add experience from fort battles? I guess that without it the 1.20 release can hardly be called complete…
    And don’t get me wrong – I’m far from complaining. I think you guys did tremendous job and fort battles are really fun. That’s why I’m excited and a bit impatient to see the thing finished 🙂

  2. July 27th, 2009 at 21:24 | #2

    @Ormitoryx: XP for battles are in the works, as well as item dropping. It will be releases with 1.21 – which should not take too long. We know that 1.20 is not a complete release, but we didn’t want to wait much longer because the release of a new version becomes more complicated the more code has been changed. So you can expect that the next releases for the next 3-4 months will contain fixes and features that didn’t made it into 1.20.

  3. Joe Torpedo
    July 28th, 2009 at 09:32 | #3

    Some cheating strategies in fortbattles
    1. Spies
    They are registered on an opposite side
    Look arrangement of opponents before fight, then do not participate or participate without the weapon and clothes

    2. Filling by a ballast (swarming)
    Before fight fill the opponent with deserters
    They also look arrangement, then do not accept participation or simply leave fort before battle
    As a result sympathising fighters cannot take part because of a limit and the easy uninteresting victory is reached

    How can this is possible to stop:
    1. To add to the head of a fort (or leader of offenders) kick out function removing any player from the list of participants,
    Thus such player receives the disability on fortfights (effective against spies, because the head/leader do not kick out good ones, I think)
    2. For deserters: the disability to fortfight for 2-3 days

  4. Dim
    July 28th, 2009 at 20:12 | #4

    Something I would like fort fights to have is the name of the cities on both sides.
    OK we can see the defender -they are the owners of the fort- but why can’t we see the assaulting town in order to choose side?

Comments are closed.