Expanding Hedgehog AI

 

1) Basics

1.1) Write a small introduction to yourself.

Hi, my name is David Young or dayoung on IRC.  Having been around computers, games, and programming all my life I find that I still can’t get enough.  I mean how many 25-year-old programmers started on 286 MS-DOS computers over 20 years ago, that’s me though.  I hold both a BS in Computer Science a MS in Computer Science and currently pursuing a second MS in Computer Science while simultaneously working full time as a Software Engineer for the past 3-4 years ever since my Bachelors.

It’s probably pretty weird to see someone pursing a second Masters but for me I thought it was the opportunity of a lifetime.  I specialize in Game Artificial Intelligence at the University of Southern California, the number 1 Game Development school in the United States at the same time as working full time writing mission critical ground systems for NASA.

Professionally I get to work with all sorts of people that are incredibly intelligent, and are all specialists in their own fields.  Feel free to visit this site for just a little information on the current mission I work on and don’t worry! we already delivered our final ground systems release over 6 months before launch.

http://marsprogram.jpl.nasa.gov/msl/

Academically and what I do for fun (hint, coding), is up on my online portfolio at:

http://www.goliathdesigns.com

1.2) State your preferred email address.

dayoung@goliathdesigns.com

1.3) If you have chosen a nick for IRC and Hedgewars forums, what is it?

dayoung

1.4) Why do you want to participate in Google Summer of Code?

I want to code of course! But besides just that, I want to give back to great open source communities after having used so many great open source projects and games.

Being an avid gamer and game AI programmer I want to apply the skills I have to make open source games even more engaging for players, hopefully finding a open source community that I can become an active part of and continue to help develop far after Google’s summer of code.

1.5) What are you studying, subject, level and school?

Currently I’m pursuing a second Masters in Computer Science, this time specializing in Game AI/Game Development at the University of Southern California.  My specialty in Game AI doesn’t stop there though, I program physics systems, animation systems, graphics, gameplay, etc, but AI is definitely my main passion and expertise.

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

I’m from the United States and in particular California, the PST time zone (GMT – 7).  I will be in IRC 24 hours a day most likely from both my work PC and home PC.  I will be most active after 5pm PST but I will check in sporadically throughout the day.

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

I currently work full time as a Software Systems Engineer but I’m definitely used to working full time and going to school full time.  Managing both a full time job and being a full time student ever since my Bachelors have taught me critical time management skills that are necessary to ensure deadlines are met.  Not taking classes in summer frees up a ton of time for me that I plan to fully dedicate to more coding! 

I understand that the Hedgewars organization might have an issue with working full-time and also participating in GSoC full-time.  Please let me give you an example of what my typical load includes to reassure you that I am definitely capable to accomplish both outstandingly. 

While working for the NASA Deep Space Network, I held both a full time job, took double the course work of a full-time Master’s Graduate in Computer Science, completed and implemented my thesis and defense in a single quarter, and completed the Masters program in a single year.  No other CS Graduate from my University has ever completed the Masters program in a single year due to the incredible work required in writing and defending a thesis.  My thesis of course was also in Game AI!

As for anything else I’m not planning on any vacations or any other reason that will stop me from coding!

2) Experience

2.1) What programs/software have you worked on before?

For my day job I work on the mission critical ground systems for the next Mars rover mission for the NASA Jet Propulsion Laboratory. (Java/Python/Sql)  The next generation ground systems is the first ground systems to ever be multi-mission and will be used in upcoming and future NASA missions.

For my academic pursuits I’ve created and work on the AI module to the USC GamePipe game engine.  The USC GamePipe engine integrates industry technologies such as Ogre3d, Havok, RakNet, as well as custom libraries in order to be a generic game engine for students to build games and prototypes.  I architected and implemented the C++/Lua generic AI system currently used by students in games and prototypes.  I’m still actively developing for the engine to expand what the AI is capable of.

On my own time for fun I’m currently working on an Unreal Tournament 2004 bot to enter in the CIG2011 and CEC2011 human-like AI bot competitions. (C++/Java)

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

To date I’ve worked on and continue to work on teams of numerous sizes, complexities, and skill levels.

Professionally I work on a medium sized team with very fixed deadlines, schedules, performance requirements, testing schedules, task breakdowns, reviews, you name it!

Academically I work on the USC GamePipe engine in a medium sized team.  I’ve led smaller groups focusing on AI while at the same time working with numerous other groups to have the AI integrate with graphics, physics, animation, live editor, etc.

