Calculator Community > Axe

A* Star and Min Heap Help

(1/1)

**Ki1o**:

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: ---..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

--- End code ---

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: ---GetCalc("appvFLOOR",2304)->Floor

GetCalc("appvDISTMAP",1296)->DistMap

--- End code ---

I'm only editing the floor appvar. I do not resize this in any way. If I do not call

--- Code: ---GetCalc("appvDISTMAP")->DistMap

--- End code ---

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: ---DelVar "appvDISTMAP"

--- End code ---

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:

**E37**:

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: ---: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()

--- End code ---

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?

**Ki1o**:

Yes that is correct. Not sure if the While loop condition is the problem or the Swap function.

**Xeda112358**:

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: ---.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

--- End code ---

**E37**:

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: ---:.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

--- End code ---

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.

Navigation

[0] Message Index

Go to full version