MP grid with weights

[ViareJhun]

Is your feature request related to a problem?

I need to find a path with different weights for cells. To do this, I created my analog of mp_grid with weights. I also had to create my path find function.

The problem is performance. This creates a really big problem in the game I'm working on. There are large spaces and the path is calculated to the mouse position. When I start moving the mouse, the FPS drops really badly (down to 5-20 on YYC on my intel i7).

I think this bad performance is because mp grid is implemented natively and my function is not. In some cases (like in the picture), the performance difference reaches up to 400x.

Describe the solution you'd like

I would like a native implementation of weighted pathfinding. Either as a separate structure or as an extension to mp_grid. This is probably the only way to solve the performance issue.

Describe alternatives you've considered

Not sure about DLL libraries - they cut off cross-platform and it's not clear how to pass a lot of information about the whole grid.

Other implementations of pathfinding with weights in Game Maker also suffer in performance.

YYC hardly helps. The difference is still very high in cases with large open spaces (avoiding such cases is impossible due to the game specifics).

(on the screenshot is pathfinding with YYC)

Additional context

I attached a sample, where I compared my system with weights and built-in system, you can check performance difference there. mp_grid_with_weights.zip

[Alphish]

Another potential alternative would be exposing the built-in A* algorithm and have it work on an arbitrary graph, though I'm afraid making it available would be more of a new runtime thing, considering the data formatting needed. ^^'

(on the other hand, being able to set one's own nodes and links with their distances would be greatly useful, not only for weighted nodes - which can be simulated by setting links distance as "node1 weight + node 2 weight" - but for different types of layouts such as hexagonal grids as well!)

[attic-stuff]

i would love for native A but i don't want an even-slower mp grid. good and proper A needs to be able to assign weights to coarse and fine, arbitrary nodes and then the agents moving on the graph need to be able to have their calculation spread across multiple frames, in a queue.

would love to see an advanced path layer in the room editor where you could set this up and tie it to tilemaps, including buckets you can put your instances in to tell them to execute their step event every N frames to really speed pathfinding up. i would wait a couple more years for this feature for it to be done just right, even!

(that being said, fast native gml A* is definitely possible but it definitely takes some work. you gotta throw nodes-as-constructors-or-objects out the door and use bitfields or tilemap masks, you gotta setup a queue system so that homies are not calculating every frame, you gotta learn to put a hierarchy in place so speed up the graph traversal, cache neighbors when you can, etc etc. all possible in gml but at the cost of every ounce of your free time and you will forget what your mom's name is.)

[RichardHM91]

really need it!