Path Finding ... don't get lost

Ok, another day, another thread.
Here to keep all info, thoughts, examples regarding path finding together in one place.

Please keep comments to the subject.

@meburningslime , @thebrickccentric and myself will verbally abuse any unrelated posts :slight_smile:

I think we have to split the task?

Path finding for ‘fixed’ level maps.
Path finding for random generated ones.

As in, in a fixed dungeon for example, one could precalculate direction info and save those pointers hidden in the map tiles.
That’s what you kinda mentioned @thebrickccentric ?

Hmmm, precalculate would work perfectly if the target is fixed too
Like Tower defense games :slight_smile:

@TinkerSmith if you use blocks that extract their own positions then send those to an NPC command system then destroys themselves, and only place those on road and the like, I think it would work.

Hmm, kinda like the scanner tile i used in the map generators?
Only purpose … evaluate, submit info … NOW DIE :slight_smile:

Well, starting off, here’s a few articles listing possible pathfinding algorithms (I know they are on Wikipedia; look at the sources). If anyone knows how to implement these in Flowlab, please explain.

meburningslime, you also had a way of pathfinding; could you restate that here?

Actually, roads is a good point.
Roads = pre-defined fixed paths

They only would need a value assigned to them that the moving object can use to find the shortest one.

Ups, I did it again … I said ‘only’ …

The pathfinding is relatively simple once you understand it. Have raycasts test for walls in all four directions, but only is activated if the NPC is facing the same direction. Next, if the raycast hits, then have a boolean randomizer make the NPC turn 90 degrees or -90 degrees. This then turns off the first raycast and starts the one for the proper direction.
On the more complicated part, you can even add in noise sensing! If the NPC gets a message that it hears a noise, then it raycasts in all directions to find the source, then turns to faces it. If it finds no targets, it does not react.

Finds no target as in no clear line of sight?

@TinkerSmith I mean it finds no object that makes that specific noise.

TinkerSmith, are you talking about physical roads? Or do you mean a network of invisible, pre-defined paths?
meburningslime, does your way of pathfinding incorporate a goal? So far to me it sounds like an object-avoidance system (albeit a good one) kind of like in my game I mentioned in the other thread.
An edit: sorry, I didn’t see the top of the thread until now. I’m reading it…

@thebrickccentric this is for stealth and combat based games, such as BOTW, not for TDs.

Either, or @thebrickccentric
Just throwing ideas out, brainstorming.

Physical roads would work for open world style maps. If ‘off path’ the object would just have to find the next road.
But you bring up a good point, invisible paths. A concept we should keep in mind.
Maybe we should agree on the first ‘test subject’ before we run into too many directions, lol

TinkerSmith you mentioned how my way might work on preset maps, and I agree, but I think it could even work on random maps, too. I don’t know how to do this yet, but it could work if there was a way to lock the rotation of those pointers I mentioned into either the rotation or the negative rotation based on where the player / goal is. In other words, if the player is in the line of sight, fine, the pointers just point to the player and enemies following the pointers do, too. But if the pointers are pointing at the player but a wall is in the way, then they revert to a certain rotation that is derived from where they are around an obstacle. The part I cannot figure out yet is how to make them point, for example, up or down.
Ok, I’m really not doing a great job explaining this, so I’m going to try to make a diagram. It’ll take a few minutes . . .
Yet another edit: sorry, I didn’t see your most recent comment before posting this one. By ‘test subject’ do you mean which game we should try it in?

@thebrickccentric , pointers
@meburningslime raycasts, directions
Sounds like the two of you talk about the same thing with different words. Vectors :slight_smile:
(my word, haha)

P.S. nice collection of different algorithms

Here is an attempt at a diagram. Sorry about how messy it is.

I’ve been testing out that site you linked above, and it seems like the fastest or most efficient one is ‘Trace’ set to Manhatttan. Any idea how the ‘trace’ system works?

Nice, thanks for providing the image. Visuals always help.
Vectors … lol

As in @meburningslime idea, the use of raycasts should help a lot.
What I painfully realized when i did the map generator is that FL evaluates every object on the screen every frame anyway. You might have noticed how everything slows down once it starts filling up the 8x8.
So we might as well put that to good use.
I like the idea of having pointers in each cell that show the way to the target.

I haven’t looked into the details yet @thebrickccentric , that page doesn’t work on my phone,lol. I just put it there for inspiration.

But yes, the Manhattan distance is the most common one used on grid based systems. One of the reasons I had a play with it.
It is so freaking simple, lol.

The tracing … we make our own using whatever functionality in FL gives us an advantage like raycasting.
One of the reasons you should take the examples in the link only as visual inspiration, we don’t have half of the functions they use.