GML Pathfinding Alternative

[mar_cuz]

Hi guys,

I'm looking for an alternative to A* pathfinding and steering behaviours. Those two styles don't operate the way i need.

I have a lot of objects needing to pathfind at the same time so A* cuases slowdowns and steering behaviours are too slow when changing their target x and y.

Is there anything out there? Or can someone give me an idea on how I could code my own pathfinding?

Thanks.

 

[NicoFIDI]

Imagination will work...

Maybe if a lot of your objects are near (and they move like a pack)
Group them, and use the algorithm only once for the whole group.

Or

Group them in groups of "not a lot" and make the groups take turns to use the algorithm.

But if you want real solutions give real problems.
There's not a superfast way to find any path in any grid.
But your case might have one superfast solution that only works for you.

 

[NightFrost]

Well, A-star is considered a fast pathfinding algo across a graph (in GM pathfinding, always a grid graph). If it is too slow, you may need to rething how you are using it. How steering behaviors are too slow exactly? Their work is influenced by how you set the maximum forces, so if some behavior feels sluggish at changing vector, you need to up how much it can affect your final steering.

Also a note about motion planning: many use it to guide multiple agents to singular target, like a horde of zombies converging on player. This is an inefficient way of going about it. When there is just one target and large number of agents pathfinding to it, flow field & heatmap approach can give better results. There's no handy commands for that in GM though, like how mp commands wrap and hide all the A-star maths, you need to write them yourself.

 

[mar_cuz]

Well, A-star is considered a fast pathfinding algo across a graph (in GM pathfinding, always a grid graph). If it is too slow, you may need to rething how you are using it. How steering behaviors are too slow exactly? Their work is influenced by how you set the maximum forces, so if some behavior feels sluggish at changing vector, you need to up how much it can affect your final steering.

Also a note about motion planning: many use it to guide multiple agents to singular target, like a horde of zombies converging on player. This is an inefficient way of going about it. When there is just one target and large number of agents pathfinding to it, flow field & heatmap approach can give better results. There's no handy commands for that in GM though, like how mp commands wrap and hide all the A-star maths, you need to write them yourself.

Thanks for your reply. I should have been more clear. The steering behaviours aren't slow in their movement but when the target changes, in my game it changes regularly, the objects kind of delay a little before attempting to find the new target. The delay is around 2 seconds (120 fps).

Also for A* there is slowdowns i think because of the size of the grid im using 32x32 squares in a room size over 4000x4000 plus the targets move and change. Also the path movement is not as natural as i would like. I've been testing the mp_potential functions and that gets me closer to what im after.

The flow field you mentioned sounds interesting. Can you please explain a liitle more about that for me and how i might go about implementing it?

 

[Yal]

Also for A* there is slowdowns i think because of the size of the grid im using 32x32 squares in a room size over 4000x4000

The grid has over 15,000 cells with that setup, so it definitely could explain slowdown (especially if EVERY object needs to create the grid and then do the A* algorithm in it, and you have potentially hundreds of them). Perhaps you could use a much bigger cell size (e.g. 100x100) and instead of making a path using the grid, just note down the coordinates of the center of each cell, then smoothly move through those in order using e.g. steering behavior?

 

[Strawbry_jam]

If your environment is static, you could try creating a navmesh.
https://en.m.wikipedia.org/wiki/Navigation_mesh
You would still have to use A* to traverse but that can all be done once when making it and then looking up stored paths. It would be much faster than searching across many 32x32 cells since the polygons can take up a large area and they look more natural. Then once you get to the target polygon you just move to the target point.