Sign in to follow this  
suliman

Pathfinding A* pathfind - shortcuts in gridbased-paths?

Recommended Posts

Alberth    9525

Maybe your grid-based path calculation is the wrong approach? What if you convert the grid to navmesh, and then do continuous path computation?

Unfortunately, the above sentence is as far as my knowledge goes, I have no idea of implications if you take that approach.

 

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this  

  • Similar Content

    • By Crayz92
      Here are the two main files:
      Path: https://pastebin.com/ZkrbJ78t
      AStar: https://pastebin.com/EVGazFtU
       
      A few things I've done to optimize the search:
      1. Rather than a dictionary to keep track of scores and parents, I use a 2d array of objects that are mapped to the grid i.e. [x,y] represents grid point (x,y).  Objects have F,G,H and Parent fields, these fields are reset to default values during each search.
      2. Cheap weighted heuristic
      3. Orthogonal neighbors (searching 4 neighbors rather than 8)
      Paths don't have to be beautiful because the point reduction smooths them out quite nice. 
      In Path.cs you can see the two functions to reduce points, Incremental and Stretch.  Stretch is much faster because it has the potential to reduce points all the way to the end right off the bat or early on thus reducing calls to the LineOfSight function, but it isn't so reliable around small areas/corners.  The incremental function is reliable but it calls to the LineOfSight function for each and every point along the path, this causes the path reduction to be just about as slow as calculating the path itself. 
      Line of Sight is determined by getting all points between 2 points and checking that they are all flagged as Walkable.
       
      My grid is dynamic and roughly 250x250.  I tried out Theta* and JPS, both were slower than my current A*.  I'm trying to avoid using a navmesh or worker thread, I suppose mostly just looking for ideas to tighten up my code
    • By lucky6969b
      When my program was generating navigation meshes for my geometry, and the extent is 5000x5000 (m), with a cell size of 5.0 meters, it has to generate 250,000 cells, which makes my computer halt, the target object is a truck, which has a radius of about 20 meters, should I give the cell size a value of 20, because I don't really want to use this navigation mesh on one type of vehicle only. I want to use it for vehicles like cars, which has only about 5 meters in radius... the generation speed is a problem while the memory consumption is another.
      Any ideas how to improve this?
      Thanks
      Jack
    • By Jesse "Chime" Collins
      3D Rigger Mixamo Is Making Some Changes
      Originally founded in 2008, Mixamo has been a go-to source for 3D animation and rigging for nearly a decade. On August 28th, 2013, Mixamo launched a platform called Face Plus. It was designed to allow developers or animators turn facial expressions recorded with even a webcam into top-notch 3D animation. This is not unlike what Holotech Studios’ “FaceRig” does for streamers and video creators as well.
      Back this past May 2017, Adobe (publishers of the Mixamo platform since 2015) announced the end of an era. Mixamo’s Face Plus will be removed on August 22nd, 2017, as well as several other free features.
      According to the Adobe post on the Mixamo website, they lay out what is changing and what is staying the same.

      Set out as bullet points in the post, they seem to be cleaning house on the “free” features. But, they are keeping a small handful of their main key points, such as:
      Select and use characters from Mixamo’s Character Collection
      Upload 3D characters to get them ready to animate using the Auto-Rigger
      Apply animations to characters
      Download as an .fbx or .dae
      Noticeably, the list that’s getting 86’ed includes major tools and the ability to save assets from their site:
      The ability to save and retrieve assets in “My Assets”.
      The Face Plus facial animation plugin
      The Decimator polygon reduction tool
      The ability to download Control-rig scripts
      Download types for .bvh and .biped that streamline integration with 3rd party applications
      Mixamo forums will close and all help articles will be moved to Adobe’s HelpX
      Don't Worry! There's still time!

      They’re allowing people to still download the tools and plug-ins until August 22nd, as well as utilizing their easy-to-download features of saving Assets directly. Those that use Mixamo, utilize Face Plus, or even just do animation are highly encouraged to take advantage and download the tools for the next week.
      To download, sign into your (free) Adobe account at the Mixamo website and start downloading. Developers have only one week left to grab as much as they can. For a complete FAQ and how-to for the Mixamo massacre, check out the Adobe post from their Customer Care Team.
      UPDATE (8/15/17): Adobe would like to stress that Mixamo, itself, is not going anywhere, just the Face Plus features, the tools mentioned above, and a couple other features to make the platform more "streamlined and a little modernized". Once the dust is cleared next week from the changes, I'll reach out to Adobe from a more guided tour of the new set-up. Additionally, I have changed the title of this article to reflect the clarification. Apologies for the inconvenience to those that have already read the article. 

    • By suliman
      Hi
      In a game like stronghold with many workers going back and forth from a workplace to a dropoff-point for example, would I store the path and then use it backwards to not have to redo pathfinding all the time? If the moving units in the city doesnt block movement, very often I could just reuse the old path. Only if i run into a wall (if the player constructs a new building in the path of the old workers) will I recalculate the path.
      Workers in old age of empires for example, do they pathfind every time they go back to drop off gold in the storage?
      Thanks!
      Erik
  • Popular Now