Path Finding ! Where to now, bob

Xer0botXer0

Senpai
I'm scratching my brain here,

I imagine having around 100-200 npcs wondering around using pathfinding, and another couple dozen driving around using pathfinding.

So, is that a lot of processing ? yes,no, who cares.

Alternatively to the pathfinding functions of GML, I imagine a scenario where because the world isn't large, I'd just set it off on a path, move 100 pixels west, move 150 pixels north, reach destination on left, lerp into garage!

Has anyone tried something like that ? I'm somewhat excited to try such an approach.

I do believe I'd still have to check for collisions with lamps, other npcs, and what ever else comes up in the future, I mean lamps I could just make sure the x/y coordinates are right so it doesn't start off with a line running into a lamp. But for other npcs .. just stop moving ? oh hold on, walk through em! haha

So outdoors I think I'm sorted, but on a smaller more detailed scale there's indoors, I need a system to handle movements. I imagine a 2d array, the first dimension representing the current step, the second dimension holding coordinates for each step, and once the last coordinates are reached then the npc can sit down at the chair until the action sequence has completed then it moves onto the next first dimension of the 2d array.

My primary concern with using GMLs pathfinding is that I've got sidewalks that I want npcs to walk on, and crossroads too. For cars I've got roads. I'd like the cars to be centered in their lanes, and the npcs not straying from their paths.

Suppose the solution to that would be to create invisible collidors around the paths ? and invisible toggle colliders that toggle off collision where a car must turn into a sidewalk.
 
Well, for one, I think you are overcomplicating things, as they should have to check for one (or two with the obj_player) collision each, some kind of par_collider object that is a parent of all the stuff you don't want to bump into.
And the collision checks with solid objects that are not moving could even be irrelevant, as you could mark those areas forbidden from the start and not even consider them in your paths.
Does depend on the style of your game, also, those NPCs in JRPGs move once every couple seconds on a grid, so that simplifies things by a lot.
I'm also betting you won't have 200 NPC on the screen at the same time, so you can always deactivate the stuff that's out of view.
For a game like The Sims, for example, where NPC interact with each other and have some sort of brain, that would be much more involved, you'd have to treat each one of those as it's own player.
 

Yal

šŸ§ *penguin noises*
GMC Elder
The key to good pathfinding performance in GM is to pathfind as little as possible. Using a path is very little processing, while finding it is at least O(N^2) based on room size... per instance. In my current project, objects pathfind once every 5-10 seconds, faster if their target is moving, and switch over to a basic straight line as soon as there's unbroken line of sight.

mp_grids can be reused, so if you don't have moving obstacles (or treat those differently) you can have one grid for pedestrians that have roads marked as obstacles (except where there's crossings), and another for cars that marks anything except roads as obstacles. Not having to fill the entire grid every time you need to pathfind is a huge benefit speed-wise, and you'd lose that if you add moving obstacles to the grid too. So ideally you want to compute an "ideal" path that ignores moving obstacles, and then have some secondary logic to loosely follow the path, but be able to walk around other pedestrians, rubble, cars etc. mp_potential_step approaches where you approach one path point at a time could work for simple cases, or you could do something more advanced like e.g. radial raycasts to tell which direction has the most manoeuverability.
 
Top