Tel-Hai Academic College

IPHA - An Open Source Framework for Development of Strategy Games based on Microsoft Technology

Jacob Barkai

Table of Contents

Table of Figures ... 4

1. Abstract ... 6

2. Project Goals ... 7

3. Introduction to Strategy Computer Games ... 8

3.1 Tools and Technologies ... 8
    3.1.1 The Microsoft .NET Framework ... 8
    3.1.2 Available Literature ... 8
    3.1.3 Overview of Existing Open Source Projects ... 9
3.2 Strategy Games Theoretical Concepts ... 10
    3.2.1 Turn-Based Strategy Games: Classic Model Overview ... 10
        General ... 10
        The Goal ... 11
        The Players ... 12
        The Board ... 12
        The Pawns ... 13
        Other Restrictions ... 14
    3.2.2 Modern Approach for Turn-Based and Real-Time Strategy Games ... 16
        General ... 16
        The 4X: eXplore, eXpand, eXploit and eXterminate ... 19
        The Mission ... 19
        The Players ... 22
        The Map ... 23
        The Pawns ... 24
        Resources ... 28
        Technology ... 30
3.3 Artificial Intelligence Algorithms and Concepts for Strategy Computer Games ... 32
    3.3.1 Choosing the Right Algorithm ... 32
        General ... 32
    3.3.2 Theoretic AI Concepts ... 32
        Intelligent Agents ... 32
        Data Structures ... 34
        Defining the Problem Domain ... 36
    3.3.3 Algorithms ... 37
        General ... 37
        Basic Movement: Bresenham′s Algorithm ... 37
        Advanced Movement: Extended A* Algorithm ... 40
        Pattern-based Movement ... 42
        Obstacle Avoidance in Dynamic Environments ... 43
        Flocking: Follow the Leader ... 46
        Next Target to Handle (NTH) ... 48
        Next Pawn to Attack (NPA) ... 48
        Next Pawn to Defense (NPD) ... 51
        Next Pawn to Build (NPB) ... 53
        Next Resource to Harvest (NRH) ... 56
        Retreat Under Pressure (RUP) ... 57
        Structure Placement ... 59

4. Further Directions ... 61

5. Bibliography ... 62

6. Appendix: The IPHA API ... 63

6.1 Disclaimer for the code and the document ... 63

2. Project Goals

The creation of a comprehensive strategy games framework is a process which involves large scale of disciplines to research and develop, and hundreds (if not thousands…) of total human labor years. Generally, in every computer game company we usually find a large group of people that give a hand in creating a reliable commercial product. Among those people we find back-end and front-end programmers, game designers, story builders, QA testers, 3D modeling experts, directors and more.

As this project was written as an "internal project" in my B.Sc. degree studies (Computer Science in Tel-Hai Academic College) and I′m only a single person, I had to make a significant cutoff and focus on specific goals I want to achieve on a limiting work time. I didn′t focus on writing the code itself, but otherwise deeply explored the principals of creating modern strategy computer game framework. The current version of the project′s document covers three topics out of the totality subjects:

1. Describing the fundamentals of classic and modern strategy computer games.

2. Understanding chosen artificial intelligence algorithms based on "the game theory" and techniques that take part in strategy computer games. As AI algorithms for classic strategy games are widely described and implemented in many ways and plenty of information can be found, this project will otherwise try to cover aspects of AI algorithms that used by modern strategy games.

3. Well designed, multi-threaded .NET Class Libraries that can be later used for development a complete strategy game, also involving Microsoft′s XNA. Thus, the game will be written in a complete managed code end to end.

Jacob Barkai

Tel-Hai Academic College, Israel

April 2009

3. Introduction to Strategy Computer Games

3.1 Tools and Technologies

3.1.1 The Microsoft .NET Framework

Searching for a fitted programming language to use, I eventually found the Microsoft .NET framework (C# specifically) as the best one because of its strong, flexible and somewhat easy to use characteristics. I also kept in mind the fact that this project should be later enhanced and extended using Microsoft′s new XNA technology, which is a set of tools with a managed runtime environment that facilitates computer game development and management. XNA attempts to free game designers from writing "repetitive boilerplate code" and bring different aspects of game production into a single system.

All the classes were written in the Visual Studio 2008 IDE, in so called "managed code", and could be used in both Microsoft and Linux operating systems (by using "Mono"). The .NET framework version is 3.5 and can be freely downloaded from Microsoft′s website.

3.1.2 Available Literature

I couldn′t find any specific book that covers all what I wanted to show in this project, so I had to read and collect information from many different sources, books, online materials and even user guides of game I managed to reach. I found that there is an available series of books publish by Delmar Cengage Learning and titled "Game Development Essentials" (2007) which is a true game development encyclopedia and covers any possible information – from game project management to game artificial intelligence. Anyway I wanted to dig into the materia by myself and attack this subject from the pure game theory aspect, which is not a common methodology by the book writers.

Here is a list of the key sources I used in this project. The complete list of sources appears in the bibliography section, at the end of this document:

• "Artificial Intelligence: A Modern Approach" (Prentice Hall, second edition, 2002) by Stuart Russell and Peter Norvig. A comprehensive book for theoretic and general AI algorithms and concepts.
• "An Introduction to Game Theory" (Oxford University Press, 2003) by Martin J. Osborne. Presents the main principles of game theory and shows how they can be used to understand economic, social, political, and biological phenomena.
• "Artificial Intelligence for Games" (Morgan Kaufmann, 2006) by Ian Millington. Explains algorithms rigorously while also discussing appropriate implementation details such as scheduling AI over time and using the right data structures.
• "AI for Game Developers" (O′Reilly, 2004) by David M. Bourg and Glenn Seemann. Introduces to techniques such as finite state machines, fuzzy logic, neural networks, and many others.
• "Command & Conquer: Red Alert walkthrough – strategy guide" by Roger Wong, 1997 (http://www.the-spoiler.com/STRATEGY/Westwood/red.alert.2.html). The purpose of this online RTS guide is to aid the public with strategies and tactics for use in the game Command and Conquer: Red Alert™, by Westwood Studios Inc.
• "Civilizations IV: FAQ/Walkthrough by Warfreak", 2007 (http://www.gamefaqs.com/computer/doswin/file/919352/47887). The purpose of this online TBS guide is to aid the public with strategies and tactics for use in the game Civilizations IV™, by Fraxis Games.

3.1.3 Overview of Existing Open Source Projects

There are several running open source projects for specific strategy games, which doesn′t intentionally designed for general purpose, and many others that are no more under development. Source code repository sites such as sourcefourge.net and codeplex.com are hosting some strategy games code examples, currently in various development stages. I observed two projects which still running:

• "Bos Wars" (www.boswars.org): a grounded, multi-platform futuristic real time strategy game (RTS) with popular game elements, such as economy management and army building. It involves AI algorithms as well as graphics and sound handling. The source code is written in C++.
• "Battle for Wesnoth" (www.wesnoth.org): a grounded, multi-platform turn-based strategy game (TBS) with a fantasy theme. Has a reach inventory of unit types and races. The source code is written in C++.

[...]