• Advertisement
  • Popular Tags

  • Popular Now

  • Advertisement
  • Similar Content

    • By lucky6969b

      Let's say, on abstract level, the path, namely, A->B->C->D->E is valid, but the agent must choose portal #1 to reach E.... Presumably the agent has chosen portal #2, and go to B, C and D and finally ending up finding itself getting stuck at D and cannot move over to E... The whole computation is wasted. How do I avoid this problem?
      thanks
      Jack
    • By ferreiradaselva
      There are a bunch of path finding implementations online. But, to be honest, I wasn't much satisfied with  most of them, for one of these reasons:
      Dynamic memory allocation in the middle of the algorithm Algorithm that does too much (more than what is needed) Too many files for just a single task So I made this two-files (`uastar.c` and `uastar.h`) library: https://github.com/ferreiradaselva/uastar
      No memory dynamic allocation. Straight to the point (the README.md explains how to use).
      It's nothing biggie, but certainly useful.
      Path finder at work:

      I'm leaving this in announcements, because I probably won't add more features (it's pretty much done).
    • By lucky6969b
      I am not sure I can ask questions about a specific library here, but if you haven't already. I'd like to tag some polys in a navigation mesh that correspond to grass or road etc, I can give an extent to do so, or in another way, I can directly feed a geometry in and the polys are tagged this way. But I am looking into alternative ways such as allowing the user to tag the polys using a text file or bitmap file (like the way heightfields are done).. If I define a area map which is a grayscale  image, and the values range from 0-255, and for example, if the value of the first char is 0, then I can map this index to certain place in the navigation mesh, and say this is a walkable ground etc, unlike heightfields, where you define an image and the resultant thing is some terrain, but when you start off with a bitmap for area map, you end up with what? you see, I had the geometry already, the area map probably doesn't make sense here, same way as the text file thing....
      Any ideas?
      Jack
    • 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?
  • Advertisement
  • Advertisement
Sign in to follow this  

Pathfinding A* pathfind - shortcuts in gridbased-paths?

Recommended Posts

Advertisement
4 hours ago, IADaveMark said:

So no one read my post on JPS+? That's the standard way for not only allowing any angle movement but reducing the complexity of the search space so that your pathing calls are faster to begin with. Seriously... watch the vid with Steve Rabin.

I watched the video you posted but did not see any mention of any-angle pathing.  However I could see how it might be extended it to any angle pathfinding if you allowed more than 8 jump links per node. (i.e. links to all visible intersection/corner nodes).  I looked at the source code and I don't see anything about any-angle support.  Do you have a specific spot where an any-angle implementation is mentioned?

Or did the example he gave in the video just happen to align with 8-direction, and the four diagonals are actually allowed to be any diagonal direction?

Edited by Nypyren

Share this post


Link to post
Share on other sites

Something to mention is that Jump Point Search only works on Uniform cost grids.  So if you have mud tiles that cost more to traverse than road tiles, or whatever, it won't work.

Share this post


Link to post
Share on other sites

You are correct Nypyren -- my bad. At that point, of course, stringpulling and similar are your solutions. An LOS check up the next nodes on the path list until one fails is the simple explanation. Then you just steer towards the last one you can see.

Share this post


Link to post
Share on other sites

With string pulling what about this problem:

I pathfind first. The path it finds prefers road and avoids forest and swamp. But when i start string pulling the found path it will not take terrain cost into consideration. It will find a walkable shorter line shortcutting diagonally over the swamp but it might be slower if the terrain is slower. Right? 

Share this post


Link to post
Share on other sites
3 hours ago, suliman said:

I pathfind first. The path it finds prefers road and avoids forest and swamp. But when i start string pulling the found path it will not take terrain cost into consideration. It will find a walkable shorter line shortcutting diagonally over the swamp but it might be slower if the terrain is slower. Right?

Yes. You should verify that the cost does not increase when you change the path.

I never did stringpulling, but since you know the exact old and new path (I assume), you can easily calculate costs, and they should be equal. (If the new path has higher cost, it's a worse path. If it is lower, your pathfinding is broken.)

Share this post


Link to post
Share on other sites

But the whole point is that I pathfind on a strict gridbased map, and when I string pull I remove nodes so that there is still a walkable path, even though that walking will not be strictly ON nodes (i will cut over the nodes in various angles making walking look less rigid).

When units walk they check the walking speed from whatever node is under them right now. You mean I should do this ("walk" along the new path by incrementing position and check the total travel time) when stringpulling and only remove a node if the new "path" will be faster? (the walking cost CAN and should be lower since the pathfinding only finds paths using "whole nodes" and with stringpulling I will find "other paths" See the pic i posted in the first post.).

Edited by suliman

Share this post


Link to post
Share on other sites

Hmm, I am not sure you should compute the cost of the new path in a different way than you did previously in the grid-based pathfinding stage. It may create all kinds of subtle changes in costs if you do it wrong. (Eg since your new path is subtly cheaper, code may pull the string a bit into the swamp, right until all your cost reduction has been eaten by the swamp.)

A somewhat safer method is to still use the grid-based costs, but use the new path to decide which grid-elements you visit.

Share this post


Link to post
Share on other sites

But if the path is not going strictly across the middle of the nodes in the grid (which is the entire point of this thread) I must use that method right? It's still based on the cost for each tile (the tile has a terrain-type, which translates to a movement cost)

Edited by suliman

Share this post


Link to post
Share on other sites

String-pulling/funnel systems assume that there is no difference in the passability or quality of a path between the 2 points in question. This isn't the case for you, so you can't use it. (You didn't mention movement costs in the first post.)

Obviously you can't easily compare grid-based movement with continuous movement. The path you find across a grid is based on the assumption that you follow the grid. If you're not following the grid then you're not using the path!

It's not even practical to hack this; a naive approach might be to examine the string-pulled path and see how fast it is compared to the regular path, but you'll have to calculate how much of the path crosses each square, consider whether the unit can fit there based on adjacent blocked tiles, etc.

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  

  • Advertisement