RTS4 Data File Structure

There haven’t been any gameplay changes recently, instead I’ve been working on adding features for modding. The current proto data format automatically supports a lot of scenarios, but many common concepts can be tedious to write. The latest build includes some of those changes (and a lot of bugs).
RTS4 Release 9
Webplayer (Unity)

I’m working towards supporting advanced scripts like this RPG-style script:

Player.default {
  Level = 1;
  Experience = 0;
  NextLevelXP = $Level * 200;
  Health = 200 + $Level * 20;
  RequireComponent<AttackMelee> {
    Attack = 20 + $Level * 2;
    OnKill = (other) {
      Experience += other.$XPGain;
    };
  };
  Event(Experience >= NextLevelXP) {
    Level += 1;
  };
}
Grunt.default {
  XPGain = 1
}

Several fields (NextLevelXP, Health, Attack) are augmented by other fields. By default, these fields only include the augmentations that appear prior, adding a $ causes all augmentations to be used. Using this feature does introduce the possibility of cross-dependent fields which would crash the game; I’ll need to add some protections for that later (probably just not run those augmentations recursively). An example of something that would break it is:

Health += $BonusHealth
BonusHealth = Health * 0.5

The OnKill event handles giving experience when they kill a grunt. Any augmentations that appear in these scripts are somewhat special; a single augmentation is allocated at compile time, which starts off as the identity value; whenever the script is run, the augmentation value is changed by whatever the script says. This has the benefit of allowing any other augmentations later in the file to still be applied correctly (ie. if Experience *= 2 appears in a later technology, the experience will correctly be doubled until that tech is removed).

Finally, the script creates a level up event to be run when the players experience passes the required amount. Because of the $ in earlier dependent fields, changing the level later in the file still correctly affects Health/Attack/NextLevelXP.

Currently fields referencing other fields, and simple scripts are supported. Its also possible to define “APIs” (RequireComponent and RequireTechnology are now external APIs) to provide more functionality, without bloating the code.

RTS4 Progress

There were a few glaring features missing, but the last build was mostly complete functionally. I’ve since been working on getting the game to feel much more polished.

Prototypes

The prototype system used for unit configurations was changed to be far more flexible and will work more like CSS, where “technologies” (classes in CSS) have various selectors which determine which entities they are active for. Fields are overwritten in the same way, but a single units prototype can be spread throughout the file; the end result is that it is now easy to add upgrades that can have a significant effect on the game.
Unity RTS4 SignalFires upgrade example

Selection/Placement

I never paid much attention to selection previously, but entities can now be box-selected by boxing any part of them (instead of just their origin). The units centre is restricted to the current box selection, then that restricted point is tested against the units collider to determine if the unit should be boxed or not. Buildings also attempt to move to a valid nearby place when attempting to place them on top of another building (with standard 2D un-intersect style physics)

Projectiles

A game will obviously have a lot of projectiles (arrows, priest attack, etc.), which all act very simply. Theres now a special subsystem dedicated to handling projectiles in a much more efficient way than creating a new entity for each projectile. They are rendered and (soon) animated with the same prototype configuration as normal entities.

MiniMap

This one is a much more substantial feature addition. The game now has a minimap which rotates with the camera and shows/allows movements of the camera frustum. I may look in to dirty sectioning for it later, but the draw overhead is so minor that it probably doenst matter that its O(n).
Unity RTS4 MiniMap Screenshot

Optimisation

The game now tracks a separate list of entities which need to be updated each frame, which is only units tasked with a command. It is possible to reduce this to only units which have a move command, but the current method is likely fast enough. The game also has an EntityMap, which tracks nearby groups of entities (white boxes in the image below). Entities will delay repathing when given a new target until required. Loading is still too slow for my liking; it takes 80ms to parse the prototypes and 550ms to instantiate entities in the current demo map, but optimisations come later!
EDIT: Oops.. I still had some testing code in there; instantiating entities takes 50ms now.
Unity RTS4 EntityMap Debug View

Multiplayer

Was working well previously, but some of the newer optimisation and validation changes have probably broken things. Dont expect this to work terribly well until nearer to release.

Webplayer

Back to RTS4

The previous tutorial series covers most of the basics for an RTS. I probably wont be doing any others for a while as I’d now like to concentrate on RTS4. There has been some quite significant progress made to the project; with the cleaner design from the UnityRTS tutorial series, and the separation of simulation from visuals, the project is much easier to work with now.

