GML mp_grid what happens under-the-hood?

xDGameStudios

GameMaker Staff
GameMaker Dev.
I wanted to ask YYG team or someone that knows this, what implementation is used
by the mp grid pathfinding under the hood?

1) A* + normal grid?
2) A* + QuadTree?

Is it even A*?
I've been looking at some algorithms and wanted to know how can pathfinding in GMS2 can be made better (more flexible + faster)
 

Evanski

Raccoon Lord
Forum Staff
Moderator
im not sure what happens under the hood, but mp_grids are pretty fast and flexible as is, I made a dynamically updating path find grid and it updates its path in milliseconds, and all im telling it is to recheck the cells and update the grid then find a path through that grid, it does all of that in a blink of a eye, so TL;DR im not sure how much faster/flexible you'd want it to be
 

FrostyCat

Redemption Seeker
I would assume it's A* plus a normal grid.
The Manual entry for Motion Planning > Grid Functions said:
The final type of function use a much more complex mechanism based on a grid-based approach (sometimes called an A* algorithm). It will be much more successful in finding paths (although it still might fail) and will find the shortest paths possible but it requires more work on your side to set it up.
 

vdweller

Member
Under normal circumstances any hierarchical approach should blow vanilla mp_ out if the water. The same goes with Jump Point Search if you go for unweighted terrain (although Mr. Harabor claims weighted JPS is doable, just not very efficient for very fragmented terrains).

The problem is that GML is so ridiculously slow (even with YYC) that you would be hard pressed to have any significant benefits with a custom implementation, because at least mp_ runs entirely in-engine.

One interesting approach is, if you don't necessarily want the pathfinding to occur all in one step, and you can afford a few steps, to implement a pathfinding scheduler which only processes a few thousand nodes per step.
 

xDGameStudios

GameMaker Staff
GameMaker Dev.
What if I have a 1000 pixel grid with a 10pixel resolution we are talking a 100x100... 10000 cells isn't it better to make a "navmesh" where we can optimise the number of triangles (nodes) generated and the search should be faster... and it should also generate a less "boxy" path.
Or is not worth and I'll still have a loss in performance?!

@vdweller How would such a scheduler work! you can't calculate half a path can you?! for example you want an agent to move from a given place to target the player.... the target is the player.
Or are you saying a scheduler that will limit the amount of mp_path requested one can make and queue the remaining queries for a later time?
 
Last edited:

vdweller

Member
A scheduler would require your own implementation of A*. It is largely a custom data structure collection which can save the current state of pathfinding and expand nodes as usual in the next step.

A downside is that, unless you want a separate state copy for each entity, other entities will wait for the query to finish, but for a reasonable amount of entities there wont'be any perceivable delay since in practice entities don't all request a path at the same time. Even if a request takes 4-5 steps to finish and your character has moved in the meantime, they won't have moved by much and the chasing entity can course-correct at a later step.
 
Top