Roadmap in Mafia II (traffic paths)

Roadmap

Disclaimer: Structure and field names may not correspond to reality, some of them were taken from the GDC presentation, others from the code, and still others were generally invented depending on the context.

Roadmap {
    List<RoadSpline> Splines;
    List<RoadDefinition> Roads;
    List<Crossroad> Crossroads;
    List<ushort> RoadToCrossroadMapping;
    List<CostMapEntry> CostMap;
    
    // RoadGraph related stuff here (ce and de have different impl)
}

The structure represents sets of roads, crossroads and road graph definitions.

Splines

RoadSpline {
    List<Vector3> Points;
    float Length;
}

The structure represents a normalized Catmull–Rom spline. Roads and crossroad junctions are built on their basis.

Note: when you create custom splines make sure you keep distance between points in ranges the original game does, otherwise the driver's AI sometimes suddenly becomes anxious and can stuck or try to make a U-turn in unexpected places.

Roads

RoadDefinition {
    ushort RoadGraphEdgeIndex;
    ushort OppositeRoadGraphEdgeIndex;
    List<LaneDefinition> Lanes;
    List<RangeFlag> RangeFlags;
    byte OppositeLanesCount;
    byte ForwardLanesCount;
    byte MaxSpawnedCars;
    RoadDirection Direction;
    ushort RoadSplineIndex;
    RoadType RoadType;
}

The structure defines a road.. or rather, one direction of a road. So if we want to have a 2-way road we need to add 2 definitions. Each road consists of lanes, at least one lane must be defined. Despite the fact that for a 2-way road we define 2 definition each of them contains lanes for both opposite and forward lane definitions. The OppositeLanesCount and ForwardLanesCount fields set the number of lanes for each direction. RoadGraphEdgeIndex and OppositeRoadGraphEdgeIndex fields refer the corresponding RoadGraph edges of these roads. For one-way roads the OppositeRoadGraphEdgeIndex is set to 65535 (max 16-bit value) (please note that RoadGraphEdgeIndex cannot be 65535, if you want to define a road with opposite direction only you have to reverse the spline). The MaxSpawnedCars sets the intensity of traffic on the particular road (range is 0..15, lower value == more deserted street). The Direction field defines the direction of current road definition - Towards or Backwards; the direction is specified relatively to the road spline (if the road goes along the spline (starts on the 1st point and ends on the last point), the Towards value must be set). The RoadType specifies a type of the road, one of the following values:

• Road - just a regular road
• Train - used in train/metro tracks
• Boat - tracks for ships/barges
• EmptyRoad - for roads without any traffic (cars are not spawned, but AI can drive here)
• UnknRoadType8 - is used by one road located somewhere inside or on the roof of the Empire Arms hotel
• UnknRoadType9 - is used by a few roads located deep underground in Midtown

Lanes

LaneDefinition {
    float Width;
    LaneType LaneType;
    LaneFlags LaneFlags;
    ushort CenterOffset;
    List<IRangeFlag> RangeFlags;
}

The structure defines a road lane. The Width specifies the with of the lane. The LaneType is one of the following values:

• MainRoad - just a regular road
• Byroad - actually I didn't get the difference between this one and MainRoad
• ExclImpassable - the lanes with physical obstacles, for example it can be a concrete median barrier on highway, IA knows that it cannot go there
• EmptyRoad - mostly is used on roads with a EmptyRoad type
• Parking - defined the parking lane, cars are parked there

The LaneFlags represent the combination of Bus, Truck and Highway flags (names are self-explained). The CenterOffset specifies the distance between the spline and the center of the lane (you need to divide by 100.0f to get a float value)

RangeFlags

RangeFlag { // most likely originally it was a union struct
   float From;
   float Distance;
   RangeFlagType RangeFlagType;
   byte Unkn3;
   byte Index;
   ushort Unkn4;
   float Unkn5;
}

The structure is used in roads and lanes definitions to 'mark' some parts of the road/lane. The RangeFlagType field specifies the type:

• RailroadCrossing (lanes only) - despite the fact that there are many railroad crossings in game the only one of them is defined
• Parking (lanes only) - if you want cars be parked on some part of the road only
• BusStop (lanes only) - specifies a bus stop
• Crosswalk (roads only) - specifies a crosswalk/pedestrian crossing
• Tunnel (roads only) - is used to specify a tunnel, AI will turn on the headlights there
• TrainStation (lanes only) - is used in roads with type RoadType.Train

From and Distance fields represent the start point of the range (relatively to the start of the road) and the length of the range (end point = start point + Distance). Values of other fields are not fully researched yet.

Crossroads

Crossroad {
    ushort Index;
    Vector3 PivotPoint;
    List<RoadJunction> Junctions;
    List<Vector3> Bounds;
    List<TrafficLightSemaphore> TrafficLightSemaphores;
}

