Quenty
|
  |
| Joined: 03 Sep 2009 |
| Total Posts: 9316 |
|
|
| 31 May 2012 06:37 PM |
So the pathfinding I'm doing gets a lot faster the smaller the map is. So I was thinking - if I just provide the map area that is needed to the pathfinder, it would speed up a ton.
However, the real question is... how can I provide the map without slowing down the whole server?
Is/how would it be possible to calculate a big map, and then when needed, pull out smaller bits of the map for the pathfinding. The maps are stored like....
Map[x][y] = 0 or 1...
Because I'm using
http://www.roblox.com/A-Pathfinder-with-binary-heaps-V-1A-item?id=22333228
AI.
Apparently Binary heaps are good until you have about 10,000 plus items in your map, which I have around 260100 (The size of 1 level of terrain). If I reduce it to 25 x 25, which is probably going to be the largest pathfinding anyone's going to be doing in the game, I have 2,500 studs, and I kind of thing the pathfinding will be a bit faster.
However, the on-the-fly pull of the map seems to be slow too, with 0.013472080230713 per a pull on a 50 x 50 area, but a 7.3432922363281e-005 pull on the 25 x 25 area. What is the most efficient way to deal with this.
I'm not sure if the 7.3432922363281e-005 is actually going to be a good thing.
But if I want to precalculate it, and then pull off data sections, how is the best way to do this?
Also, am I doing this right? |
|
|
| Report Abuse |
|
|
|
| 31 May 2012 08:01 PM |
I would suggest fragmenting the map information into something like a filing system.
Lets take a 10000x10000 grid and break that into 100x100 sectors This means you will have 100 sectors
Now if you want to move from one sector to another, it will find the shortest path between the 100 nodes, or sectors, and then you would request the information from the sectors it must pass through, so you only have to parse the information for need
If that makes any sense.
Depending on map size, you might want to break the each node down to a sector containing more nodes and so on, so it has to parse less information.
Incase my point gets lost, I am paranoid, let me simplify: that your make, generalize it into nodes/sectors that may or may not contain more nodes/sectors.
Its like what we did for your dictionary a while back. |
|
|
| Report Abuse |
|
|
|
| 31 May 2012 08:02 PM |
*take your map ... have no idea how that became 'that you make' :| |
|
|
| Report Abuse |
|
|
|
| 31 May 2012 08:04 PM |
THE LOCK IS COMING! WE MUST PROTECT THE REMAINING THREADS!!!
~Read Between The Squiggles~ |
|
|
| Report Abuse |
|
|
Quenty
|
  |
| Joined: 03 Sep 2009 |
| Total Posts: 9316 |
|
|
| 31 May 2012 08:07 PM |
Wait wait. If you divide it up... How do you handle transversing between regions?
As for 'The Lock', I like that 3 of the 13 threads left are mine. :D
|
|
|
| Report Abuse |
|
|
|
| 31 May 2012 08:14 PM |
Take your map, divide it into large nodes.
You are in node1 and you want to be in nodeX Run A*
Get information from the nodes you must travel through to get to nodeX
Run A* with that
repeat for any more sub nodes
Profit???
alternate way
run A* with 200000 nodes
Probably not the best way (navmesh might be better, but a lot of work), but it is probably better than parsing everything. |
|
|
| Report Abuse |
|
|
|
| 31 May 2012 08:17 PM |
If you had the node divided into parts, you could, Uh, idk... Sorry, I can't get pathfinding to work on a small scale yet :P
I've been too busy on my obby xD
~Read Between The Squiggles~ |
|
|
| Report Abuse |
|
|
|
| 31 May 2012 08:23 PM |
Lol, I have yet to play with AI's due to lack of time and am only theorizing based on the what I understand of A*
The problem with what I am suggesting is that there is a fine balance between where this increases efficiency and where this just eats all of your system resources. It depends on map size and number of subnodes, but that should be obvious. |
|
|
| Report Abuse |
|
|
|
| 31 May 2012 08:36 PM |
I have an idea! It may fail horribly but I should suggest.
Have it search the coordinates formed by a rectangle and only search in there. If it failed, search a larger rectangle in the same kinda area or just expand around where the limit to the path finding was.
~Read Between The Squiggles~ |
|
|
| Report Abuse |
|
|
Quenty
|
  |
| Joined: 03 Sep 2009 |
| Total Posts: 9316 |
|
|
| 31 May 2012 09:12 PM |
I'm thinking of finding the smallest and highest X and Y values in the two 'start' and 'end points, and just creating my search area there, plus about 10 nodes or maybe 5.
Then I'll just limit the navigation size to like.... 20 or something. |
|
|
| Report Abuse |
|
|
|
| 31 May 2012 09:17 PM |
Yeah, I like that Idea. You have a nice obby, but the DP is messed up :P
~Read Between The Squiggles~ |
|
|
| Report Abuse |
|
|
NXTBoy
|
  |
| Joined: 25 Aug 2008 |
| Total Posts: 4533 |
|
|
| 01 Jun 2012 05:08 AM |
| Can't you just construct nodes as you need them, rather than storing an entire map? |
|
|
| Report Abuse |
|
|