Archive

Posts Tagged ‘battle’

Optimizing Fortbattles

July 27th, 2009 4 comments

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: , , ,

Welcome on the devblog

June 26th, 2009 15 comments
Hi,
I am Eike Decker, also as known as Zet. I am working at InnoGames as a developer since January and I have been assigned to The West at the end of februrary. The first project that I’ve been working on for The West was the tutorial mode for the game which was introduced in 1.19. Since then I’ve been working on the fort battles non-stop. I wrote the flash client as well as the HTML frontend for the battles and also the parts on the game server that are related to the game play. If something doesn’t work as expect in these departments I am probably the person to blame.
The fort battles are a big deal different from any other game that has been developed at InnoGames. The most significant difference is probably the quite intensive interaction between a lot of players during the battles which normally last between 5 and 10 minutes. We’ve had battles with up to 50 players running and so far I am quite content with the results.
Since the introduction of the fort battles on the public beta server I became more interested in user opinions and started reading a few threads about the beta and the fortbattles during the break. Because I have never played The West before starting working on the forts, I have a lot of things to learn about the game and the players. While reading about opinions on the public beta I realized how much the new features are awaited but also that some are upset because of the delay and the limited amount of players on the public beta.
I can understand the disappointment among the players about the delay and other problems and although I am not to blame for all of them I want to express that I appologize for this and that I want to explain this or that with this first blog entry.
The development of the fort battles
As mentioned above, the fort battles are a complete new feature that was developed practically from scratch. I don’t want to bore the audience with technical details but all that I can say is that the technical hurds have been quite complicated to take. While it was fairly simple to develop a prototype server and client, it turned out more to be a problem to integrate the game tightly into the game itself which was quite surprising for me. It is extremely difficult to estimate the development time of a feature and thus it was also expected that this new feature would take some serious time to be completed.
The development can be roughly divided into four components which partially reflect the gameplay:
– The HTML frontend that is used for joining the fort battles
– The Flash frontend that is used while the battle is running
– A Java server that communicates with the Flash frontend
– and a PHP backend that integrates the fort battles into The West.
The HTML frontend
The HTML frontend should allow players to set their starting position and targets that are used during the fort battles. It does not use Flash since we wanted to alow players to take part in the fort battles even if they can not use flash. The frontend should provide all important information about the battlefield and the positions.
The Flash frontend
We decided that flash should be used for the battle itself. It should establish a connection with the server and gather / receive information on demand. This was the key reason why we chose flash next to the additional graphic effects that Flash provides.
The Java server
For a couple of reasons we decided to develop a Java server which would be used only for the fort battles and nothing else. The reason for this was that Java is more efficient than PHP and that a crash of the Fortbattle server should not influence the game itself. The server simulates the game and communicates with the flash clients. In theory, if the Java server would crash, the battle would restart at round 1.
The PHP backend
Most of the database related processing is done in the PHP backend. It informs the Java server about new battles and once a battle is finished, a PHP process receives all results and takes all kind of actions on players and forts.
Features vs. Time, Time vs. Bugs
There are tons of features that did not get into the fort battles. There are plenty

Hi,

zetshotI am Eike Decker, also as known as Zet. I am working at InnoGames as a developer since January and I have been assigned to The West at the end of february. The first project that I’ve been working on for The West was the tutorial mode for the game which was introduced in 1.19. Since then I’ve been working on the fort battles non-stop. I wrote the flash client as well as the HTML frontend for the battles and also the parts on the game server that are related to the game play. If something doesn’t work as expect in these departments I am probably the person to blame. For anything else I am less likely to know what’s going on – I have only a limited overview on other features than the fortbattles. Simply because I have not done much else apart from that.

But as far as I can tell, the fort battles are a big deal different from any other part of The West. The most significant difference is probably the quite intensive interaction between a lot of players during the battles which normally last between 5 and 10 minutes. We’ve had battles with up to 50 players running and so far I am quite content with the results.

intro_blog_attackswarm
Attackers are swarming the defenders on the beta server

Since the introduction of the fort battles on the public beta server I became more curious about user opinions (especially on the fort battles) and started reading a few threads about the beta and the fortbattles during the breaks on the public forums. Because I have never played The West before starting working on the forts, I have a lot of things to learn about the game and the players. While reading about opinions about the public beta I realized how much the new features are awaited but also that quite a few are upset because of the delay and the limited amount of players on the public beta.

I can understand the disappointment among the players about the delay and other problems. And although I am not to blame for all of them I want to express that I appologize for this and that I want to explain this or that with this first blog entry.

The development of the fort battles

As mentioned above, the fort battles are a complete new feature that was developed practically from scratch While it was fairly simple to develop a prototype server and client, it turned out more to be a problem to integrate the game tightly into the game itself which was quite surprising for me. It was extremely difficult to estimate the development time of that feature beacuse of this.

The development can be roughly divided into four components which partially reflects the gameplay:

  • The HTML frontend that is used for joining the fort battles
  • The Flash frontend that is used while the battle is running
  • A Java server that communicates with the Flash frontend
  • and a PHP backend that integrates the fort battles into The West.

The HTML frontend

The HTML frontend should allow players to set their starting position and targets that are used during the fort battles. It does not use Flash since we wanted to allow players to take part in the fort battles even if they can not use flash. The frontend should provide all important information about the battlefield and the positions. Characters that are not controlled by connected players will move to their chosen destiny on their own. They are – no question – much less flexible as the characters that are actively played, however they can still provide the tip on the scales that changes the battle outcome.

The Flash frontend

We decided that flash should be used for the battle itself. It should establish a connection with the server and gather / receive information on demand. This was the key reason why we chose flash next to the additional graphic effects that Flash provides. We accepted the fact that a minority of players are going to be unable to play the game that way (for example if they don’t have Flash or if they are behind a firewall that they cannot influence) in favor of these technical advantages. We will try to bypass these problems in the future and I have already ideas how to work that out. But for the moment, the connection itself seems to be stable enough for the release.

The Java server

For a couple of reasons we decided to develop a Java server which would be used only for the fort battles and nothing else. The reason for this was that Java is more efficient than PHP and that a crash of the Fortbattle server should not influence the game itself. The server simulates the game and communicates with the flash clients. Because it is less of a problem to manage different threads in Java and also having more control on the memory, it also doesn’t cost too much performance. We have no facts so far, but we expect that this solution will work much better while using less resources than using PHP.

In theory, if the Java server would crash, the battle would restart at round 1. Of course this would also upset the players that are involved, but that seemed to be the most acceptable consequence compared with other outcomes of other technologies. We hope that this won’t happen and we also planned to restore partial gameplays once the basic features are working.

The PHP backend

Most of the database related processing is done in the PHP backend. It informs the Java server about new battles and once a battle is finished, a PHP process receives all results and takes all kind of actions on players and forts.

Features vs. Time, Time vs. Bugs

There are tons of features that did not get into the fort battles. There are plenty of ideas that we have for future releases and we tried during the design of the system to provide enough room to make these changes when we have the time to do them. We are only working right now on features that are eminent for the gameplay or that are mostly done. Right now we are denting out bugs that we oversaw so far.

At this point I also want to thank all beta testers who help us to find bugs and testing the game. Some hints had been really a great help to prevent that the release would fail. Of course there are no guarantees for the planned release, but I feel much more confident because of our beta testers.

intro_devblog_fort_hourglass

Future blogging

For the future, I am planning to blog constantly on development about The West. If this is not possible because new features are not yet to be mentioned yet, I’ll just come up with rants on technical details about what I already did at InnoGames.