SummerOfCodeProposal cjhopman

note to mentors

this is a major work in progress, feel free to not review it yet.

Questionnaire

Basics

1. Write a small introduction to yourself.
   • My name is Chris Hopman, I'm a student of computer science and mathematics. I'm graduating from the University of Wisconsin - Madison in May and will be attending the cs PhD program here in the fall.
2. State your preferred email address.
   • cjhopman@gmail.com
3. If you have chosen a nick for IRC and Wesnoth forums, what is it?
   • My nick is cjhopman pretty much everywhere.
4. Why do you want to participate in summer of code?
   • Participating in summer of code will give me an opportunity to spend a lot of time doing something that I enjoy. I will get to work on an interesting project and will get to make a major contribution to a great project.
5. What are you studying, subject, level and school?
   • I am currently an undergraduate studying mathematics and computer science at the University of Wisconsin - Madison. I will be graduating in May and will be attending the PhD program here in the fall.
6. If you have contributed any patches to Wesnoth, please list them below. You can also list patches that have been submitted but not committed yet and patches that have not been specifically written for Wesnoth. If you have gained commit access to our SVN (during the evaluation period or earlier) please state so.
   • I received commit access to the Wesnoth SVN early in 2008. There is a list of some of my contributions below.

Experience

1. What programs/software have you worked on before?
   • The largest program that I have worked on is definitely Wesnoth. Other than that, and other than projects just for classes, I have worked on two other projects. The first is autoscanner. The goal of this program is to do automatic 3d reconstruction of a statue from a short video clip. I did this project with another student for a professor that we worked for. The second project is more of a library of various functions. It can be found here. It is meant primarily to be useful for algorithm competitions (TopCoder, ICPC, etc.) and so is mostly graph theory, computational geometry, linear algebra, and other similar stuff.
2. Have you developed software in a team environment before? (As opposed to hacking on something on your own)
   • Other than Wesnoth, the two projects I just mentioned were both done in groups of 2-3. So, primarily my experience of developing software in a team environment is just that from my contributions to Wesnoth.
3. Have you participated to the Google Summer of Code before? As a mentor or a student? In what project? Were you successful? If not, why?
   • I have not participated in Google Summer of Code before.

Open Source

