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: Using Region() Speeds up pathfinding.

Previous Thread :: Next Thread 
ScripterJQ is not online. ScripterJQ
Joined: 22 May 2012
Total Posts: 177
18 Oct 2013 08:37 AM
Use region to get surrounding nodes instead of going through the grid table every time a new parent is picked. You can have up to 1000 nodes and A* still finds a path within 0.1-0.9 millisecs
Report Abuse
zars15 is not online. zars15
Joined: 10 Nov 2008
Total Posts: 9999
18 Oct 2013 09:15 AM
That's actually a brilliant idea! Althrought I simply can't learn A* or any other path finding algorithm, I do understand what you mean by that.
Report Abuse
ScripterJQ is not online. ScripterJQ
Joined: 22 May 2012
Total Posts: 177
18 Oct 2013 09:25 AM
Thanks!
I implemented it into my bots. Without using region, A* taken almost 8 seconds to find a path, but with region, it is lightning fast. Max time to find a path with region is only 1 second. Max time without region is nearly 13 seconds!
Report Abuse
SN0X is not online. SN0X
Joined: 24 Oct 2011
Total Posts: 7277
18 Oct 2013 09:28 AM
cant tell if trolling or simply dont understand

(findpartsinregion3??? compared to mapping with a table??? or something else?? i don't know)

could you explain?
Report Abuse
ScripterJQ is not online. ScripterJQ
Joined: 22 May 2012
Total Posts: 177
18 Oct 2013 09:33 AM
Use FindpartsinRegion to return nodes within 30x30. Instead of going through the nodes table which has over 1000 nodes in it. Repeating through the nodes table every second causes severe lag. But using region will return surrounding nodes without having to search through the entire nodes table.
Report Abuse
Oysi is not online. Oysi
Joined: 06 Jul 2009
Total Posts: 9058
18 Oct 2013 10:20 AM
[ Content Deleted ]
Report Abuse
SCARFACIAL is not online. SCARFACIAL
Joined: 28 Jan 2010
Total Posts: 7970
18 Oct 2013 10:39 AM
FindPartsInRegion3 is less effective. It has a cap on the number of parts it will return in a given region. It would be more useful if roblox git rid of the cap
Report Abuse
ScripterJQ is not online. ScripterJQ
Joined: 22 May 2012
Total Posts: 177
18 Oct 2013 04:38 PM
@Oysi,
I use waypoints. Grid is way too much lag, but I used grid as an example on here. Using node[x][y] wouldn't be very efficient that away.
Report Abuse
reptoslicerguy is not online. reptoslicerguy
Joined: 01 Jan 2010
Total Posts: 2098
18 Oct 2013 04:57 PM
i always feel like a noob when i read this form.
could never make a fully successful pathfinder i tried it worked kinda but some times failed :C
Report Abuse
ScripterJQ is not online. ScripterJQ
Joined: 22 May 2012
Total Posts: 177
18 Oct 2013 04:59 PM
@repost
Don't worry about it, man. A lot of people seem to misunderstand how A* works. But if you fully understand how it does work, I PROMISE, you will be able to make your own A* with only a few lines of code. :D
Report Abuse
chickenman158 is not online. chickenman158
Joined: 18 Jan 2011
Total Posts: 915
18 Oct 2013 05:01 PM
Or you can make a better looking pathfinding algorithm, which would be slower but makes the AI look more real, rather than they always find the fastest way to you.
Report Abuse
reptoslicerguy is not online. reptoslicerguy
Joined: 01 Jan 2010
Total Posts: 2098
18 Oct 2013 05:02 PM
i'm pretty sure i get how it works though.
maybe you can explain it to me better then?
Report Abuse
ScripterJQ is not online. ScripterJQ
Joined: 22 May 2012
Total Posts: 177
18 Oct 2013 05:03 PM
@Chicken,
I already implemented that. My bots A* to "suspicious areas" to investigate, rather directly A* to its target.
Report Abuse
ScripterJQ is not online. ScripterJQ
Joined: 22 May 2012
Total Posts: 177
18 Oct 2013 05:05 PM
@repost
Let me dig up an shorter, older version of my A* source.
Just pm me and I will send it to you.
Report Abuse
reptoslicerguy is not online. reptoslicerguy
Joined: 01 Jan 2010
Total Posts: 2098
18 Oct 2013 05:06 PM
Thanks :)
Report Abuse
chickenman158 is not online. chickenman158
Joined: 18 Jan 2011
Total Posts: 915
18 Oct 2013 05:06 PM
I was not trying to belittle you, by the way. Just a suggestion to the guys who don't know how A* works. It is a neat algorthim. I am not sure how to construct an A* map from an ever changing environment, I am used to just using it for 2D static terrain pathfinding.
Report Abuse
ScripterJQ is not online. ScripterJQ
Joined: 22 May 2012
Total Posts: 177
18 Oct 2013 05:10 PM
@Chicken
I know. And that's why I implemented "Dynamic object avoidance" into my A*. It ray cast around dynamic objects. And then I use a flocking Algorithm so other bots avoid each other.
Report Abuse
Oysi is not online. Oysi
Joined: 06 Jul 2009
Total Posts: 9058
18 Oct 2013 05:33 PM
[ Content Deleted ]
Report Abuse
ScripterJQ is not online. ScripterJQ
Joined: 22 May 2012
Total Posts: 177
18 Oct 2013 05:47 PM
Lol. A* is unbelievably easy to implement. Do you need proof? lol
Report Abuse
Oysi is not online. Oysi
Joined: 06 Jul 2009
Total Posts: 9058
19 Oct 2013 03:13 AM
[ Content Deleted ]
Report Abuse
magnalite is not online. magnalite
Joined: 18 Oct 2009
Total Posts: 2467
19 Oct 2013 05:05 AM
Wat. Region3 faster than a table lookup? Wat?

If your pathfinding is taking that long you are doing something very, very wrong.
Report Abuse
magnalite is not online. magnalite
Joined: 18 Oct 2009
Total Posts: 2467
19 Oct 2013 05:07 AM
Also y u no.

ConnectedNodes[node] = {Nodes that node is connected to}

Report Abuse
Radioaktiivinen is not online. Radioaktiivinen
Joined: 25 Apr 2009
Total Posts: 18629
19 Oct 2013 06:16 AM
Region might be faster if:

-You really have thousands of nodes
-The nodes are placed irregularly (not in a grid, thus direct table lookup wont work)
-The nodes are not far from each other/the part density of the place is small/you are able to ignore all other parts than node parts (so region only returns a few parts for you to go thru)

But there are other ways too:
*Dont find the node the agent is in - if you have a path, you should know which node the agent is heading for . If the agent stops following the path to dynamically avoid obstacles and might move to a completely different location as a consequence, then it makes sense. (but still, it should be a rare operation)

*Write a spatial partitioning thing yourself, it would be less hacky since it wont include other parts and can be customized for the purpose. Eg. Put your irregularly placed nodes into a big grid so you can check a few cells for nearby nodes (which you can also use region for)
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