SummerOfCodeProposal 2011 LuaAI JodyNorthup

This page is related to Summer of Code 2011

See the list of Summer of Code 2011 Ideas

This is a Summer of Code 2011 student page

Project: SoC_Ideas_LuaAI_2011

Description

Jody Northup - Improve and extend Lua AI scripting facilities

This is the Lua AI improvement idea.
If I am accepted for this project, I will bring the Lua AI scripting functionality up to par with the current C++ AI programming functionality by first exposing all of the C++ AI support functions to Wesnoth's Lua API, and then adding WML utilities to include and handle custom Lua AI code in WML modules.
I expect the first step to involve an in-depth analysis of the C++ AI functions and an inventory of the gaps in the currently-implemented Lua AI API, followed by tedious Lua API programming to expose each of those functions. I expect that the second step will involve communication with the development community to determine good WML specifications for the use of Lua AI code in UMC modules.

IRC

Upthorn, Upth

SoC Application

SoC Application

Questionnaire

(Largely copied from my successful application last year)

Basics

Write a small introduction to yourself.

My name is Jody Northup. I am a 26 year old college student from the United States. Under normal circumstances, I should have graduated by now, but there have been a number of obstacles on my route to academic success.

I have been programming since I was introduced to C++ in the summer of 1999.

State your preferred email address.

upthorn@gmail.com

If you have chosen a nick for IRC and Wesnoth forums, what is it?

• irc: Upthorn
• irc alternate: Upth
• Wesnoth forums: Upthorn
• gna.org: Upthorn

Why do you want to participate in summer of code?

It is a good opportunity to gain experience in aspects of programming that aren't covered in classes, it is a great way to contribute to the open source community on projects that I believe in or even make use of myself, being able to contribute usefully to something gives me a great sense of accomplishment, and it is much more fun than any other summer job opportunity I know of.

What are you studying, subject, level and school?

I'm an undergrad with an undeclared major at Sacramento City College. In terms of credit earned, I am in my fourth year, in terms of time spent I am in my 6th year, and in terms of the length of time remaining until I graduate, I might as well be halfway through my 2nd year. In another year I hope to transfer to the University of Maryland, where I plan to double-major in Computer Science and Linguistics, getting a simultaneous degree in both if possible.

What country are you from, at what time are you most likely to be able to join IRC?

I live on the west coast of the United States (UTC-7 during the summer), but my sleep schedule is fairy flexible. I am generally available on IRC between around 18:00 and 9:00 UTC, but I can change this during the coding period if it is inconvenient to my mentor. Until my class period ends, I will have limited availability on Mondays.

Do you have other commitments for the summer period ? Do you plan to take any vacations ? If yes, when.

I have a recurring social engagement all day every Wednesday, but this commitment can be cancelled if there is urgent work to be done. I also have D&D from 18:00 to 0:00 on Friday nights (1:00 to 7:00 Saturdays, UTC). Additionally, I would like to take up an additional part-time job during the summer if I can fit one into the schedule, but there are no definite plans around this at the moment.

Experience

What programs/software have you worked on before?