1. Are you already involved with any open source development projects? If yes, please describe the project and the scope of your involvement.
   • Wesnoth is the only open source project that I am involved in (actually both of my projects on code.google.com are also open source but it's a whole different level). Most of my contribution to Wesnoth has been bug fixes and other minor work, though I have had several larger contributions. There is a list of these below.

Gaming experience - Are you a gamer?

1. What type of gamer are you?
   • I am a diverse gamer. I've been playing games for more than 80% of my life (wow, just realized how long it has been)
2. What type of games?
   • I like pretty much all genres. Yet, my favorites tend to be strategy games or rpgs. And those that find a good blend of the two are great. For example, Battle for Wesnoth (some others, too--Final Fantasy Tactics comes to mind).
3. What type of opponents do you prefer?
   • Smart ones. I love the challenge of trying to outplay a smart player.
4. Are you more interested in story or gameplay?
   • It depends. Generally when I am playing single-player games story and gameplay are both important though I am more likely to accept below average gameplay for an above average story than vice-versa. Playing multiplayer, particularly competitive multiplayer, gameplay is much more important.
5. Have you played Wesnoth? If so, tell us roughly for how long and whether you lean towards single player or multiplayer.
   • I have played Wesnoth for a bit over a year. I had focused on single player campaigns but in the last two months have shifted to almost only multiplayer.

Communication skills

1. Though most of our developers are not native English speakers, English is the project's working language. Describe your fluency level in written English.
   • I am fluent in written English. I had better be as I am definitely not in any others.
2. Are you good at interacting with other players? Our developer community is friendly, but the player community can be a bit rough.
   • Yes, I am good at interacting with other players and with other people in general.
3. Do you give constructive advice?
   • I think that I give constructive advice. I have been a tutor in math and computer science for a couple years and a sailing instructor for longer. Both of these have definitely improved my ability to give constructive advice.
4. Do you receive advice well?
   • Yes, I do. I feel that a factor in this is that I am always interested in learning more and advice often offers an opportunity to do that.
5. Are you good at sorting useful criticisms from useless ones?
   • Yes.

Project

1. Did you select a project from our list? If that is the case, what project did you select? What do you want to especially concentrate on?
   • I chose to work on the optimization of wml for memory usage problem.
2. Why did you choose this project?
   • I chose this project because I enjoy working with algorithms and data structures, and, in particular, I enjoy the challenge of finding better ways of doing things. I think that this project will be a chance for me to do that.
3. Include an estimated timeline for your work on the project.
   • See timeline below.
4. Include as much technical detail about your implementation as you can
   • See technical details below.
5. What do you expect to gain from this project?
   • .
6. What would make you stay in the Wesnoth community after the conclusion of SOC?
   • .

Practical considerations

1. Are you familiar with any of the following tools or languages? Subversion, C++, Python, build environments
   • I am very familiar with C++. I have used subversion enough that I can do the basics, I am not very familiar with creating and merging branches. I only have a little experience with both Python and build environments. With either of these, I currently can only do the most basic tasks.
2. Which tools do you normally use for development? Why do you use them?
   • Currently, I do almost all of my development in Linux, with a text editor, gdb and other command-line tools. Linux in general just makes development so much easier and the tools it provides are very powerful. In Windows (which I haven't really developed in in almost a year) I use Visual Studio 2005/2008. For debugging I feel it is even better than the tools available in Linux, and it has a few other nice features that may improve my productivity.
3. What programming languages are you fluent in?
   • I am very fluent in C++, and less so in Java. For example, I know the C++ standard library very well and I know many of the C++ idioms, but am not as familiar with Java's. I have some experience with C, Scheme and SML, and less with Python and Prolog.
4. What spoken languages are you fluent in?
   • English.
5. At what hours are you awake and when will you be able to be in IRC (please specify in UTC)
   • I am generally awake from 1:00pm to 5:00 am UTC and will be available most of that time.
6. Would you mind talking with your mentor on telephone / internet phone? We would like to have a backup way for communications for the case that somehow emails and IRC do fail.
   • I would not mind that at all.

My contributions to Wesnoth

Larger patches and other substantial contributions

unit_map
Originally redesigned this in early 2008 to have iterators that would be updated as a unit is moved and that would know when they become invalidated. Also added some more powerful iterators/accessors.[1][2] Recently I have refactored this a bit, templatizing the iterators. Even better, I greatly improved the documentation of the interface. [3]

gui2 text box history
I added support for text box history to gui2. [4]

Profiling and some optimization
I have google performance tools working with Wesnoth to do some profiling. Originally I set this up as being able to profile memory usage and cpu usage will be important to this project. I have some results of this up at another page.
While doing some profiling I found a couple of bottlenecks in the code.
First, image::locator::locator() was using ~8-10% of the time in-game. I rewrote its lookup to use a hash-based map and cut the time the function used in half. [5]
Second, I changed the algorithm that we used to determine what rectangles to redraw. This shows significant gains in some graphics-intensive situations (as much as 3x fps).[6]
Third, I am doing some work on the tokenizer used for parsing wml that shows a 10-20% speedup of WML loading at the cost of significant complexity. I'm not sure yet that this is worth it without first optimizing the underlying preprocessor stream that the tokenizer gets its input from.

Smaller changes and bug fixes

Report an error when a macro is not resolved and is not a filename.[7]
Very simple bug fix.[8]
Prevent duplicate advances_from entries.[9]
Fix bug #13003.[10]
Fix bug #12990.[11]
Began to refactor the attack class.[12]
Fix bug #11031.[13]
Fix bug with KNOCKBACK and similar wml.[14]
Simplified unit_map lookup by id.[15]
Improved error message when attempting to dereference invalid iterator.[16]