GOAP: A Basic AI Tutorial

Game development specific discussions.
leopardpm
Posts: 1795
Joined: Feb 28, 2009 20:58

GOAP: A Basic AI Tutorial

Postby leopardpm » Dec 28, 2018 4:33

I have been exploring AI used for gaming (specifically, individual Agent AI) and thought that my discoveries might be of help to others desiring to learn about AI for their game. I will be focusing on one algorithm called GOAP (Goal Oriented Action Planning). GOAP is not a complete AI system and requires additional routines to make it functional, the only thing that a GOAP routine is: Given a Desired Goal State and a list of Actions which affect various World States, figure out a sequence of Actions which would achieve the Desired Goal. This result, the 'sequence of Actions' is called a Plan.

Definitions:
Goal State / World States: These are variables which describe the world (or agent) in some manner.
ex: the World State "IsItRaining" would be equal to '1' if it is raining in the world, or '0' if it is not.

Action: This is a set of data which describes both the Pre-Conditions and the Effects which an agent may do.
ex: the Action "Pick Up Axe" would probably require the Agent to be physically next to an axe (Pre-condition) and the effects of 'doing' this Action might be: "Remove Axe from World" and also "Add Axe to Agent Inventory"

Pre-Conditions: These are basically world states which need to be TRUE in order for this particular Action to be performed.

Effects: These are basically world states which are altered in some manner when this Action is performed.

Plan: a sequence of Actions which, when performed, will result in a Desired Goal state to be achieved.
ex: This series of Actions: (MoveToAxe, PickUpAxe, MoveToTree, ChopDownTree, PickUpFirewood, MoveToFirePit, PutDownFireWood, MoveToMatches, PickUpMatches, MoveToFirePit, LightFirewood) results in the Desired Goal State of "Campfire" = 1

How the GOAP routine figures out a plan is rather simple. Each action has a set of preconditions and effects. So, starting 'backwards' with the Goal World state, the routine finds all Actions which directly bring the desired change to the Goal World State through their respective Effects. For each of these Actions, it gets their Pre-Conditions and sets these each as NEW 'Desired World States', then loops again until there are no more Goal World States to fulfill.

I realize it is both confusing, yet seems to make sense, at this point mostly because we are talking in abstract terms which need to be codified to really understand. So here's some starting code:

SimpleGOAP Tut v01.bas

Code: Select all


data 12  ' Number of Actions
'     ACTION               Time Effort  NumOf   ReqWS  ReqWS  ReqWS    NumOf   EffWS  EffWS  EffWS   Location
'     NAME                 Cost  Cost   ReqWS    (1)    (2)    (3)     EffWS    (1)    (2)    (3)    Req Type
data 1,"Get Axe",              1,    1,     0,     0,0,   0,0,   0,0,      1,     1,1,   0,0,   0,0,  "Axe",1
data 2,"Chop Tree",            7,   10,     1,     1,1,   0,0,   0,0,      1,     2,1,   0,0,   0,0,  "Tree",2
data 3,"Get Matches",          1,    1,     0,     0,0,   0,0,   0,0,      1,     3,1,   0,0,   0,0,  "Matches",3
data 4,"Make Campfire",        3,    2,     2,     2,1,   3,1,   0,0,      1,     4,1,   0,0,   0,0,  "Firepit",4
data 5,"Make Magic Campfire",  2,    1,     1,     6,1,   0,0,   0,0,      1,     4,1,   0,0,   0,0,  "Firepit",4
data 6,"Get Saw",              1,    1,     0,     0,0,   0,0,   0,0,      1,     5,1,   0,0,   0,0,  "Saw",5
data 7,"Saw Tree",             5,    9,     1,     5,1,   0,0,   0,0,      1,     2,1,   0,0,   0,0,  "Tree",2
data 8,"Get Magic Wand",       1,    1,     0,     0,0,   0,0,   0,0,      1,     6,1,   0,0,   0,0,  "Wand",6
data 9,"Collect Branches",     2,    2,     0,     0,0,   0,0,   0,0,      1,     2,1,   0,0,   0,0,  "Tree",2
data 10,"Get Pick",            1,    1,     0,     0,0,   0,0,   0,0,      1,     8,1,   0,0,   0,0,  "Pick",7
data 11,"Mine Ore",            8,   10,     1,     8,1,   0,0,   0,0,      1,     9,1,   0,0,   0,0,  "IronVein",8
data 12,"Refine Ore",          4,    3,     2,     4,1,   9,1,   0,0,      1,    10,1,   0,0,   0,0,  "Firepit",4


type wsp
    as ushort ws_pntr
    as ushort val
end type

type act
    as ushort index
    as string name
    as ushort TimeCost
    as ushort EffortCost
    as ushort NumOfReqWS
    as wsp ReqWS(3)
    as ushort NumOfEffWS
    as wsp EffWS(3)
    as string LocReqName
    as ushort LocReqPntr
end type

dim as act Actions(20)
dim as ushort NumOfActions

' Load Actions Array
    read NumOfActions
    print using " Actions (&):";NumOfActions
    print " ACTION NAME             #ReqWS  ReqWS(1)  ReqWS(2)  ReqWS(3)    #EffWS   Eff(1)    Eff(2)    Eff(3)"
    print " -------------           ------  -------   -------   -------     ------   ------    ------    ------"
    for tmp as integer = 1 to NumOfActions
        read Actions(tmp).index
        read Actions(tmp).name
        read Actions(tmp).TimeCost
        read Actions(tmp).EffortCost
        read Actions(tmp).NumOfReqWS
        print using " (##) \                  \  ##   ";tmp;Actions(tmp).name;Actions(tmp).NumOfReqWS;
        for tmp1 as integer = 1 to 3
            read Actions(tmp).ReqWS(tmp1).ws_pntr
            read Actions(tmp).ReqWS(tmp1).val
            if Actions(tmp).ReqWS(tmp1).ws_pntr = 0 then
                print "   -     ";
            else
                print using "(##)=##  ";Actions(tmp).ReqWS(tmp1).ws_pntr;Actions(tmp).ReqWS(tmp1).val;
            end if
        next tmp1
   
        read Actions(tmp).NumOfEffWS
        print using "       ##     ";Actions(tmp).NumOfEffWS;
        for tmp2 as integer = 1 to 3
            read Actions(tmp).EffWS(tmp2).ws_pntr
            read Actions(tmp).EffWS(tmp2).val
            if Actions(tmp).EffWS(tmp2).ws_pntr = 0 then
                print "   -     ";
            else
                print using "(##)=##  ";Actions(tmp).EffWS(tmp2).ws_pntr;Actions(tmp).EffWS(tmp2).val;
            end if
        next tmp2
        read Actions(tmp).LocReqName
        read Actions(tmp).LocReqPntr
    print
    next tmp

data 10  ' Number of Different WorldStates(WS)
data 1,"hasAxe",      0 ' WS=1
data 2,"hasWood",     0 ' WS=2
data 3,"hasMatches",  0 ' WS=3
data 4,"hasCampfire", 0 ' WS=4
data 5,"hasSaw",      0 ' WS=5
data 6,"hasMagicWand",0 ' WS=6
data 7,"canUseMagic" ,0 ' WS=7
data 8,"hasPick",     0 ' WS=8
data 9,"hasOre",      0 ' WS=9
data 10,"hasIronBar", 0 ' WS=10

type wstype
    as ushort index
    as string name
    as ushort val
end type

dim shared as wstype WSA(20)
dim shared as integer NumOfWS

' Load WorldState array
    read NumOfWS
    print
    print using " WorldStates (&):";NumOfWS
    print " WS   STATE          DEFAULT"
    print " --  -------------   -------"
    for ws as integer = 1 to NumOfWS
        read WSA(ws).index,WSA(ws).name, WSA(ws).val 'default values...
        print using " (&) \              \   &";ws;WSA(ws).name; WSA(ws).val
    next ws
    print


sleep
end

This is a bit more extensive then we have covered so far, but not impossible to figure out. The World States are pretty straightforward. The Actions have some extra stuff in there that will be addressed later.
Time = how much 'game time' does this Action take
Effort = how hard is this action to perform
NumOfReqWS = Number of Required World States (pre-conditions)
ReqWS(1-3) = the required World State # and its value
NumOfEffWS = Number of Effected World States
EffWS(1-3) = the affected World State # and the effect (value)
Location vars = just ignore for now, not used in this version

First, lets completely forget about movement between actions. We will just focus on how the Actions get linked together first.

