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

Discussion in 'Learning Ruby and RGSSx' started by toto8080, Apr 24, 2018.

  1. toto8080

    toto8080 Villager Member

    Messages:
    15
    Likes Received:
    0
    First Language:
    German
    Primarily Uses:
    RMVXA
    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.
     
    #1
  2. Kes

    Kes Global Moderators Global Mod

    Messages:
    20,613
    Likes Received:
    10,514
    First Language:
    English
    Primarily Uses:
    RMVXA
    'Scripts' is where people who have written completed scripts that they want to share with others can post them.

    I've moved this thread to Learning Ruby and RGSSx. Please be sure to post your threads in the correct forum next time. Thank you.

     
    #2
  3. MobiusXVI

    MobiusXVI Game Maker Veteran

    Messages:
    359
    Likes Received:
    84
    First Language:
    English
    #3
  4. toto8080

    toto8080 Villager Member

    Messages:
    15
    Likes Received:
    0
    First Language:
    German
    Primarily Uses:
    RMVXA
    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.
     
    #4
  5. MobiusXVI

    MobiusXVI Game Maker Veteran

    Messages:
    359
    Likes Received:
    84
    First Language:
    English
    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.
     
    #5
    toto8080 likes this.

Share This Page