јвтор: ќлекс≥й —Їдов
ƒата: 05.03.06.

¬ ц≥й статт≥ ¤ спробую коротко описати один з можливих вар≥ант≥в алгоритму побудови шл¤ху у стратег≥чн≥й гр≥. ƒаний алгоритм ¤ розробив самост≥йно ≥ усп≥шно випробував на своњй RTS Ђ«емл¤ он≥мод≥вї.

ќтже, розпочнемоЕ

як ви гадаЇте, на побудову ¤кого шл¤ху витрачаЇтьс¤ б≥льше всього процесорного часу? «вичайно, це такий шл¤х, де мети дос¤гти неможливо. јдже, аби переконатис¤, що до мети д≥йти справд≥ не можна, доведетьс¤ обшарити вс≥ потаЇн≥ куточки вашого ≥грового св≥ту. ¬иходить, треба знайти р≥шенн¤, при ¤кому без побудови шл¤ху, можна буде одразу визначити, чи дос¤жна мета чи н≥. ƒл¤ цього пропоную ввести пон¤тт¤ "район" ≥ визначити його так: ¤кщо з одн≥Їњ кл≥тинки можна потрапити до ≥ншоњ, то вони в≥днос¤тьс¤ до того самого району, в ≥ншому випадку - райони р≥зн≥. “епер, ¤кщо ми заздалег≥дь (тобто при старт≥ карти) визначимо дл¤ кожноњ кл≥тинки номер њњ району, то це ≥ буде р≥шенн¤м проблеми. “обто тепер можна буде в≥дразу дов≥датис¤ чи можна з крапки ј д≥йти до крапки Ѕ.

якщо район крапки ј дор≥внюЇ району крапки Ѕ, то шл¤х будувати можна. ≤накше Ѕ дос¤гти неможливо. ƒо реч≥, неможлив≥сть дос¤гти крапки Ѕ не означаЇ, що до нењ не потр≥бно рухатис¤, але про це мова йтиме п≥зн≥ше.

–озд≥лити ≥грове поле на райони дуже просто. ƒл¤ цього досить дл¤ кожноњ кл≥тинки пол¤ завести ще одну перем≥нну, у ¤к≥й ≥ буде збер≥гатис¤ номер району. ƒал≥ потр≥бно у вс≥х кл≥тинках про≥н≥ц≥ал≥зувати район числом 0.

“епер приступимо до визначенн¤ район≥в. ƒл¤ цього проб≥гаЇмо по вс≥х кл≥тинках карти ≥ дл¤ кожноњ з них виконуЇмо наступне:

int ≥ндекс_району = 1;
for (int x = 0; x < довжина_карти; x++)
  for (int y = 0; y < висота_карти; y++)
    if (поле[x][y].район != 0 && поле[x][y] != перешкода)
    {
      // дл¤ даноњ кл≥тинки треба визначити район
      // робимо це методом заливки
      Fill(x, y, ≥ндекс_району);
      ≥ндекс_району++;
    }

‘ункц≥¤ Fill(int x, int y, int ≥ндекс_району) повинна працювати за аналог≥Їю з≥ звичайною кол≥рною заливкою. “обто заповнювати дл¤ кл≥тинок перем≥нну Ђрайонї цифрою Ђ≥ндекс_районуї. ѕриродно, що п≥д час заливки т≥ кл≥тинки, на ¤к≥ не можна Ђнаступитиї повинн≥ слугувати границею.

ѕропонований мною метод дуже простий ≥ зазвичай не вимагаЇ н≥¤кого налагодженн¤. ÷ю просту думку мен≥ п≥дкинув м≥й товариш –оман  оваленко у далекому 1993 роц≥. ” т≥ часи ¤ з PC комп'ютерами взагал≥ не був знайомий, ми програмували на саморобних Spectrum-ах, на чистому асемблер≥. “од≥ одинак-програм≥ст був "один у поле воњн", а заразЕ на жаль, без колективу н≥куди. Ќудно все цеЕ

јле, повернемос¤ до теми статт≥. ќтже такЕ

—творюЇте 2 однакових масиви великоњ довжини (щоб не переповнилис¤), у ¤к≥ будуть складатис¤ координати x, y. ўоб почати заливку занес≥ть у перший масив координату початку.

—ам цикл заливки вигл¤даЇ таким чином:

for (i = 0; i < к≥льк≥сть_координат_у_масив≥1; i++)
{
  int x = масив1[i].x;
  int y = масив1[i].y;
  поле[x][y].район = ≥ндекс_району;
  // тепер треба перев≥рити вс≥ сус≥дн≥ кл≥тинки на можлив≥сть заливки
  // сус≥дн≥х кл≥тинок буде або 8 або 4, залежно в≥д того, чи вм≥ють ваш≥
  // юн≥ти протискуватис¤ в щ≥лини по д≥агонал≥.
  ЕЕЕЕЕЕЕЕЕЕЕ
  ЕЕЕЕЕЕЕЕЕЕЕ

  
  ЕЕЕЕЕЕЕЕЕЕЕ
  ЕЕЕЕЕЕЕЕЕЕЕ
  // ¤кщо сус≥дн¤ кл≥тинка п≥дходить дл¤ заливки (на нењ можна встати, вона не
  // виходить за поле ≥ поки не була залитою), то заносимо њњ координати у масив2:
  масив2[к≥льк≥сть_координат_у_масив≥2].x = x_сус≥да;
  масив2[к≥льк≥сть_координат_у_масив≥2].y = y_сус≥да;
  к≥льк≥сть_координат_у_масив≥2++;
}

ƒал≥ йде такий самий цикл, т≥льки вже по масиву2, але в≥н вже заносить координати сус≥д≥в у масив1.

ќбидва ц≥ цикли потр≥бно "крутити" (в≥д перекладача: повторювати) поки до одного з масив≥в не буде занесено жодноњ координати, що ≥ буде означати, що заливку району зак≥нчено, тобто return.

