Problems with A* Path Finding - GameCreators Forum

Author

Message

Ched80

13

Years of Service

User Offline

Joined: 18th Sep 2010

Location: Peterborough, UK

Posted: 27th Oct 2013 11:41

Link

Hi all,

I've been trying to add some A* path finding to my game, but I just can't seem to get my code to play fair with me.

I'm using Tier 1 with v108B19.

The problem I'm seeing is that when it is searching for the next target square with the lowest F value on the open list is only ever finds x=2 and y=2 - even though the array value for this square is open=0!!

Any help with this would be wonderful.

Here's my code:

function NewAIPath(PlayerID as integer)
    //fins best route to mothernode

startx = trunc((player[PlayerID].PositionX+32)/64)
    starty = trunc((player[PlayerID].PositionY+32)/64)

if (player[PlayerID].activestate=0 and player[PlayerID].InNodeZone=0) or (StorageArea[startx,starty].gason>0 and player[PlayerID].GasMask<1)
        if player[PlayerID].ThinkCounter<=0

//set end tile
            select PlayerID
                case 0
                    targetx = areamaxx/2
                    targety = areamaxy/2
                endcase

case 1
                    targetx = (areamaxx/2)+1
                    targety = (areamaxy/2)+1
                endcase

case 2
                    targetx = (areamaxx/2)
                    targety = (areamaxy/2)+1
                endcase

case 3
                    targetx = (areamaxx/2)+1
                    targety = (areamaxy/2)
                endcase
            endselect
            //end tile set

//reset old AI Path & fill H values
            for tempx=2 to areamaxx
                for tempy=2 to areamaxy
                    AIPath[PlayerID,tempx,tempy].Closed = 0
                    AIPath[PlayerID,tempx,tempy].Fval = 0
                    AIPath[PlayerID,tempx,tempy].Gval = 0
                    AIPath[PlayerID,tempx,tempy].Hval = 10 * trunc(abs(tempx-startx)+abs(tempy-starty))
                    AIPath[PlayerID,tempx,tempy].Open = 0
                    AIPath[PlayerID,tempx,tempy].ParentX = 0
                    AIPath[PlayerID,tempx,tempy].ParentY = 0
                next tempy
            next tempx
            //reset complete

//add starting position to open list
            AIPath[PlayerID,targetx,targety].Open = 1

//find path
            PathComplete = 0
            LowestFVal = 1000000
            while PathComplete=0
                //find lowest open F value
                for tempx=2 to areamaxx
                    for tempy=2 to areamaxy
                        if AIPath[PlayerID,tempx,tempy].Open=1
                            if AIPath[PlayerID,tempx,tempy].FVal<LowestFVal
                                LowestFVal = AIPath[PlayerID,tempx,tempy].FVal
                                currentx = tempx
                                currenty = tempy
                            endif
                        endif
                    next tempy
                next tempx
                //new target found

print("Next Target X:"+str(currentx)+", Y:"+str(currenty)+", Lowest F:"+str(LowestFVal))
                sync()

AIPath[PlayerID,currentx,currenty].Open = 0
                AIPath[PlayerID,currentx,currenty].Closed = 0

//calculate adjacent squares
                for adjacent=0 to 3

//set next adjacent coordinates
                    select adjacent
                        case 0
                            adjx = currentx-1
                            adjy = currenty
                        endcase

case 1
                            adjx = currentx+1
                            adjy = currenty
                        endcase

case 0
                            adjx = currentx
                            adjy = currenty-1
                        endcase

case 0
                            adjx = currentx
                            adjy = currenty+1
                        endcase
                    endselect

//only calculate walkable squares
                    if adjx>1 and adjx<areamaxx
                        if adjy>1 and adjy<areamaxy
                            //squarea is within range
                            if AIPath[PlayerID,adjx,adjy].Closed=0
                                //square isn't closed

//add to open list
                                if AIPath[PlayerID,adjx,adjy].Open=0
                                    AIPath[PlayerID,adjx,adjy].Open = 1

//set parents
                                    AIPath[PlayerID,adjx,adjy].ParentX = currentx
                                    AIPath[PlayerID,adjx,adjy].ParentY = currenty

//Movement Costs
                                    AIPath[PlayerID,adjx,adjy].Gval = 10 + AIPath[PlayerID,currentx,currenty].Gval

//Final Scoring
                                    AIPath[PlayerID,adjx,adjy].Fval = AIPath[PlayerID,adjx,adjy].Gval + AIPath[PlayerID,adjx,adjy].Gval
                                else
                                    //already open
                                    NewGval = 10 + AIPath[PlayerID,currentx,currenty].Gval

