|
| 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 |
|
|
| |
|
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
|
  |
| 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 |
|
|
|
| 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 |
|
|
|
| 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
|
  |
| 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 |
|
|
|
| 28 May 2012 09:01 PM |
Can you give me advice on setting A* up?
~Read Between The Squiggles~ |
|
|
| Report Abuse |
|
|
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
|
  |
| 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
|
  |
| 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
|
  |
| 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 |
|
|
|
| 28 May 2012 10:32 PM |
"Cache the paths nodes take."
What?
~Read Between The Squiggles~ |
|
|
| Report Abuse |
|
|
nate890
|
  |
| Joined: 22 Nov 2008 |
| Total Posts: 21686 |
|
|
| 29 May 2012 06:45 AM |
| Record the paths nodes take. |
|
|
| Report Abuse |
|
|
|
| 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 |
|
|
|
| 29 May 2012 10:06 AM |
^Yay
~Read Between The Squiggles~ |
|
|
| Report Abuse |
|
|
TheMyrco
|
  |
| Joined: 13 Aug 2011 |
| Total Posts: 15105 |
|
|
| 29 May 2012 10:09 AM |
| Dijkstra, me gusta (he's Dutch ^^). |
|
|
| Report Abuse |
|
|
MrHistory
|
  |
| Joined: 30 Aug 2010 |
| Total Posts: 5291 |
|
|
| 29 May 2012 10:11 AM |
| I thought he was Indian or something... |
|
|
| Report Abuse |
|
|
TheMyrco
|
  |
| Joined: 13 Aug 2011 |
| Total Posts: 15105 |
|
|
| 29 May 2012 10:12 AM |
| Naw, note the special /ij/ <3 |
|
|
| Report Abuse |
|
|
|
| 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
|
  |
| 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 |
|
|
|
| 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
|
  |
| 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
|
  |
| 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 |
|
|
|
| 29 May 2012 03:17 PM |
I'm designing my own :P
~Read Between The Squiggles~ |
|
|
| Report Abuse |
|
|