===== AI ved BehaviorTree =====

Et behavior tree (BT) er, som navnet antyder, en træstruktur der er opbygget af knuder og blade. 
Knuderne (Nodes) beskriver det logiske flow i træet, og blade (Leaves) beskriver konkrete handlinger (Tasks).

Træets struktur er hierarkisk, hvilket betyder at hver node kan have en eller flere underordnede noder, kaldet *children* (child nodes). En node der ligger over andre noder kaldes en *parent node*.

Parent-node styrer evalueringen af sine child-nodes, og bestemmer, hvornår og hvordan de udføres.

Træet og dets del-trær er et hieraki af handlinger af forskellige abstraktons niveauer e.g. En opgave som fx. "Tag på arbejde" kan bestå af (Tag jakke på, find bilnøgle, kør mod arbejde)

Her vil ''Tag på arbejde'' være en parent node, og de tre underliggende handlinger vil være dens children.

  * For knuderne i træet vil vi fremover anvende det engelske ord __nodes__ (flertal) , __node__ (ental).
  * For bladene på træet vil vi fremover anvende det engelske ord __leaves__ (flertal), __leaf__(ental).

----

  * **Nodes**
    * Composites nodes ( nodes 2 eller flere child-nodes )
      * Selector (OR)
      * Sequence (AND)
    * Decorator (single child)

  * **Leaves**
    * Tasks
      * Condition/Check (if)
      * Action (handling/adfærd)

----





==== Hvornår skiftes tilstand? ====

Der er tre fundamentale grunde til at skifte fra en tilstand til en anden.

  * **SUCCESS** -> Task lykkedes. Sequence går videre til næste child.
  * **FAILURE** -> Task fejlede. Selector vil prøve næste child.
  * **RUNNING** -> Task er stadig i gang.

Uddybet

=== SUCCESS ===
  * Task blev udført korrekt.
  * I en **Sequence** betyder det, at den går videre til næste child.
  * Hvis alle children returnerer SUCCESS, returnerer hele Sequence SUCCESS.

=== FAILURE ===
  * Task kunne ikke udføres.
  * I en **Sequence** stopper den og returnerer FAILURE.
  * I en **Selector (Fallback)** prøver den næste child.

=== RUNNING ===
  * Task er stadig i gang.
  * Kan endnu ikke afgøre SUCCESS eller FAILURE.
  * Parent returnerer også RUNNING.

----


==== Virkemåde ====

  * Selector(markeret med '?') ( OR operation ) 
    * En selector er tilfreds med at kunne udføre én af sine tasks  (prøver __fra venstre__, og stopper når der kommer en success)
  * Sekvens (markeres med '->') (AND operation)
    * En sekvens node er "ambitiøs" og vil forsøge at udføre alle sine tasks __fra venstre__, og afbryder først hvis en task giver en failure.
    * En sekvens node er kun en success når __alle__, child nodes er en succes.

----

===== Evaluering af Behavior Tree (Ticks) =====

Et Behavior Tree bliver evalueret ved hjælp af *ticks*.

Et tick er et opdateringssignal, der fortæller træet:
  "Vurder hvad der skal ske nu."

I praksis kaldes root node typisk én gang pr. frame eller pr. AI-update.
Når root modtager et tick, sendes det videre ned gennem træet.

----

==== Hvordan bevæger et tick sig gennem træet? ====

  * Tick starter altid ved root.
  * Parent-noden sender tick videre til sine children.
  * Hver node returnerer én af tre statusser:
    * SUCCESS
    * FAILURE
    * RUNNING
  * Status sendes tilbage til parent-noden.

Tick fortsætter kun ned gennem de nodes, som logikken tillader.

Eksempel:
  * I en Sequence stopper evalueringen ved første FAILURE.
  * I en Selector stopper evalueringen ved første SUCCESS.
  * Hvis en node returnerer RUNNING, stopper tick her indtil næste update.

Det betyder, at et tick ikke nødvendigvis gennemløber hele træet — 
kun den del der er relevant i den aktuelle situation.


----


==== Video tutorials ====

  * [[https://www.youtube.com/watch?v=KeShMInMjro|Behavior Trees in 5 minutes]]
  * [[https://www.youtube.com/watch?v=DCZJUvTQV5Q|Introduction to behavior tress 17min]]