• A variety of programming projects for high school and college classes
• I have hacked around quite a bit on open source emulators. Primarily the rerecording branch of gens (see TASVideos.org introduction and these forum threads for more information, with some work also being done on snes9x and mupen64. Relevantly, my work on gens has included some additions/improvements to its Lua API.
• I have done a great deal of feature programming and debugging work on the Sonic 1 MegaMix romhacking project for the sega genesis.
• I have done some simple reverse engineering work to examine a simple archive file format and help create a translation patch for the Japanese indie game Bunny Must Die.
• I have done some minor testing and debugging work on a project to encapsulate windows games in a deterministic environment, allowing input to be recorded and replayed without concern for RNG input from the system clock, or other sources.
• I worked on ScummVM for Summer of Code 2009, implementing an API to allow engine modules to negotiate with backend modules to determine color depth.
• I implemented Wesnoth's persistent data WML extension for Summer of Code last year.

Have you developed software in a team environment before? (As opposed to hacking on something on your own)

Yes, I frequently collaborate with other developers in my development of gens, and Sonic 1 Megamix, as well as having worked in pair and group projects for classes. And, of course, I contributed to ScummVM for 2009's Summer of Code, as well as Battle for Wesnoth during 2010's.

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 participated in 2009's summer of code as a student for ScummVM. My project was providing support for RGB color games (Note: dead link pending assistance from melange team to update). I was successful, but had a great snag towards the end as I completed my project as proposed before the midterm, went on a pre-arranged 2-week vacation, and had a great deal of difficulty with the project I was assigned to work on for the remainder of the summer of code period. I participated in 2010's summer of code as a student with Battle for Wesnoth. My project was to extend WML to support persistent data for UMC developers. I was assigned Crab as a mentor, and had a very positive experience, in which I learned a lot about WML parsing, and where the errors lie in my approach to software development. My project took the entire length of the coding period, and was completed successfully with his guidance.

Are you already involved with any open source development projects? If yes, please describe the project and the scope of your involvement.

I have been the project maintainer and coordinator of the Gens-rerecording project since about mid-2006, having produced many new features, created a google code project page, and organized the development of many more during that time.

Gaming experience - Are you a gamer?

Yes, I enjoy games, although lately I haven't been playing them as much as I used to.

What type of gamer are you?

I am an obsessive perfectionist when it comes to gaming. I always try again and again until I get the best possible outcome, and I've collected all the items. Sometimes the frustration from this will drive me to save-scum, or edit my saves outright.

What type of games?

I love all types of games, from real time strategy (command & conquer, starcraft, total annihilation) and turn-based strategy (wesnoth, civilization) to RPGs (Planescape: Torment, Skies of Arcadia), adventures (King's Quest, Space Quest, The Void/Тургор), platformers (Sonic the Hedgehog, Mario) and racing games (Virtua Racing, Burnout) and even to First person shooters (Deus Ex, Unreal Tournament) and simulations (Escape Velocity, Dwarf Fortress)

What type of opponents do you prefer?

I prefer opponents that are on the same level or slightly better than me (so, generally, ones that are not very good).

Are you more interested in story or gameplay?

I cannot choose between story and gameplay. In the best games, there is no separation between the two, but either can hold up a good game on its own.

Have you played Wesnoth? If so, tell us roughly for how long and whether you lean towards single player or multiplayer.

Yes, I got hooked on wesnoth during my vacation in 2009, and the Heir to the Throne campaign became one of the greatest difficulties I had in accomplishing additional work for ScummVM. I am not very good at strategy games, so I have not even attempted multiplayer yet (except to the extent of debugging Persistence WML in multiplayer contexts.)

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 GSoC. If you have gained commit access to our S­­V­­N (during the evaluation period or earlier) please state so.

• I did submit a patch to correct the VC9 project files, but then I realized it was a duplicate of one from three weeks earlier.
• Patch 1612 -- implements Sapient's proposed changes to allied healing.
• Patch 1619 -- provides prototype implementation of Crab's proposed WML syntax for saving/loading persistence data.
• I gained commit access to the BfW S­­V­­N during (or slightly before) the coding period for last year's Summer of Code. It appears that I still retain this access.
• Revision 49222 -- corrects a long-standing bug which caused MSVC9 compiled Wesnoth to crash when parsing a [trait] that lacks a description
• Revision 49223 -- exposes suitable_keep() c++ AI helper function to the Lua AI library.
• Revision 49236 -- updates suitable_keep() Lua AI handler not to use obsolete code pattern shown in other Lua AI function handlers.

3) Communication skills

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 a native English speaker, and my proficiency with written English is better than average.

What spoken languages are you fluent in?

I am a fluent native speaker of English, can communicate alright in Japanese, and am at a basic level in Mandarin and Korean. I was unfortunately unable to learn Russian this year, due to scheduling conflicts.

Are you good at interacting with other players? Our developer community is friendly, but the player community can be a bit rough.

I do not know about wesnoth players specifically, but I am fairly good at interacting with players of other games. I tend to be friendly and open, and I understand that the other players' insults and other such things are just for fun and don't mean anything.

Do you give constructive advice?

I do give constructive advice whenever I can, although sometimes I think I cause offense by mistake. I always try to think my criticism through so that there is a clear indication of how the aspect could be improved.

Do you receive advice well?

I believe so, as long as it is clear and helpful.

Are you good at sorting useful criticisms from useless ones?

I think I am pretty good at sorting helpful criticism from bikeshed painting, yes.

How autonomous are you when developing ? Would you rather discuss intensively changes and not start coding until you know what you want to do or would you rather code a proof of concept to "see how it turn out", taking the risk of having it thrown away if it doesn't match what the project want

I like to keep a good balance between discussing changes and coding proof of concepts. In 2009's summer of code, I had to interact extensively with the development community in order to design a useful API for them, but at times when it wasn't clear what the community preference was, I would make a proof of concept to demonstrate the features and drawbacks of a given method. Some of the work would be thrown out, but I did my best to maximize the amount of work that could be reused on a different method. During last year's summer of code, the project specifications were almost entirly a collaboration between myself and my mentor, which allowed me to take a much more independent approach in designing my solution, therefore involving much less refactoring and wasted effort.

Project

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?

Yes: I selected the Lua AI improvement project from your ideas list. I would like to focus on ensuring that UMC authors can easily include custom Lua AI code in their modules.

Why did you choose this project?

1. AI is an interest of mine that has always felt unapproachable, and this seems like it would provide a good opportunity to learn how AI works in a game.
2. Customizability seems like one of Wesnoth's strongest "selling point"s, and if scripted AI routines are second-class citizens, difficult to use and unable to replicate hard-coded functionality, it is a major hole in Wesnoth's support for customization. In other words: it seems like a very useful goal, and I would like to improve wesnoth in a meaningful way.
3. I wanted to challenge myself more this year than I have on previous years. Working on or around AI scares me a little bit, and I want to find out if my fears are founded or not.
4. I have worked on extending an application's Lua interface before, and am confident that I can accomplish that in a timely manner.

Include an estimated timeline for your work on the project. Don't forget to mention special things like "I booked holidays between A and B" and "I got an exam at ABC and won't be doing much then".

Pessimistic:

• Now - May 23: Research the C++ AI functionality and the Lua AI functionality. Assess gaps.
  • Milestone: By May 24th, know which C++ functions are not yet exposed.
• May 23 - July 15: Bring Lua AI functionality up to par with C++
  1. Expose C++ AI functions to Lua (by July 8th)
  2. Provide thorough documentation for newly exposed Lua functions (by July 15th)
  • Milestone: By July 15th (Midterm), Lua AI has documented access to all C++ AI functionality.
• July 15 - July 27th:
  1. Implement Lua script manager to track files loaded by wesnoth.require and wesnoth.dofile (by July 20th)
  2. Ensure that each such external Lua file is loaded into memory only once, regardless of how many modules it is called from. (By July 27th)
  • Milestone: By July 27th Lua scripts can be called in multiple modules with minimal additional overhead
• July 27th - August 26th: Implement unit grouping concept for AIs
  1. Fully determine [group] tag specifications (By August 2nd)
  2. Implement group tag (By August 19th)
     1. Extend WML engine to parse and process [group] (By August 7th)
     2. Extend Lua interface to support group-based commands (Due by August 14th)
     3. Extend Lua interface to allow creation, deletion, and customization of groups (by August 19th)
     4. Update wiki documentation of GroupWML and Lua to be thorough and coherent(by August 26th)
  • Milestone: By August 26th (Final deadline) Lua AI can be scripted by UMC devs with full functionality of C++ AI, can be easily included in WML modules, and can make use of unit-grouping for fine-grained control of AI behavior. Additionally, all of these features are thoroughly documented on the wiki.

Optimistic:

• Now - May 23: Research the C++ AI functionality and the Lua AI functionality. Assess gaps. Begin correcting.
• May 23 - June 13: Finish exposing C++ AI functions to Lua
  • Milestone: By June 13th, Lua AI has access to all C++ AI functionality.
• June 13 - June 20th:
  1. Implement Lua script manager to track files loaded by wesnoth.require and wesnoth.dofile
  2. Ensure that each such external Lua file is loaded into memory only once, regardless of how many modules it is called from.
• June 20th - July 15th: Implement unit grouping concept for AIs
  1. Fully determine [group] tag specifications
  2. Implement group tag
     1. Extend WML engine to parse and process [group]
     2. Extend Lua interface to support group-based commands
     3. Extend Lua interface to allow creation, deletion, and customization of groups
     4. Update wiki documentation of GroupWML and Lua to be thorough and coherent
  • Milestone: By July 15th (midterm), Lua AI can be scripted by UMC devs with full functionality of C++ AI, can be easily included in WML modules, and can make use of unit-grouping for fine-grained control of AI behavior. Additionally, all of these features are thoroughly documented on the wiki.
• July 15 - August 26: Use community input and iterative design/debugging to address perceived shortcomings in the Lua AI system, documenting solutions as I go.
  • Milestone: By August 26th, Lua AI scripting is easy and useful to UMC community standards.

Include as much technical detail about your implementation as you can

As in my prior application, I have moved this to Project Details for organization and ease of reading.

What do you expect to gain from this project?

A better understanding of AI concepts, experience working with game AI, a better understanding of my capacities as a programmer, a sense of having been able to do something useful for someone besides myself, and a nifty t-shirt from google.

What would make you stay in the Wesnoth community after the conclusion of SOC?

My interest in the project itself, and any relationships I might forge with community members during the coding period, and the free time to make a meaningful commitment to wesnoth development.

Practical considerations

Are you familiar with any of the following tools or languages?

   * Sub­­version (used for all commits)

Yes, I have used it extensively for gens development, megamix development, my work on ScummVM in 2009, and my work on Wesnoth last summer.

   * C++ (language used for all the normal source code)

Yes, I have been working with C++ for nearly 11 years now.

   * STL, Boost, Sdl (C++ libraries used by Wesnoth)

I am fairly familiar with the STL, and worked almost exclusively with SDL on ScummVM in 2009. I am new to Boost, but in the past I have been able to catch on to these things fairly quickly with a little bit of practice.

   * Python (optional, mainly used for tools)

I have worked with python somewhat, contributing a few minor bugfixes to the Civilization 4 mod "Fall From Heaven II"

   * build environments (eg cmake/autotools/scons)

I do not have any experience with cmake, autotools, or scons.

   * WML (the wesnoth specific scenario language)

I have some minor experience with WML, from editing my own wesnoth savegames last summer.

   * Lua (used in combination with WML to create scenarios)

I have experience both in scripting Lua, and in working with the Lua C API to provide hooks and bindings.

Which tools do you normally use for development? Why do you use them?

• C/C++: I generally use Microsoft Visual C/C++, because I am familiar with it from classes, and because it provides a very useful debugger that allows me to trace problems to their source quite quickly. I have used Dev-C++ in the past, though.
• Java: Eclipse, because it was recommended to me and I do not know anything about the others, and also because it provides a very useful debugger facility.
• Lua: I just use Crimson editor, because it has support for Lua syntax highlighting, and Lua is interpreted, not compiled.

What programming languages are you fluent in?

C, C++, Lua, Java, Javascript.

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. If you are willing to do so, please do list a phone number (including international code) so that we are able to contact you. You should probably *only* add this number in the application for you submit to google since the info in the wiki is available in public. We will *not* make any use of your number unless some case of "there is no way to contact you" does arise!

I have provided my phone number in the application at google.

Project Details

Overview

I will improve and extend wesnoth's support for custom Lua AI scripts in two major steps
Step one involves use of the Lua API to create several Lua interface functions to invoke C++ functions from, and seems fairly straightforward.
Step two involves the extension of WML and the Lua API in order to better facilitate creation and customization of AIs, and is significantly more complex.
For step two, I propose a couple of extensions and modifications to WML

[Lua] and [AI] tag enhancement

I propose to add a "source" element to [Lua] and [AI] tags as an alternative to the "code" element. The source element will specify the relative path to a Lua file which contains the desired Lua code.
Files loaded from the "source" element in these tags will be indexed globally so that multiple WML modules can reference the same Lua script file without causing the file to be loaded into memory multiple times.

[group] tag

I propose to create a "[group]" tag for scenario authors to specify AI scripts per-group of units. This would be accompanied by a "[groups]" subtag in unitWML, which contains a unit's group memberships in priority order. Additionally a group could be associated with a standard unit filter in order to automatically apply itself to all new units created which match the filter.
Additionally, the Lua API will be extended to allow Lua scripts to send messages to unit groups, so that groups can be dynamically created and commanded during the execution of a scenario. This will be accomplished by significant additions to the WML parsing engine to teach it about the new unit group concept, creation of an as-yet indeterminate number of Lua or Lua API functions yet to be named, and possibly a group-related extension to Standard Unit Filters.
Proposed syntax for the [group] tag is provided below, in the proposed WML extension section.

Deliverables

Mandatory

1. Full exposure to Lua of C++ AI support functions. -- Due by July 15th
   • C++ AI support functions exposed to Lua interface -- Due by July 8th
   • Wiki documentation of all additions to Lua interface -- Due by July 15th
2. Lua loadable non-redundantly into WML from external files -- Due by July 27th
   • Lua file-loading deduplication functionality -- Due by July 27th
     • Script manager tracks files loaded by wesnoth.dofile and wesnoth.require -- Due by July 20th
     • Script manager compares new requests to files already loaded, and return reference to the loaded file -- Due by July 27th
3. [group] tag -- Due by August 26th
   • Fully define [group] tag syntax specification-- Due by August 2nd
   • Implement grouping -- Due By August 26th
     • WML engine extensions to parse [group] tags and assign one-time StandardUnitFilter groups to relevant units. -- Due By August 7th
     • Lua interface extensions to support AI issuing commands by group (including continually updated StandardUnitFilter groups) -- Due by August 14th
     • Lua interface extensions to allow adding and removing of specific units and unit filters to and from specific groups -- Due by August 19th
     • Update wiki documentation of GroupWML and Lua to be thorough and coherent -- Due by August 26th

Optional

To be determined via discussion with mentors and UMC development community.

Proposed WML extensions

[group] tag

Basic syntax

My current thinking is that a group tag will look like this

   [group]
     id=some_group_identifier
     automatic=no
     [filter]
       {optional StandardUnitFilter}
     [/filter]
     [ai]
       {optional AI specification}
     [/ai]      
   [/group]

The id element is the only mandatory element of the group tag. The other tags specify certain automated behaviors that apply to the group. An explanation of each element follows:

id

A group id will be some locally unique identifier for the group. This is the name that will be used to issue orders to members of the group, or to add or remove units from the group's membership.

automatic

The element "automatic" is a boolean element that specifies whether the wesnoth game engine should track and update the group's membership according to a supplied StandardUnitFilter.
The default value is "no", and a value of "yes" requires that the group have a StandardUnitFilter associated.

[filter]

This child tag will specify a StandardUnitFilter to which the group membership should be applied.
If automatic is yes, the [filter] tag is mandatory, and group membership will automatically be updated such that all units matching the filter are considered members, and no units not matching the filter are.
If automatic is no, units matching the filter will be added to the [group] at the time of the group's formation, but any further additions to or removals from the group will require an explicit WML or Lua command.

[ai]

This optional child tag will specify a supplementary ai to control member units. Groups without an [ai] child tag will be controlled by the overall [side] ai.

UnitWML extension

To facilitate the use of groups, I propose to extend Unit data to include a subtag [ai_groups]

Basic Structure

The basic structure of the [ai_groups] tag will be as follows

   [ai_groups]
     1=some_group_identifier
     ...
     n=yet_another_group_identifier
   [/ai_groups]

Each element shall be a number, associated with the id of an extant and valid [group] tag. The number shall be the priority of group membership, such that if two groups are issued conflicting orders, a unit with membership in both gruops will only follow commands issued to the group with the lowest priority number.
For example, assume an elven archer unit is assigned to a "forest_patrol" group and a "ranged_units" group such that

   [ai_groups]
     1=forest_patrol
     2=ranged_units
   [/ai_groups]

A command is issued to forest_patrol for all member units to move along a circular route within a particular patch of forest and a command is then issued to ranged_units to assault the enemy keep. The elven archer in question will ignore the command issued to ranged_units and continue to walk along its circular patrol.
If, instead, the command issued to ranged_units was to prefer attacking swordsmen over archers, the elven archer in question would obey both orders, walking along its circular patrol, and attacking swordsmen in its range, but not archers.

[group] modification actions

In addition to the wml extensions specified above, I propose a set of actions to allow WML authors to maintain groups manually.

Basic syntax

   [add_to_group]
     unit_id=some_unit
     group_id=some_group
     priority=1
   [/add_to_group]

   [add_to_group]
     [filter]
       StandardUnitFilter
     [/filter]
     group_id=some_group
     priority=1
   [/add_to_group]

   [remove_from_group]
     unit_id=some_unit
     group_id=some_group
   [/remove_from_group]

   [remove_from_group]
     [filter]
       StandardUnitFilter
     [/filter]
     group_id=some_group
   [/remove_from_group]

   [clear_groups]
     unit_id=some_unit
   [/clear_groups]

   [clear_groups]
     [filter]
       StandardUnitFilter
     [/filter]
   [/clear_groups]

   [delete_group]
     group_id=some_group
   [/delete_group]

   [set_group_ai]
     group_id=some_group
     [ai]
       AI Specification
     [/ai]
   [/set_group_ai]

   [clear_group_ai]
     group_id=some_group
   [/clear_group_ai]

[add_to_group] adds a single unit (specified in unit_id), or all units matching a [filter] to a group (specified in group_id). If the group does not exist it will be created. The optional priority element specifies what priority level to mark the new group memberships, and defaults to 1. The new membership will take priority over existing memberships with equal or lesser priority value.
For instance, taking the elven_archer from our previous example, if we run

   [add_to_group]
     unit_id=elven_archer
     group_id=test_group
     priority=2
   [/add_to_group]

the elven_archer's resulting memberships will be

   [ai_groups]
     1=forest_patrol
     2=test_group
     3=ranged_units
   [/ai_groups]

[remove_from_group] removes a single unit (specified in unit_id), or all units matching a [filter] from a group (specified in group_id). If the group does not exist, nothing happens.

[clear_groups] removes a single unit (specified in unit_id), or all units matching a [filter] from all current groups. spec [delete_group] destroys a current group (specified in group_id) and removes all units from its membership. If the group does not exist, nothing happens.

[set_group_ai] changes the supplementary ai running in a current group (specified in group_id) to the one specified in the [ai] child tag. If the group does not exist, it will be created.

[clear_group_ai] removes the supplementary ai running in a current group (specified in group_id) and reverts all members to the overall [side] ai. If the group does not exist, nothing happens.

Additionally these actions shall all be callable from Lua.

StandardUnitFilter extension

In order to address units by group membership, I propose to add a "group" attribute to allowable unit filters. A [filter] containing a group attribute will only return units that are members of the group whose id is specified in the attribute.