Assuming that the Desired Goal World State was to "hasCampFire"=1 (this is World State #4). The GOAP routine would initialize with that World State, and look for all the Actions which have the desired effect.... namely, there are two possible Actions which make "hasCampFire" = 1 - Action #4 ("Make Campfire") and Action #5 (Make Magic Campfire). The routine will then put the Required World States for each of those Actions in its Desired Goal State and then look for Actions which fulfill THOSE states.
The way it keeps track of the sequence of Actions and all the various possible plans is by dynamically building a tree structure with each node being an Action and linking to previous (parent) action, and then to subsequent (child) actions.

as I mentioned before, GOAP is not a complete AI system, but rather one part of it. For it to work, it requires another routine to figure out what Goal is desired (should I make a campfire or go eat some berries?), and another routine to analyze and compare possible Plans to pick which one to choose... and then another routine to actually execute the Plan in the game environment (showing proper animations, move Agent around world, etc). What GOAP does for us, as programmers, is to make it VERY easy to add actions for Agents to use in order to effect the game World. With the above simple code, one could easily make up 100's of possible actions and the routine would use them in order to achieve whatever Goal State was desired. Notice in this following code, the planner finds 9 total Plans which ALL achieve the final Goal State of 'hasCampFire' = 1. These 9 Plans are mostly different sequences of the same actions: Do I get the matches before getting the axe or chopping the tree? who knows, but ALL these plans are 'valid' in that they will each achieve the Goal.

[The code originally here can now be found in the Google Drive Link below: SimpleGOAP V006.bas]

also, please beware! This routine does not check for infinite loops which you can easily accidentally create by the way you define the actions effects & pre-conditions. For instance, an action of "Make Axe" requiring wood and perhaps an Axe head, and another action "Chop tree" which requires an Axe and produces wood..... the routine will go round n round forever trying to make an Axe to chop wood to make an axe.....

The Goal initially was to make a campfire, but to see what happens when the Goal is to do something with the campfire, like smelt some freshly mined ore into metal bars....

In line 229, change the desired Goal State to '10' instead of '4':
from this:

Code: Select all

    GoalNode.EndWS(4) = 1
to this:

Code: Select all

    GoalNode.EndWS(10) = 1
and see the explosion of possible plans....

I realize that this tutorial is not very good at explaining my code, and I probably glossed over many things that need explanation. PLEASE feel free to ask ANY questions, it helps me to understand better when I am trying to explain it to someone else....

ALSO NOTE: this code is just for testing, it has NOT been optimized in any way... I would assume the final form would utilize pointers for the entire Tree Structure, and I'm sure the other data structures are not optimal either. At some point, I will rewrite the code (with help from some great Pointer guru probably) because the speed of this routine will be keenly necessary when having large amounts of AI Agents....

********************************************************************************************************************
********************************************************NOTICE **************************************************
********************************************************************************************************************
Decided I would be smarter as to how to provide access for anyone would wants all the updated files... hence trying Google Drive

Here is the link to the project:
https://drive.google.com/drive/folders/1MW0dMC2jL_Q0-y7qpOy8R1YTeH01QWrW?usp=sharing

I will now just sync up and all files should be up-to-date including any new files needed.

In the folder are also the required fbsound library files which should work as long as they are in the same folder as the program - please let me know if you get errors or no sounds... the program also uses FBimage to load PNG graphics
********************************************************************************************************************
Last edited by leopardpm on Jan 04, 2019 8:30, edited 6 times in total.
leopardpm
Posts: 1795
Joined: Feb 28, 2009 20:58

Re: GOAP: A Basic AI Tutorial

Postby leopardpm » Dec 28, 2018 4:35

Hopefully in the next couple of days I will be posting up the next version where the routine is linked up with a graphical (basic) world and you can see the GOAP in action. Stay tuned!

NOTE: Even in this 'basic' form, the GOAP routine can be a very helpful and powerful tool in a Game Programmers toolkit when dealing with AI. There are various methods for implementing a detailed AI: FSM, HFSM, Scripting, etc. GOAP still needs those other pieces (mostly to determine which Goal to Plan for...). One way to think about GOAP is that it dynamically creates a script(Plan) for an Agent to perform, GOAP writes scripts! By enhancing GOAPs abilities (for instance, not just being able to compare boolean values but actual values with '<', '>','=', '<>', etc.) and increasing the amount of factors which might influence GOAP (an Agent without a 'Logging' skill cannot chop down trees), then it becomes very easy, using a SINGLE GOAP routine, to define multitudes of unique behaviors and different Agents (an Agent who is afraid of heights might not walk too close to the edge of a cliff to get to her destination, whereas an Agent who is a 'Risk Taker' might decide to venture into the unknown forest depths to hunt down rabbits....). It is my belief that it is possible to create realistic behaving Agents with minimal use of the CPU each game loop. we shall see...
Last edited by leopardpm on Dec 28, 2018 4:59, edited 1 time in total.
Boromir
Posts: 451
Joined: Apr 30, 2015 19:28
Location: Texas,U.S., Earth,Solar System
Contact:

Re: GOAP: A Basic AI Tutorial

Postby Boromir » Dec 28, 2018 4:57

I'm bookmarking this!
It'd be nice to make a gamedev resource compilation with useful stuff like this so it doesn't get buried.
I'd play with it and ask questions if I had more time but I'm busy with my entry for Lachie's competition.
leopardpm
Posts: 1795
Joined: Feb 28, 2009 20:58

Re: GOAP: A Basic AI Tutorial

Postby leopardpm » Dec 28, 2018 5:01

Boromir wrote:I'm bookmarking this!
It'd be nice to make a gamedev resource compilation with useful stuff like this so it doesn't get buried.
I'd play with it and ask questions if I had more time but I'm busy with my entry for Lachie's competition.
Actually, I am posting this BECAUSE of Lachie's competition - figured some folks might want an alternate method of doing their AI.

and, yes, in respect to what I have seen of the type of game you had been focusing on before (kinda RPG/RTS), GOAP would fit nicely into it. In the following posts, I will show how to make Agents with differing 'behaviors' (Wood Choppers, Miners, Farmers, etc), all with the exact same GOAP routine.
Boromir
Posts: 451
Joined: Apr 30, 2015 19:28
Location: Texas,U.S., Earth,Solar System
Contact:

Re: GOAP: A Basic AI Tutorial

Postby Boromir » Dec 28, 2018 5:08

leopardpm wrote:And, yes, in respect to what I have seen of the type of game you had been focusing on before (kinda RPG/RTS), GOAP would fit nicely into it. In the following posts, I will show how to make Agents with differing 'behaviors' (Wood Choppers, Miners, Farmers, etc), all with the exact same GOAP routine.
Sweet! I'm trying to set up a simple RTS game first and then expand based on however much time I have left before the deadline. If I have time I might try and wrap my head around this but first gotta get something playable.

I appreciate you spending time on this tutorial in the middle of the contest.
I'm excited to see what you enter in the contest. The contest should produce a nice collection of FreeBASIC games.
leopardpm
Posts: 1795
Joined: Feb 28, 2009 20:58

Re: GOAP: A Basic AI Tutorial

Postby leopardpm » Dec 28, 2018 5:17

...and I can't wait to see what you come up with too! I sure hope I can cobble something decent together before deadline... alas, I take soooo long to code even simple routines... but will try!
leopardpm
Posts: 1795
Joined: Feb 28, 2009 20:58

Re: GOAP: A Basic AI Tutorial

Postby leopardpm » Jan 01, 2019 9:07

OK...ALMOST ready to hook in the GOAP routine, found some time today to combine some various routines into somewhat of a test \playground' for GOAP to be visualized.... the code is a major mess due to combining 4 different programs... but getting there.

I am trying a new image host, hope it works right - let me know

Here are the 6 associated image files - it looks like the image host strips out any spaces and underscores from the filenames....I tried to change them in the code... hope it works...Right-Clicking and Saving the images one at a time should work to get them....
ImageImageImageImageImage
Image
new campfire image needed with this version:
Image



here is the....ug.... code: GOAP Map Test v003.bas

Code: Select all

#include "fbgfx.bi"
#if __FB_LANG__ = "fb"
Using FB '' Screen mode flags are in the FB namespace in lang FB
#endif

#include once "FBImage.bi"

#ifdef __FB_WIN32__
   Declare Function timeBeginPeriod       Alias "timeBeginPeriod"(As Ulong=1) As Long
   Declare Function timeEndPeriod         Alias "timeEndPeriod"  (As Ulong=1) As Long
#else
   #define timeBeginPeriod
   #define timeEndPeriod
#endif

chdir exepath()

const Red as ulong = rgb(255,0,0)
const Green as ulong = rgb(0,255,0)
const Grass as ulong = rgb(128,200,50)
const Blue as ulong = rgb(0,0,255)
const Yellow as ulong = rgb(255,255,0)
const Black as ulong = rgb(0,0,0)
const White as ulong = rgb(255,255,255)
const Gray as ulong = rgb(200,200,200)

const Trees as integer = 1
const IronOre as integer = 2
const BerryBushes as integer = 3
const Mushrooms as integer = 4
const firepity as integer = 5

const mapsizeX = 20
const mapsizeY = 14

const TILEW = 40
const TILEH = 40

const SCRW = 1280 '100 * TILEW
const SCRH = 600 '100 * TILEH

'==============================================
'=========== Sub/Function Declares  ===========
'==============================================

declare sub Refreshscreen
declare sub DrawMap
declare sub MakeDistanceMaps
declare sub ProcessKeyboard
declare sub Moving
declare sub Chopping
declare sub sleepytime
declare sub EnvironmentAnimations

declare sub CreateResources(ByVal ot1 as integer,_
                            ByVal ot2 as integer,_
                            ByVal ot3 as integer,_
                            ByVal ot4 as integer,_
                            ByVal ot5 as integer)

declare function PQ_TE_Add(ByVal newtime as double, byval event as ushort) as integer
declare function PQ_TE_Del(ByVal thisOne as integer) as integer

declare function FrontierDel(ByVal thisOne as integer) as integer
declare function FrontierAdd(ByVal frontX as integer,_
                             ByVal frontY as integer,_
                             ByVal frontCost as integer,_
                             byval ot as integer,_
                             byval treeNum as integer) as integer

'==============================================
'================ LOAD SPRITES  ===============
'==============================================
dim shared as any ptr sprite(1 to 4)
sprite(Trees)       = imagecreate(64,64)
sprite(IronOre)     = imagecreate(32,32)
sprite(BerryBushes) = imagecreate(32,32)
sprite(Mushrooms)   = imagecreate(32,32)

sprite(Trees)       = LoadRGBAFile("fir A ani0000 64x64.png")
sprite(IronOre)     = LoadRGBAFile("stone heap0000 32x32.png")
sprite(BerryBushes) = LoadRGBAFile("berrybush 0005 32x32.png")
sprite(Mushrooms)   = LoadRGBAFile("mushroom3 32x32.png")

dim shared as any ptr gobby
gobby = imagecreate(2432,512)
gobby = LoadRGBAFile("goblin_lumberjack_redadj.png")

' frame offset is which animation sequence to use (4 = walking w/axe, 12 = walking with wood)
dim shared as integer frameOffset = 4

dim shared as any ptr mousey
mousey = imagecreate(128,32) 'or whatever
mousey = LoadRGBAFile("Cursor-Hand-Point-Green.png")

dim shared as any ptr campfire
campfire = imagecreate(32,32) 'or whatever
campfire = LoadRGBAFile("Campfire.png")
'==============================================

    dim shared as double starttime, endtime
    dim shared as long rfps

    ' PQ_TE = Sorted Array/Stack for Timer Event Stack
type te
    as double eTime
    as ushort event
end type

    dim shared as te PQ_TE(1000)
    ' TE_pntr = Timer Event stack pointer
    dim shared as ushort TE_pntr

'==============================================

Type mouse
    As Integer res
    As Integer x, y, wheel, clip
    Union
        buttons As Integer
        Type
            Left:1 As Integer
            Right:1 As Integer
            middle:1 As Integer
        End Type
    End Union
End Type
 
Dim shared As mouse m

type SPRITE
    as integer mx    ' map cell X coord
    as integer my    ' map cell Y coord
    as integer x     ' actual pixel X coord
    as integer y     ' actual pixel Y coord
    as integer frame      ' frame #
    as integer facing     ' frame facing
    as integer w          ' width of sprite frame
    as integer h          ' height of sprite frame
end type

dim shared as sprite GobInfo

type dmapinfo
    as ushort dist
    as ubyte  pntr
    as ubyte  dirVect
end type

type mainmap
    as ubyte Obj
    as dmapinfo DMInfo(1 to 5) '1=tree, 2=iron, 3=bush, 4=mush, 5=firepit
end type

dim shared as mainmap map(mapsizeX, mapsizeY)

data "Tree", "Iron Deposit", "Berry Bush", "Mushroom", "Firepit"
    dim shared as string ObjectName(1 to 5)
    for obj as integer = 1 to 5
        read ObjectName(obj)
    next obj

    ' get Map ready...
    for i as integer = 0 to mapsizeX
        for j as integer = 0 to mapsizeY
            ' clear map objects
            map(i,j).obj = 0
            ' initialize map distances for pathfinding....
            map(i,j).DMInfo(Trees).dist = 999
            map(i,j).DMInfo(IronOre).dist = 999
            map(i,j).DMInfo(BerryBushes).dist = 999
            map(i,j).DMInfo(Mushrooms).dist = 999
            map(i,j).DMInfo(Firepity).dist = 999
        next j
    next i
   
'==============================================
type dinfo
    as byte xAdj
    as byte yAdj
    as byte mCost
end type

dim shared as dinfo DirInfo(7) ' for movement & pathfinding
' directions 0-7
' 7 0 1
' 6 x 2
' 5 4 3
'
' info: xAdj, yAdj, movecost
data  0,-1,10
data  1,-1,14
data  1, 0,10
data  1, 1,14
data  0, 1,10
data -1, 1,14
data -1, 0,10
data -1,-1,14

    ' initialize Direction Information Array
    for i as integer = 0 to 7
        read DirInfo(i).xAdj
        read DirInfo(i).yAdj
        read DirInfo(i).mCost
    next i

'==============================================
type frontierPQ
    as ushort Cost
    as ushort x
    as ushort y
    as ushort objNum
end type

dim shared as frontierPQ frontier(2000)
dim shared as integer fPntr

'==============================================

type resource
    as ushort health
    as ushort x
    as ushort y
end type
dim shared as resource WorldResource(100, 1 to 5) ' index '0' is how many of that obj type....
dim shared as integer NumOfWR(1 to 5)

'==============================================
'=========== Initialize Main Loop =============
'==============================================
    dim shared as integer FPS, LPS, desiredFPS, Loops, Frames, SleepTImes, NoSleepTimes, DoingSomething = 0
    dim shared as double TimeStart, OldTime, RefreshTime, EstRefreshdelay, Lastframe, SleepDelay, gobbySpeed
    dim shared as ushort xm, ym, curDirect
    dim shared as integer x1, y1, c1, clrNew, ot, hasWood = 0, firepit = 0

    screenres SCRW,SCRH,32,2 'set up 2 video pages (#0 visible, #1 working)
    ScreenSet 1, 0 ' working page #1, visible page #0

    randomize

    CreateResources(8,2,5,1,1) ' (trees, IronDeposits, bushes, mushrooms, firepit)
    MakeDistanceMaps

    desiredFPS = 30
    RefreshTime = 1/desiredFPS
    SleepTImes = 0 : Loops = 0 : Frames = 0 : TE_pntr = 0 ' no events in stack
    TimeStart = timer
   
    PQ_TE_Add(timer+RefreshTime,100) ' add the next screen refresh to Timer Event Stack (100 = refresh screen event)
    DrawMap
    Refreshscreen

    GobInfo.mx = 10
    GobInfo.my = 7
    GobInfo.x = ((TILEW-1) * GobInfo.mx)-22
    GobInfo.y = ((TILEH-1) * GobInfo.my)-39
    GobInfo.h = 64
    GobInfo.w = 64
    GobInfo.frame = 2  ' starting frame of animation sequences?!
    curDirect = 99
    gobbySpeed = .05   ' figure .125 is good 8 frames/sec..but was too slow for me...

' frame offset is which animation sequence to use (4 = walking w/axe, 12 = walking with wood)
    frameOffset = 4
   
'==============================================
'==============   Main Loop   =================
'==============================================
Do
    Loops = Loops + 1
   
    if timer > PQ_TE(TE_pntr).eTime then 'check timer against the next event time
        select case PQ_TE(TE_pntr).event ' figure out what Event needs to be dealt with
            case 100 ' this is the code for RefreshScreen Event
                DrawMap
                Refreshscreen
            case 200 ' gobby is moving...
                Moving
            case 300 ' gobby is chopping...
                Chopping
               
            case 400 ' Do this to update Environmental Animations
                EnvironmentAnimations
            case 500
               
            case 600
               
            case 700 ' could be an action or world update or even animation frame change...
               
        end select
    end if
   
    ProcessKeyboard
    sleepytime
Loop until multikey(SC_ESCAPE)

'==============================================
    imagedestroy sprite(Trees)
    imagedestroy sprite(IronOre)
    imagedestroy sprite(BerryBushes)
    imagedestroy sprite(Mushrooms)
    imagedestroy gobby
    imagedestroy mousey
end
'==============================================

'==============================================
'==========   Subs and Functions   ============
'==============================================
sub sleepytime
    ' if there is enough time for a minimal sleep (1.5ms) then sleep
    if PQ_TE(TE_pntr).eTime > (timer + .002) then
        timebeginperiod
        sleep 1
        timeendperiod
        SleepTImes += 1
    else
        NoSleepTimes +=1
    end if
end sub

sub EnvironmentAnimations
    TE_pntr -= 1 ' Quick n Dirty remove this event
    firepit += 1
    if firepit = 4 then firepit = 2 ' change campfire animation frame between 2 & 3
    PQ_TE_Add(timer+(.1)+(rnd/4),400) ' flicker flames every randomly
end sub

sub Chopping
    TE_pntr -= 1 ' Quick n Dirty remove this event
    GobInfo.frame += 1
   
    ' if has reach end of animation sequence, then should be in center of next map cell...
    if GobInfo.frame = 6 then
        curDirect = 99 ' end animation
        frameOffset = 4
        GobInfo.frame = 2
        DoingSomething = 0
        hasWood = 1
    else
        'if GobInfo.frame = 6 then GobInfo.frame = 0 'loop frames for animation
        PQ_TE_Add(timer+(gobbySpeed*2),300) ' add a new Chopping Event to Timer Event Stack (.125 sec = 8 frames/sec)
        DoingSomething = 1
    end if
end sub

sub Moving
    TE_pntr -= 1 ' Quick n Dirty remove this event
    ' assuming curDirect is NOT 99!!!
    GobInfo.x += (DirInfo(GobInfo.facing).xAdj * 5)
    GobInfo.y += (DirInfo(GobInfo.facing).yAdj * 5)
    GobInfo.frame += 1
    ' if has reach end of animation sequence, then should be in center of next map cell...
    if GobInfo.frame = 2 then 'for some reason the animation sequence starts in the middle...
        curDirect = 99 ' end animation
        frameOffset = 4
        DoingSomething = 0
    else
        if GobInfo.frame = 8 then GobInfo.frame = 0 'loop frames for animation
        PQ_TE_Add(timer+gobbySpeed,200) ' add a new Moving Event to Timer Event Stack (.125 sec = 8 frames/sec)
        DoingSomething = 1
    end if
end sub

sub ProcessKeyboard
    GobInfo.mx = (GobInfo.x+22)/(TILEW-1)
    GobInfo.my = (GobInfo.y+39)/(TILEH-1)
    if DoingSomething = 0 then 'if not doing anything then....
        if map(GobInfo.mx + DirInfo(GobInfo.facing).xAdj, GobInfo.my + DirInfo(GobInfo.facing).yAdj).obj = firepity then
            if MultiKey(SC_D) and (hasWood = 1) then 'drop wood in direction of facing, if there is a firepit!
                firepit = 1
                hasWood = 0
            end if
            if MultiKey(SC_F) and (firepit = 1) then 'light campfire in direction of facing, if there is a firepit with wood!
                firepit = 2
                PQ_TE_Add(timer+(.1),400) ' flicker flames every 1/2 sec
            end if
        end if
    end if
   
    if DoingSomething = 0 then 'if not doing anything then....
        if MultiKey(SC_C) then 'chop in direction of facing, if there is a tree!
            if map(GobInfo.mx + DirInfo(GobInfo.facing).xAdj, GobInfo.my + DirInfo(GobInfo.facing).yAdj).obj = trees then
                curDirect = GobInfo.facing ' this stupid variable 'curDirect' also serves to tell if an animation is in process....
                PQ_TE_Add(timer+(gobbySpeed*2),300) ' add a new Chopping Event to Timer Event Stack
                frameOffset = 20
                GobInfo.frame = 0
                DoingSomething = 1
                hasWood = 0
            else
                curDirect = 99
                frameOffset = 4
                DoingSomething = 0
            end if
        end if
    end if

    if DoingSomething = 0 then
        If (GobInfo.mx > 1)                                        and MultiKey(SC_LEFT)     Then curDirect = 6
        If (GobInfo.my > 1)                                        and MultiKey(SC_UP)       Then curDirect = 0
        If (GobInfo.mx < mapsizeX)                                 and MultiKey(SC_RIGHT)    Then curDirect = 2
        If (GobInfo.my < mapsizeY)                                 and MultiKey(SC_DOWN)     Then curDirect = 4
        If (GobInfo.my > 1) and (GobInfo.mx > 1)                   and MultiKey(SC_HOME)     Then curDirect = 7
        If (GobInfo.mx < (mapsizeX)) and (GobInfo.my > 1)          and MultiKey(SC_PAGEUP)   Then curDirect = 1
        If (GobInfo.my < (mapsizeY)) and (GobInfo.mx > 1)          and MultiKey(SC_END)      Then curDirect = 5
        If (GobInfo.my < (mapsizeY)) and (GobInfo.mx < (mapsizeX)) and MultiKey(SC_PAGEDOWN) Then curDirect = 3

        if curDirect < 99 then
            GobInfo.facing = curDirect
            if map(GobInfo.mx + DirInfo(curDirect).xAdj, GobInfo.my + DirInfo(curDirect).yAdj).obj = 0 then ' if destination map cell is empty...
                frameOffset = 4 ' select moving with axe animation
                GobInfo.frame = 2
                PQ_TE_Add(timer+gobbySpeed,200) ' add a new Moving Event to Timer Event Stack (.125 sec = 8 frames/sec)
                DoingSomething = 1
            else
                curDirect = 99
                DoingSomething = 0
            end if
        end if
    end if
   
    While Inkey <> "": Wend '' Clear the input buffer
end sub

sub Refreshscreen
    dim as double t1 = timer
   
    'PQ_TE_Del(TE_pntr) ' remove the Event
    TE_pntr -= 1 ' Quick n Dirty remove this event
    PQ_TE_Add(t1+RefreshTime,100) ' add a new Scren Refresh Event to Timer Event Stack

    ' FPS stuff
    FPS = 1/(t1 - OldTime) ' time between frames
    OldTime = t1 'reset OldTime

    m.res = GetMouse( m.x, m.y, m.wheel, m.buttons, m.clip )

'    locate 3,110: Print Using "res = #"; m.res
'    locate 4,110: Print Using "x = ###; y = ###; wheel = +###; clip = ##"; m.x; m.y; m.wheel; m.clip
'    locate 5,110: Print Using "buttons = ##; left = #; middle = #; right = #"; m.buttons; m.left; m.middle; m.right

    xm = (m.x)/TILEW : ym = (m.y)/TILEH
    if (m.clip = 0) and (xm> 0) and (xm<(mapsizeX+1)) and (ym > 0) and (ym<(mapsizeY+1)) then
        ' hide regular cursor, put map cursor
        setmouse ,,0
        put (m.x-1,m.y-1),mousey,alpha
        color Yellow
        locate 3,110 : print using "MouseOver Info at Location (&/&):  ";xm;ym;
        locate 4,110 : print "----------------------------------"
        locate 5,110 : print "Object Type: ";
        if map(xm,ym).obj = 0 then
            print "<empty>        "
            locate 7,110 : print "Distance to Nearest..."
            locate 9,110 : print using "           Tree(&) is &   ";map(xm,ym).DMInfo(Trees).pntr ;map(xm,ym).DMInfo(Trees).dist;
            locate 11,110 : print using "            Ore(&) is &   ";map(xm,ym).DMInfo(IronOre).pntr ;map(xm,ym).DMInfo(IronOre).dist;
            locate 13,110 : print using "     Berry Bush(&) is &   ";map(xm,ym).DMInfo(BerryBushes).pntr ;map(xm,ym).DMInfo(BerryBushes).dist;
            locate 15,110 : print using "       Mushroom(&) is &   ";map(xm,ym).DMInfo(Mushrooms).pntr ;map(xm,ym).DMInfo(Mushrooms).dist;
            locate 17,110 : print using "        Firepit(&) is &   ";map(xm,ym).DMInfo(firepity).pntr ;map(xm,ym).DMInfo(firepity).dist;

        else
            print ObjectName(map(xm,ym).obj);"(";map(xm,ym).DMInfo(map(xm,ym).obj).pntr;")        "
        end if
    else
        ' restore regular mouse cursor when mouse is outside of map area
        setmouse ,,1
    end if
    color White
    locate 23,110 : print "Main Loops per Frame =";Loops;"    "
    locate 24,110 : print "Display FPS =";FPS;"       "
    locate 25,110 : print "Timer =";int(t1);"      "
    locate 26,110 : print "Refresh Time = ";RefreshTime
    locate 28,110 : print "# of times Slept =";SleepTImes
    locate 29,110 : print "# of loops with No Sleep =";NoSleepTimes
    locate 31,110 : print "% of time sleeping ";int((SleepTImes*.001)/(t1-TimeStart)*10000)/100

    locate 34,110 : print using "Goblin: map(&/&)  pixel(&/&)     ";GobInfo.mx;GobInfo.my;GobInfo.x;GobInfo.y
    locate 35,110 : print using "       Frame (&) ";GobInfo.Frame
    locate 36,110 : print using "      Facing (&) ";GobInfo.facing
    locate 38,110 : print using "   CurDirect (&) ";curDirect
    locate 40,110 : print using "     Firepit (&) ";firepit
    locate 41,110 : print using "     hasWood (&) ";hasWood
    color red
    locate 45,110 : print "***************  INSTRUCTIONS: ****************"
    locate 46,110 : print "Use Keypad for movement directions"
    locate 48,110 : print "Mouse over map cells for info"
    locate 50,110 : print "If facing and next to a Tree:"
    locate 51,110 : print "    press 'C' to chop it,"
    locate 52,110 : print "    after Chopping, Gobby will be carrying Wood"
    locate 54,110 : print "If facing and next to the Firepit:"
    locate 55,110 : print "    press 'D' to Drop Wood on it,"
    locate 56,110 : print "    press 'F' to Light Wood in firepit,"
   
    ScreenCopy
    Loops = 0 'reset Loop counter
end sub

'==============================================

sub DrawMap
    dim as integer x1, y1
'        dim as ulong c1
    cls
    ' Draw Background Grid and Objects that are in behind of Gobby
    for i as integer = 1 to mapsizeX
        x1 = i*TILEW-20
        for j as integer = 1 to mapsizeY
            y1 = j*TILEH-20
            line(x1,y1)- step(TILEW-2,TILEH-2),Grass,BF
            if (map(i,j).obj > 1) and (map(i,j).obj < 5) then
                put (x1+4,y1+4),sprite(map(i,j).obj ),alpha
            end if
            if map(i,j).obj = 5 then 'firepit/campfire
                put (x1+4,y1+4),campfire,(0,0)-(31,31),alpha ' stone firepit
                if firepit > 0 then put (x1+4,y1+4),campfire,(1*32,0)-((1+1)*32-1,31),alpha '  wood only
                if firepit > 1 then put (x1+4,y1+4),campfire,(firepit*32,0)-((firepit+1)*32-1,31),alpha
            end if
        next j
    next i

    ' Show Red Map Cell Outline
    if (m.clip = 0) and (xm> 0) and (xm<(mapsizeX+1)) and (ym > 0) and (ym<(mapsizeY+1)) then
        line((xm*TILEW-20)-1,(ym*TILEH-20)-1)- step(TILEW,TILEH),Red,B
    end if

    ' Draw Gobby

    put (GobInfo.x,GobInfo.y),gobby,_
     ((GobInfo.frame+frameOffset+(hasWood*8))*GobInfo.w,GobInfo.facing*GobInfo.h)_
    -((GobInfo.frame+frameOffset+(hasWood*8))*GobInfo.w+GobInfo.w-1,GobInfo.facing*GobInfo.h+GobInfo.h-1), alpha

    ' Draw Objects(trees) that are in front of Gobby and map cell red outline
    for i as integer = 1 to mapsizeX
        x1 = i*TILEW-20
        for j as integer = 1 to mapsizeY
            y1 = j*TILEH-20
            if map(i,j).obj = trees then put (x1-14,y1-33),sprite(trees),alpha
        next j
    next i
end sub

'==============================================

function PQ_TE_Add(ByVal newtime as double, byval event as ushort) as integer
    '
    '   PQ_TE() is a Array which maintains an array in sorted order
    '
    ' This routine Adds an event to the Timer Event Stack Sorted Array
    ' this function uses and alters the shared variables: PQ_TE() & TE_pntr

    ' ... add it to the end then bubble sort it down...
    dim as integer bub, addHere
    TE_pntr = TE_pntr + 1
    addHere = TE_pntr
    PQ_TE(TE_pntr).eTime = newtime
    PQ_TE(TE_pntr).event = event
    if TE_pntr > 1 then
        bub = TE_pntr
        do
            if PQ_TE(bub).eTime > PQ_TE(bub-1).eTime then
                swap PQ_TE(bub) , PQ_TE(bub-1)
                addHere = bub - 1
            else
                bub = 2 ' early exit
            end if
            bub = bub - 1
        loop until bub < 2
    end if
    return addHere
end function

'==============================================

function PQ_TE_Del(ByVal thisOne as integer) as integer
    ' Deletes an event from the Timer Event Stack Sorted Array
    select case thisOne
        case is < TE_pntr
            for i as integer = thisOne to (TE_pntr-1)
                PQ_TE(i) = PQ_TE(i+1)
            next i
            TE_pntr = TE_pntr - 1
        case is = TE_pntr
            TE_pntr = TE_pntr - 1
    end select
    return thisOne
end function

'==============================================

sub MakeDistanceMaps
    ' a basic Djistra's Floodfill routine, not optimized at all...
    ' Assumes Frontier hold correct objects....
    '
    dim as integer x, y, i, j, dist, distNew, oldPoint, objPntr
    dim as integer x1, y1
    for ot as integer = 1 to 5
        'make frontier for this ot
        fPntr= 0
        if NumOfWR(ot) > 0 then
            for i = 1 to NumOfWR(ot)
                FrontierAdd(WorldResource(i,ot).x,WorldResource(i,ot).y,0, ot, i)
            next i
        end if

        do
            oldPoint = fPntr
            dist     = frontier(fPntr).cost
            x        = frontier(fPntr).x
            y        = frontier(fPntr).y
            objPntr  = frontier(fPntr).objNum
           
            ' remove point from frontier
            FrontierDel(oldPoint) 'remove current point from frontier
   
            ' check all 8 directions, if cost to move there is less then their current cost then
            ' change their cost and add to frontier
            for direct as integer = 0 to 7
                i = x+DirInfo(direct).xAdj
                j = y+DirInfo(direct).yAdj
                ' make sure within Map bounds and not a Blocker
                if ((i > 0) and (i < (mapsizeX+1))) and ((j > 0) and (j < (mapsizeY+1))) then
                    if (map(i,j).obj = 0  ) then
                        distNew = dist + DirInfo(direct).mCost
                        x1 = i*TILEW
                        y1 = j*TILEH
                        ' if new dist is less than old dist...
                        if map(i,j).DMInfo(ot).dist > distNew then
                            ' if old dist = UNVISITED...
                            if map(i,j).DMInfo(ot).dist = 999 then
                                FrontierAdd(i,j,distNew,ot, objPntr)
                            end if
                            map(i,j).DMInfo(ot).dist    = distNew
                            map(i,j).DMInfo(ot).dirVect = (direct+4) mod 8  ' save flow field info
                            map(i,j).DMInfo(ot).pntr    = objPntr
                        end if
                    end if
                end if
            next direct
        loop until fPntr = 0
    next ot
end sub

'==============================================

sub CreateResources(ByVal ot1 as integer,_
                    ByVal ot2 as integer,_
                    ByVal ot3 as integer,_
                    ByVal ot4 as integer,_
                    ByVal ot5 as integer)
   
    dim as integer x, y
    dim as integer ResType(1 to 5)
    ResType(1) = ot1 : ResType(2) = ot2
    ResType(3) = ot3 : ResType(4) = ot4
    ResType(5) = ot5
   
    'map(3,3).obj = 5
   
    for rt as integer = 1 to 5
        if ResType(rt) > 0 then
            NumOfWR(rt) = 0
            for i as integer = 1 to ResType(rt)
                x = rnd * (mapsizeX-2) + 1
                y = rnd * (mapsizeY-2) + 1
                while map(x,y).obj > 0
                    x = rnd * (mapsizeX-2) + 1
                    y = rnd * (mapsizeY-2) + 1
                wend
               
                map(x,y).obj = rt             ' put 1 object(ot) there
                map(x,y).DMInfo(rt).pntr = i
                map(x,y).DMInfo(rt).dist = 0  ' zero out the distance for that object
                ' add it to WorldResource() array for each obj type
                NumOfWR(rt) += 1
                WorldResource(i,rt).x = x
                WorldResource(i,rt).y = y
                WorldResource(i,rt).health = 100
            next i
        end if
    next rt
end sub

'==============================================

function FrontierAdd(ByVal frontX as integer,_
                     ByVal frontY as integer,_
                     ByVal frontCost as integer,_
                     ByVal ot as integer,_
                     ByVal treeNum as integer) as integer
    ' this function adds a Map location to the Frontier Array for use in generating a Distance Map
    '  ... add it to the end then bubble sort it down...
    dim as integer bub, frontHere
    fPntr = fPntr + 1
    frontHere = fPntr
    frontier(fPntr).Cost = frontCost
    frontier(fPntr).x = frontX
    frontier(fPntr).y = frontY
    frontier(fPntr).objNum = treeNum
    if fPntr > 1 then
        bub = fPntr
        do
            if frontier(bub).cost > frontier(bub-1).cost then
                swap frontier(bub) , frontier(bub-1)
                frontHere = bub - 1
            else
                exit do ' early exit
            end if
            bub = bub - 1
        loop until bub < 2
    end if
    return frontHere
end function

'==============================================

function FrontierDel(ByVal thisOne as integer) as integer
    select case thisOne
        case is < fPntr
            for i as integer = thisOne to (fPntr-1)
                frontier(i) = frontier(i+1)
            next i
            fPntr = fPntr - 1
        case is = fPntr
            fPntr = fPntr - 1
    end select
    return thisOne
end function

'=========================Multikey ScanCodes
'            SC_ESCAPE       &h01
'            SC_1            &h02
'            SC_2            &h03
'            SC_3            &h04
'            SC_4            &h05
'            SC_5            &h06
'            SC_6            &h07
'            SC_7            &h08
'            SC_8            &h09
'            SC_9            &h0A
'            SC_0            &h0B
'            SC_MINUS        &h0C
'            SC_EQUALS       &h0D
'            SC_BACKSPACE    &h0E
'            SC_TAB          &h0F
'            SC_Q            &h10
'            SC_W            &h11
'            SC_E            &h12
'            SC_R            &h13
'            SC_T            &h14
'            SC_Y            &h15
'            SC_U            &h16
'            SC_I            &h17
'            SC_O            &h18
'            SC_P            &h19
'            SC_LEFTBRACKET  &h1A
'            SC_RIGHTBRACKET &h1B
'            SC_ENTER        &h1C
'            SC_CONTROL      &h1D
'            SC_A            &h1E
'            SC_S            &h1F
'            SC_D            &h20
'            SC_F            &h21
'            SC_G            &h22
'            SC_H            &h23
'            SC_J            &h24
'            SC_K            &h25
'            SC_L            &h26
'            SC_SEMICOLON    &h27
'            SC_QUOTE        &h28
'            SC_TILDE        &h29
'            SC_LSHIFT       &h2A
'            SC_BACKSLASH    &h2B
'            SC_Z            &h2C
'            SC_X            &h2D
'            SC_C            &h2E
'            SC_V            &h2F
'            SC_B            &h30
'            SC_N            &h31
'            SC_M            &h32
'            SC_COMMA        &h33
'            SC_PERIOD       &h34
'            SC_SLASH        &h35
'            SC_RSHIFT       &h36
'            SC_MULTIPLY     &h37
'            SC_ALT          &h38
'            SC_SPACE        &h39
'            SC_CAPSLOCK     &h3A
'            SC_F1           &h3B
'            SC_F2           &h3C
'            SC_F3           &h3D
'            SC_F4           &h3E
'            SC_F5           &h3F
'            SC_F6           &h40
'            SC_F7           &h41
'            SC_F8           &h42
'            SC_F9           &h43
'            SC_F10          &h44
'            SC_NUMLOCK      &h45
'            SC_SCROLLLOCK   &h46
'            SC_HOME         &h47
'            SC_UP           &h48
'            SC_PAGEUP       &h49
'            SC_LEFT         &h4B
'            SC_RIGHT        &h4D
'            SC_PLUS         &h4E
'            SC_END          &h4F
'            SC_DOWN         &h50
'            SC_PAGEDOWN     &h51
'            SC_INSERT       &h52
'            SC_DELETE       &h53
'            SC_F11          &h57
'            SC_F12          &h58
'


right now, it just makes the Distance Maps, puts up a graphical screen, shows some info of the map cell the cursor is over, and allows you to move around a little goblin with the NUMPAD... ESC quits it.... The only reason user control of the goblin is in there is for animation debugging and stuff, of course the whole point will be AI control, not human....

Just something to play around with until I get the GOAP in there correctly...
I do like how the Main Loop Event Timing routine works and easily allows independent frame animation timings

If you change line 247 to:

Code: Select all

    frameOffset = 4
then the gobby carries around his axe....

EDIT: Couldn't stand how sloppy my code was, plus Goblin ran thru things, so took some time to clean up things and do quick fixes....
EDIT: Added the ability to Chop a Tree then carry wood... still buggy...
EDIT: new version, now has campfires to be made and lighted.... and environmental animations... did I mention that I REALLY like how the event timing system works? Also needs another graphic file - added above (campfires).
Last edited by leopardpm on Jan 01, 2019 22:52, edited 1 time in total.
leopardpm
Posts: 1795
Joined: Feb 28, 2009 20:58

Re: GOAP: A Basic AI Tutorial

Postby leopardpm » Jan 01, 2019 18:48

this is the latest version of the GOAP planner which I will combine with the above graphical world to take control of the goblin...

Code: Select all

'        Soooo... the recursive logic goes:
'        Node Array: an doube-linked list of nodes which is grown as the routine iterates (also known as the 'Tree')
'       
'        Node Layout: Parent Node, End State(of Parent), Action Pointer, Resultant End State(after Action Performed), Child Pointers....
'       
'        Frontier: is an array of pointers to all the Active Child Nodes(which would be considered Leaf Nodes at ths point in time) in Tree - inactive Leaf Nodes are either the Start of a Valid Plan, or, point to an invalid plan....
'       
'        Linked Actions Array: a pre-generated array which has links to all the Actions related to each State
'       
'       
'        Start by Adding 'Goal Node' into the Frontier with desired World States in End State of Node
'       
'        do:
'        A - If no Nodes in Frontier then DONE!
'        B - Get (any) Node from Frontier
'        C - Delete this Node from Frontier
'        D - Perform (Nodes' End State XOR this Action's Effects) then (OR this Actions' Req States with it)  = Resultant End States
'        E - Add to this Node: Resultant End States
'           - NOTE: if Resultant End States = 0000 then this is Valid Plan and store pointer to this Node in 'Plans' and loop!
'        F - For each State in the Resultant End States:
'            - For each Action linked to this State
'                1 - Generate Child Node and Add it to Frontier
'                2 - Add to Child Node: Parent Node(this Node) pointer
'                4 - Add to Child Node:  Action Pointer
'                5 - Add to Parent Node(this Node): Child Node pointer - could be memory extensive!
'                - NOTE: if there are no actions at all for any State, then this is an Invalid Plan!
'                - so, (delete Node from Tree?) then loop!
'        - loop!
'
    dim as uShort NumOfPlans = 0
    dim shared as uShort NumOfNodes = 1
    dim as uShort ThisNode, tmpNode

