GML Anyone know why this astar pathfinding...

Discussion in 'Programming' started by mikix, Sep 13, 2019.

  1. mikix

    mikix Member

    Joined:
    May 2, 2017
    Posts:
    343
  2. CloseRange

    CloseRange Member

    Joined:
    Jul 2, 2016
    Posts:
    760
    I have not downloaded or tested this specific package but I have a strong feeling it's probably the implementation.
    In terms of the A* algorithm (btw why not just use the gml built in pathfinding? It uses the A* anyway as far as I'm aware)
    Some things that might cause a slowdown:
    • your cell size is too small
    • you're calling the path finding too frequently / on a lot of objects (the former is less likely if it's only at the start)
    • it isn't the path-finding at all but something else you added to the
     
  3. mikix

    mikix Member

    Joined:
    May 2, 2017
    Posts:
    343
    Gml pathfinding gets me stuck. With this I don't get stuck and I make the player bounce from walls a tiny bit only when he attacks. I put the create pathfinding script on my solid wall object which is 64x64 in size and is duplicated a lot over a 10k x 10k room because before I made a minimap which covered the solid walls in a way that looked great to me. It might be because of that?

    Maybe I shouldnt put it on the solid wall object.

    Edit: Not putting in the solid wall object gets me an error.
     
    Last edited: Sep 13, 2019
  4. OdicHastings

    OdicHastings Member

    Joined:
    Sep 12, 2019
    Posts:
    5
    Did you say 10kx10k? That's pretty big.

    Is there any range limitation on this A* algorithm? And does it do anything to let itself be inaccurate? I have a custom A* pathfinding algorithm I made for my own game. It has to run independently for each creature, but even on a map that's less than 1000x1000 with less than a dozen creatures, it was still causing significant lag until I made major modifications to it.

    Pathfinding seems to just be kind of inherently slow. It takes a lot of processing power. I'm wondering if this A* algorithm you're using is trying to hard too be precise (which can cause lag over even moderate distances), and also isn't stopping itself from trying to form a path over extremely long distances (Which will also cause unbelievable lag even when imprecise)?
     
  5. NightFrost

    NightFrost Member

    Joined:
    Jun 24, 2016
    Posts:
    1,926
    So you're saying your pathfinding graph is about 150x150 (10000 pixels divided by 64 pixel grid cells)? Or that your graph is 10000x10000 with every single pixel set as node? Long-distance pathfinding can be slow even on a 150x150 graph, and on a 10K it would crawl no matter what. The longer the distance between start and destination, the more of the surroundings A* may need to explore due to obstacles. Part of the problem can also be 'pathfinding traps' or large areas that ultimately are discovered to be complete dead ends after A* has spent considerable amount of time exploring them.

    To speed up large maps, one solution is hierarchical pathfinding. In it, you group up sets of grid nodes into supergroups and calculate their connections to similalry generated neighbours, creating a graph that represents their connections on a higher hierarchical level. You perform initial pathfinding on higher hierarchical level and resolve only the immediate group's nodes as an actual path to walk, then the next one after current one has been traversed, until the goal is reached. If the map is completely static, optimally this generation has been done beforehands and injected into the game as pathfinding graph that is immediately usable. On procgenned maps, you'd just have to generate the hierarchies during world generation.

    Here for example is a grid map that has been grouped into 4x4 groups and their connections have been checked (taken from this article):
    [​IMG]
    And here's how it would look as a pathfinding graph for the higher hierarchy (from the same article):
    [​IMG]
    The numbers are precalculated travel distances between the nodes. As can be seen, the hierarchic set forces one to consider a graph as what graphs really are, and understand that grid is just a special case.
     
    OdicHastings likes this.

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice