Making a pathfinding network (collab)

[Red]

Okay... so, i'm not begging for code, i'm not asking for someone to do this for me, what i'm hoping to acomplish with this thread is a way to brainstorm and implement a waypoint network system to be used with Playmaker (and released as a package once it's fully done and successfully tested to work.) that can be used for pathfinding with enemies.

So, first off, let's assume that the waypoints are placed on the game map...

i've tried to make one that does it dynamically, looking for the objects that are tagged as "Waypoints" (custom tag of course) and collecting them... but unless using arrayMaker (still trying to figure that one out completely) i don't know how i can make it grab all of them, sort through them and sort them from distance from eachother.

another possible thing to consider is to have waypoints broadcast to all other waypoints the location of the object that the "enemies" are pursuing to all the others (as well as what waypoint is doing the broadcasting.) so that whatever enemy is using the waypoint system, it knows where it eventually has to go.

every project (i think) should have at least a bit of brainstorming involved... and IF this thread can get really popular and get all sorts of ideas in it, it could become a resource for those of us looking to do just such a thing.

so, please post your ideas on how you'd get something like this to work. let's also look at the pros and cons too.

[Red]

if this means custom code, that's cool... i'm sure it's do-able (and i'll see about brushing off my coding skills to see if i can find a way to do something like this... if not entirely, at least in part like separate actions for gathering, sorting, broadcasting, etc... it won't be pretty but i hope it'll work.)

still, the brainstorming sessions is still on the ball... and we're a community! so, let's get all community-like and get our thinking caps on!

[jeanfabre]

Hi Red,

 Unity beta 3.5 has NavMesh. Have you played with these and seen a the examples provided? I don't think that implementing a pathfinding in playmaker would be wise since a lot of good solution exists. Rather playmaker shoudl expose the appropriate tools and actions to work with them.

ArrayMaker: Where exactly do you hit trouble?

let's assume we want to find the next destination ( not each waypoint to get to the target, but the destination itself) within a set of destinations.

 I think sorting should be done on the fly and per request because obviously, computing the closest point is something unique to each enemy.

the only requests that comes to me would be:

-- enemy requests closest destination

-- enemy requests closest destination with tag "x" ( so that if several teams are competing, a team could choose another team as target and concentrate on that fight, ignoring others).


If you can think of other requests, share them please.


I'll be working this week end on an unity package doing just that and using arrayMaker. I don't expect any difficulty, you just basically go through each elements and compare store in a variable the smallest distance found with the currently found closest waypoint. I could automate this in an action yes, but I'll see how much states and action it involves first.

As for the actual pathfinding computation to have your enemy actually go to the waypoint, This will then be up to the developer to choose a tool, simplepath, unity 3.5 NavMesh, or others.


 Bye,

 Jean

[Red]

haven't tried the navmesh... and since it's apparently a pro-only feature, i'm hesitant to try and rely on it since i'm using the free/indie version.

as for arraymaker, until it ships stock with playmaker, it's one less step for the user to use (though to be frank, i do find it to be confusing... though the examples are nice, it doesn't really help me to understand how to properly use it for what i need. reason i suspect is that i'm not a decent coder so a lot of the terminology is lost on me... i can hack my way through simple scripts but more complicated ones make my head spin... which is why i opted for playmaker in the first place.)

for the "enemy requests closest destination" that sounds like it could be managed by having an overall parent of the waypoints that handles the request... and it could help keep the system clean so that you could implement multiple networks for different classes of enemies. i'll give that one a shot to see what i can do with it... to broaden on that, having multiple gameObject variables for player 1, 2, 3, etc could help... and "player 1 nearest node" could help that too... and to cut down on cycles used, make it iterate through that particular feature by restricting it to check every X frames or seconds (maybe .25 seconds?)

so, the endpoint could be accessed through this... next would be to sort through the nodes to calculate the shortest path that the enemy needs to take.