type node
    as uShort ParentPntr
    as uShort ActionPntr
    as uByte  EndWS(1 to 20)      'all possible WorldStates?
    as uShort NumOfChildren
    as uShort ChildPntr(1 to 10) ' more than enough for simple testing of logic
end type
dim shared as node Nodes(1000) ' more than enough
dim shared as node GoalNode, ChildNode

sub DELnode(byval nodenum as integer)
    if NumOfNodes > 0 and nodenum <= NumOfNodes then
        if nodenum = NumOfNodes then
            NumOfNodes -= 1
        else
            ' remove the node from nodes() by moving all nodes after, down 1
            NumOfNodes -= 1
            for i as integer = nodenum to (NumOfNodes)
                Nodes(i) = Nodes(i+1)
            next i
        end if
    end if
end sub

dim as uShort Frontier(1000) ' just a list of pointers to the nodes() on the Frontier
dim as uShort FrontierPntr  ' this is the number of Frontier nodes
dim as uShort Plans(100) ' these point to a Valid Plan (Leaf Node) in Nodes()

type wsp
    as ushort ws_pntr
    as ushort val
end type

type act
    as ushort index
    as string name
    as ushort TimeCost
    as ushort EffortCost
    as ushort NumOfReqWS
    as wsp ReqWS(3)
    as ushort NumOfEffWS
    as wsp EffWS(3)
    as string LocReqName
    as ushort LocReqPntr
