Antal1987
Warlord
I'm investigating the submarine bug using very simple scenario:
Simulation scene:
Every time I skip turn, the Galeon tries to move througn the submarine.
However, if I replace the submarine with the carrier, it doesn't happen.
I started to figure out why this is happening
I found out that every time the Game computes possible movements for AI unit it builds a movement graph. The graph contains information about current unit tile neighbours. For Naval or Air unit radius (the depth) of graph searching (in affinite coordinates) is 7. For Land unit it is 9.
Graph searhing are implemented in Trade Net class:
The address of Trade_Net in C3C v1.22: 0x00B72848
Matrix is array of int[512][512] - it containt info about Cities in Trade Net. That's why max cities count is 512 (0x200)
The address of Trade_Net.Matrix: 00B72880
I don't know yet what are those Data2, Data3, Data4 and Data5. But for naval unit Trade Net uses Data2 as Global Tiles Distance Info (Data_R1) and Data3 as Current Depth Distance Info (Data_R2).
In certain conditions (I don't known them) Data_R1 = Data4; Data_R2 = Data5;
Here is the structure of Distance Info Item:
I suppose Trade Net uses kind of breadth-first search (BFS) algorithm (see)
BFS calculates distances and weights (masses) of vertices level by level. A level is a group of vertices with the same distance. So in C3C it calculates for each Tile in Radius optimal direction to the graph root (Current Unit Tile).
Here are directions values used by Trade Net BFS. Lets call it Graph Direction. Because there are Movement Directions.
Movement Directions:
And here is part of result given by Trade Net BFS when it finished. (Sorry about that handwritten image). The image corresponds to simulation scene.
Source - Current Unit (the Galeon)
Subm - the Submarine
Target 1 and Target 2 are the points to which the game calculates routes.
W - weight, means movement cost
D - Direction to root
Well, there is a function which returns optimal movement direction from origin position (source) to target. It also returns movement cost.
It's address: 0x005802A0.
I do not share the code here, because it's too big and it has many different calls to relevant functions which are big too.
Let's look at the simulation scene.
The Galeon has coordinated [0x1C, 0x46]
The Submarine has coordinated [0x1D, 0x47]
class_Trade_Net::Get_Optimal_Direction(Trade_Net, 0x1C, 0x46, 0x1D, 0x47, Galeon, Galeon.Civ.ID, Flags, &Moves) == 3
class_Trade_Net::Get_Optimal_Direction(Trade_Net, 0x1C, 0x46, 0x1E, 0x48, Galeon, Galeon.Civ.ID, Flags, &Moves) == 3
But if I replace the submarine with the carrier
class_Trade_Net::Get_Optimal_Direction(Trade_Net, 0x1C, 0x46, 0x1D, 0x47, Galeon, Galeon.Civ.ID, Flags, &Moves) == 0
class_Trade_Net::Get_Optimal_Direction(Trade_Net, 0x1C, 0x46, 0x1E, 0x48, Galeon, Galeon.Civ.ID, Flags, &Moves) == 0
If the game takes 0 as optimal direction it doesn't use the corresponding tile into future graph calculations. So because of Get_Optimal_Direction returning 0 (when the carrier is near by the galeon), the galeon doesn't move anywhere, it just skips turn.
But if it's the submarine near by, the galeon "thinks": "the road is open, let's move out"...
I've manage to found a root of that behaviour.
There is a function, which checks whether some unit occipies a tile.
int __stdcall f_Get_Tile_OccupantID(int X, int Y, int CivID, bool Flag)
it's address: 0x0056D740
X, Y - coordinates of tile being checked
CivID - Id of civ which requests the game of checking the tile.
In this case, CivID = Galeon.Civ.ID
Flag - ??? (does't affect on result)
it returns -1 if there are no visible units in [X, Y]
If in [X, Y] there is at leat 1 visible unit of some Civ, it returns ID of that Civ.
It returns 0 if a unit in [X, Y] has Hidden Nationality flag.
Here are some tests:
f_Get_Tile_OccupantID(Submarine.X, Submarine.Y, Galeon.Civ.ID) == -1
f_Get_Tile_OccupantID(Submarine.X, Submarine.Y, Submarine.Civ.ID) == 1 (Player Civ)
f_Get_Tile_OccupantID(Carrier.X, Carrier.Y, Galeon.Civ.ID) == 1 (And here is the root of misbehavoiur)
f_Get_Tile_OccupantID(Galeon.X, Galeon.Y, Galeon.Civ.ID) == 3 (Inca Civ)
Here is the code:
Function class_Unit::Check_Unit_Visibility(class_Unit * this, int CivID) returns 0 - if unit is invisible for CivID, and 1 - otherwise.
class_Unit::Check_Unit_Visibility(Carrier, Galeon.Civ.ID) == 1
class_Unit::Check_Unit_Visibility(Submarine, Galeon.Civ.ID) == 0
Therefore, the first solution can be changing the code to make f_Get_Tile_OccupantID return Submarine.Civ.ID instead of -1. That will make the Galeon skip turn instead of triyng pass the tile where the submarine is situated.
P.S. Do not quote the entire post. Shrink it.
Simulation scene:
Every time I skip turn, the Galeon tries to move througn the submarine.
However, if I replace the submarine with the carrier, it doesn't happen.
I started to figure out why this is happening
I found out that every time the Game computes possible movements for AI unit it builds a movement graph. The graph contains information about current unit tile neighbours. For Naval or Air unit radius (the depth) of graph searching (in affinite coordinates) is 7. For Land unit it is 9.
Graph searhing are implemented in Trade Net class:
Code:
#pragma pack(push, 1)
struct class_Trade_Net
{
int vtable;
int Map_Width;
int Current_Unit_X;
int Current_Unit_Y;
class_Unit *Current_Unit;
int Current_Unit_CivID;
int Flags;
int *Data1;
struct_Trade_Net_Distance_Info *Data2;
struct_Trade_Net_Distance_Info *Data3;
int V1;
struct_Trade_Net_Distance_Info *Data4;
struct_Trade_Net_Distance_Info *Data5;
int V2;
int Matrix[262144];
};
#pragma pack(pop)The address of Trade_Net in C3C v1.22: 0x00B72848
Matrix is array of int[512][512] - it containt info about Cities in Trade Net. That's why max cities count is 512 (0x200)
The address of Trade_Net.Matrix: 00B72880
I don't know yet what are those Data2, Data3, Data4 and Data5. But for naval unit Trade Net uses Data2 as Global Tiles Distance Info (Data_R1) and Data3 as Current Depth Distance Info (Data_R2).
In certain conditions (I don't known them) Data_R1 = Data4; Data_R2 = Data5;
Here is the structure of Distance Info Item:
Code:
#pragma pack(push, 1)
struct struct_Trade_Net_Distance_Info
{
__int16 field_0;
char Remained_Moves;
char Direction;
__int16 field_4;
__int16 Moves;
__int16 field_8;
__int16 field_A;
__int16 Tile_Index;
__int16 Radius_Neighbour_Index;
};
#pragma pack(pop)I suppose Trade Net uses kind of breadth-first search (BFS) algorithm (see)
BFS calculates distances and weights (masses) of vertices level by level. A level is a group of vertices with the same distance. So in C3C it calculates for each Tile in Radius optimal direction to the graph root (Current Unit Tile).
Here are directions values used by Trade Net BFS. Lets call it Graph Direction. Because there are Movement Directions.
Movement Directions:
Code:
8
7 1
6 0 2
5 3
4And here is part of result given by Trade Net BFS when it finished. (Sorry about that handwritten image). The image corresponds to simulation scene.
Source - Current Unit (the Galeon)
Subm - the Submarine
Target 1 and Target 2 are the points to which the game calculates routes.
W - weight, means movement cost
D - Direction to root
Well, there is a function which returns optimal movement direction from origin position (source) to target. It also returns movement cost.
Code:
int __thiscall class_Trade_Net::Get_Optimal_Direction(class_Trade_Net *this, int X, int Y, int Target_X, int Target_Y, class_Unit *Unit, int CivID, int Flags, int *p_Moves)
X, Y - Origin Position
Target_X, Target_Y - target position
Unit - Current Unit (the Galeon)
CivID - Current Unit Civ ID
Flags - ???
p_Moves - pointer to variable used to store movement cost.
Returns movement directionI do not share the code here, because it's too big and it has many different calls to relevant functions which are big too.
Let's look at the simulation scene.
The Galeon has coordinated [0x1C, 0x46]
The Submarine has coordinated [0x1D, 0x47]
class_Trade_Net::Get_Optimal_Direction(Trade_Net, 0x1C, 0x46, 0x1D, 0x47, Galeon, Galeon.Civ.ID, Flags, &Moves) == 3
class_Trade_Net::Get_Optimal_Direction(Trade_Net, 0x1C, 0x46, 0x1E, 0x48, Galeon, Galeon.Civ.ID, Flags, &Moves) == 3
But if I replace the submarine with the carrier
class_Trade_Net::Get_Optimal_Direction(Trade_Net, 0x1C, 0x46, 0x1D, 0x47, Galeon, Galeon.Civ.ID, Flags, &Moves) == 0
class_Trade_Net::Get_Optimal_Direction(Trade_Net, 0x1C, 0x46, 0x1E, 0x48, Galeon, Galeon.Civ.ID, Flags, &Moves) == 0
If the game takes 0 as optimal direction it doesn't use the corresponding tile into future graph calculations. So because of Get_Optimal_Direction returning 0 (when the carrier is near by the galeon), the galeon doesn't move anywhere, it just skips turn.
But if it's the submarine near by, the galeon "thinks": "the road is open, let's move out"...
I've manage to found a root of that behaviour.
There is a function, which checks whether some unit occipies a tile.
int __stdcall f_Get_Tile_OccupantID(int X, int Y, int CivID, bool Flag)
it's address: 0x0056D740
X, Y - coordinates of tile being checked
CivID - Id of civ which requests the game of checking the tile.
In this case, CivID = Galeon.Civ.ID
Flag - ??? (does't affect on result)
it returns -1 if there are no visible units in [X, Y]
If in [X, Y] there is at leat 1 visible unit of some Civ, it returns ID of that Civ.
It returns 0 if a unit in [X, Y] has Hidden Nationality flag.
Here are some tests:
f_Get_Tile_OccupantID(Submarine.X, Submarine.Y, Galeon.Civ.ID) == -1
f_Get_Tile_OccupantID(Submarine.X, Submarine.Y, Submarine.Civ.ID) == 1 (Player Civ)
f_Get_Tile_OccupantID(Carrier.X, Carrier.Y, Galeon.Civ.ID) == 1 (And here is the root of misbehavoiur)
f_Get_Tile_OccupantID(Galeon.X, Galeon.Y, Galeon.Civ.ID) == 3 (Inca Civ)
Here is the code:
Code:
int __stdcall f_Get_Tile_OccupantID(int X, int Y, int CivID, bool Flag)
{
int v4; // ebx@0
int v5; // edi@1
int v6; // esi@1
__int16 v7; // bp@1
unsigned __int16 v8; // ax@1
class_Tile *v9; // eax@1
class_Tile *v10; // eax@2
signed int _Unit_Civ_ID; // esi@2
class_Tile *v12; // eax@3
class_Tile *v13; // eax@4
int _Civ_ID_Hidden; // ebp@4
class_Tile *v15; // eax@5
int v16; // eax@5
int _Tile_UnitID; // eax@5
class_Unit *_Tile_Unit; // esi@6
struct_Base_List_Item *v19; // eax@14
class_Tile *v20; // eax@20
int v21; // eax@20
int i; // eax@20
void *v23; // eax@24
class_Unit *v24; // esi@25
class_Tile *v25; // eax@35
int result; // eax@36
signed int v27; // [sp+Ch] [bp-4h]@4
v5 = Y;
v6 = X;
v7 = X >> 1;
v8 = (X >> 1) + Y * (BIC_Data.Map.Width >> 1);
LOWORD(X) = X >> 1;
v9 = class_Map::GetTile(&BIC_Data.Map, v8);
if ( class_Tile::Check_City(v9) )
{
v10 = class_Map::GetTile(&BIC_Data.Map, (v7 + v5 * (BIC_Data.Map.Width >> 1)));
_Unit_Civ_ID = v10->vtable->m69_get_Tile_City_CivID(v10);
}
else
{
v12 = class_Map::GetTile(&BIC_Data.Map, (v7 + v5 * (BIC_Data.Map.Width >> 1)));
if ( v12->vtable->m26_Check_Tile_Building(v12) )
{
v13 = class_Map::GetTile(&BIC_Data.Map, (v7 + v5 * (BIC_Data.Map.Width >> 1)));
v27 = v13->vtable->m70_Get_Tile_Building_OwnerID(v13);
_Civ_ID_Hidden = -1;
if ( !class_Map::f18_Check_XY_Valid(&BIC_Data.Map, v6, v5)
|| (v15 = f_Get_Map_Tile_by_XY(v6, v5),
v16 = v15->vtable->m40_get_TileUnit_ID(v15),
_Tile_UnitID = class_TileUnits::Get_Unit_ID(&Tile_Units, v16, &Y),
_Tile_UnitID == -1) )
goto LABEL_40;
do
{
_Tile_Unit = class_Base_List::Get_Item(&Units, _Tile_UnitID);
if ( _Tile_Unit && (!Flag || CivID == -1 || class_Unit::Check_Unit_Visibility(_Tile_Unit, CivID, 1)) )
{
_Civ_ID_Hidden = class_Unit::Check_Hidden_For_Civ(_Tile_Unit, CivID);
if ( _Civ_ID_Hidden )
break;
}
if ( Tile_Units.Base.Items && Y >= 0 && Y <= Tile_Units.Base.LastIndex )
{
v19 = &Tile_Units.Base.Items[Y];
Y = v19->V;
_Tile_UnitID = v19->Object;
}
else
{
_Tile_UnitID = Tile_Units.DefaultValue;
Y = -1;
}
}
while ( _Tile_UnitID != -1 );
if ( _Civ_ID_Hidden != -1 )
_Unit_Civ_ID = _Civ_ID_Hidden;
else
LABEL_40:
_Unit_Civ_ID = v27;
v7 = X;
}
else
{
Y = -1;
if ( class_Map::f18_Check_XY_Valid(&BIC_Data.Map, v6, v5) )
{
v20 = f_Get_Map_Tile_by_XY(v6, v5);
v21 = v20->vtable->m40_get_TileUnit_ID(v20);
for ( i = class_TileUnits::Get_Unit_ID(&Tile_Units, v21, &X);
i != -1;
i = class_TileUnits::Get_Unit_ID(&Tile_Units, X, &X) )
{
if ( Units.Items )
{
if ( i >= 0 )
{
if ( i <= Units.LastIndex )
{
v23 = Units.Items[i].Object;
if ( v23 )
{
v24 = (v23 - 28);
if ( v23 != 28 )
{
if ( !Flag || CivID == -1 || class_Unit::Check_Unit_Visibility(v24, CivID, 1) )
{
Y = class_Unit::Check_Hidden_For_Civ(v24, CivID);
if ( Y )
break;
}
}
}
}
}
}
}
}
_Unit_Civ_ID = Y;
}
}
if ( _Unit_Civ_ID == -1
&& (v25 = class_Map::GetTile(&BIC_Data.Map, (v7 + v5 * (BIC_Data.Map.Width >> 1))),
LOBYTE(v4) = (CivID == -1) - 1,
v25->vtable->m7_Check_Barbarian_Camp(v25, CivID & v4)) )
result = 0;
else
result = _Unit_Civ_ID;
return result;
}Function class_Unit::Check_Unit_Visibility(class_Unit * this, int CivID) returns 0 - if unit is invisible for CivID, and 1 - otherwise.
class_Unit::Check_Unit_Visibility(Carrier, Galeon.Civ.ID) == 1
class_Unit::Check_Unit_Visibility(Submarine, Galeon.Civ.ID) == 0
Therefore, the first solution can be changing the code to make f_Get_Tile_OccupantID return Submarine.Civ.ID instead of -1. That will make the Galeon skip turn instead of triyng pass the tile where the submarine is situated.
P.S. Do not quote the entire post. Shrink it.
, it is the original version of Civ 3 and its patches. Later versions are the expansions PtW and C3C.
