This is a on-going Document based tutorial about moving ENT's along a WED PATH-line with collision.

Why this and why paths?
Well, when it comes doing NPC route movement , if there is no need for the NPC to seek out and navigate through the game world in a random or shortest/targeted manner, than patrolling a PATH is perfect. Games have used simple 3 or 4 point patrolling actions for over 2 decades to bring movement without random chaos to NPC's. While many people still use entity bread crumb or entity nodes for this movement, Paths work better and with less CPU , memory and Vram cost.
There is very little saving to be had with vector list and tables as Path's basically fill the path list will this data.

But why code it?
The problem is simple. The path instructions we have, either don't work well, don't work easily or in some cases don't do collision checks. Also I kind write code, um that is my thing and all. Lastly learning , writing and using logic can only better us(well me at least - more logic less wildman ).

Could any of the built in instruction be used?
I'm not sure, but probably. Either I was to dumb to make it work or it doesn't work how I'd like.

So what is here?
#Ver 1 simply covers the Path following code I posted long ago. It's and attempt to teach and explain what, how, and why it does what it does. The goal is to empower anyone that needs to mod it(and you will need to). Here is the link to the tutorial GDoc Link to the tutorial
Here is the Original posting http://www.opserver.de/ubb7/ubbthreads.php?ubb=showflat&Number=455440#Post455440

What is coming?
In #Ver 2 - I am placing functionality for handling paths as curves. In my first code the ent follows in straight lines from node to node. This never made me happy in my own projects. I always wanted curving and arc-like movements as well as a touch more randomness. So I'll be adding it. Are there better ways than whatever I do? Yes, sure. Could you do better? Yes sure. But then you have no need to read or follow along with this work. It can really to a tutorial for you if you already know better...

Suggestion Corrections and Documentation fixes should be posted to this tread. I will not trouble shoot code here. I'll happy fix errors in the tutorial and correct or clarify trouble spots. So if you feel need or see a problem or get lost - Post me to look into the issues.

Thanks for reading this and hopeful you find this thread and tutorial helpful.


LINKS
Ver 1 GDoc Link to the tutorial
- Forget the tutorial just give me the files GIVE ME THE FILES!!!!
-Video I couldn't embed in the GDoc(Why Google??) [video:youtube]https://youtu.be/YM4U_nWbFXc[/video]

UPDATES 6-10-2016
A show-before-tell video of the curves from upcoming Doc Ver2 https://youtu.be/DSZibIFWM1w

UPDATES 6-14-2016
I will be suspending writing a tutorial document. However, I will be posting Code File download links and video example. Working on this I got really interested in bezier curve 's and will be posting little implementations of them in many ways(As long as I'm interested in the) in the comping future. Keep a eye out for new links. Unless there is any really need to write this kind of tutorial, than it's easier to post videos and dl links.

Hi Malice, tnx for the tutorial.

Purely from an as easy-to-implement and as flexible/effective as possible perspectives (so ignoring memory and speed reasons),
would entity nodes or gs3d paths be a better solution for environments where height/z also differs much (e.g. inside houses / buildings)?

Hi Reconnoiter,

Each project,its team and its sets of problems has different needs. Both ent nodes and Paths are viable solutions. Gaming companies hire a never ending stream of programmers and scripters because ambiguous,homogenized and easy solutions just aren't possible. <-(That's just to say that both solutions have limits and its as customized as the problem.)

I have planned a combination of both in a future Doc release. So this helps do a little thinking about the 2 solutions. I know in my last project that the ent node solution was to troublesome to write correctly and a lot more code to work.However in other projects and breadcrumb systems I've done ent nodes worked well (I've looking into using the Paths system for breadcrumbs in a future doc.)

The simple answer really is that paths are easier to implement. And ent node are easier to place in editor and more flexible.

However lets go pro-con for each.

Pros ent nodes
- Easier to drop and place it the world with or without WED as the level editor.
- Can be easier to run-time place and adjust(such as popping the ent out of the floor.)
- Allows access to the event system through contact using PUSH values or EVENT_TRIGGER ( However there is a event like option for the path solution)
- Are easier to see and visual debug in the run-time build.
- can be used fully linkless (But this moves out the of scope and is just a old version of AI wayfinding systems that have been replaced by NavMesh like systems and Pathfining alogorithems like A*)
- I'll edit to add more if I think them out