Separation of logic

In the UnityRTS projects, although updating happens at a fixed time interval, the coupling of the simulation and visuals makes it difficult to have simulations running in the background and ties the game more closely to the Unity engine (which with Unreal looking so nice, I want to avoid). These two functions are now separate, and each client now runs two simulations concurrently; one for the last known server state, and one for the clients visuals. Each network message is first run on the server, if it is prior to the clients visuals simulation time, the client sim is synced to the servers sim, and then rolled forward to the correct client time. This gives clients no lag while still minimising network bandwidth. As the visuals are separate to these simulations, they can smoothly interpolate whenever the client simulates incorrectly.

Prototypes

The decoupling of the simulation from the Unity visuals means that entities can no longer be described by components on a prefab. To replace and extend this system, each entity now has a prototype object, which calculates any stateless properties (its max health, build time, etc.). Getting a field is not as simple as looking it up by name; Prototypes have a list of technologies which can be enabled or disabled which augment fields, enable / disable components, and even enable / disable other technologies (both for just this entity, or for all entities owned by the player).

These toggleable technologies mean that entities can very simply support buffs and debuffs, by for example enabling a SlowPoison technology. The system also handles armoury upgrades by enabling the HardenedShields player-wide. And it can even be used to handle tech unlocks, for example by enabling age2 player-wide, which can in turn augment the villagers Builds list to include Barracks and Farms.

I dont fully understand the effects system in AoM, but this seems more extensible and quite happy at how many common RTS concepts it can support cleanly. None of my previous attempts included anything like this, so its great to finally understand it.

Unity RTS4 Prototypes example code for Villager

Multiplayer

With the changes above, multiplayer is now functional. I’m using the RPC support in Unity to send messages (after serialising them to byte arrays) which conveniently handles lobbies and NAT punchthrough for me.

 

The current version can be played here (with multiplayer disabled at the moment). I also added in the older models instead of boxes.
RTS4_7.4
Webplayer

Unity RTS – Part 6 – GUI

Although promised many times, Unity still does not have a decent UI layout engine. The process can be simplified with NGUI from the asset store, but its still tedious. For UnityRTS I opted to use a system similar to the built in GUILayout, but tried to make it much simpler to use for common use cases. It works off of a loose hierarchy of elements, with three main functions.

Most of the time, child elements will borrow a slice from their parents; removing that space from the parent and giving it to the child. This is done through WidthSlice() and HeightSlice(). Another common function is tables and grids, created through the Grid() function. After specifying the number of rows and columns, calling Cell() on a grid returns the next cell (iterating horizontally then vertically). The final function is a flow layout, though not integrated as nicely as it could be. This scales down items uniformly to fit the specified number of items in the allocated space; much like grid, but the item dimensions and count are provided, and item aspect ratios are preserved.

The UI in UnityRTS is modelled off of Age of Mythology. Two height slices cut the top and bottom bars, and various other functions allocate required space. Information is pulled from the game scene as required. Also made some pretty box art for things 😀

unityrtsui
Webplayer | Download Project

Unity RTS – Part 5 – Pathfinding

The most common algorithm used in RTS pathfinding is A*. This algorithm traverses lists of nodes in a specific order to reduce the number of nodes processed while ensuring the fastest path is taken, and requires very little preprocessing of the map data for a trivial implementation. Unity RTS is designed to use this same concept, but combined with flow fields to allow more natural movements (removing the grid-aligned movements in unprocessed A*).

Firstly, a map is created with a value for each terrain cell, which represents if that cell is occupied or not. An int is used here, so that objects stacked on top of each other work correctly when added/removed. An A* pass then propagates the cost values throughout the terrain, but with a small change. When propagating a cost to each cell, the value used is the minimum of (from_cost + 1) or ((from_cost + neighbour_cost) / 2 + 1). This means costs can be propagated diagonally. The most extreme case, where neighbour is 0 and from is 1, this results in a value of 1.5 (quite close to the correct 1.41 when using cell distances).

Objects then move by calculating a movement direction from this persistent pathing query. First the interpolated value at the objects exact position is calculated (based on the 4 surrounding corners). Then for each corner, a desired direction is calculated and finally averaged to get the movement direction. A final piece of code tries to prevent directions from pointing into blocked areas, though is not necessary.

