GML Anyone know why this astar pathfinding...

  • Thread starter Deleted member 16767
  • Start date

CloseRange

Member
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
 
D

Deleted member 16767

Guest
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 by a moderator:
O

OdicHastings

Guest
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.
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)?
 

NightFrost

Member
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):

And here's how it would look as a pathfinding graph for the higher hierarchy (from the same article):

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.
 
D

Deleted member 16767

Guest
Don't use that pathfinding script I posted a link to unless you want the game with an inventory script to not be saved. It takes up way too much memory. Not recommended! Use Mp instead.
 
Last edited by a moderator:

Jyrocity

Member
The problem with MP is that it does not allow for weighted tiles. Like water takes 5 points to move, dirt is 2, and concrete paths are 1. Some games are important to have this function. It is frustrating that the built in pathfinding does not have that.
I am currently building a hierarchical pathfinding model. Check out youtube videos for songs of syx. he has a good description of it.
 
  • Like
Reactions: Rob
Top