ID:147868
 
I'm building my own implementation of the A* algorithm and I'm using a priority queue for the OpenList to make it easy to decide which node to test next.

I've got a lot of problems with my current implementation, but I figure my current main problem(that could be the source of the others) is that my priority queue loses nodes in either the Add or Remove proc. So my problem is probably some minor linking issue but it's not making itself apparent to me :P. So I'd really appreciate if someone with a familiarity of priority queues would scan through my source code to see if I made any blatant mistakes.

[Edit:] Actually the problem is probably with the removal of an item that isn't the head. Before I started the pathfinding implementation I tested the data structure with random data several times. All the data was in the structure and in the correct order. Then I used clear which properly deleted all the nodes and in the correct order. I never actually tested the removal of a random item within the structure which my pathfinding algorithm does when it finds a better way to get to a tile in the open list. I should have tested this more extensivly before trying to use it :P.

[Edit2:] Come to think of it this isn't really a priority queue since I'm removing items that aren't the head so it probably should be titled a sorted linked list as it isn't really a queue. But that's an irrellevent semantics issue I thought I'd point out.

datum
proc
CalculateValue()
return 0

PriorityQueue
var
PriorityQueueNode/head

proc
Add(newitem)
var/PriorityQueueNode/PQN = new(newitem)
var/PriorityQueueNode/prev
var/PriorityQueueNode/iter

if(!head)
head = PQN
return PQN

if(head.value > PQN.value)
PQN.nextNode = head
head = PQN
return PQN

prev = head
iter = head.nextNode
while(iter && iter.value < PQN.value)
prev = iter
iter = iter.nextNode

PQN.nextNode = iter
prev.nextNode = PQN

return PQN

Remove(item)
var/PriorityQueueNode/iter = head
var/PriorityQueueNode/prev = null
var/datum/olditem
if(head.item == item)
head = head.nextNode
olditem = iter.item
del iter
return olditem

while(iter && iter.item != item)
prev = iter
iter = iter.nextNode

if(iter)
prev.nextNode = iter.nextNode
olditem = iter.item
del iter
return olditem
return null

Clear()
while(head)
Remove(head.item)

PriorityQueueNode
var
item
value
PriorityQueueNode/nextNode

New(datum/p_item)
item = p_item
value = p_item.CalculateValue()


Note: Also if I missed some obvious optimizations please point out those too since the speed of this is vital to the overal speed of my pathfinding.
I am testing that code you have there, and the Add doesn't seem to be placing things in the right order for me. I'm not sure why at the moment though. So it does look like you might have a problem with your Add. I'll keep testing and report again after I add in some debug lines and test it a bit more fully.
In response to Loduwijk
I am testing that code you have there, and the Add doesn't seem to be placing things in the right order for me. I'm not sure why at the moment though. So it does look like you might have a problem with your Add. I'll keep testing and report again after I add in some debug lines and test it a bit more fully.

Err you need to create a more meaningful test object. The base object always returns a value of 0 so you must derive an object from it to work and override the CalculateValue() in some meaningful way rather than just returning 0 :).

Here's a better test object to use

datum/TestObj
var/value
New()
value = rand(1,100)
CalculateValue()
return value

Theodis wrote:
I'm building my own implementation of the A* algorithm and I'm using a priority queue for the OpenList to make it easy to decide which node to test next.

Man, good luck. If you find any insight into a good A* algorithm that I can use, it might vastly speed up the Stickster logic in SotS II--which relies on lists.

I have a few thoughts that have no bearing on your bug. Bugwise your code looks fine.
PriorityQueue
proc
Add(newitem)
var/PriorityQueueNode/PQN = new(newitem)
var/PriorityQueueNode/prev
var/PriorityQueueNode/iter

if(!head)
head = PQN
return PQN

if(head.value > PQN.value)
PQN.nextNode = head
head = PQN
return PQN

prev = head
iter = head.nextNode
while(iter && iter.value < PQN.value)
prev = iter
iter = iter.nextNode

PQN.nextNode = iter
prev.nextNode = PQN

return PQN
I think much of the logic in that can be collapsed into something simpler. If you choose not to, there are at least a few minor optimizations: For one, you could use >= instead of > in your bail-out check. Here's the collapsed form:
PriorityQueue
proc
Add(newitem)
var/PriorityQueueNode/PQN = new(newitem)
var/PriorityQueueNode{prev;iter}

for(iter=head, iter && iter.value<PQN.value, iter=iter.nextNode)
prev=iter
PQN.nextNode = iter
if(prev) prev.nextNode = PQN
else head = PQN
return PQN
Now to Remove():
        Remove(item)
