En af mine store interesseområder indenfor spiludvikling er kunstig intelligens (AI). Der findes mange teknikker og modeller til at designe et spils AI, men det vigtigste er at man bruger en model som er skalerbar og er nem at editere og designe gennem et udviklingsforløb.
Behaviour Trees er en forholdsvis ”ny” model brugt indenfor kunstig intelligens, men er blevet yderst populær i spilproduktioner hvor bl.a. spil som Halo serien har benyttet sig af den.
Modellen er lavet for at gøre det nemmere for AI designeren og programmørerne at arbejde sammen, ved at give et nemt og overskueligt abstraktionslag over spillets AI. Behaviour Trees benytter sig af en overskuelig grafik repræsentation over agenternes opførsel, vha. en træstruktur med et simpelt sæt af knuder tilgængelig.
Designeren kender spillet og de overordnede mål og egenskaber for agenterne, og det er derfor muligt for ham at sætte det overordnede design. Programmørens opgave er at kode den rent faktiske implementering af agenternes opførsel.
Træet har en rod knude som altid er udgangspunkt for en agent, og designeren har mulighed for at tilføje en række undertræer til den knude. Hvert undertræ kan ses som en mulig opførsel for en agent, og fordi ingen af knuderne i træet har afhængigheder imellem sig kan undertræer/opførsler genbruges.
Et sådan træ er konstrueret og tilknyttet for hver AI type i spillet og traverseres konstant, så længe træet er den ønskede opførsel for agenten – en agent kan have flere træer. Rod knuden er altid start punkt og træet traverseres igennem knuderne til den har fundet vej til en action knude (som altid er blad knude). Når den fundne action er udført så traverseres træet igen.
Der er fire knuder som er tilgængelige for designeren: decorators, sequences, selectors og actions.
Actions
Action knuderne er bladene for træet, og de indeholder den rent faktisk implementering af agentens opførsel. En action kunne være at gå fra et punkt til et andet i verdenen. En action bør når det er muligt kodes generelt, så en designer kan genbruge actions til flere opførsler. Når en action er udført traverseres træet forfra.
Selectors
Denne knude kan have et eller flere børn, og indeholder den rent faktiske beslutningstagning for et Behaviour Tree. Målet for en selector knuden er at vælge en af sine børn som skal eksekveres. Det er muligt at skrive sin helt egen algoritme for dette, men en af de mest brugte og simple er sandsynlighed. Her vægter designeren børnene, og selectoren vælger en af dem tilfældigt baseret på vægtningen.
Sequence
Denne knude kan også have et eller flere børn, og bliver brugt når et sæt knuder har afhængig af hinanden. Sequence knuden vil først vælge sit første barn, og hvis dens action knude har udført sin action succesfuldt, så vil sequence knuden tage det næste barn i rækken. Et eksempel kunne være en agent der skal tage fjendens flag. Den opførsel kan deles op i actions hvor agenten først først skal; finde flaget, gå hen til det og til sidst samle det op.
Decorators
Den sidste knude kan indsættes imellem knuder for at tilføje funktionalitet til en generel action, eller den kan fungere som et filter. Det kan f.eks. bruges til at tjekke om fjendens flag allerede er taget før agenten forsøger at finde det.
Jeg vil som i mit forrige blog indlæg klart anbefale at man udvikler et værktøj til netop sådan en model. Vi har udviklet et værktøj til Unity motoren som gør det muligt at tegne og designe Behaviour Trees.
Her er et eksempel på et træ fra et projekt vi er ved at afslutte ved Unity Studios.
Dette træ indeholder en passagers opførslen på et skib, når han er i normal tilstand – vi skifter til et andet træ når der startes alarm på skibet.
I træet har vi fire overordnede opførsler: gå til kahyt, toilet besøg, idle og gå tilfældigt rundt. Det hele styres af en selector hvor vi har vægtet sandsynligheden for de forskellige opførsler. Hver overordnede opførsel indeholde flere actions som styres af en sequence knude. Vi benytter os også af en decorator som tjekker for at passageren har en kahyt og kan huske hvor den er, før vi forsøger at finde den i verdenen og gå hen til den.
Der er selvfølgelig meget mere at fortælle om Behaviour Trees, alt for meget til et blog indlæg, så skriv endelig i kommentar feltet hvis i har spørgsmål.
Jeg er ked af at tage pedantikerens (EDIT: som så vist hedder pedantens :)) rolle, men kan vi ikke blive enige om at det engelske ord node i denne sammenhæng (grafteori) bør oversættes til knude?
Tak for rettelsen og helt korrekt. Efter at have brugt de engelske termer kan det være vanskeligt at huske de danske :-)
Kan vi ikke blive enige om at denne type emner har et sprog der er meget forskelligt fra det normale danske, og at det engelske låne-ord "node" bedre beskriver hvad der er tale om end det danske "knude" der enten leder tankerne hen på spejdere eller sygdom?
Kan vi ikke blive enige om at denne type emner har et sprog der er meget forskelligt fra det normale danske, og at det engelske låne-ord "node" bedre beskriver hvad der er tale om end det danske "knude" der enten leder tankerne hen på spejdere eller sygdom?
Én ting er jo lægmands fortolkning, en helt anden er etableret fagterminologi, se f.eks. Den Store Danske EDIT: Det er eftersigende en god idé at gennemse sine referencer før man benytter dem, kan se Den Store Danske ikke er enig i mine definitioner, så lad mig i stedet henvise til denne introduktion til grafteori
Right ... så når definitionen ikke lige passer ind i dit kram kan du bare vælge en anden og så fremhæve den som autoritet?
Det være hvad det er: artiklen blev skrevet så den gav mening for forfatteren. Jeg forstod uden videre hvad der mentes. Du har tilsyneladende også forstået det. Var det ikke en ide at forholde dig til indholdet i stedet? Det ville i det mindste bidrage med noget værdi.
Jeg giver Peter ret; vi skal måske udvidde konceptet om grammar-nazis (grammatiknazister på dansk, så alle kan følge med) til pedant-trolls (pedanttrolle på dansk). Ja, jeg er sikker på at de danske oversættelser giver meget mere mening i et felt gennemsyret af engelsk terminologi...
Palles kommentar har måske en berettigelse hvis der var tale om en dansk publikation.
Right ... så når definitionen ikke lige passer ind i dit kram kan du bare vælge en anden og så fremhæve den som autoritet?
Den artikel i "Den Store Danske" Palle refererer til benytter heller ikke engelske fagudtryk, men derimod ordene "punkter" og "kanter" - en sprogbrug jeg godt kan forestille mig skyldes at artiklen har været en tur gennem encyklopædiens helt egen begrebstrolltjeneste (for nu at følge Marks sprogbrug).
Knuder og kanter er de almindeligt brugte danske begreber i grafteori. Muligvis benytter Bjarne Toft (der skrev artiklen på DSD) punkter for knuder, muligvis er der tale om en redaktionel tilretning, muligvis simpelthen et forsøg på at udelade fagudtryk i en tekst rettet til den almene læser.
Det er der ikke noget galt i: det er en fornuftig måde at formidle et (for nogen) kompliceret stof.
Hvis man ikke kan undgå fagudtryk skal man have en særdeles god grund til at vælge udenlandske versioner, når der (som her) findes en veletableret dansk sprogtradition inden for området. Og den særdeles gode grund findes ikke her. Peters argument:
det engelske låne-ord "node" bedre beskriver hvad der er tale om end det danske "knude" der enten leder tankerne hen på spejdere eller sygdom?
holder kun for mennesker der er så tonedøve at ordet "node" er tømt for musikalsk indhold. For alle os andre er "node" ikke nødvendigvis mere entydigt end det danske "knude". Entydigheden kommer fra sammenhængen - og i tilfælde som her, hvor Anders skriver om grafteori, så er der ikke tvivl om hvordan ordet "knude" skal forstås.
Danmark er et lille sprogområde, men ikke så lille at vi ikke kan have en levende sproglig tradition inden for mange faglige områder.
Det er en fin introduktion til behaviour trees. Er det et værktøj, som bliver tilgængeligt i Unity App store?
Jeg har et spørgsmål: Hvor udbredt er det at benytte agentens tidligere erfaring i spilscenen i den aktuelle spilscene, når vi snakker behaviour trees? Jeg tænker på, om man har eksempler på, at agenterne "trænes" på forhånd, så de kan vælge handling i den aktuelle situation ikke kun ud fra behaviour tree, men også med henblik på situationen set i forhold til tidligere erfaringer?
Jeg synes at jeres diskussion om fagtermer afsporer blogindlæggets opfordring til at snakke om datastrukturer. "Knude" er helt normalt hvis du diskuterer grafer med matematikere eller dataloger, og det er ikke spor elitært eller gammeldags at bruge danske ord -- det er derimod praktisk, så man ikke skal omstille sin tunge mindst en gang per sætning til at udtale et engelsk ord.
Behaviour Trees: De virker rigtigt smarte fordi simple adfærdsmønstre kan være relativt uafhængige af hinanden og højest opdaterer enkelte variable. Når et adfærdstræ traverseres igen og igen, er det ækvivalent til en tilstandsmaskine med cykliske ruter. Men selv hvis de blev oversat til cykliske grafer, giver det stadig god mening at definere dem som træer.
Har du nogen andre eksempler på sjove adfærde? Billedet viser, så vidt jeg tolker, en statist på en færge. Hvad hvis man forhindrer ham i at gå på toilettet ved at stå i vejen?