i was thinking, however, that in order to assess wether it would need to use the network or wether it just goes ahead could be a raycast to determine if the path between the enemy and the player is obscured, use the node... else, just move towards...

[jeanfabre]

Hi,

 Yes, NavMesh will be a pro only feature unfortunatly, but there are other solution s on the asset store that are a lot cheaper like simple path.

 What do you find confusing in arrayMaker? don't hesitate to report any thing you don't like, or would like changed or clarified. Is it the cheer number of options on some actions like set and get? or simply how should you work with them and how all these actions and array can work together? It is true that a good understanding of what an array is and what it can do for you is required. For this, studying examples is the best way to get an idea of what is at stake. Also ask for case study on this forum.

I have created a package with a live sorting fsm, that doesn't use any custom actions specifically, that is, it's using arrayMaker as is and playmaker as is. To work it out, run the scene, and in the scene view, move the various gameObjects and watch the sorting in action ( colors span from red to white depending on the order).

the main fsm to look at is in "Team A", I tried to dissect as much as I could to make the process clear.

I also run some timing to check how lon it takes, and it's just plain fast! to sort 5 objects against a target, it take on my computer around 0.0004 ( it takes around 0.008 the first time, because I create dynamic arrays components, and creting components is know to take time, so I do it only once).

So, have a go at this, and take it to pieces. If you have any questions, don't hesitate. I will also work some more on this example and ship it with the next arrayMaker release.

for more advanced readers: Yes, tons os process can be improved with some custom actions here and there, but even with not bothering and checking vector distances instead of sqrDistance, and other obvious costly api calls, It still is very fast. If the sorting array starts to be big, this will become an issue obviously. I also set up a movement detection ( no custom actions there neither) with a threshold setting, so that as you move a gameObject, it only fire a sorting event if it moved more than the threshold values. A single custom action could be created to do the gameObject sorting within an array, this is something that would make sense.

 The next steps would be to make this sorting evolve so that colors are not hardcoded but interpolated instead ( say red for closets, white for farthests, and then interpolate the color depending on the distance). and more "team" based options, but that's already going too far as far as the sorting algorithm

Bye,

 Jean


Bye,

 Jean

[Darnen]

Hi Red, I have created a waypoint system using Playmaker, although it isn't a set pathfinding it is more of a random path function. It finds random "points" on a map and goes to it, and then it uses collisions to detect if it can continue on to that point or not, once it hits something it recalculates its path and goes towards another random "point" in the map. If this is what your looking for I will be willing to share it with the community. Although I am sure all of you could make it better, like everything I make it has bugs .

[jeanfabre]

Hi,

 Don't hesitate to share it, even if it's a work in progress or not stable, it's always a positive thing, and the community can then help you improve it and make it stable.

If you'd like me to have a look and sanitize it, I'd be happy to do so.

 Bye,

 Jean

[Red]

alrighty, i've been able to sort out how to make it do on-the-fly tests between two waypoints to determine which the player is closest to... but, i think i may need to figure out how to do a custom animation to do a test on more than one (comparing which float is bigger/smaller than the rest.) might take some time but if i can figure this out as a separate script, i might be able to make it into an action (assuming it's simple enough to just append the right bits into it.)

so, step one is to make it test 3 and return which one is bigger/smaller (i think this should be solvable fairly easily with a small amount of code.)

next step, figure out how to make it do X tests where X is set by the user.

then the next step after that is to make the X tests selectable by the user OR via an int variable.

i'll see what i can whip up (though i'm going to check the action requests sub-forum first to see if something like this has already been done... if so, it would save me a headache since coding is definately not my strongest point.)

i know this is going against the whole "want to make it so that you can use it out of the box without adding in custom actions" bit... but i don't see an easy way around that.

i'll post more when i know more or have made some headway into this.

and the test will be done by the waypoint manager as i think this would be easiest.

that being said, if i can get this done, i would like to get your help, Jean, in threading arraymaker into this equation... it would give me a better understanding i would think on how array maker works