On my own time I work on both small group projects, usually 2-3 people max, and also work on one-man projects of my own.   I try and participate in Global Game Jams and plan on participating in the next upcoming Ludum Dare with a few other friends.

2.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?

This is my first time applying for Google Summer of Code and I’m definitely looking forward to it!

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

Although I haven’t joined into the development of an open source project I’ve open sourced projects of my own as well as been involved using the bleeding edge of some open source projects such as the Zend Framework and the Brood Wars API.

2.5) Gaming experience - Are you a gamer?

I’ve been a gamer ever since I’ve had access to a computer!  Since the age of 5 I was already playing DOS games on my 286

Steam ID: http://steamcommunity.com/id/goliathI3/

Xbox Live ID: http://live.xbox.com/en-US/MyXbox/Profile?gamertag=goliath%20I3

2.5.1) What type of gamer are you?

I’d probably match the bill for both a hard-core gamer as well as a casual gamer.  I play games actively on the PC, Xbox 360, PSP, Mobile, and Browser.

2.5.2) What type of games?

I play all sorts of games, from fps, to rts, to strategy, rpg, casual, etc etc.

Lately I’ve been finding myself playing more and more indie games as well as student made games, which fall into many different genres.

2.5.3) What type of opponents do you prefer?

I have a soft spot for playing against AI’s.  I enjoy analyzing how the AI is performing actions to see what I can learn from the AI implementation.  Playing with and against human counter parts though typically provides a much more diversified experience in the long run after figuring out the AI system.

2.5.4) Are you more interested in story or gameplay?

Gameplay definitely wins me over.  Probably going more toward my indie side I find that great gameplay can suck a player into a game more than a great story and poor gameplay ever can.

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

We do not plan to favor Hedgewars players as such, but some particular projects require a good feeling for the game which is hard to get without having played intensively.

I’ve just started playing Hedgewars but have a long history and love of the Worms franchise.  I unfortunately was totally unaware that Hedgewars even existed because to be honest it is far superior to Worms! And better yet it’s open source and multiplatform compatible.

For the time being I tend towards playing multiplayer because the single player AI is still at its infancy, which is the whole reason I’m applying for GSoC!!

3) Communication skills

3.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.

My primary language is English and I am fluent in both reading and writing.

3.2) What spoken languages are you fluent in?

I am fluent in speaking English.

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

Being both a gamer and developer I find myself good with interacting with both developers and the community.  I think it comes from both wanting and waiting for all these cool new features and understanding what it takes to actually create them.

3.4) Do you give constructive advice?

I typically don’t beat around the bush so to speak.  I will let people know what needs to be done, but at the same time be constructive in how I approach the situation and person.

3.5) Do you receive advice well?

I am always open to seeing different sides of a situation.  I think it’s critical that a person not be closed off to other people’s views.  No one is ever perfect and other views of the situation can provide great insight into problems.

3.6) Are you good at sorting useful criticisms from useless ones?

I’m always open to criticism but a person needs to be focused and understand when certain criticism stops being constructive.  I think navigating both office politics and academic waters have made me very experienced at sorting through useful criticism and useless ones.

3.7) 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 think this really depends on the project.  For games sometimes a risky experiment is worth the payoff especially with prototyping ideas.

I like to have a solid background of the information and then typically start coding the solution I believe would solve the problem.  For games this means I like to know what is trying to be accomplished and how it fits within the game itself.

Fast iterations I find more helpful than either lengthy designs or throw away prototype code.

4) Project

4.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?

When I saw that AI was one of the project ideas, I immediately selected it.  Since my specialty is in Game AI I thought the project idea matched perfectly with my own expertise and skills.

For concentration I’ve outlined my plans and milestone deliveries on the Hedgewars forums at http://www.hedgewars.org/node/2887 and below in the technical details portion.

4.2) If you have invented your own project, please describe the project and the scope.

Not necessary.

4.3) Why did you choose this project?

I chose Hedgewars AI because of my love of programming Game AI.  I choose to specialize in Game AI though because I’m fascinated in how computers are able to play games.   Playing games is second nature but it’s intriguing to understand how games are broken down for AI to be able to process, plan, and interact.  Game AI is still very much at its infancy, even in industry and I believe that there are still tons of innovations and new discoveries just waiting to be realized by programmers.

4.4) 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".

March 28^th – May 23^rd –