var/PriorityQueueNode/iter = head
var/PriorityQueueNode/prev = null
var/datum/olditem
if(head.item == item)
head = head.nextNode
olditem = iter.item
del iter
return olditem

while(iter && iter.item != item)
prev = iter
iter = iter.nextNode

if(iter)
prev.nextNode = iter.nextNode
olditem = iter.item
del iter
return olditem
return null
One thing I noticed right off is that the olditem var is completely redundant. If you find what you're looking for, olditem==item, so you can just return item.
    Remove(item)
var/PriorityQueueNode{prev;iter}
for(iter=head, iter && iter.item!=item, iter=iter.nextNode)
prev=iter
if(!iter) return
if(prev) prev.nextNode = iter.nextNode
head = iter.nextNode
del(iter)
return item
And your Clear() can be made much faster by just deleting the whole mess. Here's the original:
        Clear()
while(head)
Remove(head.item)
And optimized:
    Clear()
for(var/PriorityQueueNode/iter=head, iter, head=iter)
iter=head.nextNode
del(head)
I think you'll see a marked improvement on Clear(). The others should simply be easier to read. I've found with linked lists that the more you can reduce their code to simple for loops, the better. Extra var assignments just mean that much more can go wrong.

I'll have to try out a linked list solution myself. You might also want to consider an alternative format where PriorityQueue itself is a linked list--or better, a double-linked list--and stores a copy of the value. That way if you're looking for where to add an item, you can loop through queues until you either find the right one, or find a spot to add a new one.
PriorityQueue
var/PriorityQueueGroup/head

proc/Add(datum/item)
var/value = item.CalculateValue()
var/PriorityQueueGroup{prev;iter;PQG}
for(iter=head, iter && iter.value>value, iter=iter.nextNode)
prev = iter
if(!iter || iter.value != value)
PQG = new(item, value)
PQG.nextNode = iter
if(prev) prev.nextNode = PQG
else head = PQG

proc/Remove(datum/item)
var/value = item.CalculateValue()
var/PriorityQueueGroup{prev;iter}
for(iter=head, iter && iter.value>value, iter=iter.nextNode)
prev = iter
if(!iter || iter.value != value) return
. = iter.Remove(item)
if(!iter.head)
if(prev) prev.nextNode = iter.nextNode
else head = iter.nextNode
del(iter)

proc/Clear()
for(var/PriorityQueueGroup/iter=head, iter, head=iter)
iter.Clear()
iter=head.nextNode
del(head)

// all nodes in a group have the same value
PriorityQueueGroup
var/PriorityQueueNode/head
var/value

New(datum/item, value)
if(item) head = new(item)
src.value = value

proc
Add(datum/newitem)
var/PriorityQueueNode/PQN = new(newitem)
if(head) PQN.nextNode = head
else value = newitem.CalculateValue()
head = PQN
return PQN

Remove(item)
var/PriorityQueueNode{prev;iter}
for(iter=head, iter && iter.item!=item, iter=iter.nextNode)
prev=iter
if(!iter) return
if(prev) prev.nextNode = iter.nextNode
head = iter.nextNode
del(iter)
return item

Clear()
for(var/PriorityQueueNode/iter=head, iter, head=iter)
iter=head.nextNode
del(head)

PriorityQueueNode
var
datum/item
PriorityQueueNode/nextNode

New(datum/p_item)
item = p_item
The only down side to this system is that when removing an item you need to call CalculateValue() when removing an item. However if that's a bad idea, I present an alternative Remove() proc that loops through every group instead:
PriorityQueue
proc/Remove(item)
var/PriorityQueueGroup{prev;iter}
for(iter=head, iter && iter.value>value, iter=iter.nextNode)
if(iter.Remove(item)) break // found the group and removed
prev = iter
if(!iter) return
. = item
if(!iter.head)
if(prev) prev.nextNode = iter.nextNode
else head = iter.nextNode
del(iter)

Lummox JR
In response to Theodis
Thanks. I did that and ran more tests, I ran plenty of them adding and removing random data over and over again. No problems occur when I do it, it all seems to work fine.
In response to Lummox JR
An idea occurred to me just after posting, that PriorityQueueGroup could be redundant when it only has one node. You could try this out for size instead:
PriorityQueueNode
var
datum/item
value
PriorityQueueNode{nextNode;nextGroup}

New(datum/p_item)
item = p_item
value = item.CalculateValue()

proc/Add(PriorityQueueNode/node)
if(nextNode) node.nextNode = nextNode
nextNode = node