Cons ent node
- System as a wholes require a lot more code to be written to work , as well as a lot more checks and safety measure code.
- No built in linking. Each node has no easy way of knowing if it's in a link-chain and where in the chain.
- Requires special spawn-time ID and linking code to be written. Entities are created at run-time in a random kind of manner, if one ent node spawns out of order -> say node 2 spawns before node 1 there can be identity problems and run-time crashes as it looks for node 1. Again a lot of wait(till) and safety checks.
- Speed and memory -> Not do to PC limits but to the Engines own problems.
- Removes ent's out of max_ent that could be used for bullets, sprites, ect

Pros Paths
- Self linking
- Are basically a data graph of vectors with a little more information.
- Are easier to operate through code.
- Support self branching (each node can lead to 4 different edges)
- Can be used with Region/Region check to create event-like reactions
- Simple to use and set up

Cons Path
- Hard to place in WED
- WED has crashed many times while a was building complex path sets (Really a WED con not a Paths con)
- Can be tedious to place in a level
- does not support the event system
- Are very reliant on the programmers version of movement coding for the path user.
- Has a limits number of skills (6) vs ent's (100 or so)
- Can not be c-traced to cause a reaction( but you can traced to the path node and use inverse to determine if it's in sight [ 0 trace hit nothing saw node clearly] ,[1 trace hit something and it's not the node vector])
- Can not use other c_scan,ect function. (But path_scan can be used to locate the node like c_scan)

Wow that's a lot on the topic. Truth is I'm no master-adapt with ent nodes and I'm writing this series to learn more about paths.

Wayfinding/Pathfinding should use a AI Pathfinding solution. But for basic patrol like behaviors and navigating around obstacles I think path's are best. I hope to see how Path's , ent nodes, and Wayfinding can be combined to create a overall better movement behavior for NPC's and AI.

Hope I gave some kind of answer in all this that helped...

Nice comparison list Malice, kudo's!

Your post triggered me to search some more about it, and I came to an interesting article (http://aigamedev.com/open/review/alienswarm-node-graph/) about how waypoint pathfinding can still be very usefull. The example is about alien swarm.
I also thought about Superku's pathfinding, which was also simple and effective.

I used WED paths previously for patrols paths, where I found them very good. But the more I read about it, they seem pretty bad for letting the enemy lead to the player. For my current project I dont need patrols, others probably do need it so take the following part with a grain of salt:

So I am thinking about ent nodes for the pathfinding. Any editor can place them (I dont used WED ) and in the nodes' action on startup trace + save which nodes the node can see so you get a sort of pathfinding web. Than a smart algorithm in the enemy action to let the enemy pick the best path to the player (save the node IDs in an local array or such). The algorithm is the most difficult part and is still something I working out. But otherwise it would be super easy to setup.

@Reconnoiter

Well your ent-node Pathfinding sounds basically like the AUM Prefect AI or Pruuuufect AI (Whatever George named the last version.) So I'd say just mod that for a algorithm base. I couldn't comment on Superku's pathfinding as I don't recall looking at it. I have never really liked the scream-and-look run-time node setup( c_scan for nodes-scream, then c_trace-look for visible links). At one time George had a version that you ran on the dev side to build a text-file link data graph, then the release candidate loaded the graph from a text file at level start. However if I recall, he said later that the hdd read-time had turned into a handicap. But scream-and-look is crazy to me, because after dev - the released game shouldn't have nodes that change location. So your holding up level loading to scream-and-look for nodes at are always in the same place. Maybe that's not a issue or at-least a big issue for PC's today.

I surely wouldn't use the Path system for Pathfinding. If I couldn't make a NavMesh, or even a texture-read solution that was efficient(And I can't ), than I'd focus on a ent-node solution like you suggest.

I hope to one day have a combination solution that mixes all the ideas and I know the parts the Path systems play in that.

Best of luck and look forward to you Pathfinding solution in your next release.
BTW -> What editor are you using?

, could be, I only took a quick glance at that AUM so could be George has influenced my subconscious of the brain.

, you only need to do it once on startup, and possible once more on if something in the world has really changed (rocks have closed a pathway or whatever). Only for the actor code it would a cost a bit cpu to walk to right nodes, but I dont think that is much. Also I would use vec_dist and than a trace, should be enough, not c_scan or something like that. And just keep track of the closest node on each actor/character through e.g. event_trigger in the node event function.

, lol wtf , that sounds awfully complicated / tedious just to save some time on map loading. Was this a long time ago?

NavMesh is quite complicated, isn't it? From I read, is the best way but can take lots of time to implement.

, tnx, I use my own made editor. Is still has some quirks that I need to change, but its easy and fast to use and flexible (and ofcourse realtime). It is more meant to become a solid map editor that I want to ship with my gs3d game(s) (that is if I can remove all the quirks) or else I will keep it just to make the maps.