Priority Queue, Skew Heap, Fibonacchi heap for A* pathfinder

[toto8080]

I would like to optimise my A* pathfinder by storing it's open list in a priority queue. As far as I know, Ruby - and RGSS3 - does not have a priority queue implementation in its standard library.

Sadly, I'm not an expert in scripting, so I would really appreciate, if somebody could help me with this one.

 

[Kes]

'Scripts' is where people who have written completed scripts that they want to share with others can post them.

[move]Learning Ruby and RGSSx[/move]

 

[MobiusXVI]

I would recommend this post to get you started: https://www.brianstorti.com/implementing-a-priority-queue-in-ruby/

 

[toto8080]

I would recommend this post to get you started: https://www.brianstorti.com/implementing-a-priority-queue-in-ruby/

I already read this article, but the problem is, that I also have to use the 'default' Array methods (each, include?, empty?) in my script on the same array, so I can't just change it to this PriorityQueue, since I'm not enough good in coding and I cannot write these core methods myself. :/

I tried to simply just direct my sorted data (via PriorityQueue) to a simply Array, do the necessarily methods on the 'simple Array' then convert it back to a PriorityQueue. But I bumped an other error this way.. I also tried to subclass the Array class but that also hit a dead end and with the given error I'm not sure why.

 

[MobiusXVI]

Try this then. Add this script to your project: https://github.com/rubyworks/pqueue/blob/master/lib/pqueue.rb

It has built-in methods for things like ‘empty?’ and ‘include?’, and if there’s anything you still absolutely need and it doesn’t have, then you can use ‘to_a’ to get a sorted array to work on. Having programmed an A* Star search myself, I can say that this implementation has everything you need to make it work.