The structure represents a crossroad. Index - the sequential number of the crossroad in the Roadmap.Crossroads list. The PivotPoint usually is placed near the center of the crossroad but it's not a rule, that is why it got such name. Junctions - list of road junctions, each junction connects two road lines (max number junctions is 16). Bounds represents the closed loop of points around the crossroad, the purpose is still unknown and needs further research. TrafficLightSemaphores - specifies the traffic light phases. The crossroad usually defines 2 phases in case it is controlled or empty list otherwise. There is one crossroad in game that defines 3 of them.

Road junctions

RoadJunction {
    ushort FromRoadGraphEdgeIndex;
    byte FromLaneIndex;
    ushort ToRoadGraphEdgeIndex;
    byte ToLaneIndex;
    byte Unkn4;
    byte Unkn6;
    ushort Unkn8;
    RoadSpline Spline;
}

The structure represents a road lanes junction. First four fields FromRoadGraphEdgeIndex, FromLaneIndex, ToRoadGraphEdgeIndex and ToLaneIndex point to start and end road/lanes that the current junction connects. The Unkn4 field always is 255. The Unkn6 can be one of the following values: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 or 10. The Unkn8 field represents some mask. The working theory is that it can define junctions self-intersections or maybe some priorities (there is a function in game that iterates over the Crosroad.Junctions and checks the corresponding bit of this mask). The Spline specifies a spline on which the junction is built.

Semaphores

TrafficLightSemaphore {
    byte Unkn0_0;  // 4 bits
    byte Unkn0_4;  // 4 bits
    byte Unkn0_8;  // 4 bits
    byte Unkn0_12; // 4 bits
    ushort Unkn2;
    List<ushort> ManagedRoads;
}

First four fields are unknown at the moment, each of them can have value of 0, 1 or 2. The Unkn2 usually has value 100 or 50, most likely the value is related to the duration but it is unclear for now. The ManagedRoads refers the managed RoadGraph edges (type Road). In the classic game edition size of the list must be a multiple of two, in case there is a need to refer the odd amount of roads the 65535 value is added to the end of list.

RoadGraph and costs

CostMapEntry {
    RoadGraphEdgeType RoadGraphEdgeType; // Road or CrossroadJunction 
    ushort RoadGraphEdgeLink;
    ushort Cost; 
}

The road graph is represented by list of graph edges and their hierarchy mapping. In the classic game edition the hierarchy represented by two lists of indices, in the definitive edition - by one list of index pairs. The edge list is build in the way that the each road defines its edge and then defines edges for all the crossroad junctions that have start at the end of this road. The RoadGraphEdgeLink value refers a road in case it's a Road edge and a crossroad in case it's CrossroadJunction edge. The Cost value represents the graph weight . For the road edges cost can be calculated using the following code snippet (at least calculated values are identical to the original ones):

private ushort CalculateRoadCost(RoadDefinition road, float splineLength)
{
    bool hasHighwayFlag = false;
    bool hasMainRoadLaneType = false;
    
    for (int i = road.OppositeLanesCount; i < road.Lanes.Items.Count; i++)
    {
        var lane = road.Lanes.Items[i];
        
        if (lane.LaneFlags.HasFlag(LaneFlags.Highway))
        {
            hasHighwayFlag = true;
        }

        if (lane.LaneType == LaneType.MainRoad)
        {
            hasMainRoadLaneType = true;
        }
    }
    
    float multCoef = 1.0f;
    if (hasHighwayFlag)
    {
        multCoef = 0.5f;
    }
    else if (hasMainRoadLaneType)
    {
        multCoef = 0.75f;
    }
    else
    {
        multCoef = 1.5f;
    }
            
    return (ushort) (splineLength * multCoef);
}

Junction cost calculation algorithm is not researched yet.

Research/Xml/Debug

To make the research easier the Q&D xml serializer/deserializer was written. It makes it possible to make quick changes via notepad and see the possible result in the game. Code snippets how to use:

// serialization
var roadmap = new RoadmapCe(); // or new RoadmapDe
String pathToRoadmapFile = "C:\\temp\\roadmap.gsd"; // path to gsd or game file
String outXmlPath = "C:\\temp\\out.xml";
using (FileStream fileStream = File.Open(pathToRoadmapFile, FileMode.Open))
{
    roadmap.Read(fileStream);
    var roadmapXmlSerializer = new RoadmapXmlSerializer();
    roadmapXmlSerializer.Serialize(roadmap, outXmlPath);
}

// deserialization
var roadmapFactory = new RoadmapFactoryCe(); // or new RoadmapFactoryDe()
String pathToXml = "C:\\temp\\editedRoadmap.xml";
String outRoadmapPath = "C:\\temp\\editedRoadmap.gsd"; // path to gsd or game file
var roadmapXmlSerializer = new RoadmapXmlSerializer();
var newRoadmap = roadmapXmlSerializer.Deserialize(roadmapFactory, pathToXml);
using (FileStream ourFileStream = File.Open(outRoadmapPath, FileMode.OpenOrCreate))
{
    newRoadmap.Write(ourFileStream);
}