Энциклопедия алгоритмов HoMM 3

Предлагаю делиться знаниями в области программного кода Героев 3. Например, в виде псевдокода.

С-подобный псевдокод для процедуры int __userpurge sub_00438D50, с помощью которой AI определяет "ценность" заклинания Ослепление в битве (рассчитывая, стоит ли его применить). Процедура вызывается из 43A2CO.

Код: Выделить всё

int __userpurge sub_00438D50(int StackInBottom, int pBattleMonster, int SpellNumber, int ShoolLevel, int MagicPower, int Duration, char a8)

/*
Порядок поступления в стэк:
int StackInBottom
char a8
int Duration
int MagicPower
int ShoolLevel
int SpellNumber
int pBattleMonster
*/
{
   pBattleMonster = *(Ebp + 0x8);
   BattleMonsterNumber = *(pBattleMonster + 0xF8);
   Flag1 = 1 << *(DWORD*) BattleMonsterNumber;
   allMonstersWithinAttackBits = *(StackInBottom + 0x14);
   withinMonsterAttack = allMonstersWithinAttackBits & Flag1;
   
   if !(withinMonsterAttack) then
      return 0;
   else
   {
      SomeBattleState = *(BYTE*) *(StackInBottom + 0x1C);
      if(SomeBattleState)
         return 0;
      else
      {
         BattleMonsterFightValue = call combatMonster_00442B80 (pBattleMonster, *(StackInBottom + 0x20), *(StackInBottom + 0x24));
         allMonstersRating = *(StackInBottom + 0x38);
         
         if (BattleMonsterFightValue >= allMonstersRating)
            call RareSituationMayBeMonsterAlone;
         else
         {   
            Duration = *(Ebp + 0x18);
            ProbableBattleDurationOrArmiesRelation = *(StackInBottom + 0x3C);

            if (Duration  < ProbableBattleDurationOrArmiesRelation)
               Multiplier = Duration / ProbableBattleDurationOrArmiesRelation;
            else
               Multiplier = 1.0;
            
            BattleMonsterTireFlag = *(DWORD *)(pBattleMonster + 0x84) >> 26;
            if (BattleMonsterTireFlag == 1)
               return 0;
            else
            {
               Result = Multiplier * BattleMonsterFightValue;
               if (a8 == 0)
                  return Result;
               else
               {
                  Result = Result * call CombatMan_CreatureMagicResist( pCombatManager,SpellNumber,*(StackInBottom + 0xC),0,1,*(BYTE *)(StackInBottom + 0x1D) != 0);
                  return Result;
               }
            }
         }

      }

   }
}



StackInBottom - часть стэка внизу, которая не очищается, а передается из процедуры в процедуру. Играет большое значение для расчетов AI в битве. Заполняется в процедуре 41EC40, возможно, еще где-то.

sub_43B2E0 - это свитч, выбирающий функцию вычисления ценности заклинания в зависимости от его номера. Вызывается из 4-х мест:

Код: Выделить всё

sub_4396D0+6C call    sub_43B2E0
sub_43A2C0+14 call    sub_43B2E0
sub_43A560+39 call    sub_43B2E0
sub_43C0F0+9E call    sub_43B2E0

sub_00491640 orders dialog to close when used in dialog proc on an item that does not necessarily have close_dlg = TRUE flag (e.g. _DlgButton_)

Код: Выделить всё

int __stdcall sub_00491640(_EventMsg_ *msg)
{
msg->type = 0x200; // MT_MOUSEBUTTON
msg->subtype = 0x0A;
msg->item_id = 0x0A;
_WndMgr_->result_dlg_item_id = 0;
return 2;
}


Used here for example:

Ряд алгоритмов, используемых AI в битве:

1) Перед каждой битвой с участием AI комп вычисляет соотношение сил армий, причем чем ближе оно к 1, тем большее число сопоставляет компьютер. То есть он рассматривает эту величину приблизительно как ожидаемую продолжительность битвы (вернее, ее решающей фазы).

2) Комп создает и апдейтит набор битов (1 набор на всю армию - армию противника компа), отражающих возможность каждого отряда "дотянуться" до противника.

Данная система использует поля _CombatMonster_ (это уже для своей армии - для каждого отряда):
0x544 - здесь набор битов, определяющих до каких номеров (отрядов) противника дотягивается данный наш отряд.
0x538 - адрес одного из отрядов, который наш отряд мог бы ударить.
У отрядов, уже сделавших ход, бит 0x544 все равно ненулевой, если в следующий ход они смогли бы нанести удар, хотя бы гипотетически. Зато отряд, который в данный момент должен ходить имеет данный бит равным нулю. Только перед началом битвы данный отряд иногда имеет бит равный 1.
Именно поэтому комп не может наложить Жажду крови, Палача и др. на юнита и сразу же пойти и ударить данным юнитом.

Еще один момент - у стрелков 0x544 нулевой, за исключением случаев рукопашной, только перед началом битвы он ненулевой.

