Quest for optimal Pathing. menu

User Tag List

Results 1 to 10 of 10
  1. #1
    xzidez's Avatar Member
    Reputation
    12
    Join Date
    Dec 2007
    Posts
    135
    Thanks G/R
    1/0
    Trade Feedback
    0 (0%)
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    Quest for optimal Pathing.

    So Im trying to figure out how the pathing of the bot should be done.

    At first I did the pathing right on D3s navmesh. While this is good and accurate I get some problems while I run around sharp (really sharp only) corners. This when I have my path to follow I remove the first "point" in it when it gets too close to my character.
    Also this causes problems when I want to place weight on my mesh, for example I want to avoid stepping into deadly flowers, bees, frost stuffs...

    Does anyone have any knowledge of pathing on "multilayered navmesh?" (One mesh for path, multiple layers for obstacles to avoid). Do I have to merge all layers into one layer before calculating my path? Every time.. ? seems like quite a bit of hassle.

    So what I did instead is I parse the navmesh into a pointbased mesh system, kinda similar to how openbot for wow worked (apocs work if im not misstaken). Then I add weights to my points, and the heavier the point is the less likley is the bot to pass through it..
    Now this removed the first problems with the first approach, now sharp corners isnt any problem anymore because I have weights on the dots closest to walls / corners, so he runs a bit out. Avoiding stuffs is really simple by just adding weights to the points.
    Instead I introduced new problems... First is that I lose the accuracy of the firs NavMesh.. if I have 4 yards between the dots.. I have an accuracy of 0 <-> 2 yards.. about.. Which is not that bad.. But with increased accuracy, the number of points increase ( a lot )... which hits performance. Larger scenes freeze the bot for almost half a second when added..

    So this is where I am at atm. I think that the normal navmesh wiht multiple layers is the best approach.. probably fastest, accurate.. But I havent seen any resource on this? Does it even exist?

    How have you guys handled it ?
    Anyone with some impressive pathing out there that solves the addressed problems?

    Quest for optimal Pathing.
  2. #2
    MaiN's Avatar Elite User
    Reputation
    335
    Join Date
    Sep 2006
    Posts
    1,047
    Thanks G/R
    0/10
    Trade Feedback
    0 (0%)
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    To solve the corners problem, apply a higher weight to all cells that don't have 4 adjacent neighbors (or also 4 diagonal neighbors). This will make your A* prefer cells that aren't adjacent to a wall.
    To solve the many points problem, apply a point reduction (or graph simplification) algorithm after path generation: Ramer
    If the performance issues occur during path generation, you should probably look to optimize the A* since, even though there are many cells, it's still quite fast.
    [16:15:41] Cypher: caus the CPU is a dick
    [16:16:07] kynox: CPU is mad
    [16:16:15] Cypher: CPU is all like
    [16:16:16] Cypher: whatever, i do what i want

  3. #3
    st0724's Avatar Member
    Reputation
    2
    Join Date
    Feb 2007
    Posts
    60
    Thanks G/R
    0/0
    Trade Feedback
    0 (0%)
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    In my experience, 90% of the time, the performance hit is caused by redundant code/calculations. If you are not into fancy profiling software, add some stopwatch code (i.e. in your load scene code) and go from there.

  4. #4
    xzidez's Avatar Member
    Reputation
    12
    Join Date
    Dec 2007
    Posts
    135
    Thanks G/R
    1/0
    Trade Feedback
    0 (0%)
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Originally Posted by MaiN View Post
    To solve the corners problem, apply a higher weight to all cells that don't have 4 adjacent neighbors (or also 4 diagonal neighbors). This will make your A* prefer cells that aren't adjacent to a wall.
    To solve the many points problem, apply a point reduction (or graph simplification) algorithm after path generation: Ramer
    If the performance issues occur during path generation, you should probably look to optimize the A* since, even though there are many cells, it's still quite fast.
    Hi Main and thanks for the reply
    Do you use d3s own mesh for this? Or you use cells as "points" which i described in my last example. If you use your own, care to tell me some more of how you create it?

    sorry if I was unclear. The performance issue is only when I add a new scene (because I have to cut it up in points).
    And for my actual path finding I use A*.. (one that goes from target and one from source, then grabbing the path when they merge, slightly faster than just regular A*).

    It feels like if you use the "rectangular cells" that are in the normal mesh, it can turn out to be quite funny when adding weigth to the ones near corner? (this is the reason I choosed to make weight points instead).

  5. #5
    MaiN's Avatar Elite User
    Reputation
    335
    Join Date
    Sep 2006
    Posts
    1,047
    Thanks G/R
    0/10
    Trade Feedback
    0 (0%)
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Originally Posted by xzidez View Post
    Hi Main and thanks for the reply
    Do you use d3s own mesh for this? Or you use cells as "points" which i described in my last example. If you use your own, care to tell me some more of how you create it?

    sorry if I was unclear. The performance issue is only when I add a new scene (because I have to cut it up in points).
    And for my actual path finding I use A*.. (one that goes from target and one from source, then grabbing the path when they merge, slightly faster than just regular A*).

    It feels like if you use the "rectangular cells" that are in the normal mesh, it can turn out to be quite funny when adding weigth to the ones near corner? (this is the reason I choosed to make weight points instead).
    We use Diablo 3's own mesh, yeah. I'm a little rusty about internals, but I think we merge the scene's navmeshes to create big navmeshes that we then perform pathfinds on.
    [16:15:41] Cypher: caus the CPU is a dick
    [16:16:07] kynox: CPU is mad
    [16:16:15] Cypher: CPU is all like
    [16:16:16] Cypher: whatever, i do what i want

  6. #6
    xzidez's Avatar Member
    Reputation
    12
    Join Date
    Dec 2007
    Posts
    135
    Thanks G/R
    1/0
    Trade Feedback
    0 (0%)
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Originally Posted by MaiN View Post
    We use Diablo 3's own mesh, yeah. I'm a little rusty about internals, but I think we merge the scene's navmeshes to create big navmeshes that we then perform pathfinds on.

    But how do you handle something like desecration and molten on that?

  7. #7
    xzidez's Avatar Member
    Reputation
    12
    Join Date
    Dec 2007
    Posts
    135
    Thanks G/R
    1/0
    Trade Feedback
    0 (0%)
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Originally Posted by st0724 View Post
    In my experience, 90% of the time, the performance hit is caused by redundant code/calculations. If you are not into fancy profiling software, add some stopwatch code (i.e. in your load scene code) and go from there.
    Ye as I mentioned the performance issue is only when I add scenes. (because I make a "dotmap`?" of the entire scene with 4 yards between the dots). So its not anything that makes the bot playable.. its just that i "stutters" when large scenes are added.. not very nice. But not a huge issue : p

  8. #8
    Jens's Avatar Contributor
    Reputation
    179
    Join Date
    Sep 2006
    Posts
    251
    Thanks G/R
    0/0
    Trade Feedback
    0 (0%)
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Originally Posted by xzidez View Post
    Ye as I mentioned the performance issue is only when I add scenes. (because I make a "dotmap`?" of the entire scene with 4 yards between the dots). So its not anything that makes the bot playable.. its just that i "stutters" when large scenes are added.. not very nice. But not a huge issue : p
    Stop creating the entire dotmap when you meet a new scene then, it's not like you can move an entire scene in less than two seconds anyway, just split up the creating process over several ticks .

  9. #9
    ziinus's Avatar Member
    Reputation
    2
    Join Date
    Nov 2008
    Posts
    22
    Thanks G/R
    0/0
    Trade Feedback
    0 (0%)
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Add weight to nodes "dynamically" for area effect

  10. #10
    xzidez's Avatar Member
    Reputation
    12
    Join Date
    Dec 2007
    Posts
    135
    Thanks G/R
    1/0
    Trade Feedback
    0 (0%)
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Originally Posted by ziinus View Post
    Add weight to nodes "dynamically" for area effect
    Ye this is what I do. works really good tbh
    Last edited by xzidez; 06-01-2012 at 01:55 AM.