ѕ≥сл¤ визначенн¤ вс≥х район≥в масив1 ≥ масив2 можна видалити. ѕроте тепер кожна кл≥тинка приписана до свого району. Ќеприписаними залишатьс¤ лише кл≥тинки, на ¤к≥ встати не можна (район=0) через на¤вн≥сть будь-¤коњ перешкоди.

Ќасправд≥ на цьому питанн¤ район≥в далеко не вичерпане. Ќараз≥ ми виконали т≥льки те, що Ђнеобх≥дно ≥ вистачитьї. Ќаприклад, можна знайти к≥лька причин, з ¤ких може знадобитис¤ перерозпод≥л район≥в п≥д час гри:

1. «олота руда, що ран≥ше не дозвол¤ла з'Їднатис¤ двом районам, була добута, тобто тепер ц≥ 2 райони треба було б об'Їднати.
2. ” вузькому проход≥ гравець побудував буд≥влю ≥ розд≥лив район на 2 частини. «нищенн¤ буд≥вл≥ теж може ≥нод≥ об'Їднати райони.
3. ћи визначили райони т≥льки дл¤ юн≥т≥в, що займають 1 кл≥тинку. јле ж де пройде людина, там катапульта може ≥ не проњхати. “обто в ≥деал≥ потр≥бно б ще визначати райони дл¤ об'Їкт≥в р≥зного розм≥ру.

“е, у ¤кому р≥вн≥ необх≥дно доводити райони до досконалост≥, багато в чому залежить в≥д особливостей гри. якщо перешкоди на ≥гровому пол≥ складаютьс¤ в основному з л≥су, ¤кий легко видобуваЇтьс¤ роб≥тниками, то, можливо, що пункт 1 реал≥зувати просто необх≥дно. ўо стосуЇтьс¤ моЇњ реал≥зац≥њ у гр≥ "«емл¤ он≥мод≥в", то ¤ вс≥х цих доробок не робив ≥, з≥знатис¤, не шкодую. ќднак при визначенн≥ район≥в ¤ зробив наступне допущенн¤: вважав ресурси ≥ буд≥вл≥ (тобто те, що може зникнути з карти) порожн≥м м≥сцем, тобто вони не перешкоджали об'Їднанню район≥в.

ƒал≥ ¤ вимушений у 2-х словах зупинитис¤ на загальнов≥домому хвильовому алгоритм≥ пошуку шл¤ху, тому що, можливо, що хтось про нього не знаЇ чи наш≥ у¤вленн¤ трохи розход¤тьс¤. ќтже такЕ

Ћог≥ка хвильового алгоритму под≥бна до лог≥ки заливки, що була застосована ран≥ше дл¤ визначенн¤ район≥в. “обто починаЇмо заливку з крапки ј ≥ зак≥нчуЇмо њњ, коли ц¤ "хвил¤" дос¤гне крапки Ѕ. ўоб пот≥м вит¤гти з хвил≥ сам шл¤х потр≥бно просто додатково запам'¤товувати дл¤ кожноњ кл≥тинки, ту кл≥тинку, з ¤коњ в нењ прийшла хвил¤. “обто потр≥бно буде пройтис¤ по цьому ланцюжку назад в≥д крапки Ѕ до крапки ј - це ≥ буде шуканий шл¤х. ƒодатково можна робити вс≥л¤к≥ корисн≥ реч≥, наприклад, ввести дл¤ кожноњ кл≥тинки "варт≥сть" проходу. “од≥ можна буде дл¤ болота призначати високу варт≥сть, що дозволить алгоритму обходити так≥ м≥сц¤, ¤кщо ≥снуЇ дешевший шл¤х.

јлгоритм можна оптим≥зувати, ¤кщо запускати одразу 2 хвил≥: ≥ з крапки ј, ≥ з крапки Ѕ. ” цьому випадку, треба виловлювати мить, коли хвил≥ з≥штовхнутьс¤, а дал≥ з'Їднувати 2 ланцюжки в один шл¤х.

1. Ўл¤х буде знайдений завжди ≥ причому найкращий.
2. ћожлив≥сть запровадженн¤ вартост≥ кл≥тинки.
3. ћожлив≥сть побудови шл¤ху не до одн≥Їњ мети, а одразу до дек≥лькох, тобто практично в≥дбуваЇтьс¤ пошук найближчоњ мети.
4. «розум≥л≥сть ≥ простота алгоритму.

“епер ¤к завжди трохи дьогтюЕ

¬икористанн¤ под≥бного р≥шенн¤ у стратег≥чн≥й гр≥, де передбачаЇтьс¤ велика к≥льк≥сть юн≥т≥в - в≥рний провал. „ому? “ому, що процесор просто "видохнетьс¤", намагаючись рухати к≥лька сотень юн≥т≥в по ≥гровому полю 256х256. Ќе буду н≥чого стверджувати з приводу DOOMопод≥бних ≥гор, можливо, що там це ≥ пот¤гне, тому що одночасно рухаЇтьс¤ дуже мало об'Їкт≥в ≥ на коротк≥ в≥дстан≥.

ƒавайте краще пом≥ркуЇмо над тим, ¤к з цього красивого, але зовс≥м неефективного методу створити те, що д≥йсно буде можливо застосувати на практиц≥ в супербатальн≥й RTS. ќтже такЕ проблема в тому, що хвил¤ повзе в ус≥ боки ≥ при цьому практично "обшарюЇ" величезну к≥льк≥сть кл≥тинок, ¤к≥ згодом будуть просто в≥дкинут≥. Ќаприклад, у моњй гр≥ Ђ«емл¤ он≥мод≥вї, максимальний розм≥р карти 504х504 (чому так≥ дивн≥ цифри по¤сню пот≥м), тобто, ¤кщо ¤ в≥дправлю усього лише одного воњна в протилежний кут карти, то ц≥лком можливо, що хвил¤ в≥дв≥даЇ приблизно половину вс≥х кл≥тинок на ≥гровому пол≥, а це буде: (504 * 504) / 2 = 127008. Ћише у¤в≥ть, ¤ка це величезна к≥льк≥сть. јле ж юн≥т≥в у вас буде багато ≥ побудова шл¤ху в≥дбуватиметьс¤ пост≥йно. ѕитанн¤Е ¤к скоротити цю к≥льк≥сть, причому так, щоб алгоритм утратив своњ черепашач≥ ¤кост≥, але при цьому м≥г завжди д≥статис¤ мети?