if NewGval < AIPath[PlayerID,adjx,adjy].Gval
                                        //better path

//reassign parents
                                        AIPath[PlayerID,adjx,adjy].ParentX = currentx
                                        AIPath[PlayerID,adjx,adjy].ParentY = currenty

//New G
                                        AIPath[PlayerID,adjx,adjy].Gval = NewGval

//New F
                                        AIPath[PlayerID,adjx,adjy].Fval = AIPath[PlayerID,adjx,adjy].Gval + AIPath[PlayerID,adjx,adjy].Gval
                                    endif
                                endif

//check for destination
                                if adjx=startx and adjy=starty then PathComplete = 1
                            endif
                        endif
                    endif

next adjacent
                //adjacent squares calculated

endwhile
            //path found

if PathComplete=1
                Player[PlayerID].TargetX = AIPath[PlayerID,startx,starty].parentx*64.0
                Player[PlayerID].TargetY = AIPath[PlayerID,startx,starty].parentx*64.0
            endif

player[PlayerID].ThinkCounter = random(500,1000)
        else
            //reduce thinking time
            player[PlayerID].ThinkCounter = player[PlayerID].ThinkCounter-(getframetime()*1000)
        endif
    endif

endfunction

+ Code Snippet

function NewAIPath(PlayerID as integer)
    //fins best route to mothernode

    startx = trunc((player[PlayerID].PositionX+32)/64)
    starty = trunc((player[PlayerID].PositionY+32)/64)

    if (player[PlayerID].activestate=0 and player[PlayerID].InNodeZone=0) or (StorageArea[startx,starty].gason>0 and player[PlayerID].GasMask<1)
        if player[PlayerID].ThinkCounter<=0

            //set end tile
            select PlayerID
                case 0
                    targetx = areamaxx/2
                    targety = areamaxy/2
                endcase

                case 1
                    targetx = (areamaxx/2)+1
                    targety = (areamaxy/2)+1
                endcase

                case 2
                    targetx = (areamaxx/2)
                    targety = (areamaxy/2)+1
                endcase

                case 3
                    targetx = (areamaxx/2)+1
                    targety = (areamaxy/2)
                endcase
            endselect
            //end tile set

            //reset old AI Path & fill H values
            for tempx=2 to areamaxx
                for tempy=2 to areamaxy
                    AIPath[PlayerID,tempx,tempy].Closed = 0
                    AIPath[PlayerID,tempx,tempy].Fval = 0
                    AIPath[PlayerID,tempx,tempy].Gval = 0
                    AIPath[PlayerID,tempx,tempy].Hval = 10 * trunc(abs(tempx-startx)+abs(tempy-starty))
                    AIPath[PlayerID,tempx,tempy].Open = 0
                    AIPath[PlayerID,tempx,tempy].ParentX = 0
                    AIPath[PlayerID,tempx,tempy].ParentY = 0
                next tempy
            next tempx
            //reset complete

            //add starting position to open list
            AIPath[PlayerID,targetx,targety].Open = 1

            //find path
            PathComplete = 0
            LowestFVal = 1000000
            while PathComplete=0
                //find lowest open F value
                for tempx=2 to areamaxx
                    for tempy=2 to areamaxy
                        if AIPath[PlayerID,tempx,tempy].Open=1
                            if AIPath[PlayerID,tempx,tempy].FVal<LowestFVal
                                LowestFVal = AIPath[PlayerID,tempx,tempy].FVal
                                currentx = tempx
                                currenty = tempy
                            endif
                        endif
                    next tempy
                next tempx
                //new target found

                print("Next Target X:"+str(currentx)+", Y:"+str(currenty)+", Lowest F:"+str(LowestFVal))
                sync()

                AIPath[PlayerID,currentx,currenty].Open = 0
                AIPath[PlayerID,currentx,currenty].Closed = 0

                //calculate adjacent squares
                for adjacent=0 to 3

                    //set next adjacent coordinates
                    select adjacent
                        case 0
                            adjx = currentx-1
                            adjy = currenty
                        endcase

                        case 1
                            adjx = currentx+1
                            adjy = currenty
                        endcase

                        case 0
                            adjx = currentx
                            adjy = currenty-1
                        endcase

                        case 0
                            adjx = currentx
                            adjy = currenty+1
                        endcase
                    endselect

                    //only calculate walkable squares
                    if adjx>1 and adjx<areamaxx
                        if adjy>1 and adjy<areamaxy
                            //squarea is within range
                            if AIPath[PlayerID,adjx,adjy].Closed=0
                                //square isn't closed

                                //add to open list
                                if AIPath[PlayerID,adjx,adjy].Open=0
                                    AIPath[PlayerID,adjx,adjy].Open = 1

                                    //set parents
                                    AIPath[PlayerID,adjx,adjy].ParentX = currentx
                                    AIPath[PlayerID,adjx,adjy].ParentY = currenty

                                    //Movement Costs
                                    AIPath[PlayerID,adjx,adjy].Gval = 10 + AIPath[PlayerID,currentx,currenty].Gval

                                    //Final Scoring
                                    AIPath[PlayerID,adjx,adjy].Fval = AIPath[PlayerID,adjx,adjy].Gval + AIPath[PlayerID,adjx,adjy].Gval
                                else
                                    //already open
                                    NewGval = 10 + AIPath[PlayerID,currentx,currenty].Gval

                                    if NewGval < AIPath[PlayerID,adjx,adjy].Gval
                                        //better path

                                        //reassign parents
                                        AIPath[PlayerID,adjx,adjy].ParentX = currentx
                                        AIPath[PlayerID,adjx,adjy].ParentY = currenty

                                        //New G
                                        AIPath[PlayerID,adjx,adjy].Gval = NewGval

                                        //New F
                                        AIPath[PlayerID,adjx,adjy].Fval = AIPath[PlayerID,adjx,adjy].Gval + AIPath[PlayerID,adjx,adjy].Gval
                                    endif
                                endif

                                //check for destination
                                if adjx=startx and adjy=starty then PathComplete = 1
                            endif
                        endif
                    endif

                next adjacent
                //adjacent squares calculated

            endwhile
            //path found

            if PathComplete=1
                Player[PlayerID].TargetX = AIPath[PlayerID,startx,starty].parentx*64.0
                Player[PlayerID].TargetY = AIPath[PlayerID,startx,starty].parentx*64.0
            endif

            player[PlayerID].ThinkCounter = random(500,1000)
        else
            //reduce thinking time
            player[PlayerID].ThinkCounter = player[PlayerID].ThinkCounter-(getframetime()*1000)
        endif
    endif

