generic image
Processing...
  • Games
  • Catalog
  • Develop
  • Robux
  • Search in Players
  • Search in Games
  • Search in Catalog
  • Search in Groups
  • Search in Library
  • Log In
  • Sign Up
  • Games
  • Catalog
  • Develop
  • Robux
   
ROBLOX Forum » Game Creation and Development » Scripters
Home Search
 

Special Pathfinding

Previous Thread :: Next Thread 
nickmaster24 is not online. nickmaster24
Joined: 04 Oct 2008
Total Posts: 8906
28 May 2012 06:18 PM
I have a node network that is made of Human-Placed nodes that are compiled into a table that holds each's x and z position and the nodes that are accessible from it. How would y'all recommend I path-find through the list?

BTW, I did the list this way so I can check things like "cover" (if the node can be used for cover from a particular enemy and stuff of that nature. Maybe in the future there can be "Healing Stations" and stuff :P


~Read Between The Squiggles~
Report Abuse
Brandonhare is not online. Brandonhare
Joined: 02 May 2007
Total Posts: 11005
28 May 2012 06:54 PM
A*
Report Abuse
ENET is not online. ENET
Joined: 01 Jan 2010
Total Posts: 4820
28 May 2012 07:33 PM
I made parts in my game and before the game is uploaded I compile them to a table. Via ray-casting. If one part can see the other then it is assumed it can make it from point a to point b and compiles that as a path. I could make it do it at runtime, but I find it better to just compile it before upload since its a static node set anyways.
Report Abuse
Varp is not online. Varp
Joined: 18 Nov 2009
Total Posts: 5333
28 May 2012 07:57 PM
Your Guide to Pathfinding:

1) Can you represent your question as a graph? If yes, go to step 2. Otherwise, go to step 4.
2) Can each node be assigned a cost? If yes, go to step 3. Otherwise, go to step 4.
3) Can a meaningful heuristic be created to estimate the cost to travel between any two nodes? If yes, use A*. If no, use Dijkstra's algorithm.
4) You must be mistaken. Go back to whatever step you came from.
Report Abuse
nickmaster24 is not online. nickmaster24
Joined: 04 Oct 2008
Total Posts: 8906
28 May 2012 08:12 PM
@ENET

Mine compiles on the start and works pretty much the same way. It makes a Global table with all the node positions and which nodes they can go to (I use dah raycast stuffs)


@ENET

So, A*?
Fun, now I get to learn how to use a path-finding algorithm... *Opens YouTu be*

~Read Between The Squiggles~
Report Abuse
nickmaster24 is not online. nickmaster24
Joined: 04 Oct 2008
Total Posts: 8906
28 May 2012 08:18 PM
What is the difference between A* and Dijkstra's algorithm? I mean, you see my situation; what do you think will work best?

~Read Between The Squiggles~
Report Abuse
lah30303 is not online. lah30303
Joined: 15 Feb 2008
Total Posts: 10027
28 May 2012 08:47 PM
I think your set-up is fine for A*
It's only when information is limited that Dijkstra's should be used (and some other specialized reasons).
Report Abuse
nickmaster24 is not online. nickmaster24
Joined: 04 Oct 2008
Total Posts: 8906
28 May 2012 09:01 PM
Can you give me advice on setting A* up?

~Read Between The Squiggles~
Report Abuse
Quenty is not online. Quenty
Joined: 03 Sep 2009
Total Posts: 9316
28 May 2012 09:14 PM
I could, but my adivse is probably bad. I've made about 3 A* AI's, and I think only one of them worked correctly.
Report Abuse
lah30303 is not online. lah30303
Joined: 15 Feb 2008
Total Posts: 10027
28 May 2012 09:17 PM
It's very easy to make logic errors with pathfinding, so just code it carefully.
Report Abuse
ENET is not online. ENET
Joined: 01 Jan 2010
Total Posts: 4820
28 May 2012 09:30 PM
A few more ideas:
Cache the paths nodes take
Report Abuse
MrHistory is not online. MrHistory
Joined: 30 Aug 2010
Total Posts: 5291
28 May 2012 10:24 PM
A* isn't too difficult. I used this:
http://www.policyalmanac.org/games/aStarTutorial.htm
Report Abuse
nickmaster24 is not online. nickmaster24
Joined: 04 Oct 2008
Total Posts: 8906
28 May 2012 10:32 PM
"Cache the paths nodes take."