ќтжеЕ

–озбиваЇмо все наше ≥грове поле на б≥льш≥ кл≥тинки. ƒавайте ¤ назву ц≥ кл≥тинки дискретними. ” Ђ«емл≥ он≥мод≥вї ¤ використовував дискретними кл≥тинки з розм≥ром 6х6, тобто в кожн≥й кл≥тинц≥ знаходитьс¤ аж 36 звичайних кл≥тинок. я вибрав 6 через особливост≥ побудови ≥грового пол¤ в моњй гр≥, ви можете вибрати, прим≥ром, 8. –озм≥ри вашого ≥грового пол¤ мають бути кратними до розм≥р≥в дискретноњ кл≥тинки. “ому у моњй гр≥ максимальн≥ розм≥ри пол¤ 504х504.

ќтже такЕ суть у наступному: потр≥бно шукати шл¤х не по звичайних кл≥тинках, а по дискретних. ” цьому випадку дл¤ попереднього прикладу одержимо так≥ результати: ((504 / 6) * (504 / 6)) / 2 =3528. “обто теоретична оптим≥зац≥¤ з 127008 по 3528, а це в 36 раз≥в. “≥льки зам≥сть звичайних кл≥тинок ми одержимо шл¤х з дискретних кл≥тинок. Ќу ≥ що! “епер можна буде буде з'Їднувати дискретн≥ кл≥тинки хвилею, що будуватиметьс¤ по звичайних кл≥тинках, а тому-що дискретн≥ кл≥тинки завжди будуть сус≥дами, то це в≥дбуватиметьс¤ швидко.

ƒумку, гадаю, зрозум≥ли, але зовс≥м незрозум≥ло, що собою ¤вл¤Ї дискретна кл≥тинка, ≥ чому вона може зам≥нити собою 36 звичайних. “ому продовжуЇмоЕ

Ќайголовн≥ше Ц дискретна кл≥тинка розбиваЇтьс¤ усередин≥ на райони. “обто в њњ середин≥ може бути к≥лька район≥в, що не будуть з'Їднуватис¤. ƒуже важливо, що з'Їднуватис¤ райони не будуть т≥льки усередин≥ дискретноњ кл≥тинки, а за допомогою сус≥дн≥х дискретних кл≥тинок вони з'Їднуватис¤ можуть, але все р≥вно будуть рахуватис¤ ¤к р≥зн≥ райони. ÷е найважлив≥ший момент. ўе разЕ ƒискретна кл≥тинка мов би за аналог≥Їю з ус≥м ≥гровим полем под≥л¤Їтьс¤ на райони. –айони ц≥ не замикаютьс¤ саме усередин≥ дискретноњ кл≥тинки, але можуть замикатис¤ через сус≥дн≥ дискретн≥ кл≥тинки.

ƒискретн≥ кл≥тинки потр≥бно п≥дготувати заздалег≥дь, а дал≥ проводити њх оновленн¤ прот¤гом гри. я не буду в тонкощах описувати саму п≥дготовку, лише спробую роз≥брати безпосередньо устр≥й дискретноњ кл≥тинки. яким чином ви њх побудуЇте Ц справа ваша. ќсобисто ¤ використовував, знову ж, свою улюблену заливку.

’вилю, що будуватиме шл¤х по дискретних кл≥тинках, назвемо Ђдискретною хвилеюї. ” дискретн≥й хвил≥, на в≥дм≥ну в≥д звичайноњ, принцип визначенн¤ сус≥дньоњ кл≥тинки в≥др≥зн¤тиметьс¤. ƒавайте розберемос¤Е

якщо звичайна хвил¤ просто Ђрозт≥каЇтьс¤ї по вс≥х 8 сус≥дах кл≥тинки, то дискретна хвил¤ маЇ складн≥ший алгоритм визначенн¤ сус≥д≥в. ÷е пов'¤зано з тим, що район практично в≥д≥граЇ роль 3-оњ координати. “обто говорити про дискретну кл≥тинку з координатами 100, 100 безглуздо, тому що не вистачаЇ ще номера району.  ожен район повинен мати у своЇму склад≥ список доступних сус≥д≥в.

ƒл¤ прикладу розгл¤немо ситуац≥ю з жовтою дискретною кл≥тинкою. ¬она складаЇтьс¤ з 3-х район≥в, кожний з ¤ких може з'Їднуватис¤ з одним чи дек≥лькома районами ≥нших дискретних кл≥тинок.

∆овтий 1: „ервоний 1
∆овтий 2: «елений 1, ћалиновий 1
∆овтий 3: «елений 2, ћалиновий 1, Ѕлакитний 1

“обто ¤кщо дискретна хвил¤ ви¤вилас¤ в район≥ 2 жовтоњ кл≥тинки, то сус≥дами, ¤ких вона спробуЇ в≥дв≥дати будуть район 1 зеленоњ кл≥тинки ≥ район1 малиновоњ кл≥тинки.

«верн≥ть увагу на ще один малесенький нюанс. ћалиновий 1: ∆овтий 2, ∆овтий 3, Ѕлакитний 1, Ѕлакитний 2, «елений 2, Е тобто зв'¤зок з жовтою ≥ блакитною кл≥тинками в≥дбуваЇтьс¤ в≥дразу по 2-х районах.

ќдразу додам до цього ось що - дискретних кл≥тинок з дек≥лькома районами буде дуже мало. ѕрактично, завжди буде т≥льки 1 район, тому прир≥ст швидкост≥ буде близький до теоретично можливого.

ѕ≥дготувати дискретн≥ кл≥тинки зовс≥м не так просто, ¤к може показатис¤.

1. ƒвовим≥рний масив 6х6 байт, де потр≥бно збер≥гати номери район≥в. ƒл¤ чого в≥н узагал≥ потр≥бний? —права в тому, що звичайн≥ координати в дискретн≥ перевести дуже просто (под≥лити на 6), а от визначити номер району усередин≥ дискретноњ кл≥тинки Ц справа зовс≥м нелегка. “ому дл¤ оптим≥зац≥њ це краще зробити заздалег≥дь.
2.  ожен на¤вний район повинен мати список зв'¤зк≥в з ≥ншими дискретними кл≥тинками, причому кр≥м координат, повинен ще бути зазначений номер району. «ам≥сть координат краще використовувати код напр¤мку (ул≥во, догори тощо).
3. якщо заб≥гти вперед, то кожен район повинен мати ще так≥ пол¤:
   • ћаркер - буде використовуватис¤ в момент побудови хвил≥, щоб визначити, чи в≥дв≥дувала хвил¤ це м≥сце ран≥ше.  р≥м того, ћаркер використовуЇтьс¤ дл¤ марк≥руванн¤ ц≥лей, тобто крапки Ѕ.
   • ƒжерело хвил≥ - тут повинна м≥ститис¤ ≥нформац≥¤ про те, в≥дк≥л¤ хвил¤ потрапила в даний район. “обто тут збер≥гаютьс¤ координати чи напр¤мок до ≥ншоњ дискретноњ кл≥тинки ≥ номер району в н≥й. ÷¤ ≥нформац≥¤ знадобитьс¤ дл¤ вид≥ленн¤ з хвил≥ конкретного шл¤ху.
   • ¬арт≥сть Ц це поле може бути застосоване дл¤ де¤коњ оптим≥зац≥њ шл¤ху, але не Ї обов'¤зковим.
   • „ас створенн¤ Ц це поле в≥дноситьс¤ не до кожного району, а ц≥лком до дискретноњ кл≥тинки. ѕотр≥бно дл¤ того, щоб юн≥ти коректно сприймали ситуац≥ю, коли вм≥ст дискретноњ кл≥тинки зм≥нюЇтьс¤.

¬ажливо! «азвичай в стратег≥¤х бувають юн≥ти великих розм≥р≥в. Ќаприклад, танк майже гарантовано буде мати розм≥р 2х2. якщо у ваш≥й гр≥ Ї велик≥ юн≥ти, то вам доведетьс¤ зробити дискретн≥ кл≥тинки дв≥ч≥, адже буде зовс≥м неможливо використовувати райони юн≥т≥в 1х1 дл¤ юн≥т≥в 2х2. Ќа жаль, при визначенн≥ район≥в дл¤ 2х2 ≥снуЇ багато вс≥л¤ких др≥б'¤зк≥в, ¤к≥ спочатку непом≥тн≥. ѕрим≥ром, збоку дискретноњ кл≥тинки присутн¤ в≥льна л≥н≥¤ шириною в одну кл≥тинку (тобто танк 2х2 туди не пом≥ститьс¤). ќднак, ¤кщо частина танку буде знаходитис¤ на сус≥дн≥й кл≥тинц≥, то в≥н ц≥лком може своЇю другою частиною бути на ц≥й л≥н≥њ. ј зв≥дси висновок Ц ц¤ л≥н≥¤ ц≥лком нормальний район дл¤ об'Їкт≥в 2х2, хоча вони там ≥ не ум≥щаютьс¤. Ќа жаль, Ї ще де¤к≥ тонкощ≥, але ¤ просто не в змоз≥ зараз усе пригадати, тому що з моменту реал≥зац≥њ цього методу пройшло вже рок≥в з 3.

ѕ≥дготуйте дискретн≥ кл≥тинки перед запуском карти. ћожливо, вам знадобитьс¤ 2 види дискретних кл≥тинок через юн≥т≥в розм≥ром 2х2 або один вид дискретних кл≥тинок, але з двома видами район≥в усередин≥. ќсобисто ¤ використовував другий вар≥ант. ѕерш н≥ж робити райони типу 2х2 рекомендую вз¤ти пап≥р ≥ ол≥вець, ≥ зайн¤тис¤ б≥льш детальним вивченн¤м цього питанн¤, а, саме, моделюванн¤м р≥зних ситуац≥й. ƒр≥бн≥ помилки в побудов≥ район≥в виловити зовс≥м непросто, тому що в≥дпов≥сти на запитанн¤: Ђчому танк поњхав до ц≥л≥ в об'њзд?ї не завжди Ї можливим. „астково в ц≥й ситуац≥њ може допомогти функц≥¤, що буде записувати в зручному вид≥ вм≥ст дискретноњ кл≥тинки у BMP-файл. ÷е дозволить побачити очима зм≥ст проблемноњ дискретноњ кл≥тинки. ѕриклад запису BMP-файл≥в можна знайти в MSDN.

¬аш алгоритм маЇ обов'¤зково вм≥ти перебудовувати дискретн≥ кл≥тинки п≥д час гри. ÷е в≥дбуваЇтьс¤ в момент встановленн¤ чи знищенн¤ буд≥вл≥, а також, при повному видобутку одного з ресурс≥в.

¬ажливо! ¬и повинн≥ оновити не т≥льки т≥ дискретн≥ кл≥тинки, що безпосередньо були порушен≥ зм≥ною, але ще ≥ на певн≥й в≥дстан≥, ≥накше буде в≥дбуватис¤ псуванн¤ зв'¤зк≥в м≥ж районами. ” Ђ«емл≥ он≥мод≥вї ¤ зб≥льшую цю площу на 3 кл≥тинки з кожноњ сторони.

ўоб не перев≥р¤ти п≥д час гри координати кл≥тинок на вих≥д за меж≥ пол¤, дуже непогано б обнести поле невидимим Ђзаборомї, тобто реальне поле маЇ бути трохи ширшшим ≥ довшим (у моЇму випадку на 6*2=12), а весь периметр потр≥бно заповнити непрох≥дним бар'Їром. ÷е позбавить вас в≥д пост≥йних перев≥рок типу if (x>=0 && x<довжина_карти && y>=0 && y<висота_карти).

“епер ми маЇмо п≥дготовлен≥ заздалег≥дь дискретн≥ кл≥тинки. јле що ж робити дал≥? яким чином орган≥зувати хвильовий алгоритм на практиц≥?

