A* in events system: Find lowest F value

0 favourites
  • 3 posts
From the Asset Store
14 amazing sound files of game events like Level Ups, Level Completes, object spawn, object taking etc.
  • Hey Peeps,

    I'm working on a tile based tactical board game. I've implemented the A* path finding algorithm in the events system and it works fine, but its a tad slow. The boards typically range from 15x10 (1.5:1 ratio) so there not huge. One particular part of the algorithm I had to 'hack' together was choosing the lowest F value. I'm not using arrays instead I've got instance variables storing the G,H & F on each tile. This means I need to select the lowest F value which is stored in an instance variable. Currently I'm using: For each ordered (pf_F, ascending) then i stop the loop straight away as it has applied the required actions to the first instance (which has the lowest F value). So I'm wondering is there any possible optimization or more efficient way of selecting the lowest F without calling a for each ordered loop every iteration? I know system: pick instance by instance variable (=, !=, <, >, <=, =>) doesn't exist in C2 currently but it would be great. can anyone help?

  • Try Construct 3

    Develop games in your browser. Powerful, performant & highly capable.

    Try Now Construct 3 users don't see these ads
  • I think if you want better performances you should work with arrays not objects. Unless you're not using a grid based graph (?) otherwise array is probably the optimal datastructure.

    But to answer your question, the "foreach ordered" on top of looping over all instance, probably runs a sorting algorithm before (which behind the scene probably compare each instance with each other at some point so you have like a hidden nested loop).

    Maybe should just do a simple foreach like that:

    +on whatever
        local number lowest = 99999 
        local number lowestUID = -1
    
        + system: foreach object
        + object: variable < lowest
            -> system: set lowest to object.variable
            -> object: set lowestUID to object.UID
         
        + object: pick by UID lowesUID
            -> do whatever
  • If there were multiple that match the low value, instead of picking by the UID you could then "compare variables" to pick all that matched that lowest value Yann's routine found.

    (although that would be even slower, as it its basically a built in "For each" again to select all that match.)

Jump to:
Active Users
There are 1 visitors browsing this topic (0 users and 1 guests)