unless someone has already cracked this with stock actions... if so, please let me know as i would be greatly appreciative of your efforts.

NOTE: i should probably mention that there is a way around it, but since it would need to go through the list of waypoints and test them recursively, it would get way, way out of hand the more waypoints there are... so, useable for small amounts (such as a very dumb boss monster) but not useful for a large amount of waypoints as would be needed for a regular sized level like you'd see in most modern games nowadays... not to mention that it would probably suck up CPU cycles like a hoover set to shag-carpeting.

[Red]

found a possible workaround, but it uses box colliders and the waypoints set up in a grid system to determine which waypoint has a small collider attached to the player object to tell the waypoint manager which waypoint is currently closest (since i'm setting it up so that the box-colliders don't overlap and have a small gap between them.)

its imperfect and wouldn't be conducive to a setup that can't use a grid-based pattern... so, though it works, it's not what i would consider ideal... so, back to the drawing board i guess.

the custom action to sort floats and choose the largest/smallest is still on-going. if anyone, anyone at all has a better option, i'm more than open for suggestions.

[Darnen]

Alright I will get it ready to submit to the PM Forums so you all can tweak and modify as you wish.

[Red]

cool, i'll definitely take a look and see what i can learn from it.

i have figured out (since i recently found out you can stack FSMs on an object) through migrating code from separate objects to stack onto the objects i am using for the game i'm making that the systems needed to tell the enemies wether to use the waypoint network or to just pursue the player would be very, very simple.

a separate FSM system that tells the FSM controlling the movement via an event sent to it such as "within range/sight" and "use path network."

i've got some spare time tonight so i'm going to forgo the friday night socializing and see about trying to hammer out some ideas and see about implementing them. if it works, i'll post what i have as an import-able package so anyone that's taking part can dissect it to find errors or what.

i'm also going to see about using the recursive system... more to prove to myself that it can be done... and also so that anyone that wants to can see about dissecting that as well.

to be fair, if this ends up working as hoped, maybe we can put together other collaboration threads for other common game mechanics... things like making racing game AI, inventory systems, level systems and even a "random dungeon generator" thing like from the Diablo games? do you think this would be something we can all get behind? (basically, if there is enough demand, maybe a sub-forum for collaborations? maybe weekly challenges for learning and such that everyone that wants to can chip in? this kind of thing works for other communities i've seen, it seems fair to assume that it'd work for this one as well.)

[Red]

So, here's the recursive one... since it's calculating distance it doesn't have a "range" though i have noticed that the values when testing went "unlimited" when the player was off the screen. i haven't pushed these very far but i think it helps show what i meant with the recursive idea. they have triggers on them, you can ignore them (or put them to use :p)

http://fantasy21.comyr.com/Waypoint_Test_system_recursive.unitypackage

did some testing, it doesn't seem to soak up as many cycles as i had thought it would... so, next step is to see about how far i can push this. also going to see about trying to set up the enemy cubie so that it will pursue the player or waypoint depending on wether a raycast can detect the player (simple line of sight.)

there is a gizmo script on the waypoints... did that more for cosmetic reasons... if there's a playmaker set of actions that will do that for me, PLEASE let me know... this is a learning experience for me as well.)

[Red]

http://fantasy21.comyr.com/Waypoint_Test_system_recursive-2.unitypackage

an update to the system... the enemy will do a test as to whether the player is within it's line of sight and determine if they should go to the nearest waypoint or the player... it seems kinda jerky in movement at times... but it does the trick so far. the movement is a bit of a turn-off though.

[Red]

http://fantasy21.comyr.com/Waypoint%20Test%20system%20recursive(hiccup).unitypackage

need some help with this... i'm testing wether a waypoint can see it's neighbours or if it's obstructed.

and for some reason it's not going as planned so a fresh set of eyes would be appreciated.

code currently only on waypoint 1a, not going to spread it around to the other waypoints until i can get this taken care of.

[Red]

really? nobody has any ideas on how to fix this?

mighty discouraging this thread is starting to become.