// returns the new head of list; item if nothing found
proc/Remove(delitem)
var/PriorityQueueNode{prev;iter}
for(iter=src, iter && iter.item!=delitem, iter=iter.nextNode)
prev = iter
if(!iter) return item
if(prev)
prev.nextNode = iter.nextNode
del(iter)
return src
// this deletion may be redundant; the garbage collector should take it just fine
spawn(1) del(src)
if(!nextNode) return nextGroup
nextNode.nextGroup = nextGroup
return nextNode

proc/Clear()
var/PriorityQueueNode{iter;next}
for(var/PriorityQueueNode/iter=nextNode, iter, iter=next)
next = iter.nextNode
del(iter)
del(src)

PriorityQueue
var/PriorityQueueNode/head

proc/Add(item)
var/PriorityQueueNode{prev;iter;PQN}
PQN = new(item)
for(iter=head, iter && iter.value < PQN.value, iter=iter.nextGroup)
prev = iter
if(!iter || iter.value != PQN.value)
PQN.nextGroup = iter
if(prev) prev.nextGroup = PQN
else head = PQN
else
iter.Add(PQN)
return PQN

proc/Remove(item)
var/PriorityQueueNode{prev;iter;newhead}
for(iter=head, iter, iter=iter.nextGroup)
newhead = iter.Remove(item)
if(newhead != item) break
prev = iter
if(!iter) return
if(prev) prev.nextGroup = newhead
else head = newhead
return item

proc/Clear()
var/PriorityQueueNode/iter
for(var/PriorityQueueNode/iter=head, iter, iter=head)
head = iter.nextGroup
iter.Clear()
del(iter)
That should be an interesting structure. I'd call it a bilateral linked list; it links forward to the next node with the same value, and down to the next node with a different value. Only the "root" node of each forward chain (group) links down to the next, which should save DM from having to go searching for references when a node is deleted. Notice too that PriorityQueueNode/Add() always adds a node at slot #2; because the value is the same, the order is irrelevant, and the 2nd slot is the most convenient.

Lummox JR
In response to Lummox JR
I think much of the logic in that can be collapsed into something simpler. If you choose not to, there are at least a few minor optimizations: For one, you could use >= instead of > in your bail-out check.

Yeah I didn't think of just attaching an equal valued item in front to save time since the order doesn't matter for equal value items.

>       for(iter=head, iter && iter.value<PQN.value, iter=iter.nextNode)
> prev=iter


Wow I didn't even think of using this style it looks a lot slicker :P.

One thing I noticed right off is that the olditem var is completely redundant. If you find what you're looking for, olditem==item, so you can just return item.

Good one I didn't even think about that. I was in the mindeset of testing it as a value then returning the old reference but since they are one and the same it was kinda pointless.

I think you'll see a marked improvement on Clear(). The others should simply be easier to read. I've found with linked lists that the more you can reduce their code to simple for loops, the better. Extra var assignments just mean that much more can go wrong.

Cool. I'll redo though I haven't had a use of Clear() yet since I need to process each item anyway before removing them in the algorithm to clean up the mess my pathfinder makes.

I'll have to try out a linked list solution myself. You might also want to consider an alternative format where PriorityQueue itself is a linked list--or better, a double-linked list--and stores a copy of the value. That way if you're looking for where to add an item, you can loop through queues until you either find the right one, or find a spot to add a new one.

At first I was a bit confused when you stated to use a double-linked list. I was was under the impression that a double-linked list was similiar to a single-linked list execpt you could iterate backwards through the list as well as forwards. After scanning through the code it looks more like a tree structure. But that's just a difference of semantics :P. This is a really awsome idea and I can definantly see how it would improve adding to the list. But a big part of the algorithm is searching based on tile loc to see if the previous way to get to a tile was slower or not. But now that I think about it this way I just need to search the groups past the currently calculated value since it would be pointless to search the faster section since if it's in the faster section I don't want to mess with it. Or maybe I'll just do a cheap hack and store the best value for a tile in the tile itself to avoid the seek if it's unneccisary and if I do need to find it to remove it I'll know which value to find it under based on the tile information.

Thanks a lot LummoxJR this technique will probably be faster by a large order of magnitude especially on searches over a large area :).

[Edit:]
Actually within the groups it may help the algorithm converge faster if I sort the individual items in the groups by the straight distance to the destination, since that is the most likly way to the destination unless you're in something like a maze.
After debugging for awhile I found the source of all my problems. The data structure was perfectly fine and the algorithm was perfectly fine.

I just accidently used src as the parameter for one of my functions rather than T :P. 3 letters were between me and perfection and it took hours of debugging to figure this out.