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

Table of Contents

TABLE OF FIGURES

1. ABSTRACT

2. PROJECT GOALS

3. INTRODUCTION TO STRATEGY COMPUTER GAMES
3.1 Tools and Technologies
3.1.1 The Microsoft .NET Framework
3.1.2 Available Literature
3.1.3 Overview of Existing Open Source Projects
3.2 Strategy Games Theoretical Concepts
3.2.1 Turn-Based Strategy Games: Classic Model Overview
General
The Goal
The Players
The Board
The Pawns
Other Restrictions
3.2.2 Modern Approach for Turn-Based and Real-Time Strategy Games
General
The 4X: eXplore, eXpand, exploit and exterminate
The Mission
The Players
The Map
The Pawns
Resources
Technology
3.3 Artificial Intelligence Algorithms and Concepts for Strategy Computer Games
3.3.1 Choosing the Right Algorithm
General
3.3.2 Theoretic AI Concepts
Intelligent Agents
Data Structures
Defining the Problem Domain
3.3.3 Algorithms
General
Basic Movement: Bresenham's Algorithm
Advanced Movement: Extended A* Algorithm
Pattern-based Movement
Obstacle Avoidance in Dynamic Environments
Flocking: Follow the Leader
Next Target to Handle (NTH)
Next Pawn to Attack (NPA)
Next Pawn to Defense (NPD)
Next Pawn to Build (NPB)
Next Resource to Harvest (NRH)
Retreat Under Pressure (RUP)
Structure Placement

4. FURTHER DIRECTIONS

5. BIBLIOGRAPHY

6. APPENDIX: THE IPHA API
6.1 Disclaimer for the code and the document

Table of Figures

Figure 1: Ancient Egyptians Playing "Senet"

Figure 2: Hexxagon Board Layout with Hexagon Tiles

Figure 3: 8x8 "Western Chess" Board Layout with Square Tiles

Figure 4: Chinese checkers Board Layout with CircularTiles

Figure 5: International Grand MasterGary Kasparov Plays Against IBM's "Deep Blue" Chess Super Computer

Figure 6: "Command & Conquer 3:Tiberium Wars" (2007) - an RTS Game by EAStudios

Figure 7: "Civilization IV: Betond The Sword" (2007) - a Modern TBS Game By Fraxis

Figure 8: Campaign VS Scenario Sequence

Figure 9: The Fog of War-A Pawn of Type "Dock" Has a Circular Range of Sight. Black Areas Represents Unrevealed Tiles While Darkened Areas Represents Non Updated Tiles

Figure 10: An Example of a Reticulated 3D Map Surface. Each Tile Has Specific Attributes: Material, Geographic Location, Altitude and More

Figure 11: Range of Hit: A Tank has 7 Range of Hit. Green Lines Indicates "Within Range"

Figure 12: Minerals Field - A Fictional Resource Processing Center and Harvesting Pawns (StarCraft 2™ by Blizzard)

Figure 13: Evolution of Pawns: Technology Based Development

Figure 14: The Process of Acquiring New Knowledge in Learning Machines. "You Don't Know a Flame Can Burn until You ActuallyTouch It..."

Figure 15: Directed Graph Structure for Route Finding

Figure 16: BinaryTree Structure for Route Finding

Figure 17: Tile Based Movement - None of the Eight Directions for the HMMWV Leads Directly to the Rifleman

Figure 18: Chasing Methodologies-To the Left is a Simple Chase. To the Right is a Line of Sight Chase

Figure 19: Bresenham's Algorithm (Left Path) VS Another Possible Algorithm (Right Path)

Figure 20: Pattern-Based Movement- Example of Guarding a Facility

Figure 21: Obstacle Avoidance - Rifleman A's Wiggle Walk

Figure 22: Square Formation

Figure 23: Arrow Formation

Figure 24: Two-File Formation

Figure 25: NPA UtilitiesTree

Figure 26: NPD Utilities Tree

This project is dedicated to my family "Unless a variety of opinions are laid before us, we have no opportunity of selection, but are bound of necessity to adopt the particular view which may have been brought forward."

Herodotus, 5th century BC, Greek historian

1. Abstract