Begin familiarizing with the Hedgewars code base, structuring the AI changes and implementing additional AI weapons which don’t require drastic changes to the AI code base. Documenting the current AI features in the Hedgewars wiki as well as documenting the Pascal code in Pasdoc format.

May 23^rd – June 6^th –

Milestone One development and delivery on June 6^th.

June 6^th – June 20^th –

Milestone Two development and delivery on June 20^th.

June 20^th – July 11^th –

Milestone Three development and delivery on July 11^th.

July 11^th – July 25^th –

Milestone Four development and delivery on July 25^th.

July 25^th – August 15^th –

Milestone Five development and delivery on August 15^th.

August 15^th – August 26^th –

Code cleanup, documentation, and final delivery of the source code. On August 26^th.

4.5) Include as much technical detail about your implementation as you can

My implementation details and milestone deliveries are available both below and on the Hedgewars forums.

http://www.hedgewars.org/node/2887

The current state of the AI

First Milestone

For the first milestone of the Google Summer of Code the improvements to the Hedgewars AI would focus on adding additional weapons to the current structure of the AI.  No structural changes would be done to the AI, merely new weapons would be added.

Additional Weapons would be the majority of the first milestone delivery including

Deliverables

• DrillRocket
• Hellish Hand-Grenade
• SniperRifle
• Flamethrower
• Dynamite
• Ballgun
• StickyMine

Technical Outline for First Milestone

DrillRocket - Internally to calculate the valueResult the implementation will be very similar to TestDesertEagle with changes to distance checks the rocket can go through terrain.  An additional check will calculate how much estimated damage the target will incur.

Second Milestone

The second milestone would focus on adding "Modifiers" the AI would trigger as well as AI aiming.  Modifiers would include vampirism, invulnerability, etc which the AI would trigger to take advantage of additional damage or health.

Currently the AI Aims to hit the enemy.  Although this inflicts the most amount of direct damage the AI misses out on knocking enemies into the water or closer to mines.

AI Aiming

The AI's typical trajectory is the red arc, while the blue arc would actually deal less damage but consequently knock the enemy hedgehog into the water.

Offset Aiming

An additional aiming issue for the AI is the concept that the bullet does not begin at the Hog's location(Red).  Currently all aiming is calculated at the Hog's X and Y instead of at the barrel of the gun(Blue).  In Hedgewars 0.9.15 the offset bullet spawn is disabled due to the fact the AI isn't currently able to account for that.

Deliverables

• Invulnerable
• Vampirism
• Extra Damage

• Improved Aiming

Third Milestone

The third milestone would add additional "Move" abilities to the AI.  Currently the AI has limited movement abilities even when poorly positioned, clustered together, inside of holes, near water etc.  Moves which qualify as a complete move would be added first to the AI to minimize structural changes.

Moves that allow for additional attacks/moves within the same turn would require structural changes to how the AI processes during a turn.

Avoiding impending water

When an AI is very near to a body of water, or near an edge of a cliff or hill the AI should prioritize moving to a better location.  Currently the AI will still only try to attack enemies instead of moving for their life.

In sudden death as the water rises the AI will still remain stationary even when the AI will drown at the end of the turn.

Avoiding impossible shots for difficulty

Currently the AI uses a random deviation in where to target based on the difficulty level.  Higher difficulties deviate less while lower level AI deviates more.  While this approach is effective if allows low level AI to still attempt shots from across the map.

With added and improved movement of hogs low level AI's would prioritize moving closer to enemies instead of attempting shots they will never make.

An additional tweak to AI difficulty would be to tweak the amount of random deviation in the AI's shots based on how many turns the AI has missed.  This would allow the appearance of a learning AI at a small cost in computations.

Deliverables

• Move
• Teleport
• Parachute
• FlyingSaucer
• Birdy
• BlowTorch
• PickHammer

• Improved movement
• Improved difficulty

Fourth Milestone

The fourth milestone would focus on structuring weapons and movements into classes of weapons/movements.  Additional air attacks would also be added for the AI within this milestone.  

Internally the AI would first test to determine which class of attack/movement should be explored instead of iterating through all possible weapon selections.  If for example the best class of attack is "explosive" the AI would explore which explosive attack is best to perform.  If no applicable attack is found then the AI would fall back to the second best class of weapon/movement, etc.

Deviations in Weapon Selection

An additional tweak to the AI would allow the AI to choose non-optimal weapons.  Currently the AI will always choose the weapon that does the most damage.  While effective this tends to be predictable.  An alternative would allow the AI to choose randomly from a few of the top weapon choices.

