Author Topic: A* Star and Min Heap Help  (Read 471 times)

0 Members and 1 Guest are viewing this topic.

Offline Ki1o

  • LV4 Regular (Next: 200)
  • ****
  • Posts: 111
  • Rating: +5/-2
  • Doing my best...
    • View Profile
A* Star and Min Heap Help
« on: July 10, 2022, 10:55:38 am »
I've been trying to implement an A* Star algorithm in Axe, but I've been encountering a whole host of bugs or things I can't explain. I need help so I'm hoping that @E37 reads this. It is in this code where I also get a few appvar bugs. Here is the whole AI code so far.
Code: [Select]
..AI
L2+00->->^^oDistMap
L2+02->->^^oTargetX
L2+04->->^^oTargetY
L2+06->->^^oStartX
L2+08->->^^oStartY
L2+10->->^^oCurrX
L2+12->->^^oCurrY
L2+14->->^^oHCost
L2+16->->^^oGCost
L2+18->->^^oSize
L2+20->->^^oMinIndex
L2+22->->^^oRoot
L2+24->->^^oRIndex
L2+26->->^^oMinHeap
Data(~1,1,~36,36)->^^oAIDir
Goto AIEND
Lbl DoMobAI
DrawGame()
For(M,0,Mobs-1)
^^oMobArray+(M*4)->Mob
CalculatePath(NewX,NewY,{^^oMobX+Mob},{^^oMobY+Mob})
End
Return
Lbl CalculatePath
GetCalc("appvDISTMAP")->DistMap
Fill(^^oTargetX,400,0)
~3->Size
Fill(DistMap,1296,|EFF)
[r1]->TargetX
[r2]->TargetY
[r3]->StartX
[r4]->StartY
Ge\tDistance(TargetX,TargetY,StartX,StartY)->HCost
GCost->{(TargetY-6)*36+(TargetX-6)+DistMap}
Insert(TargetX,TargetY)
While 1
Extract()->A
GCost++
0->J
For(4)
A+sign{^^oDir+J}->T
T^48->CurrX
T/48->CurrY
(CurrY-6)*36+(CurrX-6)->C
If ({T+Floor}<2)?({C+DistMap}=|EFF)
Ge\tDistance(CurrX,CurrY,StartX,StartY)->HCost
Insert(CurrX,CurrY)
GCost->{C+DistMap}
End
J++
End
EndIf ((CurrX=StartX)?(CurrY=StartY))
Return
Lbl Parent
Return ([r1]-3)/6
Lbl LeftChild
Return (6*[r1])+3
Lbl RightChild
Return (6*[r1])+6
Lbl ShiftUp
While ([r1]>>0)?({^^oMinHeap+Parent([r1])}>{^^oMinHeap+[r1]})
Swap(Parent([r1]),[r1])
Parent([r1])->[r1]
End
Return
Lbl ShiftDown
While 1
LeftChild([r1])->MinIndex+3->RIndex
If RIndex<<Size
If {^^oMinHeap+RIndex}<{^^oMinHeap+MinIndex}
RIndex->MinIndex
End
End
Swap([r1],MinIndex)
MinIndex->[r1]
EndIf (Size<<MinIndex)?({^^oMinHeap+MinIndex}>={^^oMinHeap+[r1]})
Return
Lbl Swap
{^^oMinHeap+[r1]}->[r3]
{^^oMinHeap+[r1]+1}^^r->[r4]
{^^oMinHeap+[r2]}->{^^oMinHeap+[r1]}
{^^oMinHeap+[r2]+1}^^r->{^^oMinHeap+[r1]+1}^^r
[r3]->{^^oMinHeap+[r2]}
[r4]->{^^oMinHeap+[r2]+1}^^r
Return
Lbl Insert
GCost+HCost->[r3]
([r2]*^^oFloorWidth+[r1])->{[r3]->{Size+3->Size+^^oMinHeap}+1}^^r
ShiftUp(Size)
Return
Lbl Extract
{^^oMinHeap+1}^^r->Root
{^^oMinHeap+Size}->{^^oMinHeap}
{^^oMinHeap+Size+1}^^r->{^^oMinHeap+1}^^r
Size-3->Size
ShiftDown(0)
Return Root
Lbl Ge\tDistance
abs([r1]-[r3])+abs([r2]-[r4])
Return
Lbl AIEND
First off, the appvar bugs that I have been getting. I am declaring the point for the DISTMAP appvar at the same time as the FLOOR appvar like so:
Code: [Select]
GetCalc("appvFLOOR",2304)->Floor
GetCalc("appvDISTMAP",1296)->DistMap
I'm only editing the floor appvar. I do not resize this in any way. If I do not call
Code: [Select]
GetCalc("appvDISTMAP")->DistMap again in CalculatePath(), then nothing will happen and the appvar doesn't get modified even though it exists. If I create the appvar in the AI code, then the pointers for the floor and the distmap somehow get mixed up and random garbage is scrolled in on the screen. The same thing happens if the distmap appvar already exists when I run the main program. However this only occurs for the distmap appvar as the floor appvar never has this issue. Also calling
Code: [Select]
DelVar "appvDISTMAP" does nothing. Not sure how this works. Please explain appvars to me like I'm 5 because something is not making sense.
Another bug I experience is using custom named variables to hold function labels. If that's not something that's possible please let me know. I know custom variables are 2 bytes and I am making sure of that so I don't know what is going on there. It only works with Alpha variables.
Back to the MinHeap, my ShiftUp function seems to do nothing. I don't know where the logic is failing. Each entry in the MinHeap is 3 bytes. The first byte is the F Cost of a given tile and the 2 bytes after that are the tile's offset. I'm trying to sort by F Cost, so that the lowest F Cost is the root of the MinHeap. Is the problem with my ShiftUp function or the Swap function? Please help! Thanks  :banghead:

Offline E37

  • LV6 Super Member (Next: 500)
  • ******
  • Posts: 329
  • Rating: +21/-0
  • Trial and error is the best teacher
    • View Profile
Re: A* Star and Min Heap Help
« Reply #1 on: July 10, 2022, 11:20:38 am »
You are calling DelVar correctly. If nothing is happening, then either it doesn't exist or you have memory corruption going on. And since I assume that it exists for you to know the deletion doesn't work it may be memory corruption.

As for your GetCalc issues, try displaying the value it returns when you first create it and when you have to call it again a second time. They should be the same. If they differ, something you are doing is moving memory around and there isn't anything you can do besides call GetCalc again a second time like you do.

As for custom variables holding variables to hold function labels, that is perfectly fine.
Code: [Select]
:L Label->Variable .Store the address of the function to the 2-byte variable Variable
:(Variable)(1, 2) .Call the function pointed to by Variable, passing 1, 2 as arguments. No arguments is valid
:(L Label)() .The same as doing :Label()
The L followed by the space is the little uppercase L used for getting the address of a label. I can't put subscripts in code. It should be LLabel

I don't have my calculator on me at the moment as I left it at work. I will bring it back with me on Monday and check out your A* bug then. What is your shift functions supposed to do? It looks like you are placing a node in a sorted list. Is that correct?
I'm still around... kind of.

Offline Ki1o

  • LV4 Regular (Next: 200)
  • ****
  • Posts: 111
  • Rating: +5/-2
  • Doing my best...
    • View Profile
Re: A* Star and Min Heap Help
« Reply #2 on: July 10, 2022, 11:28:53 am »
Yes that is correct. Not sure if the While loop condition is the problem or the Swap function.

Offline Xeda112358

  • they/them
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4704
  • Rating: +719/-6
  • Calc-u-lator, do doo doo do do do.
    • View Profile
Re: A* Star and Min Heap Help
« Reply #3 on: July 10, 2022, 03:28:33 pm »
So this isn't exactly what you need, but here is an example program I worked on that implements pushing to and popping from a heap. In this example, I push 30 random values and then pop them off, storing the scores to an array at oMINHEAP+128, resulting in a sorted list.

You'll want to change how the "score" is calculated, as well as the 2-byte "value" associated with it in Lbl PUSH. Otherwise, you should be able to PUSH() and POP() as expected :)

Code: [Select]
.HEAP
L1+18->->^^oHEAPSIZE
L1+20->->^^oPARENT
L1+22->->^^oLCHILD
L1+22->->^^oCHILD  //Alias
L1+24->->^^oRCHILD
L1+26->->^^oSCORE
L1+28->->^^oVALUE
L1+30->->^^oMINHEAP

0->HEAPSIZE

For(30)
    PUSH(rand^16,rand^16)
End

^^oMINHEAP+127->Z
While HEAPSIZE
    POP()
    SCORE->{Z++}
End
Return

Lbl PUSH
    HEAPSIZE*3+^^oMINHEAP->A
    [r1]+[r2]->{A}
    [r1]->{A++}
    [r2]->{A++}
    HEAPSIZE++
    PROPUP(HEAPSIZE-1)
Return

Lbl POP
    Return!If HEAPSIZE
    //We'll return the root node
    {^^oMINHEAP}->SCORE
    {^^oMINHEAP+1}^^r->VALUE
    HEAPSIZE--
    Return!If HEAPSIZE

    // Backup the parent's data
    HEAPSIZE*3->P
    {^^oMINHEAP+P}->S
    {^^oMINHEAP+P+1}^^r->V

    //Call the POP subroutine
    POPS()

    //Write the parent's data
    S->{^^oMINHEAP+P}
    V->{^^oMINHEAP+P+1}^^r
    Return