end type

dim as act Actions(20)
dim as ushort NumOfActions

' Load Actions Array
    read NumOfActions
    print using " Actions (&):";NumOfActions
    print " ACTION NAME             #ReqWS  ReqWS(1)  ReqWS(2)  ReqWS(3)    #EffWS   Eff(1)    Eff(2)    Eff(3)"
    print " -------------           ------  -------   -------   -------     ------   ------    ------    ------"
    for tmp as integer = 1 to NumOfActions
        read Actions(tmp).index
        read Actions(tmp).name
        read Actions(tmp).TimeCost
        read Actions(tmp).EffortCost
        read Actions(tmp).NumOfReqWS
        print using " (##) \                  \  ##   ";tmp;Actions(tmp).name;Actions(tmp).NumOfReqWS;
        for tmp1 as integer = 1 to 3
            read Actions(tmp).ReqWS(tmp1).ws_pntr
            read Actions(tmp).ReqWS(tmp1).val
            if Actions(tmp).ReqWS(tmp1).ws_pntr = 0 then
                print "   -     ";
            else
                print using "(##)=##  ";Actions(tmp).ReqWS(tmp1).ws_pntr;Actions(tmp).ReqWS(tmp1).val;
            end if
        next tmp1
   
        read Actions(tmp).NumOfEffWS
        print using "       ##     ";Actions(tmp).NumOfEffWS;
        for tmp2 as integer = 1 to 3
            read Actions(tmp).EffWS(tmp2).ws_pntr
            read Actions(tmp).EffWS(tmp2).val
            if Actions(tmp).EffWS(tmp2).ws_pntr = 0 then
                print "   -     ";
            else
                print using "(##)=##  ";Actions(tmp).EffWS(tmp2).ws_pntr;Actions(tmp).EffWS(tmp2).val;
            end if
        next tmp2
        read Actions(tmp).LocReqName
        read Actions(tmp).LocReqPntr
    print
    next tmp