як ¤ вже говорив, повний алгоритм побудови шл¤ху складаЇтьс¤ з 2-х частин:

1. ѕобудова шл¤ху з дискретних кл≥тинок за допомогою дискретноњ хвил≥.
2. ќб'Їднанн¤ шл¤ху з дискретних кл≥тинок за допомогою звичайноњ хвил≥.

ƒавайте спочатку розберемос¤ з де¤кими аспектами орган≥зац≥њ. ѕри опис≥ структури дискретноњ кл≥тинки ¤ додав де¤к≥ пол¤, що використовуютьс¤ т≥льки в момент побудови хвил≥. ƒавайте розберемос¤ з полем ћаркер.

 оли хвил¤ розповзаЇтьс¤ потр≥бно ¤кось позначати т≥ м≥сц¤, що вона вже встигла об≥йти. јле подумайте от над чимЕ якщо ви будете позначати Ђоб≥йден≥ / не об≥йден≥ї м≥сц¤ за принципом Ђ0 / 1ї, то тод≥ п≥сл¤ кожноњ побудови вам доведетьс¤ п≥дчищати вс≥ одиниц≥. “ому зробимо по-≥ншомуЕ ¬ведемо пон¤тт¤ ћаркер. ”¤в≥ть, що ми викликаЇмо дискретну хвилю в перший раз (ћаркер=0). “од≥ ми в≥дразу можемо позначити крапку Ѕ числом ћаркер+1 (1), а саму хвилю числом ћаркер (0).  оли ми будемо викликати дискретну хвилю вдруге, то перед цим виконаЇмо такий простий х≥д: ћаркер=ћаркер+2. “обто ми будемо позначати ≥ хвилю ≥ ц≥ль вже ≥ншими числами (3 ≥ 2), що дозволить уникнути чищенн¤ пол¤ в≥д д≥й попередньоњ хвил≥.  оли ћаркер вичерпаЇ м≥стк≥сть перем≥нноњ типу WORD, то зробимо повне очищенн¤ марк≥руванн¤ вс≥х дискретних кл≥тинок будь-¤ким числом б≥льшим за 1 ≥ запишемо в ћаркер 0.

¬ ќн≥модах хвил¤ орган≥зуЇтьс¤ за таким самим принципом, що ≥ найпрост≥ший спос≥б заливки, запропонований мною на початку статт≥. “обто п≥д одну хвилю створюютьс¤ 2 масиви, що перекидають координати один у одного. ™дина в≥дм≥нн≥сть, що довжина масив≥в не задаЇтьс¤ св≥домо великою, а в раз≥ потреби, зб≥льшуЇтьс¤ з визначеним кроком.

ѕочнемо з того, що перед черговим кроком потр≥бно завжди переконуватис¤ в двох речах:

1. „и Ї ще актуальною ц≥ль? “обто можливо ворог вже загинув чи ресурс добуто. ” цьому випадку поточна д≥¤ перериваЇтьс¤.
2. „и дос¤гнуто ц≥ль? ƒос¤гненн¤ ц≥л≥ визначаЇтьс¤ по в≥дстан≥ в≥д нашого юн≥та до ц≥л≥. «авжди повинна бути в≥дома в≥дстань, що Ї достатньою дл¤ дос¤гненн¤ ц≥л≥. ѕрим≥ром, ¤кщо юн≥т рухаЇтьс¤ до ресурсу, то в≥дстань буде 1, а ¤кщо хоче п≥дстрелити ворога, то в≥дстань дор≥внюЇ рад≥усу стр≥льби.

—початку треба визначити, чи потр≥бно п≥дходити до ц≥л≥ впритул або т≥льки на в≥дстань постр≥лу.

—першу перев≥р¤Їмо Ђможе ц≥ль вже дос¤гнуто?ї Ўвидше за все Ђн≥їЕ

“од≥ перев≥р¤Їмо, чи можна дос¤гти ц≥ль, тобто застосовуЇмо райони ≥грового пол¤, про ¤к≥ ¤ говорив на самому початку. якщо ц≥ль дос¤гти не можна, то просто шукаЇмо, починаючи в≥д ц≥л≥, найближчу крапку, ¤ку дос¤гти можна Ц вона тепер ≥ буде ц≥ллю.

як ц≥ль може рахуватис¤:

1. ѕорожнЇ м≥сце.
2. –ухливий юн≥т.
3. Ѕуд≥вл¤, ресурс чи ¤кий-небудь кам≥нець.
4. Ќедобудова, тобто насправд≥ буд≥вл≥ ще нема, але треба п≥двести до нењ прац≥вника дл¤ буд≥вництва.

¬ ус≥х цих випадках можна пустити назустр≥ч одна одн≥й одразу 2 хвил≥. “обто одна хвил¤ розходитьс¤ з поточного положенн¤ юн≥та, ≥нша з положенн¤ ц≥л≥, кожна перев≥р¤Ї на з≥ткненн¤ з ≥ншою хвилею через поле ћаркер. ѕри з≥ткненн≥ - шл¤х побудований ≥ залишаЇтьс¤ т≥льки вит¤гти його через пол¤ ƒжерело хвил≥.

ѕункти а) ≥ б) н≥чим не в≥др≥зн¤ютьс¤ з погл¤ду побудови дискретноњ хвил≥. “ут ц≥ллю Ї одна крапка, точн≥ше один район в одн≥й дискретн≥й кл≥тинц≥.

ѕункт в) ≥ г) теж схож≥, але тут ¤к ц≥ль вже рахуЇтьс¤ де¤ка область Ц рамка навколо ц≥л≥. як бути в цьому випадку? ƒуже просто Ц можна пустити другу хвилю в≥дразу з кожноњ кл≥тинки, що входить у рамку. “обто дл¤ кожноњ кл≥тинки, що входить у рамку, визначаЇмо дискретну кл≥тинку ≥ район, а пот≥м заносимо њх у масив хвил≥ 2 (т≥льки дублювати не потр≥бно). ’вил¤ буде розповзатис¤ зовс≥м так само.