Lbl POPS
    0->PARENT->P
    //Now loop until this parent is smaller than the children
    While 1
        PARENT*2+1->LCHILD+1->RCHILD
        ReturnIf LCHILD>=HEAPSIZE
        LCHILD*3->L
        If RCHILD<HEAPSIZE
            L+3->R
            If {^^oMINHEAP+R}<{^^oMINHEAP+L}
                R->L
                RCHILD->LCHILD
            End
        End

        ReturnIf {^^oMINHEAP+L}>=S
        {^^oMINHEAP+L}->{^^oMINHEAP+P}
        {^^oMINHEAP+L+1}^^r->{^^oMINHEAP+P+1}^^r
        LCHILD->PARENT
        L->P
    End
    Return

//This propagates an element up the heap
Lbl PROPUP
    [r1]->CHILD*3->C
    //If the child is at the root, it can't go up further.
    Return!If CHILD

    //Calculate the parent node
    CHILD-1/2->PARENT*3->P

    //Back up the child's score
    {^^oMINHEAP+C}->SCORE

    //If the parent is smaller, exit
    ReturnIf SCORE>={^^oMINHEAP+P}

    //back up the score of the child
    {^^oMINHEAP+C+1}^^r->VALUE

    //Call the prop-up subroutine
    PROPUS()

    //Finally, write the score and value to the child's new index
    SCORE->{^^oMINHEAP+C}
    VALUE->{^^oMINHEAP+C+1}^^r
Return

Lbl PROPUS
    While 1
        //Move the parent down
        {^^oMINHEAP+P}->{^^oMINHEAP+C}
        {^^oMINHEAP+P+1}^^r->{^^oMINHEAP+C+1}^^r
        //Child is now the parent
        PARENT->CHILD
        P->C
        //Exit if we are at the root
        Return!If CHILD
        //calculate next parent
        CHILD-1/2->PARENT*3->P

        //Exit if the new parent's score is smaller than the child's
        ReturnIf SCORE>={^^oMINHEAP+P}
    End

Offline E37

  • LV6 Super Member (Next: 500)
  • ******
  • Posts: 329
  • Rating: +21/-0
  • Trial and error is the best teacher
    • View Profile
Re: A* Star and Min Heap Help
« Reply #4 on: July 11, 2022, 09:44:57 pm »
I took a long look through your code and couldn't really figure out how your shifting code was supposed to work. Are you trying to work around Axe's lack of a working backwards copy? It looks to me like you are pushing a node to the end of the stack and then bubble-sorting it down to its proper place. If so, it would be way easier to find the correct place to put the node, and use a backwards copy (Asm or Axe loop) to shift all the other nodes up to make room.

Here is the code I used to push a node onto the open stack for my A* implementation:
Code: [Select]
:.N2X, N2Y are the x and y of the new node.
:.N2VAL is the calculated weight of the node. Each node is 6 bytes
:
:Pxl-On(N2X, N2Y, oGB7) .I set pixels for each tile so I don't create duplicate nodes. Since my map is 64x64, drawing commands work perfectly
:Select(Open, *6+oOpenS->X) .Open holds the number of nodes on the open stack, X will now hold the pointer to the end of the stack
:If
:For()
:    {X-6}r >= N2VAL                 .Loop backwards until we come across a node that has more weight than the one about to be inserted
:    ? Asm(C1C3(L PushNext))    .If true, pop BC and goto PushNext (pop BC lets me use goto in this type of For loop. Axe won't let me use a goto in the loop so I wrote it in asm instead
:    .Once push next has been called, the function will never return here
:    .The only reason PushNext isn't in the loop is the fall-through case of the new node being the last one or an empty stack
:    X-6->X
:End
:
:.Pass through to the copy if no spot has been found
:
:Lbl PushNext   .This just sets up a backwards copy (lddr). DE, HL, BC are the same arguments (in the same order) as Axe's copy but it starts at the end and works backward
:
:Open++*6+OpenS    .Increment the count of nodes on the stack. Get the pointer to the end in HL
:Asm(E5) .push HL (will be popped as DE)
:-6 .Move 6 bytes back because we are shifting 6 bytes up
:Asm(E5) .push HL (will be popped as HL)
:+6-X .Get the total amount of bytes to move
:Asm(E5) .push HL (will be popped as BC)
:Asm(C1E1D178B12802EDB8) .Pop BC, HL, DE and copy
:
:.Copy the 6 byte node to the area pointed to by X now that everything above has been shifted up 6 bytes
:Copy(oN2VAL, X, 6) .I'm not really sure why I used copy for only 6 bytes. Maybe it was more efficient or something
:Return

While that code is very heavily optimized, a simpler version using the same logic shouldn't be too hard to implement.

Most of my Axe code isn't anywhere that nasty but I really needed a fast pathfind.
I'm still around... kind of.