The complicated part here is calculating a desired direction from each corner. Each corner only knows about itself and the current object position, so this direction vector simply indicates how much closer or farther the object should be to the corner, based on the assumption that the cost increases by 1 for every unit distance. The ratio of delta cost and distance is first calculated, then the resulting vector is simply:

dir += deltaP * Mathf.Sign(ratio) / (1.0f – Mathf.Abs(ratio));

Where deltaP is the object position relative to the corner, ratio is the ratio of cost to distance. Of course, this can result in a division by zero; such a case indicates that the unit should move exactly toward the corner (ignoring cost calculation errors); cdir just needs to be very big in this case to overpower the directions from any other lesser corners.

A lot more goes into the pathfinding of a AAA RTS, you can read a little about how Starcraft handles their pathfinding here, or a little about Age of Empires pathfinding here.

pathingtest
When targeting the selected object, the blue lines display the direction each corner is suggesting that the object move in, the white is the resulting normalised sum of these directions. This project is the same as in Part 4 (I just took a long time to write it up), DownloadWebplayer.

Unity RTS – Part 4 – Vision blocking

Its been a while! This time I’ve made a lot of tweaks to the Line of Sight code so that items can correctly and efficiently occlude unit vision and implemented pathfinding using flowfields for smoother unit motion. Both items took quite a bit longer than I had anticipated and are probably still quite slow, but I’m happy with how they are looking. This post will talk about the vision blockers; I’ll leave pathfinding for the next.

Some code existed in the previous build for entities to write their blocking height to a grid covering the game world. This grid tracks the highest unit on each cell and blocks sight for all shorter units. The RevealLOS method has been rewritten to now more accurately read this data and project “shadows” outward to hide areas of terrain. The algorithm has two distinct phases.

Pass 1 – Occlusion angles

The first pass iterates through all tiles within the reveal radius, ordered by their occurrence when sweeping clockwise. Think of this as a radar, which pings for each cell as the detector passes them. This ordering is important to keep the input clean and reduce the amount of work needed later.

Each cells height is compared against the current units height, if the cell is too high, it is added to an ordered list of blocking cells (ordered the same as the iteration, clockwise around the unit). The distance and angles for where the blocked vision starts and stops are also cached. A small optimisation pass is done on this data to remove cells that are eclipsed by other cells nearer to the unit center; these are redundant, since any terrain they occlude will already be occluded by the nearer cells.

Pass 2 – Terrain reveal

The next pass iterates over all tiles within the reveal radius, determines their distance and start/end angles, and looks through the previous list of occlusion cells to determine how much of the tile is occluded. As the occlusion items are ordered, iterating this list forward and shrinking the visible arc is sufficient to correctly calculate occlusion for the left-most angle. This is then repeated in reverse for the right side.

The result of this calculation is four angles; the tiles initial start and end angles relative to the unit, and the unoccluded start and end angles. The visibility of each tile is simply the unoccluded arc size divided by the total tile arc size.

Optimisations

Trigonometry functions are expensive to execute, so “angles” here are approximations. A full circle in this system is 8 degrees, and calculating the angle of a vector is simply determining what quadrant it is in, and then dividing the coordinates.

It is impossible for the arc of a nearer cell to be smaller than a farther cell it is projecting onto. If this were not the case, it could be possible for small arcs to lie entirely within a tiles arc, and be ignored by the system.

losoccluded

View online or Download Project (note: has some unfinished UI code in there too)

Unity RTS – Part 1 – Framework

I’m going to start a series on building the major components of an RTS in Unity, starting with how to develop a typical framework. RTS games remain one of the most complex and difficult game types to create, dont expect to have anything fancy working for quite a long time.

Networking Considerations

Most developers looking to build an RTS will be looking to include a multiplayer component. I wont go into a lot of detail, but supporting multiplayer in a game with hundreds of active units constantly doing things in the world is quite difficult; 1500 Archers on a 28.8: Network Programming in Age of Empires and Beyond does a much better job of explaining the typical approach used (though some other approaches also exist). A well designed RTS should have a layer which all input “Commands” pass before interacting with the world; this layer synchronises actions through to the various clients to ensure the world simulates correctly for each client.

Components