ћожна ≥ не мудрувати з другою хвилею, а просто нанести рамку ¤к ц≥ль ≥ перев≥р¤ти одн≥Їю хвилею на дос¤гненн¤ ц≥Їњ ц≥л≥.

—першу перев≥р¤Їмо Ђможе ц≥ль вже дос¤гнуто?ї Ўвидше за все Ђн≥їЕ

“ут ¤ хочу роз≥брати найскладн≥шу ситуац≥ю, що може виникнути. « нењ, ¤ спод≥ваюс¤, стане багато чого зрозум≥ло, ≥ ви заздалег≥дь дов≥даЇтес¤ про де¤к≥ Ђграбл≥ї, ¤кими густо зас≥¤ний шл¤х розроблювача. —итуац≥ю ¤ постараюс¤ роз≥брати ц≥лком, тобто не т≥льки з позиц≥й алгоритму шл¤ху, а з позиц≥й гри в ц≥лому.

”¤в≥ть соб≥, що ваш≥ миротворч≥ сили переможним маршем направл¤ютьс¤ по вузьк≥й ущелин≥ в таб≥р супротивника. јле зл≥ недруги побудували по кра¤х ущелини к≥лька оборонних вишок, що знаход¤тьс¤ поза дос¤жн≥стю вашого загону, тобто д≥йти до вишок п≥шки неможливо. ѕроте вишки по-зрадницьк≥ в≥дкривають вогонь праворуч ≥ л≥воруч по ваших хоробрих воњнах, ¤к≥, вит¤гнувшись в шеренгу, упевнено крокують вперед.

ќтже такЕ ” вашого п≥хотинц¤ потрапив снар¤д в≥д вишки. ўо робити?

«вичайно, в ≥деал≥ треба в≥дпов≥сти на агрес≥ю ≥ б≥льш того, п≥хотинець, що зазнав нападу, повинний би Ђпокликати на допомогуї найближчих друз≥в. —аме це ми ≥ робимо, алеЕ —початку перев≥р¤Їмо, чи знаходитьс¤ вишка в зон≥ враженн¤ п≥хотинц¤? якщо Ђтакї, то в≥дкриваЇмо зустр≥чний вогонь. ј от ¤кщо Ђн≥ї? јдже вишка напевно стр≥л¤Ї дал≥, ан≥ж п≥хотинець. “од≥ треба спочатку п≥д≥йти до вишки на в≥дстань постр≥лу. јле отут потр≥бно перев≥рити, а чи можна до вишки п≥д≥йти? јдже вона в нас знаходитьс¤ там, куди не д≥статис¤, що легко можна визначити, пор≥вн¤вши райони п≥хотинц¤ ≥ вишки (визначенн¤м район≥в ми займалис¤ на самому початку статт≥). якщо д≥йти можна (це не наш випадок), то п≥хотинець спр¤мовуЇтьс¤ в атаку на вишку ≥ за ним б≥жать його друз≥ по боротьб≥. ” нашому випадку ми визначаЇмо, що д≥йти не можна. ўо ж робити? “а н≥чого. “реба б≥гти дал≥, тому що зупин¤тис¤ ≥ Ђюрбитис¤ п≥д вишкоюї зовс≥м нерозумно. јЋ≈! Ђ ликати на допомогуї наш п≥хотинець усе р≥вно може ≥ повинний, тобто в≥н записуЇ у свою перем≥нну ћ≥й убивц¤ покажчик на вишку. ƒал≥ п≥хотинець пер≥одично Ђкличе на допомогу в боротьб≥ проти вишкиї, дл¤ чого шукаЇ найближчих союзних воњн≥в ≥ пропонуЇ њм ¤к ц≥ль вишку. ўо повинен робити воњн, ¤кий одержуЇ такий заклик про допомогу? ƒл¤ початку перев≥рити, а чи не зайн¤тий в≥н вже в ¤к≥йсь перестр≥лц≥? якщо Ђтакї, то потр≥бно оц≥нити ефективн≥сть новоњ ц≥л≥ (вишки) у пор≥вн¤нн≥ з поточною ц≥ллю. Ќаприклад, ¤кщо наш танк займавс¤ розстр≥лом ворожих роб≥тник≥в, що проходили повз, то в≥н повинен зрозум≥ти, що знищенн¤ вишки ц≥ль б≥льш шл¤хетна. јле отут знову виникаЇ необх≥дн≥сть у додаткових перев≥рках. —итуац≥й дек≥лька:

1. “анк знаходитьс¤ в тому самому район≥, що ≥ вишка Ц треба просто атакувати вишку.
2. “анк знаходитьс¤ в тому самому район≥, що ≥ п≥хотинець, а вишка в ≥ншому Ц необх≥дно пор≥вн¤ти далекоб≥йн≥сть танка ≥ далекоб≥йн≥сть вишки, ≥ ¤кщо танк стр≥л¤Ї дал≥, то атакувати. якщо ж п≥хотинець сам атакуЇ вишку, то можна пор≥вн¤ти далекоб≥йн≥сть танка з далекоб≥йн≥стю п≥хотинц¤, тому що ¤кщо поц≥лив п≥хотинець, то ≥ танк зможе поц≥лити.
3. “анк знаходитьс¤ в ¤комусь своЇму район≥ Ц перев≥рити, чи не знаходитьс¤ вишка вже в зон≥ ураженн¤, ¤кщо Ђтакї, то атакувати.

јле ¤ким чином найкраще побудувати шл¤х до вишки, ¤ку насправд≥ дос¤гти не можна? Ќайпрост≥ший вар≥ант вигл¤даЇ так. Ќаносимо на дискретн≥ кл≥тинки ц≥ль у вид≥ окружност≥ навколо вишки (ћаркер+1). –ад≥ус окружност≥ дор≥внюватиме рад≥усу стр≥льби воњна. “епер будуЇмо одну дискретну хвилю в≥д воњна до ц≥Їњ самоњ окружност≥. якщо окружн≥сть Ї дос¤жною, то залишаЇтьс¤ т≥льки вит¤гти шл¤х через пол¤ ƒжерело хвил≥. якщо з ¤кихось причин ц≥ль не можна дос¤гти, то потр≥бно визначити найближчу дискретну кл≥тинку до ц≥л≥. ÷е легко зробити через поле ћаркер. Ќадал≥ ц¤ дискретна кл≥тинка ≥ рахуватиметьс¤ к≥нцевою дискретною кл≥тинкою шл¤ху, але шл¤х буде вважатис¤ недобудованим.