data 12  ' Number of Actions
'     ACTION               Time Effort  NumOf   ReqWS  ReqWS  ReqWS    NumOf   EffWS  EffWS  EffWS   Location
'     NAME                 Cost  Cost   ReqWS    (1)    (2)    (3)     EffWS    (1)    (2)    (3)    Req Type
data 1,"Get Axe",              1,    1,     0,     0,0,   0,0,   0,0,      1,     1,1,   0,0,   0,0,  "Axe",1
data 2,"Chop Tree",            7,   10,     1,     1,1,   0,0,   0,0,      1,     2,1,   0,0,   0,0,  "Tree",2
data 3,"Get Matches",          1,    1,     0,     0,0,   0,0,   0,0,      1,     3,1,   0,0,   0,0,  "Matches",3
data 4,"Make Campfire",        3,    2,     2,     2,1,   3,1,   0,0,      1,     4,1,   0,0,   0,0,  "Firepit",4
data 5,"Make Magic Campfire",  2,    1,     1,     6,1,   0,0,   0,0,      1,     4,1,   0,0,   0,0,  "Firepit",4
data 6,"Get Saw",              1,    1,     0,     0,0,   0,0,   0,0,      1,     5,1,   0,0,   0,0,  "Saw",5
data 7,"Saw Tree",             5,    9,     1,     5,1,   0,0,   0,0,      1,     2,1,   0,0,   0,0,  "Tree",2
data 8,"Get Magic Wand",       1,    1,     0,     0,0,   0,0,   0,0,      1,     6,1,   0,0,   0,0,  "Wand",6
data 9,"Collect Branches",     2,    2,     0,     0,0,   0,0,   0,0,      1,     2,1,   0,0,   0,0,  "Tree",2
data 10,"Get Pick",            1,    1,     0,     0,0,   0,0,   0,0,      1,     8,1,   0,0,   0,0,  "Pick",7
data 11,"Mine Ore",            8,   10,     1,     8,1,   0,0,   0,0,      1,     9,1,   0,0,   0,0,  "IronVein",8
data 12,"Refine Ore",          4,    3,     2,     4,1,   9,1,   0,0,      1,    10,1,   0,0,   0,0,  "Firepit",4


