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
 

Re: A* pathfinding?

Previous Thread :: Next Thread 
SethDusek5 is not online. SethDusek5
Joined: 26 Mar 2011
Total Posts: 2580
12 Dec 2014 08:33 AM
I have no idea where to start, can somebody explain how to do it?
Report Abuse
SethDusek5 is not online. SethDusek5
Joined: 26 Mar 2011
Total Posts: 2580
12 Dec 2014 09:52 AM
bump
Report Abuse
JarodOfOrbiter is not online. JarodOfOrbiter
Joined: 17 Feb 2011
Total Posts: 20029
12 Dec 2014 10:10 AM
You should look at the wikipedia article for this, it gives you a complete explanation of how it works, and some pseudocode.
Report Abuse
ArbiterOfDeath is not online. ArbiterOfDeath
Joined: 20 Jun 2011
Total Posts: 1458
12 Dec 2014 10:34 AM
Pathfinding is my specialty. A* is a variant of Dijkstra's algorithm. I would first recommend implementing that. It can easily be changed into A* when your finished.

There are many websites offering psuedo code that can almost be translated directly into Lua. You should look at some of them. I recommend creating a fringe with the finish node in it (so that the resulting path will go from start to finish). Every loop evaluated every node inside the fringe, and create a new fringe. This has the effect of a FIFO stack and a breadth first search. To evaluate nodes you can use the workspace:IsRegion3Empty() and create a box around the node. You can place nodes in a table to keep track of parents. For every child, add the child as the key and the parent as the value. That way, when you evaluate the start node, you can check its parent, that its parents parent, all the way back to the finish.

I hope this helps a little. Let me know if you need help with specifics or you've completed it and want to optimize it a little.
Report Abuse
JarodOfOrbiter is not online. JarodOfOrbiter
Joined: 17 Feb 2011
Total Posts: 20029
12 Dec 2014 10:58 AM
"Dijkstra" is one of my favorite words to pronounce.
Report Abuse
SethDusek5 is not online. SethDusek5
Joined: 26 Mar 2011
Total Posts: 2580
12 Dec 2014 04:24 PM
all the examples i've seen assume your world is divided into grids, but in roblox its a lot more complex
Report Abuse
ArbiterOfDeath is not online. ArbiterOfDeath
Joined: 20 Jun 2011
Total Posts: 1458
12 Dec 2014 04:26 PM
Yeah, it is. What you can do is test grid cells to see if a part lies inside of it. In this way you can continue to use a grid. Once you get your first implementation down you could look into using navigation meshes instead.
Report Abuse
SethDusek5 is not online. SethDusek5
Joined: 26 Mar 2011
Total Posts: 2580
12 Dec 2014 04:55 PM
dont understand ^
Report Abuse
SethDusek5 is not online. SethDusek5
Joined: 26 Mar 2011
Total Posts: 2580
13 Dec 2014 06:04 AM
bump
Report Abuse
Spongocardo is not online. Spongocardo
Joined: 06 Sep 2008
Total Posts: 2843
13 Dec 2014 08:08 AM
A* pathfinding can still be used, but ROBLOX have added their own pathfinding service to make it much easier to do so.

http://wiki.roblox.com/index.php?title=Pathfinding

Here's my siggy... Done.
Report Abuse
eLunate is not online. eLunate
Joined: 29 Jul 2014
Total Posts: 13268
13 Dec 2014 08:23 AM
I suggest you actually help yourself out with a precomputed navigation mesh to boot for static elements.
Anyway, A* basically involves choosing a space which is lazily computed to have the least distance, computing a route and then going back and fixing up everywhere it messed up by choosing the spaces that actually take less distance.

