0 Members and 1 Guest are viewing this topic.
..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 AIEND
GetCalc("appvFLOOR",2304)->FloorGetCalc("appvDISTMAP",1296)->DistMap
GetCalc("appvDISTMAP")->DistMap
DelVar "appvDISTMAP"
: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()
.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
:.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
Author
Topic: A* Star and Min Heap Help (Read 2667 times)