endfunction

Back to top

Profile PM Email

Ched80

13

Years of Service

User Offline

Joined: 18th Sep 2010

Location: Peterborough, UK

Posted: 27th Oct 2013 12:16

Link

Okay this is really weird.

I added some debugging bits to try and find out why my code won't work.

So I have a small loop that resets my Path array to zero like so:

Quote: "//reset old AI Path & fill H values
for tempx=2 to areamaxx
for tempy=2 to areamaxy
AIPath[PlayerID,tempx,tempy].Closed = 0
AIPath[PlayerID,tempx,tempy].Fval = 0
AIPath[PlayerID,tempx,tempy].Gval = 0
AIPath[PlayerID,tempx,tempy].Hval = 10 * trunc(abs(tempx-targetx)+abs(tempy-targety))
AIPath[PlayerID,tempx,tempy].Open = 0
AIPath[PlayerID,tempx,tempy].ParentX = 0
AIPath[PlayerID,tempx,tempy].ParentY = 0

repeat
print("Next Target X:"+str(tempx)+", Y:"+str(tempy)+", Open:"+str(AIPath[PlayerID,tempx,tempy].Open)+", Lowest F:"+str(AIPath[PlayerID,tempx,tempy].FVal))
sync()
until getrawkeyreleased(13)=1
next tempy
next tempx
//reset complete"

You can see I added in a break so that I could check that te .Open part of the array was set to zero.

Then I change ONE value in the array

Quote: "//add starting position to open list
AIPath[PlayerID,startx,starty].Open = 1

repeat
print("Next Target X:"+str(startx)+", Y:"+str(starty)+", Open:"+str(AIPath[PlayerID,startx,starty].Open)+", Lowest F:"+str(AIPath[PlayerID,startx,starty].FVal))
sync()
until getrawkeyreleased(13)=1"

As you can see I added another break to confirm the element had changed to .Open=1

I then checked to see which element in the array had actually changed:

Quote: "for tempx=2 to areamaxx
for tempy=2 to areamaxy
if AIPath[PlayerID,tempx,tempy].Open>0
repeat
print("ERROR X:"+str(tempx)+", Y:"+str(tempy)+", Open:"+str(AIPath[PlayerID,tempx,tempy].Open))
sync()
until getrawkeyreleased(13)=1
endif
next tempy
next tempx"

To my suprise every .Open element in the array had changed to .Open=1 !!!!!

Is this a known bug in 109? Why would setting element make them all change?

I don't have problems with my other UDTs in the game, only this one.