Depending on the scale of your game, you can save yourself computing by using multiple variations of the same thing on different grid sizes and stuff (This is seen in large scale RTS games especially)
Report Abuse
lah30303 is not online. lah30303
Joined: 15 Feb 2008
Total Posts: 10027
13 Dec 2014 08:51 AM
There really are better options than A* unless you're going to be making major changes to the map while the game is playing. Precomputing a shortest path to every point on the map from every point on the map with dijkstra's and saving that computation will be enough for most of your pathfinding needs and minor obstacle avoidance (gamedevelopment(.)tutsplus(.)com/tutorials/understanding-steering-behaviors-collision-avoidance--gamedev-7777) is enough to handle small objects that may end up getting in the way on your map.
Report Abuse
ArbiterOfDeath is not online. ArbiterOfDeath
Joined: 20 Jun 2011
Total Posts: 1458
13 Dec 2014 10:23 AM
^ Not true. On a small map, lets say 100 by 100, will take 10000^10000 computations to find the path from every point to every point. That is FAR to expensive. I'd recommend sticking to Dijkstra's algorithm and creating a grid representation using the workspace:IsRegion3Empty() while you are learning. You can change your map representation to something more efficient or add heuristics to your algorithm later. Just get the basics down and you can easily add to it.
Report Abuse
lah30303 is not online. lah30303
Joined: 15 Feb 2008
Total Posts: 10027
13 Dec 2014 11:46 AM
For one thing, it doesn't matter how many computations as long as you have enough space to store them because you're not doing it run-time. The other thing is you shouldn't be calculating the path with 1x1 points.
Report Abuse
lah30303 is not online. lah30303
Joined: 15 Feb 2008
Total Posts: 10027
13 Dec 2014 11:49 AM
I suppose I should have been clearer with what I meant by "point". There are many ways to break the map into sections, but the points should be designated by the map creator (whether it be manually or with some algorithm).
Report Abuse
JarodOfOrbiter is not online. JarodOfOrbiter
Joined: 17 Feb 2011
Total Posts: 20029
13 Dec 2014 11:52 AM
But storing 10000^10000 points is ridiculous. It is much better to just calculate it at runtime. It is very unreasonable to store that many points. And especially since you might need to recalculate it eventually. It just isn't worth that.
Report Abuse
lah30303 is not online. lah30303
Joined: 15 Feb 2008
Total Posts: 10027
13 Dec 2014 11:57 AM
As I said before "unless you're going to be making major changes to the map while the game is playing."

No matter how many points you have stored, if you store them correctly it will always be faster than A*.

Most games don't make significant map changes. Don't include small movable obstacles as walls and use collision avoidance for those instead.
Report Abuse
JarodOfOrbiter is not online. JarodOfOrbiter
Joined: 17 Feb 2011
Total Posts: 20029
13 Dec 2014 12:06 PM
Right. Because that example was only for 100^2 studs. Most maps are bigger than that. And it is even more unreasonable to store (200^2)^(200^2) points. I have no idea how much RAM that would even take. Not to mention "It is not computed at runtime", meaning I need to either store all of the points in a script (That is WAY to big for Roblox scripts by the way) or create a ton of values spammed inside of a Folder or Model. Either way, it sounds really dumb and messy. And then you need to do that PER MAP too! And if you DO make changes to the map, then it is even worse, since you need to recalculate and edit some of the values. This is impractical, IMO.
Report Abuse
lah30303 is not online. lah30303
Joined: 15 Feb 2008
Total Posts: 10027
13 Dec 2014 12:11 PM
"As long as you have enough space to store them" - I said this before
Easy to store them in a modulescript with a plugin - If you don't have enough space, you are using too many points
I clearly explained before your arguing that by "point" I did not mean "every Vector3 on your entire map" and that the map creator should have a way of specifying where the points should be, whether by algorithm or manually placing them.
Report Abuse
StealthKing95 is online. StealthKing95
Joined: 13 Dec 2008
Total Posts: 4263
13 Dec 2014 12:14 PM
"I suggest you actually help yourself out with a precomputed navigation mesh"

I do this but with a nodegraph, not navmesh.
I am willing to share technology behind my pathfinder if necessary.
Report Abuse
StealthKing95 is online. StealthKing95
Joined: 13 Dec 2008
Total Posts: 4263
13 Dec 2014 12:16 PM
also if someone thought about precomputing all possible paths between all the precomputed nodes, it's not possible. Eats way too much space. I had a map with 160 nodes and the amount of possible paths was 25600 so where would you store 25600 paths? Nowhere in roblox. Trust me guys I tried.
Report Abuse
GreatOculus is not online. GreatOculus
Joined: 30 Aug 2009
Total Posts: 2103
13 Dec 2014 12:32 PM
Haha.

Pathfinding still amazes me. Recently made an implementation of dijkstras (I tried to spell it, I apologize in advance), that works pretty well. Only problem is that it computes according to which node is closest to the coordinate. Thus, if 1 direction was longer over all, but the initial node was shorter than the other direction, it would go the long way.

Btw, Roblox's pathfinding service is garbage without some kind of ninja addon. If you're using it for an AI to touch a moving player, it just gets NEAR the player and stops. Never actually touches them.
Report Abuse
JarodOfOrbiter is not online. JarodOfOrbiter
Joined: 17 Feb 2011
Total Posts: 20029
13 Dec 2014 12:33 PM
Yay, StealthKing! Someone who actually knows what he is doing!
Report Abuse
lah30303 is not online. lah30303
Joined: 15 Feb 2008
Total Posts: 10027
13 Dec 2014 12:36 PM
-modulescript inside each node
-each modulescript has dictionary with each other node as keys, linking the next adjacent node to reach said key node on the shortest path as the value

Can ROBLOX really not handle that?
Report Abuse
BowtieMod is not online. BowtieMod
Joined: 01 Apr 2013
Total Posts: 804
13 Dec 2014 12:37 PM
Pathfinding <3333

I personally like to use Bellman-Ford, as it can handle negative costs (which still have a purpose even in pathfinding).
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