Deliverables

• MineAttack
• Napalm
• PianoStrike
• DrillStrike 

• Improved Weapon Selection

Behavior Tree searching for Optimal Move

Fifth Milestone

The fifth milestone would allow Lua configurable AI's.  Weapon preferences, likelihood of using a weapon, accuracy, and minor scripting would be configured through Lua.  This would allow for different difficulty AI's as well as different play styles of AI for both single player and campaign.

Lua bindings for common AI tasks or overriding tasks would be provided.  Examples might be an AI which will constantly targets a specific AI, or remains stationary.  

Deliverables

• Lua Configurable AI weapons, utilities, and movement.
• Lua AI bindings
• Lua AI wiki documentation and tutorials

A fully flushed out structure of the AI would resemble the following.  The structure includes additional weapons, utilities, and movements for future AI work.

Planned additions for GSoC

Future additions after GSoC

In order to effectively utilize and plan AI movements an AI planner would need to be implemented into HedgeWars.  

Additional work after GSoC would include the creation of a planner in order to string together sequences of movements, attacks, and utilities, to ultimately accomplish the AI's goals.

An AI Planner would be implemented like a Hierarchical Task Network, Simple Hierarchical Ordered Planner, or a STRIPS planner.

Future AI layout

4.6) What do you expect to gain from this project?

I expect to gain a deeper understanding of how game development occurs in an Open Source community.  My current experience with development is with dedicated programmers who are tasked to perform specific implementations or fixes.  With an open source project supporting multiple platforms I’m sure there are a plethora of new issues that developers need to become familiar with and accustomed to.  I hope to gain these insists so that I may become a productive member of the community.

4.7) What would make you stay in the Hedgewars community after the conclusion of GSoC?

I choose Hedgewars because it was the type of project I could see myself being involved with far after GSoC concludes.  Before I knew about GSoC I’ve played nearly every Worms games, even the hit and miss 3d versions and I’ve been playing Worms to this day.  After seeing Hedgewars I’ve completely switched gears and play Hedgewars all the time.  To be able to develop new and innovative AI for such a game is all the reason I need to continue developing.

5) Practical considerations

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

* Mercurial (used for all commits)

Although I have only recently started using mercurial (3 months) I am familiar with other version control systems that are similar like git.

* C++ (language used in the frontend)

C++ was one of the first languages I learned as a programmer.  I still use it on a daily basis in both game development and other projects.

* QT (crossplatform library for frontend)

I am currently not familiar with QT for frontends but have experience in both SWT and Swing for cross platform gui development.

* Freepascal (engine is written in pascal)

Unfortunately I have not used pascal in the past but am already familiarizing myself with the language.  I’ve picked up a few books on Pascal and am currently familiarizing myself with the FreePascal language reference.

* SDL (wrapper for most of engine rendering)

I haven’t currently used SDL in any project but look forward to learning the library.

* build environments (eg cmake/autotools/scons)

Although most of my experience comes from ANT builds and Cruise Control for automated builds I create my own make files for smaller C++ projects.

* Lua (missions and trainings are scripted)

Having integrated Lua support into the USC GamePipe game engine I’m familiar with Lua, as well as binding C++ code to Lua, and binding Lua to C++.

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

For coding, my main IDEs are Visual Studio 2010/2008, Eclipse and NetBeans.

In particular for large C++ development or programs that target the Windows platform I use Visual Studio.  Development that targets multiple platforms and uses gcc I stick with Eclipse CDT and mingw as the compiler.

For Python development I mostly stick with Eclipse’s Pydev extension for syntax highlight and code complete.

For Java development I use Eclipse most of the time but also use NetBeans when other developers are more familiar with NetBeans.

I use Notepad++ for edits and development of languages my IDEs aren’t capable of handling.

Subversion and Mercurial are my main version control systems, which I use daily, either from the IDE or from tools like tortoiseSVN or tortoiseHG.

For bug tracking I use Trac and JIRA extensively with svn integration in order for bug submission as well as development tasks and testing statuses.

5.3) What programming languages are you fluent in?

I am fluent in C++, Java, and PHP. 

For Java I am also certified as a Sun Certified Java Programmer.

5.4) 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!

In general please try to be as verbose as possible in your answers and feel free to elaborate.

I am open to all forms of communication.  Phone calls, text, emails, letters, carrier pigeons, you name it!