Вообще, возможно, вся данная система далека от безупречной работы и, как и многие другие участки кода в игре, приводит к тому, что комп иногда делает не самые полезные для себя вещи (как говорится в народе, откровенно тупит).
Во всяком случае, для процедур типа combatMan_00437D50_BloodlustWeightAI можно было бы безболезненно и с пользой заменить использование поля 0x538 на актуальный расчет возможности дотянуться до противника (такой код все равно в игре где-то есть).

Interesting, it might be related to something I'm trying to fix.

In HotA, they added this "fix"...

Цитата:

*AI returns from an endless loop when having a huge army.
*Добавлен вывод ИИ из бесконечного цикла при слишком большой армии.

... but it is incomplete.
An AI with very large army with the "fix" will sometimes run into battle against very weak opponent and lose.

From my understanding of looking at the HotA fix, their solution is to prevent AI from swapping stacks endlessly.
On my end I achieved a similar result by modifying sub_00491640 GetArmyAIValue so that it only returns positive values, but AI hero still runs in battle and dies.

Код: Выделить всё

unsigned int __thiscall ssub_00491640 GetArmyAIValue(_Army_ *army)
{
int i = 0;
result = 0;
while ( i < 7 );
{
    if ( army->type[i] != -1 )
        result += o_pCreatureInfo[army->type[i]].fight_value * army->count[i];
    i++;
}
return result;
}

I assumed there is another check somewhere but I did not spend any time to look for it so far.

Кусок кода, позволяющий создать массив miPassability[mapSize][mapSize], содержащий логические значения -
проходима ли данная клетка карты.

Возможно, где-то в игре есть уже готовая структура, ссылающаяся на уже готовый подобный массив
(например, структура 0x6992D4 AccessableSquaresStruct), но на данный момент это достоверно неизвестно.

Код: Выделить всё

int objectsNumber;
    int bitCounter;
    int impassNumber;
    int templateId;
    int x,y;
    bool passability;
    int mapSize = o_GameMgr->GetMapWidth();
    bool **miPassability = new bool*[mapSize];
    for (x = 0; x < mapSize; x++)
        miPassability[x] = new bool[mapSize];

    for(x = 0; x < mapSize; x++)
        for(y = 0; y < mapSize; y++)
            miPassability[x][y] = true;

    objectsNumber = ((int)o_GameMgr->Map.Objects.EndData - (int)o_GameMgr->Map.Objects.Data)/12;
    for(int n = 0; n < objectsNumber; n++)
    {
        templateId = o_GameMgr->Map.Objects[n].template_id;
        x = o_GameMgr->Map.Objects[n].x - 8;
        y = o_GameMgr->Map.Objects[n].y - 6;

        bitCounter = -1;
        impassNumber = (int)o_GameMgr->Map.Templates[templateId].ImpassBitMask.bits0;
        if(impassNumber != -1)
        {
            for(int i = 0; i < 4; i++)
            {
                y = y + 1;
                for(int j = 0; j < 8; j++)
                {
                    x = x + 1;
                    bitCounter = bitCounter + 1;
                    passability = (impassNumber >> bitCounter) & (int)1;
                    if(x>=0 && y>=0 && passability == false)
                        miPassability[x][y] = false;
                }
                x = x - 8;
            }
        }
        else
            y = y + 4;

        bitCounter = -1;
        impassNumber = (int)o_GameMgr->Map.Templates[templateId].ImpassBitMask.bits32;
        for(int i = 0; i < 2; i++)
        {
            y = y + 1;
            for(int j = 0; j < 8; j++)
            {
                x = x + 1;
                bitCounter = bitCounter + 1;
                passability = (impassNumber >> bitCounter) & (int)1;
                if(x>=0 && y>=0 && passability == false)
                    miPassability[x][y] = false;
            }
            x = x - 8;
        }
    }


Я точно уже не помню, зачем мне было это нужно, но, кажется, для нахождения минимального расстояния между тайлами без учёта временно непроходимых объектов (таких, например, как кучки ресурсов, артефакты, герои и т.п.). Это очень полезная фича для оффлайн-турниров. Попробую поразбираться.

RoseKavalier

Код: Выделить всё

INT32 move_type; // +0x132DC ~ 01 move, 03 ~ range, 05 ~ hover your allies, 07 ~ melee attack, 15 ~ half ranged damage

   Pointer Type
0   Null/Not Allowed
1   Move
2   Fly
3   Shooting (Arrow)
4   Hero (Helmet)
5   Question Mark
6   Arrow Pointer
7   Attack Northeast (Sword)
8   Attack East (Sword)
9   Attack Southeast (Sword)
10   Attack Southwest (Sword)
11   Attack West (Sword)
12   Attack Northwest (Sword)
13   Attack North (Sword)
14   Attack South (Sword)
15   Half Damage (Broken Arrow)
16   Attack Wall (Catapult)
17   Heal
18   Sacrifice
19   Teleport


_Player_*
field_30[4]

Содержит тип ИИ (Воин, Строитель, Исследователь).

Нашел на ДФ в посте MoP