Sign in to follow this  
suliman

Pathfinding A* pathfind - shortcuts in gridbased-paths?

Recommended Posts

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  

  • Announcements

  • Forum Statistics

    • Total Topics
      628294
    • Total Posts
      2981882
  • Similar Content

    • By Luqman Ibrahim
      Hello guys, I just registered this site and heard from my lecturer that this a good site to talk about certain topics since my research topic are mostly programmer who are experienced with AI can answer the survey.
       
      The reason of the survey below is to understand which is suitable solution for 2d platformer pathfinding for AI and which one is easier to implement for 2D platformer. 
       
      I would appreciate if you guys give your responses for the survey link shared and thank you for spending time answering the survey. Sorry if the survey is a bit hard to understand, I tried to make it understandable as best as I can. Again, thank you!
       
      https://goo.gl/forms/S0etAlAAHL6S5kTI2
    • By baabaa
      Hello hello. I'm in the preliminary design phase for a space based game, and I need some advice on how to approach the AI side of things.
      Here's the situation in a nutshell. Say I'm a space explorer with a spaceship, and I am competing with other space explorers to be the first one to discover things. I have a procedurally generated 2D top-down solar system, and to make things a little simpler, let's say all the planets in the system are static, meaning they are not orbiting their sun. But they all have their gravity wells of varying strength. As a player I have to negotiate newtonian physics around these planets, using engine thrust at the right amounts and timing, to get to where I want. That part is not a problem. I'm also willing to assume non-newtonian rotation so that AI and player do not need to account for appyling torque to get a correct bearing.
      So far I have not mentioned whether this is real-time or turn-based and that's because of my uncertainty around AI.
      Problem is I'm not sure how to approach the AI side of things either way. Ideally I'd like to have an AI that can optimize trajectory for speed and/or fuel efficiency, but I have been able to find precious little on the topic on the interwebs. The best I've found so far is the following article from a decade ago, and it does not really point to a solution: http://playtechs.blogspot.ca/2007/05/pathfinding-in-space.html
      If I can find a good resource on how to pull this off in realtime, I'd like to go that route. At the moment my fallback is using a turn based system for exploration and visualizing the system as a hex grid. Then using A* I could get AI agents to naively assume use of thrust to come to a stand still each time they want to change trajectory, and then add extra thrust to move in the next direction, but I'm worried this would be extremely under-optimized in terms of fuel efficiency and the reach of rival ships as a result. I could also factor in the AI ship's current velocity into the graph search, which would likely greatly increase the search space for pathfinding, but I haven't experimented with it yet to be able to say whether it's viable.
      Any thoughts?
    • By povilaslt2
      Hello, I'm trying to implement enemy pathfinding algorihtm, but i have problem with empty tile collision when moving enemy to node.
       
      For example this image shows how it should move like shown in example:

      But it stucks at last tile:

       
      It happens because enemy collides with right side of "air" tile and then it removes from node list because it "collided", but it works with not "air" tiles of course. How do fix this problem?
      Code:
      void Enemy::generateMoveToNode(AStar::Vec2i lastNode) { auto lastSave = AStar::Vec2i{ 0.0f, 0.0f }; while (!target.empty()) { if (target.back().y == lastNode.y) { lastSave = target.back(); target.pop_back(); } else { moveToNodes.push_back(lastSave); moveToNodes.push_back(target.back()); generateMoveToNode(target.back()); return; } } moveToNodes.push_back(lastSave); } void Enemy::updateTarget(std::shared_ptr<InputManager> inputManager) { if (moveToNodes.empty()) return; // Calculate half sizes. float halfWidthA = getSize(0) / 2.0f; float halfHeightA = getSize(1) / 2.0f; float halfWidthB = 32.0f / 2.0f; float halfHeightB = 32.0f / 2.0f; // Calculate centers. auto centerA = glm::vec2(getPosition(0) + halfWidthA, getPosition(1) + halfHeightA); auto centerB = glm::vec2((moveToNodes.front().x * 32.0f) + halfWidthB, (moveToNodes.front().y * 32.0f) + halfHeightB); // Calculate current and minimum-non-intersecting distances between centers. float distanceX = centerA.x - centerB.x; float distanceY = centerA.y - centerB.y; float minDistanceX = halfWidthA + halfWidthB; float minDistanceY = halfHeightA + halfHeightB; setKey(inputManager->getKeyBinding("Move Left"), false); setKey(inputManager->getKeyBinding("Move Right"), false); setKey(inputManager->getKeyBinding("Jump"), false); setKey(inputManager->getKeyBinding("Duck"), false); // If we are not intersecting at all, return (0, 0). if (abs(distanceX) >= minDistanceX || abs(distanceY) >= minDistanceY) { if (moveToNodes.front().y > ceil(getPosition(1) / 32.0f)) setKey(inputManager->getKeyBinding("Jump"), true); else if (moveToNodes.front().y < ceil(getPosition(1) / 32.0f)) { if (getCanClimb()) setKey(inputManager->getKeyBinding("Duck"), true); } else { if (moveToNodes.front().x < ceil(getPosition(0) / 32.0f)) setKey(inputManager->getKeyBinding("Move Left"), true); else if (moveToNodes.front().x > floor(getPosition(0) / 32.0f)) setKey(inputManager->getKeyBinding("Move Right"), true); } updateInput(inputManager); return; } // Calculate and return intersection depths. float depthX = distanceX > 0 ? minDistanceX - distanceX : -minDistanceX - distanceX; float depthY = distanceY > 0 ? minDistanceY - distanceY : -minDistanceY - distanceY; updateInput(inputManager); moveToNodes.erase(moveToNodes.begin()); } generateMoveToNode: recursive function to generate all nodes.
      updateTarget: updates enemy every frame to check if it hits node and then removes it from list and checks next till no nodes left.
    • 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
  • Popular Now