|
| 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
|
  |
| 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 |
|
|
|
| 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
|
  |
| 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 |
|
|
|
| 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
|
  |
| Joined: 06 Jul 2009 |
| Total Posts: 9058 |
|
| |
|
|
| 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 |
|
|
|
| 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 |
|
|
|
| 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 |
|
|
|
| 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 |
|
|
|
| 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 |
|
|
|
| 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 |
|
|
|
| 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 |
|
|
|
| 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 |
|
|
| |
|
|
| 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 |
|
|
|
| 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
|
  |
| Joined: 06 Jul 2009 |
| Total Posts: 9058 |
|
| |
|
|
| 18 Oct 2013 05:47 PM |
| Lol. A* is unbelievably easy to implement. Do you need proof? lol |
|
|
| Report Abuse |
|
|
Oysi
|
  |
| Joined: 06 Jul 2009 |
| Total Posts: 9058 |
|
| |
|
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
|
  |
| 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 |
|
|
|
| 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 |
|
|