” результат≥ виклику дискретного хвильового алгоритму ви маЇте отримати шл¤х з дискретних кл≥тинок з номерами район≥в.  р≥м того, треба ще повернути ≥нформац≥ю про те, чи вдалос¤ побудувати шл¤х. як же змусити юн≥та д≥йсно почати реально рухатис¤? ќтже такЕ

ћи знаЇмо, що наш юн≥т повинен обов'¤зково потрапити в необх≥дний район черговоњ дискретноњ кл≥тинки. ј район цей ми можемо нанести вже в звичайних координатах ¤к ц≥ль дл¤ звичайноњ хвил≥, нав≥ть увесь район наносити не потр≥бно, досить лише т≥Їњ його частини, що розташована на периметр≥ дискретноњ кл≥тинки. —писок координат району на периметр≥ можна або приготувати заздалег≥дь (так роблю ¤), або одержувати перев≥ркою периметра вс≥Їњ дискретноњ кл≥тинки. ƒал≥ ми застосовуЇмо звичайн≥с≥нький хвильовий алгоритм, без жодних оптим≥зац≥й, але на дуже близьк≥й в≥дстан≥. ўе одна тонк≥сть Ц тепер кл≥тинки, що зайн¤т≥ ≥ншими юн≥тами, потр≥бно рахувати ¤к недоступн≥ ≥ обходити њх.

¬ п≥дсумку одержуЇмо коротенький сполучний шл¤х в≥д поточноњ крапки до черговоњ дискретноњ кл≥тинки.  рокуЇмо юн≥том цим шл¤хом ≥, д≥йшовши до к≥нц¤, знову будуЇмо з'Їднуючий шл¤х, але вже з наступною дискретною кл≥тинкою. “ут все чудово, кр≥м ситуац≥њ з останньою дискретною кл≥тинкою, тому що њњ вже не з чим зв'¤зувати. „ерез що тут треба будувати шл¤х пр¤мо до к≥нцевоњ ц≥л≥. якщо це крапкова ц≥ль, то проблем нема, а от ¤кщо це рамка чи окружн≥сть дл¤ постр≥лу, то доведетьс¤ њх наносити на кл≥тинки.

Ќа жаль, питанн¤ перем≥щенн¤ юн≥та з одн≥Їњ крапки до ≥ншоњ не обмежуЇтьс¤ лише побудовою шл¤ху м≥ж цими крапками.

1) Ўл¤х з дискретних кл≥тинок будуЇтьс¤ заздалег≥дь, тобто поки юн≥т рухаЇтьс¤ ним, ситуац≥¤ може сильно зм≥нитис¤, наприклад, на шл¤ху руху може бути побудований новий будинок. ƒл¤ в≥дловлюванн¤ таких зм≥н юн≥т, перед тим ¤к наступити на чергову дискретну кл≥тинку повинний визначати, а чи не оновилас¤ на н≥й ≥нформац≥¤. ƒл¤ цього кожна дискретна кл≥тинка повинна мати поле „ас створенн¤, у ¤кому збер≥гаЇтьс¤ час њњ оновленн¤ (побудови район≥в). ј кожен юн≥т повинний запам'¤товувати час, коли було побудовано дискретний шл¤х. якщо раптом ви¤вл¤Їтьс¤, що шл¤х було побудовано ран≥ше, н≥ж оновивс¤ вм≥ст дискретноњ кл≥тинки, то юн≥ту необх≥дно перешикувати весь шл¤х ц≥лком.

2)  оли юн≥т крокуЇ, то в≥н пост≥йно буде натикатис¤ на ≥нших юн≥т≥в. ƒл¤ початку треба визначити, чим зайн¤тий юн≥т, що заважаЇ. якщо в≥н рухаЇтьс¤ чи оч≥куЇ руху, то можна теж зачекати (через це у вс≥х стратег≥¤х юн≥ти шикуютьс¤ в ланцюжок). якщо чекати безглуздо (юн≥т стоњть на м≥сц≥ чи чекаЇ нашого юн≥та), то можна побудувати з'Їднуючий шл¤х ще раз.

3) ≤нод≥ щ≥льн≥сть юн≥т≥в Ї наст≥льки великою, що не виходить побудувати сполучний шл¤х до наступноњ дискретноњ кл≥тинки. ÷е найскладн≥ший момент у керуванн≥ маршрутом, адже в ц≥й товкотнеч≥ практично неможливо визначити: чи варто чогось оч≥кувати чи треба п≥ти ≥ншим шл¤хом? ўе г≥рше те, що наш юн≥т може запросто сам створювати затор. ≤нод≥ ситуац≥ю виходить пол≥пшити, ¤кщо Ђроз≥гнатиї юн≥т≥в у дов≥льних напр¤мках.

јби п≥ти ≥ншим шл¤хом можна заблокувати дл¤ дискретного хвильового алгоритму ту дискретну кл≥тинку, на ¤ку не виходить потрапити. ” ќн≥модах ¤ блокую до 3-х таких кл≥тинок п≥др¤д, п≥сл¤ чого будую весь шл¤х ≥з самого початку. ƒл¤ блокуванн¤ дискретноњ кл≥тинки досить вказати в н≥й, що хвил¤ њњ уже в≥дв≥дувала, тод≥ хвил¤ туди вдруге не п≥де (¤кщо, звичайно, ви не використовуЇте варт≥сть).

