Aircraft Movement Graph

Introduction

The aircraft movement pattern on an airport is defined through a directed graph. Each place where the aircraft changes direction, or where several paths intersect is called a node (or vertex in graph theory). The connections between nodes are called edges.

In Locomotion, everything from the approach, the holding pattern, the landing, the intersections, the terminals to the takeoff is defined by nodes and edges.

For an idea of what this looks like, here is the movement graph of the large airport:

Airport1 movement graph

Airport3 movement graphs

Nodes

Each node defines where the aircraft changes direction, or where several paths intersect. A node definition looks like this:

	<auxdata name="node[18]" size="1" num="8" type="0">
		<variable name="x" size="2">102</variable>
		<variable name="y" size="2">32</variable>
		<variable name="z" size="2">1</variable>
		<bitmask name="flags" size="2">
			<bit name="terminal">1</bit>
			<bit name="ground">1</bit>
		</bitmask>
	</auxdata>

Here we have the following variables:
x, y, z - position of this node, relative to the centre of the airport
flags - bit mask of flags for this node, how the aircraft should behave

For the position, note that each tile is 32x32, so a distance of two tiles from the centre would have 64 in the appropriate coordinate.

The following flags are defined:
aircraftbegin - aircraft begins descent for landing or acceleration for takeoff
aircraftend - aircraft finishes takeoff and heads for destination airport
bit_2 - sets the node that an aircraft enters first on approach (3 by default), set it to the first node and planes also land like helicopters
flight - aircraft is in flight at this node
ground - aircraft is on the ground at this node
helibegin - begin helicopter descent or ascent
heliend - end helicopter descent or ascent
terminal - node is a terminal
touchdown - touch down and start braking

Note that Locomotion airports have two nodes for each intersection, one for arriving aircraft movement and one for departing aircraft movement. Even though they are in the same place, they need to be separate nodes to prevent loops in the pattern.

It is not clear which node an aircraft originally heads for. Since there appears to be no special bit for this first node, it is likely that the first node (node[0]) is always where the aircraft enters the movement graph.

Edges

Each edge defines aircraft movement from one node to the next. The aircraft will try to follow a straight line from the origin to the destination node.

An edge has the following format:

	<auxdata name="edge[1]" size="1" num="12" type="0">
		<unknown name="field_0" size="1">1</unknown>
		<variable name="from" size="1">0</variable>
		<variable name="to" size="1">22</variable>
		<unknown name="field_3" size="1">2</unknown>
		<bitmask name="busymask" size="4">
			<bit name="bit_1">1</bit>
			<bit name="bit_1A">1</bit>
		</bitmask>
		<bitmask name="field_8" size="4">
		</bitmask>
	</auxdata>

Here we have the following variables:
field_0 - Type of movement, can have values:

• 0 - Normal ground movement
• 1 - Flying
• 2 - Aircraft taking off
• 3 - Helicopter Taking off / Landing

from - origin node for this edge
to - destination node for this edge
field_3 - Status of the plane, can have the values:

• 0 - Nothing special
• 1 - Preparing to land
• 2 - Heading to helipad
• 3 - Helicopter landing
• 4 - Heading to terminal
• 5 - Waiting to start landing

busymask - a plane can use the edge as long as all of these aren't busy
field_8 - a plane can use the edge as long as one of these isn't busy

The busymask variable is used to stop airplanes from running over each other. To do that, each airport has 32 bits available that are marked as busy when an aircraft occupies an edge.

It works like this:

• When an aircraft is on an edge, it sets the relative busy bit. The busy bits are in hexidecimel, so edge numbers need to be converted. Eg: edge[5] uses bit_5 and edge[26] uses bit_1A.
• When an aircraft is wants to move to a new edge, it checks the busy bits on that edge and waits until they are all clear, until moving to it. Whilst they are not clear, it waits on the current edge, not the node. So the busy bit for that edge is still active.
• When it has left an edge completely, it's relative busy bit is cleared.

field_8 is similar to the busy mask, except that the aircraft waits until at least one of the bits is clear before moving onto that edge. This allows it to wait until there is a free terminal before entering the terminal intersection block. Will also allow use of any other multiple route system, such as multiple runways.

Because of the 32bit limit of busymask and field_8 you can only use busy bits on 32 edges, although you can infinite edges overall, edges with numbers over 31 cannot be used with busy bits. This limits the complexity of an airport, but still allows dual runway systems if properly built.

To make your airports as complex as possible, you can follow these guidelines:

• Move the edges that don't require busy bits to the end of your edge list, so they take up numbers over 31. This way they don't use up busy bits that can be used elsewhere.
• You don't need a busy bit on some edges. You don't need them at all on the holding edges, which the airplanes use when waiting to use the runway. You can also remove them from the end of the runway and the helicopter takeoff edge, as planes generally can't get into these edges fast enough to cause "collisions".

To reliably prevent dead-locks or (harmless) plane collisions, planes must ensure the block (a set of edges that can only hold one plane at once) they are entering is empty. This is done by making any edges entering the block, require every edge inside the block to be clear. As the plane moves around the block, only the particular bit relating to that edge is set, as this is all that is needed to prevent another plane entering the block.

Airplane routes

When designing your airport, you need to know how the planes navigate the edges. When looking for a route to take, it goes through the edges in order, from lowest to highest. So if given the choice of edge 5 and 9, it'll try 5 first, then 9. If all the required bits are alright on an edge, it'll take that edge and ignore the rest.

To avoid problems, you need to create an out path and an in path for the terminal sections. This way, the plane is forced to go in the desired direction. If you try to use a single path, the planes will either make unecessary loops through terminals or ignore the terminal altogether.

Airport variable field_B6 is used to prevent the user/AI from putting planes on terminals while another plane is heading for it. Doing so would cause a dead-lock, which humans can fix easily by removing the plane again, but the AI doesn't recognize that.

This field has a bit set for each edge leading from the entrance node to all terminals, not including the final edge to each terminal (or else you can never add a plane while there is one at any terminal). The entrance node is the node where a plane checks that a terminal is available before proceeding. In Airport1 (see graph above) these are edges 8, 9 and 12.