What?

~Read Between The Squiggles~
Report Abuse
nate890 is not online. nate890
Joined: 22 Nov 2008
Total Posts: 21686
29 May 2012 06:45 AM
Record the paths nodes take.
Report Abuse
Brandonhare is not online. Brandonhare
Joined: 02 May 2007
Total Posts: 11005
29 May 2012 06:47 AM
I've made a heavily commented A* model for people who don't like all the pseudocode and theory.

http://www.roblox.com/A-item?id=71066974
Report Abuse
nickmaster24 is not online. nickmaster24
Joined: 04 Oct 2008
Total Posts: 8906
29 May 2012 10:06 AM
^Yay

~Read Between The Squiggles~
Report Abuse
TheMyrco is not online. TheMyrco
Joined: 13 Aug 2011
Total Posts: 15105
29 May 2012 10:09 AM
Dijkstra, me gusta (he's Dutch ^^).
Report Abuse
MrHistory is not online. MrHistory
Joined: 30 Aug 2010
Total Posts: 5291
29 May 2012 10:11 AM
I thought he was Indian or something...
Report Abuse
TheMyrco is not online. TheMyrco
Joined: 13 Aug 2011
Total Posts: 15105
29 May 2012 10:12 AM
Naw, note the special /ij/ <3
Report Abuse
nickmaster24 is not online. nickmaster24
Joined: 04 Oct 2008
Total Posts: 8906
29 May 2012 11:27 AM
I now understand the algorithm, I think. Time to make it into RBX.Lua code for my AI!

~Read Between The Squiggles~
Report Abuse
agent767 is not online. agent767
Joined: 03 Nov 2008
Total Posts: 4181
29 May 2012 11:49 AM
the dijkstras-algorithm should be better than the A*(I created one a few months ago,a pretty inefficient one-but it works :) )
Report Abuse
nickmaster24 is not online. nickmaster24
Joined: 04 Oct 2008
Total Posts: 8906
29 May 2012 11:51 AM
When I'm done I'll probably have a brand new algorithm :P

~Read Between The Squiggles~
Report Abuse
NXTBoy is not online. NXTBoy
Joined: 25 Aug 2008
Total Posts: 4533
29 May 2012 12:25 PM
> the dijkstras-algorithm should be better than the A*
Doubt it. dijkstras algorithm _is_ A*, except with a heuristic that is always 0.
Report Abuse
nate890 is not online. nate890
Joined: 22 Nov 2008
Total Posts: 21686
29 May 2012 01:13 PM
There are different heuristics, as well. Check out diagonal short-cut, along with euclidean distance,
Report Abuse
nickmaster24 is not online. nickmaster24
Joined: 04 Oct 2008
Total Posts: 8906
29 May 2012 03:17 PM
I'm designing my own :P

~Read Between The Squiggles~
Report Abuse
Previous Thread :: Next Thread 
Page 1 of 1
 
 
ROBLOX Forum » Game Creation and Development » Scripters
   
 
   
  • About Us
  • Jobs
  • Blog
  • Parents
  • Help
  • Terms
  • Privacy

©2017 Roblox Corporation. Roblox, the Roblox logo, Robux, Bloxy, and Powering Imagination are among our registered and unregistered trademarks in the U.S. and other countries.



Progress
Starting Roblox...
Connecting to Players...
R R

Roblox is now loading. Get ready to play!

R R

You're moments away from getting into the game!

Click here for help

Check Remember my choice and click Launch Application in the dialog box above to join games faster in the future!

Gameplay sponsored by:
Loading 0% - Starting game...
Get more with Builders Club! Join Builders Club
Choose Your Avatar
I have an account
generic image