Here's the full sequence:

//reset old AI Path & fill H values
            for tempx=2 to areamaxx
                for tempy=2 to areamaxy
                    AIPath[PlayerID,tempx,tempy].Closed = 0
                    AIPath[PlayerID,tempx,tempy].Fval = 0
                    AIPath[PlayerID,tempx,tempy].Gval = 0
                    AIPath[PlayerID,tempx,tempy].Hval = 10 * trunc(abs(tempx-targetx)+abs(tempy-targety))
                    AIPath[PlayerID,tempx,tempy].Open = 0
                    AIPath[PlayerID,tempx,tempy].ParentX = 0
                    AIPath[PlayerID,tempx,tempy].ParentY = 0
                    //repeat
                        //print("Next Target X:"+str(tempx)+", Y:"+str(tempy)+", Open:"+str(AIPath[PlayerID,tempx,tempy].Open)+", Lowest F:"+str(AIPath[PlayerID,tempx,tempy].FVal))
                        //sync()
                    //until getrawkeyreleased(13)=1
                next tempy
            next tempx
            //reset complete

//add starting position to open list
            AIPath[PlayerID,startx,starty].Open = 1

repeat
                print("Next Target X:"+str(startx)+", Y:"+str(starty)+", Open:"+str(AIPath[PlayerID,startx,starty].Open)+", Lowest F:"+str(AIPath[PlayerID,startx,starty].FVal))
                sync()
            until getrawkeyreleased(13)=1

for tempx=2 to areamaxx
                for tempy=2 to areamaxy
                    if AIPath[PlayerID,tempx,tempy].Open>0
                        repeat
                            print("ERROR X:"+str(tempx)+", Y:"+str(tempy)+", Open:"+str(AIPath[PlayerID,tempx,tempy].Open))
                            sync()
                        until getrawkeyreleased(13)=1
                    endif
                next tempy
            next tempx

+ Code Snippet

//reset old AI Path & fill H values
            for tempx=2 to areamaxx
                for tempy=2 to areamaxy
                    AIPath[PlayerID,tempx,tempy].Closed = 0
                    AIPath[PlayerID,tempx,tempy].Fval = 0
                    AIPath[PlayerID,tempx,tempy].Gval = 0
                    AIPath[PlayerID,tempx,tempy].Hval = 10 * trunc(abs(tempx-targetx)+abs(tempy-targety))
                    AIPath[PlayerID,tempx,tempy].Open = 0
                    AIPath[PlayerID,tempx,tempy].ParentX = 0
                    AIPath[PlayerID,tempx,tempy].ParentY = 0
                    //repeat
                        //print("Next Target X:"+str(tempx)+", Y:"+str(tempy)+", Open:"+str(AIPath[PlayerID,tempx,tempy].Open)+", Lowest F:"+str(AIPath[PlayerID,tempx,tempy].FVal))
                        //sync()
                    //until getrawkeyreleased(13)=1
                next tempy
            next tempx
            //reset complete

            //add starting position to open list
            AIPath[PlayerID,startx,starty].Open = 1

            repeat
                print("Next Target X:"+str(startx)+", Y:"+str(starty)+", Open:"+str(AIPath[PlayerID,startx,starty].Open)+", Lowest F:"+str(AIPath[PlayerID,startx,starty].FVal))
                sync()
            until getrawkeyreleased(13)=1

            for tempx=2 to areamaxx
                for tempy=2 to areamaxy
                    if AIPath[PlayerID,tempx,tempy].Open>0
                        repeat
                            print("ERROR X:"+str(tempx)+", Y:"+str(tempy)+", Open:"+str(AIPath[PlayerID,tempx,tempy].Open))
                            sync()
                        until getrawkeyreleased(13)=1
                    endif
                next tempy
            next tempx

Back to top

Profile PM Email

Ancient Lady

Valued Member

20

Years of Service

User Offline

Joined: 17th Mar 2004

Location: Anchorage, Alaska, USA

Posted: 27th Oct 2013 16:51

Link

There used to be problems using UDTs in arrays, especially multi-dimensioned ones. The work around was to copy the UDT element to a variable of the same UDT type. Then do any manipulations with the variable and copy it back into the UDT array when done. Awkward, but it worked.

Can you try that and see if it works? Just for the line where you set one of the entry's .Open value to 1. If that 'fixes' the issue, than TGC might have a clue as to where to look for the problem.

Cheers,
Ancient Lady
AGK Community Tester and AppGameKit Master

Back to top

Profile PM

Ched80

13

Years of Service

User Offline

Joined: 18th Sep 2010

Location: Peterborough, UK