An RTS framework will likely involve the following components (and more):

  • Entity: Represents the base data that each object within the scene contains (Name, Player, Health)
  • Action: Contains logic for an action that an entity can perform
    • MoveAction: Take a target location and walk the best path to reach that location
    • BuildAction: Invoke MoveAction; when in range, begin construction on a Buildable component
    • GatherAction: Invoke MoveAction; when in range, gather resources from a ResourceSite component
    • AttackAction: Invoke MoveAction; when in range, reduce the target Entitys Health
  • Components: Optional items that augment the way an entity acts
    • Sight: Cause this object to reveal the surrounding area
    • Buildable: Accept build actions from other entities; when complete, swap for another entity
    • ResourceSite: Hold an amount of resource that can be gathered
  • Pathfinder: Store terrain information required for pathfinding and provide pathfind query results
  • Player: Store information about a player (Name, Colour, Alliances)
  • Command: A target and action to be applied to a set of entities
  • SceneManager: Handle executing commands in the correct order and at the correct time, and querying for entities
  • LOSManager: Hide objects that are out of sight of the player
  • SelectionManager: Store and allow interactions of the currently selected entities
  • CameraManager: Handle camera movements
  • BuildManager: Allows the player to interactively place buildings when a building type is selected
  • InputManager: Receive mouse and keyboard inputs and send them to the appropriate manager

To ensure the game simulates correctly on all clients, no gameplay-altering information should ever leak into the entities or their actions/components except through generating Commands. Unfortunately, Unity makes this constraint very difficult to enforce; at any point a script can change the state of an entity or an action can query the Input class and cause a client desync. It is entirely up to the programmer to make sure that never happens.

Implementation

UnityRTSP1
I’ve created a very basic framework, you can view it online here, or download the project file here:
http://weesals.com/Releases/Unity/UnityRTS/Part1/UnityRTS.zip
Its very simple, dont expect much.

This project contains a working Action system, though has only a partially implemented Move action. Entities can be selected by clicking or box-selecting them, they can then be ordered to move by right-clicking the terrain or another entity. Right-clicking another entity will cause the target position to continually update, and cause the entities to follow.

New actions can be implemented in a similar way, and then dragged onto the object via the inspector. An AttackAction may subclass the MoveAction and only run base.Step() when the object is too far away to attack. Once the objects are in range, it can then begin the attack logic. The action with the highest score for a given request is used, thus an attack action returning a score of 2 when targeted at an enemy entity would be used instead of the MoveAction returning a score of 1.

Ludum Dare 26

I was planning on doing Uni work this weekend, but lots of friends were entering the Ludum Dare gamejam, and the theme was pretty cool, “Minimalist”. I decided to put together the quickest RTS I could, based off of SimWar.

I’ve managed to get multiplayer working with lockstep synchronisation, along with some basic RTS features: team colours, collision checks, the worlds worst pathfinding, unit selection/ordering/placement. The games page is available here:
Ludum Dare – SimWar
Source

I’m pretty happy with the results, especially for less than 24 hours of development time. It gave me a good way to test how the networking would work for RTS4. It also allowed me to test the simulation rate being significantly slower than the rendered framerate (simulation is at 4fps) and the visuals being interpolated. I had previously been told that this wouldn’t work, however it seems to be quite effective and wold make fast forwarding through replays much faster.

Reflected Vertex Declarations

Something I have found needlessly difficult while developing graphics abstractions in C++ was offering a simple, elegant and effortless way to declare new vertex structures, and ensure all required attributes are bound automatically.

One way I found around this problem is to not have a vertex structure; instead require the developer to fill a separate array for each parameter they wanted in the vertex declaration. The system could then determine which arrays were filled, assert that they are all the same size, create a vertex declaration, and interleave the data. The benefits of this system is that it can (although didn’t in my trivial implementation) support any combination of fields within the vertex declaration; the obvious drawback is that it is up to the programmer to ensure each array is the correct size, and often requires splitting already nicely-interleaved vertices to separate arrays, just to be re-interleaved later in the pipeline.

Another option only really possible on desktop systems with ample memory and bandwidth, is to just ignorantly declare a mammoth vertex structure containing all the typical required fields, something like the following:

Vector3 Position
Vector3 Normal;
Color Color;
Vector2 TexCoord;
int BoneIndices[4];
float BoneWeights[4];

Then leave unrequired fields as their default. This approach is very easy to implement, but of course has pretty bad memory repercussions, always taking 17*4 bytes for every vertex. It also will not allow the developer to create custom fields, or rename the existing fields, resulting in, for example, having to force the tangent vector into the first 3 floats of BoneWeights.