Similar Threads

  1. [BUG] Redo Quest for Quest XP! 39+
    By kookoo in forum Age of Conan Exploits|Hacks
    Replies: 6
    Last Post: 06-17-2008, 05:43 AM
  2. A easy way to do the daily bombing quest for high pop servers.
    By mythmaster30 in forum World of Warcraft Exploits
    Replies: 5
    Last Post: 03-29-2008, 07:02 PM
  3. Exploit: Demons Banishing Quest for Ogri'la
    By zzzbug in forum World of Warcraft Exploits
    Replies: 7
    Last Post: 02-24-2008, 01:11 AM
  4. Quest for head butt?
    By palidhjede in forum WoW Items & Quests
    Replies: 2
    Last Post: 09-16-2007, 09:49 PM
  5. Were to find quests for RFC, WC, and SFK
    By xlAnonym0uslx in forum World of Warcraft Guides
    Replies: 0
    Last Post: 09-01-2006, 08:54 PM
All times are GMT -5. The time now is 10:57 AM. Powered by vBulletin® Version 4.2.3
Copyright © 2024 vBulletin Solutions, Inc. All rights reserved. User Alert System provided by Advanced User Tagging (Pro) - vBulletin Mods & Addons Copyright © 2024 DragonByte Technologies Ltd.
Digital Point modules: Sphinx-based search