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

0 Members and 1 Guest are viewing this topic.

#### Ki1o

• LV4 Regular (Next: 200)
• Posts: 111
• Rating: +5/-2
• Doing my best...
##### 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]
..AIL2+00->->^^oDistMapL2+02->->^^oTargetXL2+04->->^^oTargetYL2+06->->^^oStartXL2+08->->^^oStartYL2+10->->^^oCurrXL2+12->->^^oCurrYL2+14->->^^oHCostL2+16->->^^oGCostL2+18->->^^oSizeL2+20->->^^oMinIndexL2+22->->^^oRootL2+24->->^^oRIndexL2+26->->^^oMinHeapData(~1,1,~36,36)->^^oAIDirGoto AIENDLbl DoMobAIDrawGame()For(M,0,Mobs-1) ^^oMobArray+(M*4)->Mob CalculatePath(NewX,NewY,{^^oMobX+Mob},{^^oMobY+Mob})EndReturnLbl CalculatePathGetCalc("appvDISTMAP")->DistMapFill(^^oTargetX,400,0)~3->SizeFill(DistMap,1296,|EFF)[r1]->TargetX[r2]->TargetY[r3]->StartX[r4]->StartYGe\tDistance(TargetX,TargetY,StartX,StartY)->HCostGCost->{(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++ EndEndIf ((CurrX=StartX)?(CurrY=StartY))ReturnLbl ParentReturn ([r1]-3)/6Lbl LeftChildReturn (6*[r1])+3Lbl RightChildReturn (6*[r1])+6Lbl ShiftUpWhile ([r1]>>0)?({^^oMinHeap+Parent([r1])}>{^^oMinHeap+[r1]}) Swap(Parent([r1]),[r1]) Parent([r1])->[r1]EndReturnLbl ShiftDownWhile 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]})ReturnLbl 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}^^rReturnLbl InsertGCost+HCost->[r3]([r2]*^^oFloorWidth+[r1])->{[r3]->{Size+3->Size+^^oMinHeap}+1}^^rShiftUp(Size)ReturnLbl Extract{^^oMinHeap+1}^^r->Root{^^oMinHeap+Size}->{^^oMinHeap}{^^oMinHeap+Size+1}^^r->{^^oMinHeap+1}^^rSize-3->SizeShiftDown(0)Return RootLbl Ge\tDistanceabs([r1]-[r3])+abs([r2]-[r4])ReturnLbl AIENDFirst 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)->FloorGetCalc("appvDISTMAP",1296)->DistMapI'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

#### E37

• LV6 Super Member (Next: 500)
• Posts: 330
• Rating: +21/-0
• Trial and error is the best teacher
##### 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.

#### Ki1o

• LV4 Regular (Next: 200)
• Posts: 111
• Rating: +5/-2
• Doing my best...
##### 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.

#### Xeda112358

• they/them
• Moderator
• LV12 Extreme Poster (Next: 5000)
• Posts: 4704
• Rating: +719/-6
• Calc-u-lator, do doo doo do do do.
##### 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]
.HEAPL1+18->->^^oHEAPSIZEL1+20->->^^oPARENTL1+22->->^^oLCHILDL1+22->->^^oCHILD  //AliasL1+24->->^^oRCHILDL1+26->->^^oSCOREL1+28->->^^oVALUEL1+30->->^^oMINHEAP0->HEAPSIZEFor(30)    PUSH(rand^16,rand^16)End^^oMINHEAP+127->ZWhile HEAPSIZE    POP()    SCORE->{Z++}EndReturnLbl PUSH    HEAPSIZE*3+^^oMINHEAP->A    [r1]+[r2]->{A}    [r1]->{A++}    [r2]->{A++}    HEAPSIZE++    PROPUP(HEAPSIZE-1)ReturnLbl 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    ReturnLbl 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 heapLbl 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}^^rReturnLbl 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
« Last Edit: July 10, 2022, 03:54:08 pm by Xeda112358 »

#### E37

• LV6 Super Member (Next: 500)
• Posts: 330
• Rating: +21/-0
• Trial and error is the best teacher
##### 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.