Posted: 28th Oct 2013 10:38

Link

Sorry AL - no joy.

I replaced this:

+ Code Snippet

//add starting position to open list
AIPath[PlayerID,startx,starty].Open = 1

with this:

+ Code Snippet

tempPath as PathType
temppath.Open = AIPath[PlayerID,startx,starty].Open +1

AIPath[PlayerID,startx,starty].Open = temppath.Open

and got the same result

Back to top

Profile PM Email

The Zoq2

14

Years of Service

User Offline

Joined: 4th Nov 2009

Location: Linköping, Sweden

Posted: 28th Oct 2013 11:03

Link

Try doing it without a type and just use a regular integer as temporary variable...

Say ONE stupid thing and it ends up as a forum signature forever. - Neuro Fuzzy

Back to top

Profile PM Email

Ched80

13

Years of Service

User Offline

Joined: 18th Sep 2010

Location: Peterborough, UK

Posted: 28th Oct 2013 11:41

Link

Just tried that Zoq2 - same effect - all .Open values change to 1.

Back to top

Profile PM Email

The Zoq2

14

Years of Service

User Offline

Joined: 4th Nov 2009

Location: Linköping, Sweden

Posted: 28th Oct 2013 11:53

Link

Quote: " all .Open values change to 1."

If I recall correctly, the issue with multidimentional arrays of types only set the values to 0 and nothing else, but that was a year ago and something might have changed...

Say ONE stupid thing and it ends up as a forum signature forever. - Neuro Fuzzy

Back to top

Profile PM Email

Ancient Lady

Valued Member

20

Years of Service

User Offline

Joined: 17th Mar 2004

Location: Anchorage, Alaska, USA

Posted: 28th Oct 2013 14:43

Link

What I meant was something more along these lines:

+ Code Snippet

tempPath as PathType
tempPath = AIPath[PlayerID,startx,starty]
tempPath.Open = 1;

AIPath[PlayerID,startx,starty] = temppath

You copy the entire UDT entry and then replace the entire UDT entry. What this is trying to avoid is making the AppGameKit engine figure out where the specific UDT element is in memory.

Cheers,
Ancient Lady
AGK Community Tester and AppGameKit Master

Back to top

Profile PM

Ched80

13

Years of Service

User Offline

Joined: 18th Sep 2010

Location: Peterborough, UK

Posted: 28th Oct 2013 16:28

Link

Ah - sorry AL I should have paid more attention

Anyway - same results with that technique too.

Is it worth me posting this in the v108 thread and the google code board?

Back to top

Profile PM Email

Ancient Lady

Valued Member

20

Years of Service

User Offline

Joined: 17th Mar 2004

Location: Anchorage, Alaska, USA

Posted: 28th Oct 2013 17:05

Link

Ched80, I am 20% into cloning my main Windows work drive (a backup long overdue). When I get back to working mode, I will see if I can duplicate the issue you are seeing. Then we can post it to the Google issue board.

Can you please show me the structure of the UDT you are using?

Cheers,
Ancient Lady
AGK Community Tester and AppGameKit Master

Back to top

Profile PM

Phaelax

DBPro Master

21

Years of Service

User Offline

Joined: 16th Apr 2003

Location: Metropia

Posted: 28th Oct 2013 17:28

Link

I don't know about your existing code, but have you looked at this thread? I already have an A* library ready for AGK.
http://forum.thegamecreators.com/?m=forum_view&t=206280&b=41

Download the library here.
http://www.zimnox.com/resources/agk/libraries/

http://zimnox.com

Back to top

Profile PM Email Website

Ched80

13

Years of Service

User Offline

Joined: 18th Sep 2010

Location: Peterborough, UK

Posted: 28th Oct 2013 18:52

Link

Cheers AL,

The UDT is defined as

type PathType
Closed as integer
Fval as integer
Gval as integer
Hval as integer
Open as integer
ParentX as integer
ParentY as integer
endtype

Phaelax, I did see that thread and I was using it as reference, but I wanted to generate my own A* pathfindnig routing - as I had to take into acount the effect of poisoned routes. Also I just liked the challenge of making the routine myself

Back to top

Profile PM Email

Ancient Lady

Valued Member

20

Years of Service

User Offline

Joined: 17th Mar 2004

Location: Anchorage, Alaska, USA

Posted: 28th Oct 2013 19:20

Link

I should be able to test something tomorrow. Thank you.

Cheers,
Ancient Lady
AGK Community Tester and AppGameKit Master

Back to top

Profile PM

Sorry your browser is not supported!

AppGameKit Classic Chat / Problems with A* Path Finding