type wstype
    as ushort index
    as string name
    as ushort val
end type

dim shared as wstype WSA(20)
dim shared as integer NumOfWS

' Load WorldState array
    read NumOfWS
    print
    print using " WorldStates (&):";NumOfWS
    print " WS   STATE          DEFAULT"
    print " --  -------------   -------"
    for ws as integer = 1 to NumOfWS
        read WSA(ws).index,WSA(ws).name, WSA(ws).val 'default values...
        print using " (&) \              \   &";ws;WSA(ws).name; WSA(ws).val
    next ws
    print

data 10  ' Number of Different WorldStates(WS)
data 1,"hasAxe",      0 ' WS=1
data 2,"hasWood",     0 ' WS=2
data 3,"hasMatches",  0 ' WS=3
data 4,"hasCampfire", 0 ' WS=4
data 5,"hasSaw",      0 ' WS=5
data 6,"hasMagicWand",0 ' WS=6
data 7,"canUseMagic" ,0 ' WS=7
data 8,"hasPick",     0 ' WS=8
data 9,"hasOre",      0 ' WS=9
data 10,"hasIronBar", 0 ' WS=10

'
' World States: things that define the current state of the World
' Ex: Time (of day, season), Temperature, Precipitation (rain/snow/hail), Wind?, Locations of Map Objects and all agents/mobs
'
' Agent States: things that define the current state of the Agent
' Ex: Stats (STR, DEX, etc), HP, MP, Object(s) in hands, Objects on person (in backpack?), Objects 'owned' in world
'
' Agent Influencers: things that influence choices made by Agent
' Ex: Likes/Dislikes (vegan?, magic, weapon types?, etc), Personality Traits (lazy, courageous, curious, social, evil/good, etc)
'
' Agent Skills: Knowledge Agent knows which enables certain Actions to be performed
' Ex: Archery, Swimming, Climbing, Swordsmanship, Horseback Riding, Carpentry, Blacksmithing, Alchemy, Magic Use, Fishing, Tracking,
'     herbalism, Lockpicking, Detecting Traps, Medicine, pickpocketing, stealthiness, combat tactics, farming, animal husbandry, cooking,
'     baking, leatherworking, fletching, sword-making, axe-making, etc
'

