Epic's Pathfinidng Pack

Epic428

  • Posts: 1118
OK so here is the deal. Suppose I have a list of nodes and all nodes they are attached to (neighbors). These nodes will never move.

Now I have an object that moves. This object is basically a node as well, however, its neighbors will constantly change based off its current position, and whether an object is blocking it's line of sight to that node.

For example, in the screenshot I have attached, all blue circles represent static nodes. All the lines drawn from them go to their neighbors. The red squares are objects blocking the path. They prevent nodes from having certain neighbors.

The green circle is my dynamic node that will constantly be moving. As you can see in the screenshot, only four static nodes are neighbors to the green node (it is possible there are more but for the purposes of this example there are not).

Now, I want this Dynamic node to attach to new neighbors as he moves and the path to them is no longer blocked. I also want him to detach from neighbors when their path becomes blocked.

How do I go about this? Can I use ray-casting for the solution? Would that hinder the performance, and how bad would it if so? Is there a better solution? If I can use ray-casting, how do I do it? (remember these nodes will be invisible, and their coordinates just stored in a list)

Any help figuring this out would be great! If you need more information, ask. Bonus points to anyone who can figure out why I am using nodes and dynamic nodes.

« Last Edit: April 28, 2011, 12:43:41 pm by Epic428 »
James Moore - Official Support & Documentation.
We cannot and will not respond to PM's asking questions. Please make a new thread in the forums if you have any questions, Thank you.
For better support and faster response times, please post your logs regarding any Stencyl related issues. Debug > Logs > Generate Logs

Alexin

  • *
  • Posts: 3132
The API provides a call to check if a line intersects any actor (Ray Casting). In fact, the test game I provided to Derek, which checks for actors at a certain point, can be used. You just have to open the behavior Actor Picker and replace the call in the code block.

For alternate/complementary solutions, I'd investigate and gain a bit of understanding about graphs if I were you.

You're implementing some sort of path nodes. Perhaps for a tower defense game, I don't know.
"Find the fun"
alexin@stencyl.com

Epic428

  • Posts: 1118
Awesome! I thought the actor picker would work, I just wasn't sure exactly how I would go about implementing it. I suppose I will have to play around with it a bit more to understand it better.

Any particular Graph articles you would recommend I read?

Also, You are very close Alexin, Actually I am working on a Pathfinding Resource pack to be used for TDS Games, but could also be used for other games.

I found some awesome code online that I need to heavily modify that includes an A* algorithm for path finding. I may also attempt to convert it over to DM behaviors.

Here is the link for more info: http://lassieadventurestudio.wordpress.com/2008/12/09/a-star-pathfinding/#comment-358

Edit: I wanted to keep the number of Nodes down, and have enemies and the player be dynamic nodes that constantly change values every so many frames or so, in order to be able to develop a more intelligent AI, with minimal work for the end user.  I originally thought of the idea for dynamic nodes, because the thought of grid based movement in a TDS wasn't very good.
James Moore - Official Support & Documentation.
We cannot and will not respond to PM's asking questions. Please make a new thread in the forums if you have any questions, Thank you.
For better support and faster response times, please post your logs regarding any Stencyl related issues. Debug > Logs > Generate Logs

Alexin

  • *
  • Posts: 3132
I don't have any article in particular, but Wikipedia is usually a good start. It will come in handy when, and if, you want to find the shortest path, etc, that kind of things.

I'm not giving you the exact code because I believe you have some understanding of AS3 (or coding in general). Let me know if you have any trouble modifying Actor Picker, though.
"Find the fun"
alexin@stencyl.com

Epic428

  • Posts: 1118
Sounds good. I will see what I can do. And I will let you know if I have any trouble. I did start looking through the API yesterday to see if Box2D had any raycast functions, and I found some similar, so I will see what I can do.

But, thanks!
James Moore - Official Support & Documentation.
We cannot and will not respond to PM's asking questions. Please make a new thread in the forums if you have any questions, Thank you.
For better support and faster response times, please post your logs regarding any Stencyl related issues. Debug > Logs > Generate Logs

Hectate

  • *
  • Posts: 4643
Ah yes, I figured some kind of AI, pathfinding it is. It reminded me of the way that Half-Life AI uses nodes to determine how to effectively reach the player (assuming the mapper has included the necessary entities).
:
:
Patience is a Virtue,
But Haste is my Life.
Proud member of the League of Idiotic Stencylers; doing things in Stencyl that probably shouldn't be done.

Alexin

  • *
  • Posts: 3132
I attached a small game with the essential behavior. It doesn't do anything right now, but it will get you started.
"Find the fun"
alexin@stencyl.com

Epic428

  • Posts: 1118
Thanks Alexin! I will play around with it and try and get this moving over the next few days
James Moore - Official Support & Documentation.
We cannot and will not respond to PM's asking questions. Please make a new thread in the forums if you have any questions, Thank you.
For better support and faster response times, please post your logs regarding any Stencyl related issues. Debug > Logs > Generate Logs

Epic428

  • Posts: 1118
I think I am a bit confused as to how getActorsAlongLine() works. I had assumed that it drew an imaginary line from point A to point B. if any actors intersected that line it would return them.

However, I tried two different ways to make this work and both times no actors were found. Occasionally I would run into the error below:

Code: [Select]
[object AlchemyExit]
at Function/<anonymous>()
at Function/<anonymous>()
at Box2DAS.Dynamics::b2World/RayCast()[/Users/jon/Desktop/stencyl/plaf/flash/Box2DAS/Box2DAS/Dynamics/b2World.as:116]
at stencyl.api.engine::Script/getActorsAlongLine()[/Users/jon/Desktop/stencyl/plaf/flash/root/stencyl/api/engine/Script.as:1201]
at scripts::ActorPickerLine/pick()[C:\Users\James\Documents\StencylWorks\sandbox\flash\scripts\ActorPickerLine.as:69]
at Function/http://adobe.com/AS3/2006/builtin::call()
at stencyl.api.engine.behavior::BehaviorManager/call2()[/Users/jon/Desktop/stencyl/plaf/flash/root/stencyl/api/engine/behavior/BehaviorManager.as:353]
at stencyl.api.engine::GameState/say()[/Users/jon/Desktop/stencyl/plaf/flash/root/stencyl/api/engine/GameState.as:1631]
at stencyl.api.engine::Script/sayToScene()[/Users/jon/Desktop/stencyl/plaf/flash/root/stencyl/api/engine/Script.as:500]
at scripts::Design_1_1_ActorPickerTest/pickActors()[C:\Users\James\Documents\StencylWorks\sandbox\flash\scripts\Design_1_1_ActorPickerTest.as:91]
at scripts::Design_1_1_ActorPickerTest/update()[C:\Users\James\Documents\StencylWorks\sandbox\flash\scripts\Design_1_1_ActorPickerTest.as:73]
at stencyl.api.engine.behavior::Behavior/update()[/Users/jon/Desktop/stencyl/plaf/flash/root/stencyl/api/engine/behavior/Behavior.as:203]
at stencyl.api.engine.behavior::BehaviorManager/update()[/Users/jon/Desktop/stencyl/plaf/flash/root/stencyl/api/engine/behavior/BehaviorManager.as:123]
at stencyl.api.engine::GameState/innerUpdate()[/Users/jon/Desktop/stencyl/plaf/flash/root/stencyl/api/engine/GameState.as:1376]
at stencyl.api.engine::GameState/postUpdate()[/Users/jon/Desktop/stencyl/plaf/flash/root/stencyl/api/engine/GameState.as:1299]
at stencyl.api.engine::GameState/update()[/Users/jon/Desktop/stencyl/plaf/flash/root/stencyl/api/engine/GameState.as:1281]
at org.flixel::FlxGame/update()[/Users/jon/Desktop/stencyl/plaf/flash/flixel/org/flixel/FlxGame.as:343]

I have included a screen shot of my behavior. I first tried it by using mouse presses to create the line. That didn't work. I then thought maybe it has to hit the actor's on their x/y values exactly. So I rearranged my actors so that it was guaranteed to hit a few exactly on each of their x/y's and that didn't work. I combined bother versions in the screenshot.

I even added a print statement in the onActorPick() function, which isn't being printed, so it definitely is not being called.

I can upload game to forge if you'd like to look at it. But I am stumped as to why it isn't working as I think it should.
James Moore - Official Support & Documentation.
We cannot and will not respond to PM's asking questions. Please make a new thread in the forums if you have any questions, Thank you.
For better support and faster response times, please post your logs regarding any Stencyl related issues. Debug > Logs > Generate Logs

Alexin

  • *
  • Posts: 3132
I'll take a look at it today, if I get a chance.
"Find the fun"
alexin@stencyl.com

Epic428

  • Posts: 1118
I put the game up on forge so you can look at it. It is called Actor Picker Line Test.

Thanks again for your help. I couldn't find anything in the API about the getActorsAlongLine() function.
James Moore - Official Support & Documentation.
We cannot and will not respond to PM's asking questions. Please make a new thread in the forums if you have any questions, Thank you.
For better support and faster response times, please post your logs regarding any Stencyl related issues. Debug > Logs > Generate Logs

Alexin

  • *
  • Posts: 3132
The game a gave you yesterday was faulty. I fixed it and improved it a bit to show off the feature, however, it doesn't find anything. I didn't look thoroughly but everything seems fine and I'm not getting any errors.

Did anyone ever used this API call?

(Click and drag the mouse to draw a line. Look at the console.)
"Find the fun"
alexin@stencyl.com

Greg

  • *
  • Posts: 1260
I remember testing it last time when you posted it for someone else, and I recall it working back then.

Epic428

  • Posts: 1118
Yeah, it doesn't seem to be finding anything on my end either. I still get the error I posted above if I single click, and more often if I single click on the actor.

I wish I could see more of the behind the scenes aspect of that line of code. Otherwise, I couldn't say why it isn't finding anything.

Hopefully it is figured out as it seems to be a really efficient way to create my dynamic nodes.
James Moore - Official Support & Documentation.
We cannot and will not respond to PM's asking questions. Please make a new thread in the forums if you have any questions, Thank you.
For better support and faster response times, please post your logs regarding any Stencyl related issues. Debug > Logs > Generate Logs

Alexin

  • *
  • Posts: 3132
I still get the error I posted above if I single click, and more often if I single click on the actor.
The code doesn't check for that corner case since the documentation doesn't refer it. It can be fixed easily, though.

What the docs say, however, is that if the starting point falls right inside a shape, then this same shape is excluded.
"Find the fun"
alexin@stencyl.com