Now that I have moved to a managed language, with support for reflecting data fields within a type and allowing attributes on fields, a lot of the work required for generating vertex declarations can be automated. The following is an example of a typical vertex structure:

[StructLayout(LayoutKind.Sequential)]
struct VertexPositionColor2 {
    public Vector3 Position;
    public Color Color;
    [VertexAttribute(VertexElementFormat.Fixed, sizeof(byte), 4)]
    public uint Color2;
}

This structure gets reflected when used in a VertexBuffer<T>, and the fields in the struct are reflected to determine how the field should be serialized/bound, and a VertexDeclaration object is created caching the fields and their descriptions for the next time this structure is used. Vector3 and Color have default attributes, which tells the VertexDeclaration, when it reflects, how the data is laid out in the type, and how it should be bound to a shader. Color2 shows an example of overriding the default with its own format/layout.

Each field has the following metadata associated with it to aid in binding:
Name: Used as the semantic name when binding to a shader
Format: Float, Integer, or Fixed (fixed referring to normalized types with fixed precision)
Size: Size in bytes of a component within this field (ie. sizoef(float), sizeof(byte))
Offset: The offset in bytes from the start of the vertex structure, to where this field begins
Count: The number of components within this field

One issue remains with this declaration; signed bytes used for normals need to be normalized, but retain their sign. The current meta-data does not yet store if a Fixed type is signed or unsigned, and is assumed to be unsigned. Two possible fixes for this is to add a Signed boolean, or extend the Format to include FixedSigned. I am waiting to see how this system is used to determine which would be the preferable option (the former is more flexible; allowing unsigned Integer and Float types (where possible), the latter would minimise the fields in VertexAttributes to 3).

The implementation of this system is mostly trivial in C#, but one part which was less intuitive was getting C# to serialize to a byte array. To do so, you’ll need to make use of the Marshal class, specifically AllocHGlobal, StructureToPtr, Copy, and FreeHGlobal. The vertex declarations also unfortunately require an extra StructLayout attribute be applied to them. The procedure is:
– Allocate some unmanaged memory of sufficient size
– Loop through all vertices
– Copy the vertex data to this unmanaged memory (StructureToPtr)
– Copy the unmanaged memory to a byte array (Copy)
– Free the unmanaged memory

AOM-inspired and compatible game

I’ve decided to create a blog to document progress on random projects I’m working on, the latest one being an AOM-inspired RTS.

A wise man (Dylan from AGDC) once taught me of the importance of coming up with a mission statement for each game, so that the original intent of the game remains throughout development. My goals for this game are pretty simple:

Bring the latest improvements and expectations from the RTS genre to Age of Mythology

This is impossible by simply modding the existing game, and doing that would be no fun, so instead I am on my way to build my own game, attempting to achieve the same style and feel as AoM, but going beyond what was possible back in 2001, when Ensemble built their masterpiece.

The modding community at http://aom.heavengames.com/ has invested a huge amount of time and effort into building innovative and wonderful extensions and tweaks for the game which should not be ignored. This new game will be built to take advantage of as many of these assets as possible.

Random Maps

Age of Mythology has quite a unique random mapping system, in which a relatively short code file builds a complex, beautiful, and balanced game world with a given seed. This gives an effectively infinite number of possible maps each with unique opportunities for strategies and gameplay. These maps are written in a language called XScript, in an environment called RMS. The maps define Areas with tile sets to decorate and define those areas, Connections connecting the various areas and ensuring paths are possible, and object/player placements.

AI

I have not yet investigated in much detail how the AI works in Age of Mythology, but this appears to also make use of the XScript language to define behavioral properties.

Tech Tree and Entity Properties

Age of Mythology is a very data driven game, most properties about the buildings, units, god powers, and tech tree of the game is driven by XML files. An XML file for a building will describe all the units which can be produced from it, through icons in a grid. The system can then look the data file for the units to extract more information about them. The units can then have their own set of actions for things they can produce, which then reference yet more entities. A number of constraints on these items prevents them from being visible until the appropriate tech has been unlocked.

More progress has been made at the time of this writing, but the initial build looked something like this with the acropolis.xs map loaded. This build had a very rough first-pass area system just for testing, had scale issues, and didnt support smoothing properly, but this shows the XScript compiler working, a map loading, and the API’s being executed correctly.

This game will be code-named RTS4 from now on (ignore that the title bar says AOT)