type lAAtype
    as uShort NumOfActs
    as uShort ActPntr(1 to 20) ' this is the 'Linked Actions Array' with pointers to every Action which affects this worldstate
end type
dim as lAAtype LAA(1 to 20) ' 10 different max worldstates

    print
    print using " Linked Actions Array for all & WorldStates:";NumOfWS
    print " (List of all Actions which Affect this WorldState)"
    print " WORLDSTATE      ","ACTIONS"',,"# of Actions"
    print " ----------------","------------------------"',"------------"
    for ws as integer = 1 to NumOfWS

        LAA(ws).NumOfActs = 0
        print using " (&) \             \ ";ws;WSA(ws).name;

        for act as integer = 1 to NumOfActions
            if Actions(act).NumOfEffWS > 0 then 'should always be true as every action has some effects, right
                for eff as integer = 1 to Actions(act).NumOfEffWS
                    if Actions(act).EffWS(eff).ws_pntr = ws then' does this action affect the current WS?
                        LAA(ws).NumOfActs += 1
                        LAA(ws).ActPntr(LAA(ws).NumOfActs) = act
                       
                        if LAA(ws).NumOfActs = 1 then
                            print ,
                            print using "(&)&";act;Actions(act).name;
                        else
                            print ", ";
                            print using "(&)&";act;Actions(act).name;
                        end if
                    end if
                next eff
            end if
        next act
        if LAA(ws).NumOfActs = 0 then print , "<none>";
        print ',, LAA(ws).NumOfActs
    next ws

'   
'   
'' initialize

    GoalNode.EndWS(4) = 1  ' set goal of WorldState 'HasCampfire' = 1
    NumOfNodes = 1
    Nodes(NumOfNodes) = GoalNode
    FrontierPntr = 1
    Frontier(FrontierPntr) = NumOfNodes
    dim as integer IsPlan = 1
'sleep
'
'
    do
        ThisNode = Frontier(FrontierPntr)        ' using FrontierPntr as the Node for this iteration...
        FrontierPntr -= 1   'quickie delete node from Frontier
        dim as uShort nActPntr = Nodes(ThisNode).ActionPntr
        if nActPntr > 0 then  ' if this node is not the starting Goal Node (which has no actions... yet)
            IsPlan = 1
            ' copy all the WorldStates from the Parent EndStates
            for ws as integer = 1 to NumOfWS
                Nodes(ThisNode).EndWS(ws) = Nodes(  Nodes(ThisNode).ParentPntr ).EndWS(ws)
                ' and adjust them if this nodes' action effects them
                if Actions(nActPntr).NumOfReqWS > 0 then
                    for rws as integer = 1 to Actions(nActPntr).NumOfReqWS
                        if Actions( nActPntr ).ReqWS(rws).ws_pntr = ws then
                            Nodes(ThisNode).EndWS(ws) = Actions(nActPntr).ReqWS(rws).val
                            IsPlan = 0
                        end if
                    next rws
                end if
                if Actions(nActPntr).NumOfEffWS > 0 then ' should always be -> every action has an effect, right?
                    for ews as integer = 1 to Actions(nActPntr).NumOfEffWS
                        if Actions( nActPntr ).EffWS(ews).ws_pntr = ws then
                            Nodes(ThisNode).EndWS(ws) = 0 '
                        end if
                    next ews
                end if
                if Nodes(ThisNode).EndWS(ws) > 0 then IsPlan = 0
            next ws
            if IsPlan = 1 then 'VALID PLAN
                NumOfPlans += 1
                Plans(NumOfPlans) = ThisNode
                Continue Do
            end if
        end if

        for state as integer = 1 to NumOfWS
            'if (Nodes(ThisNode).EndWS(state) <=  WSA(state).val) then Nodes(ThisNode).EndWS(state) = 0
            if (Nodes(ThisNode).EndWS(state) <> 0) then
                if LAA(state).NumOfActs <> 0 then 'if 0 then INVALID PLAN!!!!!
                    '  find actions for this world state
                    for ThisAction as integer = 1 to LAA(state).NumOfActs
                        ChildNode.ParentPntr     = ThisNode