4) якщо ц≥ллю Ї ≥нший юн≥т, то в≥н може пост≥йно перем≥щатис¤. “обто вам доведетьс¤ пост≥йно ц≥лком перебудовувати весь шл¤х. як же визначити момент, коли потр≥бно це зробити? я роблю так: визначаю напр¤мок до ц≥льового юн≥та (тобто праворуч, л≥воруч, л≥воруч ≥ нагору, Е) ≥ ¤кщо в≥н зм≥нюЇтьс¤, то перебудовую маршрут ц≥лком. “аким чином, ¤кщо ц≥льовий юн≥т знаходитьс¤ далеко, то й напр¤мок буде м≥н¤тис¤ р≥дко, а ¤кщо близько, то шл¤х буде будуватис¤ швидко.

5) Ѕажано вести л≥к такт≥в, прот¤гом ¤ких, юн≥т не зм≥г зрушити з м≥сц¤. якщо цей л≥чильник перевищуватиме певне число, то це буде сигналом до вжитт¤ екстрених заход≥в, таких ¤к побудова обх≥дного шл¤ху, перем≥щенн¤ у випадковому напр¤мку чи перериванн¤ виконанн¤ команди.

6) Ќайголовн≥ше Ц використовуйте пер≥одичн≥сть. Ќаприклад, ¤кщо юн≥т чекаЇ, коли йому зв≥льн¤ть дорогу, то зовс≥м не обов'¤зково зд≥йснювати цю перев≥рку пост≥йно. ÷е можна робити пер≥одично, а це упов≥льненн¤ реакц≥њ на третину секунди гравець нав≥ть не пом≥тить. ѕерев≥рки за пер≥одом у вс≥й гр≥ Ц це саме те, що дозвол¤Ї проводити масу обт¤жливих за часом перев≥рок ≥ при цьому зберегти високу швидк≥сть.

“ут ¤ в≥докремив лише де¤к≥ очевидн≥ проблеми керуванн¤ алгоритмом шл¤ху. Ќасправд≥, питань там, набагато б≥льше, н≥ж у мене в≥дпов≥дей. ѕо складност≥ процес гарного керуванн¤ складн≥ше, чим сам алгоритм пошуку шл¤ху. ¬ам доведетьс¤ довго Ђгратис¤ї з р≥зними настроюванн¤ми, аби знайти ¤кусь середину м≥ж крайност¤ми. √оловне Ц це спробувати уникнути частого неефективного перебудуванн¤ всього шл¤ху.

Ќаприк≥нц≥ статт≥ ¤ вир≥шив к≥лька сл≥в сказати про ефективн≥сть даного комплексу р≥шень. Ќа жаль, оц≥нити швидкод≥ю точними цифрами ¤ не можу. ћожу лише висловити свою особисту точку зору. як тестовий стенд знову ж використовую свою гру Ђ«емл¤ он≥мод≥вї. „ерез те що гру, напевне, бачили далеко не вс≥, то скажу про нењ дек≥лька сл≥в.

≤зометрична 2D стратег≥¤ в реальному час≥. ћен≥ особисто гра представл¤Їтьс¤ сум≥шшю Starcraft ≥ Age of Empires. ћаксимальний розм≥р ≥грового пол¤ 504х504.

ќсновн≥ пункти витрат швидкод≥њ процесора, кр≥м обслуговуванн¤ вс≥х на¤вних юн≥т≥в:

1. ¬иведенн¤ 2D-граф≥ки на екран.
2. ѕошук кожним воњном можливоњ ц≥л≥ в межах видимост≥.
3. «аклик про допомогу.  ожен ≥гровий об'Їкт часто просить допомоги в ≥нших об'Їкт≥в. Ќаприклад, ¤кщо ¤кийсь юн≥т воюЇ, то в≥н Ђкличе на допомогу своњх товариш≥вї у межах видимост≥, ¤к п≥дсумок, воњни починають п≥дт¤гуватис¤ до м≥сц¤ бою.

√альмуючим Ї пункт 3, тому що зверненн¤ тут йде не т≥льки до своЇњ команди, але ≥ до команд союзник≥в, прим≥ром, союзний роб≥тник може полагодити ушкоджений будинок.

¬се решта, на мою думку, не дуже навантажуЇ процесор. ≤нтелект викликаЇтьс¤ дл¤ кожноњ команди приблизно раз у секунду ≥ найпов≥льн≥ша його операц≥¤ Ц пошук м≥сц¤ на карт≥ дл¤ нового сховища, що в≥дбуваЇтьс¤ лише за необх≥дн≥стю.

” процес≥ налагодженн¤ своЇњ гри ¤ використовував наступний прийом. Ќа карт≥ розм≥ром 504х504 створював 8 команд ≥ под≥л¤в њх на 2 союзи (б≥й 4 на 4). ўоб самому не напружуватис¤ включав зам≥сть себе комп'ютерний ≥нтелект, тобто живий гравець у гр≥ участ≥ не приймав. «азвичай така батал≥¤ триваЇ 40-50 хвилин. Ѕлижче до завершенн¤ л≥чильники показують приблизно 500-700 Ђживихї юн≥т≥в ≥ 200-250 будинк≥в. ѕриблизно 10-15% юн≥т≥в Ї л≥таючими, тобто алгоритм пошуку шл¤ху не використовують. ” цьому стан≥ на процесор≥ Celeron 1000 (роз≥гнаний 667) грати стаЇ дуже некомфортно, але ц≥лком можна. якщо под≥лити команди не на 2 союзи, а зробити Ђкожен сам за себеї, то загальмуванн¤ пом≥тно знизитьс¤. ѕрискоренн¤ в≥дбуваЇтьс¤ за рахунок пункту 3.

Ќа сучасних процесорах типу Pentium-4 1700 ¤когось серйозного зниженн¤ швидкост≥ не в≥дчуваЇтьс¤.

ћожна спробувати оц≥нити алгоритм ще таким способом. ¬ид≥л¤Їмо мишкою 250 юн≥т≥в ≥ направл¤Їмо њх одночасно у найдальший кут ≥грового пол¤. ” цю мить побудова дискретноњ хвил≥ в≥дбудетьс¤ в≥дразу 250 раз≥в. ѕауза на Celeron-1000 забере приблизно п≥всекунди-секунду, дал≥ вс≥ юн≥ти спок≥йно в≥дправл¤тьс¤ до зазначеного м≥сц¤ вже без ¤ких-небудь загальмувань.