Strategy computer games are nowadays a very popular and exciting genre in the world of computer games. Many succeeding commercial games were developed since the end 1980's and contributed to the growth and interest in computer games in general and strategy games in particular. Games such as Command & Conquer™ series (by Westwood and EA Studios), Civilization™ series (by Sid Meier), Warcraft™ and StarCraft™ series (by Blizzard) entered to the computer games' hall of fame, thanks to their inventiveness, artificial intelligence challenge and visual effects that they offer.

Almost every strategy computer game was based on the idea of an "electronic board game", a modern brother to the classic, "physical" board games such as chess, checkers, backgammon, hexxagon and more. An interesting issue is the fact that both the classic board games and the modern strategy computer games are sharing many of the key elements that make the players think and act strategically and tactically, according to the development of the game. This issue is the basis for the project, and discussed further in the next pages.

It is common to divide strategy games into two main types: "Abstract strategy", where there is "perfect information" regard to the game's state. An example for an "Abstract strategy" is Chess. The other type is "Concrete strategy" where there is "incomplete information" regard to the game's state. This characteristic makes the game more interesting and surprising. An example for such a game is "Stratego"^[1].

This project aims to serve as an open source code framework, written under Microsoft .NET, for easy creation and expansion of "abstract strategy" games by providing operational artificial intelligence algorithms and well-defined class libraries based on concepts taken from "the game theory" for decision making aspects.

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:

1 "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.eom/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.gamefaas.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++.

3.2 Strategy Games Theoretical Concepts

3.2.1 Turn-Based Strategy Games: Classic Model Overview

General

Turn-based strategy games, often abbreviated as "TBS", are an old genre of entertaining instrument with a long history of development and changes. Although chess (at least the so called "Western" chess variation) is the most famous and considered a historic representation for TBS game, we can find much older sources - back to 3100 BC (Predynastic Egypt period), such as the "Senet" game evolved by the ancient Egyptians^[2].

Maybe the main reason that TBS games were developed especially in nationalistic and militant cultures is that TBS games force you to "think twice" before you order your warriors to do the next step. You always keep in mind that if you lose, the "assets" you're holding will be lost, and thereupon be remembered eternally in disgrace...

illustration not visible in this excerpt

Figure 1: Ancient Egyptians Playing "Senet"

A very important keynote that will help you survive and eventually win the game is the fact you can always see the current state of the game. That is, where is yours and your opponent pawns are placed, how many pawns you and your opponents left, what are the risks that each of yours and your opponents pawns face with, what are the legal moves you and your opponent can do next, be aware to the size of the "battlefield" and its restrictions (which is not being modified during the entire game) and so on. This type of knowledge is known in the world of artificial intelligence (AI) as "perfect information", where you have a complete picture regard the current state of all parameters of the game.

This privilege of knowing the entire details of the current state (a.k.a. "Abstract strategy pattern") is something that distorts the truth, since in the real world you know some of yours and your enemy's abilities. Even if you have the most powerful intelligence forces, it helps you know most of the information, but not everything. Also, you don't always have a complete data regard the manpower quota you keep, naturally not that of your enemy. You also don't know what the final borders of the battlefield are. In spite of that, for those old days these restrictions weren't an actual factor and it was a highlight game for the players ofthat era.

Specifically in TBS games^[3], each player makes his move in his turn while the opponent only observes it. That is, the progress of the game is done synchronously, making the state change be done only by a single player. This behavior is what making the game "turn-based". We should notice that a "move" can be interpreted as zero or more pawns changing of place, and not only a single step as we use to think. We should also notice that an "opponent" can be interpreted as one or more players, and not just a single one.

When we face with the task of designing an abstract TBS game, we need to take in account the following elements which construct game rules:

The mission of the game, players, board attributes, pawn types and some other restrictions:

The Goal

A classic TBS game has a well defined board state when the goal of the game is achieved. That is, as much number of players participating the game, there's only a single player who wins the game. Moreover, although the board state for symbolizing a goal is well defined, it is quite possible that there will be plenty of winning board states combinations, and yet the total number of winning boards states is finite (determined by the board size).

Several games, such as checkers and backgammon, have no "dead-end" board states. I.e., situations in which there are no more legal moves that can lead to a winning board state (and therefore the game is referred as "stuck").

[...]

^[1] (Strategies: Webster's Quotations, Facts and Phrases, 2006) - Page 416

^[2] (In Search of the Meaning of Senet, 1980)

^[3] (Andrew Rollings and Ernest Adams on Game Design, 2003) - Page 416