Priority queue in Developer Help

ID:142644
 
Apr 9 2008, 5:35 pm (Edited on Apr 9 2008, 9:24 pm)
Code:
// NOTE EVERYTHING WORKS EXCEPT THE LINE NOTED, SEE BELOW...
prioqueue
    var
        value
        item
        prioqueue/next
    New()
        world << "New prioqueue"
        value=999999999
        item=null
        next=null
        return src
    Del()
        if(next==null)
            world << "del terminator"
            ..()
        else
            del next
            world << "del [item]=[value]"
            ..()
        return
    proc
        insert(newvalue,newitem)
            if(newvalue>=value)
                if(item==newitem)
                    return
                else
                    next.insert(newvalue,newitem)
            else
                var/prioqueue/p=new()
                p.value=value; p.item=item; p.next=next
                value=newvalue; item=newitem; next=p
            return
        remfirst()
            world << "remfirst creating returnval"
            var/prioqueue/returnval=new()
            world << "inserting 1st item to returnval"
            returnval.insert(value,item)
            world << "returnval=[returnval.totext()]  src=[totext()]"
            world << "setting src=next"
            src=next // <<<<<*********** PROBLEM IS HERE
            world << "returning returnval=[returnval.totext()]  src=[totext()]"
            return returnval
        totext()
            if(next==null) return ""
            return "[item]=[value] [next.totext()]"

mob
    verb
        testqueue()
            var/prioqueue/P=new()
            world << "newed P=[P.totext()]"
            P.insert(10,"A")
            world << "inserted A, P=[P.totext()]"
            P.insert(20,"B")
            world << "inserted B, P=[P.totext()]"
            world << "creating Q to get 1st item"
            var/prioqueue/Q=new()
            world << "calling Q=P.remfirst()"
            Q = P.remfirst()
            world << "final result Q=[Q.totext()]  P=[P.totext()]"


Problem description:
In remfirst(), I want it to return the 1st node, then set the queue to the next node. src=next appears to set the queue to the next node, but after returning it didn't really do anything.

Here's the output:
New prioqueue
newed P=
New prioqueue
inserted A, P=A=10
New prioqueue
inserted B, P=A=10 B=20
creating Q to get 1st item
New prioqueue
calling Q=P.remfirst()
remfirst creating returnval
New prioqueue
inserting 1st item to returnval
New prioqueue
returnval=A=10 src=A=10 B=20
setting temp=src
setting src=next
returning returnval=A=10 src=B=20
del terminator
final result Q=A=10 P=A=10 B=20
del terminator
del A=10
del terminator
del B=20
del A=10

#1 Apr 9 2008, 5:37 pm
Oh yeah, using version 412.977 if that matters.
#2 Apr 9 2008, 7:04 pm
In response to Traztx (#1)
From what I can tell, it looks like its producing the same thing over and over because you keep setting src to next. Unless each of the prioqueue objs that are created get deleted after it goes through the processing, that obj will always be there, it will continue to be src, and it will return the same value over and over.

I may be wrong, but that's what I see happening here.
#3 Apr 9 2008, 9:21 pm
In response to Pyro_dragons (#2)
I don't know what you mean by "over and over" since src=next is only happening once.

It's as if changing src only changes a local version of it, but if I try ..src=next I get an error.

So I figured out a different way to do it. Set a temporary queue to next, then copy the item, value and next of it to src, then terminate temp.

So now everything is working perfectly and here is the version that works:
        remfirst()
            var/prioqueue/returnval=new()
            var/prioqueue/temp
            returnval.insert(value,item)
            temp=next
            value=temp.value ; item=temp.item; next=temp.next
            temp.next=null
            return returnval


Also I took out the new() where the caller was setting up Q, which was superfluous. It get's del'd when remfirst returns and it is replaced with the returned prioqueue.

Now, I can turn my attention to A* =)
#4 Apr 9 2008, 9:29 pm
In response to Traztx (#3)
Traztx wrote:
I don't know what you mean by "over and over" since src=next is only happening once.

It's as if changing src only changes a local version of it, but if I try ..src=next I get an error.

Yep, src is really just a local var that points to the owner of the proc. If you set src to a new value, it will only have meaning for the duration of that proc. The caller's src won't be updated at all.

Now, I can turn my attention to A* =)

I'm using A* in SotS II with pretty good results. I have two different implementations working, both of which use a heap sort to sort the open and closed nodes. The Stickster basically keeps trying to find a path to any target, and will start moving toward them, whereas the NPC AI just calculates out to a certain distance and will allow its pather to venture only into charted territory. I may eventually move the Stickster onto a much shorter pathfinding algorithm just to improve his results.

From my own experience, the most intensive of A* seems to be sorting and retrieving the open and closed nodes. Your mileage may vary.

Lummox JR
#5 Apr 9 2008, 9:51 pm
In response to Lummox JR (#4)
Thanks. That explains it.

Yes I agree queue mainenance is the bulk of A* processing. This priority queue method avoids sorting by always inserting in order, but doing it as a simple linked list would not be as efficient to access as something like a balanced b+ tree. Right now I'm just trying to get some functionality going. I can always swap out methods with more efficient versions.

Since the Stickster is looking for any target, I'm guessing you simplify the heuristics to just 0 and terminate the search when you reach the 1st target. Am I guessing right?

And kudos to Byond's clean-up. I noticed automatic calls to del that I wasn't expecting.