'                        ChildNode.ParentEndState = Nodes(ThisNode).EndState
                        ChildNode.ActionPntr     = LAA(state).ActPntr(ThisAction)
                        NumOfNodes += 1
                        Nodes(NumOfNodes) = ChildNode
                        FrontierPntr += 1
                        Frontier(FrontierPntr) = NumOfNodes
                        Nodes(ThisNode).NumOfChildren += 1
                        Nodes(ThisNode).ChildPntr(Nodes(ThisNode).NumOfChildren) = NumOfNodes
                    next ThisAction
                else
'                - NOTE: if there are no actions at all for any State, then this is an Invalid Plan!
'                - so, (delete Node from Tree?) then Recurse!
                    'DELnode(ThisNode)
                    print using " NO valid action for state(&)";state
                    continue do
                end if
            else
            end if
        next state
        'sleep
    loop until FrontierPntr = 0 or ThisNode = 0
'
    print
    print "Total Plans found = ";NumOfPlans
    print "Total Number of Nodes = ";NumOfNodes
    print
    Print "<Hit key to see Plans!>"
sleep

for p as integer = 1 to NumOfPlans
    print "PLAN #";p
    ThisNode = Plans(p)
    dim as ushort totalEffort = 0
    dim as ushort totalTime = 0
    dim as ushort currLocX, currLocY, totalDist = 0
    print "  Action Sequence: ";
    do
        dim as uShort nActPntr = Nodes(ThisNode).ActionPntr
        print using "(&)";nActPntr;
        print Actions(nActPntr).Name;"  ";

        ' calculate travel and costs...
        select case Actions(nActPntr).LocReqName
        case "Axe"
            ' calc distance from currLocX,currLocY to nearest Axe
            ' pathfind(Tree)  ----- just filler for now
            totalDist += 1 ' actually add Axe distance
            currLocX = 1   ' actually make it the Axe location
            currLocY = 1   ' actually make it the Axe location
           
        case "Tree"
            ' calc distance from currLocX,currLocY to nearest Tree
            ' pathfind(Tree)  ----- just filler for now
            totalDist += 1 ' actually add tree distance
            currLocX = 1   ' actually make it the tree location
            currLocY = 1   ' actually make it the tree location
        case "Matches"
           
        case "Firepit"
           
        case "Saw"
           
        case "Wand"
           
        case "Pick"
           
        case "IronVein"
           
        end select
       
        totalTime += Actions(nActPntr).TimeCost
        totalEffort += Actions(nActPntr).EffortCost

        ThisNode = Nodes(ThisNode).ParentPntr
    loop until ThisNode = 1
    print
    print using "  This plan takes ### secs and ### effort and Agent travels a total of about ### spaces";totalTime;totalEffort;totalDist
    print
next

'
sleep
end

leopardpm
Posts: 1795
Joined: Feb 28, 2009 20:58

Re: GOAP: A Basic AI Tutorial

Postby leopardpm » Jan 02, 2019 16:22

OK, got side tracked with sounds, no less.... but decided I would be smarter as to how to provide access for anyone would wants all the files... hence trying Google Drive

Here is the link to the project: https://drive.google.com/drive/folders/1MW0dMC2jL_Q0-y7qpOy8R1YTeH01QWrW?usp=sharing

I will now just sync up and all files should be up-to-date including any new files needed.

In the folder are also the required fbsound library files which should work as long as they are in the same folder as the program - please let me know if you get errors or no sounds...
Boromir
Posts: 451
Joined: Apr 30, 2015 19:28
Location: Texas,U.S., Earth,Solar System
Contact:

Re: GOAP: A Basic AI Tutorial

Postby Boromir » Jan 02, 2019 16:52

This is looking really good, I'm looking forward to seeing them combined.
leopardpm wrote:In the folder are also the required fbsound library files which should work as long as they are in the same folder as the program - please let me know if you get errors or no sounds...

There isn't any sound library files for linux included. Also no 64 bit dll for windows. You're using Fbimage as well which you don't include anything for.
Not a complaint, just a heads up.
leopardpm
Posts: 1795
Joined: Feb 28, 2009 20:58

Re: GOAP: A Basic AI Tutorial

Postby leopardpm » Jan 02, 2019 17:03

Boromir wrote:This is looking really good, I'm looking forward to seeing them combined.
leopardpm wrote:In the folder are also the required fbsound library files which should work as long as they are in the same folder as the program - please let me know if you get errors or no sounds...

There isn't any sound library files for linux included. Also no 64 bit dll for windows. You're using Fbimage as well which you don't include anything for.
Not a complaint, just a heads up.
drats! i forgot all the different things....hmmm.... there has got to be a better way.....
I can put the 64bit windows things in there easily enough, but unsure about anything linux

ok, did that - does that work better, Boromir? There is now a subfolder with all the possible crap required for fbsound lib, multiple OSes and 32/64
still working on fbimage ones...

guess folks with linux can install fbsound the old fashioned way... through the forum library section.... plus the thread might have answers to questions that I have no clue on....

same thing with fbImage... don't know if all the needed files could just be in the same folder as the .bas file and function correctly...

such a pain in da arse....

anyways, glad you like it! I saw your game & videos on indiedb and it motivated me - I commented there as well. Its nice that our two 'games' have a lot of commonality, but we are approaching it from different aspects of gameplay... it makes it so that ideas either one of us have can pretty easily be used by the other if they desire.... This first GOAP program will end up with agents that are still 'directed' in the same manner that you direct yours, so just a different way of doing it... I assume you are basically using FSMs and having the Agents be in different 'states' like wood chopping, or building, etc... they might even be assigned 'roles' like 'wood chopper' et al.... which will show the alternative way compared to the way I am showing... its a good comparison I think!!! Your project looks like it is coming along nicely as well!
Boromir
Posts: 451
Joined: Apr 30, 2015 19:28
Location: Texas,U.S., Earth,Solar System
Contact:

Re: GOAP: A Basic AI Tutorial

Postby Boromir » Jan 02, 2019 21:28

leopardpm wrote:ok, did that - does that work better, Boromir? There is now a subfolder with all the possible crap required for fbsound lib, multiple OSes and 32/64
still working on fbimage ones...

I had a copy of fbimage on my pc I just got the linux files from there. The included fbsound files work.
I've been using the sdl_mixer for sound in the past. I didn't realize fbsound supported 64 bit. I'll have to switch. :)

It's been a while since I've worked on the Eric RTS. I want to get back to it eventually but I have a lot of smaller side projects right now including my entry for the contest.
Multiplayer 3d ascii RTS game
Image
leopardpm
Posts: 1795
Joined: Feb 28, 2009 20:58

Re: GOAP: A Basic AI Tutorial

Postby leopardpm » Jan 02, 2019 21:51

Multiplayer 3d ascii RTS game
Really? Multiplayer LAN or through the internet? Thats exciting! I also would like to eventually include multi-player (LAN and internet), but that is far from top-priority at the moment

Why ASCII? Doesn't seem any 'easier' to implement over a graphical game....

Can't wait to play you on your game!!! ...and I will be looking out for your cheat codes.....

Code: Select all

if player.name = "boromir" then BoromirsGold +=100000
Boromir
Posts: 451
Joined: Apr 30, 2015 19:28
Location: Texas,U.S., Earth,Solar System
Contact:

Re: GOAP: A Basic AI Tutorial

Postby Boromir » Jan 02, 2019 22:01

leopardpm wrote:Really? Multiplayer LAN or through the internet? Thats exciting! I also would like to eventually include multi-player (LAN and internet), but that is far from top-priority at the moment

Why ASCII? Doesn't seem any 'easier' to implement over a graphical game....

It's both internet or lan. Even a combination. I haven't tested how many clients can play in one game. I guess that would depend on how good of a pc the server is running on.
I used ascii to force myself to focus on the gameplay over the graphics. I still got a bit carried away though.

leopardpm wrote:Can't wait to play you on your game!!! ...and I will be looking out for your cheat codes.....

Code: Select all

if player.name = "boromir" then BoromirsGold +=100000
Haha! There is a little bit of client anti-cheat coded but some things would still be easy to cheat on. Person operating the server could really cheat. We just have to agree to play honorably. :)
leopardpm
Posts: 1795
Joined: Feb 28, 2009 20:58

Re: GOAP: A Basic AI Tutorial

Postby leopardpm » Jan 02, 2019 22:17

That's really cool - I can't wait to check out your networking code

I totally understand about the graphics being distracting to the main thrust of coding... but they are sooo 'immediate gratification'... same with sounds, as I found out last night. I really am avoiding doing the grunt work on hooking in the GOAP planner to the graphical world... my goal is to do it today... cuz I work out of town next few days...

Return to “Game Dev”

Who is online

Users browsing this forum: No registered users and 3 guests